資源描述：
《網(wǎng)格環(huán)境中基于dag的并行任務(wù)調(diào)度算法.研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、上海交通大學(xué)碩士學(xué)位論文ABSTRACTconsideredasschedulingtheDAG.Thecomputingabilitiesofmachinesonthegridaredifferent.Sometypesofsub-jobscanonlybescheduledtospecificmachines,andsomesub-jobscanbedistributedonseveralmachinestoaccelerateitsexecution.Inordertomeasurethisheterogeneousnessofg
2、rid,wedefinedtwoconcepts,jobandmachinecalculability.AndthispaperproposedaDAGbasedheuristic,whichutilizesthejobandmachinecalculability,andsupportsresourcereservation.Besidesdifferentcalculability,gridsuffersdifferentnetworkconnections.Networkbetweendifferentresourcedomain
3、sarerestrictedandunstable.Ourproposedanotherlistalgorithmbasedonthisproperty.Wetrytoschedulestrongrelatedtaskstothesamedomain,inordertoreducethecostofnetworkcommunication.AnextensivesimulationstudyinSimGridsimulationplatformwasconductedtoevaluateandcomparetheperformanceo
4、fthealgorithms.ItshowedthegeneralsuitabilityandbetterperformanceofourenhancedlistschedulingheuristicswithinheterogeneousGridenvironments.Keywords:GridComputing,DAG,listscheduling,SimGrid上海交通大學(xué)工程碩士學(xué)位論文攻讀碩士學(xué)位期間已發(fā)表或錄用的論文第62頁上海交通大學(xué)工程碩士學(xué)位論文攻讀碩士學(xué)位期間已發(fā)表或錄用的論文第63頁上海交通大學(xué)碩士學(xué)位論文網(wǎng)格環(huán)
5、境中基于DAG的并行任務(wù)調(diào)度算法研究第一章緒論1.1本文的研究背景網(wǎng)格正逐步成為一種新的技術(shù)和基礎(chǔ)設(shè)施，可以充分利用集成的資源形成一個大規(guī)模的計算池，其目的是為了在分布、異構(gòu)，自治的網(wǎng)絡(luò)資源環(huán)境上構(gòu)造動態(tài)的虛擬組織，并在其內(nèi)部實現(xiàn)跨自治域的資源共享與資源協(xié)作，有效地滿足面向互聯(lián)網(wǎng)的復(fù)雜應(yīng)用對大規(guī)模計算能力和海量數(shù)據(jù)處理的需求。在網(wǎng)格計算技術(shù)中，網(wǎng)格系統(tǒng)軟件起著關(guān)鍵的作用，他提供單一系統(tǒng)映像、透明性、可靠性、負(fù)載平衡和資源共享等功能。網(wǎng)格系統(tǒng)軟件中的網(wǎng)格操作系統(tǒng)層提供網(wǎng)格的底層管理功能，編程和使用環(huán)境可提供用戶接口，從而使一般應(yīng)用和專門為
6、網(wǎng)格開發(fā)的應(yīng)用能方便和有效地利用網(wǎng)格資源。許多行業(yè)和領(lǐng)域，如能源、交通、氣象、水利、農(nóng)林、教育、環(huán)保等，以及涉及科研、開發(fā)、教育的諸多部門、單位和企業(yè)，對高性能計算網(wǎng)格以信息網(wǎng)格的需求是非常巨大的。無論是早期的計算網(wǎng)格還是目前的服務(wù)網(wǎng)格，都面臨著如何有效地管理和調(diào)度網(wǎng)格資源問題[1-3]。通常是發(fā)現(xiàn)適合于給定任務(wù)的潛在資源集合，從那些資源中選擇合適的資源子集，這些資源滿足一個預(yù)先定義好的調(diào)度約束，找到一個這樣的Makespan是NP完全問題[4]。目前常見的網(wǎng)格任務(wù)調(diào)度算法按照任務(wù)之間有無數(shù)據(jù)依賴關(guān)系可以分為獨立任務(wù)調(diào)度和依賴關(guān)系任務(wù)調(diào)
7、度，前者在調(diào)度任務(wù)時不用考慮任務(wù)之間的依賴關(guān)系；而后者通常用有向無環(huán)圖(DAG)表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系，在調(diào)度過程中滿足任務(wù)之間的數(shù)據(jù)依賴關(guān)系。針對以有向無環(huán)圖DAG(directedAcyclicGraph)來表示的并行任務(wù)模型的研究在近20年得到了迅速發(fā)展。這種模型限制條件包括:任務(wù)執(zhí)行具有非搶占性，即處理機只有在執(zhí)行完某個任務(wù)之后才能處理另外一個任務(wù)，另外這些任務(wù)之間具有前驅(qū)后繼的依賴關(guān)系，某個子任務(wù)只有在其所有的父節(jié)點任務(wù)處理完畢后才能開始執(zhí)行;該模型的調(diào)度目標(biāo)就是要使得整個DAG圖的調(diào)度長度最短。早期的這種DAG調(diào)度模型只
8、引入了各個任務(wù)的執(zhí)行時間(用每個節(jié)點權(quán)值表示)，而并沒有考慮任務(wù)之間的通信時第1頁上海交通大學(xué)碩士學(xué)位論文網(wǎng)格環(huán)境中基于DAG的并行任務(wù)調(diào)度算法研究間。但即使是在這種情況下，這種DAG調(diào)度仍然被證明是NP完
