Study of Performance Evaluation of Binary Search on Merge Sorted Array Using Different Strategies

Full Text (PDF, 462KB), PP.1-8

Views: 0 Downloads: 0

Author(s)

Sherin W. Hijazi 1,* Mohammad Qatawneh 1

1. University of Jordan, Amman, Jordan

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2017.12.01

Received: 12 Oct. 2017 / Revised: 28 Oct. 2017 / Accepted: 8 Nov. 2017 / Published: 8 Dec. 2017

Index Terms

Binary search, Merge Sort, Parallel, Multithread, P-thread, MPI, Supercomputer

Abstract

Search algorithm, is an efficient algorithm, which performs an important task that locates specific data among a collection of data. Often, the difference among search algorithms is the speed, and the key is to use the appropriate algorithm for the data set. Binary search is the best and fastest search algorithm that works on the principle of ‘divide and conquer’. However, it needs the data collection to be in sorted form, to work properly. In this paper, we study the efficiency of binary search, in terms of execution time and speed up, by evaluating the performance improvement of the combined search algorithms, which are sorted into three different strategies: sequential, multithread, and parallel using message passing interface. The experimental code is written in ‘C language’ and applied on an IMAN1 supercomputer system. The experimental results show that the decision variables are generated from the IMAN1 supercomputer system, which is the most efficient. It varied for the three different strategies, which applies binary search algorithm on merge sort. The improvement in performance evaluation gained by using parallel code, greatly depends on the size of data set used, and the number of processors that the speed-up of the parallel codes on 2, 4, 8, 16, 32, 64, 128, and 143 processors is best executed, using between a 50,000 and 500,000 dataset size, respectively. Moreover, on a large number of processors, parallel code achieves the best speed-up to a maximum of 2.72.

Cite This Paper

Sherin W. Hijazi, Mohammad Qatawneh, "Study of Performance Evaluation of Binary Search on Merge Sorted Array Using Different Strategies", International Journal of Modern Education and Computer Science(IJMECS), Vol.9, No.12, pp. 1-8, 2017. DOI:10.5815/ijmecs.2017.12.01

Reference

[1]A. El-Nashar. “2011”. Parallel Performance of MPI Sorting Algorithms On Dual–Core Processor Windows-Based Systems. International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.3, May 2011
[2]A. Madsen, F. Jensen, A. Salmeron, H. Langseth and Th. Nielsen. “2017”. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge base system, 117(2017) 46-55 Elsevier.
[3]A. Singh, Monika, Vandana and S. Kaur. “2011”. Assortment of Different Sorting Algorithms. Asian Journal of Computer Science and Information Technology, ISSN 2249- 5126.
[4]D. Penas, P. Gonzalez, J. Egea, J. Banga and R. Doallo. “2015”. Parallel metaheuristics in computational biology: an asynchronous cooperative enhanced Scatter Search method. ICCS 2015 International Conference On Computational Science, Volume 51, 2015, Pages 630-639, Elsevier.
[5]M. Geiger. “2017”. A multithread local search algorithm and computer implementation for the multimode, resource- constrained multi-project scheduling problem. European Journal of Operation Research. 0377-2217/@ 2016 Elesvier B.V.
[6]M. Saadeh, H. Saadeh and M. Qatawneh. “2016”. Performance Evaluation of Parallel Sorting Algorithms on IMAN1 Supercomputer. International Journal of Advanced Science and Technology Vol.95 (2016), pp.57-72
[7]M. Dawra, and Priti. “2012”. Parallel Implementation of Sorting Algorithms. IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 4, No 3, July 2012 ISSN (Online): 1694-0814.
[8]M Rajasekhara Babu, M Khalid, Sachin Soni, Sunil Chowdari Babu, Mahesh. “2011”. Performance Analysis of Counting Sort Algorithm using various Parallel Programming Models. International Journal of Computer Science and Information Technologies, Vol. 2 (5) , 2011, 2284-2287.
[9]Mustafa B. and Waseem Ahmed. Parallel Algorithm Performance Analysis using OpenMP for Multicore Machines. International Journal of Advanced Computer Technology (IJACT), VOLUME 4, NUMBER 5, ISSN:2319-7900.
[10]Olabiyisi S.O, Aladesae T.S. , Oyeyinka F.I. , and Oladipo Oluwasegun. “2013”. Evaluation of Critical Factors Affecting The Efficiency of Searching Techniques. International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 7, July 2013, ISSN: 2277 128X.
[11]P. Kulkarni and S. Pathare. “2014”. Performance Analysis of Parallel Algorithm over Sequential using OpenMP. IOSR Journal of Computer Engineering (IOSR-JCE) e-ISSN: 2278-0661, p- ISSN: 2278-8727Volume 16, Issue 2, Ver. X (Mar-Apr. 2014), PP 58-62.
[12]R. Banos, J. Ortega, C. Gil, F. de Toro and M. Montoya. “2016”. Analysis of OpenMP andMPI implementations of meta-heuristics for vehicle routing problems. Applied Soft Computing, 1568-4946/@2016 Elesvier B.V.
[13]Sh. Kathavate1 and N.K. Srinath. “2014”. Efficiency of Parallel Algorithms on Multi Core Systems Using OpenMP. International Journal of Advanced Research in Computer and Communication Engineering Vol. 3, Issue 10, October 2014.
[14]S. K. Sharma and K. Gupta. “2012”. Performance Analysis of Parallel Algorithms on Multi-core System using OpenMP. International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol.2, No.5, October 2012.
[15]Venkata Siva Prasad Ch., Ravi S. and Karthikeyan V. “2015”. Performance Improvement in Data Searching and Sorting Using Multi-Core. ARPN Journal of Engineering and Applied Sciences, VOL. 10, NO. 16, SEPTEMBER 2015, ISSN 1819-6608.
[16]Azzam Sleit, Wesam AlMobaideen, Mohammad Qatawneh, Heba Saadeh.”2008”. Efficient Processing for Binary Submatrix Matching. American Journal of Applied Sciences 6 (1): 78-88, 2008, ISSN 1546-9239.
[17]Mohammad Qatawneh, Azzam Sleit, Wesam Almobaideen. “2009”. Parallel Implementation of Polygon Clipping Using Transputer. American Journal of Applied Sciences 6 (2): 214-218, 2009. ISSN 1546-9239.
[18]Mohammad Qatawneh. “2011”.Multilayer Hex-Cells: A New Class of Hex-Cell Interconnection Networks for Massively Parallel Systems. Int. J. Communications, Network and System Sciences, 2011, 4, 704-708.
[19]Mais Haj Qasem, Mohammad Qatawneh. “2017”. Parallel Matrix Multiplication for Business Applications. Proceedings of the Computational Methods in Systems and Software. 201, 24-36.
[20]http://www.iman1.jo/iman1/index.php/about#.(Accessed on 03-01-2017)
[21]https://en.wikipedia.org/wiki/Binary_search_algorithm. (Accessed on 03-01- 2017).
[22]https://en.wikipedia.org/wiki/Merge_sort. (Accessed on 03-01- 2017).
[23]http://penguin.ewu.edu/~trolfe/ParallelMerge/ParallelMerge.html. (Accessed on 03-09- 2017)
[24]https://en.wikipedia.org/wiki/POSIX_Threads. (Accessed on 03-09- 2017)