Space-Efficient Parallel Bitonic Sorting On a Cluster of PCs

Main Article Content

Jureeporn Boonniyom*
Phairoj Samutrak
Jeeraporn Srisawat

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

Section
Original Research Articles

References

[1] Batcher, K.E. 1968 Sorting networks and their applications. Proceedings Spring Joint Computing Conference AFIPS. Washington DC. 307-314.
[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