車向前，張欣欣，邊　莉

(1.黑龍江科技大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，哈爾濱 150022； 2.黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022； 3.黑龍江科技大學(xué) 電子與信息工程學(xué)院，哈爾濱 150022)

?

利用組合型交叉熵實(shí)現(xiàn)多處理機(jī)調(diào)度的算法

車向前1，張欣欣2，邊莉3

(1.黑龍江科技大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，哈爾濱 150022； 2.黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022； 3.黑龍江科技大學(xué) 電子與信息工程學(xué)院，哈爾濱 150022)

為提高大型多處理機(jī)調(diào)度的效率與穩(wěn)定性，提出一種利用組合型交叉熵實(shí)現(xiàn)多處理機(jī)調(diào)度的方法。該方法依據(jù)處理機(jī)與作業(yè)的約束關(guān)系，將處理機(jī)調(diào)度問題表示為使目標(biāo)函數(shù)最小化的線性0-1整數(shù)規(guī)劃模型，采用組合型交叉熵算法對該模型進(jìn)行優(yōu)化求解。利用組合型交叉熵算法對多處理機(jī)問題的具體事例進(jìn)行測試，與模擬退火算法和蟻群算法的測試結(jié)果對比分析。結(jié)果表明：組合交叉熵算法的優(yōu)化速度是蟻群算法的6.1倍，是模擬退火的29.5倍，該算法穩(wěn)定性高，收斂速度快，運(yùn)行時(shí)間短，在解決大型多處理機(jī)問題時(shí)效率明顯高于模擬退火算法和蟻群算法。

組合型交叉熵； 多處理機(jī)調(diào)度； 0-1整數(shù)規(guī)劃

0　引　言

并行分布式計(jì)算是當(dāng)前科學(xué)領(lǐng)域研究的熱點(diǎn)問題。并行算法的設(shè)計(jì)、任務(wù)的劃分、通信的協(xié)調(diào)和同步、多任務(wù)的調(diào)度是目前并行分布式計(jì)算需要解決的問題，其中任務(wù)的調(diào)度會直接影響計(jì)算的效率，因此，如何合理高效地進(jìn)行多任務(wù)的調(diào)度與分配是目前亟須解決的難題。多處理機(jī)調(diào)度問題[1-3]的應(yīng)用及理論方面的研究，得到了科學(xué)領(lǐng)域研究者的極大關(guān)注。多處理機(jī)調(diào)度問題實(shí)質(zhì)是NP完全問題，傳統(tǒng)的線性規(guī)劃無法解決，目前，國內(nèi)外多采用啟發(fā)式算法近似求解。文獻(xiàn)[4]利用蟻群算法實(shí)現(xiàn)多處理機(jī)調(diào)度問題，每個(gè)處理機(jī)對應(yīng)一只螞蟻，每次迭代過程中并行螞蟻由主控進(jìn)程生成，當(dāng)所有螞蟻完成一次搜索時(shí)再進(jìn)行同步，這種方法增加了執(zhí)行時(shí)間。文獻(xiàn)[5]采用動態(tài)信息素更新和參數(shù)選擇，將蟻群算法進(jìn)行改進(jìn)，該方法在保證收斂速度的條件下能夠得到全局最優(yōu)解，很好地解決了多處理機(jī)任務(wù)調(diào)度問題。但這種方法存在收斂速度慢、效率較低等不足。文獻(xiàn)[6]將量子計(jì)算和粒子群算法結(jié)合解決多處理機(jī)調(diào)度問題，雖然操作簡單，容易實(shí)現(xiàn)，但是效率低、易陷入局部最優(yōu)解。針對現(xiàn)有研究解決多處理機(jī)問題時(shí)普遍存在收斂速度較慢、效率較低的現(xiàn)狀，筆者引入了組合型交叉熵算法。

1　多處理機(jī)調(diào)度模型

多處理機(jī)調(diào)度問題是指有c臺型號相同的處理機(jī)H1，H2，…，Hc，d項(xiàng)相互獨(dú)立的作業(yè)T1，T2，…，Td，作業(yè)獨(dú)立工作，而且每項(xiàng)作業(yè)在每臺處理機(jī)上工作的概率相同，但是每項(xiàng)作業(yè)不允許中斷。d項(xiàng)相互獨(dú)立的作業(yè)不能拆分為更小的子作業(yè)。調(diào)度的目的是給出一種合理優(yōu)越的調(diào)度方案，使c臺處理機(jī)以盡量短的時(shí)間完成d項(xiàng)作業(yè)[7]。多處理機(jī)調(diào)度問題的目標(biāo)是指在滿足一定性能指標(biāo)和約束條件的前提下，將可并行的任務(wù)按適當(dāng)?shù)姆峙洳呗源_定一種分派和執(zhí)行順序，合理分配到各處理機(jī)上有序執(zhí)行，以達(dá)到減少總執(zhí)行時(shí)間的目標(biāo)。因此，多處理機(jī)調(diào)度問題的數(shù)學(xué)模型如式(1)所示。多處理機(jī)調(diào)度問題的目的即求z的最小值。

