CaltechAUTHORS
  A Caltech Library Service

The Sneptree - A Versatile Interconnection Network

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

[img]
Preview
Postscript
See Usage Policy.

2181Kb
[img]
Preview
Other (Adobe PDF (2MB))
See Usage Policy.

1898Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1985.5194-tr-85

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 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
Record Number:CaltechCSTR:1985.5194-tr-85
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1985.5194-tr-85
Usage Policy:You are granted permission for individual, educational, research and non-commercial 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