期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种基于代价抢占的混合可重构任务调度算法

Scheduling algorithm preempted based on price for hybrid reconfigurable tasks
下载PDF
导出
摘要 针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。 Concerning scheduling problem of the hybrid reconfigurable tasks that including both dependent tasks and independent tasks,this paper proposed a real-time scheduling algorithm preempted based on price for hybrid reconfigurable tasks.Calculated the equal running deadline of dependent tasks to make the hybrid reconfigurable tasks be configurated according to configuration deadline.Considering the characteristic of dependent tasks,it confirmed and dropped the dependent tasks set that could＇t be scheduled successfully in advance according to the sufficient condition for deciding failing schedule of dependent reconfigurable task set;the limited pre-configuration avoided the dependent tasks occuping reconfigurable resources too earlier than it could start running time;used the preempted based on price to reduce the number of scheduling failed tasks.Simulation results show that,this scheduling algorithm can increase the task scheduling success rate.
作者 韩晓亚 汪斌强 黄万伟 王保进
机构地区 国家数字交换系统工程技术研究中心
出处 《计算机应用研究》 CSCD 北大核心 2011年第11期4040-4044,共5页 Application Research of Computers
基金 国家"863"高技术研究发展计划资助项目(2009AA01A334 2009AA012201 2008AA01A323 2008AA01A325 2008AA01A326)
关键词 混合可重构任务 实时调度 有限预配置 基于代价抢占 调度成功率 hybrid reconfigurable tasks real-time scheduling limited pre-configuration preempted based on price scheduling success rate
分类号 TP393 [自动化与计算机技术—计算机应用技术] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献16

  • 1SEDCOLE P, BLODGET B, BECKER T, et al. Modular dynamic reconfiguration in virtex FPGAs [ J ]. Computers and Digital Techniques, 2006,153 ( 3 ) : 157-164.
  • 2BAZARGAN K, KASTNER R, SARRAFZADEH M. Fast template placement for reconfigurable computing systems[ J]. IEEE Design & Test of Computers ,2000,17 (1) :68-83.
  • 3STEIGER C, WALDER H, PLATZNER M. Heuristics for online scheduling real-time tasks to partially reconfigurable devices [ C ]// Lecture Notes in Computer Science,vol 2778. Heidelberg: Springer, 2003:575- 584.
  • 4MARCONI T, LU Yi, BERTELS K, et al. Online hardware task scheduling and placement algorithm on partially reconfigurable de- vices [ C ]//Proc of the 4th International Workshop on Reconfigurable Computing: Architectures, Tools and Applications. Heidelberg: Springer-Verlag, 2008:306-311.
  • 5黄万伟,汪斌强,王保进,于婧.面向区分服务的可重构任务在线调度算法[J].计算机辅助设计与图形学学报,2010,22(4):717-723. 被引量：4
  • 6BUELL D, EI-GHAZAWI T, GAJ K, et al. Guest editors' introduction: high-performance reconfigurable computing [ J ]. Computer, 2007,40 ( 3 ) : 23 - 27.
  • 7DITTMANN F, GOTZ M. Applying single processor algorithms to schedule tasks on recorffigurable devices respecting reconfiguration times[ C]//Proc of the 20th International Parallel and Distributed Processing Symposium. [ S.l. ] : IEEE Computer Society, 2006:229- 232.
  • 8DITTMANN F, FRANK S. Hard real-time reconfiguration port scheduling[ C]//Proc of Design, Automation & Test in Europe Conference & Exhibition. [ S. l. ] : IEEE Computer Society, 2007 : 1 - 6.
  • 9ZHIYUAN L, SCOTT H. Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation [ C ]//Proc of IEEE/ACM International Symposium on Filed-Programmalbe Gate Arrays. [ S. l. ] : 1EEE Computer Society, 2002: 187-195.
  • 10BANERJEE S, BOZORGZADEH E, DUTT N. Considering run-time reconfiguration overhead in task graph transformation for dynamically reconfigurable architectures [ C ]//Proc of the 13th Annuals IEEE Symposium on Field-Programmable Custom Computing Machines. [ S. l. ] :IEEE Computer Society, 2005:732-738.

二级参考文献23

  • 1周博,邱卫东,谌勇辉,彭澄廉.基于簇的层次敏感的可重构系统任务划分算法[J].计算机辅助设计与图形学学报,2006,18(5):667-673. 被引量：12
  • 2梁,周学功,王颖,彭澄廉.采用预配置策略的可重构混合任务调度算法[J].计算机辅助设计与图形学学报,2007,19(5):635-641. 被引量：12
  • 3Compton K,Hauck S.Reconfigurable computing:a survey of systems and software[J].ACM Computing Surveys,2002,34(2):171-210.
  • 4Danne K,Miihlenbernd R,Platzner M.Executing hardware tasks on dynamically reconfigurable devices under real-time conditions[C]//Proceedings of Field Programmable Logic and Applications,Madrid,2006:1-6.
  • 5Walder H,Platzner M.Online scheduling for block partitioned reconfigurable devices[C]//Proceedings of Design,Automation and Test in Europe Conference and Exhibition,Munich,2003:290-295.
  • 6Bazargan K,Kastner R,Sarrafzadeh M.Fast template placement for reconfigurable computing systems[J].IEEE Design and Test of Computers,2000,7(1):68-83.
  • 7Steiger C,Walder H,Platzner M.Operating systems for reconfigurable embedded platforms:online scheduling of real-time tasks[J].IEEE Transactions on Computers,2004,53(11):1393-1407.
  • 8Marconi T,Lu Y,Bertels K,et al.Online hardware task scheduling and placement algorithm on partially reconfigurable devices[C]//Proceedings of the 4th International Workshop on Applied Reconflgurable Computing,Heidelberg,2008:306-311.
  • 9Handa M,Vemuri R.An efficient algorithm for finding empty space for online FPGA placement[C]//Proceedings of the 41st Annual Design Automation Conference,San Diego,2004:960-965.
  • 10Steiger C,Walder H,Platzner M,et al.Online scheduling anti placement of real-time tasks to partially reconfigurable devices[C]//Proceedings of the 24th IEEE Real-Time Systems Symposium,Cancun,2003:224-235.

共引文献14

计算机应用研究
2011年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部