發(fā)布時(shí)間：2018-10-05 15:42

【摘要】：現(xiàn)場(chǎng)可編程門陣列(Field-Programmable Gate Array,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à),需要對(duì)任務(wù)進(jìn)行有效的調(diào)度和布局。針對(duì)現(xiàn)有的FPGA架構(gòu),本文對(duì)動(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)度和布局,本文提出三元序列組(Se-quence Triple)的表示方法。三元序列組由三個(gè)同時(shí)集成時(shí)域和空域劃分的任務(wù)嵌套序列PS、MS、RS構(gòu)成。(PS,MS)為混合嵌套序列對(duì)(Hybrid Nested Sequence Pair),表示所有重構(gòu)區(qū)域在各個(gè)調(diào)度時(shí)刻的任務(wù)布局。通過求解混合嵌套序列對(duì)的最長(zhǎng)公共子序列,能夠計(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)的最長(zhǎng)路徑,能夠計(jì)算出任務(wù)配置時(shí)刻和執(zhí)行時(shí)刻。在動(dòng)態(tài)可重構(gòu)過程中,任務(wù)調(diào)度和布局必須滿足硬件資源約束和任務(wù)數(shù)據(jù)依賴關(guān)系。本文給出了可行任務(wù)調(diào)度和布局的充要條件,可以確立三元序列組完整的可行解空間。本文設(shè)計(jì)的優(yōu)化算法基于模擬退火算法(Simulated Annealing),能夠同時(shí)優(yōu)化調(diào)度和布局。根據(jù)三元序列組的表示特征,本文采用刪除插入的擾動(dòng)方法:從三元序列組中隨機(jī)刪除一個(gè)任務(wù),將所刪除的任務(wù)插入三個(gè)刪除后的任務(wù)序列中新的合適的位置。不同的插入位置對(duì)應(yīng)不同的調(diào)度和布局解。通過枚舉和評(píng)估可行插入位置,能夠跳過很多調(diào)度和布局結(jié)果較差的解。在擾動(dòng)過程中,本文采用增量式評(píng)估方法,能夠在線性時(shí)間復(fù)雜度內(nèi)評(píng)估所有可行插入位置所對(duì)應(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í),提高布局成功率。并且對(duì)于實(shí)驗(yàn)測(cè)試用例中任務(wù)并行度較低的計(jì)算應(yīng)用,能夠明顯降低動(dòng)態(tài)重構(gòu)過程中的重構(gòu)時(shí)延。相比于未優(yōu)化通信代價(jià)的情況,本文所提出的算法實(shí)現(xiàn)了對(duì)通信代價(jià)的優(yōu)化,但求解時(shí)間會(huì)相應(yīng)增加。并且對(duì)于任務(wù)數(shù)據(jù)依賴關(guān)系越多的實(shí)驗(yàn)測(cè)試用例,通信代價(jià)的優(yōu)化效果越好。
[Abstract]:Field Programmable Gate Array (Field-Programmable Gate Array,FPGA) is a kind of programmable integrated circuit, which can realize circuit design efficiently and change circuit architecture flexibly. Dynamic reconfigurable system is based on the dynamic reconfiguration characteristic of FPGA and can adapt to different computing requirements with limited resources. It is an effective solution for hardware acceleration technology. Through dynamic reconfiguration design, tasks in large-scale computing applications can be dynamically time-sharing and multiplexing hardware resources. The reconfiguration order and location of tasks will affect the performance of the system. The efficiency of refactoring resources and the communication cost between tasks need to be effectively scheduled and distributed. Aiming at the existing FPGA architecture, this paper studies the partitioning, scheduling and layout problems in dynamic reconfigurable systems, establishes the problem model of scheduling and layout, and puts forward the corresponding optimization algorithm. In order to represent task scheduling and layout in dynamic reconfigurable systems, a representation method of triple sequence sets (Se-quence Triple) is presented in this paper. The triple sequence is composed of three task nested sequences (PS,MS,RS) which integrate the division of time domain and space domain simultaneously. (PS,MS) is a hybrid nested sequence pair representing the task layout of all reconstructed regions at each scheduling time. By solving the longest common subsequences of the mixed nested sequence pairs, the task position coordinate. RS can be calculated as the reconstruction sequence, which indicates the assignment order of the tasks in all the reconstructed regions. By combining the reconfiguration sequence with the task data dependency, the reconfiguration constraint graph (Reconfigurable Constraints Graph),) can be constructed to represent the priority constraint relation of the task during dynamic reconfiguration. By solving the longest path from the reconstruction constraint graph to the vertex, the task configuration time and the execution time can be calculated. In the process of dynamic reconfiguration, task scheduling and layout must meet hardware resource constraints and task data dependencies. In this paper, the necessary and sufficient conditions for the scheduling and layout of feasible tasks are given, and the complete feasible solution space of the triple sequence can be established. The optimization algorithm designed in this paper can optimize scheduling and layout simultaneously based on simulated annealing algorithm (Simulated Annealing),). According to the representation characteristics of triple sequences, this paper adopts the perturbation method of deletion and insertion: one task is deleted randomly from the triple sequence, and the deleted task is inserted into a new suitable position in the three deleted task sequences. Different insertion locations correspond to different scheduling and layout solutions. By enumerating and evaluating feasible insertion locations, many poor scheduling and layout solutions can be skipped. In the process of disturbance, the incremental evaluation method is used to evaluate the scheduling and layout solutions of all feasible insertion locations within the linear time complexity. The effectiveness and efficiency of the scheduling and layout algorithm are verified by experiments in this paper. The experimental results show that the algorithm proposed in this paper can optimize the scheduling and layout integration, which can ensure better scheduling effect and improve the success rate of layout at the same time. In addition, the delay of dynamic reconstruction can be significantly reduced when the task parallelism is low in the experimental test cases. Compared with the unoptimized communication cost, the proposed algorithm optimizes the communication cost, but the solution time increases accordingly. And the more the task data dependency, the better the optimization effect of communication cost.
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TN791

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 李春生;周學(xué)海;曾芳玲;王超;;一種基于頂點(diǎn)位置樹的可重構(gòu)軟硬件迭代協(xié)同算法[J];中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào);2014年04期

