【正文】 他們教會(huì)我的不僅僅是專業(yè)知識(shí)，更多的是對(duì)待學(xué)習(xí)、對(duì)待生活的態(tài)度。然而,隨著并行分布計(jì)算的高速發(fā)展,研究一些新的更高效的算法迫在眉睫。網(wǎng)格調(diào)度算法是網(wǎng)格計(jì)算的靈魂，決定了其性能。把可靠性開(kāi)銷納入調(diào)度依據(jù)并采用層次調(diào)度是可行的，而且使調(diào)度結(jié)果的性能和可靠性得到提高。處理器速度為310?41000000000 到 1500000000。 ? 如果使用動(dòng)態(tài)庫(kù)（推薦使用）： gcc lsimgrid o MainProgram 在這種情況下，所有的 SimGrid 函數(shù)都不直接包含進(jìn)了 MainProgram，需要設(shè)置環(huán)境變量： export LD_LIBRARY_PATH=$HOME/lib/:$LD_LIBRARY_PATH，這樣在運(yùn)行時(shí)才能找到 。argc, argv)。MSG 用來(lái)模擬簡(jiǎn)單的應(yīng)用；GRAS 用來(lái)開(kāi)發(fā)分布式應(yīng)用程序； SMPI 用來(lái)在虛擬環(huán)境中運(yùn)行 MPI程序；SimDag 用來(lái)仿真并行的 DAG 圖任務(wù)。GridSim 通過(guò)模擬來(lái)研究基于計(jì)算經(jīng)濟(jì)模型的有效資源分配方法。第四章 仿真 網(wǎng)格模擬器如何在復(fù)雜的網(wǎng)格環(huán)境中設(shè)計(jì)一個(gè)好的任務(wù)調(diào)度算法是網(wǎng)格技術(shù)研究的重點(diǎn)之一。在 上傳輸應(yīng)用 的可靠性概率定義如下 :yxVL, , iA )(/), ,][yxiyxVLyxi VLwAVLAeER????（）在 上運(yùn)行應(yīng)用 的可靠性概率可以通過(guò)公式（）計(jì)算。表 顯示了該算法的偽代碼。任務(wù) 可靠性等于其從前繼任務(wù)成功傳輸數(shù)據(jù)的3,1l?3,1ljv概率乘以處理器 成功執(zhí)行任務(wù)的概率。在本項(xiàng)目中我們提出了 HRDS 算法，在 HRDS算法中我們用和 HEFT 算法相同的方法來(lái)計(jì)算 RRank 并確定優(yōu)先級(jí)。基于區(qū)間插入技術(shù)將任務(wù) 分配給處iv理器 得到最早完成時(shí)間 ，將任務(wù)分配給最早完成時(shí)間最小的處理器。本文中用到的變量定義總結(jié)如表 。每個(gè)本地服務(wù)器資源管理系統(tǒng)包含一個(gè)次級(jí)調(diào)度器，這負(fù)責(zé)將應(yīng)用程序的任務(wù)調(diào)度到各主機(jī)上。圖 顯示了一個(gè)分配了任務(wù)和邊的權(quán)entryvexitv值的 DAG 例子。當(dāng)一個(gè)任務(wù)所有的輸入都滿足時(shí)，該任務(wù)就觸發(fā)執(zhí)行。異態(tài)最早完成時(shí)間 HEFT 算法有較高的效率，它有兩個(gè)階段: 權(quán)值分配階段和任務(wù)分配階段。網(wǎng)格計(jì)算即利用網(wǎng)格對(duì)問(wèn)題進(jìn)行處理，網(wǎng)格最根本的應(yīng)用。層次式調(diào)度方案可擴(kuò)展性較好，在任務(wù)分發(fā)器下還可再設(shè)置第三級(jí)任務(wù)分發(fā)器。上述4大功能模塊構(gòu)成了網(wǎng)格系統(tǒng)的整體框架，系統(tǒng)運(yùn)轉(zhuǎn)過(guò)程中，各個(gè)模塊相互協(xié)作，完成作業(yè)調(diào)度的任務(wù)。早期網(wǎng)格系統(tǒng)中網(wǎng)格調(diào)度器并不是必需的，隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)格調(diào)度器的引入可以使得網(wǎng)格系統(tǒng)能夠取得更好的擴(kuò)展性，網(wǎng)格調(diào)度器逐步成為網(wǎng)格系統(tǒng)不可缺少的一部分。需要消耗大量的 CPU 計(jì)算，對(duì)網(wǎng)絡(luò)流量不大，存儲(chǔ)和硬盤訪問(wèn)量不大。 網(wǎng)格計(jì)算 1990 年代提出的網(wǎng)格計(jì)算( Grid Computing)概念 , 是基于網(wǎng)格的問(wèn)題的求解。首先描述了任務(wù)模型和系統(tǒng)模型，然后介紹了 HEFT 和 HRDS 算法的特點(diǎn)和流程及 HRDS 算法的改進(jìn)。然而,隨著網(wǎng)格計(jì)算的快速發(fā)展,一些新的更好的算法必會(huì)出現(xiàn)。網(wǎng)格進(jìn)一步發(fā)展延伸，形成了如今人們最為關(guān)注的云計(jì)算。SimGrid 為在分布計(jì)算環(huán)境下進(jìn)行分布并行應(yīng)用調(diào)度研究提供一個(gè)仿真環(huán)境。相對(duì)于大型機(jī)，網(wǎng)格系統(tǒng)更適合執(zhí)行計(jì)算密集型的并行和分布式應(yīng)用程序。本課題設(shè)計(jì)深入研究并實(shí)現(xiàn) HeterogeneousEarliestFinish(HEFT)[2]算法和新的Hierarchical ReliabilityDriven Scheduling(HRDS)算法。國(guó)外包括 IBM、Microsoft、Sun 與一些公司早已將網(wǎng)格運(yùn)算加入到商用的系統(tǒng)中。異態(tài)最早完成時(shí)間 HEFT 算法有較高的效率，它有兩個(gè)階段: 任務(wù)優(yōu)先級(jí)排序階段和處理器選擇階段。 論文構(gòu)成及研究?jī)?nèi)容本論文共分五章：第一章為緒論。 網(wǎng)格 本節(jié)介紹了網(wǎng)格及網(wǎng)格計(jì)算的基本概念。網(wǎng)格計(jì)算是一種計(jì)算能力提升的方式，其原理是依據(jù)并行計(jì)算理論，通過(guò)任務(wù)分解，將子任務(wù)分布式提交到其他服務(wù)器上運(yùn)行，以獲得更強(qiáng)大計(jì)算能力。網(wǎng)格調(diào)度器主要負(fù)責(zé)接收用戶提交的作業(yè)、查詢信息服務(wù)、完成作業(yè)到資源的映射、產(chǎn)生調(diào)度結(jié)果集、將作業(yè)傳送到選定的資源具體執(zhí)行。信息服務(wù)保存整個(gè)系統(tǒng)資源的信息，為產(chǎn)生合理的調(diào)度方案提供支持。但各調(diào)度器之間的通信量很大，也不能掌握網(wǎng)格中所有資源，因而很難找到全局最優(yōu)的資源分配方式。第一層是一個(gè)主調(diào)度器；第二層由若干個(gè)次級(jí)調(diào)度器組成，主調(diào)度器并不負(fù)責(zé)直接調(diào)度任務(wù)，而是將任務(wù)分發(fā)給各次級(jí)調(diào)度器，第三層是底層的資源站點(diǎn)，具體負(fù)責(zé)完成分配的任務(wù)，并返回結(jié)果。性能評(píng)估模型綜合考慮作業(yè)和資源的性能指標(biāo)，選出總體性能最好的調(diào)度方案；4)網(wǎng)格調(diào)度器將作業(yè)傳送到所選資源執(zhí)行，完成作業(yè)到資源的映射。每個(gè)網(wǎng)格的應(yīng)用程序由有向無(wú)環(huán)圖（DAG）表示，其中 V 是 v 個(gè)可在任何可用的處理器上執(zhí)行的任務(wù)； 是???EVG, VE??代表任務(wù)之間依賴關(guān)系的有向邊。開(kāi)始的任務(wù)沒(méi)有前繼的節(jié)點(diǎn)。我們虛擬一個(gè)本地局域網(wǎng)絡(luò)的計(jì)算機(jī)群為一個(gè)節(jié)點(diǎn)（VN） ，它包含許多不同的處理能力的計(jì)算資源，如計(jì)算能力為 的處理器 ，及存儲(chǔ)器、程序等。在我們的網(wǎng)格計(jì)算系統(tǒng)模型中，虛擬節(jié)點(diǎn)由各種的計(jì)算資源完全連接起來(lái)，并由一個(gè)無(wú)向圖建模 ，其中 P 是 p 個(gè)頂點(diǎn)的有限集合，L 是 l 條無(wú)向邊的有限???LGT,集合。RRank 的遞減順序提供了任務(wù)的拓?fù)漤樞?，并滿足運(yùn)行的約束。在研究的所有方法中，均值是的最適當(dāng)?shù)姆椒?。HRDS 在 HEFT 算法的基礎(chǔ)上考慮了可靠性，把保證可靠性的開(kāi)銷也納入調(diào)度依據(jù)。HRDS 算法進(jìn)行層次式調(diào)度，分為本地可靠性驅(qū)動(dòng)的調(diào)度和全局可靠性驅(qū)動(dòng)調(diào)度。因此，VL 的可靠性是應(yīng)用程序可靠性的一個(gè)關(guān)鍵組成 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 14 頁(yè)部分。為研究算法我們制定了調(diào)度模型，我們用有向無(wú)環(huán)圖（DAG）表示一個(gè)應(yīng)用程序，用無(wú)向圖表示網(wǎng)格中計(jì)算機(jī)網(wǎng)絡(luò)，并且把本地局域網(wǎng)絡(luò)虛擬為一個(gè)節(jié)點(diǎn)（VN） 。Bricks 是一個(gè)對(duì)高性能廣域計(jì)算環(huán)境中的各種調(diào)度方案進(jìn)行分析和比較的性能評(píng)價(jià)系統(tǒng)。SimGrid 是由美國(guó)加州大學(xué)圣地亞哥分校網(wǎng)格研究和創(chuàng)新實(shí)驗(yàn)室（Grid Research And Innovation Laboratory）主導(dǎo)開(kāi)發(fā)的，主要研究網(wǎng)格中分布并行應(yīng)用調(diào)度。SimDag 是在 SURF 之上建立的來(lái)處理 DAG 圖的實(shí)現(xiàn)。SD_exit ()。模擬的網(wǎng)格環(huán)境由 5 個(gè) VN 和一個(gè)網(wǎng)格全局服務(wù)器組成。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é)果的性能如圖表 和圖表 所示。網(wǎng)格系統(tǒng)適合執(zhí)行計(jì)算密集型的并行和分布式應(yīng)用程序。隨著科學(xué)計(jì)算的日趨復(fù)雜,大型科學(xué)與工程項(xiàng)目的組織與實(shí)施都面臨著大量異構(gòu)計(jì)算資源、多信息系統(tǒng)之間的協(xié)作與交互，網(wǎng)格技術(shù)不可或缺。感謝指導(dǎo)我畢業(yè)論文的李肯立老師和唐小勇老師，是他們促成了本次論文的順利完成。最后，感謝四年的大學(xué)生活，感謝我的家人和那些永遠(yuǎn)也不能忘記的朋友，他們的支持與鼓勵(lì)，是我永遠(yuǎn)的財(cái)富。而所有的這一切都為我以后的學(xué)習(xí)、工作打下了堅(jiān)實(shí)的基礎(chǔ)。兩算法的調(diào)度結(jié)果在 SimGrid網(wǎng)格模擬器中仿真調(diào)度，仿真成功并且調(diào)度結(jié)果在可靠性和性能 HRDS 都比 HEFT 算法要好。仿真結(jié)果驗(yàn)證了 HRDS 算法的正確性，并證明了其調(diào)度結(jié)果比 HEFT 算法性能更好，可靠性更高。410?5 仿真結(jié)果CCR= 時(shí) HRDS 和 HEFT 算法調(diào)度結(jié)果的性能如圖表 和圖表 所示。為突出比較的有效性，我們使用隨機(jī)生成的應(yīng)用任務(wù)圖每個(gè)應(yīng)用程序 DAG 包含 40 個(gè)任務(wù)。SD_task_schedule (task,workstation_nb, workstation_list,putation_amount,munication_amount, rate)。但是版本 3 中應(yīng)用了新的核心（SURF），DAG 部分（SG）被移除掉。EDGSim用來(lái)模擬歐洲數(shù)據(jù)網(wǎng)格的性能，但是更注重于調(diào)度算法的優(yōu)化問(wèn)題，主要用來(lái)研究數(shù)據(jù)的局部性原理在調(diào)度決策過(guò)程中的重要性問(wèn)題。通過(guò)配置參數(shù)，可以更加真實(shí)的模擬出現(xiàn)實(shí)環(huán)境中的各種應(yīng)用場(chǎng)景，使得模擬結(jié)果更具真實(shí)性；通過(guò)分析在模擬器上試驗(yàn)的結(jié)果， 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 16 頁(yè)我們可以不斷的改進(jìn)設(shè)計(jì)。HRDS 全局可靠性驅(qū)動(dòng)調(diào)度的算法如表 所示。選擇對(duì)于 最小 的處理器 。調(diào)度到虛擬節(jié)點(diǎn) 的應(yīng)用xVN程序 的可靠性概率，等于其結(jié)束任務(wù)的可靠性概率，表示如下：iA ][][,exitxi vVNAER?（） 層次調(diào)度HEFT 算法把網(wǎng)格作為一個(gè)整體作為調(diào)度對(duì)象，并沒(méi)有考慮到網(wǎng)格中局域網(wǎng)絡(luò)和廣域網(wǎng)絡(luò)的網(wǎng)絡(luò)層次帶來(lái)的問(wèn)題。以下兩種情況可能會(huì)出現(xiàn)：第一，可靠性要求較高的應(yīng)用程序運(yùn)行在一個(gè)較低的可靠性水平，從而導(dǎo)致應(yīng)用程序故障。文獻(xiàn)[9]研究了不同權(quán)值分配方法的影響。通過(guò)平均計(jì)算量和 湖南大學(xué)畢業(yè)設(shè)計(jì)(論文) 第 10 頁(yè)平均通信量計(jì)算 RRank 值，再由 RRank 得出優(yōu)先級(jí)。全局服務(wù)器，負(fù)責(zé)收集所有VN 和終端使用者的信息。),(rypvESTnp此外， 分配的處理器表示為 。任務(wù) 的前繼節(jié)點(diǎn)的集合用 表示。 調(diào)度模型為了實(shí)現(xiàn)算法調(diào)度，需要把現(xiàn)實(shí)問(wèn)題數(shù)字化，我們必須為任務(wù)和網(wǎng)格環(huán)境建模 [8]。網(wǎng)格調(diào)度策略主要有集中式、層次式與分布式調(diào)度方案。本文主要研究基于層次式的調(diào)度模型。該調(diào)度方案擴(kuò)展性較差，當(dāng)網(wǎng)絡(luò)