Hypercube-Netzwerktopologie - Hypercube internetwork topology

In Computernetzwerken sind Hypercube- Netzwerke eine Art von Netzwerktopologie, die verwendet wird, um mehrere Prozessoren mit Speichermodulen zu verbinden und Daten genau zu routen . Hypercube-Netzwerke bestehen aus 2 ^m Knoten , die die Eckpunkte von Quadraten bilden, um eine Internetwork- Verbindung herzustellen. Ein Hypercube ist im Grunde ein mehrdimensionales Mesh-Netzwerk mit zwei Knoten in jeder Dimension. Aufgrund der Ähnlichkeit werden solche Topologien normalerweise in eine k- äre d- dimensionale Netztopologiefamilie gruppiert , wobei d die Anzahl der Dimensionen darstellt und k die Anzahl der Knoten in jeder Dimension darstellt.

Unterschiedliche Hyperwürfel für unterschiedliche Anzahl von Knoten

Topologie

Das Hypercube-Verbindungsnetzwerk wird durch die Verbindung von N Knoten gebildet, die als Zweierpotenz ausgedrückt werden können. Das heißt, wenn das Netzwerk n Knoten hat, kann es ausgedrückt werden als:

${\displaystyle N=2^{m}}$

wobei m die Anzahl der Bits ist, die erforderlich sind, um die Knoten im Netzwerk zu kennzeichnen. Wenn es also 4 Knoten im Netzwerk gibt, werden 2 Bits benötigt, um alle Knoten im Netzwerk darzustellen . Das Netzwerk wird aufgebaut, indem die Knoten verbunden werden, die sich in ihrer binären Darstellung nur um ein Bit unterscheiden . Dies wird allgemein als binäres Etikettieren bezeichnet. Ein 3D Hypercube Interwork wäre ein Würfel mit 8 Knoten und 12 Kanten . Ein 4D-Hypercube-Netzwerk kann erstellt werden, indem zwei 3D- Netzwerke dupliziert und ein höchstwertiges Bit hinzugefügt werden. Das neu hinzugefügte Bit sollte '0' für einen 3D-Hyperwürfel und '1' für den anderen 3D-Hyperwürfel sein. Die Ecken der jeweiligen um ein Bit geänderten MSBs werden verbunden, um das höhere Hyperwürfel-Netzwerk zu bilden. Dieses Verfahren kann verwendet werden, um jeden m-Bit-dargestellten Hyperwürfel mit (m-1)-Bit-dargestellten Hyperwürfel zu konstruieren.

E-Cube-Routing

Die Routingmethode für ein Hypercube-Netzwerk wird als E-Cube-Routing bezeichnet. Der Abstand zwischen zwei Knoten im Netzwerk kann durch Hamming-Gewicht (Anzahl von Einsen in) der XOR- Operation zwischen ihren jeweiligen Binärbezeichnungen angegeben werden.

Der Abstand zwischen Knoten 1 (dargestellt als '01') und Knoten 2 (dargestellt als '10') im Netzwerk, gegeben durch:

${\displaystyle {\mathsf {Hamming\_weight}}(01\oplus 10)={\mathsf {Hamming\_weight}}(11)=2}$

E-Cube-Routing ist eine statische Routing- Methode, die den XY-Routing- Algorithmus verwendet . Dies wird allgemein als deterministische , Dimension bestellt Routing - Modell. Das E-Cube-Routing funktioniert, indem es das Netzwerk in der k- ^ten Dimension durchquert, wobei k das niedrigstwertige Bit ungleich Null im Ergebnis der Entfernungsberechnung ist.

Angenommen, das Label des Senders sei '00' und das Label des Empfängers '11'. Der Abstand zwischen ihnen beträgt also 11 und das niedrigstwertige Nicht-Null-Bit ist das LSB- Bit. Den Weg für eine '0' oder '1' zu finden, wird durch den XY-Routing-Algorithmus bestimmt.

Metriken

Es werden verschiedene Leistungsmaße verwendet, um die Effizienz einer Hypercube-Netzwerkverbindung im Vergleich zu verschiedenen anderen Netzwerktopologien zu bewerten.

Grad

Dies definiert die Anzahl der unmittelbar benachbarten Knoten zu einem bestimmten Knoten. Diese Knoten sollten unmittelbare Nachbarn sein. Bei einem Hyperwürfel ist der Grad m.

Durchmesser

Dies definiert die maximale Anzahl von Knoten, die eine Nachricht auf ihrem Weg von der Quelle zum Ziel passieren muss. Dies gibt uns im Grunde die Verzögerung bei der Übertragung einer Nachricht über ein Netzwerk. Bei einem Hyperwürfel beträgt der Durchmesser m.

Durchschnittliche Entfernung

Der Abstand zwischen zwei Knoten, definiert durch die Anzahl der Hops auf dem kürzesten Pfad zwischen zwei bestimmten Knoten. Es ist durch die Formel gegeben -

${\displaystyle d_{a}=\sum_{d=1}^{r}{(d.N_{d}) \over N-1}}$

Bei Hypercubes wird die durchschnittliche Distanz mit m/2 angegeben.

Halbierungsbreite

Dies ist die niedrigste Anzahl von Drähten, die Sie schneiden sollten, um das Netzwerk in zwei gleiche Hälften zu teilen. Es wird mit 2 ^m-1 für Hypercubes angegeben.

Verweise