Forscherteam in New Mexico bringt Parallelrechner auf Trab:

Hypercubus arbeitet fast ohne Overhead

27.05.1988

Kommt die Rede auf Parallel-Computer - Systeme also mit 4, 16 oder 16 000 Prozessoren - so findet sich häufig noch der Fehlschluß, diese Rechner müßten entsprechend ihrer Prozessoranzahl schneller sein als der zugrunde liegende Monoprozessor. Eine Forschergruppe in New Mexico zeigte jetzt jedoch, daß eine Leistungssteigerung bei Multiprozessorsystemen fast ohne Overhead möglich ist.

Wenn eine Frau zum Austragen ihres Kindes neun Monate braucht - wie lange brauchen dann neun Frauen für die gleiche Aufgabe? Allenfalls Mathematiker hätten auf diese Frage eine ebenso schnelle wie kurzschlüssige Antwort parat. Doch ausgerechnet bei (Parallel-)Computern ist diese Schlußweise häufig anzutreffen. Der Grund für die Nicht-Linearität zwischen Prozessorzahl und Rechenleistung liegt vor allem in der Schwierigkeit, Aufgaben so gliedern zu können, daß die Prozessoren auch tatsächlich parallel arbeiten können.

Speedup von 5 schon zufriedenstellend

Seit langem ist daher die Frage, wie man Aufgaben sinnvoll auf viele, parallel arbeitende Prozessoren verteilen kann, eines der meistdiskutierten Themen im laufend größer werdenden Kreis der eingeschworenen Parallelrechner-Fans. Meist war man dabei schon recht zufrieden, mit beispielsweise acht Prozessoren das fünffache Tempo des Monoprozessors erreichen zu können ("Speedup" = 5). Auf das Gesamtsystem bezogen sind dies 62 Prozent der theoretisch erreichbaren Leistung.

Zwar ist nie umstritten gewesen, daß man durch das geschickte Zergliedern von Programmen, die sich ihrer ganzen Struktur nach besonders gut für das Zerlegen in parallel bearbeitbare Bruchstücke eignen, auch eine noch höhere Effizienz erreichen kann. Doch als nun aus New Mexico unlängst in der Tat entsprechende Erfolgsmeldungen kamen - da horchte die Fachwelt denn doch auf. Den dortigen Sandia-Nationallaboratorien war unter Einsatz von genau 1024 Prozessoren doch tatsächlich die Realisierung der 1020fachen Leistung gelungen. Dies entspricht einem Effizienz-Wert von immerhin 99,61 Prozent, der bislang als schlicht unmöglich galt.

Wie bemerkenswert das Spitzentempo des Sandia-Prozessor-Teams in der Tat ist - dies rückt Edwin H. Barsis, der Direktor des Forschungs-Bereichs Computerwissenschaft und Mathematik mit knappen Worten ins rechte Licht: "Wir haben, und dies ist das eigentlich Wichtige, nicht nur etwas vollbracht, was bisher für unmöglich galt. Wir haben außerdem sogar echte Probleme aus der realen Welt behandelt - und nicht nur mathematische Spielereien ohne realen Nutzeffekt betrieben". Denn das, was dort parallelisiert worden sei, sei bisher nicht für so befriedigend parallelisierbar gehalten worden. Und damit, so meinen Barsis und seine Kollegen, sei vielleicht gar endlich der Durchbruch durch eine "psychologische Barriere" gelungen - mit dem Resultat, daß der Weg nun frei sei, das Feld der parallelen Systeme intensiver denn je zu beackern.

Psychologische Barriere jetzt durchbrochen

Das Rekordtempo ihres 1024-Prozessoren-Komplexes erzielten die Sandia-Wissenschaftler bei der Bearbeitung verschiedener Physik-Programme, die physikalische Systeme mit instabilem beziehungsweise irregulärem Verhalten beschreiben und die bisher immens viel Rechenzeit zu beanspruchen pflegten. Doch nach Zergliederung in lauter extrem kleine Portionen Codes laufen diese - allerdings von Haus aus gut parallelisierbaren - Programme auf der vergleichsweise billigen Sandia-Maschine kaum langsamer als bisher auf weitaus teureren Rechnern, bemerken Barsis und sein Parallelisierer-Team.

Den großen Fortschritt, den diese Gruppe von Forschern erzielt hat unterstreicht auch der Computer-Fachmann Alan Karp. Es gebe fortan, so seine Einschätzung der Neuentwicklung, keinen Zweifel mehr: die Menschen können hochgradig parallele Systeme heute nicht nur bauen, sondern auch effizient nutzen. Und das Sandia-Team selber meint, sollte die neue, "feinkörnige" Parallelisierungstechnik sich auch auf weitere Problemstellungen aus den Bereichen Wissenschaft und Technik übertragen lassen, so könnte man fortan wohl mit einem ziemlichen Boom bei Parallelsystemen und allem, was dazugehört, rechnen. Damit könnten schon bald viele Forscher jederzeit ihren eigenen Super-Computer greifbar haben.

