GSE - A FULL-ACCESS MULTISTAGE INTERCONNECTION NETWORK OF ARBITRARY SIZE

Existing multistage interconnection networks (MINs) which are based on 2 x 2 switching elements are generally of size N x N where N is a pow er 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([log2 N]). Th is causes a wastage of resources In order to overcome this problem we propose a new MIN called the Generalized Shuffle Exchange (GSE) of siz e 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 re ach every output of the network. Routeing between any input-output pai r in GSE is simple and can be done by using a routeing vector, generat ed from the input and output addresses. When N is a power of 2, say 2( n), GSE reduces to a conventional n-stage network with a unique path f or each input-output pair. But, if 2(n-1) < N < 2(n), given a specific input, there are 2([log N]) - N outputs for which there exist alterna tive paths. Therefore, to realize any N x N permutation in GSE, we are to select a set of N conflict free paths, one for each input-output c onnection. Here, we have presented a scheme for determining whether a given permutation is realizable in the GSE in a single pass.