并行異構(gòu)系統(tǒng)任務(wù)調(diào)度問題研究.pdf

1、并行分布計算是當(dāng)前計算機科學(xué)的熱點之一。而并行系統(tǒng)中的任務(wù)調(diào)度算法是影響分布式計算效率的關(guān)鍵因素，也是一個具有挑戰(zhàn)性的課題。并行系統(tǒng)中任務(wù)調(diào)度是指把一個應(yīng)用中有先后關(guān)系的任務(wù)合理地分配到并行機的處理器上，使得整個應(yīng)用完成時間最短。已經(jīng)證明，這是一個NP難的問題，現(xiàn)階段主要的研究是提出近似算法，提高調(diào)度的效率。本文研究了并行異構(gòu)系統(tǒng)中的任務(wù)調(diào)度問題，在經(jīng)典的任務(wù)模型和有通信沖突的模型上分別提出了新的算法。本文的主要貢獻包括： (1

2、)經(jīng)典模型上的任務(wù)調(diào)度算法本文調(diào)研了現(xiàn)有的任務(wù)調(diào)度算法，在經(jīng)典的并行異構(gòu)環(huán)境任務(wù)調(diào)度模型上，對已有的基于任務(wù)復(fù)制的排序調(diào)度算法進行改進，改變了任務(wù)復(fù)制的策略，并且引入了區(qū)間插入的概念，設(shè)計出新的任務(wù)調(diào)度算法，并且通過模擬程序?qū)λ惴ǖ男阅苓M行測試，新算法的性能比已有算法有了明顯提高。 (2)有通信沖突模型上的任務(wù)調(diào)度算法考慮到有通信沖突模型的自身特點，本文在現(xiàn)有的有通信沖突模型算法中引入任務(wù)復(fù)制的方法，從而設(shè)計出更有效的新算法，通