An On-line Energy-efficient Real-time Scheduling Algorithm

doi:10.3969/j.issn.1000-3428.2015.02.009

Abstract

Abstract: With the continuous expansion of the scale of the multi processor system,the issue of energy consumption becomes more and more important. How to save energy becomes an important problem to be solved. Based on the multiprocessor system,On-line Energy-efficient Real-time Scheduling Algorithm(OERSA) aiming at a random task is proposed. According to the arrival time and calculated amount of the existing task,the algorithm estimates the executive voltage / frequency of the new task in the idle processor by using statistical methods,which can meet the deadline and save the energy effectively for not yet arrived tasks. At the same time,considering the task executed on a single processor,the algorithm first calculates the average voltage / frequency required to perform these tasks,thus making all the task execution speed equal as much as possible. When some tasks can not meet the deadline requirements,voltage / frequency for previous not executed tasks will be adjusted high. Experimental results show that OERSA has obvious advantages in the aspect of meeting deadlines and energy consumption saving compared with EDF,HVEA,MEG and ME-MC algorithm.

Key words: multiprocessor system, random task, dynamic voltage / frequency scaling, on-line, real-time, energy-efficient scheduling

摘要： 随着多处理器系统规模的不断扩大,如何节能成为一个亟待解决的重要问题。为此,基于多处理器系统提出一种针对随机任务的在线节能实时调度算法。使用统计方法,根据已有任务的到达时间和计算量估计新任务在空闲处理器上执行的电压/ 频率,使还未到达的任务能够满足截止期限并有效节能。在考虑单个处理器上执行的任务时,计算执行这些任务所需的平均电压/ 频率,使所有任务的执行速度尽量均衡,当某些任务不能满足截止期限要求时,则调高未执行任务的电压/ 频率。实验结果表明,与EDF,HVEA,MEG 和ME-MC 算法相比,该算法在满足截止期限和节能方面具有明显的优势。

关键词: 多处理器系统, 随机任务, 动态电压/ 频率调整, 在线, 实时, 节能调度

CLC Number:

TP316. 4

ZHANG Binlian,XU Hongzhi. An On-line Energy-efficient Real-time Scheduling Algorithm[J]. Computer Engineering.

张彬连,徐洪智. 一种在线节能实时调度算法[J]. 计算机工程.

/ Recommend / Download Citations

URL:

https://www.ecice06.com/EN/Y2015/V41/I2/41

References

