2.2.7 Das DeBrujin-Netzwerk

Die bisher betrachteten Topologien besitzen die in Tabelle 2.8 aufgeführten Eigenschaften. Während bei Ring/Torus die Anzahl der Links mit der Raumdimension beschränkt ist (was aber mit einer großen max. Weglänge erkauft werden muß), steigen die pro Knoten benötigten Links bei Tree/Hypercube mit der Anzahl der benötigten Knoten an (was für größere Knotenanzahlen in technologischen Problemen resultiert). Wünschenswert wäre eine Topologie, welche eine max. Weglänge der Ordnung ${\mathcal{O}}(\log_2(P))$ bei kleiner, konstanter Anzahl der Links pro Knoten besitzt. Das DeBrujin-Netzwerk ist genau ein solches.

  

Abbildung 2.8: Eigenschaften Topologien

Zunächst einige Begriffe:

• Left Shuffle [LS] $=$ ISHFTC($b , 1 , d$) (im weiteren Link 1)
  
  
  
  
• Right Shuffle [RS] $=$ ISHFTC( $b , -1 , d$) (im weiteren Link 2)
  
  
  
  
• Left Shuffle Exchange [LSE] $=$ IOR(ISHFTC($b , 1 , d$),$2^{d-1}$) (Link 3)
  
  
  
  
• Right Shuffle Exchange [RSE] $=$ IOR(ISHFTC( $b , -1 , d$),$2^{d-1}$) (Link 4)
  
  
  
  
• Netzwerk der Dimension $d$ besitzt $2^d$ Knoten und $2^{d+1}-2$ (gerichtete) Kanten.
• Jeder Knoten (außer Knoten $0$ und $2^{d-1}$) besitzt genau 4 Links. Die Knoten $0$ und $2^{d-1}$ benötigen nur 2 Links.
• Nur gerade Knoten im Graphen
  $\Longrightarrow$ Graph ohne Überschneidung durchlaufbar.
  $\Longrightarrow$ Ring ist eingebettet.
• Die max. Weglänge ist $d$.

 

Abbildung 2.9: DeBrujin Netzwerk $d=3$ : 8 Knoten, 14 Kanten

Es ist keine kommerzielle Hardwarerealisierung des DeBrujin Netzwerks bekannt.


Aufgabe :

Für welche Knotennummern $i=0,\ldots,2^{d}-1$ im de Brujin-Netzwerk gilt

Hinweis: Unterscheiden Sie, ob $d$ gerade bzw. ungerade ist.  




Aufgabe :

Stellen Sie ein de Brujin-Netzwerk für $d=4$ auf !  




Aufgabe :

Beweisen Sie, daß im de Brujin-Netzwerk die maximale Weglänge zwischen zwei beliebigen Knoten $p,q$ gleich der Dimension $d$ ist !