6th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS '97)
The Universality of a Class of (2 log2N-1)-stage Interconnection Networks
Tunis, TUNISIA
October 29-October 31
ISBN: 0-8186-8153-5
The performance of a highly-parallel multiprocessor system depends heavily on the efficiency of its interconnection network. In this paper we will focus on an N x N, (2logN-1)-stage interconnection networks. A concatenated (2logN-1)-stage interconnection network is a combination of two, cube-type networks with the rightmost stage of a right subnetwork and the leftmost stage of a left subnetwork overlapped. Despite of the better performance, (2logN-1)-stage networks have not been studied enough to explore all the important topological properties. We study the topological structure of concatenated (2logN-1)-stage networks and then state, formulate and prove a very important property, the Interstage Correlation. The Interstage Correlation is the relationship between output line bits of the left network SEs and input line bits of the right network SEs in a (2logN-1)-stage network. Interstage Correlation can be used as the criteria of classification for (2logN-1)-stage networks. Until now, research in this field was focused only on class of Benes-equivalent networks. This class is just a small subset of a set of all possible interconnection networks. In this paper, we make an attempt to formulate interstage correlation such that it can be used to classify many possible (2logN-1)-stage networks and discuss their topological equivalence.
Citation:
Yanggon Kim, Tse-yun Feng, "The Universality of a Class of (2 log2N-1)-stage Interconnection Networks," ftdcs, pp.92, 6th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS '97), 1997