Robert Sedgewick: Algorithmen

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


40. Parallele Algorithmen



Die Algorithmen, die wir untersucht haben, sind hinsichtlich ihrer Anwendbarkeit meist bemerkenswert robust. Die meisten betrachteten Verfahren sind bereits zehn oder mehr Jahre alt und haben viele sehr radikale Veränderungen auf dem Gebiet der Computer-Hardware und -Software überlebt. Neuentwicklungen im Bereich der Hardware und neue Möglichkeiten der Software können sicher auf spezielle Algorithmen einen wesentlichen Einfluß haben, doch gute Algorithmen auf alten Maschinen erweisen sich in den meisten Fällen als gute Algorithmen auf neuen Maschinen.

Ein Grund dafür ist, daß sich der grundlegende Aufbau »herkömmlicher« Computer im Laufe der Jahre nur wenig verändert hat. Der Aufbau der großen Mehrheit der Computersysteme beruht auf dem gleichen Grundprinzip, das in den frühen Tagen der modernen Computertechnik von dem Mathematiker John von Neumann entwickelt wurde. Wenn wir von dem von Neumann-Rechner sprechen, meinen wir ein Schema der Berechnung, bei dem Anweisungen und Daten im gleichen Speicher abgelegt werden und ein einziger Prozessor Anweisungen aus dem Speicher entnimmt und eine nach der anderen ausführt (vielleicht indem er Operationen mit den Daten ausführt). Es wurden ausgeklügelte Mechanismen entwickelt, um Computer billiger, schneller, kleiner (physikalisch) und größer (logisch) zu machen, doch die Architektur der meisten Computersysteme kann als Variation des von Neumannschen Themas betrachtet werden.

Vor kurzer Zeit haben jedoch radikale Veränderungen bei den Kosten der Computerbauteile dazu geführt, daß es erstmals praktisch möglich wurde, völlig andere Maschinentypen zu betrachten, solche, bei denen zu jedem Zeitpunkt eine große Anzahl von Anweisungen ausgeführt wird, oder bei denen die Anweisungen »fest verdrahtet« sind. Dadurch werden für spezielle Zwecke bestimmte Maschinen befähigt, nur ein bestimmtes Problem zu lösen, oder eine große Anzahl kleinerer Maschinen kann bei der Lösung des gleichen Problems zusammenwirken. Kurz gesagt, anstatt eine Maschine zu jedem Zeitpunkt nur eine Anweisung ausführen zu lassen, können wir die Möglichkeit ins Auge fassen, eine große Zahl von Operationen gleichzeitig zu realisieren. Im vorliegenden Kapitel wollen wir die potentiellen Auswirkungen dieser Ideen auf einige der von uns untersuchten Probleme und Algorithmen darlegen. Insbesondere betrachten wir zwei Ansätze für die Architektur von Maschinen, die die Entwicklung von parallelen Algorithmen ermöglichen: Das perfekte Mischen (perfect shuffle) und das systolische Feld (systolic array).


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