串行程序的并行劃分算法研究

盧成浪

(溫州大學(xué)甌江學(xué)院，浙江溫州 325035)

串行程序的并行劃分算法研究

盧成浪

(溫州大學(xué)甌江學(xué)院，浙江溫州 325035)

給出了一個(gè)將串行程序進(jìn)行并行劃分的算法，并對(duì)算法的有效性進(jìn)行了理論分析和實(shí)驗(yàn)驗(yàn)證．結(jié)果表明，該算法能有效地并行劃分串行程序，提高串行程序的執(zhí)行效率．

串行程序；并行劃分模型；計(jì)算復(fù)雜度；相關(guān)度

并行算法的設(shè)計(jì)分為四個(gè)階段：任務(wù)劃分（Partitioning）、通信分析（Communication）、任務(wù)組合（Agglomeration）和處理器映射（Mapping），統(tǒng)稱PCAM設(shè)計(jì)過程[1]．在PCAM過程中，首要問題是如何把任務(wù)劃分為若干個(gè)功能獨(dú)立且計(jì)算量均衡的子模塊[2]，從而有效減少任務(wù)的并行執(zhí)行開銷．文獻(xiàn)[2-6]對(duì)這個(gè)問題進(jìn)行了研究，提出了一些有效的串行程序并行劃分方法，其中最具代表性的為 RPDMA算法[4-5]，它是以程序塊之間的相關(guān)度盡可能小為準(zhǔn)則對(duì)串行程序進(jìn)行并行劃分的．但是，假如由RPDMA得到的并行劃分模型為若存在程序塊其計(jì)算量遠(yuǎn)大于其它的程序塊，則根據(jù)Ω設(shè)計(jì)得到的并行程序的執(zhí)行開銷受iP支配，若再考慮通信等開銷，那么該并行程序的執(zhí)行開銷將大于原有的串行程序，這種情況下采用RPDMA算法是無法提高串行程序的執(zhí)行效率的．有鑒于此，本文改進(jìn)了RPDMA算法，引入了程序塊計(jì)算復(fù)雜度等概念，并據(jù)此給出了新的串行程序并行劃分算法，稱作PPA算法．

1 并行劃分模型

文獻(xiàn)[6]定義了程序塊之間的控制相關(guān)?C、流相關(guān)?F、輸出相關(guān)?O和反相關(guān)?U等概念．本文基于以上這些概念，定義一個(gè)新的并行劃分模型，該模型主要涉及程序塊相關(guān)、相關(guān)度和計(jì)算復(fù)雜度等概念．

定義1 若Θ表示程序塊的集合，則Θ上的相關(guān)二元關(guān)系?定義如下：

若任意程序塊的對(duì)偶∈?，則稱作A相關(guān)于B，并記作A?B．

定義1表明：任意兩個(gè)串行程序塊之間存在相關(guān)關(guān)系，當(dāng)且僅當(dāng)這兩個(gè)程序塊之間存在控制相關(guān)關(guān)系、流相關(guān)關(guān)系、輸出相關(guān)關(guān)系或反相關(guān)關(guān)系．

定義2表明：任意兩個(gè)串行程序塊的相關(guān)度不僅與它們的輸入輸出集有關(guān)，并且還與它們之間的控制相關(guān)度有關(guān)．采用基本程序塊的相關(guān)關(guān)系（即定義1）來劃分串行程序塊，很難將串行程序塊劃分為多個(gè)可并行的程序塊．考慮基本程序塊之間總是存在相關(guān)關(guān)系，本文引入了程序塊相關(guān)度的概念，這樣，在進(jìn)行并行劃分時(shí)，不要求程序塊之間的相關(guān)度為零，只要它們之間的相關(guān)度足夠?。ㄐ∮谝粋€(gè)給定的閾值），就可對(duì)它們進(jìn)行劃分．

定義3 若Q為串行程序語句的集合，且P?Q，則程序塊P的計(jì)算復(fù)雜度δ定義為：

為了更好地衡量串行程序塊的計(jì)算復(fù)雜度，定義3將程序塊中的基本語句劃分為三類：基本語句、循環(huán)語句和函數(shù)調(diào)用語句，然后采用不同的方法來分別計(jì)算這三類語句的復(fù)雜度．對(duì)于基本語句，為方便處理，本文把它的計(jì)算復(fù)雜度簡(jiǎn)單地設(shè)定為一個(gè)常數(shù)（稱作計(jì)算量常數(shù)）；對(duì)于循環(huán)語句，其計(jì)算復(fù)雜度被設(shè)定為計(jì)算量常數(shù)與循環(huán)次數(shù)的乘積；對(duì)于函數(shù)調(diào)用語句，它的執(zhí)行將引入一個(gè)新的程序塊，該新程序塊也是由基本語句、循環(huán)語句和函數(shù)調(diào)用語句組成，所以其計(jì)算復(fù)雜度可以由定義3遞歸地進(jìn)行計(jì)算．串行程序塊的所有語句計(jì)算復(fù)雜度的累加和構(gòu)成該串行程序塊的計(jì)算復(fù)雜度．

