Purdue UniversityPurdue e-PubsECE Technical Reports Electrical and Computer Engineering7-1-1992FRAMES: A SIMPLE CHARACTERIZATIONOF PERMUTATIONS REALIZED BYFREQUENTLY USED NETWORKSHASAN CAMPurdue University, School of Electrical EngineeringJOSE A.B. FORTESPurdue University, School of Electrical EngineeringFollow this and additional works at: http://docs.lib.purdue.edu/ecetrThis document has been made available through Purdue e-Pubs, a service of the Purdue University Libraries. Please contact epubs@purdue.edu foradditional information.CAM, HASAN and FORTES, JOSE A.B., "FRAMES: A SIMPLE CHARACTERIZATION OF PERMUTATIONS REALIZED BYFREQUENTLY USED NETWORKS" (1992). ECE Technical Reports. Paper 309.http://docs.lib.purdue.edu/ecetr/309HASAN CAM JOSE ' A.B. FORTES TR-EE 92-32 JULY 1992 FRAMES: A SIMPLE CHARACTERIZATION OF PERMUTATIONS REALIZED BY FREQUENTLY USED NETWORKS Hasan Cam and JosdA. B. Fortes School of Electrical Engineering Purdue University West Lafayette, IN 47907- 1285 ABSTRACT Rearrangeable multistage interconnection networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, non-rearrangeable networks can have inexpensive routing algorithms, but no simple technique exists to characterix all the permutations realized on these net- warks. This paper introduces the concept of frame and shows how iit can be used to characterize all the permutations realized on various multistage inteirconnection net- works. They include any subnetwork of the Benes network, the class of networks that are topologically equivalent to the baseline network, and cascaded baseline and shuffle-exchange networks. The question of how the addition of a stage to any of these networks affects the type of permutations realized by the network is precisely answered. Also, of interest from a theoretical standpoint, a new simple proof is pro- vided for the rearrangeability of the Benes network. Index Terms- Multistage interconnection network, permutations, rearrangeabil- ity, topological equivalence, balanced matrices, frames. - 'Ibis; research was supported in part by the Office of Naval Reaea~~h under contract No. 00014- 90-1-1483 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the Office of Naval Research under contract NO. 00014-88-k-0723. List td Symbols IN: irrteammction nehvorl. IP: imrterconnection pattern. IPh: intMconnection pamm fonned by input links. IP,: inte~cmnection pawn formed by w q ~ t links. SB: switching box; switch. BE: tawline network., see Definition II.3. RB: reverse basline network., see Definition II.3. SE: shuffie-exchange network; see Definition IL3. SE-' : inverse shuMIeexchange new&, see Definition 11.3. BS: ELenes n e t w e , see Qefinition 11.3. CS: C:los n e t w e see Definition 11.3. N: number of inputs/wq~ts of a networlr. n: logzN. Fck: the standard a-type frame with k columns; see Definition 111.2. FYzk: an a-type frame with A columns; see Definition III.3. F;,~: the universal frame with k columns; see Definition III.6. I: the identity permutation matrix; see Definition 11.1. R: the reverse permutation rnabix; see Definition II.1. r: the reverse permutation represented by R. AN*: matrix A with N rows and A columns. AN*(i): the ith rOW of A. r: a pennutation on the set (0.1, . . . , N-1); see Definition 111.2. B:amnappingoftheset (1,2,.. . ,k) into (1,2,. . . ,n);seeDefinitionIII.2. P: a luple of partitions; see Definition III.2. L INTRODUCTION Interconnection networks are utilized to provide communication among process- ing: elements and/or memory modules. Network performance significantly affects the ovt=rall cost and performance of a computational system because proce:ssors may spend a c:onsiderable amount of time in processor-processor and/or processor-memory com- mumication. Therefore, it is important to know exactly the interconnection patterns that can be implemented by a network. In particular, it is desirable to know what permuta- tioinr can be realized because parallel algorithms often require permutation-type data transfers. This paper presents a simple and easily understandable characterization of the permutations realized by any network with N=2" inputs that is topologically equivalent to one of the following netwoxks: first k stages, 1 S k S 19, of the reverse bareline network, the last n+k-1 stages of Benes network [7], or a casaade of baseline [ l I.] and k-stage shuffle-exchange [1,5] networks. The proposed characterizations are bard on the notion of "frm" (introduced in this paper), balanced matrices [2] and graph theory [3,41. The effectiveness of any interconnection network depends on factors such as the efficiency of the routing algorithm, the number and type of permuta~tions it realizes, mi the actual hardware implementation of the network. On one hmd, rearrangeable multistage interconnection networks such as Benes and &XI-' (the R!D-' is a cascade of (omega and inverse omega [I]) can realize any permutation. However, there are no known efficient routing algorithms to allow dynamic configuration in an environment whm the switching permutations change rapidly. On the other hand, some networks such as baseline and omega have efficient routing algorithms and srnall propagation delays, but cannot realize many permutations. In these cases, it is irr~portant o know which permutations aze realizable and this is possible by using the results of this paper. Different approaches have been proposed in the literature to circumvent inefficient routing algorithms. One approach is to determine certain types of permuta- t io~~s that occur more frequently than others in a parallel processing environment. Such permutations have been classified by Lenfant [23] into five families. III order to imple- ment these permutations on the Benes network with a small propagation &lay, Lenfant proposed a specialized routing algorithm for each family. A permutation that fails to be in one of these families still is routed using an inefficient routin.g algorithm. To increase the number of the families of permutations that can be realized by a network, Youssef and Arden [22] introduced an O(log2N) routing algorithm. which sets the (rxr) crossbar switches of the first stage of 3-stage Benes networks with N=r2 inputs to ;a fixed configuration and acts exactly like a self-routing algorithm in setting the reniaining switches. Another approach is to provide self-routing algorithms for realiz- ing some classes of permutations in various multistage interconnection networks such as 'Benes, 2n-stage shuffle-exchange. Nassimi and Sahni [24] psented simple self- routing algorithms to realize some important permutations in Bcnes networks. Ragllavendra and Boppana [25] proposed self-routing algorithms to realize the class of linear permutations on Benes and 2n-stage shuffle-exchange networks. Although a large number of multistage interconnection networks are extensively studjied, there is a relatively small number of basic designs for their underlying topolo- gies, Especially, Benes networks and six topologically equivalent networks, namely, omega, flip, indirect binary cube, modified data manipulator, baseline and reverse baseline have been investigated in depth and are frequently used in research studies and real systems. Characterizations of the topologies of these networks are given in [9,26,27]. However, to our knowledge, the characterization of the pelmutations per- formed by these and other networks is done for the first time in this paper. One excep- tion is the work of Lee [lo] which characterizes the permutations realized by the inverse omega network in terms of residue classes. The rest of the paper is organized as follows. Basic definitions ancl notations used throughout the paper are presented in Section 11. Also included in this section is a motivational example for the concept of frame. In Section 111, this concept, illustra- tions of many different frames, notation and terminology are introduced. Permutations realized by the k-stage reverse-baseline, 1 5 k 5 n, and the networks wh:ich are topolog- icalliy equivalent to it are characterized in Section IV. In Section V, the permutations realized by a cascade of reverse baseline and the k-stage shuffle-exchan,ge networks are identified. These cases show how frames can be used to characterize tlne permutations of some relatively complex networks with more than n stages. Section VI provides new proofs for the rearrangeability of the three-stage Clos and Benes networks. Permu- tations rdhed by the last n+k-1 stages of Benes network are identified in Section VTI,. This characterization illustrates how frames can be used to understand why a net- work is rearrangeable. Section VIII concludes the paper. The Appendix (Section IX) contains the proofs of most of theorems and lemmata in the paper. 11. ]BASIC DEFINITIONS AND A MOTIVATIONAL EXAMPLE Throughout this paper, matrices are denoted by single capital 1ettc:rs and columns of a1 matrix are represented by the lower case of the capital letter denoting that matrix. Matrix A having N rows and k columns is denoted by AN*. Given a matrix, e.g. AN&, the jth column is denoted by aj, 1 S j 5 k. To be able to refer to it set of specific colilmns of a matrix, the notation AxZy is used to denote the submatrix that contains tho:% columns of A whose indices are x, x+l, . . . ,y, where 1 5 x S y; if x happens to be ]water than y, then Ax:y refers to a nil matrix, unless stated otherwise. If x=y, then A,::, refers to a single column a,. Unless specifically stated, the number of the rows of a matrix Ax:y is assumed to be equal to N. AN,(i) refers to the ith row of the mamx AN-, whem 0 S i S N -1. A column vector of N entries of which half are 0's and the other half m 1's is called a column permutation. Unless otherwise stated, any column of any matrix in this paper is a column permutation. The binary representation of a potsi tive integer OSbSN-1 is (b1b2 ' . ' b n) such that b == b .2n-1+b2.2n-2+ +bn.20. A permutation on a set X is a bijection of X onto itself. A permutation f permutes the: ordered list 0, 1, . , N-1 into f (0), f (1), . , f (N -1). A cyclic notation [20,21] can be used to represent a permutation as the product of cycles, where a cycle (c0c1c2 c k - 1 ~ ~ ) means f ( co )=c l , f ( c l )=c2 , . - . f (C~-I)=CAY andf (ck) = co. The composition of several permutations f 1 .f2 fk is; evaluated from left to right, i.e., it maps i into fk( . . Cf2Cfl (i))) . ). Definition 11.1. (Permutation matrix, identity permutation matrix, reverse permutation matrix): A permutation h can be represented by a N:xn binary matrix cdled pennutation matrix, H, such that its ith row, HNxn(i), is the binary representation of the integer Mi). The identity permutation matrix denoted by IN:cn is the matrix wh~ose ith row is the binary representation of i (this is called "stmidard matrix" in [I:!]). The reverse permutation matrix, denoted RNxn, is the matrix whose jth column is the (n+l-j)th column of IN,. For instance, the identity permutation matrix Igd, the reverse pennutation matrix R g a and a permutation matrix E g a are shown below: Clearly, there is a one-to-one correspondence between permutations and permuta- tion matrices. For instance, R8a represents the permutation r: Using the cyclic notation, r is represented by r = (0)(1 4)(2)(3 6)(5)(7:). 11.1. Networks In the terminology used in this paper, a k-stage interconnection ne.twork (IN) con- sists of k columns of switching boxes (SBs), each followed and preceded by links which fonn interconnection patterns (IPS) as shown in Figure 11.1. The IPS formed by the input and output links are denoted by IPh and IPOu, respectively. 'Ibus, an IN con- tains (k +l ) interconnection patterns labeled IPa , IP 1 , IP 2 , . . . , IdPk -I, . A colrlmn of IN contains N/2 (2x2) SBs, each of which can be set either zitraight or cross. Figures II.2, II.3,II.4, II.5, and III.6 show several networks considered in this paper for N=16, namely, reverse baseline, baseline, Benes, the 4-stage shuffle-exchange (SE), and. the 4-stage inverse SE. If some networks are placed in parallel to form a new IN, then the IN is said to be a "pile of networks". Unless otherwise stated, any IN is assiamed to have N inputs/outputs and its stages are labeled from left to right starting with 1. Network stages are defined below and illustrated in the figures. Definition II.2. (Stages of reverse baseline, baseline, Benes, SE, and inverse SE networks): With one exception, a stage in the reverse baseline and SE networks con~sists of a connection pattern and the following column of SBs. The exception is the rightmost stage (i.e., the output stage) which consists of the last column of SBs and both the preceding and succeeding connection patterns. Stages are labeled from left to right in ascending order starting with 1. In the baseline network the kth stage corresponds to the (n -k+l)th stage of the reverse baseline network. (IVotice that both the reverse baseline and the baseline can have at most n stages, by &:finition). In the inverse SE network with m stages, its kth stage corresponds to the (m--k+l)th stage of the m-stage SE network. In this paper, Benes network is considemi as being com- posed of the first n-1 stages of the n-stage baseline followed by the n-stage reverse baseline. (It could also be considered as being composed of the n-stage baseline fol- loured by the last n-1 stages of the n-stage reverse baseline). Therefore, the stages of Belles network are labeled according to the labeling rules of the baseline and the reverse baseline. Column 1 2 k Figm 11.1. An IN with (2x2) SBs and interconnection patterns shown as large boxes. Fipm 11.2. The 4-stage rev- Wl ine network with 16 inputs/outputs. F i g u ~ 11.3. The 4-stage baseline network with 16 inputs/outputs. P 2 3 0 4 u i : s ,. 19 s 12 STAGE 1 2 3 4 5 6 7 Figure II.4. Benes network with 16 inputs/wtputs. 0 1 2 ;: 6 T i l ; tP 12 S 13 '- STAGE 1 2 3 4 tl Figure II.5. The omega network (i.e., the 4-stage SE) with 16 inputsloutputs. Figure II.6. The inverse omega network (i.e., the 4-stage inverse SE) with 16 in]puts/outputs. An IN having N inputs/outputs and k stages is ¬ed by both INN4 and IN 1:k, wlhere k 2 1. The subnetwork that consists of the stages x through y of IN is denoted by INX:y, where 1 S xcy 5 k. If x>y, then INxIy refers to a nil network, unless specified otherwise. IN,, 1 5 j 5 k, refers to the jth stage of The notaition used for net- works is different from that used for matrices because matrices are always ¬ed by single letters. Without loss of generality, it is assumed that routing of a permutation through a ne:twork is done as described in this paragraph. Assuming that the stages of the net- work are labeled from left to right starting with 1, if the routing tag is d ld2 . - - dk, then di is examined to set the SB at stage i as follows: if di equals zero then the output is sent to the upper output of the SB; otherwise, it is sent to the lower output. The ith entries of the routing tags of the two inputs entering a SB are also czalled the control bits of that SB. So, to set a SB properly to either straight or cross (or equivalently not to have any conflict in a SB), the control bits of a SB must constitute: the set (0, l) . In some networks, the routing tag of an input equals its destination address, but this is not always the case. In this paper the following convention is adopted to ¬e an IN: if the name of an IN has more than one word, then it is denoted by the upper case form of the first letters of those words; otherwise, it is denoted by the upper case fo~m of its first and lait letters. Also, if X X denotes an IN, then the inverse X X network may be denoted by XX- ' . The following definition applies this convention to the baseline, reverse base- line, shuffleexchange, inverse shuffle-exchange, Benes and three-stage Clos networks of interest in this paper. Definition IL3. (BE, RB, SE, SF', BS, CS, composite IN): The symbols BE, R13, SE, SE-' , BS and CS in this paper refer to the networks baseline, reverse baseline, shuffle-exchange, inverse shuffle-exchange, Benes and three-stage Clos network v(:2,2,N 12) [7,13], respectively. (If the number of inputs/outputs of he-stage Clos network v(2,2,N/2) is equal to N, then each of the outside stages of' three-stage Clos network in this paper contains N 12 (2x2) SBs and the middle stage consists of 2 boxes with N/2 inputs/outputs each). If an IN is a cascade of different INS, then it is called a composite IN and is ¬ed by the concatenation of symbols that represent the INS in tht: order they are cascaded. As an example for a composite network, the notation RB l,nSE I:,,, m 2 1, denotes the network consisting of RB followed by SE Linial and Tarsi [2] introduced the concept of balanced matrices to establish a relation between SE networks and their realizable permutations. The following definition is equivalent to the one given in [2]. Definition II.4. (Balanced matrix): Let N=2* and call a 0-1 matrix AN& bal- anced if either one of the following conditions is satisfied: 1. For k S n, it consists of any k columns of the binary representation of a permu- tation on the set {O,1, ..., N-1). 2. For k>n, every n consecutive columns farm the binary represemtation of a per- mutation on the set {O,l, ..., N-1). As an example, two balanced matrices E and F are shown below. But notice that the matrix [E F ] is not balanced. Definition ILS. (Pass, realize): A balanced matrix AN& (respectively, an IN) is said to pass a k-stage IN (respectively, a matrix AN&) if no conflict oc:curs in the SBs of tile IN when AN& is used as the routing tag for the ith input of the: IN. A network IN realizes a permutation represented by BN, if there is a network switch setting such that input iis sent tooutputB(i) for all i=O,l, . . . ,N-1. According to the last definition, in this paper, the phrases "an I N passes a bal- anced matrix" and "a balanced matrix passes an IN" are used alternatively. It is also assumed that only "one pass" is allowed through a network to realize a permutation. Themfore, the phrase "one pass" is omitted in the sequel. To emphasiu: the distinction between the meaning of the terms "pass" and "realize" as used in this paper, it is important to notice that matrix ANxk in Definition IL5 does not necessarily carrespond to the permutation realized by the network IN. Indeed, the ith row of AN& is the rout- ing tag for input i and it is only when it equals the destination of input i that AN& is the pernnutation realized by IN; the cases in which this occurs will beco~me clear in the remiainder of the paper. 11.2. A Motivational Example Consider permutations xl = (0 6)(1 2)(3 5 4)(7), x2 = (0 2)(1 4 3 '7)(5 6), and the reverse baseline network with 8 inputdoutputs, ¬ed by RB ga and shown in Figure n .7~~ . A ffame is illustrated in Figure II.7b. The binary representations of these per- mutations are given below: Figure 11.7. (a) The reverse b l i n e network with 8 inputdoutputs. (b) A frame. When the ith row, 0 S i S 7, of both xl and x2 is used as the routing tag for the ith input of RBad, no conflict occurs in the switches and connections are established between the input i and the outputs 111 ( i ) and I12(i), respectively. Irherefo~, RBad reallizes xl and x2. NOW, let US place the ith row of xl and x2 into the ith row of the frame in Figure II.7b with 8 rows as shown in Figure II.8a and Figure II.8b, respec- tivdy. Figurc II.8. (a) Frame with the binary representation of the permutation nl. (b) Frame with the binary repnsentation of the pennutation Q. The: first k columns, 1 5 k 5 3, of any of these two frames consists of 2sk rectangles of size: ~ ~ x k . Note that the matrix enclosed by any rectangle of the frames is balanced (in fact., it represents a permutation on {O,1, . . . , 2k)). It is shown in Section TV that, when the rows of any permutation realized by the reverse baseline network are placed into this type of frame, the matrix enclosed by each rectangle is balanced, and vice versa. Different frames are introduced in this paper and it is shown how they a useful to identify the permutations realized by some frequently used networks. IU. FRAMES AND FUNDAMENTAL CONCEPTS This section introduces the concept of h e s to characterize the permutations reallized by a network. Different frames are derived from this concept imd their graphi- cal representations are presented. In addition, some related fundamental concepts used in the proofs of this paper are introduced. More extended discussion o~f these concepts appears in [28]. In order to facilitate the understanding of the concept of frame, the following definition is first introduced (a k-tuple V with the elements v 1 ,v2, . . . , vk, denoted by V =: , refers to an ordered collection of k elements). Definition III.1. (Partition. Pi, block, standard partition P;, P'): Let X= (O,l, . . . , N -1 ) , N=2" and i =1,2, . . . , n. A partition Pi of X is a tuple of 2"-' dis- joint ordered subsets of X, called blocks, each of which is a tuple with 2' distinct ele- ments. The partition P;=< such that h mod 2'= 0 and h =: O,1,. . . , N-l> is a stundard partition of X. The n-tuple CP;, i=1,2,. . . ,n> is derroted by P * . Example III.1. Let N=8. The following are the standard partitions: P;=< <0,1>, <2,3>, <4,5>, <6,7> >, P;=< <0,1,2,3>, c4,5,,6,7> > and ~;=<0,1,2,3,4,5,6,7>. Also, P*=. The notion of frame is defined next and an example (Example II1.2) is given after tht: definition. Note that the frame of Figures II.7 and 11.8 is characterized by the label- ing of its columns, the labeling of its rows and how each column is partitioned. There- fa=, the definition of frame is done in terms of two mappings (the column and row latreling) and a tuple of partitions (one for each column). The column labels determine tk, number and size of the blocks in each partition and the row labeling determines the elements in each block and their order. As precisely stated in the definition, column with label p(i) carresponds to a partition with 2"-p(') blocks with 2p1(') elements each and the mth element within the jth block corresponds to the label *r) of row r = 2 i - l m -1) After Example III.2, a convenient graphical nzpresentation for frames is introduced and its use is illustrated in Example 111.3 for the frames described in Example III.2. Definition IIL2. (Frame): Let 1 5 k 5 n and 1 5 i 5 k. A frame FN*, 1 5 k 5 n, is a 3-tuple , where - pisamappingoftheset {1,2 ,..., k) into{1,2 ,..., n), - yisapermutationontheset{O,l, ..., N-1) and - P is a tuple of partitions CP B(~) ,P ~(21, . . . , Pp(k) > determined by P and y as follows: Pp(i) =

