楊際祥 凌 玲

(重慶交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 重慶 400074)

?

多核集群任務(wù)分配問(wèn)題的0-1整數(shù)規(guī)劃求解模型①

楊際祥②凌 玲

(重慶交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 重慶 400074)

研究了典型多核集群任務(wù)分配中的節(jié)點(diǎn)內(nèi)通訊特性?；?-1整數(shù)非線性規(guī)劃模型和線性松弛技術(shù)，給出了一種0-1整數(shù)線性規(guī)劃任務(wù)分配問(wèn)題求解優(yōu)化模型。由于節(jié)點(diǎn)內(nèi)的通訊量與通訊延遲較大，以最小化計(jì)算代價(jià)和節(jié)點(diǎn)間通訊代價(jià)為研究目標(biāo)的傳統(tǒng)求解模型具有嚴(yán)重的局限性，而該求解模型考慮了節(jié)點(diǎn)內(nèi)通訊代價(jià)，并采用了線性規(guī)劃松弛技術(shù)，其目標(biāo)是最小化計(jì)算代價(jià)、節(jié)點(diǎn)間通訊代價(jià)和節(jié)點(diǎn)內(nèi)通訊代價(jià)。計(jì)算結(jié)果驗(yàn)證了提出的模型的有效性。

多核集群， 任務(wù)分配問(wèn)題(TAP)， 0-1整數(shù)規(guī)劃， 線性規(guī)劃松弛

0 引 言

任務(wù)分配問(wèn)題(task allocation problem, TAP)是并行計(jì)算領(lǐng)域的一個(gè)經(jīng)典問(wèn)題，任務(wù)分配旨在將一組任務(wù)分配到一組計(jì)算節(jié)點(diǎn)上，以最小化總成本?？偝杀就ǔ０▓?zhí)行成本和節(jié)點(diǎn)間(或處理器間)通訊成本。然而，隨著基于多核節(jié)點(diǎn)的以層次方式構(gòu)成的集群成為并行計(jì)算的一種發(fā)展趨勢(shì)，通訊成本不但包括節(jié)點(diǎn)間通訊成本，還應(yīng)包括節(jié)點(diǎn)內(nèi)通訊成本，而節(jié)點(diǎn)內(nèi)通訊成本又與節(jié)點(diǎn)內(nèi)的通訊量和通訊延遲兩個(gè)因素密切相關(guān)。文獻(xiàn)[1,2]通過(guò)通訊量和通訊延遲展示了節(jié)點(diǎn)內(nèi)通訊的重要性。文獻(xiàn)[1]指出，網(wǎng)絡(luò)附屬存儲(chǔ)(NAS)基準(zhǔn)測(cè)試中超過(guò)50%的通訊量是通過(guò)節(jié)點(diǎn)內(nèi)通訊完成的。文獻(xiàn)[2]研究表明，在典型的多核集群系統(tǒng)中，在節(jié)點(diǎn)內(nèi)的通訊延遲與節(jié)點(diǎn)間的通訊延遲之比隨消息的增大而增大。因此，考慮并優(yōu)化節(jié)點(diǎn)內(nèi)通訊與優(yōu)化節(jié)點(diǎn)間通訊成本同等重要。傳統(tǒng)的任務(wù)分配問(wèn)題(TAP)求解以最小化節(jié)點(diǎn)計(jì)算代價(jià)與節(jié)點(diǎn)之間的通訊代價(jià)為研究目標(biāo)，具有嚴(yán)重的局限性。

現(xiàn)有的求解TAP的方法大致可分為三類，即圖理論法、數(shù)學(xué)規(guī)劃法以及啟發(fā)式方法[3]。數(shù)學(xué)規(guī)劃方法將任務(wù)分配問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題，并使用數(shù)學(xué)規(guī)劃技術(shù)[3,4]進(jìn)行求解。如果未知變量為整數(shù)，則該問(wèn)題為整數(shù)規(guī)劃問(wèn)題。在實(shí)際情況中，通常未知變量個(gè)數(shù)有限，該問(wèn)題為一NP難問(wèn)題。0-1整數(shù)規(guī)劃為整數(shù)規(guī)劃的一種特殊情況，變量或?yàn)?或?yàn)?，該問(wèn)題仍為一NP難問(wèn)題。傳統(tǒng)的四個(gè)或者更多個(gè)計(jì)算機(jī)上的任務(wù)分配問(wèn)題的求解為一NP完全問(wèn)題，更不必說(shuō)新的多核集群任務(wù)分配問(wèn)題(task allocation problem in multi-core clusters，TAPMC)的求解為一難解問(wèn)題。本文使用整數(shù)規(guī)劃理論求解TAPMC，首先給出一個(gè)0-1整數(shù)非線性規(guī)劃求解模型，然后借助線性規(guī)劃松弛技術(shù)與優(yōu)化方法給出一種新的0-1整數(shù)線性規(guī)劃模型。

1 傳統(tǒng)TAP的0-1整數(shù)規(guī)劃模型

