异构多核片上系统的帧任务节能分配算法

doi:10.19665/j.issn1001-2400.2019.03.014

西安电子科技大学学报 ›› 2019, Vol. 46 ›› Issue (3): 89-95.doi: 10.19665/j.issn1001-2400.2019.03.014

异构多核片上系统的帧任务节能分配算法

夏军,杨逸,林毅

重庆邮电大学通信与信息工程学院,重庆 400065

收稿日期:2018-11-13 出版日期:2019-06-20 发布日期:2019-06-19
作者简介:夏军(1979-),男,高级工程师,硕士,E-mail: xiajun@cqupt.edu.cn.
基金资助:
国家自然科学基金(61501074);国家科技重大专项(2018ZX0301007-004);重庆市教委科技研究项目(KJ1600436)

Algorithm for scheduling energy-saving frame-based tasks on the heterogeneous multi-core SoC

XIA Jun,YANG Yi,LIN Yi

School of Communication and Information Engineering, Chongqing Univ. of Posts and Telecommunications, Chongqing 400065, China

Received:2018-11-13 Online:2019-06-20 Published:2019-06-19

摘要/Abstract

摘要：

针对异构多核片上系统的高能耗问题,提出了一种对帧任务进行分配的高能效两级优化算法。算法将系统能耗最小化问题定义为非线性整数规划问题。第一级优化将问题进行松弛处理,求解得到任务分配矩阵;第二级优化采用带判决门限的取整函数更新分配矩阵,构造新的规划问题并求解;最后结合两级优化得出最终的任务分配矩阵。仿真结果表明,与部分启发式算法相比,该算法能耗降低了20%50%,接近理论最优能耗;与能耗接近的其他优化算法相比,求解时间减少了54%75%。

关键词: 实时系统, 异构系统, 节能调度

Abstract:

Aiming at the high energy consumption of the heterogeneous multi-core system on the chip, an efficient two-level optimization algorithm for frame task assignment is proposed. The algorithm defines the problem of minimizing system energy consumption as a nonlinear integer programming problem. The first-level optimization is used to relax and solve the problem. The second-level optimization uses the rounding function with the decision threshold to update the assignment matrix, and then constructs a new planning problem and solves it. Finally, combining the two-level optimization results to formulate the final assignment matrix. Simulation shows that compared with some heuristic algorithms, the energy consumption of the algorithm is reduced by 20%50%, which is close to the theoretical optimal energy consumption. Compared with other optimization algorithms with similar energy consumption, the complete time is reduced by 54%75%.

Key words: real-time systems, heterogeneous systems, energy-saving scheduling

中图分类号:

TP316.2

夏军,杨逸,林毅. 异构多核片上系统的帧任务节能分配算法[J]. 西安电子科技大学学报, 2019, 46(3): 89-95.

XIA Jun,YANG Yi,LIN Yi. Algorithm for scheduling energy-saving frame-based tasks on the heterogeneous multi-core SoC[J]. Journal of Xidian University, 2019, 46(3): 89-95.

图/表 4

表1

图1

图2

图3

参考文献 13

