| Sorting on a mesh-connected parallel computer |
| Full text |
 Pdf
(784 KB)
|
Source
|
Communications of the ACM
archive
Volume 20 , Issue 4 (April 1977)
table of contents
Pages: 263 - 271
Year of Publication: 1977
ISSN:0001-0782
|
|
Authors
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 12, Downloads (12 Months): 88, Citation Count: 82
|
|
|
 ABSTRACT
Two algorithms are presented for sorting n2 elements on an n × n mesh-connected processor array that require O (n) routing and comparison steps. The best previous algoritmhm takes time O(n log n). The algorithms of this paper are shown to be optimal in time within small constant factors. Extensions to higher-dimensional arrays are also given.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Barnes, G.H., et al. The ILLIAC IV computer. IEEE Trans. Comptrs. C-17 (1968), 746-757.
|
| |
2
|
Batcher, K.E. Sorting networks and their applications. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N.J., pp. 307-314.
|
| |
3
|
Baudet, G., and Stevenson, D. Optimal sorting algorithms for parallel computers. Comptr. Sci. Dep. Rep., Carnegie-Mellon U., Pittsburgh, Pa., May 1975. To appear in IEEE Trans. Comptrs, 1977.
|
| |
4
|
Flynn, M.J. Very high-speed computing systems. Proc. IEEE 54 (1966), 1901-1909.
|
| |
5
|
Gentleman, W.M. Some complexity results for matrix computations on parallel processors. Presented at Syrup. on New Directions and Recent Results in Algorithms and Complexity, Carnegie-Mellon U., Pittsburgh, Pa., April 1976.
|
| |
6
|
|
| |
7
|
|
| |
8
|
Stone, H.S. Parallel processing with the perfect shuffle. IEEE Trans. Comptrs. C-20 (1971), 153-161.
|
CITED BY 82
|
|
|
|
|
|
|
|
|
|
|
Christos Kaklamanis , Danny Krizanc , Lata Narayanan , Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.17-28, July 21-24, 1991, Hilton Head, South Carolina, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
William L. Hightower , Jan F. Prins , John H. Reif, Implementations of randomized sorting on large parallel machines, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.158-167, June 29-July 01, 1992, San Diego, California, United States
|
|
|
Venkatavasu Bokka , Koji Nakano , Stephen Olariu , James L. Schwing , Larry Wilson, Optimal Algorithms for the Multiple Query Problem on Reconfigurable Meshes, with Applications, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.875-887, September 2001
|
|
|
|
|
|
|
|
|
Bryan Ackland , Neil Weste , D. J. Burr, An integrated multiprocessing array for time warp pattern matching, Proceedings of the 8th annual symposium on Computer Architecture, p.197-215, May 12-14, 1981, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Susanne Hambrusch , Xin He , Russ Miller, Parallel algorithms for gray-scale image component labeling on a mesh-connected computer, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.100-108, June 29-July 01, 1992, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Kaufmann , Sanguthevar Rajasekaran , Jop F. Sibeyn, Matching the bisection bound for routing and sorting on the mesh, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.31-40, June 29-July 01, 1992, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dharmavani Bhagavathi , Himabindu Gurla , Stephan Olariu , Larry Wilson , James L. Schwing , Jingyuan Zhang, Time- and VLSI-Optimal Sorting on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.929-937, October 1998
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
