Parallel Sorting with Serial Memories
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 379-383
- https://doi.org/10.1109/tc.1985.5009391
Abstract
This correspondence examines the problem of sorting on a network of processors, where each processor consists of a single storage register and a small control unit capable of comparing two numbers and has a single serial memory attached to it. We show how to sort optimally on one- or two-dimensional arrays of p processors in time θ(n + (n2/p2)) and θ((n/√p) + (n2/p2)), respectively. Because of the implementational advantages of serial memories, we feel that our architecture will be attractive for several applications.Keywords
This publication has 9 references indexed in Scilit:
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- On the Complexity of Sorting in Magnetic Bubble Memory SystemsIEEE Transactions on Computers, 1980
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Permutation of data blocks in a bubble memoryCommunications of the ACM, 1979
- Algorithm and Hardware for a Merge Sort Using Multiple ProcessorsIBM Journal of Research and Development, 1978
- Optimal Sorting Algorithms for Parallel ComputersIEEE Transactions on Computers, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971