ON SYNTHESIZING CUBE AND TREE FOR PARALLEL-PROCESSING

In this paper we propose a VLSI implementable architecture called Cube Connected Tree having advantageous properties of both tree and hyperc ube. This structure has a fixed low degree of nodes for any size of th e network unlike the hypercube where the node degree is dependent on t he size of the hypercube. The degree-diameter product metric [26] of C CT is low compared to that of a hypercube of comparable size. It overc omes the data congestion problem near the root of the binary tree by h aving multiple roots in the structure, thereby enhancing the I/O bandw idth of the system. The complexity of the VLSI layout of this structur e has been addressed within the grid model of Thompson [12]. By using spare links and PEs, fault tolerance capabilities of the system have b een enhanced. Easy programmability of this structure has been demonstr ated by designing polylogarithmic algorithms for sorting and discrete Fourier transform.