并行算法設(shè)計(jì)及編程基本方法

1、 182第 2 卷 第 4 期 零陵學(xué)院學(xué)報(bào)(教育科學(xué)) Vol. 2 No.4 2004 年 8 月 Journal of Lingling University Aug. 2004 并行算法

2、設(shè)計(jì)及編程基本方法 孫興文 (永州職業(yè)技術(shù)學(xué)院,湖南永州,425006) 摘 要: 并行算法是指一次可執(zhí)行多個(gè)操作的算法。對(duì)并行算法的研究現(xiàn)在已發(fā)展為一個(gè)獨(dú)立的研究領(lǐng)域。很多用串行算法解決的問(wèn)題也已經(jīng)有了相應(yīng)的并行算法。在本文，我們闡述了一些簡(jiǎn)單的并行計(jì)算以說(shuō)明并行算法的一些基本概念、應(yīng)用和編程方法。 關(guān)鍵詞: 并行算法; 效率 ;編程 * 中圖分類號(hào): TP311 文獻(xiàn)標(biāo)識(shí)碼: A 文章編號(hào)：1671-9697(2004)0

3、4-0182-03 1. 并行算法設(shè)計(jì) 1.1 并行算法的基本概念 所謂并行，是只有一個(gè)以上的事件在同一時(shí)刻伙同時(shí)間段內(nèi)發(fā)生，有人把并行分為幾類：數(shù)據(jù)并性行，分布式并性行與人的并行性，世界上客觀事物的發(fā)展過(guò)程很多是并行的，彼此相對(duì)獨(dú)立，相互又有一定的聯(lián)系和制約。 1.2 并行算法的目標(biāo) 從計(jì)算復(fù)雜性的角度來(lái)看， 一個(gè)算法的復(fù)雜性表示為空間復(fù)雜性和時(shí)間復(fù)雜性兩個(gè)方面。 并行算法的目標(biāo)是盡可能減少時(shí)間復(fù)雜性，通常是增加空間復(fù)雜性（如增加空間

4、的維數(shù)及增加處理器的臺(tái)數(shù)）來(lái)實(shí)現(xiàn)。從算法樹的結(jié)構(gòu)來(lái)看，通常的串行算法樹“深而窄”。 遞推算法是串行算法本質(zhì)上是為一維問(wèn)題設(shè)計(jì)的， 而不少高維問(wèn)題的計(jì)算本質(zhì)上仍借助一維的張量積形式。體現(xiàn)在矩陣計(jì)算則是 70 年代稀疏矩陣技術(shù)的廣發(fā)應(yīng)用。 并行算法樹的結(jié)構(gòu)則截然不同，為達(dá)到把時(shí)間復(fù)雜性轉(zhuǎn)化為時(shí)間復(fù)雜性的目的，并行算法樹采用“淺而寬”的結(jié)構(gòu)，即每時(shí)刻可容納的計(jì)算量相應(yīng)增加，使整個(gè)算法的步數(shù)盡可能減少。適當(dāng)增加空間復(fù)雜性（如引入較復(fù)雜的基底，增

5、加空間維數(shù)等） ，是不少并行算法所實(shí)際采用的有效的方法。 1.3 加速比定率與可擴(kuò)展性 顧名思義，并行加速比是表示采用多個(gè)矗立起計(jì)算速度所能得到的加速的倍數(shù)。 設(shè) t seq 表示用串行機(jī)求解某個(gè)計(jì)算問(wèn)題所需的時(shí)間，tP 是用 p 個(gè)處理器求解該問(wèn)題所需的時(shí)間。 定義 1.1 p 個(gè)處理器加速比． SP=t1/t2 （１.１） 這里 t 1 是用但處理求解統(tǒng)一問(wèn)題所需的時(shí)間。 定義 1.2 并行加速比 ?P＝ tsep/ tp

