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

有效

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

1.一種面向可分割任務的粒子群調度方法，包括：

將待調度的任務分割為子任務后，以隨機產生的任務分配方案作為一個粒子，以任務分配方案對應的時間性能作為粒子的適應度，以粒子適應度之間的差值計算粒子之間相互移動的速度，對粒子群做多次進化，從多次進化的結果中選出適應度最好的粒子；最后結合開銷值，對適應度最好的粒子所對應的任務分配方案中的各個子任務做子任務調度；

該方法具體包括：

步驟1)、收集待調度任務的指令條數、分割后的多個子任務的指令條數、子任務之間的時序依賴關系，各任務的文件塊大小；

步驟2)、采集集群中各個服務器的運行速度MIPS、單位時間電費開銷CPS、當前負載、最早空閑時刻EST，計算服務器之間的帶寬信息；

步驟3)、將隊列中的待調度任務按照指令條數進行降序排序，對于隊首的待調度任務，依次執(zhí)行步驟4)—步驟10)，直至隊列中的所有待調度任務均被處理完成；

步驟4)、對當前的待調度任務進行分解，得到子任務結構圖，并為所述待調度任務隨機產生N個分配方案，形成初始種群；

其中，所述子任務結構圖反映了待調度任務被分解為子任務之前的時序關系；

所述初始種群包括隨機生成的N個粒子P₁,P₂,...P_N，每一個粒子代表一個“任務—服務器”分配方案，若服務器的總數為M，則每個粒子P_n表示為一個L*M矩陣S_n：其中，1≤n≤N，N的大小根據集群中的服務器數目、待調度任務中包含的子任務數目來設定，L表示待調度任務分解后所得到的子任務的個數；

Task_j為第j個子任務，Server_k為第k個服務器；

步驟5)、計算N個粒子的時間跨度Makespan，得出N個粒子的適應度；

步驟6)、計算粒子在新一輪迭代中的移動速度，將每個粒子進行一次進化，得到下一代粒子群；

步驟7)、判斷當前的進化次數是否小于預設值，若是，重新執(zhí)行步驟5)，否則，執(zhí)行步驟8)；

步驟8)、從之前所有的進化結果中篩選出適應度最高的粒子P_best；

步驟9)、設置開銷性能對應的權值P，進行基于開銷Cost的任務遷移；

步驟10)、輸出步驟9)的任務遷移結果，按此結果進行子任務調度。

2.根據權利要求1所述的面向可分割任務的粒子群調度方法，其特征在于，在步驟5)中，根據如下原則計算時間跨度Makespan：

a、子任務的開始時刻須在其所有前驅子任務的結束時刻之后；

b、子任務須接收其所有前驅子任務的輸出文件作為其輸入文件；

c、子任務須在當前所在處理器空閑狀態(tài)下開始；

d、子任務須在滿足上述條件a-c條件的情況下盡早開始；

e、子任務Task_j執(zhí)行所需時間為Task_MI_j/MIPS_k；Task_MI_j為第j個子任務Task_j的指令條數；MIPS_k為Server_k每秒運行的指令條數；

f、一個任務完成的時間跨度Makespan為其第一個子任務的開始時刻與最后一個子任務的結束時刻之間的時間跨度。

3.根據權利要求1所述的面向可分割任務的粒子群調度方法，其特征在于，在步驟5)中，按照下面的公式(2)計算第n個粒子的適應度Fitness_n：

Fitness_n＝max{Makespan₁,Makespan₂,...Makespan_N}-Makespan_n 式(2)

Makespan_n為第n個粒子的時間跨度，1≤n≤N。