Leistungskriterien einesSupercomputers sind für den Anwender oft nur schwer zu erkennen:

Verläßliche Benchmarks fehlen immer noch

04.09.1987

Es ist eine bekannte Tatsache, daß der Bedarf an Rechenleistung stets höher ist als das, was die derzeit schnellsten Rechner zu leisten vermögen. Dabei handelt es sich nicht nur um vielzitierte Beispiele wie Berechnung der Wetterkarte. In zunehmendem Maße wird extrem hohe Rechenleistung auch in den Bereichen Forschung, Entwicklung und Konstruktion, beispielsweise bei Simulationen, benötigt, Ein ähnlich hoher Bedarf wächst bei der Analyse komplexen Zusammenhänge (Decision Support) heran.

Seit längerer Zeit ist bekannt, daß der Rechengeschwindigkeit von Computern mit einem einzelnen Prozessor vom Von-Neumann-Typ physikaliche Grenzen gesetzt sind. Diese Grenzen ergeben sich durch absolute Beschränkungen der Schaltgeschwindigkeit einzelner Gatter sowie Signallaufzeiten zwischen den einzelnen Schaltelementen. Die schnellsten heute verfügbaren Prozessoren haben diese physikalische Grenze zwar noch nicht erreicht, aber der Bedarf an Rechengeschwindigkeit geht schon heute darüber hinaus. Ein natürlicher Ansatz, dises Dilemma zu umgehen, besteht darin, eine Aufgabe auf mehrere Prozessoren zu verteilen (Parallelverarbeitung).

Diese Grundidee ist nicht neu, sondern wurde auch in der Vergangenheit schon verfolgt, um mit der jeweils verfügbaren Technologie möglichst hohe Rechenleistung zu erzielen. Warum hat es dann so lange gedauert, bis Parallelrechner beginnen, am Markt Fuß zu fassen? Ein Grund mag gewesen sein, daß die der Vergangenheit hohen Hardwarkosten ein Hindernis waren. Der Hauptgrund ist jedoch eher in der Tatsache zu sehen, daß erst jetzt befriedigende Methoden zur Handhabung der Parallelverarbeitung verfügbar werden.

Das Ziel der Parallelverarbeitung ist, ein (beliebiges) einzelnes, zeitaufwendiges Programm (Programmteil, Prozeß) gleichzeitig von vielen rechneden Einheiten bearbeiten zu lassen. Es geht nicht darum, einige unabhängige Prozesse zu erkennen und dann auf zwei oder drei Prozessoren zu verteilen, sondern einen Prozeß als Ganzes hochgradig zu parallelisieren. Nur eine Kombination von paralleler Architektur und parallelen Algorithmen ist in der Lage, auf sein Wege die physikalisch bedingten Leistungsgrenzen der Von-Neumann-Rechner um viele Größenordnungen nach oben zu verlagern.

Eine häufig gestellte Frage lautet: Welche Anwendungen sind parllelisierbar? Hier gibt es Erfreuliches zu berichten. Es gibt keine parllelisierbaren beziehungsweise nicht parallelisierbaren Probleme. Vielmehr: Es gibt zeitaufwendige und wenig zeitaufwendige Probleme. Zeitaufwendig heißt: Bei optimalem Programm auf einen Von-Neumann-Rechner ist die Laufzeit als Funktion der Datenmenge hoch. Und es gibt gute Parallelkonzepte, schlechte Parallelkonzepte und Parallelrechner ohne Konzept. Eine gute Parallelarchitektur sollte in der Lage sein, möglichst proportional zur Anzahl der Prozessoren (mindestens jedoch zum Preis) aus zeitaufwendigen Anwendungen wenig zeitaufwendige Anwendungen zu machen.

Erfreulich ist weiterhin: Erste parallele Supercomputer mit einem breiten Anwendungssprektrum werden verfügbar. Meist ist sogar das Preis-Leisung-Verhältnis erheblich besser als das heutiger Supercomputer. Eine Prinzipielle Leistungsgrenze ist mit guten Parallel-Architekturen noch in weiter Ferne. Heute schon Rechner mit Leistungen von 10 12 bis 10 13 Operationen pro Sekunde zu bauen, scheitert allein am Preis beziehungsweise Raumbedarf, der sich aus der zur Zeit verfügbaren Technolgie ergibt, nicht jedoch an der Machbarkeit. Bis dieser Leistungssprung um weitere drei Zehnerpotenzen bezahlbar wird, werden jedoch noch einige Jahre ins Land gehen.

