GSE: a generalized full-access multistage interconnection network with minimum cost
Rajib Das, Nabanita Das · 1996
We propose a new multistage interconnection network (MIN) called Generalized Shuffle Exchange (GSE) to connect N processors and N resources where N need not be a power of 2, but only an even number. It uses N/2 switches per stage and the number of stages is equal to [log N]. We show that GSE is a full-access network. Routing between any input-output pair in GSE is simple and can be done by using a routing vector, generated from the input and output addresses. When N is a power of 2, say 2n, GSE reduces to conventional n-stage network with unique path for each input-output pair. But, if 2n-1ngiven a specific input, there are 2[logN]-N outputs for which there exist alternative paths. Therefore, to realize any N×N permutation we are to select a set of N conflict free paths, one for each input-output connection. Now, the problem of determining whether any given permutation is realizable in a single pass by a MIN is known as the permutation admissibility problem. Here, we have presented a scheme for resolving the permutation admissibility problem in a GSE.