Research Article
Effect of Parallelization, Execution Time and Inter-process Communication on Sorting Techniques using Message Passing Interface
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 101 - Issue 5 |
| Published: September 2014 |
| Authors: Dev Gaurav, Sahil Arora, Prashant Gupta |
10.5120/17681-8524
|
Dev Gaurav, Sahil Arora, Prashant Gupta . Effect of Parallelization, Execution Time and Inter-process Communication on Sorting Techniques using Message Passing Interface. International Journal of Computer Applications. 101, 5 (September 2014), 7-12. DOI=10.5120/17681-8524
@article{ 10.5120/17681-8524,
author = { Dev Gaurav,Sahil Arora,Prashant Gupta },
title = { Effect of Parallelization, Execution Time and Inter-process Communication on Sorting Techniques using Message Passing Interface },
journal = { International Journal of Computer Applications },
year = { 2014 },
volume = { 101 },
number = { 5 },
pages = { 7-12 },
doi = { 10.5120/17681-8524 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Dev Gaurav
%A Sahil Arora
%A Prashant Gupta
%T Effect of Parallelization, Execution Time and Inter-process Communication on Sorting Techniques using Message Passing Interface%T
%J International Journal of Computer Applications
%V 101
%N 5
%P 7-12
%R 10.5120/17681-8524
%I Foundation of Computer Science (FCS), NY, USA
Abstract
The aim of this paper if to show that the great part of the execution time is consumed in computations. So as the number of processors increase, the amount of work done by each processor will be decrease regardless the effect of the number of physical cores used. Still the time taken to solve the computations dominates over the communication time as by increasing number of processors; tasks are more divided so overall time decreases. The total overhead generated from process initializations and inter-process communication negatively affects the execution time. Using MPI, parallelization on five sorting techniques which are selection sort, bubble sort, quick sort, insertion sort and shell sort have been implemented.
References
- Narayan Desai, Andrew Lusk, Rick Bradshaw, Ewing Lusk, "MPISH: A Parallel Shell for MPI Programs", 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05), pp. 1530-2075
- Fangfa Fu, Siyue Sun, Xin'an Hu, Junjie Song, Jinxiang Wang and Minyan Yu, "MMPI: A Flexible and Efficient Multiprocessor Message Passing Interface for NoC-Based MPSoC", IEEE, 2010, pp. 359-362
- Jesper Larsson Träff, William D. Gropp and Rajeev Thakur, "Self-Consistent MPI Performance Guidelines", IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, May 2010,vol 21, pp. 698-709
- Zhongxiao Zhao, Chen Min and Fuzhou, "An Innovative Bucket Sorting Algorithm Based on Probability Distribution", World Congress on Computer Science and Information Engineering, 2009, pp. 846-850
- Adeel Abbas, Affan Ahmad, "Object Oriented Parallel Programming", IEEE, 2002, pp. 89-93
- Xiao-ping LIU, En-zhu WANG, Li-ping ZHENG, Xing-wu WEI," Study on Template for Parallel Computing in Visual Parallel Programming Platform", 1 st International Symposium on Pervasive Computing and Applications, 2006, pp. 476-481
- Sequential and parallel sorting algorithms http://www. iti. fh-flensburg. de/lang/algorithmen/sortieren/algoen. htm
- LINUX MAGAZINE-MPI in Thirty Minutes http://www. linux-mag. com/id/5759/
- Message Passing Interface (MPI) Author: Blaise Barney, Lawrence Livermore National Laboratory
- R. S. RamPriya, M. A. Maffina, "A Secured and Authenticated Message Passing Interface for Distributed Clusters", SPSymposium, IIITD, 2013
- Wang Xiang, "Analysis of the Time Complexity of Quick Sort Algorithm", IEEE, 2011, pp. 408-410
- Keliang Zhang,"A Novel Parallel Approach of Radix Sort with Bucket Partition Preprocess", IEEE, 2012, pp. 989-994
Index Terms
Keywords