Implementation of Permutation Functions in Illiac IV-Type Computers
- 1 September 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-25 (9) , 929-936
- https://doi.org/10.1109/tc.1976.1674718
Abstract
Much research has recently been done on processor interconnection schemes for parallel computers. These interconnection schemes allow certain permutations to be performed in less than linear time, typically 0(log N), 0(log2N), or 0(√N) for a vector of N elements and N processors. In this paper we show that many permutations can also be performed in less than linear time on a machine with an Illiac IV-type interconnection scheme, that is connections to processors at distances of ± 1 and ±√N. These reselts show that, for irregular permutations, these recently developed interconnection schemes yield a speedup of at most 0(√N) over the Illiac IV-type interconnections. These results are of current interest due to the present Illiac IV programming effort.Keywords
This publication has 10 references indexed in Scilit:
- Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange NetworkIEEE Transactions on Computers, 1976
- Interconnections for Parallel Memories to Unscramble p-Ordered VectorsIEEE Transactions on Computers, 1974
- Fast Computational Algorithms for Bit ReversalIEEE Transactions on Computers, 1974
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of EquationsJournal of the ACM, 1973
- Dynamic Memories with Enhanced Data AccessIEEE Transactions on Computers, 1972
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- The ILLIAC IV ComputerIEEE Transactions on Computers, 1968
- ILLIAC IV Software and Application ProgrammingIEEE Transactions on Computers, 1968
- An Adaptation of the Fast Fourier Transform for Parallel ProcessingJournal of the ACM, 1968
- Very high-speed computing systemsProceedings of the IEEE, 1966