计算机应用 ›› 2010, Vol. 30 ›› Issue (11): 2870-2872.

• 先进计算 • 上一篇    下一篇

基于放置代价的可重构系统任务统一调度算法

蔡富强1,郭兵2,沈艳3,王继禾4,伍元胜2   

  1. 1. 四川大学
    2. 四川大学 计算机学院,成都610065
    3. 成都信息工程学院 控制工程学院,成都610225
    4. 四川大学 计算机学院
  • 收稿日期:2010-04-26 修回日期:2010-06-23 发布日期:2010-11-05 出版日期:2010-11-01
  • 通讯作者: 蔡富强

Unified task scheduling algorithm of reconfigurable system based on placement cost

  • Received:2010-04-26 Revised:2010-06-23 Online:2010-11-05 Published:2010-11-01

摘要: 高效的任务调度算法对可重构系统的性能有极大的影响。针对目前可重构系统任务在线调度算法的不足,提出了一种基于放置代价的调度算法。该算法考虑了3种代价,分别为:硬件任务在FPGA上的执行时间、占用的FPGA面积以及FPGA的碎片情况,并且也考虑了软硬件任务的统一调度。在调度过程中,当代价超过设定的阈值时,就拒绝其在FPGA上运行,并由CPU执行其软实现。通过合理地拒绝一些代价较大的任务,能够从整体上提高任务调度成功率。实验表明,同已有算法相比,该算法能够获得更高的任务截止保证率。

关键词: 可重构系统, 调度算法, 放置算法, 放置代价, 硬件任务

Abstract: High efficient task scheduling algorithms can greatly influence the performance of reconfigurable systems. This paper analyzed the disadvantages of some current on-line reconfigurable system task scheduling algorithms, and proposed a new scheduling algorithm based on placement cost. This scheduling algorithm considered three types of cost, including hardware task execution time in FPGA, occupied FPGA area and fragmentation situation of FPGA, and also considered the unified scheduling of hardware and software tasks. When a hardware task was in scheduling, if the placement cost exceeded the setting threshold value, the task would be rejected to run in FPGA, but its software implementation could run in CPU. By reasonably rejecting some high cost tasks, this algorithm could achieve a higher overall successful scheduling rate. The simulation results show that this scheduling algorithm can achieve a higher deadline-guarantee ratio than others.

Key words: reconfigurable system, scheduling algorithm, placement algorithm, placement cost, hardware task