Integration von QLSA-MOEAD für präzise Aufgabenplanung in heterogenen Rechenumgebungen

Warum intelligentere Rechnerplanung wichtig ist

Von Erdbebensimulationen bis zu Weltraumteleskopen läuft die Wissenschaft heute auf ausgedehnten Rechensystemen, die viele Arten von Chips mischen – klassische CPUs, Grafikprozessoren und rekonfigurierbare Hardware. Zu entscheiden, welcher Chip welchen Arbeitsabschnitt ausführen soll und in welcher Reihenfolge, ist überraschend schwierig und kann bei schlechter Planung Zeit und Energie verschwenden. Dieses Papier stellt eine neue Methode vor, um diese komplexen Arbeitslasten so zu koordinieren, dass große Jobs schneller fertig werden, die Hardware besser ausgelastet ist und in einigen Fällen weniger Energie verbraucht wird.

Verschiedene Chips, verknüpfte Aufgaben

Moderne Hochleistungsrechner sind „heterogen“: Sie kombinieren CPUs, GPUs, FPGAs und andere Beschleuniger, die jeweils unterschiedliche Stärken haben. Wissenschaftliche und industrielle Anwendungen zerlegen ihre Arbeit häufig in viele kleine Aufgaben, die durch Datenabhängigkeiten verknüpft sind und natürlicherweise einen gerichteten azyklischen Graphen (DAG) bilden. Manche Aufgaben müssen abgeschlossen sein, bevor andere starten können, und Aufgaben laufen je nach zugewiesenem Chip schneller oder langsamer. Die Herausforderung besteht darin, hunderte voneinander abhängiger Aufgaben auf eine Mischung von Prozessoren zu verteilen, sodass die Gesamtlaufzeit kurz ist, die Maschinen beschäftigt statt untätig sind und – für bestimmte Workflows – der Energieverbrauch im Rahmen bleibt. Mathematisch ist dies ein NP‑hartes Problem, das bedeutet, eine vollständige Suche ist für realistische Systeme unpraktikabel.

Warum ältere Methoden nicht ausreichen

Traditionelle Planungsansätze gehen oft von einer stabilen Umgebung aus und konzentrieren sich auf ein einzelnes Ziel, etwa die Minimierung der Fertigstellungszeit. Bekannte Heuristiken wie HEFT ordnen Aufgaben nach Priorität, während Metaheuristiken wie simuliertes Tempern oder Tabu‑Suche den Raum möglicher Zeitpläne nach Verbesserungen durchsuchen. Diese Methoden können auf kleineren oder einfacheren Systemen gut funktionieren, starten aber typischerweise von zufälligen Anfangsplänen, passen sich nicht an, wenn sich die Bedingungen ändern, und haben Schwierigkeiten, mehrere Ziele gleichzeitig zu berücksichtigen – etwa Zeit, Auslastungsbalance der Hardware und Energie. Neuere, auf maschinellem Lernen basierende Scheduler bringen Anpassungsfähigkeit, benötigen jedoch meist große Trainingsdatensätze und besitzen weiterhin keinen prinzipiellen Weg, eine volle Menge von Trade‑off‑Lösungen für mehrere Ziele zu erzeugen.

Ein hybrider Lernende, der plant und verfeinert

Die Autorinnen und Autoren schlagen QLSA‑MOEAD vor, ein hybrides Framework, das drei Ideen verbindet: Q‑Learning, simuliertes Tempern und eine multi‑objektive evolutionäre Technik namens MOEA/D. Zuerst wird ein Q‑Learning‑Agent darin trainiert, Aufgabenreihenfolgen durch Versuch und Irrtum zu erstellen. Er konstruiert wiederholt Zeitpläne, beobachtet deren Laufzeiten und aktualisiert eine Tabelle von „Q‑Werten“, die abbilden, welche Entscheidungen tendenziell zu besseren Ergebnissen führen. Anstatt sich auf feste Regeln zu stützen, lernt der Agent schrittweise gute Muster zur Zuordnung von Aufgaben zu Prozessoren, einschließlich eines Verhaltens bei neu auftauchenden Aufgaben während der Ausführung. Mithilfe dieser gelernten Policy generiert das System einen starken Anfangszeitplan statt eines zufälligen und verschafft dem Optimierungsprozess so einen Vorsprung.

