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

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

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

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

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

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