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

• 作者: 伍卫国 杨志华 王涛 钱德沛
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 可重构 时间片 双仲裁 任务调度
• 年，卷（期）: 2013,（9）
• 所属期刊栏目: 计算机理论
• 页码范围: 1850-1867
• 页数: 18页
• 分类号: TP301
• 字数: 13793字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2013.01850

摘要

在可重构系统中,二维布局模型比一维布局模型具有更高的自由度.然而,二维模型获得较高的资源利用率要以复杂的资源管理和任务调度算法为代价,这不但使调度过程变得复杂,而且导致时间开销大,直接影响系统实时性.针对这一问题,在综合考虑性能和算法复杂度的基础上,提出了一种适用于二维可重构器件的双仲裁时间片可重构硬件任务调度算法DATS(Double Arbiters Time-Sliced).算法采用两个仲裁器对硬件资源进行管理,并根据空间和时间约束动态裁决任务布局位置；同时设计了双仲裁时间片任务调度模式图,对任务的调度和布局过程进行合理分离,使任务调度和布局过程相对独立并简化处理过程.DATS算法的调度时间复杂度为O(N),单任务布局算法的时间复杂度为O(E),其中N为被调度的任务总数,E(＜N)为器件中正在执行的任务数目,实验表明,DATS算法时间开销小,在轻负载情况下任务调度成功率比stuffing算法高1％～2％,在重负载情况下资源利用率保持在80％～85％的水平,与时间复杂度为O(N2)的算法基本一致,所以更适合于实时情况下的任务调度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钱德沛	北京航空航天大学中德软件新技术研究所	98	550	12.0	18.0
2	伍卫国	西安交通大学计算机科学与技术系	93	1002	15.0	29.0
3	王涛	西安交通大学计算机科学与技术系	64	268	10.0	13.0
4	杨志华	西安交通大学计算机科学与技术系	4	18	3.0	4.0