3.1.4 Omega-Netzwerk

Eine weitverbreitete Multistage-Verbindungsstruktur ist das Omega-Netzwerk. Zwischen den p = 2^k Prozessoren und den p Speicherbänken befinden sich log p Stufen mit jeweils p/2 Schaltelementen. Daher wachsen die Kosten mit O(p · log p) .
Jede Stufe verbindet ihren i -ten Input mit ihrem j -ten Output nach der Formel

Diese Verbindung heißt Perfect Shuffle und bedeutet eine Linksrotation auf dem Binärmuster von i . Ihr Name rührt von der Beobachtung, daß alle n Zahlen wie beim Kartenmischen verschränkt werden.

Perfect Shuffle zwischen 8 Inputs und 8 Outputs

Die Outputs einer Stufe werden paarweise in Schaltelemente geführt, welche ihre Eingänge entweder durchrouten oder vertauschen.

Zustände eines Schaltelements: (a) Pass-Through (b) Cross-Over

Ein Weg vom Startpattern s zum Zielpattern t entsteht durch systematisches Zusammensetzen der Zieladresse, wobei durch eine Shuffle-Kante das bereits erreichte Bitmuster zyklisch um ein Bit nach links geshiftet wird und durch das darauffolgende Schaltelement das letzte Bit ggf. invertiert werden kann.

Vollständiges Omega-Netzwerk zwischen 8 Inputs und 8 Outputs

Omega-Netzwerke gehören zu den blockierenden Netzwerken, da zwei Kommunikationsströme ggf. über denselben Link laufen (siehe Bild 3.1).