Robert Sedgewick: Algorithmen

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


40. Parallele Algorithmen



Ausblick

Die Betrachtung des perfekten Mischens und systolischer Maschinen veranschaulicht, daß der Hardware-Entwurf einen erheblichen Einfluß auf den Algorithmen-Entwurf haben kann, indem er zu Änderungen anregt, die interessante neue Algorithmen liefern und neue Herausforderungen an den Algorithmen-Entwickler stellen können.

Obwohl dies ein interessantes und fruchtbares Gebiet für weitere Forschungsarbeiten ist, müssen wir mit einigen ernüchternden Bemerkungen schließen. Zunächst ist ein erheblicher technischer Aufwand notwendig, um allgemeine Schemata für parallele Berechnungen der oben skizzierten Art in wirkliche algorithmische Maschinen mit hoher Leistungsfähigkeit zu übertragen. Für viele Anwendungszwecke ist der erforderliche Aufwand einfach nicht gerechtfertigt, da eine einfache »algorithmische Maschine«, die aus einem herkömmlichen (billigen) Mikroprozessor besteht, der einen herkömmlichen Algorithmus realisiert, völlig ausreichend ist. Wenn man etwa viele Instanzen des gleichen Problems zu lösen hat und über mehrere Mikroprozessoren verfügt, mit denen sie gelöst werden können, kann eine ideale parallele Verarbeitung erreicht werden, indem man - ohne jede Zusammenschaltung - jeden Mikroprozessor (unter Anwendung eines herkömmlichen Algorithmus) eine andere Instanz des Problems bearbeiten läßt. Wenn man N Dateien zu sortieren hat und N Prozessoren zur Verfügung stehen, mit denen sie sortiert werden können, warum sollte man nicht einfach für jeden Sortiervorgang einen Prozessor verwenden, anstatt alle N Prozessoren gemeinsam an allen N Sortiervorgängen arbeiten zu lassen?

Es ist sehr schwierig, die Auswirkung verschiedener Strategien der parallelen Berechnung auf die Leistungsfähigkeit von Algorithmen einzuschätzen. Alle in den Kapiteln 6 und 7 erörterten Aspekte müssen berücksichtigt werden, wobei die zusätzliche Komplikation auftritt, daß die Maschine selbst zu einer Variablen wird. Die einfachste (und vielleicht verbreitetste) Methode, Maschinen zu vergleichen, kann zu völlig falschen Schlußfolgerungen führen: Wenn man das gleiche Programm auf beiden Maschinen abarbeiten läßt, so ist dies genau das falsche Experiment, falls der zugrunde liegende Algorithmus in enger Beziehung zu der Architektur der einen, aber nicht der anderen Maschine steht. Im Falle der Übereinstimmung muß das Ergebnis viel besser ausfallen als bei Nichtübereinstimmung. Um Maschinen richtig zu vergleichen, sollte man seine Aufmerksamkeit auf das zu lösende Problem konzentrieren und den besten Algorithmus für dieses Problem auf jeder Maschine betrachten. Gestattet uns die neue Architektur, ein Problem zu lösen, das mit einer alten Architektur nicht gelöst werden könnte?

Methoden von der in diesem Kapitel betrachteten Art lassen sich gewöhnlich nur für Anwendungen mit sehr spezifischen Anforderungen an Zeit oder Speicherplatz rechtfertigen. Indem wir verschiedene parallelen Berechnungsschemata und ihre Auswirkungen auf die Leistungsfähigkeit verschiedener Algorithmen untersuchen, können wir auf die Entwicklung von universellen Computern für die parallele Berechnung hoffen, die für eine Vielzahl von Algorithmen eine erhöhte Leistungsfähigkeit gewährleisten werden.


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