CFP last date
22 July 2024
Reseach Article

Effect of Parallelization, Execution Time and Inter-process Communication on Sorting Techniques using Message Passing Interface

by Dev Gaurav, Sahil Arora, Prashant Gupta
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 101 - Number 5
Year of Publication: 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 },
issue_date = { September 2014 },
volume = { 101 },
number = { 5 },
month = { September },
year = { 2014 },
issn = { 0975-8887 },
pages = { 7-12 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume101/number5/17681-8524/ },
doi = { 10.5120/17681-8524 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:30:52.856099+05:30
%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
%J International Journal of Computer Applications
%@ 0975-8887
%V 101
%N 5
%P 7-12
%D 2014
%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
  1. 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
  2. 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
  3. 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
  4. 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
  5. Adeel Abbas, Affan Ahmad, "Object Oriented Parallel Programming", IEEE, 2002, pp. 89-93
  6. 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
  7. Sequential and parallel sorting algorithms http://www. iti. fh-flensburg. de/lang/algorithmen/sortieren/algoen. htm
  8. LINUX MAGAZINE-MPI in Thirty Minutes http://www. linux-mag. com/id/5759/
  9. Message Passing Interface (MPI) Author: Blaise Barney, Lawrence Livermore National Laboratory
  10. R. S. RamPriya, M. A. Maffina, "A Secured and Authenticated Message Passing Interface for Distributed Clusters", SPSymposium, IIITD, 2013
  11. Wang Xiang, "Analysis of the Time Complexity of Quick Sort Algorithm", IEEE, 2011, pp. 408-410
  12. Keliang Zhang,"A Novel Parallel Approach of Radix Sort with Bucket Partition Preprocess", IEEE, 2012, pp. 989-994
Index Terms

Computer Science
Information Sciences

Keywords

MPI Parallel Programming Selection sort Bubble sort Quick sort Insertion Sort Shell Sort Bucket sort Sequential Programming.