生成有限拓撲的負載均衡算法*

陳建兵， 梁立， 葉志霞

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

1 引 言

有限拓撲是指有限集合的拓撲：由n元集合X的子集生成的集族T滿足：

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

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

則稱集族T是X的一個拓撲.

1元集合X的拓撲只有1個：{Φ,X}；2元集合有4個拓撲，3元集合有29個拓撲，4元集合有355個拓撲，5元集合有6 942個拓撲，6元集合有209 527個拓撲，……，10元集合有8 977 053 873 043個拓撲[1]……

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

2 遞推算法

2.1 有關(guān)概念

設(shè)n元集合Xn的拓撲T={Φ,A1,…,Ak,Xn}，則

(1)拓撲長度：拓撲中非空真子集的個數(shù)，即|T-{Φ,Xn}|，取值范圍0～2n-2.平庸拓撲的長度最小為0，離散拓撲的長度最大為2n-2.

(2)拓撲元數(shù)：拓撲中所有非空真子集的并所含元素個數(shù)，即|∪A∈T-{Φ,Xn}A|，取值范圍0～n.只有平庸拓撲的拓撲元數(shù)為0.稱Smax=∪A∈T-{Φ,Xn}A為T的最大子集.

如果拓撲元數(shù)小于n，則稱T為α拓撲；如果拓撲元數(shù)等于n，則稱T為β拓撲.

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

2.2 遞推算法

n元集合Xn={x1,x2,…,xn} 的所有拓撲由n-1元集合Xn-1的每一個拓撲生成[5-6].對每一個n-1元集合的拓撲T={Φ,A1,…,Ak,Xn-1}，由下面T1-T5五步產(chǎn)生n元集合的拓撲(新拓撲)：

T1:T1=T∪{Xn}

T2:T2=T∪(T?xn)

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

T4: 對每一個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}，并計算T6

計算T6：

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

對每一個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是計算T6的一個子例程：

procedure max_main(Smax,Smain，Told，J)

{

C=Xn-Smax

對每一個C1∈2C，C1≠Φ

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

對每一個Di∈D

ifDi>Smain

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

如果G是拓撲

把G賦給T6

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

}

對每一個n-1元集合的拓撲T，在T1-T2每一步只產(chǎn)生一個新拓撲；T3-T4會產(chǎn)生多個新拓撲；T6是在產(chǎn)生T5之后才計算(只有T是α拓撲才產(chǎn)生一個T5，也才會計算T6).

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

這個算法的時間復雜度比早期的一些算法有了很大的改進，計算量幾乎就是拓撲數(shù)量，只有T6的計算有冗余.

3 負載均衡算法

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

(1)對每一個T，用5個CPU分別計算T1-T5.顯然，T1-T2容易計算；T3-T4計算時間與T的長度有關(guān)；如果T是α拓撲那么計算T5之后還需要計算T6，計算時間與T的長度和拓撲元數(shù)都有關(guān)系，如果T不是α拓撲就不需要計算T5.顯然，5個步驟的計算量很不均衡.

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

(3)把所有的T歸類.拓撲元數(shù)相同且拓撲長度也相同的T歸為一類.把同一類CPUs個T同時調(diào)度CPUs個CPU，最后剩余的T做一次善后處理.因為n-1元集合的拓撲數(shù)量很大，把它們同時放在內(nèi)存是不現(xiàn)實的，而且各類拓撲分布零散不容易歸類，所以這是一種理想方法，難以實現(xiàn).下面的三種方法是基于這種理想方法而逐步改進的.

(4) 把α拓撲和β拓撲交叉計算.設(shè)兩個函數(shù)α(T)和β(T)，α(T)包含了T1-T5的計算，β(T) 包含了T1-T4的計算.如果T的拓撲元數(shù)小于n-1則調(diào)用給α(T)， 否則調(diào)用β(T).α拓撲和β拓撲可能交叉出現(xiàn)，這是一種容易實現(xiàn)的并行算法.不同的T調(diào)用β(T) 的計算量比較相近，但是α(T) 的計算任務差異很大，因此負載也很不均衡.

(5)改進第(4)種方法，把α拓撲和β拓撲分開計算.對n-1元的所有拓撲掃描兩次：第一次處理n-1元的α拓撲，第二次處理n-1元的β拓撲.實驗表明，這種方法比前面幾種方法在負載均衡的性能上有了明顯的改善，但是拓撲元數(shù)差別很大的兩個α拓撲，它們的計算時間相差也很大.

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

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

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

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

4 算法實驗

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

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

表1 幾種并行計算時間對照表

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

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

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

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

5 結(jié) 論

上述算法和實驗中，除了拓撲長度和拓撲元數(shù)對負載均衡有較大影響外，每一類數(shù)據(jù)使用CPU的個數(shù)對負載均衡影響也不小.

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

另外，如果用文件存儲n-1元集合的拓撲數(shù)據(jù)，數(shù)據(jù)量很大，存為CPU個文件比較好：一是讀寫數(shù)據(jù)相對快，二是每一個線程單獨讀或?qū)懸粋€文件，不需要解決互斥的問題.對同一個CPU，先處理α拓撲之后緊接著處理β拓撲，因為處理α拓撲比β拓撲更花時間，如果順序顛倒，很有可能線程之間需要等待才能全部結(jié)束，尤其是共享內(nèi)存的并行計算的算法這一點更重要.