不失一般性，假設(shè)n個(gè)任務(wù)分配到m個(gè)計(jì)算節(jié)點(diǎn)上，部分任務(wù)間彼此存在通訊。如果任務(wù)i被分配到計(jì)算節(jié)點(diǎn)j上，產(chǎn)生的執(zhí)行成本設(shè)為eij，而設(shè)當(dāng)任務(wù)i與任務(wù)k未被分配到同一個(gè)計(jì)算節(jié)點(diǎn)上產(chǎn)生的通訊成本為cik。二元變量xij定義為1，當(dāng)且僅當(dāng)任務(wù)i分配到計(jì)算節(jié)點(diǎn)j上，反之為0。傳統(tǒng)任務(wù)分配問(wèn)題可轉(zhuǎn)化為0-1整數(shù)規(guī)劃問(wèn)題，該0-1整數(shù)規(guī)劃問(wèn)題旨在最小化完成任務(wù)的總成本，如模型

(1)

所示。

0-1整數(shù)規(guī)劃問(wèn)題可分為整數(shù)規(guī)劃問(wèn)題或者非線性規(guī)劃問(wèn)題，部分研究者給出了該問(wèn)題的求解方法?；诜种ο藿缂夹g(shù)，文獻(xiàn)[5]給出了一種求解該問(wèn)題的方法。文獻(xiàn)[6]使用Lagrangian對(duì)偶公式分枝限界法給出了一種有效的求解算法；文獻(xiàn)[7,8]給出一種解決整數(shù)規(guī)劃問(wèn)題的列生成模型，并且證明了它們的計(jì)算性能；文獻(xiàn)[4]引入一種混合整數(shù)規(guī)劃模型，當(dāng)存在大量的任務(wù)通訊時(shí)尤其有效，求解大規(guī)模問(wèn)題時(shí)比其它精確算法更為有效。

2 多核集群任務(wù)分配問(wèn)題(TAPMC)求解模型

2.1 0-1整數(shù)非線性規(guī)劃模型

0-1整數(shù)規(guī)模劃型(式(1))能夠有效求解傳統(tǒng)任務(wù)分配問(wèn)題，但無(wú)法有效求解多核集群任務(wù)分配問(wèn)題。在本文中，考慮了多核集群任務(wù)分配問(wèn)題的0-1整數(shù)規(guī)劃問(wèn)題，給出多核集群任務(wù)分配問(wèn)題的一種0-1整數(shù)非線性規(guī)劃求解模型，如模型

(2)

所示。

在模型式(2)中，目標(biāo)函數(shù)包括以下三個(gè)部分：

為有助于求解TAPMC問(wèn)題，模型式(2)可表示為

(3)

2.2 0-1線性整數(shù)規(guī)劃模型

(4)

進(jìn)一步，引入變量uij與vij。若任務(wù)i未分配到計(jì)算節(jié)點(diǎn)j，則uij(或者vij)為0，否則表示任務(wù)i與其它任務(wù)(任務(wù)i+1,i+2,…,n)之間發(fā)生的節(jié)點(diǎn)間(或者節(jié)點(diǎn)內(nèi))通訊總成本。因此，模型式(4)可表示為

(5)

2.3 應(yīng)用極大獨(dú)立集優(yōu)化TAPMC求解模型

盡管給出了求解TAPMC的0-1整數(shù)線性規(guī)劃模型，該模型仍需進(jìn)一步優(yōu)化。在計(jì)算節(jié)點(diǎn)內(nèi)與節(jié)點(diǎn)間的通訊成本時(shí)，假定通訊圖為一完全圖，因此可能產(chǎn)生一些不必要的計(jì)算。為避免這些不必要的計(jì)算，引入極大獨(dú)立集理論以優(yōu)化通訊成本的計(jì)算。

定義1：對(duì)于一個(gè)無(wú)向圖G=(V,E)及子集S(S?V)，若：(1) S中的任意兩個(gè)節(jié)點(diǎn)不相鄰，則稱S為G的一個(gè)獨(dú)立集；(2) S為G的一個(gè)獨(dú)立集，且對(duì)任意v∈V-S，在S中至少存在一個(gè)節(jié)點(diǎn)鄰接v，則稱S為G的一個(gè)極大獨(dú)立集。

圖1 調(diào)整前的通訊圖與通訊矩陣

圖2 調(diào)整后的通訊圖與通訊矩陣

在算法1中，swap(i, j)方法完成第i行與第j行之間的數(shù)據(jù)交換操作，同時(shí)完成第i列與第j列之間的數(shù)據(jù)交換操作。

3 計(jì)算結(jié)果

任務(wù)間的通訊使得分配決策比較困難。傳統(tǒng)的任務(wù)分配問(wèn)題的解決方法在任務(wù)間存在較少通訊時(shí)比較有效，而在解決涉及大量的任務(wù)間通訊(如通訊密度為50%、75%或100%)情形時(shí)顯得較為困難。文獻(xiàn)[4]引入了一種任務(wù)分配問(wèn)題整數(shù)求解模型U2,且計(jì)算結(jié)果表明其在當(dāng)所求解問(wèn)題存在大量的任務(wù)間通訊成本時(shí)效果較好。因此，通過(guò)與U2計(jì)算結(jié)果比較，以研究本文模型的有效性。

