【摘要】：在分布式內(nèi)存多處理機(jī)系統(tǒng)上，對(duì)于中、細(xì)粒度并行程序而言，不同處理機(jī)之間的通信開銷在整個(gè)程序的執(zhí)行時(shí)間中所占的比重仍然很大，有時(shí)可能會(huì)抵消多處理機(jī)并行所帶來的好處。為了使并行程序能得到高效地執(zhí)行，必須采用合理的靜態(tài)任務(wù)調(diào)度技術(shù)將不同的任務(wù)分配給合適的處理機(jī)去執(zhí)行。靜態(tài)任務(wù)調(diào)度的目標(biāo)是最小化并行程序的執(zhí)行時(shí)間。 靜態(tài)任務(wù)調(diào)度的實(shí)現(xiàn)方法有兩種：1)．程序員／用戶手工地將任務(wù)分配給處理機(jī)；2)．采用調(diào)度算法自動(dòng)地將任務(wù)分配給處理機(jī)。在應(yīng)用較為規(guī)則或劃分后的應(yīng)用拓?fù)渑c處理機(jī)系統(tǒng)的拓?fù)湎嘁恢聲r(shí)，采用手工的方法去分配任務(wù)是可行的。但對(duì)于一些不規(guī)則應(yīng)用，尤其當(dāng)問題的規(guī)模較大時(shí)，應(yīng)當(dāng)采用一些專門的算法去自動(dòng)調(diào)度任務(wù)。本文重點(diǎn)討論如何采用算法去自動(dòng)調(diào)度并行任務(wù)，主要貢獻(xiàn)有： 1．對(duì)于完全互連的系統(tǒng)，提出了一個(gè)基于動(dòng)態(tài)關(guān)鍵路徑的調(diào)度算法('NF。算法('NF的特點(diǎn)有：(1)根據(jù)任務(wù)調(diào)度過程中關(guān)鍵路徑的動(dòng)態(tài)變化相應(yīng)地調(diào)整關(guān)鍵路徑。(2)總是優(yōu)先調(diào)度關(guān)鍵路徑上的任務(wù)。(3)當(dāng)參與調(diào)度的任務(wù)只有一個(gè)子任務(wù)時(shí)，則采用一種試探法來選擇處理機(jī)；當(dāng)參與調(diào)度的任務(wù)有多個(gè)子任務(wù)時(shí)，則為這樣的任務(wù)選擇能最早地開始執(zhí)行的處理機(jī)。本文還將該算法與其它三種典型的算法在調(diào)度長度上進(jìn)行了比較，結(jié)果表明本文中提出的算法平均調(diào)度長度最短。另外，本文還提出了一種有效的可以節(jié)省任務(wù)調(diào)度中所需使用處理機(jī)數(shù)目的方法。 2．對(duì)于非完全互連系統(tǒng)，給出了任務(wù)調(diào)度問題的形式化描述。針對(duì)一些典型的系統(tǒng)，如線性陣列、環(huán)、二維Mesh網(wǎng)與超立方體，將不同處理機(jī)之間的鏈路看成是資源，提出了一個(gè)基于靜態(tài)關(guān)鍵路徑的調(diào)度算法。算法中重點(diǎn)解決的問題是如何為消息分配路由，該問題按存儲(chǔ)轉(zhuǎn)發(fā)與蟲道尋徑兩種不同的尋徑技術(shù)分別進(jìn)行了討論。在針對(duì)總線互連的多處理機(jī)系統(tǒng)的調(diào)度算法中，本文首次考慮了消息廣播對(duì)任務(wù)調(diào)度的影響。 3．移植了一個(gè)基于任務(wù)級(jí)并行的編程環(huán)境(?)RAPID系統(tǒng)。為了實(shí)現(xiàn)進(jìn)程之間的通信，該系統(tǒng)原先調(diào)用了('RAY T3E上提供的共享內(nèi)存庫，而移植后系統(tǒng)的底層通信環(huán)境完全建立在MPI之上。目前，算法('NF已被成功
【學(xué)位授予單位】：中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：1999
【分類號(hào)】：TP338.6
【圖文】：

.:5程序串行執(zhí)行Gatllt圖(11二512)圖6.6:自動(dòng)任務(wù)調(diào)度程序執(zhí)行Gallt.t圖(n二512)圖(，了:手工任務(wù)聚類程序執(zhí)行(;alltt圖(n二512)

分布式內(nèi)存多處理機(jī)上并行任務(wù)靜態(tài)調(diào)度圖6.:5程序串行執(zhí)行Gatllt圖(11二512)圖6.6:自動(dòng)任務(wù)調(diào)度程序執(zhí)行Gallt.t圖(n二512)圖(，了:手工任務(wù)聚類程序執(zhí)行(;alltt圖(n二512)

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 顧小旭;網(wǎng)格環(huán)境下的電網(wǎng)動(dòng)態(tài)安全分析和算法研究[D];上海交通大學(xué);2009年

本文編號(hào)：2798699