面向异构系统的节能调度算法

Liu Yong-xing; Li Ken-li; Tang Zhuo; Li Ke-qin

doi:10.1631/FITEE.1400399

Your Location：

Home >

Browse articles >

面向异构系统的节能调度算法

服务可用性专题 | Updated：2022-06-06

- 面向异构系统的节能调度算法
- Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems*
- 信息与电子工程前沿（英文） 2015年16卷第7期页码：519-531
- Affiliations：
  
  1.College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
  2.Department of Computer Science, State University of New York, New Paltz, New York 12561, USA
- Author bio：
  
  †E-mail:yongxing510@126.comlkl@hnu.edu.cn
  ‡Corresponding Author
- Funds：
  
  *Project supported by the National Natural Science Foundation of China (Nos. 61133005, 61432005, 61370095, 61472124, and 61402400)
- DOI：10.1631/FITEE.1400399
  中图分类号：
- 收稿：2014-11-24，
  
  修回：2015-06-05，
  
  录用：2015-04-30，
  
  纸质出版：2015-07
- Accepted：
Scan QR Code
面向异构系统的节能调度算法[J]. 信息与电子工程前沿（英文）, 2015,16(7):519-531.

Liu Yong-xing, Li Ken-li, Tang Zhuo, et al. Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(7): 519-531.
面向异构系统的节能调度算法[J]. 信息与电子工程前沿（英文）, 2015,16(7):519-531. DOI： 10.1631/FITEE.1400399.

Liu Yong-xing, Li Ken-li, Tang Zhuo, et al. Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(7): 519-531. DOI： 10.1631/FITEE.1400399.

摘要

目的

当前，异构计算系统面临能量消耗巨大的严峻问题，降低系统运行过程中能量消耗成为一个亟待解决的问题。任务调度作为计算系统中的核心部分，起着对计算资源进行全局管理和分配的关键作用。本文结合调度算法与动态电压调节技术来优化系统的总能量消耗。

创新点

本文用有向无环图来表示应用模型，并对其进行重构，使得应用能够被更加合理地调度和分配。在优化系统能量消耗的过程中，本文通过均衡两个任务间的处理器空闲时间来降低系统能量消耗，并以递进方式处理剩余任务。

方法

在建立计算系统模型和应用模型后，算法对应用中的路径集进行提取，并基于路径集对应用进行重构。为优化系统的总能量消耗，算法采取递进的方式来均衡任务的运行频率。最后用实验验证算法性能。

结论

针对异构系统环境，提出一个基于动态电压调节技术的节能调度算法。该算法通过优化任务分配来减少应用的完成时间，并通过均衡任务间的处理器空闲时间来降低系统的总能量消耗。文中通过大量的实验对算法的性能进行了评估，并分析了实验结果，实验结果证明了算法的有效性（图6-10）。

Abstract

With the increasing energy consumption of computing systems and the growing advocacy for green computing

energy efficiency has become one of the critical challenges in high-performance heterogeneous computing systems. Energy consumption can be reduced by not only hardware design but also software design. In this paper

we propose an energy-aware scheduling algorithm with equalized frequency

called EASEF

for parallel applications on heterogeneous computing systems. The EASEF approach aims to minimize the finish time and overall energy consumption. First

EASEF extracts the set of paths from an application. Then

it reconstructs the application based on the extracted set of paths to achieve a reasonable schedule. Finally

it adopts a progressive way to equalize the frequency of tasks to reduce the total energy consumption of systems. Randomly generated applications and two real-world applications are examined in our experiments. Experimental results show that the EASEF algorithm outperforms two existing algorithms in terms of makespan and energy consumption.

关键词

Keywords

references

E Amador , R Knopp , R Pacalet , 等 . Dynamic power management for the iterative decoding of turbo codes . IEEE Trans VLSI Syst , 2012 . 20 ( 11 ): 2133 - 2137 . DOI: 10.1109/TVLSI.2011.2167765 http://doi.org/10.1109/TVLSI.2011.2167765 .

R Bajaj , DP Agrawal . Improving scheduling of tasks in a heterogeneous environment . IEEE Trans Parall Distr Syst , 2004 . 15 ( 2 ): 107 - 118 . DOI: 10.1109/TPDS.2004.1264795 http://doi.org/10.1109/TPDS.2004.1264795 .

S Bansal , P Kumar , K Singh . An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems . IEEE Trans Parall Distr Syst , 2003 . 14 ( 6 ): 533 - 544 . DOI: 10.1109/TPDS.2003.1206502 http://doi.org/10.1109/TPDS.2003.1206502 .

