并行計(jì)算中快速排序算法的改進(jìn)

1、并行計(jì)算中快速排序算法的改進(jìn)摘要：排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列 調(diào)整為“有序”的記錄序列。排序是計(jì)算機(jī)科學(xué)中最重要的研究問(wèn)題之一。本文先 從串行的快速排序講起，進(jìn)而過(guò)渡到并行的快速排序算法。串行算法的平均時(shí)間復(fù) 雜為O(nlogn),而并行算法的平均時(shí)間復(fù)雜度為0(21ogn),。但是當(dāng)數(shù)據(jù)量非常大 的時(shí)候，傳統(tǒng)的快速排序辦法理論可行，但實(shí)際上卻是不可行的。為此，本文提出 一種結(jié)合歸并排序的方法給出一種改進(jìn)的并行快速排序，得到一個(gè)可以用在待排序 的數(shù)據(jù)個(gè)數(shù)巨大時(shí)的實(shí)用的并行算法。關(guān)鍵詞：快速排序；歸并排序；串行算法；并行算法；時(shí)間復(fù)雜度1 .引言排序是計(jì)算

2、機(jī)科學(xué)中最重要的研究問(wèn)題之一。由于它的應(yīng)用廣泛和同行的理論上的重要 性，2000年它被列為對(duì)科學(xué)和工程計(jì)算的研窕與實(shí)踐影響最大的10大問(wèn)題之一口】。因此對(duì) 干排序的研究既有理論上的重要意義，又有實(shí)際應(yīng)用價(jià)值。它在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè) 汁、機(jī)器人、模式識(shí)別及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用基本的排序問(wèn)題是重排一個(gè)給定的 數(shù)據(jù)項(xiàng)集，使它按遞增(或遞減)排列。數(shù)據(jù)項(xiàng)可以是具有線性順序的任意對(duì)象。例如，在 典型商業(yè)數(shù)據(jù)處理應(yīng)用中數(shù)據(jù)項(xiàng)是記錄，每一個(gè)記錄都包含有一個(gè)稱為關(guān)鍵字的特殊標(biāo)識(shí)符 域，并且記錄是按關(guān)鍵字進(jìn)行排序。排序能夠大大簡(jiǎn)化查找或更新一個(gè)記錄的過(guò)程。到目前 為止，盡管研究人員已經(jīng)設(shè)計(jì)了多種排序算

3、法。但快速排序仍然是實(shí)際應(yīng)用中最常用的一種 排序算法。對(duì)它復(fù)雜度的分析方法和數(shù)據(jù)結(jié)構(gòu)的研究是研究許多應(yīng)用問(wèn)題的基礎(chǔ)?？焖倥判?中使用的分治策略是設(shè)計(jì)布.效計(jì)算幾何和組合問(wèn)題算法的典型設(shè)計(jì)方法。本文將探討并行計(jì) 算中快速排序的改進(jìn)。2 .快速排序簡(jiǎn)介快速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年 提出。它的基本思想是通過(guò)-趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的 所有數(shù)據(jù)都比另外一部分的所行數(shù)據(jù)都要小，然后再按此方法時(shí)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速 排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判蛩惴ㄊ抢梅种渭夹g(shù)的典

4、型例子。分治策略分為三步。首先將問(wèn)題分成若干大 小基本相等的子問(wèn)題；獨(dú)立地解決這些子問(wèn)題；最后將子問(wèn)題歸并成原問(wèn)題的解。因此方法 的有效性取決于對(duì)初始問(wèn)題劃分的過(guò)程和最后一步歸并解的過(guò)程。假設(shè)待排序的n個(gè)元素存儲(chǔ)在數(shù)組A0,n-l中?？焖倥判蛩惴ǖ母呒?jí)描述如下：(1)從數(shù)組A0,n-l中選取樞軸元素。(2)重排數(shù)組A中元素，并將其劃分成左右兩部分。使得數(shù)組中所有比樞軸元索小的元 素在左部分中，比它大的元素在右部分中。(3)對(duì)左、右部分進(jìn)行遞歸排序。如果先不看實(shí)現(xiàn)的細(xì)節(jié)和算法的正確性證明，不難看出算法使用了分治策略。在這種情 況卜:第一、二步相應(yīng)于劃分步，第三步求解歸約的子問(wèn)題，實(shí)現(xiàn)對(duì)整個(gè)數(shù)組的

