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

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

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

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

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

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

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

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

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

9、特性，它們同樣適用于串行計算，便是很好的例子。 同時， 我們必須清醒地看到，并行計算有一定的適用范圍，它主要適用于超大型計算。 解決中，小規(guī)模問題不必用并行機(jī)。由于目前各種并行機(jī)在不同程度上仍停留在專家級的使用水平，如果所要解決的問題規(guī)模不大，就不必要那么的精力去搞并行。 另外，并行機(jī)的使用效率也于解決問題的類型有關(guān)，即目前而言，對于求解與大型代數(shù)方程組及偏微分方程有關(guā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]杜端甫.運籌圖論(網(wǎng)、網(wǎng)絡(luò)理論中的運籌問題) [M].北京航空航天大學(xué)出版社, 1990. [3]肖位樞.圖論及其算法[M].航空工業(yè)出版社,1993. [4]陳國良.并行算法的設(shè)計與分析[M].高等教育