where P P ( ~ ) , ~ = CUl,j,U2,j, . . . , U2Ui),j> S U C ~ that uWj = *2Mi)u -1)i-m -1) for 1 5 j 2"-p(') and 1 m :s 28('). Definition 111.3. (a-frame, standard a-frame) : Consider the 3 - tuple c P, y, P > that defines a frame FN3. If P is the kkntity permutation, then FNXn is an a-frame denoted by Ffi3. If P and y m the identity permutations (which implies P=P'), then FNd is the standard a-frame denoted by Fpd. By definition of standard a-type frame, column flu, 1 S i 5 n, has 2"" blocks, each having 2' rows. Unless otherwise stated, the number of the rows of FTak, k 2 1, is assumed to be N. Similar to the notation of matrices, to be able to refer to specific columns of a frame, the notation FxZy is used to denote the subfratne that contains those columns of F whose indices are x, x+l, . . . , y. Unless specifically stated, the number of rows of Fxv is assumed to be N. Example III.2. The following are examples of fiames for N=8 amd k=3. (a) F8d=~P,'y,P> where P = (1 2)(3), y is the identity pzrmutation and P=:cP2,P1,P3> such that P~=P;, P~=P; and P~=P;. (b) F&=cp,y,P> where p=i&ntity permutation, y=(0)(1 ;!)(3)(4)(5)(6)(7), P=:

