并行異構系統(tǒng)任務調度問題研究.pdf

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

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