楊際祥 凌 玲
(重慶交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 重慶 400074)
?
多核集群任務(wù)分配問題的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ù)分配問題求解優(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ù)分配問題(TAP), 0-1整數(shù)規(guī)劃, 線性規(guī)劃松弛
任務(wù)分配問題(task allocation problem, TAP)是并行計(jì)算領(lǐng)域的一個(gè)經(jīng)典問題,任務(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]通過通訊量和通訊延遲展示了節(jié)點(diǎn)內(nèi)通訊的重要性。文獻(xiàn)[1]指出,網(wǎng)絡(luò)附屬存儲(chǔ)(NAS)基準(zhǔn)測(cè)試中超過50%的通訊量是通過節(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ù)分配問題(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ù)分配問題轉(zhuǎn)化為優(yōu)化問題,并使用數(shù)學(xué)規(guī)劃技術(shù)[3,4]進(jìn)行求解。如果未知變量為整數(shù),則該問題為整數(shù)規(guī)劃問題。在實(shí)際情況中,通常未知變量個(gè)數(shù)有限,該問題為一NP難問題。0-1整數(shù)規(guī)劃為整數(shù)規(guī)劃的一種特殊情況,變量或?yàn)?或?yàn)?,該問題仍為一NP難問題。傳統(tǒng)的四個(gè)或者更多個(gè)計(jì)算機(jī)上的任務(wù)分配問題的求解為一NP完全問題,更不必說新的多核集群任務(wù)分配問題(task allocation problem in multi-core clusters,TAPMC)的求解為一難解問題。本文使用整數(shù)規(guī)劃理論求解TAPMC,首先給出一個(gè)0-1整數(shù)非線性規(guī)劃求解模型,然后借助線性規(guī)劃松弛技術(shù)與優(yōu)化方法給出一種新的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ù)分配問題可轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題,該0-1整數(shù)規(guī)劃問題旨在最小化完成任務(wù)的總成本,如模型
(1)
所示。
0-1整數(shù)規(guī)劃問題可分為整數(shù)規(guī)劃問題或者非線性規(guī)劃問題,部分研究者給出了該問題的求解方法?;诜种ο藿缂夹g(shù),文獻(xiàn)[5]給出了一種求解該問題的方法。文獻(xiàn)[6]使用Lagrangian對(duì)偶公式分枝限界法給出了一種有效的求解算法;文獻(xiàn)[7,8]給出一種解決整數(shù)規(guī)劃問題的列生成模型,并且證明了它們的計(jì)算性能;文獻(xiàn)[4]引入一種混合整數(shù)規(guī)劃模型,當(dāng)存在大量的任務(wù)通訊時(shí)尤其有效,求解大規(guī)模問題時(shí)比其它精確算法更為有效。
2.1 0-1整數(shù)非線性規(guī)劃模型
0-1整數(shù)規(guī)模劃型(式(1))能夠有效求解傳統(tǒng)任務(wù)分配問題,但無法有效求解多核集群任務(wù)分配問題。在本文中,考慮了多核集群任務(wù)分配問題的0-1整數(shù)規(guī)劃問題,給出多核集群任務(wù)分配問題的一種0-1整數(shù)非線性規(guī)劃求解模型,如模型
(2)
所示。
在模型式(2)中,目標(biāo)函數(shù)包括以下三個(gè)部分:
為有助于求解TAPMC問題,模型式(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è)無向圖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ù)交換操作。
任務(wù)間的通訊使得分配決策比較困難。傳統(tǒng)的任務(wù)分配問題的解決方法在任務(wù)間存在較少通訊時(shí)比較有效,而在解決涉及大量的任務(wù)間通訊(如通訊密度為50%、75%或100%)情形時(shí)顯得較為困難。文獻(xiàn)[4]引入了一種任務(wù)分配問題整數(shù)求解模型U2,且計(jì)算結(jié)果表明其在當(dāng)所求解問題存在大量的任務(wù)間通訊成本時(shí)效果較好。因此,通過與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)系
任務(wù)分配是多核集群系統(tǒng)中的一個(gè)重要問題。傳統(tǒng)TAP為NP難問題,新的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
①國家自然科學(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(