[發(fā)明專利]一種面向可分割任務(wù)的粒子群調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410768968.9
• 申請(qǐng)日: 2014-12-11
• 公開（公告）號(hào): CN105740059B
• 公開（公告）日: 2018-12-04
• 發(fā)明（設(shè)計(jì)）人: 尤佳莉;喬楠楠;劉學(xué);齊衛(wèi)寧
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院聲學(xué)研究所;上海尚恩華科網(wǎng)絡(luò)科技股份有限公司;北京中科海力技術(shù)有限公司
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46
• 代理公司: 北京方安思達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11472
• 代理人: 王宇楊;楊青

本發(fā)明涉及一種面向可分割任務(wù)的粒子群調(diào)度方法，包括：將待調(diào)度的任務(wù)分割為子任務(wù)后，以隨機(jī)產(chǎn)生的任務(wù)分配方案作為一個(gè)粒子，以任務(wù)分配方案對(duì)應(yīng)的時(shí)間性能作為粒子的適應(yīng)度，以粒子適應(yīng)度之間的差值計(jì)算粒子之間相互移動(dòng)的速度，對(duì)粒子群做多次進(jìn)化，從多次進(jìn)化的結(jié)果中選出適應(yīng)度最好的粒子；最后結(jié)合開銷值，對(duì)適應(yīng)度最好的粒子所對(duì)應(yīng)的任務(wù)分配方案中的各個(gè)子任務(wù)做子任務(wù)調(diào)度。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，特別涉及一種面向可分割任務(wù)的粒子群調(diào)度方法。

背景技術(shù)

常見的任務(wù)調(diào)度方法有多種，其中一部分方法是將任務(wù)視為不可拆分的整體進(jìn)行調(diào)度，這類方法可列舉如下：

Min-Min算法首先預(yù)測(cè)出當(dāng)前任務(wù)隊(duì)列中每一個(gè)任務(wù)在各個(gè)處理器上的最小完成時(shí)間，然后將具有最小完成時(shí)間的任務(wù)分配給相應(yīng)的處理器，同時(shí)更新相應(yīng)的處理器的就緒時(shí)間，將被分配的任務(wù)從任務(wù)隊(duì)列移去，如此重復(fù)分配剩余的任務(wù)，直至整個(gè)任務(wù)隊(duì)列為空。Min-Min算法易出現(xiàn)負(fù)載不均衡現(xiàn)象。

Max-Min算法與Min-Min算法不同之處在于，在確定了每個(gè)任務(wù)在各個(gè)處理器上的最早完成時(shí)間之后，將具有最大的最早完成時(shí)間的任務(wù)分配給相應(yīng)的處理器，并及時(shí)更新相應(yīng)的處理器就緒時(shí)間，對(duì)于剩下的任務(wù)進(jìn)行重復(fù)處理。Max-Min算法在負(fù)載均衡方面比Min-Min算法有所改善。

Promethee算法在任務(wù)端，根據(jù)用戶自定義的標(biāo)準(zhǔn)(例如任務(wù)規(guī)模、在當(dāng)前處理器上的預(yù)測(cè)執(zhí)行用時(shí)、花銷等指標(biāo)中的一種，也可以是將多種指標(biāo)進(jìn)行加權(quán)處理得到的綜合性能指標(biāo))將待執(zhí)行的任務(wù)進(jìn)行優(yōu)先級(jí)排序；在處理器端，實(shí)時(shí)監(jiān)控機(jī)器狀態(tài)，一旦有機(jī)器出現(xiàn)空閑狀態(tài)，便根據(jù)事先得到的任務(wù)優(yōu)先級(jí)排序?qū)?yōu)先級(jí)最高的任務(wù)分配到當(dāng)前空閑的機(jī)器上去。仿真表明，適當(dāng)?shù)卣{(diào)整各個(gè)性能指標(biāo)之間的權(quán)值，可使算法實(shí)現(xiàn)多方面的性能最優(yōu)。

另有一些方法提出將任務(wù)分割為多個(gè)子任務(wù)進(jìn)行逐個(gè)調(diào)度，但是分析的任務(wù)對(duì)象僅限于某一個(gè)具體任務(wù)，并沒有涉及到大批量任務(wù)同時(shí)出現(xiàn)、多種分割方式并存的情形，這類方法可列舉如下：

對(duì)時(shí)序相關(guān)子任務(wù)并行調(diào)度的遺傳算法首先分析了子任務(wù)之間的時(shí)序要求，對(duì)所有子任務(wù)執(zhí)行時(shí)的時(shí)間深度值進(jìn)行排序。然后隨機(jī)生成若干種“子任務(wù)-節(jié)點(diǎn)”分配矩陣，每一種“子任務(wù)-節(jié)點(diǎn)”矩陣即為一種分配方案。算法的思路是隨機(jī)生成若干種分配方案構(gòu)成初始種群，并對(duì)種群中的個(gè)體進(jìn)行變異和篩選操作，使之逐代改進(jìn)，從而得到新的、完成時(shí)間更短的方案。經(jīng)過很多代遺傳算法之后，可以得出穩(wěn)定的、較優(yōu)的解。但是遺傳算法的復(fù)雜度較高，在網(wǎng)絡(luò)中任務(wù)總數(shù)較多的情況下會(huì)造成很大的計(jì)算時(shí)延。

EDTS算法是針對(duì)一個(gè)任務(wù)內(nèi)部的N步子任務(wù)進(jìn)行最優(yōu)調(diào)度的方法，算法首先預(yù)測(cè)出各個(gè)子任務(wù)在所有機(jī)器上執(zhí)行所花費(fèi)的時(shí)間及能耗，然后為這一連串任務(wù)設(shè)定了總截止時(shí)間，在固定的總截止時(shí)間下，結(jié)合已有的時(shí)序關(guān)系，找出盡可能節(jié)能的子任務(wù)分配方式，但EDTS算法只是針對(duì)一個(gè)任務(wù)進(jìn)行拆分、調(diào)度，實(shí)現(xiàn)的是一個(gè)任務(wù)自身的性能最優(yōu)，當(dāng)網(wǎng)絡(luò)中出現(xiàn)大量媒體任務(wù)時(shí)，子任務(wù)之間由于時(shí)序約束造成的相互等待時(shí)長(zhǎng)較長(zhǎng)，每個(gè)任務(wù)的局部最優(yōu)與整體的優(yōu)化是矛盾的。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)中的子任務(wù)調(diào)度方法復(fù)雜度高、計(jì)算時(shí)延大、能耗高等缺陷，從而提供一種綜合衡量時(shí)間、能耗的子任務(wù)調(diào)度方法。

為了實(shí)現(xiàn)上述目的，本發(fā)明提供了一種面向可分割任務(wù)的粒子群調(diào)度方法，包括：

將待調(diào)度的任務(wù)分割為子任務(wù)后，以隨機(jī)產(chǎn)生的任務(wù)分配方案作為一個(gè)粒子，以任務(wù)分配方案對(duì)應(yīng)的時(shí)間性能作為粒子的適應(yīng)度，以粒子適應(yīng)度之間的差值計(jì)算粒子之間相互移動(dòng)的速度，對(duì)粒子群做多次進(jìn)化，從多次進(jìn)化的結(jié)果中選出適應(yīng)度最好的粒子；最后結(jié)合開銷值，對(duì)適應(yīng)度最好的粒子所對(duì)應(yīng)的任務(wù)分配方案中的各個(gè)子任務(wù)做子任務(wù)調(diào)度。

上述技術(shù)方案中，該方法具體包括：