Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

22.02.1991 - 

Vier Pro-Argumente gegen acht Kontra-Argumente

Dynamische Algorithmen fordern die parallelen Rechner heraus

Professor. Dr. Ulrich Trottenberg ist Leiter des Forschungsschwerpunktes "Scientific Supercomputing" in der Gesellschaft für Mathematik und Datenverarbeitung (GMD). In seiner Rolle als Initiator und wissenschaftlicher Leiter der nationalen Suprenum-Entwicklung und des europäischen Projekts Genesis zählt er zu den Vorreitern für den Einsatz von Parallelrechnern.

Mit Multigrid-Verfahren können die "großen" Aufgaben der Strömungsmechanik der Elementarteilchenphysik, der Meteorologie, der Klimaforschung und vieler anderer Gebiete um Größenordnungen sehender bearbeitet werden als bisher. Eine besondere Herausforderung stellt dabei der Einsatz der dynamischadaptiven (Multigrid-)Verfahren auf parallelen Superrechnern dar.

"Dem parallelen Rechnen gehört die Zukunft." Vier Argumente habe ich vor einigen Jahren angeführt, um diese These zu begründen. Zunächst die Pro-Argumente :

1. Nur Parallelrechner bieten eine prinzipiell unbegrenzte Leistung, da hierbei beliebig viele Prozessoren (über geeignete Verbindungsstrukturen) zusammengefügt werden können.

2. Parallelrechner bieten prinzipiell ein günstigeres Preis-Leistungs-Verhältnis als herkömmliche Superrechner. Denn sie beziehen ihre Leistung aus der Vielzahl der Prozessoren, nicht aus einer besonders schnellen (und daher teuren) Technologie.

3. Parallelrechner sind prinzipiell allgemeiner einsatzfähig als Vektorrechner, da Vektorverarbeitung eine Spezialform der Parallelverarbeitung ist.

4. Investitionen für die Lösung des Softwareproblems für Parallelrechner (Parallelisierung von Anwendungssoftware etc.) zahlen sich unabhängig von den technologischen Fortschritten auf der Hardwareseite in jedem Fall aus. Denn die Parallelverarbeitung läßt sich mit jeder beliebigen Hardware-Entwicklung kombinieren und bedeutet eine Vervielfachung der Leistung.

Diese Argumente sind auf Skepsis und auf Gegenargumente gestoßen.

Kontra:

1. Nur eine bestimmte Klasse von Anwendungen ist für die Parallelverarbeitung prinzipiell geeignet.

2. Auch dort, wo die Parallelverarbeitung im Prinzip möglich ist, sind die schnellsten bekannten Algorithmen (zum Beispiel dynamisch-adaptive Multigrid-Verfahren) nicht vollständig, sondern nur begrenzt parallelisierbar.

Sofern es wirklich schnelle parallele Verfahren überhaupt gibt, müssen sie erst noch entdeckt beziehungsweise entwickelt werden.

3. Der Geschwindigkeitsgewinn durch Parallelverarbeitung ist - nach Amdahls Gesetz - dadurch limitiert, daß (fast) alle Algorithmen sequentielle Teile enthalten.

4. Parallelrechner sind komplizierter zu programmieren als sequentielle. Es gibt keine Standardprogrammiersprachen für Parallelrechner.

5. Die verschiedenen parallelen Rechnerarchitekturen benutzen unterschiedliche Softwarekonzepte und Programmiermodelle. Portabilität ist daher unter; den parallelen Architekturen nicht gewährleistet.

6. Verglichen mit der immensen Fülle sequentieller Anwendungssoftware, die heute in der Welt ist, ist der Anteil existierender paralleler Anwendungssoftware verschwindend gering. Wer soll die Portierung vornehmen?

Die "automatische Parallelisierung" beziehungsweise eine Entwicklung von entsprechenden Werkzeuge steht erst am Anfang.

7. Die Softwarehäuser warten ab. Noch haben sie sich auf die parallele Welt nicht eingelassen. Der Markt ist schmal.

8. Die etablierten Rechnerhersteller betreten die parallele Welt sehr vorsichtig. In der kommerziellen Datenverarbeitung spielen parallele Systeme bisher nur eine marginale Rolle.

