LAUSR

This paper introduces a new nonblocking self-routing network, called a multi-root binary tree, which may be used to interconnect the cores in multicore chips. The multi-root binary tree network differs from other binary tree-based networks in that the cores are placed at the roots rather than the leaves or the interior nodes of the trees. The self-routing property of a multi-root binary tree is built on the concept of replication and clustering. A new replication and clustering method, called the triangular shift pairing is given to connect the cores together over dedicated paths. It is shown that connecting cores in clusters requires at least $n/2$ columns of pairings for an $n$ -core network in a grid layout model and triangular shift wiring method matches this lower bound. The replication and clustering concept leads to a simple self-routing scheme that pairs cores by decoding both unicast and multicast connection requests using $\mathrm{lg} \;n$ -bit cluster address bits. In particular, it is established that cores can identify the cluster with which they pair with other cores using simple modulo addition of their own ids and addresses of the targeted cores in $2\mathrm{lg}\; n$ single bit-decoding steps. It is also shown that, if connection requests are uniformly distributed among the cores then blocking due to target conflicts can be avoided if cores serve connection requests at a small multiple of the frequencies with which they receive them.