Abstract
An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a PE address Matrix transpose, bit reversal, vector reversal, and perfect shuffle are examples of data permutations that can be specified in this way The algorithm presented uses the minimum number of unit distance routing steps for every data permutation that can be specified as above.
Original language | English (US) |
---|---|
Pages (from-to) | 6-29 |
Number of pages | 24 |
Journal | Journal of the ACM (JACM) |
Volume | 27 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1 1980 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- ILLIAC IV
- complexity
- data routing
- mesh-connected computer
- parallel algorithm
- permutation