一种面向动态可重构计算的调度算法

硬件任务的调度是影响动态可重构系统性能的关键因素之一.提出一种任务间最小空隙调度算法MGS(minimum gap scheduling algorithm),该算法借助任务投影和调度代价函数,采用二维时空坐标系协调各硬件任务占用的芯片资源和执行时间,可有效减少系统资源浪费,提高并行度.MGS算法策略直观,调度开销小,且同时适用于实时和非实时场合.仿真实验表明,与已有算法相比,MGS算法不但降低了硬件任务的调度时间开销,而且具有更高的芯片利用率和更低的任务拒绝率.

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.