The Sneptree - A Versatile Interconnection Network

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.