Special Issue — International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2009)No Access

AN EFFICIENT PARALLEL SORTING COMPATIBLE WITH THE STANDARD QSORT

DUHU MAN

Department of Information Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashihiroshima, Hiroshima 739-8527, Japan

Search for more papers by this author

YASUAKI ITO

Department of Information Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashihiroshima, Hiroshima 739-8527, Japan

Search for more papers by this author

, and

KOJI NAKANO

Department of Information Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashihiroshima, Hiroshima 739-8527, Japan

Search for more papers by this author

https://doi.org/10.1142/S0129054111008568Cited by:5 (Source: Crossref)

Abstract

The main contribution of this paper is to present an efficient parallel sorting "psort" compatible with the standard qsort. Our parallel sorting "psort" is implemented such that its interface is compatible with "qsort" in C Standard Library. Therefore, any application program that uses standard "qsort" can be accelerated by simply replacing "qsort" call by our "psort". Also, "psort" uses standard "qsort" as a subroutine for local sequential sorting. So, if the performance of "qsort" is improved by anyone in the open source community, then that of our "psort" is also automatically improved.

To evaluate the performance of our "psort", we have implemented our parallel sorting in a Linux server with four Intel hexad-core processors (i.e. twenty four processor cores). The experimental results show that our "psort" is approximately 11 times faster than standard "qsort" using 24 processors.

Keywords:

References

D. E. Knuth, The Art of Computer Programming. Vol.3: Sorting and Searching, 1973 . Google Scholar
S. G. Akl , Parallel Sorting Algorithms ( Academic Press Inc. , 1990 ) . Google Scholar
M. Jeon and D. Kim, International Journal of Parallel Programming 31(1), 21 (2003), DOI: 10.1023/A:1021734202931. Crossref, Web of Science, Google Scholar
K. Batcher, Sorting Networks and Their Applications, Proceedings of the AFIPS Spring Joint Computer Conference 32 (1968) pp. 307–314. Google Scholar
M. F. Ionescu and K. E. Schauser, Optimizing Parallel Bitonic Sort, Proceedings of the 11th International Symposium on Parallel Processing (Geneva, Switzerland, 1997) pp. 303–309. Google Scholar
D. R. Helman, D. A. Bader and J. JáJá, Journal of Parallel and Distributed Computing 52, 1 (1998), DOI: 10.1006/jpdc.1998.1462. Crossref, Web of Science, Google Scholar
A. C. Dusseauet al., IEEE Transactions on Parallel and Distributed Systems 7, 791 (1996), DOI: 10.1109/71.532111. Crossref, Web of Science, Google Scholar
A. Sohn and Y. Kodama , Load Balanced Parallel Radix Sort , Proceedings of the 12th ACM International Conference on Supercomputing . Google Scholar
S. J. Leeet al., Journal of Parallel and Distributed Computing 62, 656 (2002), DOI: 10.1006/jpdc.2001.1808. Crossref, Web of Science, Google Scholar
P. Tsigas and Y. Zhang, A Simple, Fast Parallel Implementation of Quicksort and its Performance Evaluation on SUN Enterprise 10000, Proceedings of Euromicro Conference on Parallel, Distributed, and Network-Based Processing (2003) pp. 372–381. Google Scholar
D. R. Helman and J. JáJá, Designing Practical Efficient Algorithms for Symmetric Multiprocessors, Algorithm Engineering and Experimentation (ALENEX'99)1619, Lecture Notes in Computer Science (Springer-Verlag, Baltimore, MD, 1999) pp. 37–56. Google Scholar
R. Francis and I. Mathieson, IEEE Transactions on Computers 37, 1619 (1988), DOI: 10.1109/12.9738. Crossref, Web of Science, Google Scholar
J. Chhugani et al. , Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture , Proceedings of the 34th International Conference on Very Large Data Bases 1 ( 2008 ) . Google Scholar
R. Parikh, Accelerating QuickSort on the Intel Pentium 4 Processor with Hyper-Threading Technology, 2008 , http://softwarecommunity.intel.com/articles/eng/2422.htm . Google Scholar
N. Govindarajuet al., GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management, Proceedings of the ACM SIGMOD International Conference on Management of Data (2006) pp. 325–336. Google Scholar
A. Gress and G. Zachmann , GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures , Proceedings of 20th International Parallel and Distributed Processing Symposium . Google Scholar
E. Sintorn and U. Assarsson, Journal of Parallel and Distributed Computing 68, 1381 (2008). Crossref, Web of Science, Google Scholar
B. Gedik, R. Bordawekar and P. S. Philip, CellSort: high performance sorting on the cell processor, Proceedings of the 33rd international conference on Very large data bases (2007) pp. 1286–1297. Google Scholar
H. Inoueet al., AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors, Proceedings of the 16th International Conference on Parallel Architectures and Compilation Techniques (2007) pp. 189–198. Google Scholar
K. Nishihataet al., Parallel sampling sorting on the multicore processors, Proceedings of the 8th International Conference on Applications and Principles of Information Science (2009) pp. 233–236. Google Scholar
T. Hayashi, K. Nakano and S. Olariu, IEEE Trans. on Parallel and Distributed Systems 9(3), 275 (1998), DOI: 10.1109/71.674319. Crossref, Web of Science, Google Scholar
OpenMP Application Program Interface , http://www.openmp.org/ . Google Scholar
Intel Corporation, Intel Xeon Processor 7000 Sequence , http://www.intel.com/products/processor/xeon7000/ . Google Scholar
Diomidis D. Spinellis and Markus Weissmann, C Multithread Library – libmt , http://libmt.sourceforge.net/ . Google Scholar