陳建兵， 梁立， 葉志霞

(1.云南師范大學(xué) 信息管理處,云南 昆明 650500；2.云南師范大學(xué) 信息學(xué)院,云南 昆明 650500)

1 引 言

有限拓?fù)涫侵赣邢藜系耐負(fù)洌河蒼元集合X的子集生成的集族T滿足：

(1)可行性：Φ,X∈T

(2)封閉性：對任意的A,B∈T都有A∪B∈T且A∩B∈T

則稱集族T是X的一個(gè)拓?fù)?

1元集合X的拓?fù)渲挥?個(gè)：{Φ,X}；2元集合有4個(gè)拓?fù)洌?元集合有29個(gè)拓?fù)洌?元集合有355個(gè)拓?fù)洌?元集合有6 942個(gè)拓?fù)洌?元集合有209 527個(gè)拓?fù)?，……?0元集合有8 977 053 873 043個(gè)拓?fù)鋄1]……

在早期，用枚舉法生成拓?fù)洳⒂?jì)數(shù)[2]，計(jì)算量相當(dāng)龐大.n元集合的所有集族有22n個(gè)，即使只枚舉滿足可行性的集族，也需要檢驗(yàn)22n-2個(gè)集族的封閉性，計(jì)算量仍然龐大.而且拓?fù)湔加屑宓谋壤喈?dāng)?shù)蚚3]，說明枚舉法做了大量的無效計(jì)算.趙婷婷根據(jù)文獻(xiàn)[4]的構(gòu)造定理，得到了文獻(xiàn)[5]和[6]的遞推算法，大大減少了無效的計(jì)算，但算法的時(shí)間復(fù)雜度仍然是非多項(xiàng)式的.拓?fù)鋽?shù)量的下界[7]是2n2/4也表明了這是一個(gè)NP難問題，即使完全有效的計(jì)算，計(jì)算量也很驚人的.因此，構(gòu)造并行算法很有必要，而負(fù)載均衡技術(shù)是有效發(fā)揮并行計(jì)算的關(guān)鍵.

2 遞推算法

2.1 有關(guān)概念

設(shè)n元集合Xn的拓?fù)銽={Φ,A1,…,Ak,Xn}，則

(1)拓?fù)溟L度：拓?fù)渲蟹强照孀蛹膫€(gè)數(shù)，即|T-{Φ,Xn}|，取值范圍0～2n-2.平庸拓?fù)涞拈L度最小為0，離散拓?fù)涞拈L度最大為2n-2.

(2)拓?fù)湓獢?shù)：拓?fù)渲兴蟹强照孀蛹牟⑺貍€(gè)數(shù)，即|∪A∈T-{Φ,Xn}A|，取值范圍0～n.只有平庸拓?fù)涞耐負(fù)湓獢?shù)為0.稱Smax=∪A∈T-{Φ,Xn}A為T的最大子集.

如果拓?fù)湓獢?shù)小于n，則稱T為α拓?fù)洌蝗绻負(fù)湓獢?shù)等于n，則稱T為β拓?fù)?

(3)直和運(yùn)算：設(shè)Xn的集族J={J1,J2,…,Jm},x∈Xn，則J?{x} ={J1∪{x},J2∪{x},…,Jm∪{x}}稱為J與x的直和運(yùn)算，簡記為J?x.

2.2 遞推算法

n元集合Xn={x1,x2,…,xn} 的所有拓?fù)溆蒼-1元集合Xn-1的每一個(gè)拓?fù)渖蒣5-6].對每一個(gè)n-1元集合的拓?fù)銽={Φ,A1,…,Ak,Xn-1}，由下面T1-T5五步產(chǎn)生n元集合的拓?fù)?新拓?fù)?：

T1:T1=T∪{Xn}

T2:T2=T∪(T?xn)

T3: 對每一個(gè)Ai∈T-{Φ,Xn-1}，T3=T∪(J?xn),其中J={Aj|Ai?Aj,Aj∈T}