Vier Pro-Argumente gegen acht Kontra-Argumente. Und doch hat die Entwicklung der letzten Jahre die Eingangsthese bestätigt. In der Welt des Scientific Computing, dort, wo hohe und höchste Rechenleistung für die numerische Simulation benötigt wird, hat man die Bedeutung der Parallelverarbeitung erkannt. Einen starken Impuls auf die Forschungsszene in Deutschland hat das Suprenum-Projekt ausgeübt. Das parallele Softwareproblem, vor einigen Jahren noch als ungelöst betrachtet, wird in wesentlichen Bereichen heute beherrscht. Die Skepsis ist gewichen. Alle Hersteller paralleler Systeme haben davon profitiert.

Andere neue Gebiete, wie die Neuroinformatik, enthalten die Parallelverarbeitung - in spezifischen Ausprägungen - als ein tragendes Element. Was also ist zu den obigen Gegenargumenten zu sagen? Sind sie alle durch die Wirklichkeit bereits widerlegt?

Eine systematische Überprüfung der obigen Gegenargumente wurde eine differenziertere Betrachtung und eine Unterscheidung verschiedener Klassen paralleler Architekturen erfordern, zum Beispiel

- SIMD versus MIMD,

- globaler versus verteilter Speicher,

- hohe versus geringe Leistung des Einzelprozessors.

Wirklichkeit besteht aus parallelen Ereignissen

Generell kann man sicher sagen, daß die letzten fünf Argumente keine Aussage über die Zukunft, sondern über die Gegenwart machen. Die hier angesprochenen Probleme werden Schritt für Schritt aus der Welt geschafft werden.

Die ersten drei Argumente sind grundsätzlicher Natur. Sie betreffen die inhärente Parallelität in den Anwendungen und die parallele Algorithmik. Mit diesen Argumenten wollen wir uns im folgenden etwas genauer auseinandersetzen.

Eine erste, grundlegende Feststellung betrifft die Parallelität, die wir in der Welt vorfinden: Unsere Wirklichkeit in Raum und Zeit verläuft zeitlich sequentiell; zu jedem festen Zeitpunkt ist der Raum jedoch von einer Vielzahl gleichzeitig ablaufender örtlich verteilter Vorgänge erfüllt. Das heißt: In der Wirklichkeit haben wir es mit zeitlicher Sequentialität und räumlicher Parallelität zu tun.

Je feiner das Gitter, um so sicherer die Prognose

Diese Eigenschaften weisen natürlicherweise daher auch die mathematischen Modelle auf, die Phänomene der Wirklichkeit beschreiben. Sie enthalten eine inhärent räumliche Parallelität und sind damit prinzipiell auf einen Parallelrechner abbildbar. Dies gilt insbesondere für alle Modelle aus den Bereichen des Scientific Computing und der numerischen Simulation, die schon heute auf Superrechner angewiesen sind: Strömungsmechanik, Strukturmechanik, Meteorologie, Klimaforschung, Teilchenphysik, Plasmaphysik, Chemie/Pharmazie, Ölexploration etc.

Ein typisches Beispiel: In der mittelfristigen Wettervorhersage (Drei- bis Zehn-Tages-Vorhersage) werden globale Wettermodelle auf einem räumlichen dreidimensionalen Gitter gerechnet, das die gesamte Erdatmosphäre beschreibt. Je feiner das 3D-Gitter, um so genauer beschreibt das Modell die realen Verhältnisse und um so größer ist die Wahrscheinlichkeit einer zutreffenden beziehungsweise exakten Prognose. Auch der für die Prognose festgelegte Zeitraum wird in kleine Zeitschritte zerlegt. Die Rechnung schreitet in diesen Zeitschritten fort; dabei werden in jedem Zeitschritt Rechenoperationen in sämtlichen 3D-Gitterpunkten durchgeführt. Die räumliche Parallelität dieser Anwendung bedeutet hier, daß diese Operationen pro Zeitschritt für alle Gitterpunkte (oder einen großen Teil davon) gleichzeitig ausgeführt werden können.

Jeder Prozessor arbeitet nur auf einem Teilgitter

