Sortieren auf zweidimensionalen Prozessorfeldern

Das Verfahren von Thompson und Kung [TK 77] für das Sortieren auf zwei­dimensionalen Prozessor­feldern ist nicht nur asymptotisch, sondern auch hinsichtlich seiner Konstanten optimal.

Idee

Der Algorithmus Odd-even Merge [Bat 68] wird auf zwei­dimensionale Felder angewendet. Durch die Operation unshuffle werden die Elemente an geraden Positionen und die Elemente an ungeraden Positionen getrennt, jeweils für sich sortiert und durch die Operation shuffle wieder zusammen­geführt.

Es werden drei Varianten von Algorithmen auf Grundlage dieser Idee entwickelt. Ausgangs­situation ist jeweils ein k×m-Feld, das aus 2, aus 2s bzw. aus s² in Schlangen­linie sortierten Teilfeldern besteht. Die Korrektheit der Verfahren wird mit Hilfe des 0-1-Prinzips gezeigt. Es wird daher von einer Belegung der Felder mit Nullen (weiß) und Einsen (grau) ausgegangen (Bild 1).

Bild 1: Ausgangssitutation für die Algorithmen 2-way-merge, 2s-way-merge und s²-way-merge

Grundoperationen

Die Algorithmen greifen auf die Grund­operationen shuffle, unshuffle, oddexchange und oets zurück.

shuffle

Ein pro­fessioneller Karten­spieler mischt einen Stoß Spielkarten, indem er die erste und die zweite Hälfte reiß­verschluss­artig ineinander gleiten lässt. Die englische Bezeichnung hierfür ist perfect shuffle oder kurz shuffle. Sie steht für folgende Permutation, hier dargestellt für n = 8 Elemente:

Auf Prozessor­feldern kann die Permutation shuffle durch ein "Dreieck" von Ver­tauschungen zwischen Nachbar­elementen hergestellt werden:

unshuffle

Die Permutation unshuffle ist die inverse Permutation von shuffle:

Die Permutation unshuffle entsteht, wenn Spielkarten reihum an zwei Spieler verteilt werden. Der erste Spieler erhält die "geraden" Spielkarten, d.h. die Karten 0, 2, 4, 6 usw.; der zweite Spieler erhält die "ungeraden" Spielkarten, d.h. 1, 3, 5, 7 usw.

Auch die Permutation unshuffle kann auf Prozessor­feldern durch ein Dreieck von Ver­tauschungen zwischen Nachbar­elementen hergestellt werden:

oddexchange

Die Operation oddexchange wird auf ein zwei­dimensionales k × m-Feld angewandt. Sie bewirkt eine Vertauschung aller Elemente an den Positionen (i, j), wobei i ungerade und j gerade, mit den entsprechenden rechten Nachbar­elementen (i, j+1) (i ∈ {0, ..., k-1}, j ∈ {0, ..., m-1}).

Ist die Sortier­richtung auf dem zwei­dimensionalen Feld die Schlangen­linie, so kommen hierdurch alle Elemente der Folge, die sich an den geraden Positionen der Sortier­reihen­folge befinden ("gerade Elemente"), in eine Spalte mit geradem Spaltenindex ("gerade Spalte"), entsprechendes gilt für die ungeraden Elemente (Bild 2).

oets

Die Operation oets steht für einen Schritt von Odd-even Trans­position Sort. Bei einem Even-Schritt werden alle geraden Elemente mit ihren rechten Nachbar­elementen verglichen und gegebenen­falls vertauscht, bei einem Odd-Schritt alle ungeraden Elemente. Odd- und Even-Schritte werden abwechselnd angewendet.

2-way-merge

Der folgende Algorithmus 2-way-merge ist zunächst die einfachste Implementation für ein k × m-Feld, wobei k, m Zweier­potenzen sind.

Prozedur 2-way-merge(k, m)

Eingabe:

k × m-Feld (m > 1), dessen linke und rechte Hälfte jeweils in Schlangenlinie sortiert ist (Bild 1a)

Ausgabe:

das in Schlangenlinie sortierte k × m-Feld

Methode:

