基于化學反應優(yōu)化的網(wǎng)格任務調(diào)度研究.pdf

1、網(wǎng)格計算是伴隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展而產(chǎn)生的一種新型分布式計算模式，通過互聯(lián)網(wǎng)將分散的計算資源虛擬成一個超級計算機，實現(xiàn)跨地域的、并行分布式聯(lián)合計算，以完成重大科學領(lǐng)域的大規(guī)模復雜計算問題。網(wǎng)格任務調(diào)度是網(wǎng)格計算的核心技術(shù)之一，高效的網(wǎng)格任務調(diào)度算法可以充分利用網(wǎng)格系統(tǒng)中的計算資源，從而盡可能的使整個系統(tǒng)的性能達到最佳。然而，由于網(wǎng)格資源自身的分布性、異構(gòu)性、動態(tài)性等特征，使得網(wǎng)格任務調(diào)度極其困難、復雜，因此，如何開發(fā)出高效的任務調(diào)度算

2、法來盡可能地提高網(wǎng)格系統(tǒng)的吞吐量是網(wǎng)格計算的一大挑戰(zhàn)。
　　針對網(wǎng)格任務調(diào)度問題，目前已經(jīng)研究出了一些有效的調(diào)度策略，如基于表結(jié)構(gòu)調(diào)度的最早完成時間(Heterogeneous Earliest Finish Time，HEFT)算法以及基于隨機搜索的遺傳算法、蟻群算法、模擬退火算法、禁忌算法等。這些算法皆優(yōu)缺點分明，并且網(wǎng)格環(huán)境中的任務調(diào)度己被證明是一個NP(Non-deterministicPolynomial)難問題，所以通

3、常也只能得到問題的近似最好解。網(wǎng)格環(huán)境中，存在著大量類型的調(diào)度問題，而目前所實現(xiàn)的解決方案并不是很多，并且不存在有效地通用調(diào)度算法，所以需要開發(fā)出更多的解決方法。
　　本文對網(wǎng)格任務調(diào)度的概念、特點及目標進行了介紹，并對網(wǎng)格環(huán)境中的任務調(diào)度方法進行了詳細地分類及介紹。針對網(wǎng)格環(huán)境中最主要的任務類型：依賴任務，介紹了其有向無環(huán)圖(Directed Acyclic Graph，DAG)數(shù)學模型，并在該數(shù)學模型上，提出了一種新的網(wǎng)格任務

4、調(diào)度算法，CROTS(Chemical ReactionOptimization for Task Scheduling)。該算法由兩部分組成，一種基于任務層次的智能任務序列搜索算法以及基于化學反應優(yōu)化(chemical reaction optimization，CRO)的處理機映射方案搜索。CRO是通過模擬化學反應中，分子運動這種自然現(xiàn)象得到的一種元啟發(fā)式方法，算法的核心為四種基本操作：撞墻、分解、交換以及合成。其中，分解操作有效地