(1)

式中:z——完成d項(xiàng)作業(yè)所需要的時(shí)間；

ynm=1——作業(yè)Tm在處理機(jī)Hn上處理；

tm——處理機(jī)完成作業(yè)Tm的時(shí)間；

根據(jù)多處理機(jī)調(diào)度問題的特點(diǎn)和模型可知，多處理機(jī)調(diào)度問題屬于離散優(yōu)化問題，文中應(yīng)用CE對多處理機(jī)問題進(jìn)行優(yōu)化求解，即通過交叉熵算法求出z的最小值。因?yàn)閥nm的取值為0或1，所以多處理機(jī)調(diào)度問題是0-1整數(shù)規(guī)劃問題。

2　交叉熵算法

交叉熵算法[8](Cross entropy algorithm，CE)是以信息論中的交叉熵理論為基礎(chǔ)提出的一種全局隨機(jī)優(yōu)化算法。近些年來,交叉熵算法被應(yīng)用到故障診斷、預(yù)測等大型復(fù)雜、優(yōu)化問題中。該算法的基本特征是在優(yōu)化過程中根據(jù)參數(shù)化概率密度分布，使每次迭代使用的候選樣本都發(fā)生變化。因此，CE算法優(yōu)化過程中的關(guān)鍵是迭代，具體的實(shí)現(xiàn)過程可分為兩步[9-12]：一是由給定的概率密度函數(shù)生成一組隨機(jī)樣本；二是根據(jù)產(chǎn)生的隨機(jī)樣本更新概率密度函數(shù)，進(jìn)而為下一步迭代產(chǎn)生更優(yōu)的樣本數(shù)據(jù)。

2.1交叉熵算法的基本原理

針對優(yōu)化問題

(2)

式中：S——X上的實(shí)值函數(shù)；

x*——所求問題的最優(yōu)解；

γ*——所求函數(shù)S的最小值。

CE算法將以上優(yōu)化問題轉(zhuǎn)化為概率問題，即轉(zhuǎn)化為求S(X)比已知參數(shù)γ小的概率問題。該問題可表示為

l(γ)=Pv(S(X)≤γ)=

(3)

式中：X=(x1,x2,…，xn)隨機(jī)向量，由f(·，v)產(chǎn)生的隨機(jī)樣本；

f(·,u)——概率密度函數(shù)；

I{S(X)≤γ}——指示函數(shù)；

γ——給定實(shí)數(shù)；

l——S(X)比給定實(shí)數(shù)γ小的概率；

I{S(X)≤γ}——指示函數(shù)集合；

Ev——相應(yīng)的期望值。

當(dāng)γ接近γ*時(shí)，l值將會越來越小，因此，為了有意義，值不能太小，則γ和v的選取至關(guān)重要。為了解決此問題，采用多級別算法，構(gòu)造分布參數(shù)序列{vt，t>0}和級別序列{γt，t>0}，t為迭代次數(shù)。將vt和γt進(jìn)行更新迭代，一直到某次迭代后分布參數(shù)序列中對應(yīng)元素改變量的最大值小于某一規(guī)定的參數(shù)btol，則迭代結(jié)束[13]。

2.2組合型交叉熵算法

CE算法分為連續(xù)型交叉熵算法和組合型交叉熵算法[14]，組合型交叉熵算法(CCE)是用來處理離散型數(shù)據(jù)，而連續(xù)性交叉熵算法是用來處理連續(xù)性數(shù)據(jù)。兩者之間的區(qū)別在于概率密度函數(shù)的選擇，針對組合優(yōu)化問題組合型交叉熵算法的概率密度函數(shù)為Berboulli分布。設(shè)成功概率為p，則CCE算法的概率密度函數(shù)為

f(x;p)=px(1-p)1-x，

(4)

式中,當(dāng)x=1時(shí)，f(x；p)=p；

當(dāng)x=0時(shí)，f(x;p)=1-p。

CCE算法的步驟為：

第一步設(shè)置初始值P(0)(n為P(0)的維數(shù))，最佳樣本的分?jǐn)?shù)ρ，樣本數(shù)M，平滑系數(shù)α，迭代次數(shù)t=0，終止參數(shù)btol。

第二步令t=t+1，Pt-1以Bernoulli分布產(chǎn)生M+n的樣本矩陣Xt=(X1(t),X2(t),…,XM(t))，其中Xm(t)=(xm(t),1,xm(t),2,…，xm(t),n)，1≤m≤M 。

γ(t)=S[(1-ρ)M]。