Sandia-Forscher kassieren 100-Dollar-Wette

Auf Dr. Karp aus Palo Alto muß die Nachricht vom schnellen Parallelsystem seiner Kollegen in Sandia sicher teils wie eine Heils-, teils aber auch wie eine kleine Hiobsbotschaft gewirkt haben. Denn so sehr er sich über den wissenschaftlichen Durchbruch und über den "superben Job", E der da vollbracht worden war, gefreut haben dürfte - zugleich ging es ihm nun auch ans Portemonnaie. Karp nämlich hatte vor Jahren einen Hundert-Dollar-Schein für jenen ausgelobt, der an einem Parallel-System erstmals mindestens die 200fache Leistung eines Monoprozessors nachweisen könnte. Denn mit vielen seiner Kollegen hing auch Karp bislang einer These an, die manche auf den Computer-Pionier Gehe Amdahl zurückführen. Und die besagen soll, daß ein Mehrrechnersystem niemals mehr als das 50- bis 100fache Tempo eines Monoprozessorrechners erreichen könne. Zur besseren Einschätzung dieser Regel muß man wissen, daß sie schon aus den 60er Jahren stammt, als Amdahl noch im Dienst des Großrechnerhauses IBM mit seinen Einprozessorsystemen war.

Rekordergebnisse bei Physik-Problemen

Die Problemstellungen, bei denen die Wissenschaftler in New Mexico so überaus flott ans Ziel kamen, stammen aus drei Bereichen der Physik Im ersten Fall ging es um die Berechnung der Fortpflanzung einer Schallwelle beziehungweise anderer Wellen im Bereich ablenkender Wände, während im zweiten ein Flüssigkeitsstrudel untersucht wurde. Und die dritte Kalkulation schließlich betraf die internen Spannungen eines einseitig eingespannten, waagerechten Balkens.

Zum Erzeugen eines sinnvollen, feinkörnigen Parallelsystem-Codes, bei dem jeder einzelne Prozessor dann ein kleines Element der Welle, des Strudels oder des Balkens darstellen und dessen Verhalten berechnen soll, war nach Barsis' Worten ein hoher Aufwand nötig. Doch kennt man die Technik erst mal, so soll sie sich dann leicht weiteren Aufgabenstellungen der gleichen Klassen anpassen lassen.

Auf der Sandia-Maschine mit ihren 1024 Prozessoren lief das Wellenprogramm mit dem erwähnten Rekord-Speedup von 1020, während des Balken- und das Strudelprogramm Speedups von 1019 und 1011 erreicht haben sollen. Dieser letztere Wert spiegelt übrigens auch wider, daß bei der Strudel-Kalkulation aus dem Bereich der Strömungsmechanik mehr Daten zwischen den einzelnen Prozessoren ausgetauscht werden mußten, als bei den beiden anderen.

Erstaunen macht auf den ersten Blick, daß die Wissenschaftler des renommierten Computer-Forschungszentrums in New Mexico nicht etwa einen ganz speziellen, selbst entwickelten Labortypen von innovativem Rechner eingesetzt hatten, sondern sich quasi aus dem nächsten Computershop ein kommerziell erhältliches System geholt haben: den Hyperkubus des Herstellers NCube aus Beaverton im US-Bundesstaat Oregon. Er verfügt über 1024 Mikrorechner, die unabhängig voneinander unterschiedliche Befehlsketten abarbeiten können; die also nicht, wie etwa die einzelnen Rechenelemente eines herkömmlichen Vektor-Rechners alle immer nur die gleichen Instruktionen bearbeiten.

1024 Mikros arbeiten unabhängig voneinander

Ein Hyperkubus ist toplogisch eine Struktur, die entsteht, wenn man beispielsweise zwei herkömmliche, deckungsgleiche Würfel nimmt und deren (je) acht Ecken so durchnumeriert, daß deckungsgleiche Ecken die gleiche Nummer bekommen. Denn dann muß man diese beiden Würfel nur noch nebeneinander legen und alle Ecken mit gleicher Nummer paarweise (miteinander) verbinden.

Es entsteht bei dieser Prozedur ein Hyperkubus mit 16 Ecken oder besser "Knoten", den man nun durch sinngemäß das gleiche Vorgehen erneut verdoppeln kann. Irgendwann landet man dann auch beim Sandia-Hyperkubus mit seinen 1024 Ecken beziehungsweise Prozessoren. Er hat ein paar interessante Eigenschaften: so etwa die, daß von jedem seiner Knoten exakt zehn Leitungen zu bestimmten anderen Knoten gehen.

Und daß zur Verbindung zweier Knoten miteinander niemals mehr als zehn Knoten-Leistungs-Teilstücke nacheinander durchlaufen werden müssen.

Der 1024er-Hyperkubus wird auch gern als zehndimensionaler Hyperkubus bezeichnet. Das hat mit der erwähnten Zahl von zehn Leitungen pro Knoten zu tun sowie damit, daß 1024 eben gleich 2¹º ist.

