Robert Sedgewick: Algorithmen

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


40. Parallele Algorithmen



Perfektes Mischen

Um einige der Fragen zu illustrieren, die auftreten, wenn Algorithmen in Form von Maschinen anstatt von Programmen implementiert werden, betrachten wir ein interessantes Verfahren für das Mischen, das für eine Hardware-Implementation geeignet ist. Wie wir sehen werden, kann das gleiche allgemeine Verfahren zu einem Entwurf für eine »algorithmische Maschine« weiterentwickelt werden, welche ein grundlegendes Zusammenschaltungsschema enthält, um die parallele Funktion von M Prozessoren bei der Lösung verschiedener Probleme - zusätzlich zum Mischen - zu gewährleisten.

Wie bereits erwähnt, besteht ein prinzipieller Unterschied zwischen der Erstellung eines Programms zur Lösung eines Problems und dem Entwurf einer Maschine darin, daß ein Programm sein Verhalten an die spezielle Instanz des zu lösenden Problems anpassen kann, während die Maschine im voraus »verdrahtet« werden muß, um dann immer die gleiche Folge von Operationen auszuführen. Um diesen Unterschied zu verdeutlichen, betrachten wir das erste von uns untersuchte Programm zum Sortieren, sort3 aus Kapitel 8. Unabhängig von den drei als Eingabedaten dienenden Zahlen führt das Programm stets die gleiche Folge von drei grundlegenden Operationen »Vergleichen-Vertauschen« aus. Keiner der anderen von uns betrachteten Sortieralgorithmen hat diese Eigenschaft. Alle diese Algorithmen führen vielmehr eine Folge von Vergleichen aus, die vom Ergebnis vorangegangener Vergleiche abhängt und daher bei einer Hardware-Implementation zu ernsten Problemen führen würde.

Wenn wir insbesondere eine Hardware-Komponente mit zwei Leitungen für die Eingabe und zwei Leitungen für die Ausgabe haben, die die beiden Zahlen am Eingang vergleichen und sie wenn notwendig für die Ausgabe vertauschen kann, so können wir drei dieser Elemente so miteinander verdrahten, wie es Abbildung 40.1 zeigt. Dadurch entsteht eine Sortiermaschine mit drei Eingängen (in der Abbildung oben) und drei Ausgängen (unten). Hierbei vertauscht der erste Kasten C und B, dann vertauscht der zweite Kasten B und A, und schließlich vertauscht der dritte Kasten C und B und erzeugt damit das sortierte Ergebnis. Die Maschine sortiert jede beliebige Permutation der Eingabedaten (genau wie sort3).

Abbildung 40.1
Abbildung 40.1 Eine Maschine, die drei Elemente sortiert.

Natürlich müssen viele Einzelheiten ausgearbeitet werden, bevor eine reale, auf diesem Schema beruhende Sortiermaschine hergestellt werden kann. Zum Beispiel wurde das Verfahren der Kodierung der Eingabedaten noch nicht angegeben. Eine Möglichkeit wäre, sich jede Leitung in dem obigen Schema als einen »Bus« vorzustellen, der genügend viele Leitungen enthält, um die Daten mit einem Bit pro Leitung zu übertragen; ein anderer Weg wäre, daß man die Sortier-Elemente ihre Eingabedaten bitweise über eine einzige Leitung einlesen läßt (z.B. das Bit mit dem größten Stellenwert zuerst). Gleichfalls noch unberücksichtigt ist die zeitliche Abstimmung: Es müssen Mechanismen vorgesehen werden, die gewährleisten, daß kein Element seine Operation ausführt, bevor seine Eingabedaten bereitgestellt wurden. Natürlich ist es uns nicht möglich, auf diese Aspekte des Schaltungsentwurfs noch ausführlicher einzugehen; stattdessen konzentrieren wir uns auf die auf einer höheren Ebene angesiedelten Fragen, die die Zusammenschaltung einfacher Prozessoren von der Art der Sortier-Elemente zum Zwecke der Lösung umfangreicherer Probleme betreffen.

Zu Beginn betrachten wir einen Algorithmus für das Mischen von zwei sortierten Dateien unter Benutzung einer Folge von Operationen des »Vergleichens-Vertauschens«, die von den zu mischenden Zahlen unabhängig und somit für eine Hardware-Implementation geeignet ist. Abbildung 40.2 zeigt den Ablauf dieses Verfahrens für zwei aus acht Schlüsseln bestehende sortierte Dateien, die zu einer sortierten Datei zusammengemischt werden.

Abbildung 40.2
Abbildung 40.2 Mischen durch Aufspalten und Schichten.

