Optimally scaling permutation routing on reconfigurable linear arrays withoptical buses

We present an optimal and scalable permutation routing algorithm for three reconfigurable models based on linear arrays that arrow pipelining of infor mation through an optical bus. Specifically: for any P less than or equal t o N, our algorithm routes any permutation of N elements on a P-processor mo del optimally in O(N/P) steps. This algorithm extends naturally to one for routing h-relations optimally in O(h) steps. We also establish the equivale nce of the three models: linear array with a reconfigurable pipelined bus s ystem, linear pipelined bus, and pipelined optical bus. This implies an aut omatic translation of algorithms (without loss of speed or efficiency) amon g these models. (C) 2000 Academic Press.