動(dòng)態(tài)可重構(gòu)系統(tǒng)中任務(wù)調(diào)度與布局算法研究
[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
本文鏈接:http://www.lk138.cn/shoufeilunwen/xixikjs/2253950.html