Benutzer:Stormi83/Omega

Ein Omega Netzwerk ist ein Verbindungsnetzwerk, das zur Klasse der dynamischen Verbindungsnetzwerke gehört.

Merkmale

Ein Omega Netz ist ein mehrstufiges dynamisches Verbindungsnetzwerk, dass zu dem noch einen $logN$ Charakter besitzt, d.h. es hat $ldN$ Stufen mit jeweils N/2 Schaltzellen pro Stufe bei insgesamt N verbundenen Knoten. Die Schaltzellen in den einzelnen Stufen sind Betazellen, also 2x2 Crossbars. Eine wichtige Eigenschaft eines Omega Netzes ist die, dass zwischen den Stufen jeweils die selbe Permutation verdrahtet ist und zwar die Perfect Shuffle Permutation. Ein Omega Netz als $logn$ Netz ist nicht blockierungsfrei, d.h. es kann nicht alle $n!$ möglichen Permutationen schalten.

Self Routing

Bedingt durch oben genannte Merkmale ergibt sich für das Routing durch das Netzwerk ein einfacher Algorithmus. Nummeriert man die beteiligten Knoten binär, dann stellt jedes Bit des Zielknotens dar, welchen Ausgang der Betazelle der entsprechenden Stufe die Daten nehmen (0 - oberer Ausgang, 1 - unterer Ausgang). Zudem ergibt die XOR Verknüpfung von Quell und Zieladresse ein Ergebniswort, dass die Schalterstellung der Betazelle der entsprechenden Stufe codiert (0 - straight, 1 - crossed). Die einfache Erlangung der benötigten Routinginformationen nur aus Quell- und Zieladresse der beteiligten Knoten gibt dem Verfahren seinen Namen.

Beispiel

Omega Netz mit 8 verbundenen Knoten, d.h. $ld8=3$ Stufen mit jeweils 8/2 = 4 Schaltzellen

• Senderknoten: 2 (binär 010)
• Empfängerknoten: 4 (binär 100)

010 XOR 100 = 110

• Stufe 1: unteren Ausgang wählen (linkestes Bit im Zielwort ist 1), dazu Schalterstellung "crossed" (linkestes Bit des XOR Ergebniswortes 1)
• Stufe 2: oberen Ausgang wählen (Mittelbit im Zielwort ist 0), dazu Schalterstellung "crossed" (Mittelbit des XOR Ergebniswortes 1)
• Stufe 3: oberen Ausgang wählen (rechtestes Bit im Zielwort ist 0), dazu Schalterstellung "straight" (rechtestes Bit des XOR Ergebniswortes 0)

Blockierungserkennung

Bevor zwei unabhängige Verbindungen geschalten werden, ist es möglich zu erkennen, ob dies eine Blockierung in einer Stufe auslöst, d.h., ob die Verbindungen in einer Stufe die selbe Schaltzelle benutzen, sich dabei aber gegenseitig ausschließen, weil z.B. beide den selben Eingang/Ausgang benutzen.

Beispiel

ERKLÄRUNG MIT BILD UNBEDINGT NÖTIG