Loadbalancing auf Parallelrechnern mit Hilfe endlicher Dimension-Exchange-Verfahren / von Holger Arndt. 2003
Inhalt
- Tabellenverzeichnis
- Abbildungsverzeichnis
- Algorithmenverzeichnis
- Vorwort
- 1 Einleitung
- 1.1 Das Loadbalancing-Problem und Matrizen für Graphen
- 1.2 Allgemeines Vorgehen
- 1.3 Anwendungen für Loadbalancing
- 1.4 Parallelrechner
- 1.5 Kommunikationsmodelle und Verfahrensklassen
- 1.6 Anforderungen an Loadbalancing-Verfahren
- 1.7 Häufig verwendete Standardgraphen
- 1.8 Produktgraphen
- 1.9 Bezeichnungen für spezielle Matrizen
- 2 Diffusionsverfahren
- 2.1 Matrizen für Diffusionsverfahren
- 2.2 Einfache Diffusionsverfahren: FOS, SOS und Chebyshev
- 2.3 Endliche Diffusionsverfahren: OPS und OPT
- 2.4 Eigenwerte von Graphen
- 2.5 Stabilität und Sortierung der Eigenwerte
- 2.6 Flüsse
- 3 Dimension-Exchange-Verfahren
- 3.1 Motivation und Einfärbung von Graphen
- 3.2 Matrizen für gefärbte Graphen
- 3.3 Allgemeines Vorgehen zur Konstruktion von DE-Verfahren
- 3.4 Ein erstes Dimension-Exchange-Verfahren: DE-FOS
- 3.5 Endliche Dimension-Exchange-Verfahren
- 3.6 Eigenwerte gefärbter Graphen
- 3.6.1 Mathematische Grundlagen
- 3.6.2 Die Bedeutung von alpha=1/2
- 3.6.3 Zyklus C_n mit geradem n
- 3.6.4 Pfad P_n
- 3.6.5 Zyklus C_n mit ungeradem n
- 3.6.6 Produktgraphen
- 3.6.7 Gitter und Tori
- 3.6.8 Hypercube H_d
- 3.6.9 Zusammenfassung
- 3.7 Flussminimierung
- 3.8 Abschätzungen für Flüsse
- 3.9 Aufwand der Verfahren
- 3.10 Stabilität der Dimension-Exchange-Verfahren
- 4 Verfahren für Produktgraphen
- 4.1 ADI-FOS
- 4.2 SDI-Verfahren
- 4.3 ADI-OPT
- 4.4 ADI-SOS und ADI-Chebyshev
- 4.5 ADI-OPS
- 4.6 Dimension Exchange für Produktgraphen
- 4.7 Laufzeiten
- 5 Details zur Implementierung und Messergebnisse
- 5.1 Allgemeines
- 5.2 Verwaltung der Last
- 5.3 Speicherung der Graphen
- 5.4 Berechnung und Speicherung der Flüsse
- 5.5 Grundlegende Voraussetzungen für alle Verfahren
- 5.6 Synchron oder Asynchron?
- 5.7 Verwendete Rechner und Software
- 5.8 Ergebnisse der Zeit- und Flussmessungen
- 6 Scheduling-Verfahren
- 7 Kurze Ausblicke
- 8 Zusammenfassung der Ergebnisse
- Literaturverzeichnis