A Boundary-Table-Based Algorithm for Reconfigurable Resource Management and Hardware Task Scheduling

Reconfigurable computing (RC) is a kind of computation schema with hardware efficiency and software flexibility. The management of the reconfigurable resources and the scheduling of the hardware tasks are two critical factors that are concerned closely with the performance of RC. Focusing on the scheduling of hardware tasks in linear dimension reconfigurable device, one method based on boundary table (BT) is proposed for reconfigurable resource management by using the BT data structure to record the regional boundaries and their location relations in R-T coordinates. On the basis of the method, a new algorithm BT-P (boundary table placement) is also proposed to achieve the scheduling and placement of hardware tasks. By utilizing the weighted overlapping boundary length as the evaluation function and combining it with the reconfigurable resource management method, the proposed scheduling algorithm can realize optimization in a smaller runtime overhead way. The simulation results show that, compared with the stuffing algorithm, the proposed algorithm can effectively increase the chip utilization by 5% to 11% with the change of the load rate and lower rejection rate of the tasks by 9% to 11% with the change of load rate and the relaxation factor. The average time overhead of each task in scheduling and placement is between 2-4 microseconds.