3.2.10 Shuffle Exchange

Ein Shuffle Exchange-Netzwerk der Dimension k ( SE(k) ) besteht aus p = 2^k Knoten. Es gibt zwei Arten von Kanten:

exchange: zwischen Prozessoren, deren Adressen bis auf das low-order-Bit übereinstimmen,

shuffle: von i nach (2 · i)mod (p - 1) für i = 0,...,p - 2 und von p - 1 nach p - 1 .

Eine Shuffle-Kante bewirkt eine zyklische Linksrotation der Binärdarstellung.

Shuffle-Exchange-Netzwerk der Dimension 3

K₁ : ja

K₂ : 3 (wenn Richtung ignoriert wird)

K₃ : Um von x nach y zu gelangen: Passe schrittweise die Bits von x den Bits von y an. Konstruiere jeweils im letzten Bit (durch Übernahme des vordersten (shuffle) oder durch Übernahme des vordersten mit Invertierung (shuffle + exchange)) das nächste Bit der Zieladresse.

K₄ : 2k - 1

K₅ : nein