A self-routing multi-logN permutation network is presented and studied. This network has 3log N-2 depth and N(log/sub 2//sup /spl gamma//N)(3log 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 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.
An 0(log2 N) Depth Asymptotically Nonblocking Self-Routing Permutation Network / De Biase, G. A.; Ferrone, Claudia; Massini, A.. - In: IEEE TRANSACTIONS ON COMPUTERS. - ISSN 0018-9340. - STAMPA. - 44:8(1995), pp. 1047-1051. [10.1109/12.403721]
An 0(log2 N) Depth Asymptotically Nonblocking Self-Routing Permutation Network
De Biase, G. A.;FERRONE, CLAUDIA;Massini, A.
1995
Abstract
A self-routing multi-logN permutation network is presented and studied. This network has 3log N-2 depth and N(log/sub 2//sup /spl gamma//N)(3log 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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
