Deterministic permutation routing on a reconfigurable mesh
A. Kapoor, H. Schroder, Bryan Beresford‐Smith · 2002
Presents an algorithm for Permutation Routing on a reconfigurable mesh based on the divide and conquer paradigm. The algorithm has a worst case running time of 4n+O(log2/sup /n) communication steps and requires a maximum queue size of 5. The O(log/sup 2/ n) term is associated with communication of single words which convey information about the distribution of packets. Hence, if the packet length is much larger than a single word, then the constant associated with this term is negligible.>