Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems

doi:10.1631/FITEE.1400399

Frontiers of Information Technology & Electronic Engineering

2015, Vol. 16

Issue (7): 519-531 https://doi.org/10.1631/FITEE.1400399

本期目录

Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems

Yong-xing LIU¹(

),Ken-li LI^1,^*(

),Zhuo TANG¹,Ke-qin LI^1,²

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

全文: PDF(862 KB)

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.

Key words： Dynamic voltage scaling Energy aware Heterogeneous systems Task scheduling Directed acyclic graph

收稿日期: 2014-11-24 出版日期: 2015-07-20

Corresponding Author(s): Ken-li LI

引用本文:

. [J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(7): 519-531.
Yong-xing LIU,Ken-li LI,Zhuo TANG,Ke-qin LI. Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems. Front. Inform. Technol. Electron. Eng, 2015, 16(7): 519-531.

链接本文:

https://academic.hep.com.cn/fitee/CN/10.1631/FITEE.1400399
https://academic.hep.com.cn/fitee/CN/Y2015/V16/I7/519

1	Amador, E., Knopp, R., Pacalet, R., , 2012. Dynamic power management for the iterative decoding of turbo codes. IEEE Trans. VLSI Syst., 20(11): 2133-2137. [] https://doi.org/10.1109/TVLSI.2011.2167765
2	Bajaj, R., Agrawal, D.P., 2004. Improving scheduling of tasks in a heterogeneous environment. IEEE Trans. Parall. Distr. Syst., 15(2): 107-118. [] https://doi.org/10.1109/TPDS.2004.1264795
3	Bansal, S., Kumar, P., Singh, K., 2003. An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. IEEE Trans. Parall. Distr. Syst., 14(6): 533-544. [] https://doi.org/10.1109/TPDS.2003.1206502
4	Bansal, S., Kumar, P., Singh, K., 2005. Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs. J. Parall. Distr. Comput., 65(4): 479-491. [] https://doi.org/10.1016/j.jpdc.2004.11.006
5	Benini, L., Bogliolo, A., de Micheli, G., 2000. A survey of design techniques for system-level dynamic power management. IEEE Trans. VLSI Syst., 8(3): 299-316. [] https://doi.org/10.1109/92.845896
6	Boeres, C., Rebello, V.E.F., 2004. A cluster-based strategy for scheduling task on heterogeneous processors. 16th Symp. on Computer Architecture and High Performance Computing, p.214-221. [] https://doi.org/10.1109/SBAC-PAD.2004.1
7	Bozdag, D., Ozguner, F., Catalyurek, U.V., 2009. Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans. Parall. Distr. Syst., 20(6): 857-871. [] https://doi.org/10.1109/TPDS.2008.260
8	Brown, R., 2008. Report to Congress on Server and Data Center Energy Efficiency: Public Law 109-431. Lawrence Berkeley National Laboratory. [] https://doi.org/10.2172/929723
9	Cormen, T.H., Leiserson, C.E., Rivest, R.L., , 2009. Introduction to Algorithms. MIT Press, Cambridge.
10	Freund, R.F., Siegel, H.J., 1993. Guest editor’s introduction: heterogeneous processing. Computer, 26(6): 13-17.
11	Fu, F.F., Bai, Y.X., Hu, X.A., , 2010. An objectiveflexible clustering algorithm for task mapping and scheduling on cluster-based NoC. Academic Symposium on Optoelectronics and Microelectronics Technology and 10th Chinese-Russian Symp. on Laser Physics and Laser Technology Optoelectronics Technology, p.369-373. [] https://doi.org/10.1109/RCSLPLT.2010.5615317
12	Hagras, T., Jane?ek, J., 2005. A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems. Parall. Comput., 31(7): 653-670. [] https://doi.org/10.1016/j.parco.2005.04.002
13	Huang, Q.J., Su, S., Li, J., , 2012. Enhanced energy-efficient scheduling for parallel applications in cloud. 12th IEEE/ACM Int. Symp. on Cluster, Cloud and Grid Computing, p.781-786. [] https://doi.org/10.1109/CCGrid.2012.49
14	Ilyas, M.U., Khan, S.A., 2001. A clustering heuristic algorithm for scheduling periodic and deterministic tasks on a multiprocessor system. Proc. IEEE Int. Multi Topic Conf., Technology for the 21st Century, p.1-5. [] https://doi.org/10.1109/INMIC.2001.995305
15	Iverson, M.A., Ozguner, F., Follen, G.J., 1995. Parallelizing existing applications in a distributed heterogeneous environment. 4th Heterogeneous Computing Workshop, p.93-100.
16	Khan, M.A., 2012. Scheduling for heterogeneous systems using constrained critical paths. Parall. Comput., 38(4-5): 175-193. [] https://doi.org/10.1016/j.parco.2012.01.001
17	Kim, S.J., Browne, J.C., 1988. A general approach to mapping of parallel computation upon multiprocessor architectures. Int. Conf. on Parallel Processing, 3: 1-8.
18	Kwok, Y.K., Ahmad, I., 1996. Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parall. Distr. Syst., 7(5): 506-521. [] https://doi.org/10.1109/71.503776
19	Kwok, Y.K., Ahmad, I., 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 31(4): 406-471. [] https://doi.org/10.1145/344588.344618
20	Lee, C.H., Shin, K.G., 2004. On-line dynamic voltage scaling for hard real-time systems using the EDF algorithm. 25th IEEE Int. Real-Time Systems Symp., p.319-335. [] https://doi.org/10.1109/REAL.2004.38
21	Lee, Y.C., Zomaya, A.Y., 2011. Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE Trans. Parall. Distr. Syst., 22(8): 1374-1381. [] https://doi.org/10.1109/TPDS.2010.208
22	Li, K.Q., 2012. Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers. IEEE Trans. Comput., 61(12): 1668-1681. [] https://doi.org/10.1109/TC.2012.120
23	Mehta, N., Amrutur, B., 2012. Dynamic supply and threshold voltage scaling for CMOS digital circuits using insitu power monitor. IEEE Trans. VLSI Syst., 20(5): 892-901. [] https://doi.org/10.1109/TVLSI.2011.2132765
24	Mei, J., Li, K.L., 2012. Energy-aware scheduling algorithm with duplication on heterogeneous computing systems. ACM/IEEE 13th Int. Conf. on Grid Computing, p.122-129. [] https://doi.org/10.1109/Grid.2012.32
25	Mishra, R., Rastogi, N., Zhu, D.K., , 2003. Energy aware scheduling for distributed real-time systems. Proc. Int. Parallel and Distributed Processing Symp., p.1-9. [] https://doi.org/10.1109/IPDPS.2003.1213099
26	Mittal, S., 2014. A survey of techniques for improving energy efficiency in embedded computing systems. Int. J. Comput. Aided Eng. Technol., 6(4): 440-459. [] https://doi.org/10.1504/IJCAET.2014.065419
27	Piyatamrong, B., Ohara, S., Kantakajorn, S., 2000. GTCS: a greedy task clustering and scheduling algorithm for distributed memory processor architecture. Proc. 4th Int. Conf./Exhibition on High Performance Computing in the Asia-Pacific Region, p.310-314. [] https://doi.org/10.1109/HPC.2000.846567
28	Sih, G.C., Lee, E.A., 1993. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parall. Distr. Syst., 4(2): 175-187. [] https://doi.org/10.1109/71.207593
29	Tang, X.Y., Li, K.L., Liao, G.P., , 2010. List scheduling with duplication for heterogeneous computing systems. J. Parall. Distr. Comput., 70(4): 323-329. [] https://doi.org/10.1016/j.jpdc.2010.01.003
30	Terzopoulos, G., Karatza, H.D., 2013. Dynamic voltage scaling scheduling on power-aware clusters under power constraints. IEEE/ACM 17th Int. Symp. on Distributed Simulation and Real Time Applications, p.72-78. [] https://doi.org/10.1109/DS-RT.2013.16
31	Topcuoglu, H., Hariri, S., Wu, M.Y., 2002. Performanceeffective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parall. Distr. Syst., 13(3): 260-274. [] https://doi.org/10.1109/71.993206
32	Ullman, J.D., 1975. NP-complete scheduling problems. J. Comput. Syst. Sci., 10(3): 384-393. [] https://doi.org/10.1016/S0022-0000(75)80008-0
33	Wang, L.Z., Khan, S.U., Chen, D., , 2013. Energyaware parallel task scheduling in a cluster. Fut. Gener. Comput. Syst., 29(7): 1661-1670. [] https://doi.org/10.1016/j.future.2013.02.010
34	Yang, T., Gerasoulis, A., 1994. DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parall. Distr. Syst., 5(9): 951-967. [] https://doi.org/10.1109/71.308533
35	Zhu, X.M., He, C., Li, K.L., , 2012. Adaptive energyefficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters. J. Parall. Distr. Comput., 72(6): 751-763. [] https://doi.org/10.1016/j.jpdc.2012.03.005

[1]		Download
[2]		Download

Viewed

Full text

Abstract

Cited

Shared

Discussed