T4: 對每一個(gè)Ai∈T-{Xn-1}，T4=(T?xn)∪J,其中J={Aj|Ai?Aj,Aj∈T}

T5：如果∪A∈T-{Φ,Xn-1}A≠Xn-1，則產(chǎn)生T5=(T-{Xn-1})∪{Xn}，并計(jì)算T6

計(jì)算T6：

Call max_main(Smax∪{xn}，Φ，T5，T5-Xn)

對每一個(gè)Ai∈T5-{Φ,Xn}

T6=T5∪J,其中J={Aj|Ai?Aj,Aj∈T5-{Φ,Xn}}⊕xn

Call max_main(Smax∪{xn}，Ai∪{xn}，T6，J)

下面的過程max_main是計(jì)算T6的一個(gè)子例程：

procedure max_main(Smax,Smain，Told，J)

{

C=Xn-Smax

對每一個(gè)C1∈2C，C1≠Φ

D=J?C1?xn={D1,……,Dh}，其中Di=Ji∪C1∪{xn}，Di≠Xn

對每一個(gè)Di∈D

ifDi>Smain

G=Told∪H,其中H={Dj|Di?Dj,Dj∈D}

如果G是拓?fù)?/p>

把G賦給T6

Call max_main(Smax∪Di，Di，T6，J∪H)

}

對每一個(gè)n-1元集合的拓?fù)銽，在T1-T2每一步只產(chǎn)生一個(gè)新拓?fù)?；T3-T4會產(chǎn)生多個(gè)新拓?fù)?；T6是在產(chǎn)生T5之后才計(jì)算(只有T是α拓?fù)洳女a(chǎn)生一個(gè)T5，也才會計(jì)算T6).

對每一個(gè)n-1元集合的拓?fù)銽產(chǎn)生新拓?fù)涞娜蝿?wù)都是獨(dú)立的，所以算法并行化是很容易的.分布式內(nèi)存并行計(jì)算的加速比很高(MPI易于實(shí)現(xiàn))，對每一個(gè)空閑的CPU都可以立即分配一個(gè)新的T，然后獨(dú)立完成T1-T6步；而共享內(nèi)存的并行計(jì)算存在多個(gè)計(jì)算任務(wù)等待的情況(主要是第T6步的計(jì)算量差異較大)，按照α拓?fù)溥M(jìn)行分類等待的時(shí)間會大大減少 (OpenMP易于實(shí)現(xiàn)共享內(nèi)存的并行算法) .

這個(gè)算法的時(shí)間復(fù)雜度比早期的一些算法有了很大的改進(jìn)，計(jì)算量幾乎就是拓?fù)鋽?shù)量，只有T6的計(jì)算有冗余.

3 負(fù)載均衡算法

上述的遞推算法T1-T5每一步之間是相互獨(dú)立的，沒有耦合，它們只依賴n-1元集合的拓?fù)銽，容易實(shí)現(xiàn)算法的并行計(jì)算.但是，每一個(gè)T所需要計(jì)算的時(shí)間不同，T1-T5每一步所花的時(shí)間差異很大，所以并行計(jì)算的負(fù)載均衡很重要.下面7種并行計(jì)算方法主要考慮負(fù)載均衡的問題：

(1)對每一個(gè)T，用5個(gè)CPU分別計(jì)算T1-T5.顯然，T1-T2容易計(jì)算；T3-T4計(jì)算時(shí)間與T的長度有關(guān)；如果T是α拓?fù)淠敲从?jì)算T5之后還需要計(jì)算T6，計(jì)算時(shí)間與T的長度和拓?fù)湓獢?shù)都有關(guān)系，如果T不是α拓?fù)渚筒恍枰?jì)算T5.顯然，5個(gè)步驟的計(jì)算量很不均衡.

