Parallelrechner

Inhaltsverzeichnis

1 Einleitung.- 1.1 Einige Meilensteine auf dem Weg zum parallelen Rechner.- 1.2 Die Probleme mit parallelen Rechnern.- 2 Klassifikation paralleler Architekturen.- 2.1 Einführung.- 2.2 Varianten und Ebenen der Parallelität.- 2.3 Parallele Anwendungen.- 2.4 Parallele Programmiersprachen.- 2.5 Parallele Betriebssysteme.- 2.6 Parallele Hardware.- 2.6.1 Parallele Verarbeitungseinheiten.- 2.6.2 Verbindungsstrukturen.- 2.6.3 Speicherstruktur.- 2.6.4 Peripheriestruktur.- 2.7 Klassifikationen.- 2.7.1 Übersicht über Klassifikationen paralleler Architekturen.- 2.7.2 Integrierte Klassifikation von Hardware und Software paralleler Architekturen.- 3 Grundbegriffe der Leistungsbewertung.- 3.1 Die Notwendigkeit frühzeitiger Leistungsabschätzung.- 3.2 Methodisches Vorgehen.- 3.3 Leistungsgrößen: Problemstellungen und Definitionen.- 3.3.1 Globale Verkehrsprobleme und Leistungsmaße.- 3.3.2 Lokale Verkehrsprobleme und Leistungsmaße.- 3.3.3 Populäre Leistungsmaße.- 3.3.4 Spezielle Maße für Parallelrechner.- 4 Grundlagen paralleler Architekturen.- 4.1 Einleitung.- 4.2 Die Ebenen der Parallelität.- 4.3 Unterscheidung der Parallelrechner nach dem Operationsprinzip.- 4.4 SIMD-Architekturen.- 4.5 MIMD-Architekturen.- 4.5.1 Einteilung der MIMD-Architekturen.- 4.5.2 Gemeinsamer Speicher.- 4.5.3 Verteilter Speicher.- 4.5.4 Kommunikation und Synchronisation.- 4.6 Datenflußarchitekturen.- 4.6.1 Das Datenflußprinzip.- 4.6.2 Datenflußarchitekturen.- 4.7 Mehrfädige Architekturen.- 4.8 Verbindungsnetzwerke.- 4.8.1 Systematik.- 4.8.2 Die Verbindungsarten.- 4.8.3 Verbindungsaufbau.- 4.8.4 Arbeitsweise.- 4.8.5 Topologie der Verbindungsnetzwerke.- 4.8.6 Statische Verbindungsnetzwerke.- 4.8.7 Dynamische Verbindungsnetzwerke.- 5 Parallelität auf Block- und Instruktionsebene.- 5.1 Einführung.- 5.1.1 Mikrobefehlsebene.- 5.1.2 Instruktionsebene.- 5.1.3 Blockebene.- 5.1.4 Taskebene.- 5.2 Optimierungsverfahren.- 5.2.1 Datenflußanalyse.- 5.2.2 Kontrollflußanalyse.- 5.2.3 Optimierung von Schleifen.- 5.3 Hardwareeinflüsse.- 5.3.1 Parallelitätspotentiale.- 5.3.2 Ausnutzung von Parallelität auf Instruktionsebene.- 5.3.3 Dynamisches Scheduling.- 5.3.4 Konsistenzprobleme bei Pufferspeichern.- 5.3.5 Beispiele für Mikroprozessoren mit Parallelität auf Instruktionsebene.- 5.3.6 Beispiele für Parallelität auf Instruktionsebene.- 5.3.7 Profiling-Ergebnisse von Beispielanwendungen.- 5.4 Aktuelle Forschungsarbeiten und Ausblick.- 5.4.1 Neue Compiler- und Softwarekonzepte.- 5.4.2 Programmiermodelle für parallele Programmierung.- 5.4.3 Automatische Parallelisierung.- 5.5 Zusammenfassung.- 6 Assoziative Architekturen.- 6.1 Das assoziative Operationsprinzip.- 6.1.1 Assoziative Operationen.- 6.1.2 Die Selektionsphase ?.- 6.1.3 Die Aktionsphase ?.- 6.1.4 Das assoziative Speicherproblem.- 6.1.5 Das assoziative Verarbeitungsproblem.- 6.1.6 Parallelismus in assoziativen Funktionen.- 6.2 Implementierungsformen.- 6.2.1 Die vollparallele Implementierungsform.- 6.2.2 Bit-parallele Wort-sequentielle Implementierungsform.- 6.2.3 Bit-sequentielle Wort-parallele Implementierungsform.- 6.2.4 Die sequentielle Implementierungsform.- 6.2.5 Mischformen.- 6.3 Assoziative Speicher und Prozessoren.- 6.3.1 Prinzipieller Aufbau inhaltsadressierbarer Speicher mit lokaler Speicherung.- 6.3.2 Implementierungen und Konzepte assoziativer Speicher und Prozessoren.- 6.4 Die Programmierung assoziativer Architekturen.- 6.4.1 Assoziative Sprachen.- 6.4.2 Modifizierte Standardsprachen.- 6.4.3 Assoziative Punktionsbibliotheken.- 6.4.4 Unterstützung spezieller Konstrukte höherer Programmiersprachen.- 7 Realisierungen paralleler Architekturen.- 7.1 Einleitung.- 7.1.1 SIMD-Rechner.- 7.1.2 MIMD-Rechner.- 7.1.3 Verbindungsnetze.- 7.2 SIMD-Rechner.- 7.3 MIMD-Maschinen mit verteiltem Adreßraum.- 7.3.1 Topologien.- 7.3.2 Hypercube-Systeme.- 7.3.3 Zweidimensionale Topologien.- 7.3.4 Dreidimensionale Topologien.- 7.3.5 Mehrstufige Verbindungsnetze.- 7.4 MIMD-Maschinen mit globalem Adreßraum.- 7.4.1 Ring-Topologien.- 7.4.2 Dreidimensionale Topologien.- 7.4.3 Mehrstufige Verbindungsnetze.- 7.4.4 Kreuzschienen-Schalter.- 7.5 Einige vergleichende Betrachtungen.- 8 Fehlertolerante Architekturen.- 8.1 Kenngrößen und Verfahren.- 8.1.1 Zuverlässigkeit und Verfügbarkeit.- 8.1.2 Fehlertoleranzverfahren.- 8.2 Fehlertoleranztechniken.- 8.2.1 Diagnose.- 8.2.2 Maskierende Redundanz.- 8.2.3 Paarweise Redundanz.- 8.2.4 Gegenseitig genutzte Redundanz.- 8.3 Fehlertolerante Parallelrechner.- 8.3.1 Tandem Integrity.- 8.3.2 Stratus Continuous Processing.- 8.3.3 Tandem NonStop.- 8.4 Skalierbare Parallelität.- 8.4.1 Fehlertolerante Verbindungsnetzwerke.- 8.4.2 Tandem Himalaya.- 8.4.3 TeraData.- 8.4.4 Weitere Architekturbeispiele.- 8.4.5 Fehlertolerante Platten-Arrays.- 9 Algorithmen für Parallelrechner.- 9.1 Schachbrett-Relaxation.- 9.2 Tridiagonale Gleichungssysteme.- 9.3 Die Matrixmultiplikation.- 9.4 Die Matrixtransposition.- 9.5 Sortieren.- 9.6 Schlußbetrachtung.- 10 Betriebssysteme für Parallelrechner.- 10.1 Historische Entwicklung und Begriffsbildung.- 10.1.1 Monolithische Systeme.- 10.1.2 Geschichtete Systeme.- 10.1.3 Auf Zugriffsausweisen basierende Systeme.- 10.1.4 Instanzorientierte (objektorientierte) Systeme.- 10.2 Anforderungen und Lösungskonzepte.- 10.2.1 Grundstrukturen von Betriebssystemen.- 10.2.2 Speicherverwaltung in parallelen Systemen.- 10.2.3 Interaktionsmechanismen.- 10.2.4 Aktivitätsträger und ihre Verwaltung.- 10.2.5 Verteilung.- 10.2.6 Betriebsmodi und Systempartitionierung.- 10.3 Realisierung in existierenden Systemen.- 10.3.1 Strukturen klassischer Basisbetriebssysteme.- 10.3.2 Ausgewählte Parallelrechnersysteme.- 11 Parallele Programmiersprachen.- 11.1 Einleitung.- 11.2 Datenparallelität.- 11.3 Funktionsparallelität.- 11.3.1 Kommunikation über Kanäle.- 11.3.2 Kommunikation über gemeinsame Datenbereiche.- 11.3.3 Kommunikation über Dienstleistungsprozesse.- 11.3.4 Kombination verschiedener Konzepte in einer Sprache.- 11.4 Unkonventionelle Sprachkonzepte.- 11.4.1 Parallele funktionale Programmierung.- 11.4.2 Parallele logische Programmierung.- 11.4.3 Parallele objektbasierte Programmierung.- 11.4.4 Linda.- 11.5 Schluß.- 12 Leistungsbewertung von Parallelrechnersystemen.- 12.1 Einleitung.- 12.2 Leistungsmessung.- 12.2.1 Monitoringmethoden.- 12.2.2 Monitoring in parallelen und verteilten Systemen.- 12.2.3 Ereignisbasierte Auswertemethoden.- 12.3 Leistungsmodellierung.- 12.3.1 Modellierungstechniken.- 12.3.2 Auswertetechniken - Analyse und Synthese.- 12.4 Integration von Messung und Modellierung.- 12.4.1 Modellgesteuerte Programminstrumentierung.- 12.4.2 Validierung.- 12.4.3 Modellgesteuerte Spurauswertung.- 13 Werkzeuge zur Entwicklung paralleler Programme.- 13.1 Phasen der Entwicklung paralleler Programme.- 13.2 Laufzeitbeobachtung mittels Monitoring.- 13.3 Werkzeuge für die frühen Phasen des Entwurfs.- 13.3.1 Werkzeuge zur Spezifikation und Verifikation.- 13.3.2 Werkzeuge zur Zerlegung und Parallelisierung.- 13.3.3 Werkzeuge für das Mapping.- 13.3.4 Werkzeuge für Simulation und Profiling.- 13.4 Werkzeuge für die späten Phasen des Entwurfs.- 13.4.1 Werkzeuge für das Debugging.- 13.4.2 Werkzeuge für die Visualisierung.- 13.4.3 Werkzeuge zur Leistungsanalyse.- 13.5 Werkzeuge für den dynamischen Lastausgleich.- 13.6 Sonstige Werkzeuge.- 13.7 Überblick.- 14 Automatische Parallelisierung Sequentieller Programme.- 14.1 Einleitung.- 14.2 Massiv Parallele Maschinen und ihre Programmierparadigmen.- 14.3 Modell.- 14.3.1 Der Datenraum eines Programms.- 14.3.2 Datenaufteilungen.- 14.3.3 Standardaufteilungen.- 14.3.4 Allgemeine Blockaufteilungen.- 14.4 Elemente der Transformationsstrategie.- 14.4.1 Phase 1: Analyse und Normalisierung.- 14.4.2 Phase 2: Programmzerlegung.- 14.4.3 Phase 3: Initiale Parallelisierung.- 14.4.4 Phase 4: Optimierung und Objektcode-Generierung.- 14.4.5 Prozeduren.- 14.5 Laufzeitanalyse für Schleifen mit irregulären Zugriffen.- 14.5.1 Der Inspektor.- 14.5.2 Der Exekutor.- 14.5.3 PARTI und CHAOS.- 14.6 Übersicht relevanter Entwicklungen.- 14.7 Grenzen gegenwärtiger Compiler und aktuelle Forschung.