一种基于双仲裁时间片策略的可重构硬件任务调度算法

A Double-Arbiter Time-Sliced Tasks Scheduling Algorithm for Reconfigurable System

在可重构系统中，二维布局模型比一维布局模型具有更高的自由度．然而，二维模型获得较高的资源利用率要以复杂的资源管理和任务调度算法为代价，这不但使调度过程变得复杂，而且导致时间开销大，直接影响系统实时性．针对这一问题，在综合考虑性能和算法复杂度的基础上，提出了一种适用于二维可重构器件的双仲裁时间片可重构硬件任务调度算法DATS（Double Arbiters Time-Sliced）．算法采用两个仲裁器对硬件资源进行管理，并根据空间和时间约束动态裁决任务布局位置；同时设计了双仲裁时间片任务调度模式图，对任务的调度和布局过程进行合理分离，使任务调度和布局过程相对独立并简化处理过程．DATS算法的调度时间复杂度为O（N），单任务布局算法的时间复杂度为O（E），其中N为被调度的任务总数，E（〈N）为器件中正在执行的任务数目，实验表明，DATS算法时间开销小，在轻负载情况下任务调度成功率比stuffing算法高1％～2%，在重负载情况下资源利用率保持在80％～85％的水平，与时间复杂度为O（N^2）的算法基本一致，所以更适合于实时情况下的任务调度．

In reconfigurable systems, two-dimensional layout model has a higher degree of freedom than the one-dimensional one. However, higher resource utilization rate is obtained at the cost of more complex resource management and task scheduling algorithms, which not only makes the scheduling process more complicated but also affects the real-time performance by causing higher time overhead. To address this issue, considering both the performance and the algorithm complexity, a double-arbiter time-sliced tasks scheduling algorithm （DATS） based on 2D devices for reconfigurable system is presented. Two arbiters are applied to manage the hardware resources and to dynamically determine the placement of the current task under the space and time constraints. The task scheduling model diagram for DATS is designed. Using the task scheduling model diagram, the scheduling process can be separated from the placement process, making the task scheduling process and the placement process independent from to each other, which simplifies the entire process to a large scale. The time complexity of DATS scheduling is O（N）, and the layout time complexity is O（E）, where N is the total number of tasks to be scheduled, and E（〈N） is the number of the tasks being executed in the logical device. Experiment results showy that the DATS realizes a task scheduling success rate 1%-2% higher than the Stuffing algorithm under the low-load condition, and maintains 80%-85% resource utilization under the heavy-load condition. DATS achieves performance equivalent to that of the algorithms of O（N2） complexity with much lower time overhead, and is therefore more suitable for task scheduling in the realtime environment.