定義4 程序塊集合Θ的并行劃分模型Ω是集合Θ上的一個(gè)劃分，并且

其中，ξ為計(jì)算復(fù)雜度上限閾值，ζ為相關(guān)度上限閾值．

定義4表明：在并行劃分模型Ω中，任意兩個(gè)基本程序塊均不相關(guān)或相關(guān)度低于給定的相關(guān)度上限閾值．也就是說，對(duì)于Ω中任意基本程序塊若其計(jì)算復(fù)雜度高于給定的復(fù)雜度上限閾值，則該程序塊必不可再次劃分為兩個(gè)相關(guān)度小于相關(guān)度上限閾值的子程序塊．因此，并行劃分模型Ω綜合考慮了程序塊的相關(guān)度和計(jì)算復(fù)雜度，其目標(biāo)是，在保證各程序塊的計(jì)算復(fù)雜度基本平衡的條件下，使各程序塊之間的相關(guān)度盡可能?。薛钢械母鞒绦驂K調(diào)度到不同的處理機(jī)上并行處理，以提高任務(wù)的執(zhí)行效率．

性質(zhì)1 程序塊集Θ的并行劃分模型Ω滿足以下性質(zhì)：并行劃分模型的該性質(zhì)保證了串行程序的任何一個(gè)子程序塊不會(huì)被執(zhí)行多于一次，也保證了程序的每一個(gè)子程序塊都可以被執(zhí)行．

2 并行劃分算法

根據(jù)本文第一部分所描述的并行劃分模型，我們可以設(shè)計(jì)對(duì)應(yīng)于該模型的并行劃分算法，并稱之為PPA算法．PPA算法的輸入是一個(gè)串行程序P，而輸出是并行劃分模型Ω．PPA算法與復(fù)雜度上限閾值ξ和相關(guān)度上限閾值ζ相關(guān)．復(fù)雜度上限閾值ξ限定了程序塊的最大允許復(fù)雜度，如果程序塊的復(fù)雜度大于ξ，則該程序塊需要再次劃分．相關(guān)度上限閾值ζ限定了程序塊允許劃分的最大相關(guān)度，如果兩個(gè)程序段的相關(guān)度大于ζ，則這兩個(gè)程序段只能屬于同一程序塊而不允許劃分．

PPA算法的主要思路是把劃分后的程序段之間的相關(guān)程度轉(zhuǎn)化成為各個(gè)節(jié)點(diǎn)之間的通信，而通信是并行處理的瓶頸，PPA的目標(biāo)是盡量降低各個(gè)節(jié)點(diǎn)之間的通信量，并同時(shí)考慮各節(jié)點(diǎn)的計(jì)算量，盡量均衡各節(jié)點(diǎn)的計(jì)算復(fù)雜度．為此，PPA算法可以簡(jiǎn)要描述如下：

1）由給定的串行程序P，生成一個(gè)基本程序塊的集合．

2）根據(jù)各程序塊之間的相關(guān)性生成一個(gè)帶權(quán)圖G，圖的節(jié)點(diǎn)是程序塊，圖的任意邊AB的權(quán)表示基本程序塊A和B之間的相關(guān)度．

3）找出G中權(quán)最小的邊，然后讓每一條邊的權(quán)都減去該邊的權(quán)．如果產(chǎn)生的新圖是非連通圖，則表明串行程序可以劃分為兩個(gè)或兩個(gè)以上的帶有一定相關(guān)性的子程序．如果新圖是連通圖，那么再按照上述的方法進(jìn)行劃分，直到產(chǎn)生的新圖為非連通圖．

4）計(jì)算得到的劃分的各程序塊的計(jì)算復(fù)雜度．如果各程序塊的計(jì)算復(fù)雜度均小于ξ，則可以認(rèn)為劃分合理．否則，重新劃分計(jì)算復(fù)雜度大于ξ的程序塊．在劃分程序塊時(shí)，如果發(fā)現(xiàn)兩個(gè)程序段的相關(guān)度大于ζ，則不再劃分這兩個(gè)程序段．直到所有計(jì)算復(fù)雜度大于ξ的程序塊都被處理完畢．

重新計(jì)算劃分模型Ω的各程序塊的計(jì)算復(fù)雜度，如果仍有程序塊的計(jì)算復(fù)雜度大于ξ，則認(rèn)為該串行程序并行化代價(jià)太大，從而不能并行化．

更加具體的PPA算法描述如下所示：

算法：PPA

輸入：一個(gè)串行程序P和復(fù)雜度上限閾值ξ及相關(guān)度上限閾值ζ

