Characterizing Bit Permutation NetworksGerard J. Chang, Frank K. Hwang, Li-Da TongDepartment of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, TaiwanReceived August 1997; accepted October 1997Abstract: In recent years, many multistage interconnection networks using 2 1 2 switching elementshave been proposed for parallel architectures. Typical examples are baseline networks, banyan networks,shuffle-exchange networks, and their inverses. As these networks are blocking, such networks with extrastages have also been studied extensively. These include Benes networks andD!D* networks. Re-cently, Hwang et al. studied k-extra-stage networks, which are a generalization of the above networks.They also investigated the equivalence issue among some of these networks. In this paper, we studieda more general class of networks, which we call (m / 1 )-stage d -nary bit permutation networks. Wecharacterize the equivalence of such networks by sequence of positive integers.q 1999 John Wiley &Sons, Inc. Networks 33: 261–267, 1999Keywords: multistage interconnection network; switching network; permutation routing; Sterling num-ber; rearrangeably nonblocking1. INTRODUCTIONFor a detailed description and notation of bit permutationnetworks, see Section 2.Note that (n/1)-stage binary bit permutation net-Consider a multistage interconnection networkVwith Nworks include all self-routing networks like Omega, ban-Ådn/ 1inputs and outputs and which has m/1 stagesyan, baseline, and their inverse networks. Binary bit per-of N/d crossbars of size d1d. Let the jth crossbar in amutation networks have been widely studied in the litera-stage be labeled by j in the d-nary number (with n bits).ture [1, 3, 6, 8, 11] for their topological equivalence.A bit-i group consists of those crossbars whose labels areBermond et al. [3] characterized the Omega-equivalentidentical except the ith bit. Such a group will be labeledclass by the P(i, j) property. An (n/1)-stage networkby a d-nary number x with n bits which is identical tosatisfies the P(i, j) property if the subnetwork from stageany member in the group except that bit i is replaced byi to stage j has exactly 2n0j/icomponents. Then, an (nthe symbol x0, which stands for the set {0, 1, ...,d01}./1)-stage network with the unique path property is inVwill be called a (m/1)-stage d-nary bit permutationthe Omega-equivalent class if and only if it satisfies thenetwork if the linking between stage k to stage k/1isP(i, j) property for all 0°i°j°n.always from a bit-ikgroup G to a bit- jkgroup G*, whereAnother special class of bit permutation networks con-G*is a permutation of G, for kÅ0, 1, ..., m01.sists of (n/1)-stage networks with extra stages. A k-extra-stage network is a cascade of a (n/1)-stage net-work with k extra stages also satisfying the bit permuta-Correspondence to: G. J. Changtion linking pattern. Lea and Shyy [7, 9] proposed addingContract grant sponsor: National Science Council; contract grantnumber: NSC86-2115-M0009-002extra stages to a binary inverse banyan network while theq 1999 John Wiley & Sons, Inc. CCC 0028-3045/99/040261-072618u26 846/ 8U26$$0846 05-07-99 09:03:29 netwa W: Networks262CHANG, HWANG, AND TONGelement, and Figure 2 shows a baseline network with NÅ16, in which a terminal i is represented by its binarynumber representation (x3, x2, x1, x0) and is adjacent toa switching element named by (x3, x2, x1).One can view the baseline network in Figure 2 as agraph whose vertices are those 32 switching elementsFig. 1. A21 2 switching element.named by (x3, x2, x1)i, where 0°i°3 and x1, x2, x3√{0, 1}, and there are linksk extra stages are added by pattern F01(see below).from (x3, x2, x1)0to (x0, x3, x2)1,Hwang et al. [5] generalized the study of equivalence byfrom (x3, x2, x1)1to (x3, x0, x2)2, andadding extra stages to a binary Omega-equivalent networkfrom (x3, x2, x1)2to (x3, x2, x0)3,with the following patterns for extra stages:where x0√{0, 1}, meaning there are two links, one with(i) F: They are identical to the first k stages of thex0Å0 and the other with x0Å1. A link from a switchingnetwork;element x at stage i to a switching element y at stage i(ii) F01: Identical to the mirror image of the first k/1 exists if the bits of y can be obtained from the bitsstages;of x by a permutation depending only on i. For instance,we can represent the links from stage 0 to stage 1 by a(iii) L: Identical to the last k stages;permutation f1on {0, 1, 2, 3} with(iv) L01: Identical to the mirror image of the last kstages.f1(0)Å1, f1(1)Å2, f1(2)Å3, f1(3)Å0.In this paper, we determined the equivalence classesIn this way, the links from stage 0 to stage 1 are thoseamong all (m/1)-stage d-nary bit permutation net-from (x3, x2, x1)0to (xf1(3), xf1(2), xf1(1))1. We can alsoworks. We characterize such a network by an m-sequencesay that for a link from xÅ(x3, x2, x1)0to yÅ(x0, x3,over {1, 2, ...,n}, namely, every (m/1)-stage d-naryx1)1a coordinate xjat the jth position of x moves to thebit permutation network is reduced to an m-sequence overf011( j)th position of y, where the coordinate x0’s moving{1, 2,..., n} and equivalence is determined by somefrom ‘‘outside’’ into y means there are two such links.easily computable sequence statistics. Note that the se-Similarly, the following permutations f2and f3representquence is independent of d. For mÅn, this characteriza-links from stage 1 to stage 2 and stage 2 to stage 3,tion, of course, corresponds to the P(i, j) characterization.respectively:But the sequence-graph correspondence is not in an obvi-ous way. With the power and convenience of the sequencef2(0)Å1, f2(1)Å2, f2(2)Å0, f2(3)Å3;characterization, we easily give an explicit solution of thesize of the s-stage bit permutation class. Recently, Hu etf3(0)Å1, f3(1)Å0, f3(2)Å2, f3(3)Å3.al. [4] gave an O(N4log N)-time algorithm to check theequivalence of combined (2n01)-stage networks, whichThroughout this paper, we shall use the cycle notation forare obtained by cascading two Omega-equivalent net-works. We give an (mn)-time algorithm for checkingthe equivalence of two (m/1)-stage bit permutationnetworks. In particular, the running time is O(log2N)when the network has 2n01 stages.2. NETWORKSWe start the discussion of bit permutation networks byexamining the following classical example: A typicalOmega-equivalent network consists of N input terminals,N output terminals, and log2N columns (stages) of 212 switching elements in