''An Optimal and Scalable Algorithm for Permutation Routing on Reconfigurable Linear Arrays with Optically Pipelined Buses''

Jerry L. Trahan

Anu G. Bourgeois

Yi Pan

Ramachandran Vaidyanathan

Journal of Parallel and Distributed Computing, vol. 60, no. 9, pp. 1125-1136, 2000


Many practical and efficient algorithms have been designed for models based on reconfigurable optical buses. Most algorithms, however, assume that the problem size determines the physical size of the model. This paper studies the scalability of basic data movement operations on an LARPBS to efficiently implement arbitrarily sized algorithms on a given sized LARPBS.

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 in $O(N/P)$ steps. This algorithm extends naturally to one for routing $h$-relations optimally in $O(h)$ steps. These results hold much significance toward designing scaling simulations for these models.

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. In particular, since the LPB is the same as an LARPBS without the ability to segment its buses, their equivalence establishes reconfigurable delays (rather than segmenting ability) as the key to the power of optically pipelined 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.