A Genetic Algorithm for Energy Aware Task Scheduling in Heterogeneous Systems
Abstract
In distributed systems, an application can be decomposed to tasks which can be executed on different processors in parallel. Modern processors allow variable supply voltages and dynamic voltage scaling (DVS) provides the possibility to reduce the power consumption. In this paper, we present a static scheduling approach to integrate task mapping, scheduling and voltage selection to minimize energy consumption of real-time dependent tasks executing on a number of heterogeneous processors. The approach is based on Genetic Algorithms. The simulation results show that the proposed algorithm is very effective and reduces the energy consumption ranging from 20% to 90% under different system configurations. We also compare the proposed genetic-algorithm-based energy aware algorithm with other three algorithms, namely earliest-deadline-first-based, longest-time-first-based and simulated-annealing-based energy aware algorithms. The comparison results demonstrate that the genetic-algorithm-based energy aware algorithm outperforms other three algorithms.
References
T. D. Burd and R. W. Brodersen , Energy CMOS microprocessor design, Proceedings of HICSS Conference (Maui, Hawaii, 1995) pp. 288–297. Google Scholar-
A. Chandrakasan and R. Brodersen , Low Power Digital CMOS Design ( Kluwer Academic Publishers , 1995 ) . Crossref, Google Scholar A. Demers , F. Yao and S. Shenker , A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (1995) pp. 374–382. Google Scholar-
F. Glover and M. Laguna , Modern Heuristic Techniques for Combinatorial Problems ( Blackwell Scientific Publications , 1993 ) . Google Scholar F. Gruian and K. Kuchcinski , LEneS: Task-scheduling for low-energy systems using variable voltage processors, Proceedings of Asia South Pacific-Design Automation Conference (ASPDAC-01) (2001) pp. 449–455. Google ScholarT. Ishihara and H. Yasuura , Voltage scheduling problem for dynamically variable voltage processors, Proceedings of International Symposium on Low Power Electronics and Design (ISLPED-98) (1998) pp. 197–202. Google ScholarM. Lin and L. T. Yang , Hybrid genetic algorithms for partially ordered tasks in a multi-processor environment, Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA-99) (1999) pp. 382–387. Google ScholarJ. Luo and N. K. Jha , Static and dynamic variable voltage scheduling algorithms for real-time heterogeneous distributed embedded systems,ASP-DAC/VLSI Design 2002 () (Bangalore, India, 2002) pp. 719–726. Google Scholar-
Z. Michalewicz , Genetic Algorithms + Data Structures = Evolution Programs , 2nd edn. ( Springer-Verlag , 1994 ) . Crossref, Google Scholar - J. Oh and C. Wu. Genetic-algorithm-based real-time task scheduling with multiple goals. To appear on Journal of Systems and Software, 2002 . Google Scholar
- IEEE Journal of Solid-State Circuits 35(11), 1571 (2000). Crossref, ISI, Google Scholar
Y. Zhang , X. Hu and D. Chen , Task scheduling and voltage selection for energy minimization, Proceedings of Design Automation Conference (DAC-02) (New Orleans, Louisiana, USA, 2002) pp. 183–188. Google ScholarD. Zhu , R. Melhem and B. Childers , Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems, Proceedings of the 22th IEEE Real-Time Systems Sumposium (RTSS-01) (UK, 2001) pp. 84–94. Google Scholar


