A self-routing multi-logN permutation network is presented and studied. This network has 3log/sub 2/ N-2 depth and N(log/sub 2//sup /spl gamma//N)(3log/sub 2/, N-2)/2 nodes, where N is the number of network inputs and /spl gamma/ a constant very close to 1. A parallel routing algorithm runs in 3log/sub 2/N-2 time on this network. The overall system (network and algorithm) can work in pipeline and it is asymptotically nonblocking in the sense that its blocking probability vanishes when N increases, hence the quasi-totality of the information synchronously arrives in 3log/sub 2/N-2 steps at the network outputs. This network presents very good fault tolerance, a modular architecture, and it is suitable for information exchange in very large scale parallel processors and communication systems.>

A self-routing multi-log-N permutation network is presented and studied. This network has log/sub 2/N depth and N(log/sub 2//sup 2/N+log/sub 2/N)/2 nodes, where N is the number of network inputs. Its parallel routing algorithm runs in log/sub 2/N time. The network architecture guarantees that only a negligible quantity of information is blocked, while the quasi-totality of the information synchronously reaches the network outputs in log/sub 2/N steps. This network works in pipeline, it has a modular architecture suitable for very large N, it can be used as very high performance fast packet switching fabric, and it is suitable for information exchange in very-large-scale multiprocessor systems.>