Simple path selection for optimal routing on processor arrays
- 1 June 1992
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
In this paper, we consider the problem of permutation routing in two- and three-dimensional mesh-connected processor arrays. We present new on-line and off-line routing algorithms, all of which are optimal to within a small additive term. In particular, our results include the following: 1. An off-line algorithm for routing a permutation in an n x n mesh in time 2n – 1 using buffers of size 4.Keywords
This publication has 7 references indexed in Scilit:
- Constant queue routing on a meshPublished by Springer Nature ,2005
- A NOTE ON OFF-LINE PERMUTATION ROUTING ON A MESH-CONNECTED PROCESSOR ARRAYParallel Processing Letters, 1991
- Balanced routingPublished by Association for Computing Machinery (ACM) ,1991
- A unified approach to off-line permutation routing on parallel networksPublished by Association for Computing Machinery (ACM) ,1990
- Average case analysis of greedy routing algorithms on arraysPublished by Association for Computing Machinery (ACM) ,1990
- A 2 n -2 step algorithm for routing in an nxn array with constant size queuesPublished by Association for Computing Machinery (ACM) ,1989
- Optimal routing algorithms for mesh-connected processor arraysPublished by Springer Nature ,1988