動態(tài)可重構(gòu)系統(tǒng)實時任務(wù)調(diào)度算法研究.pdf

1、可重構(gòu)計算技術(shù)結(jié)合了通用處理器(General-Purpose Processor,GPP)和專用集成電路(Application Specific Integrated Circuits,ASIC)兩者的優(yōu)點,能夠提供硬件的高效性和軟件的可編程性,是當(dāng)前熱門的研究課題之一。動態(tài)部分可重構(gòu)技術(shù)是可重構(gòu)計算技術(shù)的最新進(jìn)展之一。該技術(shù)能夠在可重構(gòu)系統(tǒng)正常工作的情況下,配置其中部分可重構(gòu)資源,使得一部分任務(wù)的執(zhí)行能夠與另一部分任務(wù)的配置同時進(jìn)

2、行。動態(tài)重構(gòu)技術(shù)能提高系統(tǒng)的靈活性和資源利用率,從而提升整個系統(tǒng)的性能。
　　 在動態(tài)可重構(gòu)系統(tǒng)中,硬件任務(wù)的調(diào)度是影響動態(tài)可重構(gòu)系統(tǒng)性能的關(guān)鍵因素之一。為了盡量提高系統(tǒng)芯片的利用率,降低硬件任務(wù)的拒絕率和調(diào)度時間開銷,這就需要采用高質(zhì)量的調(diào)度算法來對硬件任務(wù)進(jìn)行合理的調(diào)度和管理。本文針對實時任務(wù)在二維可重構(gòu)器件上的在線放置和調(diào)度問題,主要完成了以下工作:
　　 (1)本文考慮將硬件任務(wù)按照長、寬及調(diào)度時間構(gòu)成一個三維資

3、源模型,將每個硬件任務(wù)看成是一個空間塊,提出了一種基于三維空間鄰接度的放置算法。該算法首先對可重構(gòu)資源進(jìn)行編碼,到達(dá)的任務(wù)總是通過某個頂點依附另一個任務(wù)的邊界被放置,確定候選的放置頂點；然后以到達(dá)任務(wù)與已放置在三維空間的鄰接度為代價函數(shù),選擇代價函數(shù)值最大的頂點放置任務(wù),從而使得到達(dá)任務(wù)與已放置任務(wù)在三維空間接觸的鄰接面最大?？墒谷蝿?wù)安排得更緊湊,減小對系統(tǒng)資源的浪費,提高芯片利用率。
　　 (2)本文提出了一種基于頂點鏈表的硬

4、件任務(wù)間最小空間調(diào)度算法MSSA(minimun space scheduling algorithm),該算法充分考慮利用任務(wù)的松弛時間內(nèi)的調(diào)度延遲,采用基于三維空間鄰接度的放置方法,選擇松弛時間內(nèi)使得鄰接度最大的放置頂點和任務(wù)開始執(zhí)行時間來執(zhí)行任務(wù),使得任務(wù)更加整齊、緊密的放置,從而降低任務(wù)拒絕率,提高硬件任務(wù)執(zhí)行的并發(fā)度和資源利用率。
　　 (3)設(shè)計仿真實驗,將MSSA調(diào)度算法分別和Stuffing算法、MGS算法、CR