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

doi:10.3969/j.issn.1006-2475.2016.06.019

Abstract

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

CLC Number:

TP391

SONG Qi, JING Chao. Ant-colony Optimization Energy-saving Scheduling Algorithm for Multi-core Systems[J]. Computer and Modernization, 2016, 0(6): 91-96.

References

［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]	HE Sida, CHEN Pinghua. Intent-based Lightweight Self-Attention Network for Sequential Recommendation [J]. Computer and Modernization, 2024, 0(12): 1-9.
[2]	ZHENG Jiuchao, ZHAO Xinyuan. Entity Linking Method Based on Topics and Description Information [J]. Computer and Modernization, 2024, 0(12): 10-14.
[3]	ZHAO Chenyang, XUE Tao, LIU Junhua. Fashion Clothing Pattern Generation Based on Improved Stable Diffusion [J]. Computer and Modernization, 2024, 0(12): 15-23.
[4]	HUANG Tingpei1, MA Lubiao1, LI Shibao2, LIU Jianhang1. Gesture Recognition Method Based on WiFi and Prototypical Network [J]. Computer and Modernization, 2024, 0(12): 34-39.
[5]	LIU Yunhai1, Feng Guang1, WU Xiaoting2, YANG Qun2 . Safety Helmet Wearing Detection Algorithm for Complex Construction Scenes [J]. Computer and Modernization, 2024, 0(12): 66-71.
[6]	WANG Yanyuan, MAO Zhengchong. Detection and Recognition Algorithms for Chinese and English Scene Text Images [J]. Computer and Modernization, 2024, 0(12): 84-90.
[7]	ZHANG Kun1, ZHANG Yongwei1, WU Yongcheng1, ZHANG Xiaowen2, ZHAI Shichen2. An LLM-based Method for Automatic Construction of Equipment Failure Knowledge Graphs [J]. Computer and Modernization, 2024, 0(11): 46-53.
[8]	ZHANG Zhixia, QIN Zhiyi. Network Public Opinion Prediction Based on Variational Mode Decomposition and IGJO-SVR [J]. Computer and Modernization, 2024, 0(11): 77-83.
[9]	WAN Hongwei, CHEN Pinghua. Polyp Segmentation Based on Involution and Coordinate Reverse Attention [J]. Computer and Modernization, 2024, 0(11): 84-90.
[10]	ZHANG Yu1, 2, LI Jing1, 2, MA Ming1, 2, WANG Zhongxiang1, 2, SUN Yan1, 2. YOLOLW: A Novel Lightweight Object Detection Model [J]. Computer and Modernization, 2024, 0(11): 91-98.
[11]	DONG Yuwen. Multi-scale Moving Object Detection Algorithm Based on Improved YOLOv7-tiny [J]. Computer and Modernization, 2024, 0(11): 99-105.
[12]	QI Xian, LIU Daming, CHANG Jiaxin. Multi-view 3D Reconstruction Based on Improved Self-attention Mechanism [J]. Computer and Modernization, 2024, 0(11): 106-112.
[13]	CHEN Kai1, LI Yiting1, 2, QUAN Huafeng1. A River Discarded Bottles Detection Method Based on Improved YOLOv8 [J]. Computer and Modernization, 2024, 0(11): 113-120.
[14]	YANG Qingwu, LUO Xiaohui, LIU Xin. Industrial Image Circle Detection Algorithm Based on Edge Drawing [J]. Computer and Modernization, 2024, 0(11): 121-126.
[15]	ZHOU Anda, TANG Chaoying. Semantic Segmentation Algorithm for Rainy Road Scene and Its Mobile Deployment [J]. Computer and Modernization, 2024, 0(10): 7-13.