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

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

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