(5)

第四步利用式(6)更新參數(shù)P：

(6)

第五步利用平滑參數(shù)α，對pj處理，如式(7)所示：

pj=αpj+(1-α)pj-1。

(7)

第六步若相鄰兩次迭代產(chǎn)生的參數(shù)矩陣滿足式(8),則停止迭代，否則從第二步開始重新迭代。

(8)

3　算　例

文獻(xiàn)[8]中的實(shí)例，三臺相同的處理機(jī)和九項(xiàng)作業(yè)，為了驗(yàn)證算法在解決大型多處理機(jī)調(diào)度問題時(shí)的有效性與優(yōu)越性，現(xiàn)取d=21項(xiàng)作業(yè)，算法復(fù)雜度以指數(shù)劇增。每項(xiàng)作業(yè)需要運(yùn)行的時(shí)間tm=(81,40,26,4,65,98,53,71,15,23,45,78,56,12,31,28,60,21,17,32,35)，下面解決如何使21項(xiàng)作業(yè)在盡可能短的時(shí)間內(nèi)由三臺處理機(jī)完成的NP完全問題。設(shè)Ynm為作業(yè)Tm分配到處理機(jī)Hn上所有的處理方案，則多處理機(jī)調(diào)度問題的求解由式(1)轉(zhuǎn)化式(9)

(9)

3.1多處理機(jī)調(diào)度問題的CCE算法

根據(jù)多處理機(jī)調(diào)度問題的數(shù)學(xué)模型可得,CCE算法的目標(biāo)函數(shù)式(9)為z，z中的變量ynm的取值為0和1，ynm服從Bernoulli分布，因此，該算法可以解決多處理機(jī)調(diào)度問題。為了得到目標(biāo)函數(shù)的最小值，利用CCE算法優(yōu)化目標(biāo)函數(shù)z，選取初始為P0=(0.5，0.5，…，0.5)(P0的維數(shù)為n)，ρ=0.85，M=60，α=0.9，btol=0.1× 10-3。文中的實(shí)驗(yàn)環(huán)境為CPU 1.8 GHz，內(nèi)存為4 G，采用Matlab對該問題編程，程序運(yùn)行10次，結(jié)果見表1。

表1　CCE算法的10次運(yùn)行結(jié)果

由表1可知，計(jì)算結(jié)果平均在第11次收斂，選取10次計(jì)算結(jié)果中最好解，目標(biāo)函數(shù)與迭代次數(shù)nd的關(guān)系，如圖1所示。

圖1　CCE算法的計(jì)算過程

由圖1可見，CCE算法在第13次迭代時(shí)已經(jīng)尋找到了種群最優(yōu)適應(yīng)值，z=286。對應(yīng)的調(diào)度方案為H1(81,26,98,28,21,32)，H2(15,45,78,56,31,60),H3(40,4,65,53,71,23,12,17,35)，調(diào)度時(shí)間為286 s。

3.2三種算法的比較

針對多處理機(jī)調(diào)度問題，采用模擬退火算法和蟻群算法與CCE算法進(jìn)行對比分析。經(jīng)過實(shí)驗(yàn)分析與驗(yàn)證，模擬退火算法中起始溫度20 000 ℃，終止溫度1 ℃，退火速度α=0.97。相同條件下測試10次最好解的測試結(jié)果，如圖2所示。蟻群算法中信息素持久性系數(shù)ρ=0.8，信息素總量Q=200，相同條件下測試10次最好解的測試結(jié)果，如圖3所示。

圖2　模擬退火算法的計(jì)算過程

Fig.2Calculation process of simulated annealing algorithm

圖3　蟻群算法的計(jì)算過程

表2　三種算法結(jié)果比較

綜合三種算法對多處理機(jī)調(diào)度問題的測試結(jié)果，CCE算法比模擬退火算法和蟻群算法具有運(yùn)行時(shí)間短、收斂速度快、穩(wěn)定性高的優(yōu)勢，可以在大型多處理機(jī)調(diào)度方案中應(yīng)用。

4　結(jié)　論

(1)將組合型交叉熵算法應(yīng)用到多處理機(jī)調(diào)度問題中，通過對該算法和多處理機(jī)調(diào)度問題的建模和仿真分析，得出CCE算法的優(yōu)化速度是蟻群算法的6.1倍，是模擬退火算法的29.5倍。

(2)CCE算法的平均值為293.1，小于蟻群算法和模擬退火算法，說明CCE算法穩(wěn)定性更高。將CCE算法應(yīng)用于更大的多處理機(jī)調(diào)度問題，該算法調(diào)度任務(wù)時(shí)會節(jié)省很多時(shí)間。

(3)CCE算法可解決多處理機(jī)調(diào)度問題，證明該算法具有穩(wěn)定性高、收斂速度快、運(yùn)行時(shí)間短等優(yōu)勢。

