2.2.5 Der Tree

Der Tree (oder Baum) in Abb. 2.5 ist eine sehr flexible Topologie, mit guten Kommunikationseigenschaften.

Optimaler Baum :  
Baum dessen maximale Tiefe und Verästelung (d.h. Verzweigungen pro Knoten) nicht größer als  $d = \log_{2} P$ ist.

Wir verwenden im weiteren die Bezeichnung Baum stets im Sinne eines optimalen Baumes.
Somit gilt für Bäume stets

• $2^{d-1} \,<\, P \,\le\, 2^d$
• Max. $d$ Links pro Knoten
• Max. Weglänge: $2d - 1 \,=\, 2 \log_2 P -1$

Konstruktionsprinzip

Gray-Code :  
Die Binärdarstellungen der Nummern benachbarter Knoten unterscheiden sich in genau einem Bit ( $[0,\ldots,d]$) !


Bemerkung : Von einem beliebigen Knoten im Baum mit der Wurzel in $000$ werden so viele Äste gebildet, wie $0$-Bits dem letzten $L$-Bit der Binärdarstellung der Knotennummer folgen.

  

Abbildung 2.5: Optimaler Baum in Binärdarstellung

Hardware: Convex-MPP mit dem Konzept der ''Fat Trees'', d.h. je näher ein Link an der Wurzel des Baumes, desto leistungsfähiger ist die Datenleitung ausgelegt.