論文著重于多核多線程處理器上的任務(wù)調(diào)度相關(guān)的研究。首先是從理論角度提出了3種與基于復(fù)制的任務(wù)調(diào)度相關(guān)的算法,這3種算法都表現(xiàn)出了較好性能。然后結(jié)合一種實(shí)際的多核多線程處理器(網(wǎng)絡(luò)處理器IXP)展開了對任務(wù)調(diào)度實(shí)例化研究,并且運(yùn)用地址轉(zhuǎn)換和迭代編譯等技術(shù)構(gòu)建了新型統(tǒng)一網(wǎng)絡(luò)編程環(huán)境,又結(jié)合實(shí)際網(wǎng)絡(luò)應(yīng)用提出了吞吐量與延遲相結(jié)合的網(wǎng)絡(luò)任務(wù)調(diào)度算法。本文主要貢獻(xiàn)如下: 提出了滿足通信限制的基于復(fù)制的優(yōu)化fork-join調(diào)度算法TDC_FJ,TDC_FJ利用基于復(fù)制的fork-join最優(yōu)化調(diào)度結(jié)果來對fork-join任務(wù)圖進(jìn)行調(diào)度,并且在調(diào)度過程中加入處理器之間的通信限制,也就是一條通信信道不能同時(shí)被兩個(gè)通信事件占用。TDC_FJ算法在調(diào)度時(shí)力求減少需要的處理器數(shù)目,盡量調(diào)度任務(wù)到已占用處理器上,在保證性能的同時(shí)減少處理器的消耗量。 給出針對普通任務(wù)圖帶通信限制的基于復(fù)制調(diào)度算法TDMSCL。該算法把普通任務(wù)圖轉(zhuǎn)換為join與fork等基本形狀,然后運(yùn)用對join圖與fork圖的優(yōu)化調(diào)度研究結(jié)果對這些基本形狀進(jìn)行任務(wù)調(diào)度。相對于傳統(tǒng)任務(wù)調(diào)度中找關(guān)鍵路徑或者計(jì)算權(quán)值逐步調(diào)度的方式,TDMSCL算法把調(diào)度過程轉(zhuǎn)變?yōu)榘凑胀負(fù)湫蛄兄鸩角髢?yōu)的過程。算法力求保證每個(gè)節(jié)點(diǎn)的最早開始時(shí)間,通過這種調(diào)度方式獲得整個(gè)任務(wù)的優(yōu)化調(diào)度結(jié)果。合并過程采用貪婪策略力求在較小時(shí)間開銷內(nèi)提高合并的耦合度,并且考慮了通信信道的獨(dú)占性制止了同一通信信道的通信重疊。最后與其他幾種常見的任務(wù)調(diào)度算法進(jìn)行了對比測試,結(jié)果顯示TDMSCL在算法時(shí)間復(fù)雜度處理器消耗與調(diào)度長度上有性能優(yōu)勢。 提出了一種新的冗余任務(wù)消除算法RTE解決了基于復(fù)制的任務(wù)調(diào)度生成的冗余任務(wù)問題。大多數(shù)基于復(fù)制的算法調(diào)度后的任務(wù)存在部分冗余。這種冗余的任務(wù)會(huì)導(dǎo)致處理器計(jì)算資源的浪費(fèi)。RTE可以作為一種輔助手段用于提高已有基于復(fù)制的任務(wù)調(diào)度算法的效能,具有很好的通用性。任何一種基于復(fù)制的調(diào)度算法都可以和它結(jié)合使用。測試表明該算法可以使已有的基于復(fù)制的調(diào)度算法都不同程度的獲得效能提升。 針對異構(gòu)多核處理器IXP構(gòu)建編譯器Shangri-la的統(tǒng)一編譯后端框架。采用地址轉(zhuǎn)換方法來解決異構(gòu)內(nèi)核使用不同尋址方式的指針共享問題。提出了收斂的迭代編譯框架來控制最終代碼生成大小。這些技術(shù)的運(yùn)用使Shangri-la很好整合了兩種不同處理器核的編譯工作。這種統(tǒng)一的編譯平臺(tái)掩蓋了復(fù)雜的網(wǎng)絡(luò)處理器結(jié)構(gòu)特征,使得網(wǎng)絡(luò)程序編寫和傳統(tǒng)模式的程序編寫一樣簡單方便。 提出針對網(wǎng)絡(luò)應(yīng)用特性的任務(wù)調(diào)度算法LTTS。網(wǎng)絡(luò)程序不同于普通程序,網(wǎng)絡(luò)應(yīng)用具有較高的并行性,但是網(wǎng)絡(luò)應(yīng)用中的并行性是數(shù)據(jù)并行性。而且網(wǎng)絡(luò)程
【學(xué)位單位】：中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2006
【中圖分類】：TP332
【部分圖文】：