Man kann sich nun leicht vor Augen führen, daß ein gewöhnlicher Würfel mit seinen zwölf Kanten ein dreidimensionaler und daß unser vorhin "verdoppelter" Würfel ein vierdimensionaler Hyperkubus ist Und natürlich auch, daß man Hyperkuben mit - theoretisch - unbegrenzt vielen Dimensionen bauen kann.

Selten auf dem Weg zu fernen Prozessoren

Hyperkuben haben im Vergleich zu Strukturen, bei denen jeder Knoten mit jedem anderen direkt verbunden ist, einen großen Vorteil: Die Zahl der Leitungen von und zu jedem einzelnen Knoten wächst beim Hyperkubus nur mit dessen Dimensionen - also beispielsweise 3 oder 4 oder 10 - und nicht direkt mit der Zahl der Knoten an. Was die Kommunikation zwischen zwei topologisch "entfernten" Knoten zwar verlangsamt, die ganze Sache aber schaltungstechnisch-konstruktiv noch einigermaßen handhabbar macht.

Die Sandia-Forscher haben beim Umformulieren und Restrukturieren ihrer Programme viel Aufmerksamkeit auf Strategien verwendet, die sicherstellen, daß sich die Prozessor-Prozessor-Kommunikation im Kubus weitgehend auf den Datenaustausch zwischen je zwei direkt benachbarten Prozessoren beschränkt. Den zeitraubenden Weg zu fernen Prozessoren treten Informationen nur ausgesprochen selten an.

Die Frage, wie nützlich die neuen Techniken für die Computer-Wissenschaft ganz allgemein werden können, hängt weitgehend von deren Übertragbarkeit ab. Davon also, ob die Parallelisierungstechniken aus New Mexico beispielsweise auch in der Aerodynamik und in vielen weiteren Feldern der Physik, der Chemie, der Meteorologie und der Ingenieurwissenschaften brauchbar sind.

Erfolgreich auf der tiefsten Ebene

Die Chancen hierfür scheinen recht gut zu sein. Denn die Sandia-Forscher haben nicht allein die Tatsache genutzt, daß manche Programme mehr parallel abarbeitbare, in sich jedoch streng sequentielle Befehlsketten aufweisen, als andere. Sie haben die sequentiellen Ketten außerdem nochmals einer exakten Analyse unterzogen und nach darin verborgenem Parallelismus auf unterstem Zerteilungs-Niveau gesucht. Dabei haben sie dann festgestellt, daß Berechnungen umso besser zergliedert und parallelisiert werden können, je tiefer man bis auf die Ebene der einzelnen Maschineninstruktionen hinabsteigt. Denn mit diesem Eindringen in die Feinstruktur eines gegebenen Algorithmus wächst der Anteil der parallel bearbeitbaren Befehle von Schritt zu Schritt.

Wie wichtig dieses feinkörnige Parallelisieren ist, wenn man hohe Speedups beziehungweise Geschwindigkeitssteigerungen erzielen will, zeigt folgende simple Überlegung: Selbst wenn ein Parallelsystem Hunderte und Tausende von Verarbeitungselementen besitzen mag - es kann Programme, bei denen auch nur ein Zwanzigstel oder 5 Prozent des gesamten, auszuführenden Codes sequentiell bearbeitet werden müssen, nicht allzu flott abspulen. Denn hier ist ja bei einem Speedup von maximal 20 eine unüberschreitbare Grenze erreicht. Deshalb würde es sich auch kaum lohnen, Hunderte von Prozessoren einzusetzten.

Zu den neuen Entwicklungen des Sandia-Teams meint ein bekannter Rechner-Fachmann, massiv parallele Maschinen wie etwa ein zehndimensionaler Hyperkubus mögen "vielleicht nur wenige der Dinge, die wir mit Computern heute erledigen, beschleunigen". Doch mit diesen Rechnern werden wir "eine Menge Sachen machen können, an die bisher einfach nicht zu denken war".

Supercomputer könnten unterfordert sein

Am Rande sei schließlich noch kurz bemerkt, daß die, auf maximal 500 Mega-FLOPS ausgelegte Sandia-Maschine mit ihren speziell entwickelten Prozessor-Chips im Vergleich zu superschnellen, teuren Rechnern der Spitzenklasse pro Befehlszyklus eher lange braucht. Doch das ist in diesem Fall kein Problem, denn allein die laufende Kommunikation zwischen den Prozessoren verschlingt ja sowieso schon eine gewisse Zeit; lange Mikro- und Nanosekunden, während derer Prozessoren schnellerer Machart dann warten müßten.

Dieser Zusammenhang zwischen Kommunikations- und Befehlsbearbeitungszeit wiederum macht deutlich: Die Technik des parallelen Zusammenschaltens mehrer Rechnersysteme muß nicht in jedem Fall der richtige Weg sein. Denn zumindest miteinander kommunizierende Supercomputer höchster Taktrate könnten dann leicht unterfordert sein.