Sortieren auf zweidimensionalen Prozessorfeldern

Das Sortiernetz Odd-even Transposition Sort lässt sich sehr gut auf einem ein­dimensionalen Prozessor­feld implementieren. Dabei hält jeder Prozessor ein Datenelement. Ein Vergleichs-Austausch-Schritt wird realisiert, indem jeweils zwei benachbarte Prozessoren ihr eigenes Datenelement mit dem des Nachbarn vergleichen und gegebenen­falls vertauschen. Bild 1 zeigt einen Odd- und einen Even-Schritt von Odd-even Trans­position Sort auf einem ein­dimensionalen Prozessor­feld.

In Prozessor­feldern können nur benachbarte Prozessoren miteinander kommunizieren. Dies gilt auch für zwei­dimensionale Prozessor­felder, hier hat jeder Prozessor allerdings noch zwei weitere Nachbarn in senkrechter Richtung. Bild 2 zeigt zwei mögliche Sortier­schritte auf einem zwei­dimensionalen Prozessor­feld.

Problem

Die Definition des Sortier­problems wird zunächst verall­gemeinert, damit nicht nur ein­dimensionale Datenfelder, sondern auch zwei­dimensionale (und darüber hinaus beliebige) Datenfelder behandelt werden können.

Beispiel:  Bei Datenfolgen entspricht r(i) = i auf­steigender Sortier­richtung, r(i) = n – 1 – i absteigender Sortier­richtung.

Bei n×n-Datenfeldern sind folgende Sortier­richtungen üblich:

zeilenweise:		r(i, j)  =   i·n + j
in Schlangen­linie:		r(i, j)  =   i·n + j        falls  i gerade i·n + n – 1 – j     falls  i ungerade

Die n×n-Datenfelder sollen auf einem n×n-Prozessor­feld sortiert werden. Die Daten sind den Prozessoren in natürlicher Weise so zugeordnet, dass jeder Prozessor (i, j) das Datenelement a_i, j enthält. Die Sortier­richtung soll stets zeilenweise aufsteigend sein.

Untere Schranken

Befindet sich das kleinste Element anfangs in der rechten unteren Ecke des n×n-Feldes, so benötigt es mindestens 2n – 2 Schritte, um in die linke obere Ecke zu kommen. Diese triviale untere Schranke wurde von Kunde auf 3n – 2n – 3 Schritte verbessert [Kun 87].

In Bild 3 ist ein n×n-Feld dargestellt. Das einge­zeichnete rechte untere Dreieck des Feldes wird Jokerzone genannt, da die Daten in dieser Zone zunächst noch nicht festgelegt werden. Außerhalb der Jokerzone ist das Feld mit lauter ver­schiedenen Daten belegt.

Die Daten­elemente der Jokerzone können frühestens nach 2n – 2n – 2 Schritten die linke obere Ecke des Feldes erreichen. Das Element x, das zu diesem Zeitpunkt in der linken oberen Ecke steht, ist also unabhängig von den Daten der Jokerzone: ganz gleich, welche Werte die Daten der Jokerzone haben, wird nach 2n – 2n – 2 Schritten stets dasselbe Element x in der linken oberen Ecke stehen.

Die Werte der Daten­elemente der Jokerzone werden nun so gewählt, dass das Element x in der sortierten Reihenfolge an den rechten Rand des Feldes gehört. Da die Jokerzone n Elemente enthält, ist genug "Manövrier­masse" vorhanden, um x an den rechten Rand zu drängen. Das Element x muss also nach dem 2n – 2n – 2-ten Schritt noch einen Weg der Länge n-1 zurücklegen, sodass insgesamt mindestens 3n – 2n – 3 Schritte erforderlich sind, um das Feld zu sortieren.

Sortierverfahren auf n×n-Prozessorfeldern

Bereits 1977 ver­öffentlichten Thompson und Kung eine Arbeit über das Sortieren auf einem n×n-Prozessor­feld [TK 77]. Der dort vorgestellte Algorithmus s²-way Mergesort war sowohl asymptotisch als auch hinsichtlich der Konstanten vor dem Term höchster Ordnung bereits optimal. Die Komplexität des Algorithmus beträgt 3n + O(n^2/3 log(n)) Vergleichs-Austausch-Operationen.

Danach erschien noch eine ganze Reihe weiterer Arbeiten, in denen Sortier­verfahren für n×n-Prozessor­felder mit der Zeit­komplexität O(n) vorgestellt wurden (u.a. [LSSS 85], [SchSh 86], [MG 88]). Diese Verfahren sind teilweise einfacher als das Verfahren von Thompson-Kung, jedoch alle langsamer. Lediglich der Algorithmus 3n-Sort von Schnorr und Shamir [SchSh 86] erreicht mit 3n + O(n^3/4) Schritten dieselbe Konstante vor dem Term höchster Ordnung.

Als besonders einfache und gut zu implementierende Verfahren sollen im Folgenden zunächst die Verfahren LS3-Sort von Lang, Schimmler, Schmeck und Schröder [LSSS 85] sowie 4-way Mergesort von Schimmler [Schi 87] angegeben werden, ferner das ideenreiche, aber etwas langsamere Verfahren Rotatesort von Marberg und Gafni [MG 88].

Literatur

[Kun 87]   M. Kunde: Lower Bounds for Sorting on Mesh-Connected Architectures. Acta Informatica 24, 121-130 (1987)

[LSSS 85]   H.W. Lang, M. Schimmler, H. Schmeck, H. Schröder: Systolic Sorting on a Mesh-Connected Network. IEEE Transactions on Computers C-34, 7, 652-658 (1985)

[MG 88]   J.M. Marberg, E. Gafni: Sorting in Constant Number of Row and Column Phases on a Mesh. Algorithmica 3, 561-572 (1988)

[Schi 87]   M. Schimmler: Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut für Informatik, Christian-Albrechts-Universität Kiel (1987)

[SchSh 86]   C.P. Schnorr, A. Shamir: An Optimal Sorting Algorithm for Mesh-Connected Computers. Proc. of the 18th ACM Symposium on Theory of Computing, 255-261 (1986)

[TK 77]   C.D. Thompson, H.T. Kung: Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM, 20, 4, 263-271 (1977)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Die parallelen Sortierverfahren LS3-Sort, Rotatesort und 3n-Sort finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie.

[Weitere Informationen]