A Scheduling Algorithm for Dynamic Reconfigurable Computing

Dynamic reconfigurable system can be partially configured at run-time, without disturbing the execution of original functions. Such system has become the focus of research in recent years. The scheduling of hardware tasks is one of the critical factors that is concerned closely with the performance of the dynamic reconfigurable computing system. In this paper, an MGS (minimum gap scheduling) algorithm is proposed, which employs a 2-dimentional time-space coordinate system for the hardware tasks to allocate the resources on chip and the time slices of execution. The concepts of task shadow and cost function are also presented to facilitate the process of scheduling. The algorithm can reduce the waste of reconfigurable resources and can effectively improve the parallelism of the tasks. The algorithm is quite easy to implement and is suitable to be applied for both situations of real-time and non-real-time. The simulation results show that the MGS algorithm can not only reduce the scheduling overhead, but also achieve higher chip utilization and lower task rejection ratio than using other existent scheduling algorithms at the same time.