并行算法綜述

摘 要：本文主要對(duì)并行算法的概念、設(shè)計(jì)等進(jìn)行綜述。首先概要的介紹有關(guān)并行算法的相關(guān)概念，接著詳細(xì)的介紹并行算法的設(shè)計(jì)策略、設(shè)計(jì)方法等，最后對(duì)并行算法的前景做簡(jiǎn)單的分析討論，并做總結(jié)。

關(guān)鍵詞：并行算法；算法設(shè)計(jì)；設(shè)計(jì)策略；設(shè)計(jì)方法

中圖分類號(hào)：TP393

隨著計(jì)算機(jī)時(shí)代的到來，計(jì)算機(jī)的應(yīng)用和開發(fā)主要延伸到社會(huì)的各個(gè)領(lǐng)域，無論是國(guó)家的經(jīng)濟(jì)科技還是生活教育等，都能看到計(jì)算機(jī)的身影。而高性能計(jì)算機(jī)的研究和開發(fā)更能直接體現(xiàn)出一個(gè)國(guó)家的經(jīng)濟(jì)科技水平，同時(shí)由于信息化國(guó)防建設(shè)也使得高性能計(jì)算機(jī)成為國(guó)防安全的寵兒。世界各國(guó)都在努力爭(zhēng)奪高性能計(jì)算機(jī)的戰(zhàn)略制高點(diǎn)，這也充分說明高性能計(jì)算機(jī)對(duì)于一個(gè)國(guó)家科技實(shí)力的重要性。計(jì)算機(jī)的發(fā)展迅速，從最初的電子管到現(xiàn)在大規(guī)模繼承電路技術(shù)的應(yīng)用，計(jì)算機(jī)的運(yùn)算速度更快，功能也更加強(qiáng)大。當(dāng)然，其關(guān)鍵因素就是并行算法，并行算法直接決定著計(jì)算機(jī)性能的高低，同時(shí)并行算法的發(fā)展程度也相當(dāng)明顯的顯示出國(guó)家計(jì)算機(jī)科技水平的發(fā)達(dá)程度，是國(guó)家綜合國(guó)力的一個(gè)體現(xiàn)。

1 并行算法

1.1 國(guó)內(nèi)外研究現(xiàn)狀

并行算法研究的高峰期在70、80年代。這一時(shí)期，涌現(xiàn)除了很多優(yōu)秀的非數(shù)值并行算法，它們?cè)谡麄€(gè)并行算法研究歷史上占據(jù)著非常輝煌的一頁(yè)。90年代中期以后，并行算法的研究漸漸面向?qū)嶋H，內(nèi)容也有所擴(kuò)展。

近年來，并行算法的研究更是趨于實(shí)際應(yīng)用中。比如：一種基于局部小型分布式存儲(chǔ)架構(gòu)的大規(guī)模Fock矩陣建設(shè)的新的并行算法：RT并行算法；基于共享內(nèi)存架構(gòu)的節(jié)能性能權(quán)衡分析并行算法；在多核心CPU與GPU中基于塊三角矩陣求解線性系統(tǒng)的并行算法；同構(gòu)新的并行劃分方法和巨人矩陣轉(zhuǎn)置并行算法，等等。圖像匹配的并行算法；面向異構(gòu)體系結(jié)構(gòu)的粒子輸運(yùn)并行算法；海量數(shù)據(jù)擬合并行算法；基于GPU的高性能并行算法；遙感數(shù)字影像中提取植被指數(shù)的并行算法；Fermi架構(gòu)下超聲成像組織運(yùn)動(dòng)可視化并行算法；分布式水文模型的并行計(jì)算；聲納圖像對(duì)比度增強(qiáng)的并行算法；大規(guī)模稀疏矩陣特征問題求解的并行算法；分布動(dòng)載荷識(shí)別的并行算法，等等。

1.2 并行算法