1. wenn m > 2 dann
1. oddexchange
2. unshuffle in den Zeilen
3. 2-way-merge(k, m/2) rekursiv auf linke und rechte Hälfte anwenden
4. shuffle in den Zeilen
5. oddexchange
6. 2 oets-Schritte auf der Schlangenlinie
2. sonst
1. 2-column-merge(k)

Die Rekursion bricht ab, wenn jeweils nur noch zwei Spalten zu verschmelzen sind. Dann wird das folgende Verfahren 2-column-merge verwendet.

Prozedur 2-column-merge(k)

Eingabe:

k × 2-Feld, dessen linke und rechte Spalte sortiert ist

Ausgabe:

das in Schlangenlinie sortierte k × 2-Feld

Methode:

1. oddexchange
2. Sortieren der Spalten
3. 2 oets-Schritte auf der Schlangenlinie

Korrektheit von 2-way-merge

Nach dem 0-1-Prinzip kann von einer Belegung des Feldes mit Nullen und Einsen ausgegangen werden.

1. Fall: m > 2

Durch Schritt 1 kommen alle geraden Elemente der Sortier­reihen­folge in eine gerade Spalte, alle ungeraden Elemente in eine ungerade Spalte.

In jeder der beiden Hälften des Feldes können dadurch die ungeraden Spalten zusammen­genommen eine Eins mehr enthalten als die geraden. Dies liegt daran, dass bei ungeradem Gewicht einer Hälfte die "überzählige" Eins sich zunächst an einer ungeraden Position der Sortier­reihen­folge befindet. Nach Schritt 1 befindet sie sich somit in einer ungeraden Spalte.

In Schritt 2 werden durch die unshuffle-Operation alle geraden Spalten nach links, alle ungeraden Spalten nach rechts verschoben. Das Gewicht der rechten Hälfte ist anschließend um höchstens 2 größer als das der linken Hälfte.

In Schritt 3 werden die linke und die rechte Hälfte rekursiv sortiert.

Anschließend wird die Permutation der Schritte 1 und 2 wieder rückgängig gemacht (Schritte 4 und 5).

Das Ergebnis ist eine Folge, die aus zwei ineinander ver­schränkten (geshuffelten) sortierten Folgen besteht, von denen die zweite ein um höchstens 2 höheres Gewicht als die erste hat. In Schritt 6 wird die dadurch entstehende unsortierte Zone auf der Schlangen­linie mit 2 oets-Schritten bereinigt (tatsächlich genügt sogar ein Schritt, wenn mit dem richtigen Schritt (odd) angefangen wird).

2. Fall: m = 2

Die Korrektheit von 2-column-merge wird anhand von Bild 3 dargestellt.

Ausgangs­situation ist ein k × 2-Feld, dessen beide Spalten sortiert sind (a). Durch die Vertauschung in ungeraden Zeilen werden die Einsen gleichmäßig auf beide Spalten verteilt (b). Dann werden die Spalten sortiert. Eine Spalte kann eine Eins mehr enthalten als die andere (c). Tatsächlich genügt ein Even-Schritt von Odd-even Trans­position Sort, um das Feld in Schlangen­linie zu sortieren (d).

Analyse von 2-way-merge

Mit T(k, m) sei die Anzahl der Operationen von 2-way-merge(k, m) bezeichnet. T(k, 2) ist die Anzahl der Operationen von 2-column-merge(k). Für m > 2 ergibt sich folgende Anzahl von Operationen T(k, m) :

Die Schritte 1, 2 und 4, 5 benötigen zusammen genau m Operationen. Somit ist für m > 2

T(k, m)  =  m + 2 + T(k, m/2)

Mit T(k, 2) = k + 3 ergibt sich

T(k, m)  =  k + 2m + 2 log(m) – 3

Sortieren mit 2-way-merge

Aus dem Merge-Verfahren lässt sich rekursiv ein Sortier­verfahren für ein n × n-Feld konstruieren. Da jedoch nur in horizontaler Richtung jeweils eine Reduktion der Feldgröße um die Hälfte stattfindet, liegt die Komplexität dieses Verfahrens in O(n·log(n)).

