基于二維動(dòng)態(tài)可重構(gòu)模型的空閑資源搜索算法研究.pdf

1、可重構(gòu)計(jì)算是一種介于軟件和專用集成電路之間的新的求算方式,它兼顧了軟件的靈活性和硬件的高效性。為了充分發(fā)揮可重構(gòu)硬件在高性能和靈活性方面的優(yōu)勢(shì)以及簡(jiǎn)化可重構(gòu)邏輯器件的管理,有研究提出將硬件功能模塊視為硬件任務(wù),由操作系統(tǒng)統(tǒng)一管理軟硬件任務(wù)。這其中的主要工作之一就是為硬件任務(wù)尋找適當(dāng)?shù)目臻e區(qū)域供其選擇,因此可重構(gòu)硬件的空閑資源搜索策略是可重構(gòu)計(jì)算領(lǐng)域的研究點(diǎn)之一。
　　 本文的主要工作是研究現(xiàn)有可重構(gòu)系統(tǒng)的空閑區(qū)域搜索策略,提出了

2、三種基于最大空矩形的空閑資源搜索算法：SSLA1(Strengthened Scan Line Algorithm1)、SSLA2(Strengthened Scan Line Algorithm2)和SLA_VP(Scan Line Algorithin_ValleyPoint)。三種算法的基本思想都是一邊搜索有效寬度,一邊搜索最大空矩形。其中算法SSLA1和SSLA2采用有序有效搜索寬度的概念,保證了每次搜索出的空矩形都是最大空矩形

3、,但是兩種算法搜索有序有效搜索寬度的順序不同,算法SSLA1采用由小到大的順序,而算法SSLA2采用由大到小的順序。兩種算法通過建立一維輔助數(shù)組,對(duì)搜索過程中與有序有效搜索寬度相等的單元賦0來避免重復(fù)搜索問題,與ESLA(Enhanced Scan Line Algorithin)中采用二維輔助數(shù)組相比,有效地減少了輔助存儲(chǔ)空間代價(jià)。通過進(jìn)一步研究發(fā)現(xiàn),兩個(gè)相鄰最大關(guān)鍵元素之間的谷點(diǎn)有如下特性：如果谷點(diǎn)的單元值不為0,則存在能覆蓋兩個(gè)最

4、大關(guān)鍵元素的最大空矩形。算法SLA_VP通過保存谷點(diǎn)的信息以判斷兩個(gè)最大關(guān)鍵元素是否相鄰,并利用谷點(diǎn)的特性確定最小搜索寬度,避免了重復(fù)搜索問題,與前兩種算法相比,輔助存儲(chǔ)空間代價(jià)進(jìn)一步減少。
　　 最后,本文通過實(shí)驗(yàn)檢測(cè)了上述所提算法的性能。實(shí)驗(yàn)結(jié)果表明,三種新算法的平均運(yùn)行時(shí)間開銷都小于ESLA算法。三種算法相比,算法SSLA1和SSLA2的平均運(yùn)行時(shí)間開銷都小于算法SLA_VP。算法SSLA1與算法SSLA2相比,在負(fù)載率小