[1]	SUN W, SUGAWARA T . Heuristics and Evaluations of Energy-aware Task Mapping on Heterogeneous Multiprocessors [C]// Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum. Washington: IEEE Computer Society, 2011: 599-607.
[2]	IZAKIAN H, ABRAHAM A, SNASEL V . Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments [C]//Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization. Washington: IEEE Computer Society, 2009: 8-12.
[3]	AWAN M A, PETTERS S M . Energy-aware Partitioning of Tasks onto a Heterogeneous Multi-core Platform [C]//Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium. Washington: IEEE Computer Society, 2013: 205-214.
[4]	AWAN M A, YOMSI P M, NELISSEN G , et al. Energy-aware Task Mapping onto Heterogeneous Platforms Using DVFS and Sleep States[J]. Real-Time Systems, 2016,52(4):450-485. doi: 10.1007/s11241-015-9236-x
[5]	ZAHAF H E, BENYAMINA A E H, OLEJNIK R et al. Energy-efficient Scheduling for Moldable Real-time Tasks on Heterogeneous Computing Platforms[J]. Journal of Systems Architecture, 2017,74:46-60. doi: 10.1016/j.sysarc.2017.01.002
[6]	LI D, WU J . Minimizing Energy Consumption for Frame-based Tasks on Heterogeneous Multiprocessor Platforms[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(3):810-823. doi: 10.1109/TPDS.2014.2313338
[7]	LI Y, NIU J W, ATIQUZZAMAN M , et al. Energy-aware Scheduling on Heterogeneous Multi-core Systems with Guaranteed Probability[J]. Journal of Parallel and Distributed Computing, 2017,103:64-76. doi: 10.1016/j.jpdc.2016.11.014
[8]	THAMMAWICHAI M, KERRIGAN E C . Energy-efficient Real-time Scheduling for Two-type Heterogeneous Multiprocessors[J]. Real-Time Systems, 2018,54(1):132-165. doi: 10.1007/s11241-017-9291-6
[9]	刘亚秋, 陈雨佳, 景维鹏 , 等. 基于多核处理器的低能耗任务调度优化算法[J]. 沈阳工业大学学报, 2017,39(1):48-54.
	LIU Yaqiu, CHEN Yujia, JING Weipeng , et al. Optimization Algorithm for Task Scheduling with Low Energy Consumption Based on Multi-core Processor[J]. Journal of Shenyang University of Technology, 2017,39(1):48-54.
[10]	KONG F X, YI W, DENG Q X . Energy-efficient Scheduling of Real-time Tasks on Cluster-based Multicores [C]//Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. Piscataway: IEEE, 2011: 1135-1140.
[11]	BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2013.
[12]	Texas Instruments Inc. AM572x Power Estimation Tool[R/OL]. [ 2018- 7- 30]. . http://www.ti.com/lit/an/spraca0/spraca0.pdf
[13]	STAVRINIDES G L, KARATZA H D . The Impact of Workload Variability on the Energy Efficiency of Large-scale Heterogeneous Distributed Systems[J]. Simulation Modelling Practice and Theory, 2018,89:135-143. doi: 10.1016/j.simpat.2018.09.013

序号	图形处理器			数字信号处理器			微处理器
序号	电压/V	频率/GHz	功率/mW	电压/V	频率/ GHz	功率/mW	电压/V	频率/GHz	功率/mW
1	0.89	0.425	299.0	0.92	0.50	296.2	0.89	0.500	382.6
2	0.89	0.450	316.2	0.92	0.55	325.9	0.89	0.750	573.9
3	1.10	0.500	536.6	0.92	0.60	355.5	0.89	0.850	650.4
4	1.22	0.532	702.4	1.10	0.65	550.6	0.89	1.000	765.2
5	1.22	0.625	825.1	1.10	0.70	592.9	1.10	1.176	1 375.0
6	1.22	0.750	990.2	1.20	0.75	756.0	1.22	1.300	1 869.0
7	N/A	N/A	N/A	N/A	N/A	N/A	1.22	1.500	2 157.0

异构多核片上系统的帧任务节能分配算法

Algorithm for scheduling energy-saving frame-based tasks on the heterogeneous multi-core SoC

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 13

相关文章 3

Metrics

本文评价

推荐阅读 10

[1]	孙健;张兴军;董小社. 一种可靠性框图的异构系统可用性评价模型[J]. 西安电子科技大学学报, 2016, 43(3): 190-196.
[2]	张海宾;段振华. 稠密时间区间时序逻辑的可满足性判定 [J]. J4, 2007, 34(3): 463-467.
[3]	雍信阳;蔡希尧;陈平. 6种需求描述方法的比较[J]. J4, 1996, 23(2): 0-0.