5、排序，從而 無(wú)需歸并步驟。在快速排序算法的描述中，忽視了兩個(gè)關(guān)鍵的問(wèn)題：(1)選擇樞軸元素的方法；(2)如樞軸元素被選擇后，使用的劃分方法。由于本文主要探討快速算法的并行化，故采用簡(jiǎn)化的方法，直接選取數(shù)組的首個(gè)元素為 樞軸元素。3 .歸并排序艮一歸并排序內(nèi)(MERGESORT)是建立在此并操作上的一種有效的排序算法，該算法是采 用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列公井，得到完 全有序的序列：即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè) 有序表，稱為二路歸并。歸并排序具體工作原理如下(假設(shè)序列共有n個(gè)元素)：(1)將序列每相

6、鄰兩個(gè)數(shù)字進(jìn)行歸并操作(merge),形成floor(n/2)個(gè)序列，排序后每 個(gè)序列包含兩個(gè)元素，(2)將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素，(3)重復(fù)步驟(2),直到所有元素排序完畢。4 .并行算法中的快速排序并行計(jì)算是實(shí)現(xiàn)高性能計(jì)算的主要技術(shù)手段叫排序問(wèn)題是計(jì)算機(jī)科學(xué)中最重要的研究 問(wèn)題之一。對(duì)快速排序方法的研究表明，至今快速排序算法仍然是流傳久遠(yuǎn)的最實(shí)用的排序 算法。盡管在最壞情況"它的平均情況卜的時(shí)間復(fù)雜度相當(dāng)好巴 將串行的快速排序并行 化，必然能夠提高對(duì)數(shù)據(jù)處理的效率。4.1 PRAM-CRCW上快速排序算法執(zhí)行快排序可以看成是構(gòu)造一棵

7、二叉樹，其中主元是根，小于等于主元的元素處于左子 樹，大于主元的元素處于右子樹。算法首先從選第一個(gè)主元開始，它劃分原序列為兩個(gè)自序 列：然后相繼子序列中主元的選取則可并行執(zhí)行。當(dāng)這樣的二叉樹造好后，采用中序遍歷的 方法就可得到一個(gè)有序序列田。令待排序的序列為(A1,，An),處理器Pi保存元素Ai, LC i n和RC l:n 分別記錄給定主元的左孩子和右孩子，fi中存有其元素是主元的處理器號(hào)。開始時(shí)所有處 理器均將它們自己的處理器號(hào)寫入變量root, Aroot是第一個(gè)主元，并且root被復(fù)制給每 個(gè)處理器1的fi.然后那些其元素小于Afi的處理器將其號(hào)碼寫入LCH,而大于Afi的處理 器將

