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 Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant 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.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
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
