基于雙核系統(tǒng)的快速排序效率分析

摘要：隨著多核技術(shù)的不斷發(fā)展，多核CPU已經(jīng)成為處理器市場(chǎng)的主流。如何充分利用多核的優(yōu)勢(shì)提高應(yīng)用程序的性能是開發(fā)人員不得不面對(duì)的課題。多核系統(tǒng)為開發(fā)人員提供了一個(gè)實(shí)現(xiàn)并行計(jì)算的重要平臺(tái)。文中探討了基于雙核系統(tǒng)的快速排序的效率，介紹了C#線程編程的相關(guān)知識(shí)，并在此基礎(chǔ)上實(shí)現(xiàn)了基于雙核系統(tǒng)的多線程的快速排序算法，實(shí)驗(yàn)結(jié)果表明該算法較傳統(tǒng)快速排序算法而言，算法執(zhí)行效率得到了很大的提升。

關(guān)鍵詞：多核編程；并行計(jì)算；多線程；快速排序

中圖分類號(hào)：TP332文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)22-705-03

The Efficiency Analysis of the Quick Sort Based On The Dual-core Systems

ZHANG Huo-lin， LI Guo-qing， ZHANG Jiang-wei

(Xuchang University，Xuchang 461000，China)

Abstract: With the rapid development of multi-core technology， the multi-core CPU processors have become the mainstream of CPU market. how to make full use of the advantages of multi-core to improve the performance of the application has become a new issue that the developers have to face. Multi-core system provide an important paltform of parallel computing developers. In this paper，we discussed the efficiency of the quick sort based on the dual-core systems， introduced the C # thread programming， and based on this we developped the multi-threading version of the quick sort algorithm based on the dual-core system， the results showed that the efficiency of new algorithm has been greatly improved compared with the sequence.

Key words: multi-core programming; parallel computing; multi-threading; quick sort

1 引言

在現(xiàn)有生產(chǎn)工藝條件下，CPU主頻升級(jí)之路已經(jīng)走到了拐點(diǎn)。桌面的主頻在2000年達(dá)到了1GHz，2001年達(dá)到2GHz，2002年達(dá)到了3GHz。但至今仍然沒有看到4GHz處理器的出現(xiàn)，電壓和發(fā)熱量成為最主要的障礙。Intel和AMD開始尋找其它方式提升處理器的能效，而最具實(shí)際意義的方式是增加CPU內(nèi)處理核心的數(shù)量。多核時(shí)代開創(chuàng)于2005年春季，其標(biāo)志是Intel的Pentium D處理器800系列的發(fā)布。近兩年來隨著Intel和AMD雙核、四核CPU的陸續(xù)推出，由于其優(yōu)良的性價(jià)比，多核處理器已經(jīng)成為處理器市場(chǎng)的主流。

多核時(shí)代的到來，給傳統(tǒng)的基于單核的編程思想帶來了巨大的沖擊。常見的串行程序在單核CPU上是順序執(zhí)行的，在多核系統(tǒng)上運(yùn)行只能利用其中的一個(gè)核心，因此不能獲得性能的提升。為了能夠充分地利用多核CPU的性能，程序開發(fā)員必須學(xué)習(xí)新的程序設(shè)計(jì)模式。在新的設(shè)計(jì)模式中，軟件開發(fā)人員面臨的任務(wù)就是如何充分利用多核，避免性能閑置。對(duì)應(yīng)用程序可以并行的部分線程化，并將這些線程有效地分配到不同的內(nèi)核中去，多個(gè)核心同時(shí)執(zhí)行，軟件的性能與效率必將得到大幅的提升。

目前有多種可選擇的多核多線程開發(fā)工具。相對(duì)于C/C++/Fortran等編譯型語(yǔ)言，C#/java/Python等新型語(yǔ)言也許是更好的選擇[1]。原因C#/java/Python等語(yǔ)言一般都提供了對(duì)多線程的原生支持；如C#的System.Threading.Thread、Java的java.lang.Thread及Python的Threading.Thread。相形之下，編譯型語(yǔ)言往往都是通過平臺(tái)相關(guān)的庫(kù)來提供多線程支持，如Win32 SDK、POSIX threads等，由于沒有統(tǒng)一的標(biāo)準(zhǔn)，造成使用C/C++編寫多線程程序需要考慮更多的細(xì)節(jié)，提高了項(xiàng)目成本。

2 C#多線程簡(jiǎn)介

2.1 線程簡(jiǎn)述

