并行遺傳算法及其在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用研究.pdf

1、網(wǎng)格是當前并行計算技術(shù)的一個重要發(fā)展方向，其目標是實現(xiàn)對地理上廣泛分布的大量異構(gòu)資源的資源共享。其中，任務(wù)調(diào)度是實現(xiàn)高性能網(wǎng)格計算的核心服務(wù)技術(shù)，也是保證應(yīng)用程序有效執(zhí)行的重要組成部分。
　　 網(wǎng)格任務(wù)調(diào)度是將并行程序任務(wù)分配到網(wǎng)格系統(tǒng)的處理節(jié)點上，涉及到程序模型和并行計算系統(tǒng)模型，算法的設(shè)計要綜合考慮程序和目標系統(tǒng)的特點，是一種典型的NP完全問題。遺傳算法由于具有良好的全局搜索能力，在處理任務(wù)調(diào)度算法時比傳統(tǒng)調(diào)度算法更具優(yōu)越性

2、。但是，應(yīng)用基本的遺傳算法容易陷入“過早收斂”的誤區(qū)，同時求解精度不高。本文針對網(wǎng)格任務(wù)調(diào)度問題，提出了一種基于MPI的并行遺傳算法處理方式。
　　 文章首先簡述了一下遺傳算法的基本原理，針對傳統(tǒng)遺傳算法自身的并行性，從全局并行的角度出發(fā)提出了一種粗粒度的并行遺傳算法。該算法采用分布式并行模式，通過子種群的個體遷移策略，緩解“早斂”和求解精度不高的問題，同時精英保留機制的引入，讓調(diào)度策略有更好的收斂性。
　　 然后，研究

3、了任務(wù)調(diào)度的機理、調(diào)度過程和調(diào)度模型，通過與現(xiàn)有調(diào)度算法的比較，確定了采用并行遺傳算法的任務(wù)調(diào)度方案，并規(guī)劃了任務(wù)調(diào)度的目標，在滿足任務(wù)優(yōu)先約束關(guān)系的前提下實現(xiàn)最優(yōu)跨度。
　　 最后，針對網(wǎng)格動態(tài)的、異構(gòu)的、分布的計算環(huán)境，采用C語言和消息傳遞接口MPI實現(xiàn)了本文算法，在建立的模擬網(wǎng)格環(huán)境PC機群中分別對本文算法、傳統(tǒng)遺傳算法進行了不同分組的任務(wù)調(diào)度仿真實驗，通過不同規(guī)模的調(diào)度時間性能進行對比分析，結(jié)果表明，本文提出的改進遺傳算