''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.
Abstract:
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.