計(jì)算節(jié)點(diǎn)具體環(huán)境為Intel(R) Core(TM)2 Quad CPU Q6000 @2.40GHz,8G內(nèi)存,L2 Cache 4M, L1 Cache 32KB;Windows Server 2003;CPLEX 9.0[9]。任務(wù)數(shù)n配置為100,150,200；計(jì)算節(jié)點(diǎn)數(shù)m配置為4,6,8,10；通訊密度配置為50%,75%,100%。

計(jì)算結(jié)果如圖3～圖5所示。在任務(wù)數(shù)n=100,150,200時(shí)，本文模型的求解時(shí)間皆快于U2，且隨任務(wù)間通訊密度的增大，本文模型的優(yōu)勢(shì)更加明顯。此外，當(dāng)n=150,m=10，通訊密度=100%；n=200，m=8,10，通訊密度=50%, 75%；n=200,m=6,8,10，通訊密度=100%時(shí)，模型U2計(jì)算效率低下(超時(shí))，而本文模型則表現(xiàn)出了良好的計(jì)算效率與可擴(kuò)展性。

圖3 不同通訊密度下的任務(wù)(任務(wù)數(shù)n=100)求解時(shí)間隨節(jié)點(diǎn)數(shù)的變化關(guān)系

圖4 不同通訊密度下的任務(wù)(任務(wù)數(shù)n=150)求解時(shí)間隨節(jié)點(diǎn)數(shù)的變化關(guān)系

圖5 不同通訊密度下的任務(wù)(任務(wù)數(shù)n=200)求解時(shí)間隨節(jié)點(diǎn)數(shù)的變化關(guān)系

4 結(jié) 論

任務(wù)分配是多核集群系統(tǒng)中的一個(gè)重要問(wèn)題。傳統(tǒng)TAP為NP難問(wèn)題,新的TAPMC的求解更具有挑戰(zhàn)性。本文給出一種求解TAPMC的0-1整數(shù)非線性規(guī)劃模型,并給出一種0-1整數(shù)線性規(guī)劃模型及其優(yōu)化方法。計(jì)算結(jié)果表明,當(dāng)存在大量任務(wù)間通訊時(shí),本文給出的計(jì)算模型比較有效。

[1] Chai L, Gao Q, Panda D K. Understanding the impact of multi-core architecture in cluster computing: a case study with Intel dual-core system. In: Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid, Rio De Janeiro, Brazil, 2007. 471-478

[2] 涂碧波，鄒銘，詹劍鋒等. 多核處理器機(jī)群Memory層次化并行計(jì)算模型研究. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(11): 1948-1955

[3] Ernst A, Jiang H, Krishnamoorthy M. Exact solutions to task allocation problems.ManagementScience, 2006, 52(10): 1634-1646

[4] Menon S. Effective reformulations for task allocation in distributed systems with a large number of communicating tasks.IEEETransactionsonKnowledgeandDataEngineering, 2004, 16(12): 1497-1508

[5] Soylu B. Heuristic approaches for biobjective mixed 0-1 integer linear programming problems.EuropeanJournalofOperationalResearch, 2015, 245(3): 690-703

[6] Sherali H D, Smith J C. Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs.OptimizationLetters, 2012, 6(1): 127-139

[7] Alfandari L, Sadki J, Plateau A. Hybrid column generation for large-size covering integer programs: application to transportation planning.Computers&OperationsResearch, 2013, 40(8): 1938-1946

[8] R?nnberg E, Larsson T. All-integer column generation for set partitioning: basic principles and extensions.EuropeanJournalofOperationalResearch, 2014, 233(3): 529-538

[9] ILOG, Inc. ILOG CPLEX 9.0 User’s Manual. 2003, http://eaton.math.rpi.edu/cplex90html/pdf/usrcplex.pdf

A model for solving task allocation problems in multi-core clusters using 0-1 integer programming

Yang Jixiang, Ling Ling

(School of Mathematics and Statistics, Chongqing Jiaotong University, Chongqing 400074)

The in-node communication characteristics of the task allocation of multi-core clusters was studied. An optimized model for solving task allocation problems in multi-core clusters using 0-1 integer linear programming was proposed based on the 0-1 integer linear programming model and the linear relaxation technique. Considering that the traffic and delay of in-node communications are bigger, which brings serious limitations to the traditional models aiming to minimize the computing cost and the cost of the node-node communications, the proposed model takes account of the cost of in-node communications and adopts the technique of linear programming relaxation, with the aim to minimize the computing cost, the cost of node-node communications, and the in-node communication cost. The effectiveness of the model is verified by the computation result.

multi-core cluster, tast allocation problem, 0-1 integer programming, linear programming relaxation

10.3772/j.issn.1002-0470.2016.04.003

①國(guó)家自然科學(xué)基金(11401061)，重慶市自然科學(xué)基金(KJ1400316)和交通運(yùn)輸部建設(shè)科技基金(2014318223030)資助項(xiàng)目。

2015-12-16)

②男，1975年生，博士，副教授；研究方向：并行計(jì)算與系統(tǒng)可靠性等；聯(lián)系人，E-mail: jixiang_yang@126.com(