A permutation network for interprocessor communication in parallel computers

The design and hardware implementation of a permutation network architecture are examined. This is done by first defining a network and a setup procedure for it, and then coding the setup procedure into hardware at the register transfer level. The chip implementation of this network is also examined and found to be very feasible in a VLSI design environment. Furthermore, the modularity feature of the design approach makes it easy to build larger-size networks by using 16-input networks as building blocks. For example, by using three 16-input permutation networks it is possible to build a 32-input permutation network, by using three 32-b permutation networks it is possible to build a 64-input permutation network, and so on. Thus, a permutation network with a large number of inputs can easily be constructed using 16-input permutation networks, each of which can be housed in a VLSI chip. For example, a 1024-input permutation network can be built by using 729 16-input permutation networks