Nonblocking On-Chip Interconnection Networks

Interconnection networks enable fast data communication between components of a digital system. The selection of an appropriate interconnection network and its architecture plays an important role in the development process of the system. The selection of a bad network architecture may significantly delay the communication between components and decrease the overall system performance. There are various interconnection networks available. Most of them are blocking networks. Blocking means that even though a pair of source and target components may be free, a connection between them might still not be possible due to limited capabilities of the network. Moreover, routing algorithms of blocking networks have to avoid deadlocks and livelocks, which typically does only allow poor real-time guarantees for delivering a message. Nonblocking networks can always manage all requests that are coming from their input components and can therefore deliver all messages in guaranteed time, i.e, with strong real-time guarantees. However, only a few networks are nonblocking and easy to implement. The simplest one is the crossbar network which is a comparably simple circuit with also a simple routing algorithm. However, while its circuit depth of O(log(n)) is optimal, its size increases with O(n^2) and quickly becomes infeasible for large networks. Therefore, the construction of nonblocking networks with a quasipolynomial size O(nlog(n)^a) and polylogarithmic depth O(log(n)^b) turned out as a research problem. Benes [Clos53; Bene65] networks were the first non blocking networks having an optimal size of O(nlog(n)) and an optimal depth of O(log(n)), but their routing algorithms are quite complicated and require circuits of depth O(log(n)^2) [NaSa82]. Other nonblocking interconnection networks are derived from sorting networks. Essentially, there are merge-based (MBS) and radix-based (RBS) sorting networks. MBS and RBS networks can be both implemented in a pipelined fashion which leads to a big advantage for their circuit implementation. While these networks are nonblocking and can implement all n! permutations, they cannot directly handle partial permutations that frequently occur in practice since not every input component communicates at every point of time with an output component. For merge-based sorting networks, there is a well known general solution called the Batcher-Banyan network. However, for the larger class of radix-based sorting networks this does not work, and there is only one solution known for a particular permutation network. In this thesis, new nonblocking radix-based interconnection networks are presented. In particular, for a certain permutation network, three routing algorithms are developed and their circuit implementations are evaluated concerning their size, depth, and power consumption. A special extension of these networks allows them to route also partial permutations. Moreover, three general constructions to convert any binary sorter into a ternary split module were presented which is the key to construct a radix-based interconnection network that can cope with partial permutations. The thesis compares also chip designs of these networks with other radix-based sorting networks as well as with the Batcher-Banyan networks as competitors. As a result, it turns out that the proposed radix-based networks are superior and could form the basis of larger manycore architectures