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

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

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

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

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