Ec-A: A Task Allocation Algorithm for Energy Minimization in Multiprocessor Systems

Authors: Anju S. Pillai, T.B. Isha

Abstract:

With the necessity of increased processing capacity with less energy consumption; power aware multiprocessor system has gained more attention in the recent future. One of the additional challenges that is to be solved in a multi-processor system when compared to uni-processor system is job allocation. This paper presents a novel task dependent job allocation algorithm: Energy centric- Allocation (Ec-A) and Rate Monotonic (RM) scheduling to minimize energy consumption in a multiprocessor system. A simulation analysis is carried out to verify the performance increase with reduction in energy consumption and required number of processors in the system.

Keywords: Energy consumption, Job allocation, Multiprocessor systems, Task dependent.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1091690

References:

[1] S. H. Edwin Hou, Nirwan Ansari, Hong Ren, "A genetic algorithm for multiprocessor scheduling”, IEEE Trans. on Parallel and Distributed Systems, vol. 5, no. 2, February 1994.
[2] Jane W. S. W. Liu. Real-Time Systems. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2000.
[3] C. L. Liu and J. W. Layland, "Scheduling algorithms for Multi programming in a hard-real-time environment”, Journal of ACM, vol. 20, no. 1, pp. 4661, 1973.
[4] G. Buttazzo, "Rate monotonic vs. EDF: Judgment day”, in Proceedings of 3rd ACM International Conference on Embedded Software, Philadephia, USA, Oct 2003.
[5] Moreshet, Tali and Bahar, R. Iris and Herlihy, Maurice. "Energy reduction in multiprocessor systems using transactional memory”, ISLPED, editor(s) Roy, Kaushik and Tiwari, Vivek. 331-334, ACM, 2005.
[6] Wei, T., Mishra, P., Wu, K., Liang, H., "Fixed-Priority Allocation and Scheduling for Energy-Efficient Fault Tolerance in Hard Real-Time Multiprocessor Systems", IEEE Transactions on Parallel and Distributed Systems, On page(s): 1511 - 1526, Volume: 19 Issue: 11, Nov. 2008.
[7] Sung I. Park, "The Design of Power Aware Embedded Systems,” PhD Thesis, University of California, Los Angeleles, 2003.
[8] Padmanabhan Pillai and Kang G. Shin,"Real-Time Dynamic Voltage Scaling for Low Power Embedded Operating Systems”, Symposium on Operating Systems Principles’01, 2001.
[9] Woonseok Kim; Jihong Kim; Sang Lyul-Min, "Dynamic voltage scaling algorithm for fixed-priority real-time systems using work-demand analysis," ISLPED '03. Proceedings of the 2003 International Symposium on Low Power Electronics and Design, vol., no., pp. 396- 401, 25-27 Aug. 2003.
[10] J. Goossens, S. Funk, and S. Baruah. "Priority-driven scheduling of periodic tasks systems on multiprocessors”, Real-Time Systems, 25(2-3):187–205, 2003.
[11] S.K. Baruah, N.K. Cohen, C.G. Plaxton, D.A. Varel, "Proportionate progress: a notion of fairness in resource allocation”, Algorithmica 15 (6), 600–625., 1996.
[12] S.K. Baruah, J. Gehrke, C.G. Plaxton, "Fast scheduling of periodic tasks on multiple resources”, Proc. of The International Parallel Processing Symposium, pp. 280–288, Apr. 1995.
[13] J.H. Anderson, A. Srinivasan, "Mixed pfair/erfair scheduling of asynchronous periodic tasks”, Proc. of the 13th Euromicro Conference on Real-Time Systems, pp. 76–85, Jun. 2001,
[14] J.H. Anderson, A. Srinivasan, "Early-release fair scheduling”, Proc. of the 12th Euromicro Conference on Real-Time Systems, pp. 35–43, Jun. 2000.
[15] J.H. Anderson, A. Srinivasan, "Pfair scheduling: Beyond periodic task systems”, Proc. of the 7th Int’l Workshop on Real-Time Computing Systems and Applications, pp. 297–306., Dec. 2000
[16] Dakai Zhu, Xuan Qi, Daniel Mosse, Rami Melham, "An optimal boundary fair algorithm scheduling algorithm for multiprocessor real time systems”, Journal of parallel and Distributed Computing, pp. 1411-1425, Jun. 2011.
[17] H. Aydin, D. Zhu, "Reliability-aware energy management for periodic real-time tasks”, IEEE Transactions on Computers, 58:10, 1382–1397, Jun. 2011.
[18] L. Huang, Q. Xu, "Energy-efficient task allocation and scheduling for multimode MPSoCs under lifetime reliability constraint”, in: IEEE Conference on Design, Automation and Test in Europe, 2010.
[19] A. Das, A. Kumar, B. Veeravalli, "Energy-aware communication and remapping of tasks for reliable multimedia multiprocessor systems”, in: International Conference on Parallel and Distributed Systems, ICPADS, 2012.
[20] Chang, Po-Chun and Wu, I-Wei and Shann, Jean Jyh-Jiun and Chung, Chung-Ping.” ETAHM: an energy-aware task allocation algorithm for heterogeneous multiprocessor”, DAC. editor(s) Fix, Limor. 776-779, ACM, 2008.
[21] Apodaca, Jonathan and Young, Bobby Dalton and Briceno, Luis Diego and Smith, Jay and Pasricha, Sudeep and Maciejewski, Anthony A. and Siegel, Howard Jay and Bahirat, Shirish and Khemka, Bhavesh and Ramirez, Adrian and Zou, Yong. "Stochastically robust static resource allocation for energy minimization with a makespan constraint in a heterogeneous computing environment”, AICCSA. editor(s) Siegel, Howard Jay and El-Kadi, Amr. 22-31, IEEE, 2011.
[22] Karimi, Hamid and Kargahi, Mehdi and Yazdani, Nasser. "On the Handling of Node Failures: Energy-Efficient Job Allocation Algorithm for Real-time Sensor Networks”, In JIPS, (6) 3: 413-434, 2010.
[23] Mohsen Sharifi, and Morteza Okhovvat, "Scate: A Scalable Time and Energy Aware Actor Task Allocation Algorithm in Wireless Sensor and Actor Networks," ETRI Journal, vol. 34, no. 3, pp. 330-340, Jun. 2011.
[24] Tarek A. AlEnawy, Hakan Aydin, "Energy-Aware Task Allocation for Rate Monotonic Scheduling", IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 213-223, 2013.
[25] Paterna, Francesco and Acquaviva, Andrea and Caprara, Alberto and Papariello, Francesco and Desoli, Giuseppe and Benini, Luca. "An efficient on-line task allocation algorithm for QoS and energy efficiency in multicore multimedia platforms”, pp.100-105, IEEE, 2011.
[26] Shinpei Kato and Nobuyuki Yamasaki, "Real Time Scheduling with Task Splitting on Multiprocessors,” in 8th IEEE International conference on Embedded and Real-Time computing systems and Applications, RTCSA 2007.
[27] M. Joseph, P.Pandya, "Finding response times in a real time system”, BCS Computer Journal, vol. 29, no. 5, pp. 390-395, Oct. 1986.
[28] E., Bini, G., C., Buttazzo, "Biasing Effects in Schedulability Measures”, IEEE Proceedings of the 16th Euromicro Conference on Real-Time Systems, Aatania, Italy, July 2004.