Space-Efficient Parallel Bitonic Sorting On a Cluster of PCs
Article Sidebar
Main Article Content
Abstract
This paper presents the space-efficient parallel Bitonic sorting for a very large data set on a cluster of PCs by using MPI. Recently, most studies have focused on the theoretical approach of the parallel Bitonic sorting on shared-memory or distributed-memory parallel computers. As a combination of theoretical and practical approach, we are interested to study and implement the parallel Bitonic-sorting on a cluster of PCs with efficient-space and efficient-communication overhead. In such cluster environment, the system performance of our parallel Bitonic sorting(NBS) and existing Bitonic sorting(BS) have been compared in terms of response time, speedup, and efficiency. In experimental results, our space-efficient parallel Bitonic sorting yielded similar results to those of the parallel Bitonic MPI-based sorting, while the space of our method was improved up to 50%.
Keywords: Parallel Bitonic sorting, efficient space, efficient communication, MPI (Message Passing Interface), a cluster of PCs
Corresponding author: E-mail: s7063605@kmitl.ac.th
Article Details
Copyright Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
Here is the link for download: Copyright transfer form.pdf
References
[2] Brest, J. Vreze, A. and Zumer, V. 2000 A Sorting Algorithm on a PC Cluster. Proceedings 2000 ACM Symposium on Applied Computing (SAC’00), Como, Italy, 710-715.
[3] Gropp, W. Lusk, E. and Skjellum, A. 1994 Using MPI: Portable Programming with the Massage Passing Interface. Cambridge, MA, MIT Press.
[4] Helman, D.R. and JaJa, J. 1997 Sorting on Cluster of SMPs. 12th International Parallel Processing Symposium, University of Maryland, Colledge Park, MD, USA.
[5] lonescu, M.F. and Schauser, K.E. 1997 Optimizing Parallel Bitonic Sort. Proceedings 11th Int’l, Parallel Processing Symposium, 303-309.
[6] Kim, Y.C.Jeon, M. Kim, D. and Sohn, A. 2001 Communication-Efficient Bitonic Sort on a Distributed Memory Parallel Computer. Int’l Conference Parallel and Distributed Systems, 165-170.
[7] Lee, J.D. and Batcher, K.E. 2000 Minimizing Communication in the Bitonic Sort. IEEE Transaction on Parallel and Distributed Systems, 459-473.
[8] Message Passing Interface Forum. 1994 MPI: A message passing interface standard. Int’l Journal of Supercomputer Applications, 8(3/4).
[9] www.http://www-unix.mcs.anl.gov/mpi/papers/archive/index.html