Tatsächlich scheint die Parallelverarbeitung das einzige Mittel zu sein, um die erforderlichen Rechenleistungen zu erreichen. Um diesen Sachverhalt zu erläutern, soll kurz auf die übrigen leistungssteigernden Möglichkeiten eingegangen werden.

Multiprozessorsysteme: Hier besteht, nicht zuletzt geschürt durch einige Hersteller, eine Begriffsunsicherheit bei der Abgrenzung zwischen Multiprozessorsystemen und Parallelrechnern. Die Arbeitsweise dieser beiden Rechnertypen unterscheidet sich jedoch grundlegend.

Gegenüber der oben angedeuteten Arbeitsweise von Parallelrechnern werden bei Multiprozessorsystemen vorhandene sequentielle Programmteile (Prozesse) auf die vorhandenen Prozessoren unverändert verteilt. Die Verteilung erfolgt in aller Regel durch das Betriebssystem zur Laufzeit, und einzelne Prozesse werden nicht weiter parallelisiert. Die Anzahl der bei dieser Methode nutzbaren Prozessoren ist naturgemäß klein. Daher ist es nicht verwunderlich, daß kommerziell verfügbare Multiprozessorsysteme oft weniger als zehn Prozessoren aufweisen.

Die Grenze wird nur nach oben verschoben

Obwohl mit dieser Methode eine Leistungssteigerung um einige hundert Prozent möglich ist, greift auch hier in Zukunft die physikalische Grenze der Von-Neumann-Prozessoren. Die Grenze ist lediglich etwas nach oben verschoben.

Spezialprozessore.n: Spezialprozessoren erlauben es, ganz konkrete Operationen besonders schnell zu verarbeiten (Floating-Point-Operationen, FFT-Berechnungen, Pixel-Berechnungen etc4 In gewissem Sinne fallen auch einige Vektor-Prozessoren unter diese Kategorie). Bei diesen Prozessoren handelt es sich um eine spezielle, in Hardware realisierte Form der Parallelverarbeitung.

Ein Nachteil dieses Ansatzes besteht darin, daß die Anwendbarkeit dieser Prozessoren sehr eingeschränkt ist. In bezug auf hohe Rechenleistung ergibt sich die Einschränkung, daß nur einzelne Operationen beschleunigt werden und damit die Steigerung der Rechengeschwindigkeit begrenzt ist.

Algorithmen: In die Erarbeitung effizienter Algorithmen wurde in der Vergangenheit mit Recht viel Aufwand investiert. Tatsächlich hat die Effizienz eines Programms meist weit größeren Einfluß auf die Rechenzeit als die Geschwindigkeit der Von-Neumann-Maschine, auf der es abläuft. Andererseits hat jede Aufgabenstellung ihre minimale Anzahl von sequentiellen Operationen, die durch geschickte Programmierung nicht weiter unterschritten werden kann.

Reduziemng des Problems. Vielfach wird aufgrund der hohen Rechenzeiten die Anforderung an ein Programm reduziert. Zum Beispiel wird nicht ein optimaler Wert berechnet, sondern eine gute Näherungslösung. Auch solche Maßnahmen können eine drastische Reduzierung der Laufzeiten verursachen.

Bei den meisten Anwendern besteht nach den vielen Ankündigungen neuer Rechner eine Unsicherheit bei der Bewertung verschiedener paralleler Architekturen, der Leistungsbewertung und der Frage, wie und mit welchem Aufwand Applikationen realwerbar beziehungsweise portierbar sind. Bevor wir die Methoden der Parallelverarbeitung an einem Beispiel erläutern, wollen wir daher einige dieser Punkte ansprechen und auch Problematiken aufzeigen, die von Herstellern meist verschwiegen und allenfalls in kleinen Expertenrunden diskutiert werden.

Von Parallel arbeitenden Super-computern darf man heute erwarten:

- Eine extrem hohe tatsächliche Leistung, die bis um den Faktor 1000 über der herkömmlicher Mainframes liegen sollte.

- Diese Leistung sollte verfügbar sein bei einem Preis-Leistungs-Verhältnis, das deutlich besser ist als das von Ein-Prozessor-Systemen.

- Die Leistung sollte bei möglichst vielfältigen Anwendungen und unter unterschiedlichsten Bedingungen erreichbar sein. Auch bei einzelnen Applikationen treten heute ganz unterschiedliche Anforderungen an Rechenleistung auf, die nicht durch eine allzu spezialisierte Architektur bewältigt werden können, sondern erst durch eine möglichst vielseitige Nutzbarkeit der vorhandenen Prozessoren.

- Damit verbunden ist auch der Bedarf an einer extrem hohen Ein-/Ausgabe-Leistung zu und von peripheren Geräten. Auch dieser Bereich kann und sollte parallelisiert werden.

- Der Parallelrechner sollte problemlos, das heißt ohne Aufwand bei der Umstellung, in der Leistung gesteigert werden können durch Ergänzung um weitere Hardware-Komponenten.

- Der Parallelrechner sollte zu simultanem Multitasking fähig sein, um auch im Normalbetrieb durch die gleichzeitige Bearbeitung vieler kleiner Prozesse einen hohen Durchsatz zu erzielen.

- Der Parallelrechner sollte nicht nur eine Ansammlung von Prozessoren sein, sondern einhergehen mit speziell auf die Parallelverarbeitung abgestimmten Betriebssystemen und Compilern, die eine ökonomische Software-Entwicklung gestatten. Der Hersteller sollte in der Lage sein, die notwendigen Software-Tools zur Verfügung zu stellen, bei der Portierung vorhandener Software behilflich zu sein und generell Know-how über die spezielle Art der Parallelverarbeitung vermitteln können.

Was man nicht erwarten darf, ist, daß zum Beispiel ein beliebiges Fortran-Programm ohne menschliches Zutun so auf die Parallelmaschine portiert wird, daß die volle Leistung genutzt werden kann. Obwohl die Möglichkeiten der automatischen Parallelisierung weitreichender sind als die der Auto-Vektorisierung, ist der erzielte Beschleunigungsfaktor zumindest bei großen Prozessorzahlen von der Art des Ausgangsprogramms abhängig. In extrem hohen Leistungsbereichen, die wesentlich über das hinausgehen, was mit Von-Neumann-Maschinen erreichbar ist - in Bereichen also, wo die vorhandenen Maschinenleistung wenigstens annähernd ausgenutzt werden soll -, muß die Parallelität bei der Portierung beziehungsweise Programmerstellung berücksichtig werden. Dieses ist ein Punkt, den die Hersteller (nicht nur von echten Parallelrechnern) gerne verschweigen.

Flops bei Benchmarks

Das Problem der Leistungsmessung bei Supercomputern ist immer noch nicht ausgestanden. Insbesondere unter dem Aspekt der Programmierung und Portierung vorhandener Programme stellt sich die augenblickliche Situation folgendermaßen dar: Wohlwissend um die Ansprüche der Anwender wirbt die Mehrzahl der Anbieter mit Mips- und MFlops-Zahlen, die im täglichen Betrieb nicht annähernd erreicht werden können. Das gilt bei einigen Maschinen sogar bei optimaler Programmierung und der Architektur angepaßten Anwendungen. Werden Auto-Vektorisierer oder Auto-Parallelisierer eingesetzt, so ist die Diskrepanz zwischen Mips und Realität meist noch viel größer. Dann tritt entweder Resignation ein, oder Schwärme von Programmierern versuchen in oft mühevoller Kleinarbeit, noch ein paar Mips mehr aus der Maschine herauszukitzeln.

Das Problem der Leistungsangabe liegt darin, daß einerseits Mips und sogar MFlops keine Maßeinheit sind und andererseits immer noch verläßliche, allgemein anwendbare Benchmarks fehlen. Teilweise werden bei Parallelrechnern (ebenso wie bei Multiprozessorsystemen und Vektorrechnern) sogar die Mips der einzelnen rechnenden Einheit multipliziert mit der Anzahl der rechnenden Einheiten. Bei diesen Angaben fehlen vollständig folgende leistungsbestimmende Faktoren: Wie leistungsfähig ist ein Mips? Lassen sich die Programme überhaupt so auf die Architektur abbilden, daß der notwendige Informationsaustausch schnell genug erfolgen kann? Hält der Datentransfer Schritt mit der Rechengeschwindigkeit? Wie gut sind die Compiler? Welchen Verwaltungs-Overhead erzeugt das Betriebssystem etc.

