一种基于双仲裁时间片策略的可重构硬件任务调度算法  

A Double-Arbiter Time-Sliced Tasks Scheduling Algorithm for Reconfigurable System

作　　者：杨志华[1] 伍卫国[1] 王涛[1] 钱德沛[2] 

机构地区：[1]西安交通大学计算机科学与技术系,西安710049 [2]北京航空航天大学中德软件新技术研究所,北京100191

出　　处：《计算机学报》2013年第9期1850-1867,共18页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2008AA01A202;2011AA01A204);国家自然科学基金(61073011;61133004);国际科技合作计划项目(2009DFA12110);国家科技支撑计划项目(2011BAH04B03)资助~~

摘　　要：在可重构系统中，二维布局模型比一维布局模型具有更高的自由度．然而，二维模型获得较高的资源利用率要以复杂的资源管理和任务调度算法为代价，这不但使调度过程变得复杂，而且导致时间开销大，直接影响系统实时性．针对这一问题，在综合考虑性能和算法复杂度的基础上，提出了一种适用于二维可重构器件的双仲裁时间片可重构硬件任务调度算法DATS（Double Arbiters Time-Sliced）．算法采用两个仲裁器对硬件资源进行管理，并根据空间和时间约束动态裁决任务布局位置；同时设计了双仲裁时间片任务调度模式图，对任务的调度和布局过程进行合理分离，使任务调度和布局过程相对独立并简化处理过程．DATS算法的调度时间复杂度为O（N），单任务布局算法的时间复杂度为O（E），其中N为被调度的任务总数，E（〈N）为器件中正在执行的任务数目，实验表明，DATS算法时间开销小，在轻负载情况下任务调度成功率比stuffing算法高1％～2%，在重负载情况下资源利用率保持在80％～85％的水平，与时间复杂度为O（N^2）的算法基本一致，所以更适合于实时情况下的任务调度．In reconfigurable systems, two-dimensional layout model has a higher degree of freedom than the one-dimensional one. However, higher resource utilization rate is obtained at the cost of more complex resource management and task scheduling algorithms, which not only makes the scheduling process more complicated but also affects the real-time performance by causing higher time overhead. To address this issue, considering both the performance and the algorithm complexity, a double-arbiter time-sliced tasks scheduling algorithm （DATS） based on 2D devices for reconfigurable system is presented. Two arbiters are applied to manage the hardware resources and to dynamically determine the placement of the current task under the space and time constraints. The task scheduling model diagram for DATS is designed. Using the task scheduling model diagram, the scheduling process can be separated from the placement process, making the task scheduling process and the placement process independent from to each other, which simplifies the entire process to a large scale. The time complexity of DATS scheduling is O（N）, and the layout time complexity is O（E）, where N is the total number of tasks to be scheduled, and E（〈N） is the number of the tasks being executed in the logical device. Experiment results showy that the DATS realizes a task scheduling success rate 1%-2% higher than the Stuffing algorithm under the low-load condition, and maintains 80%-85% resource utilization under the heavy-load condition. DATS achieves performance equivalent to that of the algorithms of O（N2） complexity with much lower time overhead, and is therefore more suitable for task scheduling in the realtime environment.

关 键 词：可重构 时间片 双仲裁 任务调度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]