74Accesses
3Citations
Abstract
We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
H. R. Arabnia and S. M. Bhandarkar, Parallel Stereocorrelation on a Reconfigurable Multi-Ring Network,The Journal of Supercomputing,10, pp. 243-269, 1996.
M. D. Atkinson, J. R. Sack, N. Santoro, and T. Strothotte, Min-max Heaps and Generalized Priority-Queues,Communications of ACM,29, pp. 996-1000, 1986.
G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith, and M. Zagha, A Comparison of Sorting Algorithms for the Connection Machine CM-2, to appear inCommunication of ACM.
G. M. Amdahl, Validity of Single-Processor Approach to Achieving Large-Scale Computing Capability,Proc. AFIPS Conference, pp. 483-485, 1967.
X. Guan and M. A. Langston, Time-Space Optimal Parallel Sorting and Merging,IEEE Transactions on Computers,40, pp. 596-602, 1991.
J. Gustafson, Reevaluating Amdahl's Law,Communication of ACM,31, pp. 532-533, 1988.
K. Hwang,Advanced Computer Architecture: Parallelism, Scalability, Programmability, McGraw-Hill, 1993.
J. Jang and V. K. Prasanna, An Optimal Sorting Algorithm on Reconfigurable Mesh,Proc. 6th Int. Parallel Processing Symposium, pp. 130-137, 1992.
D. E. Knuth,The Art of Computer Programming, Vol.3, Addison Wesley, 1973.
H. Li and M. Maresca, Polymorphic-Torus Network,IEEE Transactions on Computers,38, pp. 1345-1351, 1989.
R. Lin, S. Olariu, J. Schwing, and J. Zhang, Sorting in O(1) Time on a Reconfigurable Mesh of Sizen x n,Parallel Computing: From Theory to Sound Practice, Proceedings of EWPC'92, pp. 16-27, 1992.
R. Miller, V. K. Prasanna-Kumar, D. Reisis, and Q. F. Stout, Meshes with Reconfigurable Buses,Proceedings of the International Conference on Parallel Processing, Vol.1, pp. 205-208, 1988.
M. Nigam and Sahni, Sorting n Numbers onn x n Mesh with Buses, Technical Report #92-5, University of Florida, Gainsville, 1992.
S. Olariu and J. Schwing, A New Deterministic Sampling Scheme with Applications to Broadcast Efficient Sorting on the Reconfigurable Mesh,Journal of Parallel and Distributed Computing, to appear.
S. Olariu, J. Schwing, and J. Zhang, Applications of Reconfigurable Meshes to Constant-Time Computations,Parallel Computing,19, pp. 229-237, 1993.
X. H. Sun and L. M. Ni, Scalable Problems and Memory-Bounded Speedup,Journal of Parallel and Distributed Computing,19, pp. 27-37, 1993.
Y. Zhang and S. Q. Zheng, Design and Analysis of a Systolic Sorting Architecture,Proceedings of 7th Symposium on Parallel and Distributed Processing, pp. 652-659, 1995.
Author information
Authors and Affiliations
Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75083, USA
S. Q. Zheng
Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, LA, 70803, USA
Balaji Calidas
Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX, 75275, USA
Yanjun Zhang
- S. Q. Zheng
You can also search for this author inPubMed Google Scholar
- Balaji Calidas
You can also search for this author inPubMed Google Scholar
- Yanjun Zhang
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Zheng, S.Q., Calidas, B. & Zhang, Y. An Efficient General In-Place Parallel Sorting Scheme.The Journal of Supercomputing14, 5–17 (1999). https://doi.org/10.1023/A:1008173729055
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative