基于多線程歸并排序算法設(shè)計(jì)

孫琳琳，侯秀萍，朱 波，孫士明，高 燦

(1.長(zhǎng)春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，長(zhǎng)春130012;2.蘇州大學(xué)附屬第一醫(yī)院，江蘇蘇州215006)

0 引言

近年來(lái)，處理器的發(fā)展已經(jīng)由單核處理器轉(zhuǎn)為多核處理器，由單一主頻的提高轉(zhuǎn)為由多個(gè)處理核心進(jìn)行并行計(jì)算提高計(jì)算性能［1］。雖然多核處理器已經(jīng)成為主要發(fā)展趨勢(shì)，但傳統(tǒng)的串行程序并不能在多核處理器結(jié)構(gòu)下獲得性能的提升。為了使串行程序能有效利用多核處理器硬件方面的優(yōu)勢(shì)，需要對(duì)串行程序進(jìn)行并行化處理。目前比較流行的并行編程模型OpenMp，通過(guò)在源程序代碼中添加編譯制導(dǎo)語(yǔ)句，編譯器識(shí)別這種標(biāo)識(shí)會(huì)自動(dòng)創(chuàng)建線程對(duì)程序進(jìn)行并行化。同時(shí)在多核處理器系統(tǒng)中，多個(gè)線程可以同時(shí)在不同的處理核心上運(yùn)行，以達(dá)到真正并行的效果，從而有效提高程序的效率［2］。

排序是處理數(shù)據(jù)過(guò)程中常用的運(yùn)算，因此，提升排序算法的執(zhí)行效率具有重要的現(xiàn)實(shí)意義。歸并算法作為排序算法中比較穩(wěn)定的算法，已經(jīng)有很多學(xué)者對(duì)其進(jìn)行研究，但大多數(shù)的研究都是基于串行程序的改進(jìn)，如姜忠華等［3］提出了根據(jù)數(shù)據(jù)本身具有的規(guī)律對(duì)待排序列進(jìn)行智能歸并排序的劃分方法。白宇等［4］基于分治策略，使用深度優(yōu)先的方法，提出了一種用于線性表的穩(wěn)定原地歸并排序算法，算法在時(shí)間復(fù)雜度和空間復(fù)雜度以及排序穩(wěn)定性上達(dá)到了較好的平衡。筆者采用OpenMp編譯制導(dǎo)語(yǔ)句在多核處理器下使用多線程完成對(duì)數(shù)據(jù)的排序。……