Zuerst schreiben wir eine Datei unter der anderen auf, dann vergleichen wir die vertikal benachbarten Elemente und vertauschen sie, falls notwendig, so daß das größere Element unter dem kleineren steht. Danach spalten wir jede Zeile in zwei Hälften auf und schichten die Hälften übereinander (in der Reihenfolge: erste Hälfte der ersten Zeile, zweite Hälfte der ersten Zeile, erste Hälfte der zweiten Zeile, zweite Hälfte der zweiten Zeile); anschließend führen wir die gleichen Operationen des Vergleichens und Austauschens mit den Zahlen in der zweiten und dritten Zeile aus. (Beachten Sie, daß aufgrund des vorhergehenden Sortiervorgangs keine Vergleiche zwischen anderen Zeilenkombinationen nötig sind.) Im Ergebnis sind sowohl die Zeilen als auch die Spalten der Tabelle sortiert. Diese Tatsache ist eine grundlegende Eigenschaft dieses Verfahrens; der Leser sollte nachprüfen, daß dies zutrifft, obwohl ein strenger Beweis eine schwierigere Übung als erwartet ist.

Es zeigt sich, daß diese Eigenschaft stets erhalten bleibt, wenn die gleiche Operation angewandt wird: Aufspalten jeder Zeile in Hälften, Übereinanderschichten der Hälften und Ausführen von Operationen des Vergleichens und Austauschens für nunmehr vertikal benachbarte Elemente, die aus verschiedenen Zeilen stammen. Bei jedem Schritt wird die Anzahl der Zeilen verdoppelt und die Anzahl der Spalten halbiert, wobei die Zeilen und Spalten sortiert bleiben. Am Anfang liegen 16 Spalten und eine Zeile vor, dann 8 Spalten und 2 Zeilen, dann 4 Spalten und 4 Zeilen, dann 2 Spalten und 8 Zeilen und am Schluß 16 Zeilen und 1 Spalte, die sortiert ist.

Eigenschaft 40.1 Das Mischen von zwei aus N Elementen bestehenden sortierten Dateien kann in ungefähr lg N parallelen Schritten vorgenommen werden.

Falls N = 2n gilt, werden für das soeben beschriebene Verfahren offensichtlich genau n Schritte benötigt, von denen jeder weniger als N/2 unabhängige Vergleiche erfordert. Um zu beweisen, daß mit diesem Verfahren ein Sortieren realisiert wird, genügt es zu zeigen, daß die Spalten sortiert bleiben; dies wird dem Leser, wie oben erwähnt, als Übung überlassen. Dateien anderer Größe lassen sich behandeln, indem man ganz einfach Pseudo-Schlüssel hinzufügt. w.z.b.w.

Die grundlegende Operation in der obigen Beschreibung »spalte jede Zeile in Hälften auf, und schichte die Hälften übereinander« läßt sich auf dem Papier leicht veranschaulichen, doch wie kann man sie in eine Anweisung für eine Maschine übertragen? Auf diese Frage existiert eine überraschende und elegante Antwort, die sich unmittelbar ergibt, wenn man die Tabellen auf andere Weise schreibt. Anstatt sie in einer zweidimensionalen Form anzuordnen, wollen wir sie als einfache (eindimensionale) Liste von Zahlen schreiben, die in einer Reihenfolge mit Spaltenmajorität organisiert ist: Zuerst werden die Elemente aus der ersten Spalte genommen, dann die aus der zweiten Spalte usw. Da Operationen des Vergleichens und Austauschens nur zwischen vertikal benachbarten Elementen erfolgen, bedeutet das, daß in jeder Phase eine Gruppe von Kästen des Vergleichens und Austauschens vorliegt, die miteinander entsprechend der Operation »Aufspalten und Übereinanderschichten« verdrahtet sind, die erforderlich ist, um die Elemente in den Kästen des Vergleichens und Austauschens zusammenzubringen.

Dies führt zu Abbildung 40.3, die exakt der obigen, unter Benutzung von Tabellen gegebenen Beschreibung entspricht, nur daß die Tabellen alle in einer Reihenfolge mit Spaltenmajorität angeordnet sind (einschließlich einer 1x16-Tabelle am Anfang, in der erst die eine Datei und danach die andere erscheint). Der Leser sollte sich auf jeden Fall davon überzeugen, daß dieses Schema den oben angegebenen Tabellen entspricht. Die Kästen des Vergleichens und Austauschens sind explizit dargestellt, und die Linien zeigen, wie sich die Elemente bei der Operation des »Aufspaltens und Schichtens« bewegen; überraschend ist, daß bei dieser Darstellung jede Operation »Aufspalten und Schichten« zu genau dem gleichen Muster der Verbindungen führt. Dieses Muster wird perfektes Mischen (perfect shuffle) genannt, da die Leitungen genau in der gleichen Weise angeordnet sind, wie Karten aus den beiden Hälften bei einem idealen Mischen eines Stoßes Karten »geschichtet« werden.

Abbildung 40.3
Abbildung 40.3 Odd-even
Merging mit perfektem Mischen.

