可重构系统中的实时任务在线调度与放置算法  

On-Line Scheduling and Placement of Real-Time Tasks for Reconfigurable Computing System

作　　者：周学功[1] 梁樑[1] 黄勋章[1] 彭澄廉[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机学报》2007年第11期1901-1909,共9页Chinese Journal of Computers

基　　金：国家自然科学基金(60573105)资助.~~

摘　　要：有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信息,实现了完全识别的调度.实验表明,与已有的算法相比,新算法显著地改善了调度效果,而运行开销没有明显增加.Efficient task scheduling and placement are very important for obtaining high performance in reconfigurable computing system. This paper focuses on the on-line scheduling of realtime tasks on a 2-dimensional reconfigurable device, and introduces the notion of recognitioncomplete for scheduling algorithms, that is the algorithm do not reject a task when a feasible schedule for this task exists. A new on-line scheduling and placement algorithm is proposed. By utilizing the temporal information of real-time tasks thoroughly, the proposed algorithm achieves recognition-complete. The simulation results show that the proposed algorithm gains a prominent improvement in scheduling performance over previous algorithms, while the run-time efficiency is preserved.

关 键 词：可重构计算 在线调度 实时 放置策略 完全识别 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]