摘要
硬件任务的调度是影响动态可重构系统性能的关键因素之一.提出一种任务间最小空隙调度算法MGS(minimum gapscheduling algorithm),该算法借助任务投影和调度代价函数,采用二维时空坐标系协调各硬件任务占用的芯片资源和执行时间,可有效减少系统资源浪费,提高并行度.MGS算法策略直观,调度开销小,且同时适用于实时和非实时场合.仿真实验表明,与已有算法相比,MGS算法不但降低了硬件任务的调度时间开销,而且具有更高的芯片利用率和更低的任务拒绝率.
Dynamic reconfigurable system can be partially configured at run-time, without disturbing the execution of original functions. Such system has become the Socus 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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2007年第8期1439-1447,共9页
Journal of Computer Research and Development
基金
高校博士点基金项目(20050358040)
安徽省自然科学基金项目(070412030)
关键词
动态可重构
调度算法
布局算法
时空坐标系
代价函数
dynamic reconfiguration
scheduling algorithm
placement algorithm
time-space coordinate system
cost function