并行算法就是通過多臺(tái)處理器對(duì)于一些可同時(shí)執(zhí)行的問題聯(lián)合求解的方法和步驟。其特點(diǎn)是各個(gè)子問題相對(duì)獨(dú)立。并行算法是計(jì)算機(jī)設(shè)計(jì)相對(duì)復(fù)雜的技術(shù)之一，雖然算并行法的設(shè)計(jì)是復(fù)雜的，但并不是無跡可尋。隨著計(jì)算機(jī)的普及和應(yīng)用，技巧也被后來的人掌握并總結(jié)為最基本的設(shè)計(jì)基礎(chǔ)。

并行算法可從不同的角度分類成數(shù)值計(jì)算和非數(shù)組計(jì)算的并行算法；同步的、異步的和分布式的并行算法；共享存儲(chǔ)的和分布存儲(chǔ)的并行算法；確定的和隨機(jī)的并行算法等等。

1.2.1 并行算法的設(shè)計(jì)策略

并行算法的設(shè)計(jì)策略主要有：并行算法的直接并行化、從問題描述開始設(shè)計(jì)并行算法、借用已有算法求解新問題。具體描述如下：的并行計(jì)算方法之一，它的基本操作是將現(xiàn)有的串行算法進(jìn)行對(duì)串行代碼進(jìn)行發(fā)

串行算法直接并行化是現(xiàn)在最常用掘和利用，并合并化處理的過程。當(dāng)然并不是所有的程序都適合串行算法直接合并化。

從問題描述開始設(shè)計(jì)并行算法，即從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計(jì)一個(gè)全新的并行算法。設(shè)計(jì)方法：挖掘問題的固有特性與并行的關(guān)系。設(shè)計(jì)全新的并行算法是一份具有挑戰(zhàn)性和創(chuàng)造性的工作，利用串的周期性的PRAM-CRCW算法是一個(gè)很好的范例。

借用已有算法求解新問題，就是找出求解問題和某個(gè)已解決問題之間的聯(lián)系，改造或利用已知算法應(yīng)用到求解問題上。這是一項(xiàng)創(chuàng)造性的工作，使用矩陣乘法算法求解所有點(diǎn)對(duì)間最短路徑是一個(gè)很好的范例。

1.2.2 并行算法的基本設(shè)計(jì)技術(shù)

目前為止，并行算法的設(shè)計(jì)技術(shù)主要有：劃分設(shè)計(jì)技術(shù)、分治設(shè)計(jì)技術(shù)、平衡樹設(shè)計(jì)技術(shù)、倍增設(shè)計(jì)技術(shù)、流水線設(shè)計(jì)技術(shù)。其中劃分設(shè)計(jì)技術(shù)又可分為均勻劃分技術(shù)、方根劃分技術(shù)、對(duì)數(shù)劃分技術(shù)、功能劃分技術(shù)。具體描述如下：

劃分設(shè)計(jì)技術(shù)：

（1）均勻劃分技術(shù)，劃分方法，將n個(gè)元素A[1…n]分成p組，每組A[（i-1）n/p+1…in/p]，i=1…p；

（2）方根劃分技術(shù)，劃分方法，n個(gè)元素A[1…n]分成A[（i-1）n+1…in]，i=1…n；

（3）對(duì)數(shù)劃分技術(shù)，劃分方法，n個(gè)元素A[1…n]分成A[（i-1）logn+1…ilogn]，i=1…n/logn；

（4）功能劃分技術(shù)，劃分方法，n個(gè)元素A[1…n]分成等長(zhǎng)的p組，每組滿足某種特性。

分治設(shè)計(jì)技術(shù)，設(shè)計(jì)步驟如下：將輸入劃分成若干個(gè)規(guī)模相等的子問題，同時(shí)（并行地）遞歸求解這些子問題，并行地歸并子問題的解，直至得到原問題的解。

平衡樹設(shè)計(jì)技術(shù)，設(shè)計(jì)思想為：以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理。

倍增設(shè)計(jì)技術(shù)，設(shè)計(jì)思想為：以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理。

