A double-arbiter time-sliced tasks scheduling algorithm for reconfigurable system

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 show 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(N²) complexity with much lower time overhead, and is therefore more suitable for task scheduling in the real-time environment.