輸出：并行劃分模型Ω

據(jù)以上算法描述，若以n表示輸入串行程序的基本程序塊數(shù)，經(jīng)過PPA算法并行劃分后的基本程序塊數(shù)為|Ω|，則PPA算法的計(jì)算時(shí)間復(fù)雜度為：

3 實(shí)驗(yàn)比較

下面將通過實(shí)驗(yàn)來檢查PPA算法對(duì)串行程序的并行劃分效果．實(shí)驗(yàn)采用PPA算法與傳統(tǒng)的RPDMA算法相比較的方式進(jìn)行．步驟簡(jiǎn)要如下：

7）根據(jù)步驟5）和步驟6）記錄的運(yùn)行時(shí)間繪圖，見圖1．

圖1 程序運(yùn)行時(shí)間比較Fig 1 Comparison of Program Running Time

通常，根據(jù)RPDMA算法得到的并行劃分模型Ω的基數(shù)大于1，并保證各基本程序塊之間的相關(guān)度盡可能?。玆PDMA算法的缺點(diǎn)也是明顯的，如基本程序塊的計(jì)算量相差很大，會(huì)導(dǎo)致并行程序加速比很低．

從圖1可以看出，相比于原有的串行程序，由RPDMA得到的并行劃分模型的加速比改善效果有限．此外，對(duì)于有些并不能并行化或者需要花費(fèi)巨大的代價(jià)才能實(shí)現(xiàn)并行化的串行程序，RPDMA算法仍能給出其并行劃分結(jié)果，這是有誤導(dǎo)性的，會(huì)導(dǎo)致并行劃分后的效果更差（見圖1的第3次實(shí)驗(yàn)）．

從圖1還可以看出，通過并行劃分，PPA算法能夠有效地提高串行程序的執(zhí)行效率．這是因?yàn)?，由PPA算法得到的并行劃分模型Ω，各程序塊的計(jì)算復(fù)雜度都不超過ξ，這保證了各程序塊的計(jì)算量相對(duì)均衡，有效地彌補(bǔ)了RPDMA算法的缺陷，提高了并行劃分模型的正確性．此外，通過調(diào)整復(fù)雜度上限參數(shù)ξ和相關(guān)度上限參數(shù)ζ，PPA算法能完全兼容RPDMA算法．

4 結(jié)束語

本文提出了一個(gè)串行程序并行劃分算法（PPA），它綜合考慮了程序塊的相關(guān)度和計(jì)算量兩個(gè)因素，得到的并行劃分模型有更好的效果．與傳統(tǒng)的RPDMA算法相比，該算法能對(duì)串行程序進(jìn)行更有效的并行劃分，且擁有良好的時(shí)間復(fù)雜度．

[1] Lin C, Synder L. 并行程序設(shè)計(jì)原理[M]. 陸鑫達(dá), 林新華, 譯. 北京: 機(jī)械工業(yè)出版社, 2009: 101-195.

[2] 黃其軍, 楊建武, 余華山. 基于規(guī)范劃分集的并行循環(huán)計(jì)算劃分[J]. 軟件學(xué)報(bào), 2003, (3): 75-82.

[3] 嚴(yán)勝祥, 吳紹春, 吳耿鋒. 一種基于縱向劃分?jǐn)?shù)據(jù)集的并行決策樹分類算法[J]. 計(jì)算機(jī)工程與科學(xué), 2004, (7): 85-92.

[4] 江文毅, 龐麗萍, 高蘭, 等. 串行程序的并行劃分算法研究[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2000, (12): 30-32.

[5] 劉鍵, 謝衛(wèi), 朱曉梅, 等. 一種關(guān)于Do-loop并行劃分的新觀點(diǎn)與新方法[J]. 計(jì)算機(jī)學(xué)報(bào), 1999, (7): 520-530.

[6] 張宇亮, 張立臣, 李代平. 并行算法的任務(wù)粒度與映射方法的分析[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005, (20): 45-47.

Study on Parallel Partitioning Algorithm for Serial Program

LU Chenglang
(Oujiang College, Wenzhou University, Wenzhou, China 325035)

An effective parallel partitioning algorithm for serial programs was offered in this paper. Then theoretical analysis and experiment were carried out to validate the validity of the algorithm. Results showed that the algorithm is an effective one for partitioning serial programs and improving execution efficiency of serial programs.

Serial Program; Parallel Partitioning Model; Computational Complexity; Correlation

TP301.6

：A

：1674-3563(2010)04-0021-06

10.3875/j.issn.1674-3563.2010.04.005 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：王一芳)

2009-12-17

溫州大學(xué)甌江學(xué)院教師科研項(xiàng)目(JSKY09016)

盧成浪(1982- )，男，浙江蒼南人，助教，碩士，研究方向：并行程序設(shè)計(jì)