面向多核系统的蚁群最优化能耗调度算法

doi:10.3969/j.issn.1006-2475.2016.06.019

计算机与现代化

面向多核系统的蚁群最优化能耗调度算法

桂林理工大学信息科学与工程学院,广西桂林541006

收稿日期:2015-12-09 出版日期:2016-06-16 发布日期:2016-06-17
作者简介:宋琪(1993-),女,云南玉溪人,桂林理工大学信息科学与工程学院本科生，研究方向:云计算资源管理及调度；通信作者:敬超(1983-),男,河南长葛人,讲师,博士,研究方向:云计算与大数据处理。
基金资助:
桂林理工大学博士启动基金资助项目(002401003456); 广西自然科学基金资助项目(2015GXNSFBA139260)

Ant-colony Optimization Energy-saving Scheduling Algorithm for Multi-core Systems

School of Information Science and Engineering, Guilin University of Technology, Guilin 541006, China

Received:2015-12-09 Online:2016-06-16 Published:2016-06-17

摘要/Abstract

摘要： 主要研究多核系统的能耗最优化问题。首先，根据多核系统的特点，建立关于多核系统的任务、能耗模型；接着，设计和实现一种基于蚁群最优化能耗调度算法。本文算法以蚁群算法的概率状态转移规则为核心，通过全局信息激素更新的策略，避免了陷入局部最优的情况，从而获得全局最优解。通过实验比对，分别与贪心算法、穷举算法比较后发现：本校提出的调度算法，在最佳情况下，仅比最优能耗高0.7%，而该算法复杂度低，可以应用于任务输入集较大的场景。


关键词: 多核系统, 蚁群算法, 能耗最优化算法

Abstract: This paper mainly studies the energy consumption optimization on the multi-core systems. Firstly, according to the characteristics of the multi-core systems, we formulated the task model and energy consumption model on the multi-core systems. Then, based on ant-colony optimization, we designed and implemented an energy saving algorithm on multi-core systems. The core idea of the proposed algorithm is to use the transition rules of probabilistic state to obtain the proper solution. Furthermore, the global pheromones update strategy is used to avoid falling into local optimum. The experimental results show that the proposed algorithm outperforms better than that of greedy algorithm, etc. And it has only 0.7% higher energy consumption than that of the exhaustive algorithm. Moreover, it has a low-complexity in the large-scale data set.


Key words: multi-core systems, ant-colony optimization algorithm, energy-saving algorithm

中图分类号:

TP391

宋琪，敬超. 面向多核系统的蚁群最优化能耗调度算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.06.019.