, PI=< <0,2>, <1,3>, <4,5>, <6,7> >, P2=< <0,2,1,3>, c4.,5,6,7> > andP3=<0,2,1,3,4,5,6,7>. (c) F#J =< $,y, P > where $ = identity permutation, y = (0)(:1 3 6 4)(2 5)(7), P=, PI=< <0,3>, <5,6>, <1,2>, <4,7> >, P:l=< <0,3,5,6>, c1,2,4,7> > andP3=c0,3,5,6,1,2,4,7>. I \ (d) FsJ= when = 1 1, y is the identity permutation, C J P = < P ~ , P ~ , P ~ > , P2=P; and P~=P;. Definition III.4. (Graphical representation of a frame, rectangle of a frame): Thc: graphical representation of a frame FNxk=< P, y, P > consists of k columns labeled fi , i =1, . . . , k, from left to right and N rows labeled y(j), j = O,1, . . . , N -1 starting at the top. The column fi m s p o n d s to the partition P g(i), that is, fi consists of 2'-Ki) blacks of 28(i) entries each. In the graphical npnsentation of a frame, any polygon with four sides and four right angles is a rectangle of theframe. Example III.3. Figures III.la, III.lb, III.lc and II1.ld show the graphical representation of the frames described in the part (a), (b), (c) and (d) of Example III.2, reslxctively. Figure III.le shows the graphical representation of the ~~tandard a-frame Fg3. The labels of the partitions below each column are implicit by the sizes of the reatangles in the column and can be omitted Figure IlI.1. (a), (b), ( c ) and (d ) are the graphical rejresentatims of the frarrres described in the part (a), (b), ( c ) and (d ) of Example III.2, respectively. (e) Graphical representation of the standard a-frame FZ,. Definition III.5. (Fit): Let k 2 1,0 S i S N-1 and 1 S j S k. Consider a balanced matrix AN& and a frame FNd. The mamx A fits FNxk if and only if, after placing aij in the ith row and jth column of FNd, every rectangle of FNd contains a balanced matrix. Example III.4. The matrix E, shown just after Definition II.4, fits all the frames shown in Figures 111.1 except FE3 shown in Figure III.le because, for example, the submatrix in the top leftmost rectangle (the 2-tuple P 1.1) is not balanc~ed. Note that the value of k in Definition III.5 does not have to equal n. It will become clear that frames of any number of columns can be used to characterize permutations (which arc represented by balanced matrices of n columns). In addition to a-frames, other two types of frames are of use in this paper. One is called universal frame and, as suggested by its name, any balanced nnatrix fits it. The other type of frame is a concatenation of frames and is useful in characterizing the per- mutations realized by, for example, composite networks. DeAnition 111.6. (Universal frame F;:~): The universal frame F;:~, k 2 1, is such that, for i=1,2, . . . , k, p(i)=n, y is the identity permutation ionand Pi = P:. The uniiversal frame F;:~ is illustrated in Figure III.2. Figwe III.2. The univetsal frame F ; ~ . Definition III.7. ( F F ) : The notation F F ~ F ; : ~ , rn 2 1, represents the f m e obtained by concatenating Frn and F;, as shown in Figure 111.3. Figure III.3. 'Zhe W e flnF;:, which is obtained by concatenating Fyn and F;:,,. The following definition states pmisely what means to establish a comspon- dent= between a frame and a network. Definition KII.8. (Correspondence between frames and networks): A frame (reslpectively, an IN) is said to correspond to an IN (respectively, a frame) if a bal- anced matrix fits the frame if and only if it passes the network. When a kame corresponds to a network it suffices to check if a, matrix fits the franle in order to determine whether the network passes the matrix. Thi!s does not mean that., when the matrix represents a permutation, the network realizes tlhe permutation. Instcxd, it means that, when the rows of the matrix are used as muting tags, no codlicts occur in the network. The complexity of checking that a matrix fits a frame is discussedl next. First, the complexity of testing if a rectangle contains a permutation matrix is considered. Next, the complexity of checking all rectangles of the same size is discussed and, finally, the complexity of checking all rectangles (i.e., the entire frame) is derived. Note that it suffices to consider only those rectangles whose number of columns equals the loga- rithm of the number of rows.' To check whether a given rectangle with x rows and l o g columns contains a balanced matrix, it suffices to verify that the rows of the mabrix are distinct. This can be done by building a binary search tree starting with the root which corresponds to the first row of the matrix; each row is then added as a leaf to the tree as long as it is distinct from all previously inserted rows and so that it satisfies the binary-search-tree property [29]. According to this property, if v (p) is the value of the row that corresponds to node p, then v @)v (p) for any node z in the right subtree of p. I:n the worst case, this procedure takes 0 (x2) steps and has average complexity of 0) (xlogr) [29]. If everal mtangles of the same size exist in a frame, then the total nuniber of rows con- tained in all the rectangles with the same columns is N. The same lprocedure can be used for each rectangle and the total worst case and average complexities will be 0 (N2) and 0 (NlogN), respectively. Because there are at most k different types of rec- tangles in a frame with k columns, the total worst case and average complexities are 0 (AN2) and 0 (ANlogN), respectively. These bounds apply to any frame, but it is pos- sible to do better with particular frames. For example, for a-frame:s the worst-case complexity becomes 0 (N2+2(N 1212+ . +(N 12)2~) =0 (N 2). IV'. BASELINE-TYPE NETWORKS Equivalence relations among INS have been extensively studied in the literature using different tools such as graph theory, group theory, and Boolean algebra [6,,11,27,26]. Networks can be madeled by directed graphs where vt:rtices and edges re~msent switches and links, respectively. Two INS arefunctional€y trquivalent if they mtlize the same set of permutations while two INS are topologically ckquivalent if their tolmlogies (i.e., directed graphs) are isomorphic. Wu and Feng [ l l ] have shown the tolmlogical equivalence of a class of MINs, which include data cnanipulator [14], oniega [I], flip [IS], SW-banyan (s=f=2) [16], and indirect binary n-cube [17], baseline anld reverse baseline [ l 11. From [18], "the notion of functional equivalence is more jmictical than that of topological equivalence because it provides an equivalence basis arrlong networks at their inputs, and thus it does not call for any malification in their inlernal switching structure". Given a netwark in a class of isomorphic INS, it is possi- blt: to rename its inputs and/or outputs so that this network can directly simulate any network in the class [ l 11. In this section, all the matrices that pass those networks that an: topologically equivalent to the k-stage baseline, 1 S k S n, are identified by a- frames that may differ only in how their rows are labeled. First, the permutations real- ized by the k-stage reverse baseline are identified. Then, this result i:s extended to the other networks. These results also show how the addition of a stage to the right of thc:se networks changes the type of their realizable permutations. An algorithm is pro- vicM to find whether a network is topologically equivalent to the revcxse baseline net- wcn-k, its corresponding frame and how to relabel inputs and outputs to achieve func- tional equivalence. Omitted proofs are provided in the Appendix. IV,.l. Correspondence between Frk and Because RB I:, is functionally and topologically equivalent to BE I,, [ l 11, any permutation that is realized by RBI:, is also realized by BE I:,, and vice versa. How- ever, this is not true for RB l : ~ and BE l : ~ , l < k < n- l, because they ;ue not function- ally equivalent (they are only topologically equivalent). But, the set of balanced matrices that pass RB 1 : ~ is the same as the set of balanced matrices that pass BE 1,k as explained next. The network RB 1 : ~ can be obtained by repositioning the SBs of the second stage through the last stage of BE 1 : ~ and reordering its outputs. It follows that any pair of routing tags that enter a SB at the kth stage of BE 1:k also enter a SB at the kth stage of RB 1:k, and vice versa. So, if the routing tags used in BE 1:k do not create any conflict, then they also do not have any conflict in the SBs of RB 1:k, and vice versa. Therefore, a balanced matrix D 1 : ~ passes RB 1:k if and only if D passes BE 1 : ~ . The following theorem shows that there exists a very close relation between RB 1 : ~ and FFk, 1 I k < n, so that the matrices that pass the network can be identified by Frk. It shows that the ith input of RB1:k is sent without conflic:ts to the output whose value equals ( i 1 2 ~ ~ 2 ~ ) plus the value of D pk(i) when the ith row of a matrix L J D 1 : : ~ that fits Frk is used as the routing tag for the ith input of RB 1:k. Theorem w.1. A matrix D 1 : ~ = [dl d2 - - . dk] fits FFk if and only if D 1:k passes RB l : ~ , 1 5 k 5 n. Moreover, RB 1 : ~ sends its ith input to its jth olutput, where j is equ~al to the sum of ( i 1 2 ~ ~ 2 ~ ) and the value of D pk(i). L I Basic idea of proof (complete proof appears in Appendix): (+) D 1 : ~ fits FFk + D 1:k passes RB 1:~ . Induction on k is used. For k=l , each rectangle of Ffuk has a 0 and a 1. These correspond to the control bits of a switch in RB 1 : ~ and, thus, no conflict occurs. For k > 1, assuming the theorem holds for k-1, it is also shown that each switch in the kth stage "has" control bits 0 and 1 and, therefore, no conflicts occur. Tlhese control bits must appear as the kth bits at the end of identical (k-1)-bit rows of subframes ~ ; l - l ~ - ~ and. F$-I*-~ of FTk so that D 1 : ~ fits FTk. Each subframe corresponds to a subnet- waik of RB 1 : ~ which is also a reverse baseline network RB2k-ixk-l. (t) D 1 : ~ passes RB 1 : ~ + D 1 : ~ fits Fluk. Induction on k is used. For k=l, if d 1 passes RB 1, then each rectangle of Fvk contains a 0 and a 1 and d l fits fl. For k >1, assuming the theorem holds for ,k-1, it is shown that for the outputs of two subnetworks Z?B$- I~-~ and RB?--~,+~ to c:ause no conflict in smy switch of the kth stage it must be the case that a 0 and a 1 are added to the k-1 entries of identical rows of the frames that correspond to the two subnetworks. This implies that D 1 : ~ fits FTk. The value of j follows from the topology of RB 1 : ~ and how switches are set by control bits. Corollary IV.l. A network with k stages and N inputs/outputs is topologically equivalent to the k-stage reverse baseline, RB 1:k, if and only if it co~responds to an a- type frame FfZk, where 1 < k < n. W.2. Permutations Realized by Baseiine-Type Networks In this section, a-type frames arc used to characterize all the permutations real- ined by any network that is topologically equivalent to the baseline network. An algo- rithm, called FRAMEIN, is introduced to determine the a-type frame that corresponds to a given network. It is also shown how to construct a network to realize all the per- mutations that fit an a-type frame. Let ~ t ~ ( a - l ) ¬e a particular a-type frame where --I,, i.e., whose row labels form the vector a-'. Let ll ¬e a network with k stages which is the same as RIP 1:k except that the label of its ith input equals the ith entry of cC1. By Corollary nr. 1, a balanced matrix D 1:k fits ~ f : ~ ( a - l ) if and only if D 1:k passes n. If k=n, any of thlesc balanced matrices represents a permutation, so that ll is a network that realizes all the permutations characterized by ~ f : ~ ( a - l ) . If kcn, then the relation between a D 1:k that fits ~ f , ~ ( a - ' ) and a permutation that passes ll is first determined. By apply- ing this relation to every balanced matrix that fits ~ f : ~ ( d ' ) , all the permutations real- i u d by II are determined. Thtorem IV.3 determines the relation between a balanced mamx that fits F; and the permutation realized by RB 1:k when this balanced matrix palsses the network. Corollary IV.3 generalizes this result to the class of baseline-type networks. Theorem IV.3. A matrix D 1:k, 1 < k S n, fits Frk if and only if RB 1:k realizes the ~ ~ ~ ~ ~ t a t i ~ n represented by [I 1:n-k D Proof. (+) Let D 1 : ~ fit FfA. It is shown that RB 1 : ~ realizes the permutation presented by [I 1:n-k D 1:kI. Theorem IV.1 states that RB 1:k sends its ith input, 0 S i S N-1,, to its jth output, where j is equal to the sum of ( d k ) and the value of D l,k(i). Due to the fact L I L 1 that [( i 1 2 ~ x~')+D l:k(i)l equals the ith row of [I l:n-k D l:kl, RB l:k realizes the per- mutation represented by [I 1:n-k D (t) Assume that RB 1:k realizes the permutation represented by [I D It is shown that D l:k fits FTk. Because RB 1:k realizes the permutation represented by [I l:n-k D it sends its ith input to the output whose value equals the sum of ( i/zk x2') and the value of L 1 D l:k(i), D l:k passes RB 1:k. It follows from Theorem IV.l that D 1:k fits Ffak. Corollary IV.3. Consider a k-stage, 1 S k I n, network rI which is topologically equivalent to RB 1 :~ . The network l7 is functionally and topologically equivalent to a network IPkRB l:kIPout, where IPa and IP,, are interconnection patterns that realize permutations Uin and h, I'e~pWtively. Also, let ~ q , ~ ( a z ) denote an a-type k-column frame whose ith row label equals a ~ l (i) for i = 0.1, . . . , N -1. A matrix D l:k fits F~:,~(uL') if and only if ll realizes the permutation ab.p.aM, where is the permuta- tion represented by the balanced matrix [I D::~] and ~ ; : ~ ( i ) = D l,,t(az (i)). Cmllary IV.3 implies that the network IPinRB 1:k corresponds to the frame ~$r(a;l), where IPi. realizes the permutation sin. Hence, for a given Ffzk, a corresponding network can be constructed easily. The following example shows the cor~struction of a network that realizes a set of permutations which inclu&s two given permutations. Example IV.1. Let N=16, k=2,O S i S N-1. Assume that a* and G, ¬e the permutations realized by the interconnection patterns IPt, and IIDM. Given two permutations a =(O98 5 1 2 12 10 14637 11 13)(4)(15) and b =: (0 7)(1)(2 3 9 13 11 8 4 5)(6 12)(10 15 14), it is shown how to con~struct a network IPi,RB l:21Pout hat realizes a set of permutations including a and b. L R ~ A and B refer to the binary representations of a and b, respectively. By Theorem IV.3, any permuta- tion that passes RB 1:2 must be represented by a balanced matrix whose first (leftmost) two columns funn I (recall that k =2 and n =4 in this example). If there was only one given permutation, then the balanced matrix representing the permutation could be co~rverted by IPb to a balanced matrix whose first two columns f m ~11:2 because IPin can be chosen so as to permute the rows in any given way. However, if more than one pennutation are given, and the first two columns of their binary representations do not form the same matrix, then IP, is needed to convert the binary n:presentations of these permutations into balanced matrices whose first two columns; form the same matrix. So, the matrices A and B are first converted by IP,, to A and B such that A 1:2 = B 1:2. Specifically, a, converts A and B to A and B, respectively such that A ( ( i ) = U&(A (i)) and B (i) = a;$(~ (i)). Then, A and B are converted by Uin to A and B, respectively such that the first two columns of each of these matrices fm 11:2. Specifically, A = A a i ) ) and ~ ( i ) = B (ail (i)). :For instance, q,,,=(O1312)(15724)(386914)(101511) converts a and b to a==(061481715 1093542131211) and b==(057 128214113613159057) , respectively. Similarly, a~,,=(O541715936131211)(2148)(10) converts 6 and b into a == (0)(1 2)(3)(4)(5 6)(7)(8)(9 10)(11)(12)(13 14)(15) and b:=(O3)(1)(2)(47)(5)(6)(811)(9)(10)(1215)(13)(14), respectively. The binary representations of a, a, ii, b, b and bare shown below. The network that realizes the pennutations a and b is shown in Figure IV. 1. r cm CK) 10 cm1 CK111 0100 01 10 0101 01 1 1 11 000 liOl0 11001 1101 1 I100 Ill 10 :1101 I11 1 - Because a 2x2 switch has two possible settings (cross and straight), the number of bal- m 12 ancxd matrices that pass a k-stage baseline-type network with N inputs equals 2 . By Corollary IV.l, for any given k-column a-type frame, there exists a corresponding baseline-type network. Therefore, exactly 2M'2 balanced matrices iit any Ff :2. For k=2, 2N balanced matrices pass a baseline-type network. Let D{:2, 1 S r 5 2N, ¬e one of the 2N balanced matrices that fit ~ 7 : ~ ( a ~ l ) . Also, assume that D;;; is obtained from DiZ2 such that D;!$ (i) = ~ i : ~ (a$(i)). Let pr denote the permutation represented by [IlZ2 D;:$]. So, the network shown in Figure IV.l realizes any of those permuta- tions that resdt from ai,.~,.q,~. The ith row of D;:; is used as the routing tag for the ith input of RB 1:2 in IPinRB l:21Pout. AS an example, let r=l and consider the bal- anced matrix shown in Figure IV.28 that fits Ffl(a2). The matrix D;$ that is obitained from DiZ2, and the matrix [Ilt2 D:~:] are also shown in Figure IV.2. When the: ith mw of D;$ is used as the muting tag for the ith input of RB I:?, RB 1:2 realizes the: permutation p1 = (0)(1 3 2)(4 5 6)(7)(8 10 11)(9)(12 15 14 13) which is represented by [I D;:: 1. On the other hand, the network IPkRB l:21Pwr realizes the permuta- tion (0 9 4 8 5 7 3 1 2 12 6)(10)(11 13)(14 15) which results from ak,.pl.h,. End of ex;ample. P ? 3 3 I ! ! 0 6 6 u p 7 7 T U 8 8 p T 9 9 u s I? Y 13 13 S 12 --- I! [Pi, RB 1:2 IP, Figure IV. 1. The network IPi,RB ,21Po, of Example 1V. 1. Figure IV.2. (a) A balanced matrix ~ 1 : ~ which fits FfZ2(a';'). (b) Fftz (a : ) with D! :2. (c) D:: whose ith row equals D : , 2 ( a z (0). (d) [I l t2 D;;: I . In the rest of this section, some preliminary results used in the Algorithm FFL4M.E-IN are first presented, then the algorithm is introduced. Lemma IV.1. Let r denote the mverse permutation mpresented by the reverse permutation matrix RN, described in Definition 11.1. The reverse baseline network R13 I:, realizes r when all the switches are set straight. Proof. The permutation realized by RB 1:" when al l the switchr:~ are set straight is determined by the intexonnection patterns IPin,IP 1, . . . , IPn-][ ,IPowt. Because IP* = IP, = identity pattern, the permutation is given by a1 .a2 . . . h - 1 where Ui is t h ~ permutation realized by IPi. Permutation Ui is such that ai(x) rotates left the right- most i+l bits of x by one position because IPi is a pile of 2"j-l shuffle-exchange pat- tnns each with 2"' links. Applying this operation for all i starting with the initial rniatrix IN, yields the reverse permutation matrix RNxn = [in in-l . i I]. Because the reverse baseline network can be converted to the bueline network by repositioning the switches of the middle stages only, Lemma N.l is also valid for the baseline network. If there exists a unique path between any input anld any output of a network, then the network satisfies the Banyan property [6,26]. Be~nnond et. al 1261 prrtsent a set of properties to determine whether a network is topologically equivalent to baseline network. Their main result is formally restated below. Theorem IV.2. [26] Let G be a directed graph representing a network with n stalges and N inputs/outputs which satisfies the Banyan property. This network is topo- logically equivalent to the baseline network if and only if both the firsit j stages and the lazit j stages of G contain 2"-J connected components for each j, 1 5 j 5 n. This result is used next as the basis for Algorithm FRAMEJN. The description of the algorithm is followed by a proof of its correctness and analysis of its complexity. Algorithm FRAME - IN Input: A network GN with 2x2 switches, n stages and 2" inputs/outputs. Output: An a-type frame that corresponds to GN if GN is topologically equivalent to the baseline network, the permutations Uin and realized by the interconnection patterns IPin and IPou, respectively, such that the network IPhGN l:nIPou is function- ally equivalent to RBN,. Step 1. Let G denote a graph with n "stages" that is obtained by representing the switches and links of the given network by vertices and edges that are directed from left to right, respec- tively. Step 2. Using a hadth-first search algorithm check whether there exists a unique path between any input vertex and any output vertex of G. If so, go to next step. If not, go to Step 9, Step 3. Let j andp be integer variables initialized to 0. Step 4. Increment j by 1. If j>n, then go to next step; otherwise, using a depth-search algorithm, check whether the last j stages of' the G contain 2"-J connected components. If so, go to Step 4. If not, go to Step 9. Step 5. Increment p by 1. Ifp>n, then go to Step 7; otherwise, using a depth-search algorithm, check whether the first p stages of G contains 2"-P connected components. If so, go to next step. If not, go to Step 9. Step 6. If p=l , let V; denote a vector of the input labels of a distinct connected component (a 2x2 switch) for each r, (1 S r S 2"-I), and then go to Step 5; otherwise, do: let V$', 1 S r S 2"-p, denote a vector that is formed by merging two vectors v!-' and v{-' for 1 Ss, t S2"'P+' and sw such that the set: of entries of V$' equals the set of input labels of a distinct con- nected component determined in Step 5. Go to Step 5. Step 7. Let y(i) = Vy (i) for i= 1,2, ..., N-1 (note that Vy is obtained in Step 6). Write "The a-type frame F?:, whose ith row label equals y(i) corresponds to the GN". Slep 8. Let o denote the permutation realized by the given network GNl,, when all the switches a ~ e set straight. The permutation realized by lPh is Uin = Y' . The permutation realized by IPOu is = o-'.aZ.r, where r is the reverse permutation represented by the reverse permutation matrix RNxn (see Definition 11.1). Stop. Step 9. Write "The given network is not topologically equivalent to baseline network and no corresponding a-type frame exists". Stop. In Steps 2 through 6, Algorithm FRAME-IN checks whether the given network satisfies the set of properties described in Theorem IV.2. Specifically, Step 2 checks the Banyan pperty, while Steps 3 through 6 check whether both the first j stages and the last j stages of the network graph contain 2"-J connected compo~~ents, for each j. So, if Algorithm FRAME-IN fails in any of these steps, then it follov~s from Theorem IV,,2 that the given network is not topologically equivalent to baseline network and, by Corollary IV. 1, has no corresponding a-type frame. It is now shown that the given network corresponds to the a-type frame deter- mined in Step 7, that is, any balanced matrix that fits the a-type frame determined in Stelp 7 passes the given network, and vice versa. Theorem IV.1 proves that, for 1 I; k I; n, the frame Ff9k corresponds to RB 1:k, that is, a balanced matrix D 1:k fits FTk if and only if D 1:k passes RB 1:k. Note that RB is a pile of 2"-j RB yjs. Recall that the only difference between the standard a-frame FTk and an a-type fiame FTtk is the order of their row labels. Because Step 7 assigns $i) to the ith row label of Ff:,, this fratne corresponds to the given network. Step 8 first assumes that the permutation real- im;l by the given network equals o when all the switches are set straight. Then, Step 8 statas that the interconnection pattern IPin ~ealizes the permutation ah = yl. Relabel- ing the ith input of the given network by $i) is equivalent to adding the interconnec- tion pattern IPi, to the left of the given network. Thus, any balanced matrix that fits the a-type frame obtained in Step 7 passes the network IPhGNI:,, and vice versa. Algo- rithm FRAME-IN also adds an interconnection pattern IP,, that realizes a permuta- tion called a& to the right of the given network such that the network IPinGN l,nIP, realizes the permutation r when all the switches are set straight. By Ixmma IV.1, the reverse baseline (baseline) realizes the permutation r when all the switches are set striiight. Therefore, the network IPhGNl:,IP0, is functionally and topologically eq~livalent o the reverse baseline and baseline networks. This completes the proof of ca-rectness of the algorithm. The graph of Algorithm FRAME-IN can have at most O(N1ogN) vertices because each vertex represents a switch. Algorithm FRAME-IN uses a breadth-first search to check whether the given network holds the Banyan property. A depth-first s e i ~ h is used to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components [29]. If V and E are the sets of vertices and edges, respectively, the running time of both a breadth-lbst search and a deipth-first search is 8(V+E). This implies that, for each value of j, Algorithm FRAME-IN takes O(N1ogN) time. Because there are 2logN iterations, the running time of Algorithm FRAMEIN is Q(N log2~) . Algorithm FRAME-IN yields a frame that corresponds to the given network. This means that any matrix that fits the frame also passes the network and vice versa. However, this does not necessarily mean that the permutation relpresented by the matrix is realized by the network. When a balanced matrix DNwr fits an a-frame corresponding to a baseline-type network, the network realizes the permutation d . cq, where d is the permutation represented by DN, and G, is the permutation reidiilized by IPW determined in Step 8 of Algorithm FRAME-IN. In other words, given a network that is topologically equivalent to the reverse baseline, relabeling its inlputs and outputs by a2 and h,, respectively, results in a new network that is func- tionally equivalent to the reverse baseline. As an example, for N =16, Algorithm FRAME-IN can be used tlo characterize the permutations of the following baseline-type networks: generaliuxl cube, omega, i n c k t binary n-cube, banyan (S=F=2), inverse omega, modified dlata manipulator, flip. The topological equivalence among these networks and baseline and reverse bassline networks is well known and previously studied in [6,11,18,:!6]. From Corol- lary IV.1, each of these networks corresponds to an a-frame. Algorithm FRAMEIN yie:lds the row labeling y and og, for each of these networks and frames as follows: y=: C& = identity permutation for the reverse baseline and baseline ~~etworks, y = the reverse permutation = (0)(1 8)(2 4)(3 12)(5 10)(6)(7 14)(9)(11 13)(15) and og, = iden- tity permutation for the omega and generalized cube, y= identity permutation and = (0)(1)(2 8)(3 9)(4)(5)(6 12)(7 13)(10)(11)(14)(15) for the indirect binary cube, banyan, inverse omega, and flip networks, y=: (0)(1)(2 8)(3 9)(4)(5)(6 12)(7 13)(10)(11)(14)(15) and G,, = identity permutation fur the modified data manipulator network. V. NETWORKS RB1:nSE1:m AND S E ~ ? ~ R B I : , This section illustrates how frames can be used to characterize permutations per- formed by relatively complex networks with more than n stages. It is first shown that the: balanced matrices that pass the network RB l,,SE I:,, m 2 0, are identified by the hame FF~F;:, (Theorem V.1). then it is shown that RB l:nSE is functionally and topologically equivalent to SE~LRB I:, (Theorem V.2). Hence, any balanced matrix paising RB p,SE I:, also passes S E ~ ~ R B I:,, and vice versa. Theorem V.l also shows hoqw the addition of a SE stage to the right of RB l,,SE I:, affects the type of permuta- tio:ns realized by the network. Theorem V.2 proves that the addition of a SE stage to the: right of RB p,SE 1, is equivalent to the addition of an inverse SE: stage to the left of S E ~ ~ R B All the proofs an provided in the Appendix. V.:L. Balanced Matrices and Shuffle-Exchange Networks Linial and Tarsi [2] have shown how balanced matrices can be used to determine the number of SE stages (or the number of passes through a single SE stage) necessary to :realize a given permutation. Lemma V. 1 below restates their resu1.t using the nota- tioin and assumptions of this paper. Lemma V.1. [2] Let MN, and CNxk be balanced matrices such that MA,, = [INxn CNxk], k 2 1 and n+k=m. The network SEN* realizes the permutation r e ~ m s e n d by M (m +I-n ):ma To illustrate Lemma V.l, consider the identity permutation matrix Isx3 = [ i i i3] and the balanced matrices Msx4 = [Isd i 1], Msd =: [ISd i 1 i2] and MEId = [ISd Isd]. Because Msx4, M8d and M sx6 are balanced, !:he permutations represented in binary by [i 2 i 3 i 11, [i3 i 1 i 2] and [ i i 2 i3] are realized by the single- stage SE, 2-stage SE and 3-stage SE with N=8 inputs/outputs, respectively. V.2. Permutations Realized by RBI,, SE1,, The following theorem shows how the concatenated frame Fyn17;:, can be used to characterize the permutations xealized by RB l:,SE 1,. Theorem V.1. A balanced matrix D m 2 0, fits the frame FTnF;:, if and only if D I:(,+,) passes the network RB l,nSE I:,. Moreover, RB l:nSE I:, realizes the Permutation represented by D (m + 1 ):(n +m ) V3. Permutations Realized by SE&,RB~:, It is shown that the network SET,&RB I:, constructed by appending the network S E ~ & to the left of RB is functionally and topologically equivalent to the network RE1:,SE 1, constructed by appending SE I:, network to the right of RBI:,. Also, because RBI,, is functionally and topologically equivalent to BE I:,, Theorem V.2 remains valid when RB is =placed by BE Theorem V.2. The network RB l,,SE I,, m 2 1, is topologically and functionally eq~livalent o the network SE~&RB I:,. VI. NEW PROOFS FOR REARRANGEABILITY OF BENES AND THREE-STAGE CLOS NETWORKS Rearrangeability of Benes and three-stage Clos networks is proven in [7,13] using the: Slepian-Duguid theoxem which applies only to symmetric netw0rk.s. In this section, new simpler proofs are provided for xemangeability of these networks using balanced msitrices and the properties of graph theory. These proofs directly lead to routing algo- ritlms [19] and provide an insight into the proofs of Section VII that identify the per- mutations realized by subnetworks of the Benes network. In what follows, some known results from [2] and definitions used in the proofs are presented first. Lemma Vl. 1 from [2] is self-explanatory. Lemma VI.1. [2] For n 2 2, let A and B be two Nx(n-1) bidanced matrices. Th~en there exists a column vector x such that both [A x] and [x B] are balanced miitrices. Note that, when the order of columns in a balanced matxix with a.t most n columns is changed, the matrix remains balanced. Therefore, the position of x in the matrices A and B in Lemma VI.l is immaterial. Because the possible choices of vector x increase as the number of columns of A or B is reduced, Lemma VI.1 remains valid when A and B have less than n-1 columns. Some properties of balanced matrices can be captured by graphs. Therefore, some basic definitions of graph theory are given below. A graph G=(V,E:) consists of a set of vertices V and a set of edges E, each of which is a pair of vertices. The union of two graphs G l=(V, E 1) and G2=(V, E2) is the graph G=G VG2:=(V, E VE 2). In other words, an edge is present in G=G 1VG2 if and only if it is present in either G 1 ar G2. A subset M of edges in a graph G is called independent or a matching if no two edges of M have a vertex in common. A matching M is said to be a pcg5ect matching if it covers all vertices of G. More extended discussion of these basic: concepts can be found in [3,4]. Definition M.1. (Perfect matching graph of a matrix): Let A be an Nxk (1 5 k 5 n -1, n 2 2) balanced matrix. A peg5ect matching graph of A, denoted by PGA, is a graph whose vertices are in one-to-one comspon&nce with the: rows of A, have degree one and vertices v i and v, are joined by an edge only if the ith row and jth row of'A are identical. If the number of columns in a balanced matrix ANd is less than n-1 (i.e., if ky). The permutations that pass BS(n-r),(h-l) are characterized by the frames defined next. This characterization illustrates how frames car1 be used to gain insight into why the Benes network is rearrangeable. All the proofs are provided in the Appendix. An example is presented to illustrate the results of these proofs. For N=16, this example clearly shows how the addition of the stage BS,-r-.l to the left of BS(n-r):(h-l) converts the frame that cmsponds to BS(,,):(h-l) i.nto a new frame thalt corresponds to the resulting network. Definition WLl. (Ffir): The frame F l y , r (01, . . - 1 and k ~ ( 1 , 2 , . . . ,n),isaframe where r y is the identity permutation on the set [0,1, . . . , N -1 ) and r Note that FfsO and FW-' are identical to F R and F;:~, respectively. As exam- ples of FTc, the frames FrAO, F 3 ' , Ffi2 and FrA3 for N=16 are illustrated in Fig- ure: VII. 1. Theorem VII.1. Consider the frame FP$, 0 6 r 6 n-1. Let S be a pile of 2,'-' cqies of a reanangeable network ~(2"' !). Let T be an IN that colnsists of the net- wark S followed by RB(r+2),,. A balanced matrix DNxn fits F$$ if ;md only if DN, passes T. Corollary VII.1. A balanced matrix DN, fits the frame FpA if and only if DN, passes the network BS(n-r):(h-l), where 0 6 r 5 n-1. Example W.1. Let N=16 and n=4. The frames FI%Q FP&~ F V ~ and FS: are shown in Figure VII.1. By Theorem IV.1, all balanced matrices that fit Ffg4 pass RB 16#4. If the stage BE3 is added to the left of RB 1:4, the network BSp7 shown in Figm VII.2.a is obtained. While RB 1:4 passes all balanced matrices that fit F?&! (the same as FYh4), a balanced matrix D 1:4 passes BS3:7 if and only if D 1:4 fits F % ~ I . I f the stage BE is added to the left of BS3:7, then BS 2:7 shown in ]Figure VII.2b is obtained. A balanced matrix D I:4 passes BSzn if and only if D 1:4 fits F%$. I f the stage BE 1 is added to the left of BS 2,7, then Benes network, BS 1 :7, shown in Figm II.4 is obtained. It is obvious that a balanced matrix D 1:4 passes BS 1:7 if and only if fits F R ~ = F ; ~ ~ ~ . Notice that, when the stage BE,, 1 S j S n-1, is added to the left o ~ B E ~ + ~ ) : ~ ~ ( . - ~ + ? B the subnetwork BEj:(n-l)RB l:(n-j+l) becomes a pile of 2,-I copies of Benes network with 2"-j+' inputs/outputs and 2n-2j+l stages. Because Benes network with 2"-j+' inputs/outputs and 2n-2j+l stages is a rcarrangeable net- work, it corresponds to the universal frame with 2"-~+' rows and n-j+l columns. Thr:~fore, the !%st n - j +l columns of Fi42-j is a pile of 2,-I copies of the universal frrume with 2"-j+' rows and n -j+l columns. End of example. Figure (a) (b) Figure W.2. (a) BS3:7 (BE3 followed by RB (b) BS2,7 (BE2:3 followed by JRB VlEL CONCLUSIONS In this paper, a new approach has been developed to characte~ize permutations reidized by some frequently used networks. The concept of frame has been introduced and different frames have been illustrated. It is simple to check whether a given permu- tation is realized by a given network once the corresponding frame and the output interconnection pattern are known. The permutations of the following three classes of networks have been character- izd: the class of k-stage baseline-type networks that are topologically equivalent to the k-stage baseline network, the class of those networks that are constructed by appending shuffle-exchange stages to the left or right of a baseline-type network., and the class of those networks that form a part of Benes network. The p m f that Benes network is rearrangeable was first presented in [7]. This pnmf is based on the Slepian-Duguid theorem which applies only to symmetric net- works. In this paper, a new simple p m f has been presented for re:arrangeability of &nes and three-stage Clos networks using the notion of balanced matrices and graph thtmry. The technique used in this proof can also be applied to nonsymmetric net- wtlrks. In practice, the results presented in this paper can be used to design networks that reidize classes of permutations that fit the same frame. In addition, engineers and/or compilers may use frames to test if the corresponding networks realize a given permu- tation. Debuggers and programming environment can also use framt:s to detect when and why a permutation cannot be realized by the network. The definitions, theorems anld lemmata that are presented in this paper to characterize the pernlutations realized in the afmmentioned networks can also be used to address the issues of routing and counting permutations. But, to limit the size of this paper, these issues are addressed in [ 19,281. It is clear that frames, as defined in this paper, cannot characterize the permuta- tions of every network. Conceivably, extensions of the definitions m,ay be possible to chimterize a larger class of networks. In particular, the concepts should be extensible to networks not considered in this paper including those constru.cted with (kxk) switches for k >2. Future research will address these issues. IX. APPENDIX Proof Theorem IV.1: (+) It is shown that if D 1:k fits FTk then D l:k passes Rbf 1:k. Proof is by induction on k. Also, it is proven that RB 1:k sends its ith input to its j th output, where j is equal to the sum of i 12' ~2~ and the value of D l:k(i). [I J I Basis Step: Let k=l. Label the SBs of RB 1 in ascending order starting with 0. (Recall that RBI refers to the first stage of a reverse baseline network with N inputs/outputs). By definition, fl contains 2"-' blocks of size 2 each. The fact that D 1.:. fits FFk implies that d l fits f. Therefore, the 2rth and (2r+l)th entries of d l winstitute the set (0.1 ), where 0 S r S 2"-'-1. Hence, when the 2rt.h and (2r+l)th entries of d 1 are used as the control bits to set the rth SB of RB 1, no conflict occurs and RB 1 sends its ith input to its jth output, where j is equal to the sum of i l2 x2 [ I J I and the value of the ith entry of d l , where 0 S i S N-1. (Recall that, if the control bit of the routing tag of an input equals zero, then the input is sent to tht: upper output of the: SB that it enters; otherwise it is sent to the the lower output of the SB). Induction Step: Assume that, for 2 k S n, if D l:(k-1) fits FF?k.-l), then D p(k-1) Ff=k, then D 1:k passes RB 1:k and RB sends its ith input to its jth output, where j is equal to the sum of [ [i /2k j x2k] and the value of D l:k(i). The frame Fj',, (m=k-l,k), can be considered as being composed of 2"- cqpies of FFm in parallel if the row labels of the ath, 0 S a S 2"-"'-1, FF, consists of the numbers (ux2"') to [ ( a + l ) ~ 2 ~ - 1 ] inclusive. Let F%, denote the a th Fp,. Rbl I:, can also be considered as being the pile of 2"-m distinct RB p,s. Label these REIT,s in ascending order starting with 0 at the top and denote the a th one by RE@,. By hypothesis, D I:, fits FTm. Let DS, denote the submritrix of D I:, that fits F$-. Thus, the induction hypothesis also implies that D$-.I*-~ (which fits F!$-lxA-l) passes RBP-I&-~ and that RB&-I*-~ sends its pth input to the output whose vsllue is equal to the value of @), where 0 I p 5 2'-'-1. Let F$-I&-~ and F$-I*-~ ¬e the 21th and (21+l)th F $ - I ~ - ~ s, respectively, where 0 5 1 S 2"-'-1. Similarly, let D$-I,~-~ and ~ p - l ~ ~ - ~ denote the 21th and (21+l)th Dql-ld-l s. Likewise, assume that RB$-I+~ and RB$-~*--~ ¬e the 22th and (Z+l)th RB&-I+~S. Because Dg-lx(k-l) is a balanced matrix of order 2'-'x(k-1), it has 2'-' distinct ralws. Therefore, the matrix ccmtains 2'-' distinct rows, each being repeated twice. Assume that the rows of H are pilrtitioned into 2'-' classes, each of which contains 2 identical rows, that is, each class contains the two copies of a distinct row of H. After adding a column permuta- tion of length 2' to the right of H, call the resultant matrix DJ~,(~) . This implies that the number of the entries of the rows of a class is incremented by 1. In order for DB4') to fit F& the kth entries of the rows of each class of H must constitute the set (0,1}, which is true because D 1:' fits Frk by the induction hypothesis. By definition, the Cth stage of reverse baseline, RBk, consists of a pile of 2"-' copies of the SE stage with 2' inputs/outputs. Assume that the network consisting of the pile of two networks RB41 and RBP-1 x(k-l) followed by the SE stage with 2' inlputs/outputs is called RBJk*. Because RB$-I,~-~ sends its pth input to the output whose value is equal to the value of D$-I*-~ (p), the first (k-1) entrjies of the row that is sent to the pth output of the network R B $ - ~ ~ ( ~ - ~ ) is the same as the first (k -1) entries oil the row that is sent to the pth output of the network R B $ - ~ ~ ( ~ - ~ ) . The Cth entries of th~ose two rows sent to the pth outputs of ~~: i - - l x(k-l) and ~ ~ % l x ( ~ - ~ ~ ~ constitute the set (0,1} because D&* fits the frame F&& by induction hypothesis. '~ecause the rows that are sent to the pth outputs of R B $ - I ~ ( ~ - ~ ) and R B $ - ~ ~ ( ~ - ~ ) enter the pth SB of the SIE stage following these networks such that the kth entries of these rows are the con- trol bits for the SB, no conflict occurs in the pth SB. This amouints to stating that R B $ ~ sends its hth input to the output whose value is equal to the value of D!k*(h), where 0 5 h S 2'-1. Therefore, the balanced matrix D 1:k passes RB 1:' and RB 1:' se:nds its ith input to its jth output, where 0 5 i 5 N-1 and j is equal to the sum of i 12' and the value of D l,'(i). [I J I (c) It is shown that, if D 1:' passes RB then D l:k fits FFk. Proof is by induc- tion on k. Basis Step: Let k=l . The fact that d l passes RB 1 implies that no conflict occurs in lthe SBs of RB 1 when the ith enay of d 1 is used as the control bit for the ith input of RB 1 in setting its rth SB. Because the control bits of the rth SB of RAB 1 constitute the set {0,1) and fittherth blockoffl,dl fitsfl. Induction Step: Assume that the thtorem holds for k-1. It is sllown that it also hollds for A, where 2 5 k 5 n. By induction hypothesis, if D$-I*,~ passes RB$-I*-~ fits F $ - I ~ - ~ . Notice that the: last stage of RBB* is the SE stage with 2' input4outputs. Recall that the network consisting of the pile of two networks R B $ - ~ ~ - ~ ) and R B ~ - I - ~ ~ ~ - ~ ) followed by the SE stage with 2' inputs/outputs is called RBgk*. As it is also explained above, the rows tha.t are sent to the pth outputs of R B % I ~ ~ - ~ ~ and enter the pth SB of the SE stage that follows these networks. 1f DB* passes R B ~ * , then the kth entries of the rows of a class of H must constitute the set (0, l) to avoid having a conflict in the pth SB'. Therefare, ~ k * fits F&*. ~t follows that D 1:' fits Proof of Corollary IV.l: (+) Let 0 be topologically equivalent to RB 1:'. When interconnection networks are modeled by directed graphs in which vertices represent the: switches and edges the links, two networks are said to be topologically equivalent if Ithe graphs representing them are isomorphic. Two graphs G and H are said to be isomorphic if there exist bijections from the vertices and edges of G to the vertices and edges of H, respectively such that the relationship of adjacency is preserved. So, if two networks are topologically equivalent to each other, one of them can tre made identical to the other network by relabeling the inputs andfor outputs. This implies that @ can be made identical to RB 1:' by relabeling the inputs and/or outputs of 41, and vice versa. Because (1) FTk corresponds to RB 1:' such that there exists a one-to-one comspon- de~~ce b tween the row labels of FEk and RB 1:' (Theorem N. I), (2:) the only differ- ence between FFk and an a-type frame FYZk is the order of their row labels, and (3) @ is i:opologically equivalent to RB l:k, there exists an a-type frame FfZk corresponding to 0 such that no conflict occurs in the switches of @ when the contents of the ith row, 0 5; i 5 N -1, of FYZk are used as the routing tag for the ith input of @. (t) Let y denote the vector of input labels of @ such that the ith enay of y equals the: ith input label of a. Let FY:k(y) ¬e the frame corresponding to @ such that the ith entry of y equals the ith row label of the frame. By definition of correspondence" (Definition III.8), no conflict occurs in the switches of when the contents of the ith row of Ff:k(Y) are used as the routing tag for the ith input of @. Note that there exists a onle-to-one comspondence between the input labels of @ and the row labels of FfZk(y). Therefare, when both the ith row label of FfZk(y) and the ith input label of @ an: replaced by the integer i, the resulting frame FTk and network still remain carrespondent to each other. By Theorem N. l , Fyk corresponds to RB 1:'. It follows thiit @ can be converted to RB l:k by relabeling the input andfor output labels of 0. Thus, O is topologically equivalent to RB 1:k. Definition IX.l. (forward-routing, reverse-routing): Given an INNxk and a set- ting of its SBs that realizes h : i+h (i), forward-routing of a matrix PL means that A (i) is sent from input i to output h (i), where 0 5 i S N-1. Likewise, reverse-routing of A m a s that A (i) is sent from the output i to the input h-'(i). The matrix A ' = A (h-' (i)), i = O,1, . . . , N -1, is obtained by fnward-routing of A. Similar1 y, the matrix A = A (h (i)), i = 0.1, . . . , N -1, is obtained by reverse-routing of A. Prod of Corollary IV.3: Because the network II is a k-stage baseline-type net- wcxk, it is topologically equivalent to RB 1:k. This implies that ml:k can be made identical to II by relabeling its inputs and/or outputs. Because relabeling the inputs (n:spectively, outputs) of RB 1:k is equivalent to adding an interconrlection pattern to thle left (respectively, right) of RB 1:k, there exist two interconnection patterns IPi, and IP', such that ll is topologically and functionally equivalent to IPinRB l,kIPM. (+) Assume that D l:k fits ~ y : ~ ( a g ) . It is shown that the network Il realizes the peZTn~tati0n Uin .p.Uw. Adding the interconnection pattern IPh to the left of RB 1:k is equivalent to rela- be:ling the ith input of RB 1:k by a2 (i). Because the only difference between two a- type frames with k columns is the order of their row labels and IPOu is just an intercon- neztion pattern, it follows from Theorem IV.l that D 1:k passes ll. By Definition IX.1, when D 1:k is forward-routed through the interconnection pattern IP",, D 1:k is mapped to D;+ = D l:k(~&l (i)), i=O, 1, . . . ,N-1. By Theorem IV.3, the subnetwork RB 1:k of n realizes the permutation p represented by [Ilzn-k D;:~]. Therefole, the network realizes the permutation ah .p.&. (t) Assume that the network n realizes the permutation Uin.p.Gu. It is shown that D l:k fits ~y:~(a&l) . The fact that n realizes the permutation aj,,.p.hu implies that the permutation p is realized by RB 1:k of n. Because p is the permutation represented by the balanced matrix [I l:n-k D;:~] such that ~;:k(i) = D l,k(az (ill, it follows from Theorem IV.3 that D ;:k passes RB 1:k. By Definition IX. 1, when D 1:k is reverse-routed through the interconnection pattern IPh, D; :~ is mapped to D 1:k. Thus, D1:k passes IPinRB 1:k. Note that the network IPaRB 1:k is identical to the network obtained. by relabeling the it11 input of RB1:k by a~'( i) . In addition, because Ffzk(a2) is the same as Frk except that the ith row label of ~ f , ~ ( a z ) equals aZ(i ) instead of i , D 1:k fits F~ :~ (UG~) . Pmof of Theorem V.l: (+) It is shown that if D l:(n+m) fits F ~ ~ ~ ' . F ; : ~ , then D passes RB p,SE I : , and the permutation represented in binary by D (,+l):(,+rn) is realized by RB l,SE Recall that by definition, RBl,,SE 1 , consists of R B I : , follov~ed by SE 1,. BCGBUSC, by hypothesis, D fits F~.,F;~,, D fits F&. RBI: , maps the matrix D l:(n+m) into the matrix denoted by D;:(~,) when D l;(n+m)(i), 0 2 i i N-1, is used as the routing tag for the ith input of RB I:,. Theorem IV.1 has shown that any balanced maarix D I : , fitting the frame Fi', passes the network RB I:,. So, when D l:,(i) is used as the muting tag for the ith input of RBI,,, RBI : , sends its ith input to the output whase value equals D So, RB I , , maps any D I : , fitting the frarne FFn to I l:,. This implies that, when D l:(n+m)(i) is used as the muting tag for ihe ith input of RBI1:,SEl:,, the submatrix D;:, of D;:(~*) is the same as the identity permutation C matrix I 1 : . Therefore, D;:(~,) is quai to the balanced matrix [I l: , Dl(n+l):(n+m)]. ByLemma V.l, S E 1 , realizes the permutation repnsented by D ; + , ) : ( ~ + ~ ) and no conflict occurs in the SBs of SE 1 , when D(n+l):(n+m) ( i ) is used as thc: routing tag for the ith input of SE I,,. Therefore, D passes RB l:nSEl:m. Now, it remains to show that RB l:,SE realizes the permutation represented by D (,+I):(, +m). Let the entries of D l:(n+m)(i) be ¬ed in binary by (x ix i . . xj, - . xi+,). The faci that D;:, of D ; : ( ~ + ~ ) is identical to I implies that RB 1,. of RR l:.SE I , , sends the routing tag D l:(n+m)(i) to the output of RBI: , whose value eq~ids the value of (xi.c: . . xl) . Because the jth output of RB 1:. is the same as the jtlY input of SE 1 , whn RB l,,SE I : , is considered, D l:(nm)(i) is sent to the jth input of ;YE I : , by RB I:,, where j equals (x ix i . . . x6 ) . Hence, the bit xf,, 1 2 p i m of (xi.xi . x i . . . xi,) is used as the control bit to set a SB at the pth stage of SE I:,, where ( x i x i . x i ) and ( X ~ + ~ X L + ~ . x;+,) are the addresses of the input and the destination, respectively. Due to the fact that D I:(,+,) passes RB l:ndSE I: , and a SE stage performs the shuffle operation followed by the exchange operation, RB l:,SE 1 : ~ sends D l:(n+m)(i) to the output of RB l:,SE whose value equals ( X : + ~ X ~ + ~ . . x;+~). Therefore, the permutation represented by D(m+l):(n+m) is implemented by RB i:,SE 1,. (+) It is shown that, if D I:(,) passes RB l:nSE then Dl:(,,) fits F & F ; : ~ ancl RB p,SE realizes the permutation represented by D (,+l):(,+m). Because, by hypothesis, D 1:(,+,) passes RB l,nSE I,,, the submatrix D I : , of D 1:(,+,) passes RB I:,. So, by Theorem IV.1, the submatrix D I : , fits Fcnm By &finition, any column of the universal frame F;:, is a single block of size N. There- fore, any balanced matrix of order ( N m ) fits F;:,. It follows that D(n+l):(n+m) fits F Hence, D fits FEF;,. The &st part (+) of the proof has shown that the permutation represented by D (m+l):(n*I) is implemented by RB 1ZnSE I : , if D fits FrnF;:,. Because it is shown above that D fits F T ~ F : : ~ , RB p,SE realizes the permutation c a m s ~ o n d i n g to D (,+I):(,,) Proof of Theorem V.2: Proof is by induction on m. Baris Step: Let m=l. In this step it is proven that RB l:,SE 1 is functionally and toymlogically equivalent to SET'RB I:,. Recall that RB is functionallly and topologi- cally equivalent to BEl,,. Therefore, RB1:,SE is functionally and topologically eqluivalent to BE l,,SE 1. BE 2:n consists of 2 copies of BE 2a-lx(n-l) :in parallel, while Rbr 1,(,-1) consists of 2 copies of RBr-lx(,-l) in parallel. Because BE 2n-14n-1) is func- tionally and topologically equivalent to RBr-14n-1), BEkn is functionally and t o p logically equivalent to RB l,(,-l). T h e r e f o ~ , BE l,,SE 1 is functionally and topologi- cally equivalent to BE 1RB l:(n-l)SE 1 . Because the last stage of RB :I:, is identical to the: SE stage, RB l:(n-l)SE is identical to RB I:,. Therefore, BE 1RB l,(,-l)SE is func- tionally and topologically equivalent to BE 1RB I,,. Due to the fact that BE 1 is identi- cal. to the inverse SE stage, BE 1R.B I : , is functionally and topologicallly equivalent to s&'RB It follows that RB lZnSE is functionally and topologically equivalent to sZ?ilRB Induction Step: Assume that, for m 2 2, the theorem holds for m - 1, and show halt it also holds for m. Because RBI: , is functionally and topologically equivalent to BtSl:,, RB l,,SE I : , is functionally and topologically equivalent to BE p,SE I,,. As it is explained in the Basis Step above, BE2,, is functionally and topologically equivalent to RBl,(,-l). Therefore, RB l,,SE I : , is functionally and topologically equivalent to BE1RB l:(n-l)SE 1,. Because the last stage of RB is identical to the SE stage, BE:lRB l,(n-l)SE 1 , is identical to BE 1RB l:,SE By the induction hypothesis, RJ! l:(rn-l) is functionally and topologically equivalent to SE~' ( , -~)RO I:.. SO, BE: RB i,,SE 1:(,-1) is functionally and topologically equivalent to B E : ~ s & ~ ( ~ - ~ ) R B ~ : ~ . Because BEl is identical to the inverse SE stage, BE: s&&,-~)RB is functionally and topologically equivalent to SE:~,RB 1,. Thus, the: theorem holds. Proof of Theorem VII.1: Case I : Let r =n -1. When r =n -1, T consists of only a rearrangeable network P(2,!) and F#F.: is identical to the universal frame F;,. By &hit ion, any balanced matrix of order Nxn fits F;, and P(2"!) passes any balanced ma.mx of order Nxn. Therefore, a DN, fits F p s if and only if DNxn passes T. Case 2: Let r=O. When r=O, F#$ and T are identical to FP,, and RBN,, respectively. Because Theoxm IV.1 shows that a DNm fits Fpm if imd only if DNm passes RBN,, Theorem VII. 1 holds for this case. Case 3: Let 1 S r S n-2. Assume that DNwr(i), 0S i S N-1, is used as the rout- ing tag for the ith input of T. (+) It is shown that, ifDN, fits Fp;, then DN, passes T. In what follows, it is first shown that the submatrix D I:(,+') of a, DN, passes S. By the &fintion of mangeability, any of the 2"'-' rearrangeable networks P(Z!!+'!) of S can pass any balanced matrix of order 2'+'x(r+l). Label these rear- raqgeable networks in ascending order starting with 0. Let Pa(2'+'!) ¬e the ath mumangeable network P (2"' !) of S, where 0 S a S zn'-' -1. Consider the universal frame ~ ; r+ ld~+ ' ) . Any column of ~>+l , ( ,+~) is just a single block of length Z+'. Because a column of ~ ; r + l d ~ + ~ ) requires a column vector of ]length 2'" to have only 2' zeros and 2r ones, any column of a balanced matrix of order 2r+1 x(r +1) fits it. It follows that any balanced matrix of order 2r*1 x(r +1) fits F x r + l . Therefore, Pa (2r+' !) corresponds to the universal hame F>+l.(, +'). The subframe F~'?JJ;+') can be considered as being a pile of 2"' -' ~>+l,( ' +')s. Label these universal frames in ascending order starting with 0. Partition the balanced submatrix D 1:(,+1) of DN, into 2"'-' balanced subma- trices of order 2'+'x(r+l) such that the set of the row indices of the ath submatrix con- sis~k of the numbers (ax2'+') to [(a+1)~2~+'-1] inclusive. Label these submatrices of o d r 2r+1x(r+l) in ascending order starting with 0. Denote the ath submatrix of D l:(r+l) by D?:(r+l). By hypothesis, DN, fits This implies that D 1:(,+1) fits Ff!$+l). Therefore, Dt(,+') fits the ath ~ : r + l d ~ + ~ ) . Because Pa(2"' !) is a rearrangcable network, it passes D!(,+l), that is, Pa(2"' !) sends its kth input to the output whose value equals D&+l) (k) where 0 S k 6 zr*'-1. This implies that the network S sends its ith input to its jth output, where j equals the sum of j/2'+' x2"' and the value of the left- [[ J I most (r+l) bits of the D ':,(i). Hence, D 1:(,+1) passes S. Theorem N.1 shows that a balanced matrix C that fits Frn passes RB I,,. Thconm IV.l also shows that RB l:k+l) sends its ith input to its mh output, where h is C equal to the sum of i nr+l x r C 1 and the value of C l,(r+l)(i). Thus, the networks li J I C RB l:(,+l) and S send their ith inpu& to their jth outputs, where j equals the sum of \ I [ii2r+' ]x2'+' 1 and the value of the ith row of the matrix the corresponding C I network that is either RB or S. By &finition, FfF!l):, is the same as Fff+l):,. This implies that Ff7!2):n is also the same as Ftf+2):n. It follows frolm this paragraph thiat the argument given in the (+) part of the proof of Theorerr1 IV.l applies to RB (r+2):n of T and FF12):n. (If in Theorem IV. 1 RB I:(, +I) and F.Ia(r+:L) are replaced by S and FR;+l), respectively, Theorem IV.l becomes identical to Theorem VII. 1). Therefore, DN, passes T. (t) It is shown that, if DN, passes T, then DN~,, fits FP&. First, consider the submatrix D 1:(,+1) of D By hypothesis, DN, passes T. This implies that D 1:(,+1) passes S because S consists of 2n-r-1 copies of a rearrange- ablle network ~(2'+'!) in parallel and Dt.r+l) passes Because any bal- anced matrix of or& 2r+'x(r+l) fits a universal frame ~>+l.( ,+~), D&r+l) also fits ~ l i r + 1 ~ ( ~ + ~ ) . Recall that Ffq;+l) can be considemd as a pile of T'-' copies of ~>+lx(r+l). The~fore, D l:(r+l) fits Fr$+l)* Now, it is shown by induction on P, 1 S S n -r -1, that D l:(r+l+$) fits FT$+l+B), assuming that DNxn passes T. (The proof presented below is analogous to part (t) of the proof of Theorem TV. 1). Busis step: Let &I. For 0 5 1 5 2n-r-2-1, let D:(~+~) (k) and ~ 3 ~ + ~ ) (k) denote % r+l l the 21th and (21 +l)th D&r+l)s, respectively. Similarly, let pa' (zr+l !) and P (2 .) denote the 21th and (21+l)th rearrangeable networks of S, respectivlely. Because the stage RBb+2) consists of a pile of 2n*-2 copies of the SE stage with 2r+2 % r+ l f inlputs/outputs, the subnetwork that consists of the pile of pal (2r+1!1) and P (2 .) is followed by the SE stage with 2r+2 inputs/outputs. Because passes I), !) sends its kth input to its mth output, where m equals the contents of D&r+l)(k). Hence, the rows that rn sent to the lrth outputs of ~~ ' (2 '+ ' ! ) and p9(2'+'!) enter the kth SB of the succeeding SE stage with 2r+2 inputs/outputs. By hypothesis, DN, passes T. This implies that D 1:(~+2) passes the network consisting of S followed by the stage RBr+2 without having any conflict in the SBs. Therefore, the (r+2)th entries of the rows that are sent to the kth outputs of pq(2'+'!) and ~'%(2'+'!) constitute the set [O,l}. Notice that these rows have the same first k-1 entries. Therefore, the (r+2)th entries of any two identical rows of the submatrix constitute the set [0,1}. Therefore, by definition of fit, D l:(r+2) fits Fd3;+2). Induction step: Assume that, for 2 5 P 5 n -r -1, D ~ : ( ~ + p ) fits FT$+$). Then, show that D l:(r+l+P) also fits FT$+l+$). Let 2 S p 5 n -r -1. By the induction hypothesis, D fits FY(;+$). It is also known that DN, passes T. So, as D passes the network consisting of S followed by RB(r+2):(r+$), Dl:(,+l+$) passes the network consisting of S followed by R13 (r +2):(r +I+$) Partition the matrix D +p) into 2"-'-p submatrices DIwx(r +p), 0 i y i 2n'-p, which are labeled in ascending order starting with 0. Let 0 S u 5 2"-"-F1-1, y1=2u and g=2u+l. The stage RB (, consists of 2 "-'-El copies of tht: SE stage with 2'+'.*p inputdoutputs. The rows that arc sent to the sth, 0 i s S 2"p-I, outputs of the subnetworks that pass ~ l b ~ ~ ~ ) and D ~ + B ~ ~ + ~ ) enter the sth SB of the SE stage with 2r+11+p inputdoutputs. Because no codict occurs in the sth SB by hypothesis, the (r+l+B)th entries of the rows entering the sth SB must constitute the se:t (0,l). There- fore:, by definition of fit, D l:(r+l+p) fits Ff2;+1+p). Proof of Corollary YII.1: Consider the network T, that is defined in Theorem W. 1, and its components S and RB(' +2):),. Recall that S consists of 2"-'-' copies of a re(irmgeab1e network ~(2'*' !) in parallel. If the Benes network BS2r+142+l) substi- tutes for each rearrangeable network ~(2 '" !) of S, then S consists of 2"-'-' copies of the rearrangeable network BS 2r+1,(2r+l) in parallel and hence S is m.ade identical to the subnetwork BS(n-r):(n+r) of BSNx(2n-l). Because BSl:(2n-I) can te considered as being composed of BE l:(n-l) followed by RB BS(n,):(n+r) is the same as BE ),(,-l)RB 1:(,+1). So, T is functionally equivalent to the network consisting of BS (:n-p):(n+r) followed by RB (, +2),,. Because the network that consists of BS followed by RB(, +2),n is identical to BS(n-r):(2n-l) and the fact that a balanced matrix DM. fits FNz if and only if DNm passes T (Theorem VII. I), DN, fits .FF;rr if and only if LbNm passes BS(,-, Therefore, the corollary holds. 0 REFERENCES [I] D. H. Lawrie, "Access and alignment of data in an array pmessor," IEEE Trans. on Comput., vol. c-24, pp. 1 145-1 155, Dec. 1975. [2] N. Linial and M. Tarsi, "Interpolation between bases and the Shuffle-Exchange network," Europ. J. Cornbinutorics, vol. 10, pp. 29-39, 1989. [3] J. A. Bondy and U. S. R. Mwty, Graph Theory with Applications, North-Holland, New York, 1979. [4] L. Lovasz and M. D. Plummer, Matching Theory, Annals of Discrete Math., 29, North-Holland, 1986. [5] H. S. Stone, "Parallel processing with the perfect shuffle,'' IEEE: Trans. on Corn- put., vol. c-20, pp. 153-161, Feb. 1971. [q D. P. Agrawal, "Graph theoretical analysis and design of multistage interconnec- tion networks," IEEE Trans. Comput., vol. c-32, pp. 637-648, July 1983. [7:1 V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, New York, 1965. [8:1 A. Waksman, "A permutation network," Journal of the ACM, vol. 15, No. 1, pp. 159-163, Jan. 1968. [9:1 C. P. Kruskal and M. Snir, "A unified theory of interconnectica network struc- ture," Theoretical Computer Science, vol. 48, pp. 75-94, 1986. [lO] K. Y. Lee, "On the remangeability of 2(log N)-1 stage permutation networks," IEEE Trans. Comput., vol. c-34, pp. 412-425, May 1985. [ l 11 C. Wu and T. Feng, "On a class of multistage interconnection ~~etworks," IEEE Trans. on Comput., vol. c-29, pp. 696-702, 1980. [1:2] T. Etzion and A. Lempel, "An efficient algorithm for generating linear transfor- mations in a shuffle-exchange network," SIAM J. Comput., Vol. 15, No. 1, pp. 216-221, Feb. 1986. [I:)] C. Clos, "A study of non-blocking switching networks," Bell System Tech. J., vol. 32, pp. 406-424, 1953. [14] T.Y. Feng, "Data manipulating functions in parallel processors and their imple- mentations," IEEE Trans. on Comput., vol. c-23, pp. 309-318, March 1974. [lii] K.E. Batcher, "The flip network in STARAN," in Proc. 1976 Int. Conf. Parallel Processing, pp. 65-7 1. [l6] L.R. Goke and G.J. Lipovski, "Banyan networks for partitioning multiprocessor systems," in Proc. 1st Symp. Compuf. Architecture, Dec. 1973, pp. 175-189. [l'?] M.C. Pease 111, "The indirect binary n-cube multiprocessor array," IEEE Trans. on Comput., vol. c-26, pp. 458-473, May 1977. [ 1131 A.Y. Oruc and M.Y. Oruc, "Equivalence relations among interconnection net- works," J. of Parallel and Distributed Computing, vol. 2, pp. 30-49, 1985. [I!)] H. Cam and J.A.B. Fortes, "Permutation routing algorithms of frequently used networks," in preparation. [20] J.J. Rotman, The theory of groups: An introduction, Allyn & Bacon, Rockleigh, N.J., 1965. [2:1] H.J. Siegel, Interconnection Networks for Large-Scale Parallel Processing, Lex- ington Books, 1986. 2 2 [2:!] A. Youssef and B. Arden, "A New Approach to Fast Control of r w 3-stage Benes Networks of r w Crossbar Switches," 1990 Comput. Archit. Conf., pp. 50- 59. [23] J. Lenfant, "Parallel permutations of data: A Benes network con~trol algorithm for frequently used permutations," IEEE Trans. on Compuf., vol. c-27, pp. 637-647, July 1978. [24.] D. Nassimi and S. Sahni, "A self-routing Benes network and parallel permutation algorithms," IEEE Trans. on Comput., vol. c-30, pp. 332-340, May 198 1. [25] C.S. Raghavendra and R.V. Boppana, "On Self-Routing in Beines and Shuffle- Exchange Networks," IEEE Trans. on Comput., vol. 40, No. 9., pp. 1057-1064, Sept. 1991. [26i] J.C. Bermond, J.M. Fourneau and A. Jean-Marie, "A graph thecmtical approach to equivalence of multistage interconnection networks," Discrete Applied Mathematics, vol. 22, pp. 201-214, 1989. [27'] D.M. Dias, Packet Communication in Delta and Related Netwonh, Ph.D. Thesis, Rice Univ., 198 1. [281] H. Cam, Design and permutation routing algorithms of rearrandpeable networks, Ph.D. Thesis, Purdue Univ., May 1992. [29'] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms, MIT Press, 1991.

rt c d d w m F

Abstract

Extracted data

rt c d d w m F

Abstract

Extracted data

Related items

Related items