【文章內(nèi)容簡(jiǎn)介】 器根據(jù)目標(biāo)函數(shù)和資源性能從資源集中選擇合適的資源分配給當(dāng)前作業(yè)，形成一個(gè)調(diào)度集。性能評(píng)估模型綜合考慮作業(yè)和資源的性能指標(biāo)，選出總體性能最好的調(diào)度方案；4)網(wǎng)格調(diào)度器將作業(yè)傳送到所選資源執(zhí)行，完成作業(yè)到資源的映射。作業(yè)的執(zhí)行過(guò)程中，調(diào)度器負(fù)責(zé)搜集作業(yè)的執(zhí)行狀態(tài)，將作業(yè)執(zhí)行狀態(tài)信息反饋給用戶；作業(yè)執(zhí)行完成后，調(diào)度器負(fù)責(zé)返回用戶執(zhí)行結(jié)果；網(wǎng)格調(diào)度算法 [7]主要完成第三步的工作。當(dāng)前已有很多網(wǎng)格調(diào)度算法，如 HEFT 算法和 RDLS 算法。異態(tài)最早完成時(shí)間 HEFT 算法有較高的效率，它有兩個(gè)階段: 權(quán)值分配階段和任務(wù)分配階段?？煽啃詣?dòng)態(tài)水平調(diào)度 RDLS 算法是在 DLS 的基礎(chǔ)上把資源的可靠性納入調(diào)度標(biāo)準(zhǔn)。RDLS 算法在獲得良好的性能的同時(shí)滿足應(yīng)用的可靠性要求。 調(diào)度模型為了實(shí)現(xiàn)算法調(diào)度，需要把現(xiàn)實(shí)問(wèn)題數(shù)字化，我們必須為任務(wù)和網(wǎng)格環(huán)境建模 [8]。 任務(wù)模型在我們的任務(wù)模型中，K 個(gè)應(yīng)用程序（ 和 …… ）是相互獨(dú)立的，每個(gè)應(yīng)用1A2k 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 7 頁(yè)程序由有優(yōu)先約束的 40 個(gè)任務(wù)組成。每個(gè)網(wǎng)格的應(yīng)用程序由有向無(wú)環(huán)圖（DAG）表示，其中 V 是 v 個(gè)可在任何可用的處理器上執(zhí)行的任務(wù)； 是???EVG, VE??代表任務(wù)之間依賴關(guān)系的有向邊。例如，邊 說(shuō)明任務(wù) 應(yīng)在任務(wù) 執(zhí)行前運(yùn)行Eeji?, ivjv完。一個(gè)任務(wù)可以有一個(gè)或多個(gè)輸入。當(dāng)一個(gè)任務(wù)所有的輸入都滿足時(shí)，該任務(wù)就觸發(fā)執(zhí)行。執(zhí)行后，它會(huì)產(chǎn)生輸出。 代表任務(wù) 的計(jì)算量， 代表邊 的通)(ivwi )(,jiewjie,信量。任務(wù) 的前繼節(jié)點(diǎn)的集合用 表示。任務(wù) 的后繼節(jié)點(diǎn)的集合用iviprediv表示。開(kāi)始的任務(wù)沒(méi)有前繼的節(jié)點(diǎn)。結(jié)束任務(wù)沒(méi)有后繼節(jié)點(diǎn)。我們假設(shè) DAG)(isuc正好有一個(gè)開(kāi)始任務(wù) 和一個(gè)結(jié)束任務(wù) 。圖 顯示了一個(gè)分配了任務(wù)和邊的權(quán)entryvexitv值的 DAG 例子。 圖 DAG 圖DAG 的調(diào)度就是確定 DAG 中的每個(gè)任務(wù)開(kāi)始運(yùn)行的時(shí)間及運(yùn)行的處理器。為了 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 8 頁(yè)描述調(diào)度，我們用 的表示任務(wù) 在處理器 上的最早開(kāi)始時(shí)間，其最早完,nipvESTivnp成時(shí)間為： )(/),(),( ninini pwvpESTpvF??（）對(duì)于開(kāi)始任務(wù)， 等于處理器 上已調(diào)度的其他任務(wù)的最早完成時(shí)間。),(rypvESTnp此外， 分配的處理器表示為 。iv(ivoc 系統(tǒng)模型在網(wǎng)格計(jì)算的系統(tǒng)中，按位置分布的計(jì)算機(jī)群通過(guò)廣域網(wǎng)互連。我們虛擬一個(gè)本地局域網(wǎng)絡(luò)的計(jì)算機(jī)群為一個(gè)節(jié)點(diǎn)（VN） ，它包含許多不同的處理能力的計(jì)算資源，如計(jì)算能力為 的處理器 ，及存儲(chǔ)器、程序等。采用非搶占規(guī)則共享計(jì)算資源，)(npwnp一旦任務(wù)開(kāi)始在處理器上運(yùn)行，它不能被停止，必須在處理器上完成。每個(gè) VN 有一個(gè)本地服務(wù)器，負(fù)責(zé)收集 VN 中所有機(jī)器的信息。每個(gè)本地服務(wù)器資源管理系統(tǒng)包含一個(gè)次級(jí)調(diào)度器，這負(fù)責(zé)將應(yīng)用程序的任務(wù)調(diào)度到各主機(jī)上。兩個(gè) VN 之間的直接通信頻道被定義為一個(gè)虛擬鏈路（VL） ，可以代表不僅是物理鏈路，也是一個(gè)邏輯鏈路。虛擬化可以簡(jiǎn)化網(wǎng)格中數(shù)以千計(jì)的物理計(jì)算資源和電纜的模型。全局服務(wù)器，負(fù)責(zé)收集所有VN 和終端使用者的信息。全局服務(wù)器資源管理系統(tǒng)具有全局調(diào)度器，全局調(diào)度器負(fù)責(zé)調(diào)度任務(wù)到 VN。在我們的網(wǎng)格計(jì)算系統(tǒng)模型中，虛擬節(jié)點(diǎn)由各種的計(jì)算資源完全連接起來(lái)，并由一個(gè)無(wú)向圖建模 ，其中 P 是 p 個(gè)頂點(diǎn)的有限集合，L 是 l 條無(wú)向邊的有限???LGT,集合。點(diǎn) 代表處理器 i，無(wú)向邊 代表處理器 和 間的雙向通信鏈路， 代ipjil, ijp)(ipw表處理器 的計(jì)算速度， 代表 的帶寬。我們假設(shè)處理器間的所有通信無(wú)競(jìng)爭(zhēng)，i )(,jiwji,而且調(diào)度在同一處理器的兩個(gè)任務(wù)間的通信開(kāi)銷看作為零。本文中用到的變量定義總結(jié)如表 。表 變量的定義 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 9 頁(yè)變量名 定義 第 i 個(gè)應(yīng)用程序iA 第 i 個(gè)任務(wù)v 任務(wù) 的計(jì)算量)(iwiv 任務(wù) 的平均計(jì)算量 第 i 個(gè)任務(wù)到第 j 個(gè)任務(wù)的有向邊jie, 邊 的通信量)(, jie, 邊 的平均通信量,ji , 任務(wù) 的后繼任務(wù)vsuciv 任務(wù) 的前任任務(wù))(ipred 虛擬節(jié)點(diǎn)的第 i 個(gè)任務(wù)i 處理器 的運(yùn)算速度wip 任務(wù) 在處理器 的最早開(kāi)始時(shí)間),(nivESTvn 任務(wù) 在處理器 的最早完成時(shí)間pFi 應(yīng)用程序 在 上的最早開(kāi)始時(shí)間 ,xiVNAiAxVN 應(yīng)用程序 在 上的最早完成時(shí)間 )( 處理器 的故障率i?ip 鏈路 的故障率jil, jl, 虛擬鏈路 的故障率yxVL, yxVL, 任務(wù) 的可靠性][ivERiv 通信邊 的可靠性,jie je, 上 的虛擬節(jié)點(diǎn)的可靠性VNAxi xNiA 上 的虛擬鏈路的可靠性][,Lyi yVL, 上 的可靠性xiVERxi 任務(wù) 的 RRank 值)(vankv 任務(wù) 在處理器 上的系統(tǒng)任務(wù)開(kāi)銷,ipCinp 應(yīng)用程序的可靠性開(kāi)銷][xNA 系統(tǒng)開(kāi)銷 ,iS HEFT異構(gòu)環(huán)境最早結(jié)束時(shí)間算法(HEFT)有 2 個(gè)階段：任務(wù)優(yōu)先級(jí)排序階段和處理器選擇階段。任務(wù)優(yōu)先級(jí)排序階段：這個(gè)階段需要每個(gè)任務(wù)的優(yōu)先級(jí)。通過(guò)平均計(jì)算量和 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 10 頁(yè)平均通信量計(jì)算 RRank 值，再由 RRank 得出優(yōu)先級(jí)。排列任務(wù)的 RRank 得出任務(wù)列表，相同 RRank 隨機(jī)順序。RRank 的遞減順序提供了任務(wù)的拓?fù)漤樞?，并滿足運(yùn)行的約束。RRank 的遞歸定義： )}()({max)(,)( jjivsucii vRankewvwRankij ????（）RRank 是由從開(kāi)始任務(wù)向上遍歷任務(wù)圖遞歸計(jì)算的。對(duì)于結(jié)束任務(wù) ，RRank 值等于：exitv )()(exitexitvwRank?（）處理器選擇階段：按順序處理任務(wù)，從輸入滿足開(kāi)始搜索任務(wù)在處理器上的空閑時(shí)間，直到找到能夠容納任務(wù)計(jì)算量的時(shí)間片。基于區(qū)間插入技術(shù)將任務(wù) 分配給處iv理器 得到最早完成時(shí)間 ，將任務(wù)分配給最早完成時(shí)間最小的處理器。 np),(nipvEFT該算法的偽代碼如表 所示。表 HEFT 算法1 計(jì)算得到平均計(jì)算量和平均通信量2 計(jì)算 RRank3 遞減順序排序 RRank4 while 有任務(wù) do5 選擇任務(wù) iv6 for 每個(gè)處理器 dokp7 計(jì)算 ),(iEFT8 Endfor9 分配任務(wù) 到使 最小的處理器iv,kivkp10 endwhile 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 11 頁(yè) 分析改進(jìn)在網(wǎng)格的本地虛擬節(jié)點(diǎn)中，同一任務(wù)在不同處理器上有不同的計(jì)算開(kāi)銷，這導(dǎo)致一個(gè)問(wèn)題：使用某處理器上任務(wù)的計(jì)算開(kāi)銷來(lái)計(jì)算優(yōu)先級(jí)，可能不同于在另一處理器的優(yōu)先級(jí)。文獻(xiàn)[9]研究了不同權(quán)值分配方法的影響。在研究中，作者比較不同的方法，如平均值、中值、最佳值、最差值等，結(jié)果表明完成時(shí)間有明顯差異。在研究的所有方法中，均值是的最適當(dāng)?shù)姆椒?。HEFT 算法使用了平均值作為任務(wù)的計(jì)算開(kāi)銷來(lái)計(jì)算RRank。HEFT 算法很好，但仍有不足。在本項(xiàng)目中我們提出了 HRDS 算法，在 HRDS算法中我們用和 HEFT 算法相同的方法來(lái)計(jì)算 RRank 并確定優(yōu)先級(jí)。 可靠性HEFT 算法單純以最早完成時(shí)間為調(diào)度依據(jù)，選擇任務(wù) 最早完成時(shí)間最小的主機(jī)，iv調(diào)度結(jié)果有較高的性能。HEFT 是把整個(gè)網(wǎng)格對(duì)象看成一個(gè)整體，并沒(méi)有考慮到現(xiàn)實(shí)網(wǎng)格中的可靠性問(wèn)題。以下兩種情況可能會(huì)出現(xiàn)：第一，可靠性要求較高的應(yīng)用程序運(yùn)行在一個(gè)較低的可靠性水平，從而導(dǎo)致應(yīng)用程序故障。第二，低可靠性的應(yīng)用程序運(yùn)行在高可靠性水平，這可能導(dǎo)致差的性能。HRDS 在 HEFT 算法的基礎(chǔ)上考慮了可靠性，把保證可靠性的開(kāi)銷也納入調(diào)度依據(jù)。系統(tǒng)中處理器和網(wǎng)絡(luò)鏈路都有有一個(gè)固定的故障率。例如， 表示處理器 故障i?ip率， 表示通信鏈路 的失敗率。任務(wù) 可靠性等于其從前繼任務(wù)成功傳輸數(shù)據(jù)的3,1l?3,1ljv概率乘以處理器 成功執(zhí)行任務(wù)的概率。我們假設(shè) 和 在同一處理器調(diào)度時(shí)，任務(wù)npijv間的通信開(kāi)銷變?yōu)榱?，?shù)據(jù)傳輸是無(wú)故障的。任務(wù) 的可靠性記為 ，定義為：j ]