Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


40. Parallele Algorithmen



Allgemeine Ansätze

Einige grundlegende Algorithmen werden so häufig und für derart umfangreiche Probleme angewandt, daß ein ständiger Bedarf vorhanden ist, sie auf immer größeren und schnelleren Computern zu realisieren. Ein Ergebnis davon war eine Reihe von »Supercomputern«, in denen die neuesten Technologien verwirklicht sind; trotz einiger Zugeständnisse an die grundlegende Konzeption von von Neumann sind sie als Allzweck-Computer konstruiert und für alle Programme von Nutzen. Die übliche Vorgehensweise bei der Anwendung einer solchen Maschine für die von uns betrachtete Problemarten besteht darin, mit den Algorithmen zu beginnen, die im Falle herkömmlicher Maschinen am besten geeignet sind, und sie an die speziellen Merkmale der neuen Maschine anzupassen. Diese Herangehensweise begünstigt natürlich den Fortbestand alter Algorithmen und alter Strukturen auf neuen Maschinen.

In jüngster Zeit sind Mikroprozessoren mit beachtlicher Rechenleistung sehr preiswert geworden. Ein sich offensichtlich anbietender Ansatz besteht in dem Versuch, eine große Anzahl dieser Prozessoren zusammen einzusetzen, um ein größeres Problem zu lösen. Manche Algorithmen lassen sich gut an eine derartige »Verteilung« anpassen; andere sind für eine derartige Implementation einfach nicht geeignet.

Die Entwicklung von preiswerten, relativ leistungsfähigen Prozessoren führte auch zur Schaffung von universellen Werkzeugen für die Anwendung bei der Entwicklung und Herstellung neuer Prozessoren. Dies wiederum führte zu einer erhöhen Aktivität auf dem Gebiet der Entwicklung von spezialisierten Maschinen für spezielle Probleme. Falls für die Realisierung eines bestimmten wichtigen Algorithmus keine Maschine besonders gut geeignet ist, so können wir speziell dafür eine entwickeln und herstellen! Für viele Probleme können geeignete Maschinen konstruiert und gebaut werden, die sich auf einem VLSI-Chip unterbringen lassen.

Ein gemeinsames Merkmal all dieser Ansätze ist Parallelität: Wir versuchen, Zeit einzusparen, indem wir zu jedem Zeitpunkt möglichst viele verschiedene Dinge gleichzeitig geschehen lassen. Dies kann zu einem Chaos führen, wenn es nicht in einer geordneten Weise erfolgt. Im folgenden betrachten wir zwei Beispiele, die bestimmte Verfahren zur Erzielung eines hohen Grades an Parallelität für gewisse Problemklassen illustrieren. Die Grundidee besteht in der Annahme, daß wir nicht nur über einen, sondern über M Prozessoren verfügen, auf denen unser Programm abgearbeitet werden kann. Daher können wir, bei Erfolg, hoffen, daß wir unser Programm M mal so schnell wie zuvor abarbeiten lassen können.

Wenn wir erreichen wollen, daß M Prozessoren bei der Lösung ein und derselben Aufgabe zusammenarbeiten, treten sofort mehrere Probleme auf. Das wichtigste ist, daß sie in irgendeiner Weise in Kommunikation treten müssen: Es müssen Leitungen vorhanden sein, die sie miteinander verbinden, und spezielle Mechanismen, um über diese Leitungen Daten in beiden Richtungen zu übertragen. Weiterhin existieren physikalische Beschränkungen hinsichtlich der zulässigen Zusammenschaltungen. Nehmen wir zum Beispiel an, daß unsere »Prozessoren« einzelne Chips sind (diese können heute mehr Schaltkreise enthalten als kleine Computer der Vergangenheit), die beispielsweise 32 Pins für Verbindungen besitzen. Selbst wenn wir 1000 solcher Prozessoren hätten, könnten wir dann jeden nur mit höchstens 32 anderen verbinden. Die Entscheidung über die Zusammenschaltung der Prozessoren ist bei paralleler Verarbeitung von grundlegender Bedeutung. Darüber hinaus ist es wichtig zu berücksichtigen, daß diese Entscheidung im voraus getroffen werden muß: Ein Programm kann die Art und Weise, wie es seine Aufgabe ausführt, in Abhängigkeit von der speziellen Instanz des zu lösenden Problems verändern, doch eine Maschine kann im allgemeinen nicht die Art und Weise ändern, in der ihre Komponenten miteinander verdrahtet sind.

Dieses allgemeine Schema der parallelen Verarbeitung, das auf unabhängigen Prozessoren mit einer festen Zusammenschaltung beruht, gilt für jeden der drei oben beschriebenen Bereiche: Ein Supercomputer besitzt sehr spezielle Prozessoren und Verbindungsschemata, die integraler Bestandteil seiner Architektur sind (und viele Aspekte seines Verhaltens beeinflussen); zusammengeschaltete Mikroprozessoren entsprechen einer relativ kleinen Anzahl leistungsfähiger Prozessoren mit einfachen Verbindungen zwischen ihnen; Schaltungen mit sehr hohem Integrationsgrad (VLSI) selbst umfassen eine sehr große Zahl einfacher Prozessoren (Schaltelemente) mit komplizierten Verbindungen.

Seit von Neumann sind viele andere Aspekte der parallelen Verarbeitung gründlich untersucht worden, wobei das Interesse erneut zunimmt, seit preiswerte Prozessoren zur Verfügung stehen. Es würde mit Sicherheit über den Rahmen dieses Buches hinausgehen, wenn man alle damit zusammenhängenden Fragen behandeln wollte. Stattdessen wollen wir zwei spezielle Maschinen betrachten, die für einige vertraute Probleme entwickelt wurden. Die Maschinen, die wir untersuchen, veranschaulichen den Einfluß der Maschinenarchitektur auf die Entwicklung der Algorithmen und umgekehrt. Hier liegt eine gewisse Symbiose vor: Sicher würde man keinen neuen Computer konstruieren, ohne eine Vorstellung davon zu haben, wofür er benutzt werden soll, und für die Realisierung der wichtigsten grundlegenden Algorithmen möchte man die besten verfügbaren Computer einsetzen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]