流水線設(shè)計(jì)技術(shù)，設(shè)計(jì)思想：將算法流程劃分成p個(gè)前后銜接的任務(wù)片斷，每個(gè)任務(wù)片斷的輸出作為下一個(gè)任務(wù)片斷的輸入，所有任務(wù)片斷按同樣的速率產(chǎn)生出結(jié)果。

1.2.3 并行算法的一般設(shè)計(jì)過程

PCAM（PartitioningCommunicationAgglomerationMapping）設(shè)計(jì)方法學(xué)，它代表了并行算法設(shè)計(jì)的四個(gè)階段：

（1）劃分就是通過編譯技術(shù)通過計(jì)算將計(jì)算機(jī)的任務(wù)進(jìn)行分解，以便達(dá)到最佳的計(jì)算和數(shù)據(jù)分布形式，其目的是盡可能地合理分配給各處理器進(jìn)行開拓和執(zhí)行任務(wù)的機(jī)會(huì)。劃分方法分為兩個(gè)步驟，第一是對(duì)數(shù)據(jù)進(jìn)行分解，也稱域分解，通過對(duì)計(jì)算機(jī)的數(shù)據(jù)分解之后開始對(duì)計(jì)算機(jī)的功能進(jìn)行分解。將數(shù)據(jù)集和計(jì)算集分離。

（2）通信。通過對(duì)數(shù)據(jù)的劃分，確認(rèn)任務(wù)執(zhí)行的數(shù)據(jù)交換以及協(xié)調(diào)執(zhí)行任務(wù)，通過進(jìn)一步的檢測(cè)來進(jìn)一步檢測(cè)劃分的合理性。通訊也是PCAM設(shè)計(jì)過程中的最重要的環(huán)節(jié)之一，他能夠促進(jìn)劃分環(huán)節(jié)中的任務(wù)之間的數(shù)據(jù)交流，解決劃分環(huán)節(jié)不能完全獨(dú)立執(zhí)行的問題，并通過交流限制功能劃分的數(shù)據(jù)并發(fā)執(zhí)行。

（3）組合是提高性能和減少通信開銷的重要方法之一，也是對(duì)于前兩個(gè)階段的性能要求和代價(jià)的實(shí)現(xiàn)結(jié)果進(jìn)行的重要考察，以便確認(rèn)是否將任務(wù)組合成更大的任務(wù)量。組合是對(duì)任務(wù)量的優(yōu)化，也是一個(gè)從抽象到具體的過程，通過在并行機(jī)上的有效執(zhí)行，合并較小的任務(wù)量，以便達(dá)到減少任務(wù)數(shù)的目的。通過一系列組合，達(dá)到增加任務(wù)的粒度和重復(fù)計(jì)算，可以減少通訊成本。

（4）映射。通過執(zhí)行、通信和組合，計(jì)算機(jī)的并行計(jì)算的任務(wù)數(shù)已經(jīng)達(dá)到了一種相對(duì)合理的程度，這時(shí)將計(jì)算機(jī)的任務(wù)合理地分配給相應(yīng)的處理器，縮短執(zhí)行時(shí)間，提高相應(yīng)處理器的執(zhí)行效率和利用效率，從而達(dá)到進(jìn)一步節(jié)約通訊成本的目的。其具體方法是將每一個(gè)經(jīng)過優(yōu)化的任務(wù)映射到相對(duì)應(yīng)的具體的處理器。通過對(duì)相應(yīng)處理器的定位和運(yùn)行，進(jìn)行計(jì)算和處理。如果其任務(wù)數(shù)大于處理器的數(shù)目時(shí)，則需要對(duì)處理器的負(fù)載和任務(wù)調(diào)度進(jìn)行平衡和調(diào)整。映射實(shí)際是一種權(quán)衡，屬于NP完全問題。

2 總結(jié)

