【正文】 最后，感謝四年的大學(xué)生活，感謝我的家人和那些永遠(yuǎn)也不能忘記的朋友，他們的支持與鼓勵(lì)，是我永遠(yuǎn)的財(cái)富。 其次，感謝那些一起學(xué)習(xí)、交流的同學(xué)，他們給了我很多寶貴的建議，讓我能更全面更深入的思考問題，繼而解決問題。在對畢業(yè)設(shè)計(jì)相關(guān)知識(shí)的學(xué)習(xí)過程中，他們給了我很多的幫助，真正意義上的把我?guī)нM(jìn)網(wǎng)格計(jì)算這個(gè)領(lǐng)域，使我受益匪淺。感謝指導(dǎo)我畢業(yè)論文的李肯立老師和唐小勇老師，是他們促成了本次論文的順利完成。而所有的這一切都為我以后的學(xué)習(xí)、工作打下了堅(jiān)實(shí)的基礎(chǔ)。 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 22 頁致 謝我的畢業(yè)設(shè)計(jì)即將完成，至此，四年的大學(xué)生活即將成為過去。調(diào)度算法是網(wǎng)格計(jì)算的核心,截至目前在此方面已有人研究出一些很好的算法。隨著科學(xué)計(jì)算的日趨復(fù)雜,大型科學(xué)與工程項(xiàng)目的組織與實(shí)施都面臨著大量異構(gòu)計(jì)算資源、多信息系統(tǒng)之間的協(xié)作與交互，網(wǎng)格技術(shù)不可或缺。兩算法的調(diào)度結(jié)果在 SimGrid網(wǎng)格模擬器中仿真調(diào)度，仿真成功并且調(diào)度結(jié)果在可靠性和性能 HRDS 都比 HEFT 算法要好。為研究算法，我們引進(jìn)了調(diào)度模型 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 21 頁數(shù)字化現(xiàn)實(shí)問題，然后研究并實(shí)現(xiàn)了 HEFT 算法，通過分析總結(jié)其優(yōu)劣，對 HRDS 算法進(jìn)行改進(jìn)。網(wǎng)格技術(shù)是當(dāng)前計(jì)算機(jī)科學(xué)的熱點(diǎn)之一。網(wǎng)格系統(tǒng)適合執(zhí)行計(jì)算密集型的并行和分布式應(yīng)用程序。仿真結(jié)果驗(yàn)證了 HRDS 算法的正確性，并證明了其調(diào)度結(jié)果比 HEFT 算法性能更好，可靠性更高。 本章總結(jié)本章介紹了常見的網(wǎng)格模擬器，從中選擇 SimGrid 作為本項(xiàng)目的模擬器。調(diào)度結(jié)果顯示，分層可靠性驅(qū)動(dòng)調(diào)度（HRDS）算法的調(diào)度結(jié)果在調(diào)度長度（完成時(shí)間）和系統(tǒng)的可靠性方面要優(yōu)于 HEFT網(wǎng)格調(diào)度算法。2 4 6 810應(yīng) 用 程 序 個(gè) 數(shù)可靠性 HEFTHRDS 2 4 6 810應(yīng) 用 程 序 個(gè) 數(shù)完成時(shí)間 HEFTHRDS圖表 圖表 CCR=2 時(shí) HRDS 和 HEFT 算法調(diào)度結(jié)果的性能如圖表 和圖表 所示。410?5 仿真結(jié)果CCR= 時(shí) HRDS 和 HEFT 算法調(diào)度結(jié)果的性能如圖表 和圖表 所示。鏈路的傳輸速率假定分布在 500000000 和 2022000000 之間。各 VN 包含 3，4，5 等不同數(shù)量處理器。模擬的網(wǎng)格環(huán)境由 5 個(gè) VN 和一個(gè)網(wǎng)格全局服務(wù)器組成。為突出比較的有效性，我們使用隨機(jī)生成的應(yīng)用任務(wù)圖每個(gè)應(yīng)用程序 DAG 包含 40 個(gè)任務(wù)。 仿真 安裝好模擬器，我們需要設(shè)置好仿真參數(shù)，然后就可以對調(diào)度結(jié)果進(jìn)行仿真調(diào)度。有兩種方法將程序和 SimGrid 庫鏈接起來： 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 18 頁? 如果使用的是靜態(tài)庫： gcc o MainProgram 在這種情況下，所有的 SimGrid 函數(shù)都直接包含進(jìn)了 MainProgram，因此二進(jìn)制文件就比較大。SD_exit ()。SD_task_schedule (task,workstation_nb, workstation_list,putation_amount,munication_amount, rate)。SD_task_create (name,data,amount)。 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 17 頁SD_init((amp。SimDag 是在 SURF 之上建立的來處理 DAG 圖的實(shí)現(xiàn)。但是版本 3 中應(yīng)用了新的核心（SURF），DAG 部分（SG）被移除掉。 。 SimGrid版本 分為四個(gè)功能塊：MSG、GRAS、SMPI 和 SimGrid。SimGrid 是由美國加州大學(xué)圣地亞哥分校網(wǎng)格研究和創(chuàng)新實(shí)驗(yàn)室（Grid Research And Innovation Laboratory）主導(dǎo)開發(fā)的，主要研究網(wǎng)格中分布并行應(yīng)用調(diào)度。EDGSim用來模擬歐洲數(shù)據(jù)網(wǎng)格的性能，但是更注重于調(diào)度算法的優(yōu)化問題，主要用來研究數(shù)據(jù)的局部性原理在調(diào)度決策過程中的重要性問題。GridSim 通過資源的“買”和“賣 ”來引入“ 經(jīng)濟(jì)模型” ，從而達(dá)到控制網(wǎng)格資源的使用的目的。SimGrid 是為在網(wǎng)格環(huán)境下進(jìn)行分布并行應(yīng)用調(diào)度研究提供一個(gè)合適的模型和抽象（level of abstraction）并生成準(zhǔn)確的模擬結(jié)果。Bricks 是一個(gè)對高性能廣域計(jì)算環(huán)境中的各種調(diào)度方案進(jìn)行分析和比較的性能評價(jià)系統(tǒng)。通過配置參數(shù)，可以更加真實(shí)的模擬出現(xiàn)實(shí)環(huán)境中的各種應(yīng)用場景，使得模擬結(jié)果更具真實(shí)性；通過分析在模擬器上試驗(yàn)的結(jié)果， 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 16 頁我們可以不斷的改進(jìn)設(shè)計(jì)。在網(wǎng)格任務(wù)調(diào)度的研究中采用一個(gè)實(shí)際的網(wǎng)格環(huán)境是沒有必要的，而往往采用網(wǎng)格模擬器 [10]來完成。相對 HEFT，HRDS 算法把可靠性開銷納入調(diào)度依據(jù)，并且采用本地和全局的層次式調(diào)度，旨在提高調(diào)度結(jié)果的性能和可靠性。為研究算法我們制定了調(diào)度模型，我們用有向無環(huán)圖（DAG）表示一個(gè)應(yīng)用程序，用無向圖表示網(wǎng)格中計(jì)算機(jī)網(wǎng)絡(luò)，并且把本地局域網(wǎng)絡(luò)虛擬為一個(gè)節(jié)點(diǎn)（VN） 。HRDS 全局可靠性驅(qū)動(dòng)調(diào)度的算法如表 所示。xVNi網(wǎng)格計(jì)算系統(tǒng)中從全局服務(wù)器到目的本地 服務(wù)器經(jīng)過路徑 。 是 和 之間的信道 的可用帶寬， 是)(,yxVLwxNyVyxVL, yxVL,?的故障率。因此，VL 的可靠性是應(yīng)用程序可靠性的一個(gè)關(guān)鍵組成 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 14 頁部分。選擇對于 最小 的處理器 。表 本地可靠性驅(qū)動(dòng)調(diào)度算法1 計(jì)算任務(wù)的平均計(jì)算量和平均通信量2 計(jì)算所有任務(wù)的 RRank 值3 按 RRank 非增順序,排序調(diào)度列表中的任務(wù)4 while 調(diào)度列表不為空 do 5 從調(diào)度列表刪除第一個(gè)任務(wù) jv6 for 處理器組 P 中每個(gè)處理器 do np7 用公式()計(jì)算最早完成時(shí)間 ),(nipvEFT8 用公式()計(jì)算的處理器 上任務(wù) 的可靠性概率nj9 用公式()計(jì)算系統(tǒng)任務(wù)開銷 ,niLC10 endfor11 搜索最小 的處理器),(nipvLCmp12 把任務(wù) 分配到處理器 j13 endwhile其中，RRank 值的計(jì)算方法和 HEFT 算法中的相同。應(yīng)用程序 在虛擬節(jié)點(diǎn)網(wǎng)絡(luò) 上的最早開始時(shí)間和結(jié)束時(shí)間表示如下：iAxVN ),(),(pvESTAESTentryxi?（） ),(),(pvFVNFexitxi（） 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 13 頁 算法流程 本地可靠性驅(qū)動(dòng)的調(diào)度本地可靠性驅(qū)動(dòng)的調(diào)度算法目的是通過把任務(wù)可靠性開銷納入調(diào)度，實(shí)現(xiàn)高可靠性，縮短完成時(shí)間。HRDS 算法進(jìn)行層次式調(diào)度，分為本地可靠性驅(qū)動(dòng)的調(diào)度和全局可靠性驅(qū)動(dòng)調(diào)度。調(diào)度到虛擬節(jié)點(diǎn) 的應(yīng)用xVN程序 的可靠性概率，等于其結(jié)束任務(wù)的可靠性概率，表示如下：iA ][][,exitxi vVNAER?（） 層次調(diào)度HEFT 算法把網(wǎng)格作為一個(gè)整體作為調(diào)度對象，并沒有考慮到網(wǎng)格中局域網(wǎng)絡(luò)和廣域網(wǎng)絡(luò)的網(wǎng)絡(luò)層次帶來的問題。我們假設(shè) 和 在同一處理器調(diào)度時(shí)，任務(wù)npijv間的通信開銷變?yōu)榱?，?shù)據(jù)傳輸是無故障的。例如， 表示處理器 故障i?ip率， 表示通信鏈路 的失敗率。HRDS 在 HEFT 算法的基礎(chǔ)上考慮了可靠性，把保證可靠性的開銷也納入調(diào)度依據(jù)。以下兩種情況可能會(huì)出現(xiàn)：第一，可靠性要求較高的應(yīng)用程序運(yùn)行在一個(gè)較低的可靠性水平，從而導(dǎo)致應(yīng)用程序故障。 可靠性HEFT 算法單純以最早完成時(shí)間為調(diào)度依據(jù)，選擇任務(wù) 最早完成時(shí)間最小的主機(jī)，iv調(diào)度結(jié)果有較高的性能。HEFT 算法很好，但仍有不足。在研究的所有方法中，均值是的最適當(dāng)?shù)姆椒?。文獻(xiàn)[9]研究了不同權(quán)值分配方法的影響。 np),(nipvEFT該算法的偽代碼如表 所示。對于結(jié)束任務(wù) ，RRank 值等于：exitv )()(exitexitvwRank?（）處理器選擇階段：按順序處理任務(wù)，從輸入滿足開始搜索任務(wù)在處理器上的空閑時(shí)間，直到找到能夠容納任務(wù)計(jì)算量的時(shí)間片。RRank 的遞減順序提供了任務(wù)的拓?fù)漤樞?，并滿足運(yùn)行的約束。通過平均計(jì)算量和 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 10 頁平均通信量計(jì)算 RRank 值，再由 RRank 得出優(yōu)先級。表 變量的定義 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 9 頁變量名 定義 第 i 個(gè)應(yīng)用程序iA 第 i 個(gè)任務(wù)v 任務(wù) 的計(jì)算量)(iwiv 任務(wù) 的平均計(jì)算量 第 i 個(gè)