(4)文中對于可轉(zhuǎn)化為類似多處理機(jī)問題模型的解決方案，提供了一種全新的思路，交叉熵算法可以應(yīng)用到眾多工程問題的解決方案中。

[1]曹杰先,秦永彬,許道云.求解多處理機(jī)調(diào)度問題的近似算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(7):2407-2411.

[2]MU PENGCHENG,NEZAN JEANFRAN.Advanced list scheduling heuristic for task scheduling with communication contention for parallel embedded systems [J].Science China Information Sciences,2010,53(11):2272-2286.

[3]DA LI,LEI ZHANG.An efficient dynamic scheduling for multiprocessor architecture[J].International Conference on Electrical and Computer Engineering,2012,12(1):125-130.

[4]郭乘濤,江志斌.應(yīng)用混合蟻群算法求解并行批處理機(jī)組批與調(diào)度問題[J].上海交通大學(xué)學(xué)報(bào),2010,44(8):1068-1073.[5]鄧酩,謝曉蘭,程小輝.多處理機(jī)調(diào)度問題的蟻群優(yōu)化算法[J].桂林理工大學(xué)學(xué)報(bào),2013,33(2):329-332.

[6]黃天赦,葉春明,葉偉.關(guān)于多處理機(jī)調(diào)度問題的量子粒子群算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(9):49-51.

[7]高尚,楊靜宇.群智能算法及其應(yīng)用[M].北京:中國水利水電出版社,2006:24-28.

[8]REUVEN Y RUBINSTEIN.The Cross-entropy method:a unified approach to combinatorial optimization[M].Australia:Springer-Verlag New York Inc,2004:15-25.

[9]邊莉,車向前,張少卿.基于改進(jìn)交叉熵算法多目標(biāo)不等間距陣列綜合[J].上海交通大學(xué)學(xué)報(bào),2014,48(3):372-376.

[10]MINVIELLE P,TANTAR E.Sparse antenna array optimization with the cross-entropy method[J].IEEE Transaction on Antennas and Propagation,2011,59(8)：2862-2871.

[11]WANG CHUANSHENG,QIU YUE.Vehicle routing problem with stochastic demandsand simultaneous delivery and pickup based on the cross-entropy method[J].Advances in Automation and Robotics,2012,10(2):55-60.

[12]陳寧,沙倩,湯奕.基于交叉熵理論的風(fēng)電功率組合預(yù)測方法[J].中國電機(jī)工程學(xué)報(bào),2012,32(4):29-34.

[13]邊莉,邊晨源.基于組合型交叉熵算法的多電源配電網(wǎng)故障定位[J].電力科學(xué)與技術(shù)學(xué)報(bào),2014,29 (3):86-91.

[14]邊莉,邊晨源.組合型交叉熵算法在電網(wǎng)故障診斷中的應(yīng)用[J].電力系統(tǒng)及其自動化學(xué)報(bào),2015,27 (10):41-47.

(編輯李德根)

Problem of multiprocessor scheduling based on combinatorial cross-entropy algorithm

CHE Xiangqian1,ZHANG Xinxin2,BIAN Li3

(1.School of Computer &Information Engineering,Heilongjiang University of Science &Technology,Harbin 150022,China； 2.School of Electrical &Control Engineering,Heilongjiang University of Science &Technology,Harbin 150022,China； 3.School of Electronic &Information Engineering,Heilongjiang University of Science &Technology,Harbin 150022,China)

This paper presents a novel method designed for realizing multiprocessor scheduling using combinatorial cross entropy as part of the dedicated efforts to improve the efficiency and stability of a large multiprocessor scheduling.This method works by using the constraint relation between processor and job to define the multiprocessor scheduling as a 0-1 integer programming model for minimizing the objective function;realizing the optimal solution using the combinatorial cross-entropy algorithm;testing the concrete example of the multiprocessor scheduling problem using the combinatorial cross-entropy algorithm;and performing a comparative analysis of the results with the simulated annealing algorithm and the ant colony algorithm.Results demonstrate that the combinatorial cross entropy algorithm working at 6.1 times and 29.5 times respectively the speed of the ant colony algorithm and simulated annealing boasts a significantly greater efficiency than simulated annealing algorithm and ant colony algorithm in solving the large scale multiprocessor scheduling problem.

combinatorial cross-entropy algorithm;multiprocessor scheduling problem;0-1 integer programming problem

2016-02-01

國家自然科學(xué)基金項(xiàng)目(51504085)

車向前(1978-)，男，黑龍江省克東人，副教授，碩士，研究方向：圖像處理、機(jī)器視覺、逆向工程，E-mail:che_xq@163.com。

10.3969/j.issn.2095-7262.2016.03.018

TP301.6

2095-7262(2016)03-0323-04

A