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, doi: 10.3969/j.issn.1006-2475.2016.06.019.

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]	FU Hong-lin, ZHANG Tai-hong, YANG Ya-ting, Aizimaiti Aiwanier, MA Bo. Scenes Text Modification Network for Uyghur Based on Generative Adversarial Network [J]. Computer and Modernization, 2024, 0(01): 41-46.
[2]	WANG Qiu-yi, ZHOU Hao, ZHENG Ting-ting. Improved RetinaNet Target Detection Method for Power Equipment [J]. Computer and Modernization, 2024, 0(01): 47-52.
[3]	LIN Qi-zhao, PENG Zhi-ping, GUO Mian, CUI De-long. A Temperature Field Reconstruction Method of Furnace Tube Based on Bidirectional Multistep Prediction [J]. Computer and Modernization, 2024, 0(01): 53-58.
[4]	ZHENG Li-rui, XIAO Xiao-xia, ZOU Bei-ji, LIU Bin, ZHOU Zhan. Named Entity Recognition in Electronic Medical Record Based on BERT [J]. Computer and Modernization, 2024, 0(01): 87-91.
[5]	LI Ying-ying, HUANG Wen-pei. View Frustum Culling Algorithm for Scene Based on Optimized Octree [J]. Computer and Modernization, 2024, 0(01): 103-108.
[6]	XIA Qian-han, HE Sheng-huang, WU Yuan-qing, ZHAO Le-le. Few-shot Object Detection via Learnable Memory Feature Pyramid Network [J]. Computer and Modernization, 2023, 0(12): 7-13.
[7]	ZHOU Cheng-cheng, ZENG Qing-jun, YANG Kang, HU Jia-ming, HAN Chun-wei. EEG Recognition of Motor Imagination Based on Efficiency Channel Attention Module [J]. Computer and Modernization, 2023, 0(12): 19-23.
[8]	ZENG Wei-ping, CHEN Jun-hong, Muhammad ASIM, LIU Wen-yin, YANG Zhen-guo. Point Cloud Completion Algorithm Based on Multi-stage Fractal Combination [J]. Computer and Modernization, 2023, 0(12): 24-29.
[9]	BAI Xiao-bo, JIANG Meng-xi, WANG Tie-shan, SHAO Jing-feng, LI Bo, . Improved Harris Hawks Optimization Algorithm Based on Cluster Centroid and#br# Exponential Decline Method#br# [J]. Computer and Modernization, 2023, 0(12): 30-35.
[10]	QIU Kai-xing, FENG Guang. A Multi-label Image Classification Model Based on Dual Feature Attention [J]. Computer and Modernization, 2023, 0(12): 41-47.
[11]	DU Kang, GUO Lu-yu, XU Qi-lei, SHAN Bao-ming, ZHANG Fang-kun. Infrared Spectrum Modeling Method Based on Variable Selection of Model#br# Population Analysis#br# [J]. Computer and Modernization, 2023, 0(12): 48-52.
[12]	LIU Yu-cheng, HE Qi, DONG Yan-hua, WANG Xiao-yu. Course Recommendation Method Combining Time Correlation Degree and Course#br# Collocation Degree [J]. Computer and Modernization, 2023, 0(12): 53-58.
[13]	ZHANG Hao-yang, YIN Zi-ming, LE Jun-yi, SHEN Da-cong, SHU Yi-jun, YANG Zi-yi, . 3D-SPRNet: Segmentation Model of Gallbladder Cancer Based on Parallel Decoder and Double Attention Mechanism [J]. Computer and Modernization, 2023, 0(12): 59-66.
[14]	ZHANG Bo-quan, MAI Hai-peng, CHEN Jia-min, Pang Jin-ju. White Matter Hyperintensities Segmentation Based on High Gray Value#br# Attention Mechanism [J]. Computer and Modernization, 2023, 0(12): 67-75.
[15]	ZHANG Zai-cheng, LI Jian. Application of Neural Rendering Based Visual Synthesis in Construction Scene [J]. Computer and Modernization, 2023, 0(12): 76-81.