S Bansal , P Kumar , K Singh . Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs . J Parall Distr Comput , 2005 . 65 ( 4 ): 479 - 491 . DOI: 10.1016/j.jpdc.2004.11.006 http://doi.org/10.1016/j.jpdc.2004.11.006 .

L Benini , A Bogliolo , G de Micheli . A survey of design techniques for system-level dynamic power management . IEEE Trans VLSI Syst , 2000 . 8 ( 3 ): 299 - 316 . DOI: 10.1109/92.845896 http://doi.org/10.1109/92.845896 .

C Boeres , VEF Rebello . A cluster-based strategy for scheduling task on heterogeneous processorss . 2004 . 16th Symp. on Computer Architecture and High Performance Computing . 214 - 221 . DOI: 10.1109/SBAC-PAD.2004.1 http://doi.org/10.1109/SBAC-PAD.2004.1 .

D Bozdag , F Ozguner , UV Catalyurek . Compaction of schedules and a two-stage approach for duplication-based DAG scheduling . IEEE Trans Parall Distr Syst , 2009 . 20 ( 6 ): 857 - 871 . DOI: 10.1109/TPDS.2008.260 http://doi.org/10.1109/TPDS.2008.260 .

R Brown . Report to Congress on Server and Data Center Energy Efficiency: Public Law 109-431 , 2008 . Lawrence Berkeley National Laboratory , DOI: 10.2172/929723 http://doi.org/10.2172/929723 .

TH Cormen , CE Leiserson , RL Rivest , 等 . Introduction to Algorithms , 2009 . : Cambridge MIT Press , .

RF Freund , HJ Siegel . Guest editor’s introduction: heterogeneous processing . Computer , 1993 . 26 ( 6 ): 13 - 17 . .

FF Fu , YX Bai , XA Hu , 等 . An objective flexible clustering algorithm for task mapping and scheduling on cluster-based NoC . 2010 . Academic Symposium on Optoelectronics and Microelectronics Technology and 10th Chinese-Russian Symp. on Laser Physics and Laser Technology Optoelectronics Technology . 369 - 373 . DOI: 10.1109/RCSLPLT.2010.5615317 http://doi.org/10.1109/RCSLPLT.2010.5615317 .

T Hagras , J Janeček . A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems . Parall Comput , 2005 . 31 ( 7 ): 653 - 670 . DOI: 10.1016/j.parco.2005.04.002 http://doi.org/10.1016/j.parco.2005.04.002 .

QJ Huang , S Su , J Li , 等 . Enhanced energy-efficient scheduling for parallel applications in cloud . 2012 . 12th IEEE/ACM Int. Symp. on Cluster, Cloud and Grid Computing . 781 - 786 . DOI: 10.1109/CCGrid.2012.49 http://doi.org/10.1109/CCGrid.2012.49 .

MU Ilyas , SA Khan . A clustering heuristic algorithm for scheduling periodic and deterministic tasks on a multiprocessor system . 2001 . Proc. IEEE Int. Multi Topic Conf., Technology for the 21st Century . 1 - 5 . DOI: 10.1109/INMIC.2001.995305 http://doi.org/10.1109/INMIC.2001.995305 .

MA Iverson , F Özgüner , GJ Follen . Parallelizing existing applications in a distributed heterogeneous environment . 1995 . 4th Heterogeneous Computing Workshop . 93 - 100 . .

MA Khan . Scheduling for heterogeneous systems using constrained critical paths . Parall Comput , 2012 . 38 ( 4-5 ): 175 - 193 . DOI: 10.1016/j.parco.2012.01.001 http://doi.org/10.1016/j.parco.2012.01.001 .

SJ Kim , JC Browne . A general approach to mapping of parallel computation upon multiprocessor architectures . Int. Conf. on Parallel Processing , 1988 . 3 1 - 8 . .

YK Kwok , I Ahmad . Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors . IEEE Trans Parall Distr Syst , 1996 . 7 ( 5 ): 506 - 521 . DOI: 10.1109/71.503776 http://doi.org/10.1109/71.503776 .

YK Kwok , I Ahmad . Static scheduling algorithms for allocating directed task graphs to multiprocessors . ACM Comput Surv , 1999 . 31 ( 4 ): 406 - 471 . DOI: 10.1145/344588.344618 http://doi.org/10.1145/344588.344618 .

CH Lee , KG Shin . On-line dynamic voltage scaling for hard real-time systems using the EDF algorithm . 2004 . 25th IEEE Int. Real-Time Systems Symp. . 319 - 335 . DOI: 10.1109/REAL.2004.38 http://doi.org/10.1109/REAL.2004.38 .

YC Lee , AY Zomaya . Energy conscious scheduling for distributed computing systems under different operating conditions . IEEE Trans Parall Distr Syst , 2011 . 22 ( 8 ): 1374 - 1381 . DOI: 10.1109/TPDS.2010.208 http://doi.org/10.1109/TPDS.2010.208 .