Die Benchmark Problematik resultiert primär aus der Tatsache, daß herkömmliche Benchmarks ausschließlich programmorientiert sind. Dabei handelt es sich um Programme für Von-Neumann-Rechner. Die Ausführung eines solchen Programms (eventuell automatisch parallelisiert) gibt keine verläßliche Angabe über die Leistungsfähigkeit eines parallelen Rechners. Ein Ausweg aus diesem Dilemma könnte wie folgt aussehen: Ausgangspunkt ist eine möglichst große Anzahl von konkreten Problemen aus verschiedenen Anwendungsbereichen. Die Auswahl dieser Probleme muß repräsentativ sein (allgemein oder für bestimmte Anwendergruppen) und fair, das heißt so vielfältig, daß nicht eine bestimmte Architektur bevorzugt wird. Jede Problemstellung wird nicht als Programm oder Algorithmus gegeben, sondern als exakte Definition der Abbildung von Eingabedaten zu Ausgabedaten, zusammen mit einem umfangreichen Satz von Testdaten.

Die Formulierung der Problemlösung als Programm kann dann für unterschiedliche Architekturen verschieden ausfallen. Die Summe der Laufzeiten für alle Probleme und alle Testdaten kann als verläßliche Maßzahl zur Leistungsbewertung verwendet werden.

Die Analyse der einzelnen Laufzeiten könnte eine Aussage über die Universalität beziehungsweise die Eignung für bestimmte Anwendungsgebiete machen. Der Nachteil dieser Methode ist weniger in dem Aufwand für den Test zu sehen (diesen Aufwand wird jeder Hersteller sicher mit großer Hingabe auf sich nehmen), sondern in der Tatsache, daß noch nicht erkennbar ist, wie hoch der Implementierungsaufwand für ein bestimmtes Benchmark-Resultat war. Hier sind die internationalen Normungsgremien ernsthaft gefordert.

Was beeinflußt nun die Effizienz einer bestimmten Parallel-Architektur? Die wichtigste Erkenntnis hier ist, daß es sich nicht um ein einzelnes Kriterium handelt, an dem man die Leistungsfähigkeit einer Architektur messen kann, sondern daß eine Vielzahl von Eigenschaften zusammenkommen muß, um eine extrem hohe Leistung auch tatsächlich in der Anwendung zu erreichen. Gerade diese Kriterien sind für den Anwender oft schwer zu erkennen. Die folgenden Punkte müssen in ihrer Gesamtheit positiv erfüllt sein, um mit einem parallelen Supercomputer die erwartete Leistung zu erreichen.

- 1. Leistung pro Prozessor.

- 2. Anzahl der Prozessoren.

- 3. Kommunikationsleistung zwischen Prozessoren (hohe Datenrate und schnelle Signalausbreitung beziehungsweise Antwortzeit).

- 4. Schnelle Ein-/Ausgabeleistung mit peripheren Datenträgern.

- 5. Topologie: Wie können die einzelnen Prozessoren miteinander kommunizieren; ist diese Struktur universell nutzbar? Siehe dazu auch das nachfolgende Beispiel.

- 6. Tuning: Die Leistung der Einzelkomponenten muß aufeinander abgestimmt sein. Es nutzt nichts, wenn zum Beispiel Floating-Point-Operationen schneller ausgeführt werden können, als die Operanden herbeigeschafft werden können.

- 7. Keine gemeinsamen Ressourcen: Von allen Prozessoren genutzte Speicher und Busse sowie eine zentrale Steuereinheit (Scheduler) verhindern, daß sehr viele Prozessoren gleichzeitig ungestört arbeiten können. Das Warten auf die eine gemeinsame Ressource führt zu einer Sequentialisierung des Parallelrechners. Die Grenze, bei der solche Ansätze noch zu einer guten Auslastung der Prozessoren führen, liegt schon bei zirka zehn Prozessoren.

