Routing and Scheduling for a Novel Optical Multistage Interconnection Network

Multistage Interconnection Networks (MINs) are popular in computing and communication applications. Recently, there have also been significant advancesin electro-optic switches that have made Optical MINs (OMINs) a good choice for the high channel bandwidth and low communication latency of high performance computing and communication applications. However, OMINs introduce crosstalkwhich results fromcoupling two signals within oneswitching element. Under the constraint of avoiding crosstalk, what we are interested inis how to realize a permutation that requires theminimum number of passes. This routing problem is an NP-hard one, and manyheuristic algorithms have been devised to find a solution. In [9], Chau and Xiao have proposed an algorithm, called the Remove Last Pass (RLP) algorithm, to avoid crosstalk and route the traffic in an OMIN more efficiently. In this paper, we focus on the routing and scheduling of a novel OMIN, the base-2 MIN, propoundedby Chau and Fu in [8]. Our experiments provethat any permutation can be realized in no more than threepasses in the base-2 OMIN by using the RLP algorithm, when the network has no more than 512 nodes. The base-2 OMIN requires only

n

(log

n

+1) switching elements (SEs)for an

n

×

n

network, compared to the crossbar, which requires O(

n

2

) SEs for an

n×n

network. Therefore,the base-2 MIN should be a good candidate for communication subsystems in a parallel computing environment.