GSE: a full-access multistage interconnection network of arbitrary size
Rajib Das, Nabanita Das · International Journal of Systems Science · 1997
Existing multistage interconnection networks (MINs) which are based on 2×2 switching elements are generally of size N × N where N is a power of 2. So in situations where we need to connect N processors and N resources and N is an arbitrary number ( not necessarily a power of 2) we have to go for a network of size N' x N'; where N' = 2[log2N]is This causes a wastage of resources. In order to overcome this problem we propose a new MIN called the Generalized Shuffle Exchange (GSE) of size N x N 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, i.e. every input can reach every output of the network. Routeing between any input-output pair in GSE is simple and can be done by using a routeing vector, generated from the input and output addresses. When N is a power of 2, say 2n, GSE reduces to a conventional n-stage network with a unique path for each input-output pair. But, if 2n-1 < N <2n, given a specific input, there are 2[logN] mdash; N outputs for which there exist alternative paths. Therefore, to realize any N × N permutation in GSE, we are to select a set of N conflict free paths, one for each input-output connection. Here, we have presented a scheme for determining whether a given permutation is realizable in the GSE in a single pass.