基于動(dòng)態(tài)通信競(jìng)爭(zhēng)的任意處理機(jī)網(wǎng)絡(luò)表調(diào)度算法.pdf

1、計(jì)算技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，極大地促進(jìn)了基于網(wǎng)絡(luò)環(huán)境的科學(xué)應(yīng)用研究。許多應(yīng)用領(lǐng)域?qū)τ?jì)算能力的要求越來越高，單臺(tái)計(jì)算機(jī)已很難滿足計(jì)算需求。由多處理機(jī)構(gòu)建的高性能計(jì)算系統(tǒng)已成為計(jì)算技術(shù)發(fā)展的必然，然而在這種系統(tǒng)環(huán)境下調(diào)度任意結(jié)構(gòu)并行任務(wù)并獲取最優(yōu)解的問題仍然是NP完全難題。表調(diào)度算法是解決此類問題的一種經(jīng)典啟發(fā)式任務(wù)調(diào)度算法，具有調(diào)度性能較好，時(shí)間復(fù)雜度較低等優(yōu)點(diǎn)。但經(jīng)典表調(diào)度算法假定目標(biāo)處理機(jī)全互連，以及調(diào)度節(jié)點(diǎn)時(shí)忽略節(jié)點(diǎn)之間的通信，顯

2、然不符合任意處理機(jī)網(wǎng)絡(luò)計(jì)算環(huán)境的需求。因?yàn)閷?duì)于任意處理機(jī)網(wǎng)絡(luò)拓樸結(jié)構(gòu)的異構(gòu)系統(tǒng)，各任務(wù)之間的通信競(jìng)爭(zhēng)不可忽略，這種任務(wù)通信對(duì)整個(gè)并行應(yīng)用程序的執(zhí)行有重要影響。因而，考慮通信競(jìng)爭(zhēng)的調(diào)度算法是提高并行分布式計(jì)算系統(tǒng)實(shí)際性能的重要途徑之一。 本文研究工作主要方法是在調(diào)度算法中考慮通信競(jìng)爭(zhēng)，即調(diào)度任務(wù)時(shí)同時(shí)考慮節(jié)點(diǎn)和通信邊的調(diào)度。為了實(shí)現(xiàn)調(diào)度目標(biāo)，提出一個(gè)基于最短路徑搜索算法的最早通信完成路徑查找算法(EFCS)，采用插入式鏈路實(shí)現(xiàn)策略

3、，以達(dá)到通信邊的動(dòng)態(tài)調(diào)度；對(duì)于任意處理機(jī)網(wǎng)絡(luò)環(huán)境下的任務(wù)優(yōu)先級(jí)計(jì)算問題，受HEFT算法啟發(fā)提出遞歸優(yōu)先權(quán)計(jì)算公式，并且按非升序排列獲得各任務(wù)優(yōu)先級(jí)。同時(shí)為了降低算法執(zhí)行時(shí)間，采用OpenMP實(shí)現(xiàn)算法的并行化，理論分析表明并行算法可達(dá)到的加速比為O(PPE)。以隨機(jī)產(chǎn)生程序任務(wù)圖和現(xiàn)實(shí)中的實(shí)際應(yīng)用程序?yàn)閿?shù)據(jù)來源，在兩類不同的任意處理機(jī)網(wǎng)絡(luò)目標(biāo)系統(tǒng)上進(jìn)行了模擬實(shí)驗(yàn)。結(jié)果表明本算法明顯優(yōu)于考慮通信競(jìng)爭(zhēng)的靜態(tài)表調(diào)度算法和不考慮通信競(jìng)爭(zhēng)的表調(diào)度算