An Improved Estimation of Distribution Algorithm for Dynamic Voltage Scaling Problem in Heterogeneous System

Abstract:

Energy consumption can be optimized by utilizing dynamic voltage scaling that conjointly adjusts the supply voltage and the operational frequency during the execution of the tasks to effectively minimize the energy. An improved estimation of distribution algorithm is presented for energy saving of the distributed embedded systems that consists of dynamic voltage scalable processing elements. The algorithm evolves computation by using the univariate marginal distribution to search the solution in a discrete space and mapping the solutions into feasible ones stratified the precedence constraint. The algorithm hybridize the genetic algorithm with estimation of distribution algorithm by combines statistically learning and sampling the probability distribution of the population iteratively and the conventional evolutionary operators such as crossover and mutation together. Simulated annealing is utilized to accept some bad solution rather the elite solution to make fully use of the global and local information. Experiments are implemented to demonstrate the performance of the algorithm

• Periodical: Applied Mechanics and Materials (Volumes 631-632)
• Pages: 373-377
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.631-632.373
• Online since: September 2014
• Authors: Yan Kang*, Zhong Min Wang, Ying Lin, Yi Fan Zhang
• Keywords: Dynamic Voltage Scaling, Energy Saving, Estimation of Distribution, Heterogeneous Distributed System, Scheduling Algorithm

References

[1] M. T. Schmitz and B. M. Al-Hashimi. Considering Power Variations of DVS Processing Elements for Energy Minimisation in Distributed Systems., In Proc. ISSS, p.250–255, Oct (2001).

DOI: 10.1145/500001.500060

[2] T. D. Burd, T. A. Pering, A. J. Stratakos, and R. W. Brodersen. A Dynamic Voltage Scaled Microprocessor System., J. IEEE Solid-State Circuits. 35, 11, pp.1571-1580, (2000).

DOI: 10.1109/4.881202

[3] F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced CPU energy., Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, October 23-25; pp.374-382.

DOI: 10.1109/sfcs.1995.492493

[4] 5. C. Scordino, and G. Lipari. A resource reservation algorithm for power-aware scheduling of periodic and aperiodic real-time tasks., J. IEEE Transactions on Computers, 12, 55, pp.1509-1522, (2006).

DOI: 10.1109/tc.2006.190

[5] P. Pillai, and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems., Proceedings of the 18th ACM Symposium on Operating System Principles, October 21 – 24; Banff, Canada, (2001).

DOI: 10.1145/502034.502044

[6] S. Saewong, and R. Rajkumar. Practical voltage-scaling for fixed-priority RT-systems., Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium, May 27-30; Toronto, Canada. (2003).

DOI: 10.1109/rttas.2003.1203042

[7] H. Aydin, V. Devadas, and D. Zhu. System-level energy management for periodic realtime tasks., Proceedings of the 27th IEEE International Real-Time Systems Symposium, December 5-8; Rio de Janeiro, Brazil. (2006).

DOI: 10.1109/rtss.2006.48

[8] Y. Liu, and A. K. Mok, An integrated approach for applying dynamic voltage scaling to hard real-time systems., Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium, May 27-30; Toronto, Canada. (2003).

DOI: 10.1109/rttas.2003.1203043

[9] M. T. Schmitz, B. M. Al-Hashimi, and P. Eles. Iterative Schedule Optimization for Voltage Scalable Distributed Embedded System., ACM Transactions on Embedded Computing Systems, 3, 1, (2004).

DOI: 10.1145/972627.972636

[10] Wang, L., Wang S.Y., Xu Y., Zhou G. & Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62, 917–926.

DOI: 10.1016/j.cie.2011.12.014