Li, Peggy Pey-yun (1985) The Sneptree - A Versatile Interconnection Network. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1985.5194-tr-85
See Usage Policy.
Other (Adobe PDF (2MB))
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1985.5194-tr-85
A new interconnection network, the Sneptree, is investigated. The Sneptree consists of 2 to the power of N–1 identical nodes and each node has four links. The links are connected to form an augmented complete binary tree where the outgoing links of the leaves are feedback to all the nodes in the network. We prove that a complete binary tree with arbitrary size can be mapped onto a Sneptree optimally. Hence, the Sneptree is particularly well suited for distributed computations with tree- structured computation graph, such as divide-and-conquer and backtracking. One type of Sneptree, which contains two disjoint spanning cycles and is thus called Cyclic Sneptree, is of particular interest since it can simulate a fully unbalanced tree optimally, such as a left/right skewed tree. A recursive method is given to generate the H-structure layout of the Cyclic Sneptree. The number of crossings and the length of the longest wires in the H-structure layout are analyzed. A message routing algorithm between any two leaf nodes is presented. The routing algorithm, which is of O(n) complexity, gives a good approximation to the shortest path. The traffic congestion in the nodes at the upper levels is also significantly reduced compared to the binary tree case.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Computer Science Technical Reports|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechCSTR|
|Deposited On:||25 Jul 2002|
|Last Modified:||26 Dec 2012 14:10|
Repository Staff Only: item control page