World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Genetic Algorithm for Energy Aware Task Scheduling in Heterogeneous Systems

    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 ) . CrossrefGoogle 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 Scholar
    • T. 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 Scholar
    • M. 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 Scholar
    • J. 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 ) . CrossrefGoogle 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
    • T. D. Burdet al., IEEE Journal of Solid-State Circuits 35(11), 1571 (2000). Crossref, ISIGoogle 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 Scholar
    • D. 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