Abstract:

In order to solve the traditional recursively merge sort algorithm serial execution efficiency of general problems, we used data dependence analysis methods on recursive merge sort algorithm parallelism analysis. The analysis shows that the algorithm itself has the characteristics of parallel, and multi-core processors can be used to compile OpenMp direct guidance statement on parallel processing algorithms. In case of large amount of data, use multiple threads in a multi processor system, divide the sequence into several groups and set each thread operation of a group of data in order to make the algorithm performs faster. Finally, the research merged a plurality of partial results which were ordered. Experiment result shows that this method of parallel algorithm can improve the speed of execution of the algorithm.

Key words: merge sort, multicore and multithread, OpenMp, data dependence, parallelization