Es liegt daher nahe, die Feldgröße in jedem Rekursions­schritt des Sortier­verfahrens auch in vertikaler Richtung zu halbieren. Entsprechend wird dann ein Merge-Verfahren benötigt, das nicht nur zwei, sondern vier sortierte Teilfelder verschmelzen kann. Das folgende Verfahren kann sogar 2s sortierte Teilfelder verschmelzen (s Zweierpotenz).

2s-way-merge

Prozedur 2s-way-merge(k, m, s)

Eingabe:

k × m-Feld (k > s, m > 1), bestehend aus 2s in Schlangenlinie sortierten Teilfeldern der Größe k/s × m/2 (Bild 1b)

Ausgabe:

das in Schlangenlinie sortierte k × m-Feld

Methode:

1. wenn m > 2 dann
1. oddexchange
2. unshuffle in den Zeilen
3. 2s-way-merge(k, m/2, s) rekursiv auf linke und rechte Hälfte anwenden
4. shuffle in den Zeilen
5. oddexchange
6. 2s oets-Schritte auf der Schlangenlinie
2. sonst
1. 2s-column-merge(k, s)

Die Rekursion bricht ab, wenn jeweils nur noch zwei Spalten zu verschmelzen sind. Dann wird das folgende Verfahren 2s-column-merge verwendet.

Prozedur 2s-column-merge(k, s)

Eingabe:

k × 2-Feld, dessen linke und rechte Spalte jeweils aus sortierten Abschnitten der Länge k/s besteht

Ausgabe:

das in Schlangenlinie sortierte k × 2-Feld

Methode:

1. oddexchange
2. Sortieren der Spalten
3. 2s oets-Schritte auf der Schlangenlinie

Das Verfahren 2-way-merge ergibt sich als Spezialfall von 2s-way-merge mit s = 1.

Korrektheit von 2s-way-merge

1. Fall: m > 2

Schritt 1 bezieht sich eigentlich auf die ungeraden Zeilen der Teilfelder. Diese sind jedoch identisch mit den ungeraden Zeilen des Gesamtfeldes, da k/s ein Vielfaches von 2 ist. Analog zu Schritt 1 von 2-way-merge kommen maximal 2s "überzählige" Einsen in die ungeraden Spalten.

Nach Schritt 2 ist somit das Gewicht der rechten Hälfte um höchstens 2s größer als das der linken Hälfte.

In Schritt 3 wird 2s-way-merge rekursiv aufgerufen. Die Rekursion endet, wenn m = 2 ist, d.h. wenn das zu sortierende Feld nur noch aus zwei Spalten besteht. Dieses wird dann durch 2s-column-merge sortiert.

Das Ergebnis nach Schritt 5 ist eine Folge, die aus zwei ineinander ver­schränkten (geshuffelten) sortierten Folgen besteht, von denen die zweite ein um höchstens 2s höheres Gewicht als die erste hat.

In Schritt 6 wird die dadurch entstehende unsortierte Zone auf der Schlangen­linie mit 2s oets-Schritten bereinigt.

2. Fall: m = 2

Durch die Vertauschung in ungeraden Zeilen werden die Einsen annähernd gleichmäßig auf beide Spalten verteilt. In jedem der s Abschnitte kann auf einer Seite eine Eins mehr sein als auf der anderen Seite. Dann werden die Spalten sortiert. Eine Spalte kann maximal s Einsen mehr enthalten als die andere. Dadurch ergibt sich eine unsortierte Zone der Länge höchstens 2s auf der Schlangen­linie, der durch 2s oets-Schritte sortiert wird.

Analyse von 2s-way-merge

Mit T(k, m, s) sei die Anzahl der Operationen von 2s-way-merge(k, m, s) bezeichnet. T(k, 2, s) ist die Anzahl der Operationen von 2s-column-merge(k, s).

Die Schritte 1, 2 und 4, 5 benötigen zusammen genau m Operationen. Somit gilt für m > 2

T(k, m, s)  =  m + 2s + T(k, m/2, s)

Mit T(k, 2, s) = k + 2s + 1 ergibt sich