線程可以被描述為一個(gè)微進(jìn)程，它擁有起點(diǎn)，執(zhí)行的順序系列和一個(gè)終點(diǎn)。它負(fù)責(zé)維護(hù)自己的堆棧，這些堆棧用于異常處理，優(yōu)先級(jí)調(diào)度和其他一些系統(tǒng)重新恢復(fù)線程執(zhí)行時(shí)需要的信息[2，4]。從這個(gè)概念看來，好像線程與進(jìn)程沒有任何的區(qū)別，實(shí)際上線程與進(jìn)程之間區(qū)別在于：一個(gè)完整的進(jìn)程擁有自己獨(dú)立的內(nèi)存空間和數(shù)據(jù)，但是同一個(gè)進(jìn)程內(nèi)的線程是共享內(nèi)存空間和數(shù)據(jù)的。一個(gè)進(jìn)程對(duì)應(yīng)著一段程序，它是由一些在同一個(gè)程序里面獨(dú)立的同時(shí)的運(yùn)行的線程組成的。

線程有時(shí)也被稱為并行運(yùn)行在程序里的輕量級(jí)進(jìn)程，并且大多數(shù)現(xiàn)代操作系統(tǒng)把線程作為時(shí)序調(diào)度的基本單元。在沒有明確協(xié)調(diào)的情況下，線程相互同或異步地執(zhí)行。因?yàn)榫€程共享其所屬進(jìn)程的內(nèi)存地址空間，因此所有同一進(jìn)程中的線程訪問相同的變量，并從同一個(gè)堆中分配對(duì)象，這相對(duì)于進(jìn)程間通信機(jī)制而言實(shí)現(xiàn)了良好的數(shù)據(jù)共享，但同時(shí)也會(huì)產(chǎn)生意外的后果。C#對(duì)多線程提供語(yǔ)言和類庫(kù)級(jí)的支持，簡(jiǎn)化了并行的多線程應(yīng)用程序的開發(fā)。

2.2 C#多線程狀態(tài)及狀態(tài)之間的轉(zhuǎn)換過程

System.Threading.ThreadState枚舉指定Thread的執(zhí)行狀態(tài)，此枚舉有一個(gè)FlagsAttribute屬性，允許其成員值按位組合。下面是ThreadState定義的枚舉常數(shù)[3]。

表1 ThreadState定義的枚舉常數(shù)

■

Thread對(duì)象的ThreadState屬性提供一個(gè)由ThreadState定義的位掩碼，它指示線程的當(dāng)前狀態(tài)。一個(gè)線程至少總是處于ThreadState枚舉中定義的一個(gè)可能狀態(tài)，并且可以同時(shí)處于多個(gè)狀態(tài)。注意，只能在一些調(diào)試方案中使用線程狀態(tài)，而不應(yīng)該在代碼中使用線程狀態(tài)來同步線程活動(dòng)。在創(chuàng)建托管線程時(shí)，該線程處于Unstarted狀態(tài)。線程會(huì)保持Unstarted狀態(tài)，直到被操作系統(tǒng)調(diào)度到已啟動(dòng)狀態(tài)。調(diào)用Start方法使操作系統(tǒng)知道該線程可啟動(dòng)，但是它并不直接更改線程的狀態(tài)。一旦線程處于已啟動(dòng)的狀態(tài)中，就可以執(zhí)行許多操作來使線程更改狀態(tài)。表2列出了使?fàn)顟B(tài)發(fā)生更改的操作，以及相應(yīng)的新狀態(tài)。

表2 使線程狀態(tài)發(fā)生更改的操作及相應(yīng)的新狀態(tài)

■

在任何時(shí)間內(nèi)，線程通常都處于多個(gè)狀態(tài)中。例如，如果當(dāng)某個(gè)線程因調(diào)用Monitor.Wait方法而被阻止時(shí)，另一個(gè)線程調(diào)用該線程的Abort方法，那么該線程將同時(shí)處于WaitSleepJoin和AbortRequested狀態(tài)。在這種情況下，一旦該線程從對(duì)Wait方法的調(diào)用中返回或被中斷，它就會(huì)收到ThreadAbortException異常。

一旦線程因調(diào)用Start方法而離開Unstarted狀態(tài)，它就無法再返回到Unstarted狀態(tài)。同樣，線程也永遠(yuǎn)無法從Stopped狀態(tài)轉(zhuǎn)移到其他狀態(tài)。

