片上多核處理器的調(diào)度算法研究.pdf

1、隨著集成電路工藝的不斷發(fā)展,單核處理器的性能已經(jīng)得到了巨大的提升,然而如果要進(jìn)一步提升其性能,將無(wú)法避免的會(huì)遇到處理器與外部存儲(chǔ)器速率不匹配、指令級(jí)并行機(jī)制以及功耗等方面的問(wèn)題。為了應(yīng)對(duì)這些問(wèn)題,片上多核處理器作為一種有效的解決方案,受到了廣泛的關(guān)注。片上多核處理器,包括采用網(wǎng)絡(luò)結(jié)構(gòu)的片上網(wǎng)絡(luò),由于其具有高計(jì)算能力、高并行性以及低功耗等多方面的優(yōu)點(diǎn),在諸如無(wú)線通信、視頻/圖像處理以及云計(jì)算等諸多領(lǐng)域有著廣泛的應(yīng)用前景,其相關(guān)研究也是該研

2、究領(lǐng)域的一個(gè)熱點(diǎn)。雖然片上多核處理器相關(guān)研究在過(guò)去幾年間得到了長(zhǎng)足的發(fā)展,但是一些研究方向的滯后仍然制約著其實(shí)用化的進(jìn)程,其中一個(gè)方向就是片上多核處理器的任務(wù)調(diào)度算法研究。
　　任務(wù)調(diào)度是對(duì)任務(wù)從時(shí)間及空間兩個(gè)維度進(jìn)行計(jì)算資源分配的過(guò)程,好的任務(wù)調(diào)度算法與對(duì)提高片上多核系統(tǒng)的性能至關(guān)重要。本學(xué)位論文在廣泛研究現(xiàn)有片上多核調(diào)度算法的基礎(chǔ)上進(jìn)行總結(jié)創(chuàng)新,分別對(duì)基于實(shí)時(shí)任務(wù)集的調(diào)度算法以及基有向無(wú)環(huán)圖(DAG)的任務(wù)集調(diào)度算法進(jìn)行研究,

3、具體貢獻(xiàn)如下:
　　1.在對(duì)片上多核處理器實(shí)時(shí)任務(wù)調(diào)度進(jìn)行的研究中,對(duì)遺傳算法、粒子群優(yōu)化算法及模擬退火算法三種應(yīng)用廣泛的啟發(fā)式任務(wù)調(diào)度算法進(jìn)行性能對(duì)比仿真。對(duì)其中性能較好的粒子群優(yōu)化算法做出改進(jìn),提出了基于負(fù)載均衡的最小位置值(LB-SPV)算法以及混合粒子群優(yōu)化算法(Hybrid PSO)。通過(guò)仿真實(shí)驗(yàn)證明該算法在改善處理器任務(wù)均衡的同時(shí)整體提升了調(diào)度的性能。
　　2.在對(duì)DAG任務(wù)集在片上網(wǎng)絡(luò)中的調(diào)度問(wèn)題進(jìn)行研究中,我

4、們根據(jù)片上網(wǎng)絡(luò)中任務(wù)調(diào)度的特點(diǎn),提出了一種片上網(wǎng)絡(luò)低功耗調(diào)度算法(EES-MPNoC)。該算法以片上網(wǎng)絡(luò)中難以精確控制的調(diào)度時(shí)長(zhǎng)為第一約束,在實(shí)現(xiàn)最小調(diào)度時(shí)長(zhǎng)調(diào)度的同時(shí),使用最小路由跳數(shù)調(diào)度以及基于計(jì)算性時(shí)間松弛量的動(dòng)態(tài)電壓調(diào)控技術(shù),同時(shí)對(duì)片上網(wǎng)絡(luò)路由功耗以及處理器功耗進(jìn)行優(yōu)化。對(duì)比實(shí)驗(yàn)證明,我們所提出的EES-MPNoC算法與Level-By-Level多核調(diào)度算法相比,犧牲一定處理器功耗優(yōu)化的情況下可以減少3％的調(diào)度時(shí)長(zhǎng)及11％的路

5、由功耗。
　　3.在使用數(shù)據(jù)包絡(luò)分析方法進(jìn)行片上多核處理器實(shí)時(shí)任務(wù)調(diào)度方案效率評(píng)估的研究中,我們從調(diào)度問(wèn)題中提取出三種通用性能指標(biāo)建立了數(shù)據(jù)包絡(luò)分析決策單元模型,并在其基礎(chǔ)上提出了一種基于BCC超效率的調(diào)度方案效率分析方法,并將其應(yīng)用于遺傳算法,提出了一種優(yōu)化調(diào)度方案效率的DEA-GA調(diào)度算法。通過(guò)與幾種全局指標(biāo)遺傳調(diào)度算法進(jìn)行對(duì)比仿真,證明我們所提出的DEA-GA算法所得到的調(diào)度方案效率總是高于其它幾種調(diào)度算法。
　　4.