Parallelrechner werden oft als Formel-1-Rennwagen unter den Computern deklariert. Sie sind auf höchste Rechenleistung getrimmt, bieten aber oft - je nach Rechnertyp - noch nicht den gewohnten Programmierkomfort einer modernen Workstation. Michael Sonnenschein* beschreibt, was bei dem Einsatz klassischer Programmiersprachen im Bereich Parallelrechner zu beachten ist, und zeigt neue Ansätze auf.
Parallelrechner lassen sich ganz grob in zwei Klassen einteilen: Bei Single-Instruction-Multiple-Data-Rechnern (SIMD) besteht ein Programm im wesentlichen aus einer Folge von Anweisungen, die nacheinander, sequentiell, ausgeführt werden. Die Parallelität des Rechners kommt nur bei einzelnen Anweisungen zum Tragen. So sind häufig Anweisungen vorgesehen, die es gestatten, eine Operation auf allen Elementen eines Vektors oder einer Matrix gleichzeitig, das heißt parallel, auszuführen. Computer dieses Typs können somit in erweiterten Standard-Programmiersprachen wie Fortran-90, C oder Lisp programmiert werden.
Anforderungen an die Programme
Die Erweiterungen dieser Sprachen zur Programmierung des SIMD Rechners erfolgen auf der Ebene der Anweisungen. So läßt beispielsweise der Fortran-Compiler für die Connection-Machine CM-2 Anweisungen der Form R = T + T + ... + T zu. Die Terme T können Arrays, oder Arrays oder Produkte, bestehend aus einem Array und einem shifted Array sein. Die Connection-Machine ist aufgrund ihrer speziellen Hardwarestruktur, die aus bis zu 64000 Verarbeitungseinheiten besteht, in der Lage, solche Anweisungen datenparallel auf den Elementen der Arrays auszuführen. Der Parallelismus ist jedoch im wesentlichen auf die Ebene paralleler Matrix- oder Vektoroperationen eingeschränkt. Programme und die damit implementierten Verfahren müssen in der Regel auf diese Möglichkeiten der Parallelausführung zugeschnitten sein, damit die Leistungsfähigkeit des SlMD-Rechners genutzt wird. Darüber hinaus gibt es verschiedene prototypische Compiler, die aus gewöhnlichen sequentiellen Fortran-Programmen Code für SlMD-Rechner erzeugen, indem spezielle DO-Schleifen in parallel ausführbare Maschinenbefehle übersetzt werden. Damit wird ein Ansatz zur automatischen Parallelisierung von Programmen gewählt.
Bei der prozeßorienierten Programmierung von Multiple-Instruktion-Mulitple-Data-Rechnern (MIMD) ist zur Programmierung eine ganz andere Sicht der Parallelität erforderlich. Computer dieses Typs bestehen aus parallelen Verarbeitungseinheiten, die jede für sich ein eigenes Programm beziehungsweise einen Programmteil aus führen können. Eine Verarbeitungseinheit besteht normalerweise aus einem Mikroprozessor mit Cache, lokalem Speicher und Kommunikationsschnittstellen. Eine Kommunikation dieser Verarbeitungseinheiten untereinander ist entweder durch gemeinsame virtuelle oder reale Speicherbereiche (bei Multiprozessoren) oder durch direkte Kommunikationskanäle zwischen den Verarbeitungseinheiten (bei Multicomputern) möglich.
Zur Programmierung von MIMD-Rechnern muß das auszuführende Programm in Teile zerlegt werden, die sich sequentiell auf den einzelnen Verarbeitungseinheiten ausführen lassen. Solche sequentiell auszuführenden Programmteile mit eigenem Kontrollfluß, die beispielsweise auch in Sprachen wie C oder Fortran programmiert werden können, heißen Prozesse. Sie müssen untereinander durch gemeinsame Variablen (Shared variables) im gemeinsamen Speicherbereich eines Multiprozessors oder durch Austausch von Daten in Form von Nachrichten auf Multicomputern kommunizieren, damit sie gemeinsam an der Lösung der Gesamtaufgabe des Programms arbeiten können. Dabei müssen die Prozesse in der Lage sein, ihre Arbeit zeitlich zu synchronisieren.
Bei der Programmierung von MIMD Rechnern auf der Basis des Prozeßmodells sind zunächst die Prozesse so zu definieren, daß sie bei der Ausführung des Programms auch tatsächlich parallel ausgeführt werden können. Gefragt sind also die Wahl beziehungsweise die Definition eines effizienten verteilten und parallelen Verfahrens zur Lösung des gestellten Problems. Dabei ist insbesondere zu beachten, daß die Granularität des Parallelismus, das heißt die Größe der unabhängig zu bearbeitenden Teile der einzelnen Prozesse, so gewählt wird, daß die parallele Ausführung nicht zuviel Verwaltungs-Overhead durch Kommunikation und Synchronisation verursacht.
Natürlich werden solche prozeßorientiert strukturierten Programme nur in seltenen Fällen für eine spezielle Verbindungsstruktur und Anzahl von Verarbeitungseinheiten des MlMD-Rechners geschrieben. Wichtig ist oft, daß die parallelen Programme skalierbar sind, sie müssen mit unterschiedlicher Anzahl und Verbindungsstruktur von Verarbeitungseinheiten ausführbar sein. Nur läßt sich die Skalierbarkeit von MIMD Rechnern auch durch Programme nutzen. Zur Laufzeit des parallelen Programms werden somit mehrere Prozesse auf einer Verarbeitungseinheit quasi parallel ausgeführt, wie man es aus dem Multiprogramming-Betrieb gewohnt ist.
Damit muß auch eine flexible Zuordnung eines Großteil der Prozesse zu der jeweils ausführenden Verarbeitungseinheit erfolgen. Optimal wäre eine Zuordnung, in der zu jedem Zeitpunkt möglichst viele Verarbeitungseinheiten aktiv mit der Ausführung des Programms beschäftigt sind und möglichst wenig Laufzeit durch die Kommunikation zwischen den Verarbeitungseinheiten verlorengeht. Eine solche Zuordnung zu finden ist jedoch sehr aufwendig und bei größerer Anzahl von Prozessen in der Praxis fast unmöglich.
Daher müssen heuristische Verfahren zur Bestimmung suboptimaler Lösungen dieses Zuordnungsproblems eingesetzt werden. Viele Programmier sprachen und Betriebssysteme geben dem Programmierer die Möglichkeit, das Zuordnungsproblem selbst zu lösen. Parallele Programmiersprachen sehen zur Sicherung eines exklusiven Zugriffs auf gemeinsamen Ressourcen mehrerer Prozesse sogenannte Locks, Semaphore oder Monitore vor.
Mit dem exklusiven Zugriffsrecht auf Ressourcen handelt man sich aber die Möglichkeit sogenannter Deadlocks ein: Prozeß A besitzt den exklusiven Zugriff auf eine Ressource X, die Prozeß B benötigt. Benötigt Prozeß A aber gleichzeitig den exklusiven Zugriff auf Ressource Y, die Prozeß B gerade besitzt, so können beide Prozesse nicht mehr weiterarbeiten. Dieses Problem tritt möglicherweise in Programmiersprachen mit synchroner Kommunikation zwischen Prozessen noch in anderer Form auf. Von synchroner Kommunikation ist dann die Rede, wenn Sender und Empfänger einer Nachricht sich zum Austausch der Nachricht "synchronisieren" müssen. Hierbei können die Sender erst dann weiterarbeiten, wenn der Empfänger die Nachricht angenommen hat.
Diese Form der Kommunikation ist relativ einfach zu implementieren und wird daher von vielen parallelen Programmiersprachen wie beispielsweise Occamm vorgesehen. Die Programmierung von MIMD-Rechnern auf der Basis des Prozeßmodells konfrontiert den Programmierer also mit einigen neuen Anforderungen:
- Programme müssen explizit in verteilt und parallel zu bearbeitende Prozesse unterteilt werden. Hierzu braucht es verteilte und parallele Algorithmen.
- Prozesse sind gegebenfalls "von Hand" den ausführenden Verarbeitungseinheiten zuzuordnen um die Gesamtausführungszeit zu minimieren.
- Falsch vergebene exklusive Zugriffsrechte auf gemeinsame Ressourcen und fehlerhaft eingesetzte synchrone Kommunikation zwischen Prozessen können zu Deadlocks oder zu Performance Verlusten in der Ausführung führen.
- Das Debugging wird eventuell deutlich aufwendiger: Die Beobachtung vieler parallel ablaufender Prozesse ist schwierig oder gar unmöglich. Zudem müssen noch Grundlagenprobleme gelöst werden, damit die Benutzung von Debuggern nicht das mögliche Verhalten paralleler Programme verändert.
Die Programmierung von MlMD-Rechnern gestaltet sich mit prozeßorientierten Sprachen normalerweise zeitaufwendiger als von sequentiellen Rechnern. Das prozeßorientierte Programmiermodell erlaubt zwar eine gute Nutzung der extrem hohen Performance dieser Rechner, erfordert aber in noch höherem Maße als bei sequentiellen Rechnern eine strenge Disziplin in bezug auf die methodische Entwicklung der Programme.
Um den Aufwand der Programmentwicklung für MIMD-Rechner zu senken, gibt es eine ganze Reihe von High-level-Programmiersprachen, die sich allerdings größtenteils noch als Prototypen in Forschungslabors und Universitäten befinden.
Sprachen auf der Grundlage des Kommunikationsmodells Linda von David Gelernter sehen als zentrale Datenstruktur einen Pool von Nachrichten in Form von Records vor, auf den alle Prozesse eines parallelen Programms zugreifen können. Es gibt keine direkte Kommunikation zwischen den Prozessen. Der lesende Zugriff der Prozesse auf den zentralen Nachrichtenpool erfolgt assoziativ, ähnlich wie der Zugriff auf eine relationale Datenbank. Das Programmiermodell Gamma vor Banatre und LeMetayer sieht aktive Datenstrukturen in Form von Multimengen vor, also Mengen, in denen ein Element auch mehrfach vorkommen kann.
Auf diesen Multimengen wird durch das Programm ein Reaktionskalkül definiert: Elemente können, wenn sie die im Programm definierte Bedingungen erfüllen, miteinander in Reaktion treten und neue Elemente in weiteren Multimengen bilden. Durch den Einsatz dieser High-level-Datenstrukturen ergeben sich für viele Aufgaben in der parallelen Programmierung verblüffend einfache Lösungen Problematisch ist allerdings zu Zeit noch eine allgemeingültige effiziente Implementierung auf Multicomputern.
ParalIele objektorientierte Sprachen wie Smalltalk können um eine Klasse bereichert werden, die die Eigenschaft, "ein Prozeß zu sein", vererbt. Somit werden Objekte, die als Erben dieser speziellen Klasse fungieren, wie Prozesse behandelt. Solche Programmiersprachen bieten dem Programmierer von Parallelrechnern alle bekannten Vorteile objektorientierter Sprachen, sind jedoch relativ komplex. Es gibt auch parallele objektorientierte Sprachen auf der Basis des Actor-Modells von Carl Hewitt, die alle Objekte automatisch wie Prozesse behandeln.
Um Unterschied zu prozeßorientierten Sprachen erfolgt die Kommunikation hier durch Methodenfernaufrufe analog zu Remote Procedure Calls in verteilten Systemen. Solche Methodenfernaufrufe werden oft asynchron ausgeführt, das heißt, der Aufrufer wartet nicht, bis das aufgerufene Objekt die Methode aktiviert hat. Dadurch ergibt sich ein höherer Grad an Parallelismus in der Ausführung des Programms. Dieser Ansatz zur parallelen Programmierung eignet sich besonders gut für die Hardwarestruktur von Multicomputern, da bei der Ausführung eines solchen Programms Daten und Methoden zu ihrer Bearbeitung in integrierter Form, das heißt in Form von Objekten, lokal auf jedem Prozessor vorliegen.
Darüber hinaus gibt es Ansätze, in parallelen objektorientierten Sprachen Maßnahmen zur Fehlertoleranz von Programmen vorzusehen. Derart fehlertolerante Programme laufen auch nach dem Ausfall eines Prozessors in definierter Form weiter. Allerdings trifft die an der parallelen prozeßorientierten Programmierung geübte Kritik auf parallele, objektorientierte Sprachen zum Teil ebenfalls zu.
Das Umdenken könnte sich lohnen
Parallele funktionale und logikorientierte Sprachen lassen sich aus funktionalen und logikorientierten Sprachen wie Prolog oder Lisp entwickeln, indem sie durch Sprachkonstruktionen zur parallelen Ausführung erweitert werden. Andererseits ist es möglich, den inhärenten Parallelismus solcher Programme zu einer automatischen Parallelisierung zu nutzen: Häufig können ja Teilterme eines funktionalen Ausdrucks oder Teilziele eines Logikprogramms unabhängig voneinander ausgewertet werden.
Logikprogramme bieten darüber hinaus die Möglichkeit, verschiedene Alternativen für Teilziele parallel zu behandeln. Diese Art der Parallelausführung wird dem Programmierer bei der Verwendung von funktionalen und logischen Sprachen also leicht gemacht. Eine effiziente Implementierung auf Multicomputern ist jedoch nicht einfach. Neueste Forschungsergebnisse geben jedoch Hoffnung, daß dieser Schritt erreicht sein wird.
MlMD-Rechner stellen in der Testphase eines Programms erhöhte Anforderungen an den Programmierer, wenn eine prozeßorientierte Programmiersprache verwendet wird. Allen High-level-Ansätzen bei MIMD-Rechnern ist gemein, daß sie die Programmierung einfacher und weniger fehleranfällig gestalten. Allerdings ist die Performance im Vergleich zur prozeßorientierten Programmierung sehr niedrig.
An effizienten Implementierungstechniken von High-level-Sprachen zur parallelen Programmierung wird in vielen Forschungsprojekten intensiv gearbeitet. Erhöhter Aufwand bei der Programmierung durch maschinennahe Programmierkonzepte kann die Performance erhöhen. Die Frage ist jedoch, wo der Punkt der Unwirtschaftlichkeit durch die höheren Kosten der Programmerstellung erreicht ist.
Langfristig betrachtet kann das Umdenken auf ein neues zunächt ungewohntes Programmiermodell kostengünstiger sein Eine höhere Standard-Programmiersprache für MIMD-Rechner kündigt sich allerdings noch nicht an. Dazu ist das ganze Gebiet einfach noch zu jung. Sinn macht deshalb die Entwicklung von Sprachen für spezielle Anwendungsklassen (Anwendungsgeneratoren, 4GLs) auf MIMD-Computer, um dem Anwender die Nutzung der Parallelrechner zu vereinfachen. Bei dieser Aufgabe müssen Anwender, Hersteller und Forschungsinstitute künftig eng zusammenarbeiten.