''Optimally Scaling Permutation Routing on Reconfigurable Linear Arrays with Optical Buses''

Jerry L. Trahan

Anu G. Bourgeois

Yi Pan

Ramachandran Vaidyanathan

Proc. IPPS/SPDP'99 (13th Int'l. Parallel Processing Symposium and 10th Symp. on Parallel and Distr. Processing), pp. 233-237.


We present an optimal and scalable permutation routing algorithm for three reconfigurable models based on linear arrays that allow pipelining of information through an optical bus. Specifically, for any $P\le N$, our algorithm routes any permutation of $N$ elements on a $P$-processor model optimally in $O(\frac{N}{P})$ steps. This algorithm extends naturally to one for routing $h$-relations optimally in $O(h)$ steps.

We also establish the equivalence of the three models, LARPBS, LPB, and POB. This implies an automatic translation of algorithms (without loss of speed or efficiency) among these models.

This work was supported in part by the National Science Foundation under grant number CCR-9503882 and the Louisiana Board of Regents through the Louisiana Education Quality Support Fund under contract number LEQSF(1994-96)-RD-A-07.