動態(tài)可重構(gòu)系統(tǒng)中任務(wù)調(diào)度與布局算法研究
發(fā)布時間：2018-10-05 15:42
【摘要】：現(xiàn)場可編程門陣列(Field-Programmable Gate Array,FPGA)是一類可編程集成電路,既能高效地實(shí)現(xiàn)電路設(shè)計又能靈活地改變電路架構(gòu),具有可重構(gòu)的功能。動態(tài)可重構(gòu)系統(tǒng)基于FPGA的動態(tài)重構(gòu)特性,能夠以有限的資源適應(yīng)不同的計算需求,是硬件加速技術(shù)的有效解決方案。通過動態(tài)重構(gòu)設(shè)計,大規(guī)模計算應(yīng)用中的任務(wù)可以動態(tài)地分時復(fù)用硬件資源。任務(wù)的重構(gòu)次序和重構(gòu)位置會影響系統(tǒng)運(yùn)行的性能、重構(gòu)資源的利用效率和任務(wù)之間的通信代價,需要對任務(wù)進(jìn)行有效的調(diào)度和布局。針對現(xiàn)有的FPGA架構(gòu),本文對動態(tài)可重構(gòu)系統(tǒng)中相互耦合的劃分、調(diào)度和布局問題進(jìn)行了研究,建立了調(diào)度和布局的問題模型,提出了相應(yīng)的優(yōu)化算法。為了表示動態(tài)可重構(gòu)系統(tǒng)中的任務(wù)調(diào)度和布局,本文提出三元序列組(Se-quence Triple)的表示方法。三元序列組由三個同時集成時域和空域劃分的任務(wù)嵌套序列PS、MS、RS構(gòu)成。(PS,MS)為混合嵌套序列對(Hybrid Nested Sequence Pair),表示所有重構(gòu)區(qū)域在各個調(diào)度時刻的任務(wù)布局。通過求解混合嵌套序列對的最長公共子序列,能夠計算出任務(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),表示動態(tài)重構(gòu)過程中任務(wù)的優(yōu)先約束關(guān)系。通過求解重構(gòu)約束圖中到頂點(diǎn)的最長路徑,能夠計算出任務(wù)配置時刻和執(zhí)行時刻。在動態(tài)可重構(gòu)過程中,任務(wù)調(diào)度和布局必須滿足硬件資源約束和任務(wù)數(shù)據(jù)依賴關(guān)系。本文給出了可行任務(wù)調(diào)度和布局的充要條件,可以確立三元序列組完整的可行解空間。本文設(shè)計的優(yōu)化算法基于模擬退火算法(Simulated Annealing),能夠同時優(yōu)化調(diào)度和布局。根據(jù)三元序列組的表示特征,本文采用刪除插入的擾動方法:從三元序列組中隨機(jī)刪除一個任務(wù),將所刪除的任務(wù)插入三個刪除后的任務(wù)序列中新的合適的位置。不同的插入位置對應(yīng)不同的調(diào)度和布局解。通過枚舉和評估可行插入位置,能夠跳過很多調(diào)度和布局結(jié)果較差的解。在擾動過程中,本文采用增量式評估方法,能夠在線性時間復(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í)驗(yàn)測試用例中任務(wù)并行度較低的計算應(yīng)用,能夠明顯降低動態(tài)重構(gòu)過程中的重構(gòu)時延。相比于未優(yōu)化通信代價的情況,本文所提出的算法實(shí)現(xiàn)了對通信代價的優(yōu)化,但求解時間會相應(yīng)增加。并且對于任務(wù)數(shù)據(jù)依賴關(guān)系越多的實(shí)驗(yàn)測試用例,通信代價的優(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é)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN791
本文編號：2253950
[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é)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN791
【參考文獻(xiàn)】
相關(guān)期刊論文 前6條
1 李春生;周學(xué)海;曾芳玲;王超;;一種基于頂點(diǎn)位置樹的可重構(gòu)軟硬件迭代協(xié)同算法[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2014年04期
2 彭曉明;龐建民;郭浩然;;動態(tài)可重構(gòu)技術(shù)研究綜述[J];計算機(jī)工程與設(shè)計;2012年12期
3 鄒yN;吳強(qiáng);趙遠(yuǎn)寧;;支持動態(tài)可重構(gòu)硬件透明編程的預(yù)配置調(diào)度[J];計算機(jī)工程與應(yīng)用;2008年27期
4 周學(xué)功;梁j;黃勛章;彭澄廉;;可重構(gòu)系統(tǒng)中的實(shí)時任務(wù)在線調(diào)度與放置算法[J];計算機(jī)學(xué)報;2007年11期
5 梁;周學(xué)功;王穎;彭澄廉;;采用預(yù)配置策略的可重構(gòu)混合任務(wù)調(diào)度算法[J];計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報;2007年05期
6 齊驥;李曦;胡楠;周學(xué)海;龔育昌;王峰;;基于硬件任務(wù)頂點(diǎn)的可重構(gòu)系統(tǒng)資源管理算法[J];電子學(xué)報;2006年11期
相關(guān)碩士學(xué)位論文 前3條
1 張吉昕;基于FPGA部分動態(tài)可重構(gòu)技術(shù)的劃分和調(diào)度算法研究[D];武漢理工大學(xué);2014年
2 潘經(jīng)緯;可重構(gòu)系統(tǒng)中任務(wù)實(shí)時調(diào)度和實(shí)時布局算法的研究[D];電子科技大學(xué);2010年
3 施小祥;動態(tài)可重構(gòu)FPGA的布局布線算法研究[D];西安電子科技大學(xué);2007年
，本文編號：2253950
本文鏈接：http://www.lk138.cn/shoufeilunwen/xixikjs/2253950.html
最近更新
教材專著
