A combined (2 log N-1)-stage interconnection network (denoted by /spl Delta//spl oplus//spl Delta/') is constructed by concatenating two Omega-equivalent networks (/spl Delta/ and /spl Delta/') with the rightmost stage of /spl Delta/ and the leftmost stage of /spl Delta/' overlapped. Benes network and the (2 log N-1)-stage shuffle-exchange network are two examples of such networks. Although these two networks have received intensive studies, the research on the topology of entire class of /spl Delta//spl oplus//spl Delta/' networks is very limited so far. In this paper, we study the topological structure of /spl Delta//spl oplus//spl Delta/' networks and propose an algorithm for determining topological equivalence between two given /spl Delta//spl oplus//spl Delta/' networks. We also present a simplified /spl Omega/-equivalence checking algorithm as a supporting result.

Mesh is one of the most commonly used interconnection networks and, therefore, embedding between different meshes becomes a basic embedding problem. Not only does an efficient embedding between meshes allow one mesh-connected computing system to efficiently simulate another, but it also provides a useful tool for solving other embedding problems. The authors study how to embed an s/sub 1//spl times/t/sub 1/ mesh into an s/sub 2//spl times/t/sub 2/ mesh, where s/sub i//spl les/t/sub i/ (i=1, 2), s/sub 1//spl les/t/sub 1/=s/sub 2/t/sub 2/, such that the minimum dilation and congestion can be achieved. First, they present a lower bound on the dilations and congestions of such embeddings for different cases. Then, they propose an embedding with dilation [s/sub 1//s/sub 2/]+2 and congestion [s/sub 1//s/sub 2/]+4 for the case s/sub 2//spl ges/s/sub 2/, both of which almost match the lower bound [s/sub 1//s/sub 2/]. Finally, for the case s/sub 1/

It is difficult to partition an arbitrary permutation into a minimum number of groups such that conflict-free paths for all source-destination pairs in each group can be established on an omega network. Based on linear algebra theory, this paper presents an optimal algorithm which solves this problem for the LC class of permutations on a large class of multi-stage networks. This algorithm extends the previous result which deals with the BPC class of permutations on the omega network.