Algorithm and Performance Analysis of Optical Multistage Interconnection Network

VoL11Semlcondoctor: May 2005No,2Photonicsand" ted hnologyTotal No.40Algorithm and Performance Analysis of OpticalMultistage Interconnection NetworkLIU Jiang, MAO Yourju, ZHU Ji-hua(Institute of Opt. Commun. , Chonging University of Posts & Telecommun, , Chongqing 400065, CHN)Abstract; A sorting algorithm based on the Batcher's algorithm is presented. An 8X 8 mulistageinterconnection network(MIN) is constructed. Applying wavelength division multiplexing( WDM) technologyand integrating control mode, the designed network can realize non blocking communication. The time delay ofthe MIN and the switches needed are also analyzed in theory, the deduced result conforms that the MINdesigned previously is feasible. In the case of the same communication quality guaranteed, MIN uses the leastswitches and completes the communication more efficiently.Key words: Multistage interconnection network; Non- blocking communication; Optical cross connectsCLC number:TN929.11Document code:A Article ID: 1007 - 0206(2005)02- - -0122- -071 IntroductionResearch on optical switches has been done in Ref. [1], based on these, this paper will do deeplyanalyze the algorithms and network performance. Currently, large-scale applications in science andengineering rely on larger configurations of parallel computers, often comprised of hundreds of processorsand memoriest2]. The overall speed of computation is determined not just by the speed of the processor,but also by the ability of the memory system to feed data to it. Therefore, in order to improve theperformance of parallel computers, high communication speed between central processing units(CPUs) andmemories(MEMs) is required. Traditional electric interconnection(such as bus mode) is difficult to adaptto the communication of large capacity at a high speed, and due to the limit of electron bottleneck, theperformance of electric interconnection network is difficult to improve further. Consequently, iftransferring the internal processing and switching of parallel computer from electric domain to opticaldomain, the capability of synergetic computing and processing of parallel computers will be raised highly.Using optical cross-connects (OXC) and wavelength division multiplexing ( WDM) to construct opticalswitching networks within parallel computer is an effective and feasible way. At present, multistageinterconnection network(MIN) has been playing an important role in the design of general-purpose parallelarchitectures, and applied to realize the communication between processors and memories in a parallelcomputer system. An important class is the multistage switch network comprised of a number of stages,whose each consisted of primitive switching elements. This network consists of N inputs, N outputs, andN stages. Each stage has N/2 switching elements and each switch has two inputs and two outputsconnected in a certain pattern[3]. Many such networks have a regular structure with the same number ofswitches in each stage, and where all switches have the identical designs. The input and output ports ofthe consecutive stages are connected in order to construct中国煤化工MHCNMHGReceived date:2004 - 11-03 ;revised date:2004-11-25Foundation item: Information Industry Bureau of Chongqing(2001 13010 and 200216006)Vol, 11 No.2LIUJ, et al. Algorithm and Performance Analysis of Optical Multistage Interconnection Network1232 Several Familiar MIN2.1 Basic Requirements for MINThe reason we apply MIN to realize communication between processors and memories in a parallelcomputer system is that MIN is possessed of many advantages compared to others. First, multistagenetworks are a good compromise between cost and performance. Second, it is more scalable in the costthan crossbar and more scalable in the performance than bus. Third, it is efficient and allows easyswitching between different channels. From these advantages above, we can know the basic requirementsfor MIN are efficiency and reasonable price. Apparently, network cost is mainly dependent on the numberof switches used.2.2 Performance of Several Usual MINSwitching performance, data throughput, design and realization of protocols for data packettransmission, synchronization and routing of the whole system are decided by the topology of the opticalswitching network41]. An appropriate network topology can provide flexible strategy of routing, shortenthe transmission delay and avoid transmission congestion effectively. Furthermore, the topology of theinterconnection network also decides the number of the optical switches needed, in other words, it chieflydecides the cost of the whole system. In the following, we compare the performance of several usual MIN,such as Omega network, Benes network.There are two states for an 2 X 2 opticalswitches, as shown in Fig. 1[8]. It is well knownthat the Omega network needs least optical switchesStraight connectionCross connectionon condition that each MIN has the same number ofFig.1 Two states of a 2X2 optical switchesinputs and outputs. However, Omega network is atypical blocking network. In .such blocking network, in order to establish connections between certaininputs and outputs, it may need to pass through the network in several times, which lower thecommunication efficiency evidently. Expecting for non-blocking communication in MIN, the stages ofnetworks will be increased, namely, increasing the number of 2X 2 switches is to construct the non-blocking network.The Benes network is rearrangeably non-blocking, that is, when each connection is routed through a .single path, setting up new connections may require the re-routing of existing connections's. Benesnetworks are well known for being capable of realizing all possible permutations. Compared to the Omeganetwork, much more switches are needed in Benes network. Therefore, the cost of Benes network israther high. Thus, in the case of realizing non-blocking communication, if we can reduce the number of2X2 switches properly, the cost will be reduced while the performance of the network is guaranteed. Inorder to realize a better compromise between cost and performance, a high efficient sorting network taking2X2 optical switches as basic units is presented in the paper. It can construct MIN with less number of 2X2 optical switches to realize a non- blocking network.3 Construction and Analysis of MIN3.1 Operation Principle of Comparator中国煤化工~x'sminlx.yIBatcher' s comparators are shown in Fig. 2.YHCNMHG(bJy'max(x.yIThe elementary operations of Batcher' s comparatorsFig.2 Batcher's comparatorare to compare and conditionally switch twonumbers. From Fig. 2, a comparator is a device with two inputs x and y and two outputs x' and y'. Foran increasing somparator, x'= min{x, y} and y'= max{x, y}; For a decreasing comparator, x'= max124Semiconductor Photonics and TechnologyMay 2005{x, y} and y'= min{x, y}.3.2 Sorting Algorithm DesignAcoording to a certain topology, the comparators can be connected to construct the merging network.In software terms, a merging network is a program with no branching, looping, or arithmetic other thanthe replacement of a pair of values (x; y) withc(x; y) = (min(x; y); max(x; y)), called a comparator.In hardware terms, a merging network is a branch-free and feedback-free circuit whose only logic units arecomparators. Merging network made up of comparators can used to realize sorting performance for inputserialslo]. In order to realize sorting efficiently, an advanced algorithm is certainly needed.3.2.1 Algorithm 1Batcher' s AlgorithmGiven a serial of numbers arranged from left to right needed to sort, then the sorting process is asfollows: Firstly, partition the serial into two equal parts, i. e. bisect division. Then compare and sort theleft and right halves of the serial respectively. Secondly, pick out the numbers in odd positions of theserial, and sort them to form a subset named odd subset. Thirdly, similarly, pick out the numbers in evenpositions of the serial, and sort them to form the other subset named even subset. Fourthly, combine theodd subset with the even subset. From left to right, begin with the first element from the odd subset, andthen the first number from the even subset, then the second element from the odd subset, etc, after eachelement from odd subset is a number from even subset until the two subsets forming a new whole serial,Fifthly, compare and switch each number in even position from the left with the number in odd positionimmediately to its right, and the whole sorted serial will be formed. For example, supposing a serialincluding 8 numbers as follows:36572841We sort it according to steps above.Firstly,35671248Secondly,1346Thirdly, .2578Fourthly,12354768Fifthly, .12345 678From the instance, we can know how to sort a serial with 2n elements. We can sort left and right setsof n elements, then odd and even, at last do the last cycle of even odd comparisons and switches.Recursively, as far as a serial including 16, 32 or even more elements is concerned, algorithm 1 is fit forsorting in like manner.3.2.2 Algorithm 2-Algorithm Based on Directed GraphsA directed graph, whose edges are the orderedSourcepairs of vertices, is shown in Fig. 3. That is, eachedge can be followed from one vertex to anothervertex. The edge will point out from the positionDestinationFig. 3 Directed graphthat gets the smaller number to the one that gets thelarger one. A comparison and switch of two numbers can be described as an ordered pair of numbers bymeans of a directed edge of a directed graph. If dividing initially unsorted serial into pairs, the sortingalgorithm will be different from that we have been summa中国煤化工easible.Given a serial below:YHCNMHG1p2p3p44132where, pl, p2, p3 and p4 indicate the positions of elements. We divide the serial into two pairs, i.e. (p1,p2)門叶数据p4). Sort the two pairs separately at first.Vol, 11 No. 2LIUJ, et al. Algorithm and Performance Analysis of Optical Multistage Interconnection Network 1251423Then merge by sorting the odds and evens with edges, i.e. sort (p1, p3) and (p2, p4) separately. Itmust be noticed that when combine the sorted (p1, p3) with (p2, p4), p1 and p3 are still located in oddpositions, p2 and p4 also remain in even positions of the serial.1324Finally, complete the sorting with (p2, p3).1234Thereby, a new algorithm for a serial with 4 elements can be concluded as the following steps:Firstly, divide the serial into two pairs, (p1, p2) and (p3, p4). Secondly, compare the two pairsseparately. Thirdly, sorting odds and evens with edges, (p1, p3) and (p2， p4), respectively, aftersorting, elements in odd positions are still located in corresponding odd positions, likewise, elements ineven positions are still located in corresponding even positions. Finally, sorting with (p2,p3).Applying the algorithm above to a serial with 8 elements,p1p2p3p4p5p6p7p884316572where, pl, p2, p3, p4, p5, p6, p7 and p8 indicate the positions of elements.Firstly, divide the serial into four pairs,(p1,p2) (p3,p4) (p5,p6) (p7,p8)(8,4)(3,1)(6,5)(7,2)Secondly, compare the four pairs respectively,(4,8)(1,3)(5,6)(2,7)Thirdly, sorting odds and evens with edges, sort (p1, p3), (p2, p4), (p5, p7) and (p6, p8) separately,then combine them into a new whole serial, making sure elements in odd positions before sorting remain inodd positions and elements in even positions before sorting remain in even positions.(p1,p3) (p2,p4) (p5,p7) (p6,p8)(1,3)(4,8)(2,6)(5,7)(p2,p3) (p6,p7)(1,3)(4,8)(2,5)(6,7)Repeat the merge steps on odds and evens separately as the third step,(p1,p5) (p2,p6) (p3,p7) (p4,p8) .(1,3)(4,7)(2,5)(6,8)(p3,p5) (p4,p6)(1,3)(2,5)(4,7)(6,8)Finally, compare and switch evens with odds immediately to them.(p2,p3) (p4,p5) (p6,p7)(1,2)(3,4)(5,6)(7,8)Analyzing the two algorithms above, we can draw the following conclusions, i. e.，operating principleof algorithm 1 is easier than that of algorithm 2, so algorithm 1 is more comprehensible. However, if werealize the algorithm with optical switches, algorithm 1 is more difficult to implement, because of bisectdivision of a serial. When a serial includes many elements,中国煤化工ft and right halvesstill contain many elements, which will cause sorting diffi:MYHCN M H Gorithm 2 divides aserial into many pairs,' which is fit for a 2 X 2 optical switch having two inputs and two outputs.Consequently, in the paper, algorithm 2 is adopted to construct the MIN.3.3 MIN Network ConstructionAgeordi程to the algorithm above, merging circuits can be designed. A serial having two elements is126Semiconductor Photonics and TechnologyMay 2005needed to sort, a 1 X 1 merging circuit will beenough, as shown in Fig.4. As far as a serialFig.4 1X1 merging circuithaving four elements is concerned, and whose leftand right halves are already sorted, then a 2 X 2merging circuit will be needed, as shown in Fig. 5.Recursively, if a serial has eight elements， whose一4'left and right halves are already sorted, then a 4X4Fig.5 2X2 merging circuitmerging circuit can be enough, as shown in Fig. 6. .Consequently, in order to sort any serial, based on 1X1, 2X2 and 4X4 merging circuits, if 2X2optical switches are taken as the comparators and connected each other according to sorting algorithmabove, through certain adjustment, an 8X 8 optical switching network for one node can be constructed, asshown in Fig. 7. There are four 1X1 merging circuits, two 2X2 merging circuits and one 4X 4 mergingcircuit in an 8X8 MIN. From Fig. 7, a rule can be generalized for MIN construction, i. e.，recursively,when constructing 16X 16 MIN, eight 1X 1 merging circuits, four 2X 2 merging circuits, two 4X 4merging circuits and one 8X 8 merging circuit will be needed, etc. In Fig.7, p1, p2, p3, p4, p5, p6, p7and p8 indicate the positions of elements.output- 2'四四x四二二3阳二日个日@I回回二→5回二回二i1X12X24X4Fig.7 8X8 input output MINFig.64X4 merging circuit3.4 Input-output and Route Control of 8X8 MINThere are differences between optical switchesData sourCe 1_MI→eeiving mdiand comparators. In order to realize communicationData source2. +BReceiving end2for the whole network above， certain controlData Source中→+ Reiving endprotocols are needed. In the paper, a control4上signalingmodule is adopted to control all the opticalL Tpunt Network config atI Network confg. alswitches. The whole communication course can bet Network config att: timngsenetserved as a course of sorting for certain inputControl morlule .serials. The control mode applied is that all theFig. 8 Operation principle of control protocol for MINswitches in the network are controlled concentratedly and unitedly, as shown in Fig. 8.When data sources have an information to send, link requests will be sent to the control module. Thenaccording to these requests, the control module will decide the state of all the switches and make MINcomplete a communication for coming input serials. For instance, before tn , control module has determinedthe network configuration in terms of link requests from inputs. At t;, communication begins, at the sametime, the control module will analyze the network configur中国煤化Iore, the signal formcan be bit streams or IP packets. If taking bit streams,:MYHC N M H Gansfering over eachchannel of the MIN is only one bit, if taking IP packets, signals over each channel is a IP packet.Evidently, IP packet can take much more information during the same period. As a result, we can adapt IPpackets to be the signal form to improve an efficiency for MIN,升智据computer simulation and analysis of the algorithm and control mode above, MIN is a non-Vol. 11 No.2LIUJ, et al. Algorithm and Performance Analysis of Optical Multistage Interconnection Network127blocking network, however, not absolutely non-blocking but needs meeting a condition. In other words,given any permutation， the whole network connections must be overall arranged before thecommunication. If any new connection is to be added, the network connections may be changed. Supposinga permutation coming, the control module is used to analyze and compute the status of each optical switch,and then send an order to make the network connections take effect, realizing signals pass the MIN non-blocking, which is the whole communication course. When the next signal permutation coming, the wholeprocess is repeated.' Through analysis, if current network connections are fit for the next signalspermutation passing， the whole network connections will not be changed. If not， the networkcommunication will be paused; After the network is reconstructed, the communication will be resumed.3.5 Analysis on Transmission Delay and Number of Needed Optical Switches3.5.1 Transmission Delay AnalysisFrom graph theory, sorting numbers N = 2k i.e., K=logzN, as far as an 8X8 MIN is concerned,N=8, taking the time for two numbers sorting as a unit, i.e. T(2)= logz2=1. From Fig. 7, first passneeds four (1X1) merge circuits, the time delay is 1 unit; Second pass needs two (2X2) merge circuits,the time delay is 1+ log2=2 unit; Third pass needs one (4X4) merge circuits, the time delay is 1 十log24= 3 unit; Recursively, Mth pass needs N/2"(2M- 1 2M-1) merge circuits and the time required will be1 + log2(2M-1) = M. Supposing T(N) indicates the time required to sort a serial of size N = 2k ,consequently,log2.NT(N)= > M = logzNX (log2N +1)/2(1)Hence, the time required for an 8X8 MIN can be calculated as T(8)= logz8X (log28+1)/2=3X(3+1)/2=6 unit.In Fig. 9, taking the time for passing a switchas a unit. Obviously, the time delay increasesquickly when input serial is lengthened. In thepaper, since all the switches are controlledconcentratedly and unitedly by a module, the timeLength of input serialdelay will be different. That is to say, before anyFig. 9 The time delay graphcommunication, the whole network connections is determined by the control module, which according tothe link requests from data sources decides the network connections, i, e. , decides the state for each opticalswitch in MIN. When control module has calculated all optical switch states, there will be an order tomake the whole MIN connected as the calculated result, herein, all optical switches are switched to therequired state at the same time. Consequently, if serving the switch time between bar and cross state for aswitch as a unit, then T(8)=1. So the time delay for signal transmission is reduced evidently.3.5.2 Number of Needed Optical SwitchesAnd (2M-1X2M-1) merge circuit uses 1+ 2M-1 Xlog2(2M-1)=1+(M- 1)X 2M-1 comparator circuits.Given C(N) indicates the number of comparator circuits needed to sort a serial with length of N = 2Knumbers, according to Eq. (1), it is can be deduced as follows, .log2NC(N)= 2效[1+(M-1)X2*-]= N2[2中国煤化工log2NX (log2N- 1)*IHCNMHGv- 11N{1-yev+N4(2)By using Eq. (2) ,when N=8, .C(8)= 8X+ loex(los-1}=8x(青+3X2)= 19(3)<{1-. I128Semiconductor Photonics and TechnologyMay 2005From Eq, (3), only 19 switches will be needed in 8X8 MIN and the result conforms to that we havedesigned. Compared to Omega network, MIN improves the communication efficiency because of realizingnon-blocking communication. Likewise, compared to Benes network, MIN decreases the cost of networkdue to use less switches to construct the MIN. Consequently, according to the basic requirement for MIN,MIN is superior to the other networks.4 Increasing Traffic Capacity for MINWhen the destination addresses of severalControl, module ]signals are identical with each other, if these signalsI (Dalia D-MUX计:MINA.A)can pass through the MIN at a time, the| Data :NUX74DEMUX rSink ocommunication efficiency will be raised. UsingFig. 10 WDM applied in MINWDM technology, a single fiber can be partitionedinto multiple communication channels. Therefore, if several signals have the same destination output end,they can be multiplexed in a single optical fiber applying WDM technology, and then pass through the MIN .once. In this way, traffie capacity of MIN is expanded. From Fig. 10, by right of WDM, each data blockin which signals included have the same destination address can pass through the MIN at a time.Distinctly, the communication ability of MIN is raised highly.5 ConclusionWhen 2X2 optical switches are taken as the comparators, an 8X8 MIN is constructed based on thealgorithm presented. Combining WDM technology with a control module, the MIN provides the featureswith higher efficiency and lower cost, which realizes not only non-blocking communication but reduces thetime delay as soon as possible. Through comparing with other networks, MIN is more preferable to beapplied in interconnection network of parallel computing systems and makes data transmission much moreefficient.References:[1] HE Wei, MAO You-ju, LIU Jiang. Design and simulation of routing-switching protocol based on optical switch array[J]. Semiconductor Photonics and Technology, 2004, 10(3): 152-157.2] Grama A, Gupta A. Introduction to Parallel Computing(2nd Ed. )[M]. England; Pearson Education, 2003. 7.3] Katangur A K, Fraser M D. Simulated annealing routing and wavelength lower bound estimation on wavelength-divisionmultiplexing optical multistage networks[J]. Opt. Eng. , 2004, 43(5): 1 080-1 091.[4] Earnshaw M P,Soole J B D，Cappuzzo M，et al. 8 X 8 optical switch matrix using generalized Mach- Zehnderinterferometers[J]. IEEE Photon. Technol. Lett. ，2003, 15(6) :810-811.[5] Sapountzisy G, Katevenisy M. Benes switching fabrics with 0( N)-complexity internal backpressure[A]. IEEE Proc.Workshop on High Performance Switching and Routing (HPSR)[C]. USA: 1EEE, 2003. 11-16.[6] Bender E A. Periodic sorting using minimum delay, recursively constructed merging networks[J]. The ElectronicJournal of Combinatorics, 1998， 5(1): 2-3.Biography :LIU Jiang (1981-)， male, a native cYH中国煤化工He is now a masterstudent of Institute of Optical Commur. CNMH Gversity of Posts &Telecommunications. His main research interest is in the field of optical communication.E-mail: lonela@ sina. com