KQ Li . Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers . IEEE Trans Comput , 2012 . 61 ( 12 ): 1668 - 1681 . DOI: 10.1109/TC.2012.120 http://doi.org/10.1109/TC.2012.120 .

N Mehta , B Amrutur . Dynamic supply and threshold voltage scaling for CMOS digital circuits using insitu power monitor . IEEE Trans VLSI Syst , 2012 . 20 ( 5 ): 892 - 901 . DOI: 10.1109/TVLSI.2011.2132765 http://doi.org/10.1109/TVLSI.2011.2132765 .

J Mei , KL Li . Energy-aware scheduling algorithm with duplication on heterogeneous computing systems . 2012 . ACM/IEEE 13th Int. Conf. on Grid Computing . 122 - 129 . DOI: 10.1109/Grid.2012.32 http://doi.org/10.1109/Grid.2012.32 .

R Mishra , N Rastogi , DK Zhu , 等 . Energy aware scheduling for distributed real-time systems . 2003 . Proc. Int. Parallel and Distributed Processing Symp. . 1 - 9 . DOI: 10.1109/IPDPS.2003.1213099 http://doi.org/10.1109/IPDPS.2003.1213099 .

S Mittal . A survey of techniques for improving energy efficiency in embedded computing systems . Int J Comput Aided Eng Technol , 2014 . 6 ( 4 ): 440 - 459 . DOI: 10.1504/IJCAET.2014.065419 http://doi.org/10.1504/IJCAET.2014.065419 .

B Piyatamrong , S Ohara , S Kantakajorn . GTCS: a greedy task clustering and scheduling algorithm for distributed memory processor architecture . 2000 . Proc. 4th Int. Conf./Exhibition on High Performance Computing in the Asia-Pacific Region . 310 - 314 . DOI: 10.1109/HPC.2000.846567 http://doi.org/10.1109/HPC.2000.846567 .

GC Sih , EA Lee . A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures . IEEE Trans Parall Distr Syst , 1993 . 4 ( 2 ): 175 - 187 . DOI: 10.1109/71.207593 http://doi.org/10.1109/71.207593 .

XY Tang , KL Li , GP Liao , 等 . List scheduling with duplication for heterogeneous computing systems . J Parall Distr Comput , 2010 . 70 ( 2 ): 323 - 329 . DOI: 10.1016/j.jpdc.2010.01.003 http://doi.org/10.1016/j.jpdc.2010.01.003 .

G Terzopoulos , HD Karatza . Dynamic voltage scaling scheduling on power-aware clusters under power constraints . 2013 . IEEE/ACM 17th Int. Symp. on Distributed Simulation and Real Time Applications . 72 - 78 . DOI: 10.1109/DS-RT.2013.16 http://doi.org/10.1109/DS-RT.2013.16 .

H Topcuoglu , S Hariri , MY Wu . Performance effective and low-complexity task scheduling for heterogeneous computing . IEEE Trans Parall Distr Syst , 2002 . 13 ( 3 ): 260 - 274 . DOI: 10.1109/71.993206 http://doi.org/10.1109/71.993206 .

JD Ullman . NP-complete scheduling problems . J Comput Syst Sci , 1975 . 10 ( 3 ): 384 - 393 . DOI: 10.1016/S0022-0000(75)80008-0 http://doi.org/10.1016/S0022-0000(75)80008-0 .

LZ Wang , SU Khan , D Chen , 等 . Energyaware parallel task scheduling in a cluster . Fut Gener Comput Syst , 2013 . 29 ( 7 ): 1661 - 1670 . DOI: 10.1016/j.future.2013.02.010 http://doi.org/10.1016/j.future.2013.02.010 .

T Yang , A Gerasoulis . DSC: scheduling parallel tasks on an unbounded number of processors . IEEE Trans Parall Distr Syst , 1994 . 5 ( 9 ): 951 - 967 . DOI: 10.1109/71.308533 http://doi.org/10.1109/71.308533 .

XM Zhu , C He , KL Li , 等 . Adaptive energy efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters . J Parall Distr Comput , 2012 . 72 ( 6 ): 751 - 763 . DOI: 10.1016/j.jpdc.2012.03.005 http://doi.org/10.1016/j.jpdc.2012.03.005 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

XIRAC: an optimized product-oriented near-real-time operating system with unlimited tasks and an innovative programming paradigm based on the maximum entropy method

A multi-agent collaboration scheme for energy-efficient task scheduling in a 3D UAV-MEC space

Meeting deadlines for approximation processing in MapReduce environments