Dieses Verfahren wurde von K. E. Batcher, der es 1968 entwickelte, Odd-even Merge (ungerades-gerades Mischen) genannt. Das wesentliche Merkmal des Verfahrens besteht darin, daß alle Operationen des Vergleichens und Austauschens auf jeder Stufe parallel ausgeführt werden können. Wie Eigenschaft 40.1 besagt, ist das wesentlich, da daraus klar hervorgeht, daß zwei aus N Elementen bestehende Dateien in log N parallelen Schritten gemischt werden können (die Anzahl der Zeilen der Tabelle wird bei jedem Schritt halbiert), unter Benutzung von weniger als N log N Kästen des Vergleichens und Austauschens. Aufgrund der obigen Beschreibung könnte man meinen, daß dies ein sehr einfaches Ergebnis ist; in Wirklichkeit haben sich die Spezialisten recht lange Zeit vergeblich mit dem Problem befaßt, eine solchen Maschine zu finden.

Batcher entwickelte auch einen mit diesem Verfahren eng verwandten (jedoch schwerer verständlichen) Misch-Algorithmus, dem Bitonic Merge (bitonisches Mischen), welches zu der sogar noch einfacheren Maschine führt, die in Abbildung 40.4 dargestellt ist. Dieses Verfahren kann genau wie oben mit Hilfe der Operation »Aufspalten und Schichten« für Tabellen beschrieben werden, mit dem Unterschied, daß wir mit der zweiten Datei in umgekehrt sortierter Reihenfolge beginnen und immer Operationen des Vergleichens und Austauschens zwischen vertikal benachbarten Elementen vornehmen, die aus den gleichen Zeilen stammen. Auf den Beweis, daß dieses Verfahren zum Ziel führt, wollen wir nicht eingehen; für uns ist es deshalb von Interesse, weil bei ihm die störende Eigenschaft des Odd-even Merge beseitigt wird, daß die Kästen des Vergleichens und Austauschens bei der ersten Stufe gegenüber denen bei den folgenden Stufen um eine Position verschoben sind. Wie in Abbildung 40.4 dargestellt, besitzt jede Stufe des Bitonic Merge genau die gleiche Anzahl von Komparatoren an genau den gleichen Positionen.

Abbildung 40.4
Abbildung 40.4 Bitonic Merging mit perfektem Mischen.

Nunmehr liegt nicht nur bei den Verbindungen, sondern auch bei den Positionen der Kästen des Vergleichens und Austauschens Regelmäßigkeit vor. Es gibt mehr Kästen des Vergleichens und Austauschens als beim Odd-even Merge, doch das ist kein Problem, da die gleiche Anzahl von parallelen Schritten ausgeführt wird. Die Bedeutung dieser Methode besteht darin, daß sie unmittelbar zu einem Weg führt, wie das Mischen unter Verwendung von nur N Kästen des Vergleichens und Austauschens ausgeführt werden kann. Die Idee besteht einfach darin, die Zeilen in der obigen Tabelle zu nur einem Paar von Zeilen zusammenzufassen und auf diese Weise eine zyklisch arbeitende Maschine herzustellen, die so wie in Abbildung 40.5 dargestellt verdrahtet ist. Eine solche Maschine kann log N unserer Misch-»Zyklen« ausführen, einen für jede der Stufen in der Abbildung.

Abbildung 40.5
Abbildung 40.5 Eine Maschine für das perfekte Mischen.

Dabei ist besonders zu beachten, daß dies kein ganz »ideales« paralleles Verhalten ist: Da wir mit einem Prozessor zwei aus N Elementen bestehende Dateien mit einer zu N proportionalen Anzahl von Schritten zusammenmischen können, würden wir hoffen, daß es uns gelingt, bei Verwendung von N Prozessoren das Mischen in einer konstanten Anzahl von Schritten auszuführen. Für diesen Fall ist jedoch bewiesen worden, daß es unmöglich ist, dieses Ideal zu erreichen, und daß die obige Maschine das bestmögliche parallele Verhalten beim Mischen erreicht, wenn Kästen des Vergleichens und Austauschens benutzt werden.

Das Muster der Verbindungen des perfekten Mischens ist für eine Vielzahl weiterer Probleme geeignet. Wenn zum Beispiel eine quadratische Matrix der Dimension 2n x 2n in einer Reihenfolge mit Zeilenmajorität abgelegt wird, so bewirken n Operationen des perfekten Mischens das Transponieren der Matrix (ihre Umordnung in eine Reihenfolge mit Spaltenmajorität). Zu weiteren Beispielen gehören die schnelle Fourier-Transformation (die wir im nächsten Kapitel betrachten), das Sortieren (das entwickelt werden kann, indem eine der obigen Methoden rekursiv angewandt wird), die Berechnung von Polynomen und eine Reihe anderer Anwendungen. Jedes dieser Probleme kann gelöst werden, indem eine zyklische Maschine für das perfekte Mischen verwendet wird, die die gleichen Verbindungen wie die oben schematisch dargestellte besitzt, doch andere (etwas kompliziertere) Prozessoren. Einige Forscher schlugen gar vor, das Schema der Verbindungen des perfekten Mischens für »universelle« parallele Computer zu benutzen.


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