基于執(zhí)行時(shí)間方差的元任務(wù)網(wǎng)格調(diào)度算法研究.pdf

1、網(wǎng)格計(jì)算是一種特殊的具有重要?jiǎng)?chuàng)新思想和巨大發(fā)展?jié)摿Φ姆种ЬW(wǎng)絡(luò)計(jì)算。從概念上講，網(wǎng)格計(jì)算的目標(biāo)是資源共享和分布協(xié)同工作。而任務(wù)調(diào)度作為網(wǎng)格高性能計(jì)算的一個(gè)重要方面，它的性能好壞直接影響到網(wǎng)格計(jì)算的性能優(yōu)劣。隨著網(wǎng)格方向逐步走向標(biāo)準(zhǔn)化、大型化和多技術(shù)融合化，對任務(wù)調(diào)度的性能提出了更高的要求。網(wǎng)格任務(wù)調(diào)度算法成為網(wǎng)格研究的一個(gè)熱點(diǎn)。 網(wǎng)格的任務(wù)調(diào)度問題一直是一個(gè)NP問題，目前采用的大多是啟發(fā)式調(diào)度算法。網(wǎng)格任務(wù)調(diào)度一般分為靜態(tài)調(diào)度和動(dòng)

2、態(tài)調(diào)度兩大類。在動(dòng)態(tài)調(diào)度中任務(wù)調(diào)度又分在線模式和批模式兩種，批模式具有動(dòng)態(tài)在線模式算法的實(shí)時(shí)性，又具有靜態(tài)映射調(diào)度算法的高效性，在很多計(jì)算系統(tǒng)中得到了廣泛應(yīng)用，比在線方式更能充分利用計(jì)算資源。但是對于傳統(tǒng)的批調(diào)度算法如最小最短算法MIN-MIN、最大最短算法MAX-MIN、最大間距算法MAX-INT，從負(fù)載均衡度和調(diào)度跨度這兩個(gè)重要的網(wǎng)格性能角度看，它們在調(diào)度跨度取得較好成果的同時(shí)，在負(fù)載均衡度上并不盡如人意。針對網(wǎng)格的異構(gòu)性，本文提出

3、了一種改進(jìn)的算法--Q_VARIANCE(Queued Variance algorithm)。該算法在總結(jié)了經(jīng)典算法優(yōu)點(diǎn)及缺點(diǎn)的基礎(chǔ)上，負(fù)載均衡度有了顯著提高，并且調(diào)度跨度也得到改善。 任務(wù)分配到各個(gè)機(jī)器上執(zhí)行時(shí)間會(huì)有差異，方差是反映該差異的數(shù)學(xué)變量。該算法首先將執(zhí)行時(shí)間的方差作為任務(wù)執(zhí)行優(yōu)先級的評判基礎(chǔ)。每個(gè)任務(wù)都存在一個(gè)方差，將各個(gè)方差求得的期望作為任務(wù)分組的分界線，從而將批量任務(wù)分為方差大組和方差小組。每一次任務(wù)分配以基

4、數(shù)因子為基準(zhǔn)分成幾輪。每個(gè)輪次，每個(gè)組按照相應(yīng)比例進(jìn)行任務(wù)調(diào)度，增強(qiáng)任務(wù)的負(fù)載均衡度，縮短任務(wù)的調(diào)度跨度。然后以MIN-MIN、MAX-INT算法為測評基準(zhǔn)，利用網(wǎng)格調(diào)度的模擬工具包GRIDSIM，在NETBEANS環(huán)境下，進(jìn)行大量的仿真實(shí)驗(yàn)，結(jié)果證明：Q_VARIANCE算法具有很好的調(diào)度性能，能夠適用于網(wǎng)格異構(gòu)偏差大條件下的網(wǎng)格任務(wù)調(diào)度，并且能得到比MIN-M1N、MAX-INT更優(yōu)的調(diào)度結(jié)果。 論文最后除了對研究工作進(jìn)行了