一种基于可重构多FPGA的任务调度与任务复制方法

Task Schedule and Task Duplicate Method Based on Reconfigurable Multi-FPGAs

在可重构多现场可编程逻辑门阵列(FPGA)系统中,任务调度是一个极其重要的研究方向。参照同构与异构计算领域的调度算法,结合可重构多FPGA计算模型的自身特点,在现有的调度算法的基础上,将任务复制方法引入到可重构多FPGA系统计算领域,如果任务余图最长路经上的父子节点不在同一FPGA上,通过寻找FPGA上的复制空间,提出的算法将父节点尽可能复制在子节点所在的FPGA上,减小了任务之间的通信开销。实验结果表明,对于任务调度有向无环图,提出方法的调度长度优于或等于前人方法的性能下界,而且,FPGA利用率有所提高。

Task scheduling is an extremely important research direction in the reconfigurable multi-FPGAs systems. Referencing to the scheduling algorithm in homogeneous and heterogeneous computing, combining its own characteristics of the reconfigurable multi-FPGA computing model, and based on the existing scheduling algorithm, task duplication method is introduced in this paper： If the parent and son nodes on the longest path of the excess task graph are not on the same FPGA, through looking for the Duplicate Space on the FPGA,the proposed algorithm will duplicate the parent node onto the FPGA where the child node is, reducing the cost of communication between tasks. The experimental results show that for a directed acyclic graph of the task scheduling, the makespan of the proposed method is superior to or equal to the performance lower bound of the previous methods, moreover, the utilization of FPGA has been increased.