8、其號(hào)碼寫入RCfi。因此所有那些其元索屬于小序列的處理器便將其號(hào)碼寫入LCfi,而 所有那些其元素屈于大于序列的處理器便將其號(hào)碼寫入RCfi。但是閃為并發(fā)寫操作只有兩 個(gè)做一個(gè)對(duì)應(yīng)與LCfi,另一個(gè)對(duì)應(yīng)與RCfi)能被寫進(jìn)這些單元，所以這兩個(gè)值就變成了下 次迭代所需要的主元的處理器號(hào)。按此算法一直繼續(xù)到n個(gè)主元被選完。4.2 PRAM-CRCW上快速排序二叉樹構(gòu)造算法算法一：PRAM-CRCW上快速排序二叉樹構(gòu)造算法輸入：序列(Al,. ,An)和n個(gè)處理器 輸出：供排序用的一棵二叉排序樹 Begin(1) fbr each proceppori do(l.(1) ot = i(l.(2) f

9、i = root(1.(2) i = RCi = n+ 1endfor(2) repeat for each proceppono root do if (Ai <Afi) U (Ai = Afi A i < fi) then(2 l)LCfi = i(2 2) if i = LCfi then exit else if = LCfi end:felse(2 3) RCfi = i(2 4) if i = RCfi then exit else ft = RCfi end:fend:fend repeatEnd4.3 PRAM-CRCW上的快速排序二叉樹中序遍歷算法尊法一：PRAM

10、-CRCW上的快速排序二叉樹中序遍歷算法 輸入：AA1,，An和n個(gè)處理器，并且Aj保存在Pi的LM中 輸出：二叉排序樹 root, LC1 . n, RCl. n在 PM 中 Begin(3) for each Pi par-do(1.(1) ot = i(1.(2) fi = root(1.(3) i = RCi = n+ 1 endfor(4) repeat for each Pi <> root pai'-do if (Ai <Afi) U (Ai =Afi n i < fi) then(2.(1) fi = i(2.(2) if i = LCfi th

11、en exit else if=LCfi endif else(2 3) RCfi = i4 2.4) if i = RCfi then exit else fi = RCfi endif endifend repeat End在算法1中，可在0(1)時(shí)間內(nèi)構(gòu)造一級(jí)樹，而樹的高度為0(1。曲)，所以算法1的 時(shí)間更雜度為O(logn) o當(dāng)二叉樹構(gòu)造好以后，采用中序遍歷(算法2)就可以得到一個(gè)有 序序列，中序遍歷的時(shí)間復(fù)雜度為。(1。即)，所以并行排序算法的時(shí)間更雜度O(21ogn)， 要比串行的快速排序的時(shí)間復(fù)雜度(0(nlogn)小很彩。但是，在并行算法里要求處理器的 個(gè)數(shù)與序列中數(shù)據(jù)的個(gè)

12、數(shù)相同，在實(shí)際應(yīng)用中不可行，所以本文提出利用數(shù)據(jù)劃分方法先把 n(待排序的數(shù)據(jù)個(gè)數(shù))個(gè)數(shù)據(jù)進(jìn)行分段，把n個(gè)數(shù)據(jù)分為k段，即211年6為處理器的 個(gè)數(shù))，每一段有p個(gè)元素，其次在用快排序算法的思想把每一組數(shù)據(jù)進(jìn)行排序，最后在 用歸并排序算法把P組數(shù)據(jù)進(jìn)行歸并排序，這樣就可以解決當(dāng)n遠(yuǎn)遠(yuǎn)大于p時(shí)，快排序并 行算法要求待排序數(shù)據(jù)個(gè)數(shù)與處理器臺(tái)數(shù)相同但是在實(shí)際應(yīng)用中不可行問(wèn)題。5 .歸并排序與快排序相結(jié)合的改進(jìn)算法該算法的基本思想是：把n個(gè)數(shù)據(jù)分為k段，即k=n/p(p為處理器的個(gè)數(shù))，每一段 布.p個(gè)元素，其次在用快排序算法的思想把每一組數(shù)據(jù)進(jìn)行排序，最后在用歸并排序算法 把P組數(shù)據(jù)進(jìn)行歸并排序，這

13、樣就可以解決當(dāng)n遠(yuǎn)遠(yuǎn)大于p時(shí)，快排序并行算法要求待排 序數(shù)據(jù)個(gè)數(shù)與處理器臺(tái)數(shù)相同但是在實(shí)際應(yīng)用中不可行問(wèn)題圓。輸入：長(zhǎng)度為n的無(wú)序序列，有p個(gè)處理器，把n分為n/p=k段，每段有k(p=n 灰)個(gè)數(shù)據(jù)，每段數(shù)據(jù)有p(p=n/k)臺(tái)處理器，每臺(tái)處理器有一個(gè)數(shù)據(jù)。輸出：長(zhǎng)度為n的有序序列。Begin(1)均勻劃分：并行處理器有p個(gè)處理器，n個(gè)元素劃分成k(n/p=k)段，每一段有 p(p=n/k)個(gè)元素，即一臺(tái)處理器上有一個(gè)元素。(2)局部排序：每一段上的p個(gè)處理器對(duì)p個(gè)兀索進(jìn)行快速排序，得到k段有序序列， 用kl, k2, k3kk表示。第kl段處理器的編號(hào)為pll» p12. p13

14、.pip；第k2段 的處理器編號(hào)為p21» p22» p23 p2p.第kk段處理.器編號(hào)為pkl, pk2, pk3.pkp, 每一段的數(shù)據(jù)保存在與段號(hào)與處理器編號(hào)相同的處理器上。比如，第kl段數(shù)據(jù)就保存 在第pH個(gè)處理器，第k2段數(shù)據(jù)保存在第p22個(gè)處理器上，第kk段數(shù)據(jù)保存在第pkk 個(gè)處理器上。這樣就有k個(gè)處理器保存了 k段數(shù)據(jù)，用第一個(gè)處理器和第2個(gè)處理器 進(jìn)行比較排序，第三個(gè)和第四個(gè)進(jìn)行比較，依次類推，在用第1和第2個(gè)處理器比較 得到的有序序列和第3和第4個(gè)處理器比較得到的有序序列進(jìn)行比較，最后得到一個(gè) 具有個(gè)n數(shù)據(jù)的有序序列。當(dāng)k剛好是2的倍數(shù)時(shí)如圖1所示。當(dāng)

15、k不是2的倍數(shù) 時(shí)如圖2所示。End圖1 k剛好是2的倍數(shù)圖2 k不是2的倍數(shù)在這里分兩種情況，當(dāng)k« p時(shí)，就按照本文圖2進(jìn)行排序。當(dāng)k> p時(shí)，把k進(jìn)行分組， 用k/p» s(向上取整)，每個(gè)處理器放S段數(shù)據(jù)，當(dāng)S是2的倍數(shù)時(shí)，如圖1進(jìn)行比較，s 不是2的倍數(shù)時(shí)，如圖2進(jìn)行比較，最后得到一個(gè)具有n個(gè)數(shù)據(jù)的有序序列。6 .基于群集系統(tǒng)的快速排序的并行化方法工作站群集cow叨0Cluster Of Workstations)又稱工作站網(wǎng)絡(luò)或PC群集(PC Cluster) 是實(shí)現(xiàn)并行計(jì)算的一種新的主流技術(shù)#是一種并行或分布處理系統(tǒng)。它是基于消息傳遞的、 分布式存儲(chǔ)的N

16、IMD并行計(jì)算機(jī)結(jié)構(gòu)，由一組互連的單機(jī)組成，可分為計(jì)算機(jī)節(jié)點(diǎn)和互連 網(wǎng)絡(luò)兩部分。MPI (Message Passing Interface) 口加力是消息傳遞并行編程模型的標(biāo)準(zhǔn)，它具有可移植 性、易用性、完備的異步通信功能、正式詳細(xì)的精確定義等特點(diǎn)及?；贛PI編程就是用 標(biāo)準(zhǔn)串行語(yǔ)言(C語(yǔ)言或者Fortran語(yǔ)言)書寫的代碼，加上用于消息接受和發(fā)送的庫(kù)函數(shù) 調(diào)用組成的，其計(jì)算其實(shí)是由一個(gè)或多個(gè)彼此通過(guò)調(diào)用庫(kù)函數(shù)進(jìn)行消息收、發(fā)的進(jìn)程所組成。最簡(jiǎn)單的并行化方法是以一個(gè)進(jìn)程為開始，根據(jù)選取的樞軸把該進(jìn)程劃分成兩個(gè)進(jìn)程, 選取新的樞軸，用遞歸的方法把待排序列劃分給若干進(jìn)程，形成二叉樹。每個(gè)進(jìn)程由一

17、個(gè)節(jié) 點(diǎn)負(fù)貨排序，然后最終把結(jié)果返回到主節(jié)點(diǎn)#從而完成整個(gè)數(shù)列的排序。偽代碼如下：void main (intargc, char *argvMPI_Init(&argc, &argv),MPI_C omm_rank(MPI_CORLD, &my_rank),MPI_comm_size(N£PI_COhlhI_WORLD, &p),randsortO,sort。total-1, p, 0),if(my_rank = 0)flag=l,for(i = 0, i< p, i+)hlPI_Send(&flag, l,hlPI_INT, i, n

18、g, h4PI_COMhf_WORLD),elseMPI_Recv(&flag, 1, MPI_INT, 0, ng, MPI_C0MM_W0RLD, &status),)MPI_FinalizeO；)7 .總結(jié)和展望并行快速排序是一種典型的并行排序算法，但是，當(dāng)待排序數(shù)據(jù)個(gè)數(shù)巨大時(shí)，在并行算 法中需要N臺(tái)處理器，在實(shí)際應(yīng)用中不具備可行性。論文提出的算法解決了并行算法中快 速排序的N值問(wèn)題，但是還存在許多問(wèn)題，希望通過(guò)補(bǔ)充更多的算例，豐富、完善乃至開 拓出更新更好的方法。參考文獻(xiàn)：1 J Dongaira The Top 100 Algorithms IEEE Computing in Science & Engineering, 2000, 2(1):22-232 T H Coimen, C E Leiserson, R L Rivest Introduct