中國科學(xué)院博士學(xué)位論文──多核多線程處理器上任務(wù)調(diào)度技術(shù)研究線程切換，否則一直執(zhí)行當(dāng)前線程的指令。粗粒度多線程處理器并不需要進(jìn)行頻繁的線程切換，因此對線程切換的開銷要求也沒有細(xì)粒度多線程處理器那么高。也不需要太多的線程數(shù)目。但是粗粒度多線程處理器在進(jìn)行線程切換的時(shí)候需要排空流水線然后再進(jìn)行流水線填充。所以相對細(xì)粒度多線程粗粒度的線程切換開銷較大。多線程技術(shù)現(xiàn)在運(yùn)用得非常廣泛，超線程技術(shù)就是其中的一種。圖 1-1給出了superthreading 處理器[4]的結(jié)構(gòu)示意圖。

圖 4-2 任務(wù)圖例圖 4-2中 n1->n7->n9 是關(guān)鍵路徑，所以{n1,n7,n9}是 CPN 節(jié)點(diǎn)，{n2,n3,n4,n5,n6,n8}是 IBN 節(jié)點(diǎn)，圖中沒有 OBN 節(jié)點(diǎn)。按照 CPN_Dominant 生成算法首先選出 CPN 節(jié)點(diǎn)n1 加入到序列中{n1}，然后選取下一個(gè) CPN n7 但是 n7 的父節(jié)點(diǎn)并不是都在序列中，按照 b-level 選取最大 IBN 節(jié)點(diǎn) n2 加入序列{n1,n2}，之后又把 n3 加入到序列中{n1,n2,n3},在 n7 的父節(jié)點(diǎn)都被加入序列以后把 n7 也加入序列{n1,n2,n3,n7}，最后選取 n9 遞歸把父節(jié)點(diǎn)加入的序列，最終得到 CPN_Dominant 序列{n1,n2,n3,n7,n5,n4,n8,n6,n9}。在完成構(gòu)建 CPN_Dominant 列表后就可以進(jìn)行任務(wù)調(diào)度，具體調(diào)度算法如下CPFD 任務(wù)調(diào)度算法：1. 找出任務(wù)圖中的關(guān)鍵路徑，構(gòu)建 CPN_Dominant 序列Repeat2. 選取 CPN_Dominant 序列中的第一個(gè)未調(diào)度節(jié)點(diǎn)作為候選節(jié)點(diǎn)。3. 設(shè)定 P_SET 為處理器節(jié)點(diǎn)集合，它包含了候選節(jié)點(diǎn)的所有父節(jié)點(diǎn)所在處理器外加一個(gè)空處理器節(jié)點(diǎn)。4. 對于 P_SET 中的每一個(gè)處理器 P，計(jì)算候選節(jié)點(diǎn)在該處理器上的最早開始時(shí)間，

CPFD調(diào)度結(jié)果

【引證文獻(xiàn)】

相關(guān)期刊論文 前4條

1 孟學(xué)多;俞雪永;顏暉;;基于多核的在線判題系統(tǒng)的設(shè)計(jì)與研究[J];計(jì)算機(jī)時(shí)代;2011年07期

2 王遵彤;李彩;吳啟迪;;多處理器系統(tǒng)動(dòng)態(tài)調(diào)度負(fù)載均衡節(jié)約算法[J];控制與決策;2011年11期

3 李靜梅;張博;;基于混合粒子群優(yōu)化的CMP線程調(diào)度方法[J];計(jì)算機(jī)工程;2012年20期

4 朱仕浪;;基于NIOS Ⅱ雙軟核智能家居控制器設(shè)計(jì)[J];三明學(xué)院學(xué)報(bào);2011年05期

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

1 耿曉中;基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D];吉林大學(xué);2013年

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

1 董珍;異構(gòu)多核處理器的任務(wù)調(diào)度分配問題及算法研究[D];哈爾濱工程大學(xué);2010年

2 趙磊;適應(yīng)多核處理器的任務(wù)調(diào)度研究[D];哈爾濱理工大學(xué);2010年

3 高金華;基于多核的任務(wù)調(diào)度研究與實(shí)現(xiàn)[D];中南大學(xué);2010年

4 申建晶;嵌入式多核實(shí)時(shí)操作系統(tǒng)研究及實(shí)現(xiàn)[D];電子科技大學(xué);2011年

5 王旭濤;基于異構(gòu)多核處理器系統(tǒng)的任務(wù)調(diào)度算法研究[D];南京郵電大學(xué);2011年

6 徐茂興;全方位視覺的多核并行處理研究與應(yīng)用[D];浙江工業(yè)大學(xué);2010年

7 胡新安;支持動(dòng)態(tài)任務(wù)調(diào)度的多核分布式操作系統(tǒng)設(shè)計(jì)[D];哈爾濱工業(yè)大學(xué);2011年

8 李靜;基于多核的任務(wù)調(diào)度策略研究[D];哈爾濱工程大學(xué);2011年

9 梁帥;RSA密碼系統(tǒng)中的并行算法研究[D];內(nèi)蒙古大學(xué);2008年

10 呂堯;基于多核的網(wǎng)絡(luò)掃描研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2010年

本文編號(hào)：2814105