动态可重构系统中任务调度与布局算法研究

发布时间：2018-10-05 15:42

【摘要】：现场可编程门阵列(Field-Programmable Gate Array,FPGA)是一类可编程集成电路,既能高效地实现电路设计又能灵活地改变电路架构,具有可重构的功能。动态可重构系统基于FPGA的动态重构特性,能够以有限的资源适应不同的计算需求,是硬件加速技术的有效解决方案。通过动态重构设计,大规模计算应用中的任务可以动态地分时复用硬件资源。任务的重构次序和重构位置会影响系统运行的性能、重构资源的利用效率和任务之间的通信代价,需要对任务进行有效的调度和布局。针对现有的FPGA架构,本文对动态可重构系统中相互耦合的划分、调度和布局问题进行了研究,建立了调度和布局的问题模型,提出了相应的优化算法。为了表示动态可重构系统中的任务调度和布局,本文提出三元序列组(Se-quence Triple)的表示方法。三元序列组由三个同时集成时域和空域划分的任务嵌套序列PS、MS、RS构成。(PS,MS)为混合嵌套序列对(Hybrid Nested Sequence Pair),表示所有重构区域在各个调度时刻的任务布局。通过求解混合嵌套序列对的最长公共子序列,能够计算出任务位置坐标。RS为重构序列,表示所有重构区域中任务的配置先后顺序。将重构序列和任务数据依赖关系相结合,可以构建重构约束图(Reconfigurable Constraints Graph),表示动态重构过程中任务的优先约束关系。通过求解重构约束图中到顶点的最长路径,能够计算出任务配置时刻和执行时刻。在动态可重构过程中,任务调度和布局必须满足硬件资源约束和任务数据依赖关系。本文给出了可行任务调度和布局的充要条件,可以确立三元序列组完整的可行解空间。本文设计的优化算法基于模拟退火算法(Simulated Annealing),能够同时优化调度和布局。根据三元序列组的表示特征,本文采用删除插入的扰动方法:从三元序列组中随机删除一个任务,将所删除的任务插入三个删除后的任务序列中新的合适的位置。不同的插入位置对应不同的调度和布局解。通过枚举和评估可行插入位置,能够跳过很多调度和布局结果较差的解。在扰动过程中,本文采用增量式评估方法,能够在线性时间复杂度内评估所有可行插入位置所对应的调度和布局解。本文实验验证了调度和布局算法的有效性和高效性。实验结果表明,本文所提出的算法能够对调度和布局的进行集成优化,可以在保证较好调度效果的同时,提高布局成功率。并且对于实验测试用例中任务并行度较低的计算应用,能够明显降低动态重构过程中的重构时延。相比于未优化通信代价的情况,本文所提出的算法实现了对通信代价的优化,但求解时间会相应增加。并且对于任务数据依赖关系越多的实验测试用例,通信代价的优化效果越好。
[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.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN791

【参考文献】