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

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

中圖分類號：TP393

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

1 并行算法

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

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

近年來，并行算法的研究更是趨于實際應(yīng)用中。比如：一種基于局部小型分布式存儲架構(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)動可視化并行算法；分布式水文模型的并行計算；聲納圖像對比度增強(qiáng)的并行算法；大規(guī)模稀疏矩陣特征問題求解的并行算法；分布動載荷識別的并行算法，等等。

1.2 并行算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 總結(jié)

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

參考文獻(xiàn)：

[1]陳國良.并行計算[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].高性能計算發(fā)展與應(yīng)用，2010，1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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