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

1、現(xiàn)場可編程門陣列(FPGA)是一類可編程集成電路，既能高效地實(shí)現(xiàn)電路設(shè)計(jì)又能靈活地改變電路架構(gòu)，具有可重構(gòu)的功能。動(dòng)態(tài)可重構(gòu)系統(tǒng)基于FPGA的動(dòng)態(tài)重構(gòu)特性，能夠以有限的資源適應(yīng)不同的計(jì)算需求，是硬件加速技術(shù)的有效解決方案。
　　通過動(dòng)態(tài)重構(gòu)設(shè)計(jì)，大規(guī)模計(jì)算應(yīng)用中的任務(wù)可以動(dòng)態(tài)地分時(shí)復(fù)用硬件資源。任務(wù)的重構(gòu)次序和重構(gòu)位置會(huì)影響系統(tǒng)運(yùn)行的性能、重構(gòu)資源的利用效率和任務(wù)之間的通信代價(jià)，需要對任務(wù)進(jìn)行有效的調(diào)度和布局。針對現(xiàn)有的FPGA架

2、構(gòu)，本文對動(dòng)態(tài)可重構(gòu)系統(tǒng)中相互耦合的劃分、調(diào)度和布局問題進(jìn)行了研究，建立了調(diào)度和布局的問題模型，提出了相應(yīng)的優(yōu)化算法。
　　為了表示動(dòng)態(tài)可重構(gòu)系統(tǒng)中的任務(wù)調(diào)度和布局，本文提出三元序列組(Sequence Triple)的表示方法。三元序列組由三個(gè)同時(shí)集成時(shí)域和空域劃分的任務(wù)嵌套序列PS、MS、RS構(gòu)成。(PS，MS)為混合嵌套序列對(HybridNestedSequencePair)，表示所有重構(gòu)區(qū)域在各個(gè)調(diào)度時(shí)刻的任務(wù)布局。通過

3、求解混合嵌套序列對的最長公共子序列，能夠計(jì)算出任務(wù)位置坐標(biāo)。RS為重構(gòu)序列，表示所有重構(gòu)區(qū)域中任務(wù)的配置先后順序。將重構(gòu)序列和任務(wù)數(shù)據(jù)依賴關(guān)系相結(jié)合，可以構(gòu)建重構(gòu)約束圖(Reconfigurable Constraints Graph)，表示動(dòng)態(tài)重構(gòu)過程中任務(wù)的優(yōu)先約束關(guān)系。通過求解重構(gòu)約束圖中到頂點(diǎn)的最長路徑，能夠計(jì)算出任務(wù)配置時(shí)刻和執(zhí)行時(shí)刻。在動(dòng)態(tài)可重構(gòu)過程中，任務(wù)調(diào)度和布局必須滿足硬件資源約束和任務(wù)數(shù)據(jù)依賴關(guān)系。本文給出了可行任務(wù)

4、調(diào)度和布局的充要條件，可以確立三元序列組完整的可行解空間。
　　本文設(shè)計(jì)的優(yōu)化算法基于模擬退火算法(Simulated Annealing)，能夠同時(shí)優(yōu)化調(diào)度和布局。根據(jù)三元序列組的表示特征，本文采用刪除插入的擾動(dòng)方法:從三元序列組中隨機(jī)刪除一個(gè)任務(wù)，將所刪除的任務(wù)插入三個(gè)刪除后的任務(wù)序列中新的合適的位置。不同的插入位置對應(yīng)不同的調(diào)度和布局解。通過枚舉和評估可行插入位置，能夠跳過很多調(diào)度和布局結(jié)果較差的解。在擾動(dòng)過程中，本文采用增

5、量式評估方法，能夠在線性時(shí)間復(fù)雜度內(nèi)評估所有可行插入位置所對應(yīng)的調(diào)度和布局解。
　　本文實(shí)驗(yàn)驗(yàn)證了調(diào)度和布局算法的有效性和高效性。實(shí)驗(yàn)結(jié)果表明，本文所提出的算法能夠?qū)φ{(diào)度和布局的進(jìn)行集成優(yōu)化，可以在保證較好調(diào)度效果的同時(shí)，提高布局成功率。并且對于實(shí)驗(yàn)測試用例中任務(wù)并行度較低的計(jì)算應(yīng)用，能夠明顯降低動(dòng)態(tài)重構(gòu)過程中的重構(gòu)時(shí)延。相比于未優(yōu)化通信代價(jià)的情況，本文所提出的算法實(shí)現(xiàn)了對通信代價(jià)的優(yōu)化，但求解時(shí)間會(huì)相應(yīng)增加。并且對于任務(wù)數(shù)據(jù)依賴