可分任務(wù)的多趟調(diào)度模型及其算法研究.pdf

1、隨著處理數(shù)據(jù)的量級(jí)不斷增大，傳統(tǒng)的單計(jì)算節(jié)點(diǎn)的大型處理機(jī)已漸漸無法滿足新時(shí)代的數(shù)據(jù)處理需求。并行與分布式系統(tǒng)則為這一問題提供了新的思路與解決方案。對(duì)于大型分布式計(jì)算集群而言，如何將任務(wù)有效地進(jìn)行劃分、調(diào)度到系統(tǒng)中各個(gè)處理機(jī)則是能否高效發(fā)揮集群處理能力的關(guān)鍵性問題。高效的任務(wù)調(diào)度策略將極大地發(fā)揮現(xiàn)有集群計(jì)算能力，從而應(yīng)對(duì)更大的挑戰(zhàn)?？煞秩蝿?wù)理論是對(duì)現(xiàn)實(shí)世界中諸如圖像識(shí)別、大規(guī)模計(jì)算、視頻轉(zhuǎn)碼、網(wǎng)絡(luò)文件集特征搜索等多個(gè)領(lǐng)域問題的一種很好的近

2、似。其形式簡(jiǎn)單、易于理解卻又不失理論上的精確性，一經(jīng)提出便引起學(xué)術(shù)界的廣泛關(guān)注。尤其是在并行與分布式系統(tǒng)下的可分任務(wù)調(diào)度問題符合時(shí)代與技術(shù)的發(fā)展要求，愈發(fā)成為研究的熱點(diǎn)問題。
　　本研究主要內(nèi)容包括：⑴現(xiàn)有研究表明大多數(shù)的調(diào)度問題都是NP難問題，目前尚不能確定該類問題是否具有多項(xiàng)式時(shí)間復(fù)雜度的求解算法。因此對(duì)于此類問題，以遺傳算法為代表的智能優(yōu)化算法，能夠在相對(duì)合理的時(shí)間內(nèi)獲得原問題的近似最優(yōu)解，故得到了廣泛的研究。本文回顧遺傳算

3、法，詳細(xì)研究編、解碼策略、交叉、變異、選擇等遺傳算子。⑵研究了已有的并行與分布式系統(tǒng)下的可分任務(wù)的周期性調(diào)度算法，研究發(fā)現(xiàn)已有算法大多通過對(duì)任務(wù)完成時(shí)間關(guān)于處理機(jī)數(shù)目和調(diào)度趟數(shù)的函數(shù)求導(dǎo)的方式求解最優(yōu)的處理機(jī)數(shù)目與調(diào)度趟數(shù)。由于對(duì)函數(shù)求導(dǎo)要求該函數(shù)的定義域是連續(xù)可導(dǎo)的，然而處理機(jī)數(shù)目與調(diào)度趟數(shù)的取值范圍都是正整數(shù)，使得任務(wù)完成時(shí)間函數(shù)是不可導(dǎo)的，使用求導(dǎo)的方式求解可能會(huì)獲得不可行解。為了解決該問題，本文提出一種新的給定調(diào)度順序的周期性多

4、趟調(diào)度模型。證明了該模型下的兩條性質(zhì)，并且基于這兩條性質(zhì)本文提出一種新的快速周期性多趟調(diào)度算法。實(shí)驗(yàn)表明，本文提出的新算法可以獲得最優(yōu)的處理機(jī)數(shù)目和調(diào)度趟數(shù)，從而得到比已有算法更短的任務(wù)完成時(shí)間。⑶現(xiàn)有的研究大多針對(duì)給定調(diào)度順序的周期性多趟調(diào)度。然而，調(diào)度順序?qū)Ξ悩?gòu)并行和分布式系統(tǒng)下的周期性多趟調(diào)度結(jié)果具有重要影響。因此，為了最小化任務(wù)的完成時(shí)間，需要求解確定：最優(yōu)的任務(wù)劃分策略；最優(yōu)的參與計(jì)算的處理機(jī)數(shù)目；最優(yōu)的調(diào)度趟數(shù)；最優(yōu)的處理機(jī)