Thread類還有兩個(gè)屬性值與線程的狀態(tài)相關(guān)，即IsAlive和IsBackground。IsAlive是只讀屬性，說明線程是否已經(jīng)啟動(dòng)并且沒有結(jié)束。IsBackground用于了解線程是否是后臺(tái)線程，以及將線程設(shè)置為后臺(tái)或者前臺(tái)線程。如果IsBackground為true，則說明線程是后臺(tái)線程，Thread對(duì)象的ThreadState值包含Background。否則，線程為前臺(tái)臺(tái)進(jìn)程，Thread對(duì)象的ThreadState值不包含Background。托管線程不是后臺(tái)線程，就是前臺(tái)線程。后臺(tái)線程不會(huì)使托管執(zhí)行環(huán)境處于運(yùn)行狀態(tài)，除此之外，后臺(tái)線程與前臺(tái)線程是一樣的。一旦所有前臺(tái)線程在托管進(jìn)程中被停止，系統(tǒng)將停止所有后臺(tái)線程并關(guān)閉。直到所有前臺(tái)線程都終止了，應(yīng)用程序才會(huì)結(jié)束。當(dāng)應(yīng)用程序結(jié)束時(shí)，所有的后臺(tái)線程也會(huì)自動(dòng)終止。通過將IsBackground設(shè)置為true，可以將線程設(shè)置為后臺(tái)線程；通過將IsBackground設(shè)置為1，可以將線程設(shè)置為前臺(tái)線程。

3 基于雙核系統(tǒng)的快速排序

3.1 傳統(tǒng)的快速排序算法

快速排序算法由C.R.A.Hoare于1962年首次提出。對(duì)快速排序方法的研究表明，至今快速排序算法仍然是流傳久遠(yuǎn)的最實(shí)用的排序算法。只在輸入數(shù)據(jù)項(xiàng)有更詳細(xì)的信息時(shí)，其它排序算法才可能勝過快速排序算法。

快速排序的基本思想是：選取一個(gè)劃分基準(zhǔn)將待排序序列分為兩個(gè)子序列，一個(gè)子序列所有元素小于這個(gè)標(biāo)準(zhǔn)，另一個(gè)子序列大于這個(gè)標(biāo)準(zhǔn)。不斷進(jìn)行這樣的劃分，最后構(gòu)成n個(gè)子序列，此時(shí)，它們已經(jīng)按照遞增順序排列，算法結(jié)束[5]。下面是快速排序算法代碼。

快速排序算法：

輸入：數(shù)組list，數(shù)組起始位置low，結(jié)束位置high

輸出：按遞增順序排列的數(shù)組list[]

public void myQuickSort(int[] list， int low， int high)

{

if (low < high)

{

int pivot = Partition(list， low， high); // Partition返回樞紐元素的數(shù)組下標(biāo)

myQuickSort(list， low， pivot - 1); //對(duì)左半段快速排序

myQuickSort(list， pivot + 1， high);//對(duì)右半段快速排序

} }

上述算法中的Partition函數(shù)，將數(shù)組list[low，high]劃分為小于基準(zhǔn)list[low]的list[low，pivot]與大于基準(zhǔn)的list[pivot+1，high]兩個(gè)子序列。

快速排序算法是利用分治技術(shù)的典型例子，隨機(jī)分治策略是設(shè)計(jì)組合優(yōu)化與計(jì)算幾何一類問題有效算法的基礎(chǔ)[6]。分治策略分為三步：

1)將問題分成若干大小基本相等的子問題；

2)獨(dú)立地解決這些子問題；

3)將子問題歸并成原問題的解。

由分治技術(shù)設(shè)計(jì)思想可知，在多核系統(tǒng)上，分解而成的各個(gè)子問題可以并行求解，問題的求解效率必然得到大幅提升。因此，相較于單核系統(tǒng)，多核系統(tǒng)具有天然的優(yōu)勢(shì)。

3.2 基于雙核系統(tǒng)的快速排序

傳統(tǒng)快速排序在多核系統(tǒng)如何才能獲得較好的性能，一個(gè)直接的思路是：將待排序序列劃分為大小基本相等的子序列，由多個(gè)線程分別在各個(gè)核心上并行執(zhí)行快速排序，排序完后再使用歸并算法將排好的幾個(gè)子序列歸并成一個(gè)遞增有序序列。實(shí)驗(yàn)環(huán)境雙核Dell系統(tǒng)，2個(gè)線程并行排序的代碼如下：

threadPara threadPara1 = new threadPara(list1，low，high);//定義類threadPara的實(shí)例

threadPara threadPara1 = new threadPara(list2，low，high);//定義類threadPara的實(shí)例

Thread Thread1 = new Thread(new ThreadStart(threadPara1.doSort)); //定義線程1及其執(zhí)行方法

Thread Thread2 = new Thread(new ThreadStart(threadPara2.doSort)); //定義線程2及其執(zhí)行方法

Thread1.Start(); //線程1開始執(zhí)行

