孫發(fā)軍，彭際群

(懷化學(xué)院1.數(shù)學(xué)系;2.高性能并行計(jì)算中心，湖南 懷化 418008)

1 組合空間的劃分問(wèn)題

近年來(lái)，隨著云計(jì)算的興起，其基礎(chǔ)技術(shù)——并行計(jì)算更是得到國(guó)內(nèi)外廣泛的研究[1-6].實(shí)際應(yīng)用中通常有這樣一類問(wèn)題:需要從一個(gè)組合空間中通過(guò)窮舉搜索尋求最優(yōu)解或在組合空間上完成一定的計(jì)算，如交巡警平臺(tái)的增設(shè)問(wèn)題就是這樣一例.

為了更有效地貫徹實(shí)施巡警服務(wù)職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺(tái).每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同.假設(shè)該城市有92個(gè)路口，現(xiàn)已經(jīng)設(shè)置20個(gè)巡警平臺(tái)，根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際情況，擬在該區(qū)內(nèi)再增加2-5個(gè)平臺(tái)，即在72個(gè)路口中選擇其中2-5個(gè)，使得在平臺(tái)個(gè)數(shù)增加盡可能少的情況下整個(gè)城市巡警工作量足夠低且分配平均.

定義1組合空間的劃分問(wèn)題:并行計(jì)算中，給定k個(gè)cpu節(jié)點(diǎn)，如何把Cnm個(gè)組合動(dòng)態(tài)均衡而又連續(xù)地分配給各cpu節(jié)點(diǎn)去計(jì)算的問(wèn)題.

假設(shè)解決該問(wèn)題的劃分方案需滿足以下要求:

(1)動(dòng)態(tài)性:為了提高速度及滿足一般性需要，我們假設(shè)這Cnm個(gè)組合是運(yùn)行時(shí)動(dòng)態(tài)生成和分配的.

(2)連續(xù)性:為便于各CPU 節(jié)點(diǎn)上的并行程序在自己連續(xù)的子空間內(nèi)使用循環(huán)完成計(jì)算，如窮舉搜索最優(yōu)解，這就要求劃分組合空間后的子空間應(yīng)該連續(xù);

(3)均衡性:劃分后所得每一個(gè)子空間所含的組合數(shù)近似相等，最好能達(dá)到完全相等.

為了討論該問(wèn)題的解決方案是否均衡，我們定義了如下兩個(gè)指標(biāo)[2-4]:均衡指數(shù)和加速比.均衡指數(shù)用于理論分析中衡量均衡性，而加速比用于通過(guò)實(shí)驗(yàn)分析均衡性，因?yàn)橥ǔ?lái)說(shuō)均衡性越高所得到的加速比應(yīng)該越大，而高加速比正是我們讓劃分達(dá)到均衡的最終目的.

定義2 均衡指數(shù)δ:設(shè)分配給n個(gè)CPU 節(jié)點(diǎn)的任務(wù)量分別為q1，q2，…，qn，則我們定義均衡指數(shù)為他們之間的標(biāo)準(zhǔn)差:

定義3 加速比η:算法串行計(jì)算時(shí)間ts和算法并行計(jì)算時(shí)間tp之比，即:

2 均衡劃分研究

以前面描述的交巡警服務(wù)平臺(tái)增設(shè)問(wèn)題為例，記的組合為(u，v，w，x，y)，(假設(shè)已設(shè)置的平臺(tái)號(hào)為0～19，則其中20u87，21v88，22w89，23x90，24y91)，現(xiàn)考慮將該組合空間劃分成16個(gè)子空間，以方便將任務(wù)分配給16個(gè)cpu核并行執(zhí)行，我們總結(jié)出下面的兩類三種方案.

2.1 常規(guī)劃分

考慮20u87，計(jì)u =20 時(shí)的組合為(20，v，w，x，y)，計(jì)u =21 時(shí)的組合為(21，v，w，x，y)… 計(jì)u=87 時(shí)的組合為(87，v，w，x，y)，這樣就把C572的組合空間分成了68個(gè)u類組合.要將其劃分成16個(gè)子空間分配到16個(gè)CPU 節(jié)點(diǎn)上則可為每個(gè)節(jié)點(diǎn)分配4-5 (由68 ÷16 =4.25)個(gè)u類組合，我們可得到劃分并計(jì)算出了每個(gè)節(jié)點(diǎn)分配到的實(shí)際組合數(shù)如表1所示(為便于描述，文中所有節(jié)點(diǎn)號(hào)是CPU 節(jié)點(diǎn)號(hào)，一般來(lái)說(shuō)一個(gè)CPU 節(jié)點(diǎn)是一個(gè)CPU 核).

表1 u-均勻劃分方案

記該方案為方案一，其均衡指數(shù)為標(biāo)準(zhǔn)差δ1=δ(C1/1000，C2/1000…C16/1000)，計(jì)算得到δ1≈1080.5，均衡指數(shù)非常大表明各CPU 節(jié)點(diǎn)負(fù)載非常不均衡，最大值達(dá)到3567416個(gè)組合.

分析C37的分配情況我們不難發(fā)現(xiàn)產(chǎn)生以上現(xiàn)象的原因.C37的組合空間為(1，2，3)，(1，2，4)，(1，2，5)，(1，2，6)，(1，2，7)，(1，3，4)，(1，3，5)，(1，3，6)，(1，3，7)，(1，4，5)，(1，4，6)，(1，4，7)，(1，5，6)，(1，5，7)，(1，6，7)，(2，3，4)，(2，3，5)，(2，3，6)，(2，3，7)，(3，4，5)，(3，4，6)，(3，4，7)，(4，5，6)，(4，5，7)，(4，6，7)，(5，6，7).對(duì)于C37的組合(u，v，w)，若以均勻u為依據(jù)劃分，很顯然u =1 時(shí)的組合數(shù)是最多的，u值越大，其組合數(shù)越少，當(dāng)u =5只有一個(gè)組合(5，6，7).

2.2 均衡劃分

常規(guī)劃分方案雖然實(shí)現(xiàn)了并行計(jì)算，提高了計(jì)算的速度，但因?yàn)槌霈F(xiàn)了明顯的負(fù)載不均衡現(xiàn)象，沒(méi)有充分發(fā)掘出任務(wù)的并行性.由表1可以總結(jié)出，不能以u(píng)為標(biāo)準(zhǔn)去劃分整個(gè)組合空間，因?yàn)閷?duì)于不同的u，其組合(u，v，w，x，y)的個(gè)數(shù)本身就是不均衡的.

分析u，v，w，x，y組合的分布規(guī)律我們發(fā)現(xiàn)，w的組合分布相對(duì)更均勻(如表2所示)，表2為不同的k值的組合(u，v，w，x，y)的個(gè)數(shù).

于是我們考慮以w(22w89)為標(biāo)準(zhǔn)進(jìn)行劃分，這樣我們可給每個(gè)節(jié)點(diǎn)平均分配4-5個(gè)w值得到如表3所示的w-均勻劃分方案(記該方案為方案二)，然后可據(jù)式(1.1)計(jì)算出均衡指數(shù)為δ2=462.77，最大值降為1487196個(gè)組合，不到常規(guī)方案的42%，可見方案二比方案一的均衡性好很多，計(jì)算時(shí)間理論上可縮小一半以上.

表2 不同w值的組合個(gè)數(shù)

表3 w- 均勻劃分方案

事實(shí)上，為使各節(jié)點(diǎn)負(fù)載更均衡，我們可不均勻分配w值來(lái)進(jìn)行劃分，而是先統(tǒng)計(jì)出每一個(gè)w的組合(u，v，w，x，y)的個(gè)數(shù)(如表2所示)，再根據(jù)組合個(gè)數(shù)進(jìn)行子空間劃分，且對(duì)于w=j的組合數(shù)與w =111-j的組合數(shù)相等.C572=13991544，13991544 ÷16 =874471.5，我們考慮為每個(gè)CPU 節(jié)點(diǎn)分配800000～900000個(gè)組合數(shù)，得到如表4所示的分配方案(記為方案三).

由式(1.1)可計(jì)算出方案三的均衡指數(shù)為，計(jì)算δ3=118.24，而最大組合數(shù)為1068966，對(duì)比方案一下的均衡指數(shù)δ1=2.335δ2=9.138δ3，顯然δ3比δ1幾乎小一數(shù)量級(jí)，從而可知均衡劃分方案下各個(gè)CPU 節(jié)點(diǎn)負(fù)載更為均衡.

表4 w- 不均勻但更均衡劃分方案

3 均衡劃分的實(shí)驗(yàn)分析

為了便于比較各方案的優(yōu)劣，我們定義并行計(jì)算的加速比為式(1.2)所示.

按這種方案劃分，進(jìn)行并行計(jì)算，發(fā)現(xiàn)經(jīng)過(guò)30020.23 s 后計(jì)算完畢，速度明顯比單節(jié)點(diǎn)串行快(串行所需計(jì)算時(shí)間為117554.85 s)，我們可據(jù)式3.1 計(jì)算出其加速比為:

我們?cè)谑锕?600 系列服務(wù)器集群(10個(gè)2 路刀片服務(wù)器)上選擇了16個(gè)cpu 核對(duì)以上三種方案進(jìn)行了實(shí)驗(yàn)并記錄了相應(yīng)結(jié)果.

表5 u- 均勻劃分的實(shí)驗(yàn)結(jié)果(單位:秒)

圖1 方案一下16個(gè)節(jié)點(diǎn)的利用率

實(shí)驗(yàn)中我們記錄的各CPU 上的計(jì)算時(shí)間如表5所示，記常規(guī)方案下第i號(hào)CPU 節(jié)點(diǎn)的利用率為ei，ei=ti/MAX(t1，…，t16)×100%，得到各個(gè)CPU 節(jié)點(diǎn)的利用率如圖1所示.從圖1中可以看出，CPU利用率差異很大，該方案下CPU 資源浪費(fèi)嚴(yán)重.

表6 w- 均勻劃分的實(shí)驗(yàn)結(jié)果(單位:秒)

我們也記錄了方案二的各CPU 計(jì)算時(shí)間如表6所示，依式(1.2)我們可計(jì)算出加速比為:

結(jié)果表明w-均勻劃分相對(duì)于u-均勻劃分提高了2.40倍.

表7 w- 不均勻劃分的實(shí)驗(yàn)結(jié)果(單位:秒)

而按方案三進(jìn)行計(jì)算，各CPU的運(yùn)行時(shí)間和利用率分別如表7所示，并可計(jì)算出各CPU 節(jié)點(diǎn)利用率如圖2所示.

圖2 方案二下16個(gè)CPU 節(jié)點(diǎn)的利用率

由圖3.4可以看出，16個(gè)CPU 節(jié)點(diǎn)的利用率均比較高，CPU 資源得到了充分的利用.

同樣我們可計(jì)算出加速比為:

該加速比是u-均勻劃分的3.35倍，是w-均勻劃分的1.39倍，與理想值16 僅差2.88.

4 結(jié)論

論文提出的組合空間劃分方案充分考慮了CPU負(fù)載均衡和各CPU的利用率，進(jìn)一步挖掘了對(duì)稱多處理機(jī)上并行計(jì)算的效率，但為了方便計(jì)算機(jī)的執(zhí)行，組合空間采用了連續(xù)分配，導(dǎo)致各個(gè)劃分子空間大小仍有差距，在圖2中也可以看出，CPU 利用率最低約為63%，依然存在CPU 資源的浪費(fèi)，在并行計(jì)算過(guò)程中會(huì)出現(xiàn)一定的負(fù)載不均衡現(xiàn)象，探索出方便計(jì)算機(jī)執(zhí)行的非連續(xù)分配方案，進(jìn)一步挖掘CPU 資源的利用率，將是后續(xù)研究的一個(gè)重要內(nèi)容.事實(shí)上若將組合事先均等劃分地存到文件中，然后將文件分派到每個(gè)節(jié)點(diǎn)上執(zhí)行.這或許是種效率更高的方案，但從文件中讀數(shù)據(jù)或許會(huì)增大程序的執(zhí)行時(shí)間，從而也降低了計(jì)算速度，具體還有待進(jìn)一步研究.

[1]湯繼飛，李思，張理論，等.面向并行負(fù)載平衡的數(shù)據(jù)剖分技術(shù)[J].計(jì)算機(jī)應(yīng)用研究，2010，27 (11):4015-4019.

[2]王之元，楊學(xué)軍.并行計(jì)算系統(tǒng)度量指標(biāo)綜述[J].計(jì)算機(jī)工程與科學(xué)，2010，32 (10):44-48.

[3]鄭秋亞，劉三陽(yáng)，左大海，等.多塊結(jié)構(gòu)化網(wǎng)格CFD并行計(jì)算和負(fù)載平衡研究[J].工程數(shù)學(xué)學(xué)報(bào)，2010，27 (2):219-224.

[4]陳國(guó)良.并行算法研究方法學(xué)[J].計(jì)算機(jī)學(xué)報(bào)，2008，31 (9):1494-1502.

[5]馬永剛，譚國(guó)真，楊際祥，等.一種改進(jìn)的并行計(jì)算圖劃分模型[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32 (3):417-418.

[6]MENON S.Effective reformulations for task allocation in distributed systems with a large number of communicating tasks[J].IEEE Transactions on Knowledge and Data Engineering，2005，14 (12):1497-1508.

[7]Bokhari S H.Assignment problems in parallel and distributed computing[M].Norwell，MA，USA:Kluwer Acadermic Publishers，1987.