Journal of Computing Science and Engineering

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지
DOI QR코드

DOI QR Code

Energy Aware Scheduling of Aperiodic Real-Time Tasks on Multiprocessor Systems

  • Anne, Naveen (Department of Electrical and Computer Engineering, University of Nevada) ;
  • Muthukumar, Venkatesan (Department of Electrical and Computer Engineering, University of Nevada)
  • Received : 2012.10.09
  • Accepted : 2013.02.28
  • Published : 2013.03.30
Download PDF
⟨ Previous Next ⟩

Abstract

Multicore and multiprocessor systems with dynamic voltage scaling architectures are being used as one of the solutions to satisfy the growing needs of high performance applications with low power constraints. An important aspect that has propelled this solution is effective task/application scheduling and mapping algorithms for multiprocessor systems. This work proposes an energy aware, offline, probability-based unified scheduling and mapping algorithm for multiprocessor systems, to minimize the number of processors used, maximize the utilization of the processors, and optimize the energy consumption of the multiprocessor system. The proposed algorithm is implemented, simulated and evaluated with synthetic task graphs, and compared with classical scheduling algorithms for the number of processors required, utilization of processors, and energy consumed by the processors for execution of the application task graphs.

Keywords

References

  1. S. Zhuravlev, J. C. Saez, S. Blagodurov, A. Fedorova, and M. Prieto, "Survey of energy-cognizant scheduling techniques," IEEE Transactions on Parallel and Distributed Systems, 2012. http://doi.ieeecomputersociety.org/10.1109/TPDS.2012.20.
  2. P. G. Paulin and J. P. Knight, "Force-directed scheduling in automatic data path synthesis," in Proceedings of the 24th ACM/IEEE Design Automation Conference, Miami Beach, FL, 1987, pp. 195-202.
  3. J. W. S. Liu, Real-Time Systems, Upper Saddle River, NJ: Prentice Hall, 2000.
  4. A. Manzak and C. Chakrabarti, "Variable voltage task scheduling algorithms for minimizing energy/power," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 2, pp.270-276, 2003. https://doi.org/10.1109/TVLSI.2003.810801
  5. M. Weiser, B. Welch, A. Demers, and S. Shenker, "Scheduling for reduced CPU energy," in Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, Monterey, CA, 1994, pp. 13-23.
  6. F. Yao, A. Demers, and S. Shenker, "A scheduling model for reduced CPU energy," in Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, MI, 1995, p. 374-382.
  7. T. Ishihara and H. Yasuura, "Voltage scheduling problem for dynamically variable voltage processors," in Proceedings of the International Symposium on Low Power Electronics and Design, Monterey, CA, 1998, pp. 197-202.
  8. H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Alvarez, "Dynamic and aggressive scheduling techniques for poweraware real-time systems," in Proceedings of the 22nd IEEE Real-Time Systems Symposium, London, UK, 2001, pp. 95-105.
  9. D. Zhu, R. Melhem, and B. R. Childers, "Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 7, pp. 686-700, 2003. https://doi.org/10.1109/TPDS.2003.1214320
  10. Y. Shin, K. Choi, and T. Sakurai, "Power optimization of real-time embedded systems on variable speed processors," in Proceedings of IEEE/ACM International Conference on Computer Aided Design, SanJose, CA, pp. 365-368, 2000.
  11. G. Quan and X. Hu, "Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors," in Proceedings of Design Automation Conference, Las Vegas, NV, 2001, pp. 828-833.
  12. Y. Lee, Y. Doh, and C. M. Krishna, "EDF scheduling using two-mode voltage-clock-scaling for hard real-time systems," in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, Atlanta, GA, 2001, pp. 221-228.
  13. C. Isci, A. Buyuktosunoglu, C. Y. Chen, P. Bose, and M. Martonosi, "An analysis of efficient multi-core global power management policies: maximizing performance for a given power budget," in Proceedings of the 39th Annual IEEE/ ACM International Symposium on Microarchitecture, Orlando, FL, 2006, pp. 347-358.
  14. G. Dhiman and T. S. Rosing, "Dynamic voltage frequency scaling for multi-tasking systems using online learning," in Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design, Portland, OR, 2007, pp. 207-212.
  15. M. Kondo, H. Sasaki, and H. Nakamura, "Improving fairness, throughput and energy-efficiency on a chip multiprocessor through DVFS," ACM SIGARCH Computer Architecture News, vol. 35, no. 1, pp. 31-38, 2007. https://doi.org/10.1145/1241601.1241609
  16. N. Takagi, H. Sasaki, M. Kondo, and H. Nakamura, "Cooperative shared resource access control for low-power chip multiprocessors," in Proceedings of the 14th ACM/IEEE International Symposium on Low Power Electronics and Design, San Francisco, CA, 2009, pp. 177-182.
  17. R. Watanabe, M. Kondo, H. Nakamura, and T. Nanya, "Power reduction of chip multi-processors using shared resource control cooperating with DVFS," in Proceedings of the 25th International Conference on Computer Design, Lake Tahoe, CA, 2007, pp. 615-622.
  18. G. Dhiman, G. Marchetti, and T. Rosing, "vGreen: a system for energy efficient computing in virtualized environments," in Proceedings of the 14th ACM/IEEE International Symposium on Low Power Electronics and Design, San Francisco, CA, 2009, pp. 243-248.
  19. Y. C. Lee and A. Y. Zomaya, "Energy conscious scheduling for distributed computing systems under different operating conditions," IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 8, pp. 1374-1381, 2011. https://doi.org/10.1109/TPDS.2010.208
  20. S. Cho and R. G. Melhem, "Corollaries to Amdahl's law for energy," IEEE Computer Architecture Letters, vol. 7, no. 1, pp. 25-28, 2008. https://doi.org/10.1109/L-CA.2007.18
  21. D. Shin and J. Kim, "Power-aware scheduling of conditional task graphs in real-time multiprocessor systems," in Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design, Seoul, Korea, 2003, pp. 408-413.
  22. M. A. Moncusi, A. Arenas, J. Labarta, " Energy aware EDF scheduling in distributed hard real time systems," in Workin- Progress session of Real-Time Systems Symposium, Cancun, Mexico, 2003.
  23. T. Okuma, T. Ishihara, and H. Yasuura, "Real-time task scheduling for a variable voltage processor," in Proceedings of the 12th International Symposium on System Synthesis, San Jose, CA, 1999, pp. 24-29.
  24. L. Shang, L. S. Peh, and N. K. Jha, "Dynamic voltage scaling with links for power optimization of interconnection networks," in Proceedings of the 9th International Symposium on High-Performance Computer Architecture, Anaheim, CA, 2003, pp. 91-102.

Cited by

  1. Data-locality-aware mapreduce real-time scheduling framework vol.112, 2016, https://doi.org/10.1016/j.jss.2015.11.001
  2. GPU-SAM: Leveraging multi-GPU split-and-merge execution for system-wide real-time support vol.117, 2016, https://doi.org/10.1016/j.jss.2016.02.009
  3. An Adaptive Smart Grid Management Scheme Based on the Coopetition Game Model vol.36, pp.1, 2014, https://doi.org/10.4218/etrij.14.0113.0042