Thread1.Start(); //線程2開始執(zhí)行

Thread1.Join(); //線程1完成返回主線程

Thread1.Join(); //線程1完成返回主線程

Merge(list1， list2， resultArray1); //歸并已排好序的子序列

將待排序序列分為大小相等的兩個(gè)子序列l(wèi)ist1、list2，Thread1、Thread2的入口方法doSort調(diào)用myQuickSort分別進(jìn)行快速排序，myQuickSort的參數(shù)在定義threadPara1、threadPara2時(shí)由類threadPara的構(gòu)造函數(shù)傳入，子線程完成后返回主線程，調(diào)用靜態(tài)函數(shù)Merge進(jìn)行歸并排序得到最終序列resultArray1。

3.3 基于雙核系統(tǒng)的快速排序效率分析

為了試驗(yàn)一下多核CPU上排序算法的效率，比較單任務(wù)串行算法和多任務(wù)并行算法的差距，我們測(cè)試了在1線程、2線程、4線程條件下，對(duì)1，000，000個(gè)隨機(jī)整數(shù)進(jìn)行快速排序算法所花的時(shí)間。

實(shí)驗(yàn)平臺(tái)為Dell Latitude D630系列雙核筆記本電腦。采用Intel 965GM芯片組，Intel Core 2 Duo 2.0G，高速緩存2MB，前端總線800MHz，內(nèi)存DDR2 SDRAM 2G。操作系統(tǒng)Microsoft Windows XP Professional 5. 1. 2600(WinXP Retail )，編譯器為Microsoft Visual Studio2005。

表3 算法在三種情況下10次運(yùn)行時(shí)間

■

實(shí)驗(yàn)結(jié)果表明，對(duì)相同的1，000，000個(gè)隨機(jī)整數(shù)排序，單線程需要342ms，2線程需要202ms，4線程需要223ms。與單線程排序相比較，多線程并行快速排序算法效率有了很大的提高，2線程運(yùn)行速度比單線程提高了近69%。由于4線程分配到2個(gè)核心，存在著線程的上下文切換，因此在雙核平臺(tái)2線程排序要優(yōu)于4線程。

4 結(jié)束語(yǔ)

多核技術(shù)的發(fā)展必將引領(lǐng)軟件研發(fā)發(fā)生基礎(chǔ)性變化，特別對(duì)那些面向一般應(yīng)用、運(yùn)行在PC 和低端服務(wù)器上的應(yīng)用軟件更有非同一般的意義[7]。多核平臺(tái)為開發(fā)人員提供了一種優(yōu)化應(yīng)用程序的渠道，那就是通過仔細(xì)分配加載到各線程（或者各處理器核）上的工作負(fù)載（也就是實(shí)現(xiàn)各線程的負(fù)載均衡）就能夠得到性能上的提升。并且，開發(fā)人員也可以對(duì)應(yīng)用程序代碼加以優(yōu)化，使其能夠更加充分地使用多個(gè)處理器資源，進(jìn)而達(dá)到提升應(yīng)用程序性能的目的[2]。但是，多線程也存在它的不足，線程的使用（濫用）會(huì)給系統(tǒng)帶來上下文切換（Context switches）的額外負(fù)擔(dān)，并且避免線程間共享數(shù)據(jù)的競(jìng)爭(zhēng)而采取的同步機(jī)制，也會(huì)影響其運(yùn)行效率[8]。

參考文獻(xiàn)：

[1] 賴勇浩.積極準(zhǔn)備、謹(jǐn)慎行動(dòng)——應(yīng)對(duì)多核編程革命[J].程序員，2007(4):65-67.

[2] Akhter S.， Roberts J.多核程序設(shè)計(jì)技術(shù):通過軟件多線提升性能[M].北京:電子工業(yè)出版社，2007.

[3] Nagel C.， Evjen B.， Glynn J.， et al.C#高級(jí)編程[M].4版.北京:清華大學(xué)出版社，2006.

[4] 多核系列教材編寫組.多核程序設(shè)計(jì)[M].北京:清華大學(xué)出版社，2007.

[5] Cormen T H.， Leiserson C E.，et al. 算法導(dǎo)論[M].2版.北京:機(jī)械工業(yè)出版社，2006.

[6] 鄭宗漢，鄭曉明.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社，2007.

[7] 蔡佳佳，李名世，鄭鋒.多核微機(jī)基于OpenMP的并行計(jì)算[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007(10):87-91.

[8] Goetz B.，Peierls T.， Bloch J.，et al.JAVA并發(fā)編程實(shí)踐[M].北京:電子工業(yè)出版社，2007.