動態(tài)可重構系統(tǒng)實時任務調度算法研究.pdf

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

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

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

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