隨著計(jì)算機(jī)軟、硬件性能的不斷提高，并行算法也得到不斷的改進(jìn)和創(chuàng)新，學(xué)者們正在以各種不同的方式提高算法的性能。同時(shí)，隨著時(shí)代的進(jìn)步，并行算法的研究方向也在進(jìn)行的不斷的調(diào)整。目前并行算法研究的新走向是：并行算法研究?jī)?nèi)容不斷拓寬，并行計(jì)算被納入研究范疇；與廣大用戶領(lǐng)域結(jié)合，注重應(yīng)用，強(qiáng)調(diào)走到用戶中去，為用戶解決問題；重視新的、非常規(guī)計(jì)算模式，如神經(jīng)計(jì)算、量子計(jì)算等，這些模式能夠解決某類特定問題，有其自身的優(yōu)越性。

參考文獻(xiàn)：

[1]陳國(guó)良.并行計(jì)算[M].北京：高等教育出版社，2003，8.

[2]HajimeTakashima，SoYamada，ShigeruObara，KunihiroKitamura，ShinjiroInabata，NobuakiMiyakawa，KazutoshiTanabe，UmpeiNagashima.Anovelparallelalgorithmforlarge-scaleFockmatrixconstructionwithsmalllocallydistributedmemoryarchitectures：RTparallelalgorithm.JournalofComputationalChemistry，2002，11.

[3]VijayAnandKorthikanti，GulAgha.Energy-performancetrade-offanalysisofparallelalgorithmsforsharedmemoryarchitectures.SustainableComputing：InformaticsandSystems，2011，11.

[4]ElenaN.Akimova，DmitryV.Belousov.Parallelalgorithmsforsolvinglinearsystemswithblock-tridiagonalmatricesonmulti-coreCPUwithGPU.JournalofComputationalScience，2012，11.

[5]ZhouQihai，LiYan.IsomorphicNewParallelDivisionMethodsandParallelAlgorithmsforGiantMatrixTranspose，2010.

[6]QingkuiChen，HaifengWang，SonglinZhuang，BochengLiu.ParallelAlgorithmofIDCTwithGPUsandCUDAforLarge-scaleVideoQualityof3G，2012.7.

[7]陳文浩.并行計(jì)算前景展望[J].高性能計(jì)算發(fā)展與應(yīng)用，2010，1.

[8]陳國(guó)良.并行算法研究進(jìn)展[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊.

[9]于二麗.圖像匹配的算法研究[J].計(jì)算進(jìn)應(yīng)用技術(shù)，2011，3.

[10]龔春葉.面向異構(gòu)體系結(jié)構(gòu)的粒子輸運(yùn)并行算法研究[J].計(jì)算機(jī)科學(xué)與技術(shù)，2011，12.

[11]馮小丹.基于MPI的海量數(shù)據(jù)擬合并行算法研究[J].中國(guó)軟件與理論，2008，5.

[12]白洪濤.基于GPU的高性能并行算法研究[J].計(jì)算機(jī)軟件與理論，2010，6.

[13]于延.遙感數(shù)字影像中提取植被指數(shù)并行算法的研究與實(shí)現(xiàn)[J].科技通報(bào)，2013，2.

[14]何興無.Fermi架構(gòu)下超聲成像組織運(yùn)動(dòng)可視化并行算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，4.

[15]劉軍志.分布式水文模型的并行計(jì)算研究進(jìn)展[J].2013，4.

[16]王石成.聲納圖像對(duì)比度增強(qiáng)的并行算法研究[J].微型機(jī)與應(yīng)用，2013，4.

[17]吳洋.一類大規(guī)模稀疏矩陣特征問題求解的并行算法[J].2013，6.

[18]殷海濤.分布動(dòng)載荷識(shí)別的并行算法研究[J].國(guó)外電子測(cè)量技術(shù)，2012.8.

[19]雷英杰，霍紅衛(wèi).典型并行算法的實(shí)現(xiàn)性能分析[J].空軍工程大學(xué)學(xué)報(bào)，2003，10.

[20]蔡啟先.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)[M].北京：電子工業(yè)出版社.

作者單位：百色職業(yè)學(xué)院，廣西百色 533000；廣西英華國(guó)際職業(yè)學(xué)院，廣西百色 535000