Ein deterministisches Job-Scheduling Verfahren für massiv-parallele Systeme am Beispiel Cray T3E

Die vorliegende Arbeit stellt ein deterministisches Scheduling-Verfahren zur Optimierung von Job-Ausführungsreihenfolgen auf massiv-parallelen Rechensystemen vor und beschreibt den Entwurf eines darauf basierenden Job-Schedulers für ein System CRAY T3E unter UNICOS/mk und NQS.Während etablierte Scheduling-Strategien in der Regel genau einen Job nach Kriterien wie Job-Größe oder voraussichtlicher Laufzeit und gegebenfalls unter Berücksichtigung der aktuellen Systembelegung als nächsten auszuführenden Job bestimmen, wählt das vorgestellte Verfahren aus den möglichen Ausführungsreihenfolgen der wartenden Jobs eine optimale Reihenfolge aus. Anhand geschätzter Job-Laufzeiten werden also Ausführungsreihenfolgen vorausberechnet und über eine Bewertungsfunktion miteinander verglichen. Diese Bewertungsfunktion erlaubt die gleichzeitige Einbindung mehrerer Optimierungskriterien wie Systemauslastung, Job-Wartezeiten und die Einhaltung von zusätzlichen Randbedingungen, wie z.B. Job-Prioritäten oder Kontingentvorgaben. Durch eine gewichtete Summation der Einzelkriterien wird zudem eine flexible Kontrolle über einen anzunähernden Kompromiss zur Laufzeit möglich.Die mit diesem Ansatz verbundenen Fragestellungen werden in der Arbeit im einzelnen erörtert. Dies ist insbesondere die Einführung einer kombinatorischen Optimierung des Suchvorgangs nach der optimalen Ausführungsreihenfolge, da die Anzahl zu vergleichender Reihenfolgen mit der Fakultät der Anzahl wartender Jobs wächst. Als geeignete Verfahren werden hier genetische Algorithmen und Mutations-Selektions-Verfahren diskutiert und vergleichend bewertet. Neben der Schätzung von Job-Laufzeiten, die als ein Aspekt des Verfahrens nur angedeutet wird, werden weiterhin die Wahl einer geeigneten Bewertungsfunktion und die Problematik der Defragmentierung auf dem Zielsystem CRAY T3E behandelt und Lösungen für eine Implementierung erarbeitet.Die abschließende Umsetzung in einen Job-Scheduler für ein CRAY T3E - System zeigt die praktische Durchführbarkeit des Verfahrens, das anhand beispielhafter Schedulingsituationen validiert wird. Die Vorteile des vorgeschlagenen Verfahrens zeigen sich insbesondere in der Möglichkeit zur flexiblen Vereinbarung mehrerer Optimierungsziele unter Anwendung einer echten Optimumsuche