The universality of a class of (2log2N-1)-stage interconnection networks

The performance of a highly-parallel multiprocessor system depends heavily on the efficiency of its interconnection network. We focus on an N×N, (2log₂N-1)-stage interconnection network. A concatenated (2log₂N-1)-stage interconnection network (denoted by (Δ⊕Δ´)) is a combination of two, cube-type networks with the rightmost stage of Δ and the left most stage of Δ´ overlapped. Despite the better performance, (2log₂N-1)-stage networks have not been studied enough to explore all the important topological properties. We study the topological structure of (Δ⊕Δ´) and then state, formulate and prove a very important property, the interstage correlation. Interstage correlation is the relationship between output line bits of the left network SEs and input line bits of the right network SEs in (Δ⊕Δ´). Interstage correlation can be used as the criteria of classification for (2log₂N-1)-stage networks. Until now, research in this field was focused only on the class of Benes-equivalent networks. This class is just a small subset of a set of all possible interconnection networks. We formulate interstage correlation such that it can be used to classify many possible (2log₂N-1)-stage networks and discuss their topological equivalence