Feinabstimmung und Ausbalancierung konkurrierender Ziele

Anschließend verfeinert simuliertes Tempern den gelernten Zeitplan, indem Paare von Aufgaben vertauscht und gelegentlich schlechtere Optionen akzeptiert werden, um aus lokalen Sackgassen zu entkommen – ähnlich dem Schütteln eines Puzzles, damit es in eine bessere Anordnung fällt. Schließlich betrachtet MOEA/D die Planung als echtes Multi‑Ziel‑Problem. Anstatt alle Ziele zu einem einzigen Wert zusammenzufassen, zerlegt es das Problem in viele Teilprobleme, die jeweils einen anderen Kompromiss zwischen schneller Fertigstellung und gleichmäßiger Prozessorauslastung darstellen – und für einen seismischen Workflow namens CyberShake auch die Senkung des Energieverbrauchs. Ein evolutionärer Prozess erkundet diese Kompromisse parallel und tauscht Informationen zwischen benachbarten Teilproblemen aus, um eine vielfältige Pareto‑Front von Zeitplänen zu erzeugen, bei der eine Verbesserung eines Ziels eine Verschlechterung eines anderen bedeuten würde.

Die Methode im Praxistest

Zur Bewertung der Leistung wurde QLSA‑MOEAD an 20 Workflow‑Fällen getestet, darunter synthetische Fast‑Fourier‑Transform‑ und molekulare Workloads, ein großer astronomischer Bildzusammenfüge‑Workflow (Montage) und die reale CyberShake‑Erdbebensimulation. In 16 synthetischen Fällen lieferte die neue Methode in 14 Fällen die beste Lösungsqualität, verkürzte die Fertigstellungszeiten und verbesserte die Hardwareauslastung im Vergleich zu mehreren fortgeschrittenen Baselines. Für CyberShake, bei dem auch Energie optimiert wurde, erzielte sie zwei‑ bis vierfache Verbesserungen in einer standardisierten multi‑objektiven Qualitätsmetrik gegenüber dem bisherigen Stand der Technik, während sie eine gute Streuung der Trade‑off‑Lösungen beibehielt. In dynamischen Tests, in denen neue Aufgaben unterwegs eintreffen, konnte der gelernte Scheduler in unter zwei Millisekunden reagieren und Pläne viel schneller anpassen, als alles neu zu berechnen – wenn auch gelegentlich mit Einbußen bei der Optimalität, wenn Kommunikationsverzögerungen extrem waren.

Was das für den Alltag bedeutet

Für Nicht‑Spezialisten lautet die Botschaft: Intelligente, lernbasierte Scheduler können große, gemischte Chip‑Computer sowohl schneller als auch umweltfreundlicher machen, ohne ständige manuelle Feinabstimmung. Durch die Kombination eines erfahrungsbasierten Planers (Q‑Learning), einer sorgfältigen lokalen Suche (simuliertes Tempern) und eines Trade‑off‑Erkunders (MOEA/D) findet das vorgeschlagene Framework konstant Zeitpläne, die große Jobs schneller abschließen, teure Hardware besser auslasten und bei einigen Anwendungen den Energieverbrauch senken. Zwar gibt es weiterhin Grenzen – etwa Trainingskosten und Leistungseinbußen unter extremen Bedingungen – die Studie zeigt jedoch einen praktischen Weg zu autonomerer, effizienterer Orchestrierung komplexer wissenschaftlicher und industrieller Workflows.

Zitation: Saad, A., Abd el-Raouf, O., Hadhoud, M. et al. QLSA-MOEAD integration for precision task scheduling in heterogeneous computing environments. Sci Rep 16, 7194 (2026). https://doi.org/10.1038/s41598-026-36916-1

Schlüsselwörter: Aufgabenplanung, heterogenes Rechnen, verstärkendes Lernen, multiobjektive Optimierung, energieeffiziente Workflows