2 彭曉明;龐建民;郭浩然;;動(dòng)態(tài)可重構(gòu)技術(shù)研究綜述[J];計(jì)算機(jī)工程與設(shè)計(jì);2012年12期

3 鄒yN;吳強(qiáng);趙遠(yuǎn)寧;;支持動(dòng)態(tài)可重構(gòu)硬件透明編程的預(yù)配置調(diào)度[J];計(jì)算機(jī)工程與應(yīng)用;2008年27期

4 周學(xué)功;梁j;黃勛章;彭澄廉;;可重構(gòu)系統(tǒng)中的實(shí)時(shí)任務(wù)在線調(diào)度與放置算法[J];計(jì)算機(jī)學(xué)報(bào);2007年11期

5 梁;周學(xué)功;王穎;彭澄廉;;采用預(yù)配置策略的可重構(gòu)混合任務(wù)調(diào)度算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2007年05期

6 齊驥;李曦;胡楠;周學(xué)海;龔育昌;王峰;;基于硬件任務(wù)頂點(diǎn)的可重構(gòu)系統(tǒng)資源管理算法[J];電子學(xué)報(bào);2006年11期

相關(guān)碩士學(xué)位論文 前3條

1 張吉昕;基于FPGA部分動(dòng)態(tài)可重構(gòu)技術(shù)的劃分和調(diào)度算法研究[D];武漢理工大學(xué);2014年

2 潘經(jīng)緯;可重構(gòu)系統(tǒng)中任務(wù)實(shí)時(shí)調(diào)度和實(shí)時(shí)布局算法的研究[D];電子科技大學(xué);2010年

3 施小祥;動(dòng)態(tài)可重構(gòu)FPGA的布局布線算法研究[D];西安電子科技大學(xué);2007年

，

本文編號(hào)：2253950