(2)假設(shè)有CPUs個(gè)CPU，把T1-T5合并起來視為一個(gè)函數(shù)f(T).讀取CPUs個(gè)T之后再讓每個(gè)T分配一個(gè)CPU調(diào)用f(T)實(shí)現(xiàn)并行計(jì)算.根據(jù)(1)的分析，每一個(gè)T的長度和拓?fù)湓獢?shù)的不同，調(diào)用f(T)所需要的計(jì)算時(shí)間差異也很大.每個(gè)T的結(jié)構(gòu)不同而導(dǎo)致每個(gè)CPU的計(jì)算量很不均衡.

(3)把所有的T歸類.拓?fù)湓獢?shù)相同且拓?fù)溟L度也相同的T歸為一類.把同一類CPUs個(gè)T同時(shí)調(diào)度CPUs個(gè)CPU，最后剩余的T做一次善后處理.因?yàn)閚-1元集合的拓?fù)鋽?shù)量很大，把它們同時(shí)放在內(nèi)存是不現(xiàn)實(shí)的，而且各類拓?fù)浞植剂闵⒉蝗菀讱w類，所以這是一種理想方法，難以實(shí)現(xiàn).下面的三種方法是基于這種理想方法而逐步改進(jìn)的.

(4) 把α拓?fù)浜挺峦負(fù)浣徊嬗?jì)算.設(shè)兩個(gè)函數(shù)α(T)和β(T)，α(T)包含了T1-T5的計(jì)算，β(T) 包含了T1-T4的計(jì)算.如果T的拓?fù)湓獢?shù)小于n-1則調(diào)用給α(T)， 否則調(diào)用β(T).α拓?fù)浜挺峦負(fù)淇赡芙徊娉霈F(xiàn)，這是一種容易實(shí)現(xiàn)的并行算法.不同的T調(diào)用β(T) 的計(jì)算量比較相近，但是α(T) 的計(jì)算任務(wù)差異很大，因此負(fù)載也很不均衡.

(5)改進(jìn)第(4)種方法，把α拓?fù)浜挺峦負(fù)浞珠_計(jì)算.對n-1元的所有拓?fù)鋻呙鑳纱危旱谝淮翁幚韓-1元的α拓?fù)?，第二次處理n-1元的β拓?fù)?實(shí)驗(yàn)表明，這種方法比前面幾種方法在負(fù)載均衡的性能上有了明顯的改善，但是拓?fù)湓獢?shù)差別很大的兩個(gè)α拓?fù)?，它們的?jì)算時(shí)間相差也很大.

(6)改進(jìn)第(5)種方法，按拓?fù)湓獢?shù)歸類，仍然采用兩次掃描.用一個(gè)二維數(shù)組Tα[n-1][CPUs] 緩存α拓?fù)洌?dāng)某一個(gè)拓?fù)湓獢?shù)i存夠了CPUs個(gè)T，立即把Tα[i](i=0,1,…,n-2)分配給CPUs個(gè)CPU，調(diào)用α(T)并行計(jì)算.類似，用一個(gè)一維數(shù)組Tβ[CPUs] 緩存β拓?fù)?，?dāng)存夠了CPUs個(gè)T就分配CPUs個(gè)CPU調(diào)用β(T)并行計(jì)算.

方法(6)無論是數(shù)組Tα還是Tβ都沒有考慮拓?fù)溟L度歸類的問題.事實(shí)上，由于拓?fù)溟L度的取值范圍比較大，而且按長度分布的拓?fù)浔容^稀疏，按長度歸類是很難實(shí)現(xiàn)的.影響計(jì)算量的主要因素是拓?fù)湓獢?shù)，也就是α(T)中T5步的計(jì)算是影響計(jì)算量的主要因素.

(7)分配CPUs個(gè)CPU，每個(gè)進(jìn)程完成了T1-T5的全部計(jì)算之后，不等待其他進(jìn)程而直接讀取新的T，直到全部T處理結(jié)束.

