Deterministic permutation routing on meshes
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 814-821
- https://doi.org/10.1109/spdp.1993.395448
Abstract
We present new deterministic algorithms for routing permutations on a two-dimensional n /spl times/ n MIMD mesh. One algorithm runs in the optimal time 2 /spl times/ n - 2, while the maximal number of packets stored in a processing unit is bounded to 81. Another algorithm runs in near optimal time, 2 /spl times/ n + O(1), and has maximal queue length only 31.<>Keywords
This publication has 8 references indexed in Scilit:
- Concentrated regular data streams on grids: sorting and routing near to the bisection boundPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal routing algorithms for mesh-connected processor arraysAlgorithmica, 1992
- Constant queue routing on a meshJournal of Parallel and Distributed Computing, 1992
- Matching the bisection bound for routing and sorting on the meshPublished by Association for Computing Machinery (ACM) ,1992
- Routing and sorting on mesh-connected arraysPublished by Springer Nature ,1988
- An optimal sorting algorithm for mesh connected computersPublished by Association for Computing Machinery (ACM) ,1986
- Systolic Sorting on a Mesh-Connected NetworkIEEE Transactions on Computers, 1985
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977