Der Einsatz eines Parallelrechners für die Rechnung liegt hier unmittelbar nahe: Das 3D-Gitter wird in einer statischen Weise auf die Multiprozessor-Architektur abgebildet, und zwar so, daß jeder Prozessor ein ihm zugeordnetes Teilgitter bearbeitet. Alle Prozessoren arbeiten gleichzeitig auf diesen Teilgittern - die gleich groß sein sollten, um eine gleichmäßige Auslastung der Prozessoren sicherzustellen. Von Zeit zu Zeit ist ein Informations- beziehungsweise Datenaustausch erforderlich, der von den Kommunikationseinrichtungen des Multiprozessorsystems (oder über einen globalen Speicher) abgewickelt wird.

Speed-up ist abhängig von der Gitterdichte

Der Kommunikations-Overhead spielt eine untergeordnete Rolle, wenn sichergestellt ist daß jeder Prozessor hinreichend viele Gitterpunkte zu bearbeiten hat - das heißt wenn das Gitter fein genug beziehungsweise das Modell genau genug ist. Man kommt dann an den idealen Speed-up (Verringerung der Rechenzeit um den Faktor p beim Einsatz von p Prozessoren) nahe heran.

So weit, so gut. Wie bei diesem Beispiel spielt Amdahls Gesetz (Gegenargument 3) bei den typischen parallelen Anwendungen keine signifikante Rolle.

Und weil das Beispiel repräsentativ ist für den größten Teil des heutigen Scientific Computing, gilt auch Gegenargument 1 nicht: Da, wo herkömmliche Superrechner benötigt und eingesetzt werden, sind auch parallele Superrechner einsetzbar, und zwar mit Gewinn.

Es bleibt Gegenargument 2. So pauschal, wie dieses Argument oben angeführt wurde, trifft es sicher nicht zu. Und doch liegt in dem Bereich, auf den dieses Argument anspielt, tatsächlich eine wesentliche Herausforderung für die zukünftige numerische Forschung.

In vielen Anwendungen des Scientific Computing geht es nämlich nicht nur um die Beschreibung globaler Phänomene, sondern zusätzlich um eine möglichst genaue Erfassung lokaler Effekte - und ihrer globalen Auswirkungen (Umströmung von Flug- oder Fahrzeugen mit lokalen Einflüssen durch Kanten; Ausbreitung von Schadstoffen aus lokalen Quellen und ähnlichem). Hier sind statische 3D-Gitter eines bestimmten a priori festgelegten Feinheitsmaßes nicht angemessen.

Lokale Phänomene fordern dynamischen Gitteraufbau

Viel zweckmäßiger und für die Rechnung ökonomischer sind dynamische Gitterstrukturen, die sich den lokalen Phänomenen automatisch (durch die Rechnung gesteuert) anpassen: Da, wo lokal viel passiert, wird das Gitter automatisch verfeinert, da, wo wenig geschieht, wird ein gröberes Gitter verwendet.

In der Kombination dieser Idee mit dem Multigrid-Ansatz liegt eine besonders zukunftsträchtige numerische Thematik, die ganz neue Möglichkeiten eröffnet.

Die Frage, wie solche dynamisch-adaptiven Gitterstrukturen und -verfahren der Zukunft sich auf Parallelrechnern verhalten, ist noch nicht schlüssig beantwortet. Wollte man an dem statischen Abbildungsmodell

Gitteraufteilung < - > Multiprozessorsystem

Teilgitter < - > Einzelprozessor,

wie es oben für das meteorologische Beispiel beschrieben wurde, festhalten, würde der Gitterdynamik nicht hinreichend Rechnung getragen, und es ergäben sich stark ungleichmäßige Arbeitslasten. Will man jedem Prozessor immer die gleiche Arbeitslast (gleiche Anzahl von Gitterpunkten) zuordnen, dann sind Gitterstrukturen in der Architektur ständig neu zu verteilen - und damit beträchtliche interne Datenflüsse zu bewältigen.

Dies sind die Probleme. Lösungsansätze und -vorschläge liegen vor. Wegen der Komplexität der Aufgabenstellung konnten bisher jedoch nur wenige praktische Erfahrungen auf diesem Gebiet gesammelt werden. Die Forschung des Scientific Supercomputing und der parallelen Numerik wird sich in den nächsten Jahren auf diese Themen konzentrieren.