- 8. Granularität: Der einzelne Prozessor sollte weder zu groß und leistungsfähig sein, noch zu klein und eingeschränkt. Zu leistungsfähige Prozessoren bedeuten einen höheren Preis und Platzbedarf und gehen damit leicht überproportional zu Lasten der Anzahl der Prozessoren. Zu kleine Prozessoren mit sehr geringen lokalen Speichermöglichkeiten für Programm und Daten führen zu erhöhtem Kommunikationsaufwand und erschweren die Programmierung.

- 9. Großer Hauptspeicher: Zumindest die Summe aller lokalen Speicher sollte nicht zu klein sein. Optional sollten mehrere Gigabyte zum Standard werden. Datenmengen in dieser Größenordnung werden bei vielen Anwendungen schon heute benötigt. Das häufige Ein- und Auslagern der Daten würde den Vorteil der Parallelverarbeitung bei solchen Anwendungen zunichte machen.

- 10. Es sollte möglich sein, mit Compilern, die die Parallelität untarstützen, und einem erkennbaren Parallelisierungskonzept neue sowie vorhandene Programme ökonomisch auf dem Parallelrechner zu implementieren.

Wir wollen einige Aspekte der Parallelverarbeitung an einem konkreten, sehr einfachen Beispiel und an einem konkreten Parallelrechner erläutern, der alle bisher erwähnten Anforderungen erfüllt. Aufgrund der Vielzahl der parallelen und parallelartigen Architekturen und den unterschiedlichen damit verbundenen Ansätzen zur Parallelverarbeitung kann ein Beispiel nie repräsentativ sein für alle Parallelrechner. Bei dem hier beschriebenen Rechnertyp der Familien TX2 und TX3 handelt es sich um eine binärbaumartige Struktur, wobei jedem Knoten ein autonomer Prozessor mit Speicher entspricht und die Kanten physikalisch vorhandenen Kommunikationskanälen. Erstaunlicherweise unterscheiden sich sogar baumartige Parallelrechner untereinander sehr deutlich in ihrer Vorgehensweise und in ihren Eigenschaften.

Daß extrem zeitaufwendige Anwendungen, wie sie bei komplexen logischen Entscheidungen und Optimierungen zum Beispiel beim VLSI-Design anfallen, sich hervorragend für baumartige Strukturen eignen, ist weitläufig bekannt. Um zu demonstrieren, daß die Baumstruktur sehr universell ist und eine dem Menschen offensichtliche Problemstruktur nicht notwendigerweise in Hardware nachgebildet werden muß, wählen wir als Beispiel Matrix-Multiplikation.

Der allgemeinste Grundsatz für die parallele Programmierung ist, ein Problem in viele gleichartige Teilprobleme zu zerlegen (falls nicht zusätzlich verschiedenartige Teilprobleme erkennbar sind). Dieser Ansatz ist auch in der normalen Programmierung als Grundsatz "Teile und Herrsche" (Divide and Conquer), bekannt. Erstaunlich ist allerdings, daß die parallele Version dieser Programmiermethode so universell und vielseitig anwendbar ist. Bei dem einfachsten Programmtyp zur Multiplikation zweier nxn-Matrizen muß jede Zeile der einen Matrix mit n Spalten der anderen Matrix multipliziert werden, das heißt, es müssen insgesamt n 3 Multiplikationen und Additionen ausgeführt werden.

Eine triviale Methode der Problemaufteilung besteht einfach darin, zunächst eine der beiden Matrizen wiederholt zu halbieren und dann eine ganz normale Matrix-Multiplikation auf den resultierenden Teilmatrizen auszuführen. Ein Programmteil, der sieht in etwa folgendermaßen aus:

wave matrixmult

inner

verteile Eingabe-Matrizen

verschmelze Ausgabe-Matrix

end

leaf

multipliziere Matrizen

end

