Research Article
Parallel Quick Sort using Thread Pool Pattern
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 136 - Issue 7 |
| Published: February 2016 |
| Authors: Somshubra Majumdar, Ishaan Jain, Aruna Gawade |
10.5120/ijca2016908495
|
Somshubra Majumdar, Ishaan Jain, Aruna Gawade . Parallel Quick Sort using Thread Pool Pattern. International Journal of Computer Applications. 136, 7 (February 2016), 36-41. DOI=10.5120/ijca2016908495
@article{ 10.5120/ijca2016908495,
author = { Somshubra Majumdar,Ishaan Jain,Aruna Gawade },
title = { Parallel Quick Sort using Thread Pool Pattern },
journal = { International Journal of Computer Applications },
year = { 2016 },
volume = { 136 },
number = { 7 },
pages = { 36-41 },
doi = { 10.5120/ijca2016908495 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2016
%A Somshubra Majumdar
%A Ishaan Jain
%A Aruna Gawade
%T Parallel Quick Sort using Thread Pool Pattern%T
%J International Journal of Computer Applications
%V 136
%N 7
%P 36-41
%R 10.5120/ijca2016908495
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Sorting algorithms, their implementations and their applications in modern computing necessitates improvements for sorting large data sets quickly and efficiently. This paper will analyze the performance of a multi-threaded quick sort implemented using the thread pool pattern. The analysis will be done by comparing the time required to sort various data sets and their memory constraints, against the native sorting implementations of the Dual Pivot Quicksort and Merge Sort using the Fork-Join framework in the Oracle Java 8 programming language. Analysis is done of the effect of different number of processor (cores) of the test machine, as well as the performance barrier due to the initial time taken to create “p” threads, p being the number of processors. This paper also analyzes the limitations of the inbuilt Java method Arrays.parallelSort() and how the proposed system overcomes this problem. Finally, it also discuss possible improvements to the proposed system to further improve its performance.
References
- “Parallel Programming in C with MPI and OpenMP”. M. J. Quinn, Tata McGraw Hill Publications, 2003, p. 338
- “Java Thread Programming”, Paul Hyde, ISBN 0-672-31585-8.
- “Multi-Threaded Programming in C++”, Mark Walmsley, Springer, ISBN 1-85233-146-1.
- “Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (3 ed.)”.Sedgewick, Robet (1 September 1998).
- “Arrays (Java Platform SE 8)."Arrays (Java Platform SE 8). Web. 28 Mar. 2015.
- “Introduction to Algorithms”. Cambridg. Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
- “A Simple, Fast Parallel Implementation of Quicksort and Its Performance Evaluation on SUN Enterprise 10000.” Tsigas, P., and Yi Zhang. Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003. Proceedings. (2003)
- “Techniques for Optimizing Applications - High Performance Computing”, Garg, Rajat P. & Sharapov, Ilya. Prentice-Hall 2002,
Index Terms
Keywords