T(k, m, s)  =  k + 2m + log(m)·2s – 3

Sortieren mit 2s-way-merge

Ein durch rekursive Anwendung von 2s-way-merge realisiertes Sortier­verfahren für ein n × n-Feld hat somit z.B. mit s = 2 die Komplexität 2n + 4n + o(n)  =  6n + o(n).

Eine Ver­einfachung des entsprechenden Verfahrens ist in [LSSS 85] angegeben.

s²-way-merge

Ein noch effizienteres Sortier­verfahren ergibt sich, wenn das n × n-Feld in s² Blöcke unterteilt wird, die jeweils für sich sortiert und dann verschmolzen werden. Wird s = n^1/3 gewählt, so erreicht das Sortier­verfahren eine Komplexität von 3n + o(n).

Prozedur s²-way-merge(k, m, s)

Eingabe:

k × m-Feld (k > s, m ≥ s), bestehend aus s² in Schlangenlinie sortierten Teilfeldern der Größe k/s × m/s (Bild 1c)

Ausgabe:

das in Schlangenlinie sortierte k × m-Feld

Methode:

1. wenn m > s dann
1. oddexchange
2. unshuffle in den Zeilen
3. s²-way-merge(k, m/2, s) rekursiv auf linke und rechte Hälfte anwenden
4. shuffle in den Zeilen
5. oddexchange
6. s² oets-Schritte auf der Schlangenlinie
2. sonst
1. s²-column-merge(k, s)

Die Rekursion bricht ab, wenn jeweils nur noch s Spalten zu verschmelzen sind. Dann wird das folgende Verfahren s²-column-merge verwendet.

Prozedur s²-column-merge(k, s)

Eingabe:

k × s-Feld (k > s), bestehend aus s² sortierten Teilfeldern der Größe k/s × 1

Ausgabe:

das in Schlangenlinie sortierte k × s-Feld

Methode:

1. für r = 1 bis log(s)-1 wiederhole
1. 2-way-merge(k/s, 2^r) auf alle Teilfelder der Größe k/s × 2^r anwenden
2. 2s-way-merge(k, s, s)

Korrektheit von s²-way-merge

Der Beweis der Korrektheit von s²-way-merge lässt sich analog zum Beweis von 2s-way-merge führen.

Analyse von s²-column-merge

Die Analyse von s²-column-merge ergibt zunächst recht komplizierte Ausdrücke für die Anzahl der Operationen. Mit k = n und s = n^1/3 lassen sich diese jedoch wie angegeben abschätzen.

Analyse von s²-way-merge

Mit T(k, m, s) sei die Anzahl der Operationen von s²-way-merge(k, m, s) bezeichnet. T(k, s, s) ist die Anzahl der Operationen von s²-column-merge(k, s).

Die Schritte 1, 2 und 4, 5 benötigen zusammen genau m Operationen. Somit gilt für m > s

T(k, m, s)  =  m + s² + T(k, m/2, s)

Daraus ergibt sich

T(k, m, s) ≤ 2m + log(m)·s² + T(k, s, s)

Mit k = m = n und s = n^1/3 lässt sich die Komplexität von s²-way-merge abschätzen als

T ∈ 3n + O(n^2/3·log(n))

Sortieren mit s²-way-merge

Ein mit s²-way-merge realisiertes Sortier­verfahren für ein n × n-Feld hat somit ebenfalls eine Komplexität von 3n + O(n^2/3·log(n)), da sich die Blöcke der Seitenlänge n^2/3 in Zeit O(n^2/3) sortieren lassen (z.B. mit dem auf 2s-way-merge aufgebauten Sortier­verfahren).

Simulation

Die folgende Simulation zeigt den Ablauf des Algorithmus von Thompson-Kung mit einem 64 × 64-Feld von Nullen und Einsen. Zur besseren Anschaulich­keit werden einige Operationen sequentiell angezeigt, auch wenn sie auf einem zwei­dimensionalen Prozessor­feld parallel ablaufen könnten.

(Java-Applet zur Simulation des Algorithmus von Thompson-Kung)

Literatur

[Bat 68]   K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314 (1968)

[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)

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