Li, Peggy Peyyun (1985) The Sneptree  A Versatile Interconnection Network. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1985.5194tr85

Postscript
See Usage Policy. 2181Kb  

Other (Adobe PDF (2MB))
See Usage Policy. 1898Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1985.5194tr85
Abstract
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 divideandconquer 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 Hstructure layout of the Cyclic Sneptree. The number of crossings and the length of the longest wires in the Hstructure 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 
Record Number:  CaltechCSTR:1985.5194tr85 
Persistent URL:  http://resolver.caltech.edu/CaltechCSTR:1985.5194tr85 
Usage Policy:  You are granted permission for individual, educational, research and noncommercial reproduction, distribution, display and performance of this work in any format. 
ID Code:  26953 
Collection:  CaltechCSTR 
Deposited By:  Imported from CaltechCSTR 
Deposited On:  25 Jul 2002 
Last Modified:  26 Dec 2012 14:10 
Repository Staff Only: item control page