[發明專利]基于可靠性和非合作博弈的計算網格任務調度方法

有效

• 申請號: 201210158071.5
• 申請日: 2012-05-21
• 公開（公告）號: CN102736955A
• 公開（公告）日: 2012-10-17
• 發明（設計）人: 王勇;李凱;劉美林
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 樓艮基

技術領域

本發明涉及網格計算領域，特別是網格任務調度領域的一種調度方法。?

背景技術

任務調度是網格計算的核心研究內容。計算網格作為一種特殊的網格形式，它的資源主要是具有高性能計算能力的網格計算節點和網絡資源，其任務調度研究的是如何把用戶的計算密集型的任務通過網絡資源合理分配到具有高性能計算能力的網格計算節點上執行，以使得任務得到均衡的分配或使得每個任務的執行代價降到最低或使得系統總體的性能得到最優。?

近年來，服務質量感知的計算網格任務調度問題成為計算網格任務調度的一個新的研究方向，網格用戶不僅要求網格系統滿足任務的功能性需求，而且關注任務的服務質量，如He等首先把服務質量信息嵌入到Min-min調度算法中，對服務質量感知的網格任務調度問題做了開創性工作；Subrata等以任務處理時間作為目標，給出了一種基于非合作博弈的計算網格任務均衡調度模型，并把基于任務處理時間的計算網格作業分配問題建模為一個合作博弈，給出了納什討價還價解的結構。以上網格任務調度研究工作，采用了不同的思路，利用了不同的數學工具，取得了較好的研究成果，但存在一個共同點：任務調度以處理時間為依據，把任務分片在網格計算節點上的處理時間或任務的總處理時間作為優化調度的目標，都沒有考慮可靠性這一要素在網格任務調度中所起的作用。?

發明內容

不同于以往任務調度以時間為依據，把任務分片在網格計算節點上的處理時間或任務的總處理時間作為優化目標的調度方法，本發明的目的是將可靠性，即計算能力提供的穩定性作為網格任務調度考慮的主要因素，以各用戶的任務在網格計算節點上穩定狀態的提供能力為目標，以各用戶的任務在網格計算節點上的分片策略為博弈策略，確定網格系統中各個調度器的任務分片方案。?

本發明的特征在于含有以下步驟：?

步驟（1），構造一個基于可靠性和非合作博弈的計算網格系統：?

所述基于可靠性和非合作博弈的計算網格系統由用戶、面向各用戶的各調度器i以及面向各調度器i的網格計算節點j以及調度方案計算器組成，其中i=1,2，..,n，n為所述系統中所有調度器的數目，j=1,2，...,m，m為所述系統中所有網格計算節點的數目；?

在忽略調度器內部處理代價、任務傳輸時間下，所述調度器在進行任務分片時的可靠性條件如下：?

各個調度器從各用戶接受任務，各個調度器發出任務的平均速率λ_i的加和應該小于所述系統所有網格計算節點對任務的平均執行速率u_j的加和，速率的單位是單位時間內的任務數，下同：?

Σi=1nλi＜Σj=1muj---(1)]]>

；?

各個所述調度器發到第j個所述網格計算節點上任務分片的速率的加和應該小于第j個所述網格計算節點對所述任務分片的執行速率u_j，即計算能力：?

Σi=1nλiaij＜uj---(2)]]>