参考文献 [ 1 ]　Goller A, Leberl F. Radar Image Processing with Clusters of Computers [ J ]. IEEE Aerospace and Electronics Systems Magazine,2009,24(1):18-22. [ 2 ]　林　闯,田　源,姚　敏. 绿色网络和绿色评价:节能机制、模型和评价[J]. 计算机学报,2011,34 (4): 593-612. [ 3 ]　Li Yu,Liu Yi,Qian Depei. An Energy-aware Heuristic Scheduling Algorithm for Heterogeneous Clusters[C] / / Proceedings of the 15th International Conference on Parallel and Distributed Systems. [S. l. ]:IEEE Press, 2009:407-413. [ 4 ]　过敏意. 绿色计算:内涵及趋势[J]. 计算机工程, 2010,36(10):1-7. [ 5 ]　Jejurikar R, Pereira C, Gupta R. Leakage Aware Dynamic Voltage Scaling for Real-time Embedded Systems[C] / / Proceedings of the 41st Annual Design Automation Conference. San Diego,USA:ACM Press, 2004:275-280. [ 6 ]　Liu Wei,Yin Hang,Du Wei. Dynamic Threshold-based Energy Efficient Scheduling Algorithm for Parallel Tasks on Homogeneous DVS-enabled Clusters [C] / / Proceedings of 2011 International Conference on Cyberenabled Distributed Computing and Knowledge Discovery. Washington D. C. ,USA:IEEE Press,2011: 321-328. [ 7 ]　张冬松,吴　飞,陈芳园,等. 开销敏感的多处理器最优节能实时调度算法[J]. 计算机学报,2012,35(6): 1297-1312. [ 8 ]　Funaoka K,Kato S,Yamasaki N. Energy-efficient Optimal Real-time Scheduling on Multiprocessors[C]/ / Proceedings of the 11th IEEE Symposium on Object Oriented Realtime Distributed Computing. Washington D. C. , USA: IEEE Press,2008:23-30. [ 9 ]　Lee W Y. Energy-efficient Scheduling of Periodic Realtime Tasks on Lightly Loaded Multicore Processors[ J]. IEEE Transactions on Parallel and Distributed Systems,2012,23(3):530-537. [10]　刘　伟,尹　行,段玉光,等. 同构DVS 集群中基于自适应阈值的并行任务节能调度算法[J]. 计算机学报, 2013,36(2):393-407. [11]　朱晓敏,贺　川,王建江,等. 异构计算系统中弹性节能调度策略研究[J]. 计算机学报,2012,35 (6): 1313-1326. [12]　张冬松,吴　彤,陈芳园,等. 多核系统中基于Global EDF 的在线节能实时调度算法[J]. 软件学报,2012, 23(4):996-1009. [13]　张冬松. 多核多处理器系统的节能实时调度技术研究[D]. 长沙:国防科学技术大学,2012. [14]　Kim J K,Siegel H J,Maciejewski A A,et al. Dynamic Resource Management in Energy Constrained Heterogeneous Computing Systems Using Voltage Scaling[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(11):1445-1457. [15]　张彬连,徐洪智. 多处理器系统的在线节能调度算法[J]. 计算机应用,2013,33(10):2787-2791. [16]　Zhu Dakai. Reliability-aware Dynamic Energy Management in Dependable Embedded Real-time Systems[C]/ / Proceedings of IEEE Real-time and Embedded Technology and Applications Symposium. San Jose, USA:IEEE Press,2006:397-407. [17]　Li Jianjun,Shu L, Chen Jianjia, et al. Energy-efficient Scheduling in Nonpreemptive Systems with Real-time Constraints[J]. IEEE Transactions on Systems,2013, 43(2):332-344. 编辑　金胡考

[1]	Jin XU, Xiangdong JIA, Xianghua HAN, Xingyuan ZHANG. Analysis of Non-Linear Age of Information in Industrial Internet of Things for Non-Linear Energy Harvesting [J]. Computer Engineering, 2024, 50(8): 198-206.
[2]	WU Fan, XU Chaonong, ZOU Yinghao. Image Transmission Algorithm for Personnel Monitoring Based on PD-NOMA [J]. Computer Engineering, 2024, 50(6): 266-275.
[3]	CHEN Xiaoyu, SHEN Chen, SHEN Yue, KONG Deming. Real-Time Segmentation Network of Yard Images Based on Improved SwiftNet [J]. Computer Engineering, 2024, 50(6): 296-303.
[4]	WU Cuicui, WANG Weidong. Passive Non-Line-of-Sight Imaging Based on Diffuse Reflection [J]. Computer Engineering, 2024, 50(5): 26-32.
[5]	Haijun DU, Su YU. Dynamic Obstacle Avoidance for Service Robots Based on Spatio-Temporal Graph Attention Network [J]. Computer Engineering, 2024, 50(2): 105-112.
[6]	BAI Junqing, HAN Boxun, ZHANG Fengxia. Deep Learning-Based UAV Image Semantic Segmentation Algorithm Research [J]. Computer Engineering, 2023, 49(4): 233-239.
[7]	ZHANG Sheng, TANG Fan, ZHANG Tianqi, FAN Sen. FCM-SSGP Method for Ultra-Wideband Indoor Localization [J]. Computer Engineering, 2023, 49(3): 211-220.
[8]	Xiaoling WANG, Zhijie HU, Shuaishuai XU, Haoru HUANG. Image Dehazing Algorithm Using Improved Dark Channel Prior and Strategic Fusion [J]. Computer Engineering, 2023, 49(10): 212-221.
[9]	WANG Xiaoxue, WANG Xiaofeng, LIU Yuan. OpenStack-based Docker Scheduling Model with High Resource Utilization [J]. Computer Engineering, 2022, 48(9): 171-179,196.
[10]	LIAN Yixin, CHEN Tao, LI Wei, NAN Longmei. Reconfigurable Research and Circuit Design of Two Types of Nonlinear Cryptographic Components [J]. Computer Engineering, 2022, 48(2): 156-163,172.
[11]	GE Yongjie, WANG Lidan, CHEN Dingxi, DUAN Shukai, GAN Xiuling. Character Recognition and Judgment of Industrial Vision Box Based on Deep Learning [J]. Computer Engineering, 2022, 48(1): 296-304.
[12]	YANG Gang, ZHU Shiling, LI Qiang, ZHAO Kesong. Indoor Firefighter Positioning and NLOS Detection Algorithm Based on UWB and INS [J]. Computer Engineering, 2021, 47(9): 153-161.
[13]	ZHAO Chenyuan, LI Wenxin, ZHANG Qingxi. An Improved Real-Time Semi-Global Stereo Matching Algorithm and Its Hardware Implementation [J]. Computer Engineering, 2021, 47(9): 162-170.
[14]	WANG Fei, XU Zhan, ZHI Ruxin, CHEN Jinhui. OFDM-UWB Channel Environment Recognition Based on Convolutional Neural Network [J]. Computer Engineering, 2021, 47(7): 161-167.
[15]	LUO Shuo, HOU Jin, TAN Guanghong, HAN Yanpeng. A Low Parameter Real-Time Target Tracking Algorithm Based on Siamese Convolutional Network [J]. Computer Engineering, 2021, 47(2): 84-89.

Please choose a citation manager

Content to export