Algorithm Engineering für skalierbare Prozesszuweisung

• Antragsteller: Professor Dr. Christian Schulz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 530122198

In Hochleistungsrechnersystemen hängt die Effizienz der Kommunikation zwischen Anwendungsprozessen von verschiedenen Faktoren ab, wie z.B. der Fähigkeit und Topologie des Kommunikationssystems, den Kommunikationsanforderungen zwischen Prozessen und der Software und den Algorithmen, die für die Kommunikation verwendet werden. Die Nähe der kommunizierenden Prozesse auf demselben physischen Prozessor-Knoten ist für eine schnellere Kommunikation bevorzugt. In großen Supercomputer-Systemen beeinflussen die hierarchische Organisation von Prozessoren, Kommunikationsverbindungen und Prozessplatzierung signifikant die Kommunikationsleistung. Zur Optimierung der Kommunikationsleistung ist eine Zuordnung von Anwendungsprozessen zu Hardwareprozessoren erforderlich, die die Kommunikationsmuster und die Hardware-Topologiebeschreibung berücksichtigt. Eine gute Zuordnung zu finden, ist ein herausforderndes Optimierungsproblem. Dieses Projekt konzentriert sich auf die Algorithmusentwicklung für Prozesszuordnungsalgorithmen, die bekannte Methoden für große Rechensysteme und Anwendungen mit unterschiedlichen Arten von Bedingungen und Zielfunktionen verbessern. Skalierbare Methoden für shared- und distributed-memory Speichermodelle werden entwickelt. Ziel des Projekts ist es, Algorithmen für die Prozesszuordnung und dünnbesetzte quadratische Zuweisungsprobleme zu entwickeln, die teilweise auf der Annahme beruhen, dass Rechensysteme hierarchisch strukturiert sind und die Kommunikationsmuster dünn besetzt sind. Dies umfasst Algorithmen für das One-to-One-Zuordnungsproblem, das allgemeine Many-to-One-Zuordnungsproblem, die Modellerstellung aus Anwendungen, verteilte Algorithmen, parallele Algorithmen mit verteilter Speicherung und dynamische Algorithmen für sich zur Laufzeit ändernde Systeme. Algorithm Engineering wird die Hauptmethodik zur Verbesserung des Standes der Technik in diesem Bereich sein. Das Projekt wird untersuchen, warum verschiedene theoretische Techniken in der Praxis gut funktionieren, und Algorithmen entwickeln die die bestmögliche Leistung erreichen. Wenn möglich, werden Laufzeit- und Speicheranforderungen abgeleitet. Ziel des Projekts ist es auch, theoretische Garantien hinsichtlich der Lösungsqualität für einige Teilprobleme abzuleiten.

• DFG-Verfahren: Sachbeihilfen