并行系統(tǒng)中負(fù)載調(diào)度問題的研究.pdf

1、并行分布計算是當(dāng)前計算機(jī)科學(xué)的熱點(diǎn)之一。并行和分布式計算是求解各種計算密集型負(fù)載調(diào)度問題的有效手段，麗負(fù)載調(diào)度(包括負(fù)載的劃分和傳輸)是影響并行與分布式計算性能的關(guān)鍵因素。并行系統(tǒng)中任務(wù)調(diào)度是指把一個應(yīng)用中有先后關(guān)系的任務(wù)合理地分配到并行機(jī)的處理器上，使得整個應(yīng)用完成時間最短。已經(jīng)證明，這是一個NP難的問題，現(xiàn)階段主要的研究是提出近似算法，提高調(diào)度的效率。本文研究了基于未知網(wǎng)絡(luò)的并行異構(gòu)系統(tǒng)中的可分負(fù)載調(diào)度問題，提出了一系列新的算法。本

2、文的主要貢獻(xiàn)包括： 1.提出未知網(wǎng)絡(luò)資源下的可分負(fù)載的自適應(yīng)調(diào)度算法。該算法提出了一種新的自適應(yīng)的探測技術(shù)，采用了非固定的探測片段，能夠根據(jù)當(dāng)前網(wǎng)絡(luò)狀況自動確定探測片段的大小，并盡量減少分發(fā)給慢節(jié)點(diǎn)的探測片段數(shù)目。與已有針對未知網(wǎng)絡(luò)參數(shù)的調(diào)度算法相比，本算法能夠顯著縮短負(fù)載的總處理時間，一般性能提升達(dá)到10％以上。 2. 提出未知網(wǎng)絡(luò)資源下的總線型系統(tǒng)中多可分負(fù)載的調(diào)度算法。實(shí)際系統(tǒng)中多負(fù)載的情況更為常見，而且單可分負(fù)載

3、調(diào)度在一定條件下可以理解為多可分負(fù)載調(diào)度。采用多階段分發(fā)策略，能極大提高對系統(tǒng)計算資源的利用率。該算法將多階段分發(fā)策略引入總線型系統(tǒng)的未知網(wǎng)絡(luò)調(diào)度研究中，取得很好的調(diào)度結(jié)果。 3. 提出未知網(wǎng)絡(luò)資源下的單層樹系統(tǒng)中多可分負(fù)載的調(diào)度算法。單層樹模型在實(shí)際應(yīng)用中使用廣泛，很多實(shí)際并行系統(tǒng)都能用單層樹模型表示?；趩螌訕淠Ｐ偷漠悩?gòu)系統(tǒng)調(diào)度策略，能夠根據(jù)當(dāng)前系統(tǒng)的結(jié)果調(diào)整偏差，自動調(diào)用探測過程。該算法以前面的新的探測技術(shù)和多階段分發(fā)技術(shù)