SONG Qi, JING Chao. Ant-colony Optimization Energy-saving Scheduling Algorithm for Multi-core Systems[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.06.019.

参考文献

［1］ Li Min, Wu Xiaobo, Yan Xiaolang, et al. Q-DPM: An efficient model-free dynamic power management technique［C］// Proceedings of Design, Automation and Test in Europe. 2005,1:526-527.
［2］ Suleiman D R, Ibrahim M A, Hamarash I I. Dynamic voltage frequency scaling (DVFS) for microprocessors power and energy reduction［DB/OL］. http://www.emo.org.tr/ekler/035226640b6b89f_ek.pdf, 2013-12-24.
［3］彭蔓蔓,徐立超,王颖. 异构多核处理器的任务分配及能耗的研究［J］. 计算机应用研究, 2010,27(5):1729-1731.
［4］姚丽莎,王占凤,程家兴. 基于人工鱼群遗传算法的异构多核系统任务调度研究［J］. 计算机工程与科学, 2014,36(10):1866-1871.
［5］闫乔,覃志东,王绍宇,等. 同构多核/众核处理器任务分配自适应模拟退火算法［J］. 计算机科学, 2014,41(6):18-21.
［6］姚英彪,王璇. 面向多核任务调度的混合遗传算法［J］. 系统工程与电子技术, 2015(8):1928-1935.
［7］黄阳阳. 多核平台下考虑能耗的实时任务分派与调度研究［J］. 智能计算机与应用, 2015,5(4):78-81.
［8］ LEE W. Energy-efficient scheduling of periodic real-time tasks on lightly loaded multicore processors［J］. IEEE Transactions on Parallel and Distributed Systems, 2012,23(3):530-537.
［9］ Hou E S H, Ansari N, Hong Ren. A genetic algorithm for multiprocessor scheduling［J］. IEEE Transactions on Parallel and Distributed Systems, 1994,5(2):113-120.
［10］Huang Taiyi, Tsai Y C, Chu E T H. A near-optimal solution for the heterogeneous multi-processor single-level voltage setup problem［C］// Proceedings of IEEE International Parallel and Distributed Processing Symposium, 2007. 2007:1-10.
［11］Goh L K, Veeravalli B, Viswanathan S. Design of fast and efficient energy aware gradient-based scheduling algorithms for heterogeneous embedded multiprocessor systems［J］. IEEE Transactions on Parallel and Distributed Systems, 2009,20(1):1-12.
［12］Zhang Yumin, Hu Xiaobo, Chen D Z. Task scheduling and voltage selection for energy minimization［C］// Proceedings of the 39th Annual Design Automation Conference. 2002:183-188.
［13］Grant R E, Afsahi A. Power-performance efficiency of asymmetric multiprocessors for multi-threaded scientific applications［C］// Proceedings of the 20th International Conference on Parallel and Distributed Processing. 2006:344-351.
［14］Aydin H, Yang Qi. Energy-aware partitioning for multiprocessor real-time systems［C］// Proceedings of the 17th International Symposium on Parallel and Distributed Processing. 2003:113b.
［15］Topcuouglu H, Hariri S, Wu Min-you. Performance-effective and low-complexity task scheduling for heterogeneous computing［J］. IEEE Transaction Parallel & Distributed Systems, 2002,13(3):260-274.
［16］Rius J, Peidro A, Manich S, et al. Power and energy consumption of CMOS cCircuits: Measurement methods and experimental results［C］// Lecture Notes in Computer Science. 2003,2799:80-89.
［17］Quan Gang, Niu Linwei, Hu X S, et al. Fixed priority scheduling for reducing overall energy on variable voltage processors［C］// Proceedings of the 25th IEEE International Real-time Systems Symposium. 2004:309-318.
［18］李士勇. 蚁群算法及其应用［M］. 哈尔滨:哈尔滨工业大学出版社, 2004.
［19］李勇,段正澄. 动态蚁群算法求解TSP问题［J］. 计算机工程与应用， 2003,39(17):103-106.
［20］吴斌,史忠植. 一种基于蚁群算法的TSP问题分段求解算法［J］. 计算机学报, 2001,24(12):1328-1333.
［21］金彦亮,张勇,薛用,等. 基于拥塞控制的无线传感网蚁群最优化路由协议［J］. 上海大学学报(自然科学版), 2012,18(6):551-554.
［22］Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling［J］. IEEE Transactions on Evolutionary Computation, 2000,6(4):333-346.

[1]	张雄, 潘大志, . 融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题[J]. 计算机与现代化, 2022, 0(03): 98-102.
[2]	曲建波, 孙剑伟. 基于蚁群算法的导航卫星功率增强任务规划[J]. 计算机与现代化, 2021, 0(02): 104-108.
[3]	高月仁, 吴涛, 高峡. 基于蚁群算法优化的路由频率动态择径的研究[J]. 计算机与现代化, 2020, 0(12): 32-37.
[4]	李显良1,2，周庆平2，谭长庚3，谭焱良2，徐则阳2. 基于蚁群算法的城市体育设施优化选址[J]. 计算机与现代化, 2020, 0(03): 33-.
[5]	叶家琪1，符强1，2，贺亦甲1，叶浩1 . 基于聚类集成的蚁群算法求解大规模TSP问题[J]. 计算机与现代化, 2020, 0(02): 31-.
[6]	梁晶亮,黄军胜,白树军,王鹏,李睿. 基于蚁群算法的电力数据网络APT攻击预警模型[J]. 计算机与现代化, 2019, 0(01): 95-.
[7]	付永忠，潘云峰. 基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化[J]. 计算机与现代化, 2017, 0(8): 17-.
[8]	凌云翔1,2,宋志远1,张世海1,马力2. 基于蚁群算法的高原地区车辆运输路径优化问题[J]. 计算机与现代化, 2016, 0(9): 77-82.
[9]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[10]	李媛祯，杨群，段汐. 基于均衡更新蚁群算法的飞机排序调度[J]. 计算机与现代化, 2015, 0(2): 57-.
[11]	蔡文哲，王斌君. 一种QoS平面蚁群路由算法的设计与实现[J]. 计算机与现代化, 2015, 0(12): 15-.
[12]	陈曼青1，武子荣1，崔伟宁1，常婷婷2. 改进蚁群算法在装备保障路径选择中的应用[J]. 计算机与现代化, 2015, 0(11): 113-117.
[13]	朱卫宵，祝前旺，陈康. 基于改进蚁群算法的海上编队传感器资源分配模型[J]. 计算机与现代化, 2014, 0(12): 15-18+22.
[14]	刘晓曦;李卓越. 优化蚁群算法的云环境负载均衡[J]. 计算机与现代化, 2013, 1(9): 42-45.
[15]	袁东锋;吕聪颖. 改进蚁群算法在二次分配问题中的应用[J]. 计算机与现代化, 2013, 1(3): 9-11,1.

面向多核系统的蚁群最优化能耗调度算法

Ant-colony Optimization Energy-saving Scheduling Algorithm for Multi-core Systems

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价