Wave (Welle) ist ein Paralleles Programmkonstrukt, das in der Lage ist, einen ganzen Teilbaum aufzuspannen. Eine Welle wird ähnlich aufgerufen wie eine Prozedur. Der Rumpf dieser Welle besteht aus zwei Teilen: erstens den Anweisungen, die die Aufteilung beziehungsweise Verschraelzung der Teilprobleme definiert, und zweitens dem Algorithmus für die Lösung der Teilprobleme. Bei diesem Beispiel zeigen sich zwei wichtige Anforderungen an eine baumartige Architektur, wie sie im TX3 realisiert sind. Zum einen muß die Verteilung von Daten schnell erfolgen können. Durch baumartiges Pipelining wird erreicht, daß die Zeit zur Verteilung von Daten im ganzen Rechner nur unwesentlich mehr Zeit verbraucht als das Kopieren der Daten von einem Prozessor zum anderen. Darüber hinaus ist dieser Verteilungsvorgang schneller, als die Daten von jedem noch so schnellen Plattenspeicher gelesen werden könnten. Dieses zeigt die zweite Anforderung an Parallelrechner auf, nämlich eine extrem hohe I/O-Leistung. Auch das Lesen beziehungsweise Schreiben von und zu peripheren Speichern muß parallelisierbar sein.

Anhand dieses konkreten Beispiels können wir jetzt einige interessante Aspekte der Parallelverarbeitung erläutern.

- Es wird nicht eine Multiplikation superschnell ausgeführt, sondern beliebig oft gleichzeitig (die Parallelität ist nicht durch eine Vektorlänge begrenzt).

- Obwohl hier die häufigsten Operationen Floating-Point-Operationen sind, könnte bei anderen Anwendungen auch eine Operation im Vordergrund stehen, für die kein Spezialprozessor verfügbar ist. Es ist ersichtlich, daß beliebige Elementaroperationen gleichzeitig ausgeführt werden können.

- Der Grad der Parallelisierung (Anzahl der Prozessoren) ist nicht begrenzt. Bei größerer Matrix muß das Programm nicht verändert werden. Bei größerem Rechner (mehr Prozessoren) wird der Verteilvorgang einfach weiter fortgesetzt. Damit ist eine Beschleunigung der Berechnung verbunden, und auch hier muß das Programm nicht geändert werden.

- Das normale sequentielle Programm für Matrix-Multiplikation, geschrieben zum Beispiel in Fortran oder Pascal, kann übernommen werden. Solche Eigenschaften führen zu guten Bedingungen für automatische Parallelisierer

- Ein wesentlicher Aspekt der Baumstruktur ist, daß bei p Prozessoren der längste Weg zwischen zwei Prozessoren log p Einheiten lang ist. Ein Problem kann in log p Schritten in p Teilprobleme zerlegt werden. Bei matrixförmig angeordneten Prozessoren beträgt der entsprechende Wert immerhin die Wurzel aus p. - Ein interessierter Leser mag erkennen, daß bei diesem Beispiel über lange Zeiträume nur die untersten (Blatt) Prozessoren beschäftigt sind. Das entspräche einer gleichmäßigen Auslastung von 50 Prozent. Obwohl dieser Wert im Vergleich gar nicht schlecht ist, hat ein Parallelrechner wie der TX3 hardware- und softwareseitige Vorkehrungen, die alle vorhandenen Prozessoren in diesen Berechnungsvorgang mit einbeziehen.

- Obwohl hier alle Blattprozessoren das gleiche Programm auf unterschiedlichen Daten ausfahren (Quasi-SIMD-Mode), ist leicht einzusehen, daß das bei anderen Programmen nicht der Fall sein muß. Es sei nicht verschwiegen, daß die Nutzung der vielen Prozessoren nicht in jedem Fall so einfach ist, aber eben doch sehr oft. Eine Stärke dieser Rechnerarchitektur ist ihre Flexibilität, die es erlaubt, mit recht einfachen Mitteln. (zum Beispiel können sich Wellen gegenseitig aufrufen wie Prozeduren, können simultan oder hintereinander ablaufen) auch verschiedenartige Parallelisierungsstrategien zu verwirklichen. Wichtig insbesondere bei Neuimplementierungen ist, daß sinnvoll erweiterte Compiler für gebräuchliche Hochsprachen und gegebene Parallelisierungheuristik existieren, die einerseits den vollen Zugriff auf die Maschine erlauben andererseits aber zeitraubende Details wie die Synchronisation zwischen Prozessoren und deren Anzahl weitgehend vom Programmierer fernhalten, ohne dadurch einen Effizienzverlust zu bewirken. Der Standardansatz bei Neuimplementierungen verfolgt hier die Philosophie, Standardmethoden der Parallelisierung durch Hochsprachen-Compiler unterstützen zu lassen.