方法(7)可以使分配的CPU長期處于高利用狀態(tài)，但存在兩個(gè)負(fù)擔(dān)：一是每個(gè)CPU全程負(fù)責(zé)一個(gè)T的遞推，在讀取新數(shù)據(jù)的時(shí)候需要“互斥”處理；二是由于每個(gè)T所需時(shí)間差異很大，在任務(wù)結(jié)束前，可能導(dǎo)致長時(shí)間等待某個(gè)進(jìn)程結(jié)束才完成整個(gè)任務(wù).實(shí)驗(yàn)發(fā)現(xiàn)，把β拓?fù)浞诺阶詈筇幚泶_實(shí)有明顯的效果，原因是在任務(wù)結(jié)束前不需要計(jì)算T6.因此方法(7)具有非常好的負(fù)載均衡性能.

4 算法實(shí)驗(yàn)

在上面討論的七種并行算法中，計(jì)算結(jié)果都一樣，不一樣的是算法的計(jì)算時(shí)間.不同的計(jì)算時(shí)間是由負(fù)載均衡的性能決定的.方法(1)和(2)的負(fù)載極不均衡，方法(3)難以實(shí)現(xiàn)，方法(5)是方法(4)的改進(jìn).因此，在本節(jié)中只給出方法(5)-(7)的實(shí)驗(yàn)數(shù)據(jù)，可以看到這三種方法逐步趨于較好的負(fù)載均衡狀態(tài).

用OMP共享內(nèi)存并行程序設(shè)計(jì)[8]，使用64個(gè)CPU對方法(5)-(7)進(jìn)行實(shí)驗(yàn).在相同的云計(jì)算環(huán)境下，方法(5)-(7)的計(jì)算時(shí)間對照如表1.從實(shí)驗(yàn)數(shù)據(jù)可以看出方法(7)的計(jì)算時(shí)間有大幅度的減少，說明從方法(5)到方法(7)的改進(jìn)是有效的.

表1 幾種并行計(jì)算時(shí)間對照表

從圖1-圖3可以看出，方法(7)的計(jì)算過程比較穩(wěn)定，CPU的使用率較高.總體而言無論從計(jì)算時(shí)間還是計(jì)算過程的穩(wěn)定性的角度分析，方法(7)的負(fù)載均衡性能基本趨于最佳狀態(tài).

圖1 方法(5)的運(yùn)行記錄截圖

圖2 方法(6)的運(yùn)行記錄截圖

圖3 方法(7)的運(yùn)行記錄截圖

5 結(jié) 論

上述算法和實(shí)驗(yàn)中，除了拓?fù)溟L度和拓?fù)湓獢?shù)對負(fù)載均衡有較大影響外，每一類數(shù)據(jù)使用CPU的個(gè)數(shù)對負(fù)載均衡影響也不小.

方法(5)-(7)是基于數(shù)據(jù)歸類的思想而實(shí)現(xiàn)負(fù)載均衡的.實(shí)驗(yàn)表明是可行而且非常有效的.如果再動(dòng)態(tài)調(diào)整CPU數(shù)，會使算法的負(fù)載均衡性能達(dá)到更佳的狀態(tài).方法(7)不需要考慮算法的耦合度，是比較普適性的方法.

另外，如果用文件存儲n-1元集合的拓?fù)鋽?shù)據(jù)，數(shù)據(jù)量很大，存為CPU個(gè)文件比較好：一是讀寫數(shù)據(jù)相對快，二是每一個(gè)線程單獨(dú)讀或?qū)懸粋€(gè)文件，不需要解決互斥的問題.對同一個(gè)CPU，先處理α拓?fù)渲缶o接著處理β拓?fù)洌驗(yàn)樘幚恙镣負(fù)浔圈峦負(fù)涓〞r(shí)間，如果順序顛倒，很有可能線程之間需要等待才能全部結(jié)束，尤其是共享內(nèi)存的并行計(jì)算的算法這一點(diǎn)更重要.