6、 （１.２） 這里? tsep 是表示用串行機(jī)求解該問(wèn)題所需的時(shí)間。 應(yīng)該指出，一般情況下 ?p< sp 這是因?yàn)?t1 是在并行操作系統(tǒng)下用單個(gè)處理器計(jì)算的結(jié)果，tsep 所用環(huán)境是串行操作系統(tǒng)，而并行操作系統(tǒng)的開銷一般大于串行系統(tǒng)。 設(shè)某個(gè)計(jì)算問(wèn)題中只能穿行執(zhí)行的運(yùn)算量百分比為 s， 其余為 p 個(gè)處理器可以并行執(zhí)行運(yùn)算量的百分比１－s,如果我們忽視通信與同步等有并行引起的開銷，加速比 sp 此時(shí)應(yīng)等于 收稿日期: 2004

7、-03-29 作者簡(jiǎn)介: 孫興文（1968－） ，湖南寧遠(yuǎn)人，講師，主要研究計(jì)算機(jī)網(wǎng)絡(luò)。 184基本方法有兩個(gè)：數(shù)據(jù)分解與功能分解。 （1）數(shù)據(jù)分解方法 數(shù)據(jù)分解，有時(shí)也稱數(shù)據(jù)分割，這是各個(gè)處理器基本執(zhí)行相同的任務(wù)，只是數(shù)據(jù)不同。 （2）功能分解方法 網(wǎng)絡(luò)計(jì)算的并行化也可以通過(guò)八總負(fù)載按功能加以實(shí)現(xiàn)， 最簡(jiǎn)單的功能分解是把整個(gè)計(jì)算過(guò)程分成輸入數(shù)據(jù)， 計(jì)算進(jìn)程與輸出結(jié)果三個(gè)部分。 2.3 并行計(jì)算的技術(shù)線路 在現(xiàn)有的串行算法上作并行化，

8、以及直接從數(shù)學(xué)物理問(wèn)題出發(fā)，面向并行系統(tǒng)研制高效率的并行計(jì)算方法與設(shè)計(jì)算法，是并行計(jì)算中兩條可供選擇的技術(shù)線路。 如果串行計(jì)算并行化的間接并行效果不好， 就必須認(rèn)真考慮直接并行的線路。 從研究角度看， 直接并行計(jì)算方法是廣闊的天地，是可以大有所為的。深入開展并行計(jì)算方法研究，不僅對(duì)于提高并行機(jī)使用效率是必需的，而且往往能找到改進(jìn)現(xiàn)有串行算法的新途徑。構(gòu)造高效并性行預(yù)條件子時(shí)不僅要考慮到保持原來(lái)算子的代數(shù)的特性，而且要保持其幾何特性及分析

9、特性，它們同樣適用于串行計(jì)算，便是很好的例子。 同時(shí)， 我們必須清醒地看到，并行計(jì)算有一定的適用范圍，它主要適用于超大型計(jì)算。 解決中，小規(guī)模問(wèn)題不必用并行機(jī)。由于目前各種并行機(jī)在不同程度上仍停留在專家級(jí)的使用水平，如果所要解決的問(wèn)題規(guī)模不大，就不必要那么的精力去搞并行。 另外，并行機(jī)的使用效率也于解決問(wèn)題的類型有關(guān)，即目前而言，對(duì)于求解與大型代數(shù)方程組及偏微分方程有關(guān)的問(wèn)題效果較好。參考文獻(xiàn): [1]Dhabaleswar K．Pan

10、daet．Special Issue on workstation Clusters and Network－Based Computing．J．Parallel and Distributed Computing ,1997. [2]杜端甫.運(yùn)籌圖論(網(wǎng)、網(wǎng)絡(luò)理論中的運(yùn)籌問(wèn)題) [M].北京航空航天大學(xué)出版社, 1990. [3]肖位樞.圖論及其算法[M].航空工業(yè)出版社,1993. [4]陳國(guó)良.并行算法的設(shè)計(jì)與分析[M].高等教育