吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (4): 1112-1117.doi: 10.13229/j.cnki.jdxbgxb201404032

• • 上一篇    下一篇

制的容错节能调度算法

张忆文, 郭锐锋   

  1. 1.中国科学院 沈阳计算技术研究所, 沈阳 110168;
    2.中国科学院大学, 北京 100039
  • 收稿日期:2013-01-07 出版日期:2014-07-01 发布日期:2014-07-01
  • 通讯作者: 郭锐峰(1968-), 男, 研究员, 博士生导师.研究方向:实时系统与数控技术.E-mail:grf@sict.ac.cn
  • 作者简介:张忆文(1988-), 男, 博士研究生.研究方向:低功耗调度.E-mail:zywsy2010@126.com
  • 基金资助:
    国家科技重大专项项目(2012ZX01029001-002); 国家科技支撑计划项目(2012BAF13B08)

Fault-tolerant energy-saving scheduling algorithm base on checkpoint scheme

ZHANG Yi-wen1, 2, GUO Rui-feng1   

  1. 1.Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China;
    2.University of Chinese Academy of Sciences, Beijing 100039, China
  • Received:2013-01-07 Online:2014-07-01 Published:2014-07-01

摘要: 综合考虑了实时系统的容错和节能, 针对处理器提供离散的频率和电压, 提出了基于检查点机制的容错节能调度算法(CPFTES)。该算法利用动态电压缩放技术节能, 通过确定优化的检查点且使用检查点机制实现容错。当任务发生错误时, 恢复任务从已保存的检查点重新启动以最大的处理器速度运行, 确保任务不错过截止期限。提出了H_SPEED和A_SPEED两种速度选择策略。仿真实验表明:在PXA250处理器上, CPFTES_A_SPEED比CPFTES_NODVS平均节约66.18%的能耗, CPFTES_A_SPEED比 CPFTES_H_SPEED节约0~19.41%的能耗。

关键词: 计算机系统结构, 容错, 检查点, 动态电压缩放, 功耗管理

Abstract: A Fault-tolerant Energy-saving Scheduling Algorithm base on Checkpoint Scheme (CPFTES) is proposed. The algorithm considers fault tolerance and power management in real-time system that the discrete frequency and voltage are provided by processors. The fault tolerance is achieved via optimal checkpoint scheme and the power management is carried out using dynamic voltage scaling. The optimal checkpoints can help the task to guarantee the timing constraints and reliability. If a task fails, it can restart from a saved checkpoint and execute at the maximum speed to ensure the deadlines are met. Two speed selection strategies, named H_SPEED and A_SPEED, of the algorithm are proposed. Simulation results show that CPFTES_A_SPEED can save about 66.18% energy compared to CPFTES_NODVS and save about 0~19.41% energy compared to CPFTES_H_SPEED under PXA250 processors.

Key words: computer system architecture, fault-tolerance, checkpoint, dynamic voltage scaling, power management

中图分类号: 

  • TP316.2
[1] 刘娴, 郭锐锋, 丁万夫. 基于优先级混合策略的回卷恢复容错实时系统的可调度性[J]. 吉林大学学报:工学版, 2012, 42(5):1243-1250. Liu Xian, Guo Rui-feng, Ding Wang-fu. Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy[J]. Journal of Jilin University: Engineering and Technology Edition, 2012, 42(5): 1243-1250.
[2] 张智超, 桑楠, 熊光泽. 基于检查点机制的容错实时调度算法CP-PRA[J]. 计算机工程与设计, 2004, 25(4): 508-512. Zhang Zhi-chao, Sang Nan, Xiong Guang-ze. CP-PRA fault-tolerant real time scheduling based on checkpoint scheme[J]. Computer Engineering and Design, 2004, 25(4): 508-512.
[3] Chen Da-ren, Chen You-shyang. An efficient DVS algorithm for fixed-priority real-time applications[C]∥Parallel and Distributed Processing with Applications (ISPA), Taibei, 2010.
[4] Zhang Zhi, Li Fei, Aydin H. Optimal speed scaling algorithms under speed change constraints[C]∥International Conference on High Performance Computing and Communications, Banff AB, 2011.
[5] Melhem R, Mosse D, Elnozahy E N. The interplay of power management and fault recovery in real-time systems[J]. IEEE Transaction on Computer, 2004, 53(2): 217-231.
[6] Zhang Ying, Chakrabarry K, Swaminaathan V. Energy-aware fault tolerance in fixed-priority real-time embedded systems[C]∥International Conference on Computer Aided Design, San Jose, CA, 2003.
[7] Li Guo-hui, Hu Fang-xiao, Ling Yuan. An energy efficient fault-tolerant scheduling scheme for aperiodic tasks in embedded real-time systems[C]∥Multimedia and Ubiquitous Engineering, Qingdao, 2009.
[8] Kim K H, Kim J. An adaptive DVS checkpointing scheme for fixed-priority tasks with reliability constraints in dependable real-time embedded system[J]. Embedded Software and Systems, 2007, 45(23): 560-571.
[9] Zhao B, Aydin H, Zhu D. Energy management under general task-level reliability constraints[C]∥Proc of the 18th IEEE Real Time and Embedded Technology and Applications Symposium, Beijing, 2012.
[10] Wang Wei-xun, Ranka Sanjay, Mishra Prabhat. Energy-aware dynamic slack allocation for real-time multitasking system[J]. Elsevier Sustainable Computing: Informatics and Systems, 2012, 2(3):128-137.
[11] Bini E, Buttazzo G, Lipari G. Speed modulation in energy-aware real-time systems[C]∥Proc of the 17th Euromicro Conference on Real-Time Systems, Balearic Islands, 2005.
[12] Gong Min-Sik, Yeong S, Lee C. On-line dynamic voltage scaling on processor with discrete frequency and voltage levels[C]∥Convergence Information Technology, Gyeongju, 2004.
[13] Niu L, Li W. Energy-efficient fixed-priority scheduling for real-time systems based on threshold work-demand analysis[C]∥Proceedings of the 9th International Hardware/Software Codesign and System Synthesis, Taibei, 2011.
[1] 余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2] 董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3] 李炜, 李亚洁. 基于离散事件触发通信机制的非均匀传输网络化控制系统故障调节与通信满意协同设计[J]. 吉林大学学报(工学版), 2018, 48(1): 245-258.
[4] 赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[5] 刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[6] 董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[7] 于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[8] 邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[9] 魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[10] 郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[11] 魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[12] 车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[13] 李元春, 周帆, 马天豪, 赵博. 基于多步时延的可重构机械臂并发故障分散容错控制[J]. 吉林大学学报(工学版), 2015, 45(6): 1874-1880.
[14] 曹慧超, 李炜. 离散事件触发非线性网络化控制系统鲁棒容错控制[J]. 吉林大学学报(工学版), 2015, 45(6): 1895-1905.
[15] 董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!