8.5 Sortieren im Shuffle-Exchange

Um 2^k Zahlen im Hypercube zu sortieren, führt die Prozedur HC_bitonic_sort aus dem vorigen Abschnitt k · (k + 1)/2 Compare-Exchange-Schritte durch. Diese sind strukturiert in k Gruppen, wobei in Gruppe i die Kanten der Dimension i,i - 1,...,0 benutzt werden. Z.B. ergibt sich für k = 6 die folgende Sequenz von benutzten Dimensionen:

0 10 210 3210 43210 543210

Um eine Gruppe von k Compare-Exchange-Operationen im Hypercube längs der Dimensionen k - 1,k - 2,...,0 im Shuffle-Exchange-Netzwerk zu simulieren, werden jeweils über Shuffle-Kanten die Operanden aus Prozessor 0w und 1w in die Prozessoren w0 bzw. w1 geschickt und dort mittels der Exchange-Kante der Compare-Exchange-Schritt ausgeführt. Also werden k Schritte im Hypercube durch 2 · k Schritte im Shuffle-Exchange-Netzwerk simuliert. Für die Simulation der Gruppen, die nicht mit der höchsten Dimension beginnen, wird zunächst unter Verwendung der Shuffle-Kanten die erforderliche Ausgangsposition hergestellt.

Also läßt sich die Idee des Bitonischen Sortierens im Shuffle-Exchange-Netzwerk wie folgt formulieren (Minimum-Maximum-Problematik ignoriert):

PROCEDURE SE_bitonic_sort(my_id,k)
BEGIN
   FOR i := 0 TO k-1 DO
      FOR j := k-1 DOWNTO i+1 DO
         Schicke Daten ueber Shuffle-Kante;
      END;
      FOR j := i DOWNTO 0 DO
         Schicke Daten ueber Shuffle-Kante;
         Compare-Exchange ueber Exchange-Kante
      END
   END
END

Also können n Zahlen auf einem Shuffle-Exchange-Netzwerk mit n Knoten in O($\log^{2}_{}$n) Zeit sortiert werden. Die Kosten betragen O(n · $\log^{2}_{}$n) , also liegt kein kostenoptimaler Algorithmus vor.