Energy Efficient Resource Allocation in Distributed Computing Systems

Authors: Samee Ullah Khan, C. Ardil

Abstract:

The problem of mapping tasks onto a computational grid with the aim to minimize the power consumption and the makespan subject to the constraints of deadlines and architectural requirements is considered in this paper. To solve this problem, we propose a solution from cooperative game theory based on the concept of Nash Bargaining Solution. The proposed game theoretical technique is compared against several traditional techniques. The experimental results show that when the deadline constraints are tight, the proposed technique achieves superior performance and reports competitive performance relative to the optimal solution.

Keywords: Energy efficient algorithms, resource allocation, resource management, cooperative game theory.

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

References:

[1] T. Abdelzaher and V. Sharma, "A Synthetic Utilization Bound for Aperiodic Tasks with Resource Requirements," in Euromicro Conference on Real Time Systems, 2003.
[2] T. Abdelzaher and C. Lu, "Schedulability Analysis and Utilization Bounds for Highly Scalable Real-time Services," in IEEE Real-Time Technology and Applications Symposium, 2001.
[3] S. Ali, H. J. Siegel, M. Maheswaran, D. Hensgen and S. Ali, "Task Execution Time Modeling for Heterogeneous Computing Systems," in 9th Heterogeneous Computing Workshop, May 2000, pp. 185-199.
[4] Application Specific and Automatic Power Management based on Whole Program Analysis, available at: http://cslab.snu.ac.kr/~egger/apm/final-report.pdf, 2004.
[5] H. Aydin, R. Melhem, D. Mosse and P. Mejya-Alvarez, "Dynamic and Aggressive Scheduling Techniques for Power-aware Real-time Systems," in IEEE Real-Time Systems Symposium, Dec. 2001, pp. 95- 105.
[6] R. Bianchini and R. Rajamony, "Power and Energy Management for Server Systems," IEEE Computer, vol. 37, no. 11, pp. 68-74, 2004.
[7] S. J. Brams, Theory of Moves, Cambridge University Press, New York, USA, 1994.
[8] T. D. Braun, S. Ali, H. J. Siegel and A. A. Maciejewski, "Using the Min- Min Heuristic to Map tasks onto Heterogeneous High-performance Computing Systems," in 2nd Symposium of the Los Alamos Computer Science Institute, Oct. 2001.
[9] A. P. Chandrakasan, S. Sheng and R. W. Brodersen, "Low Power CMOS Digital Design, IEEE Journal of Solid-State Circuits, 27(4):473- 484, 1992.
[10] E. Chung, L. Benini, A. Bogliolo and G. Micheli, "Dynamic Power Management for non-stationary service requests", IEEE Transactions on Computers, vol. 51, no. 11, pp. 1345-1361, 2002.
[11] E. N. Elnozahy, M. Kistler, R. Rajamony, "Energy-Efficient Server Clusters," in 2nd Workshop on Power-Aware Computing Systems, 2002.
[12] J. Greenberg, The Theory of Social Situations: An Alternative Game- Theoretic Approach, Cambridge University Press, Cambridge, UK, 1990.
[13] S. Gurumurthi, A. Sivasubramaniam, M.J. Irwin, N. Vijaykrishnan, M. Kandemir, T. Li and L.K. John, "Using Complete Machine Simulation for Software Power Estimation: The SoftWatt Approach," in International Symposium on High Performance Computer Architecture, 2000, pp. 141-150.
[14] I. Hong, G. Qu, M. Potkonajak and M. B. Srivastava, "Synthesis Techniques for Low-power Hard Real-time Systems on Variable Voltage Processors," in IEEE Real-time Systems Symposium, 1998, pp. 178-187.
[15] C. Hsu and U. Kremer, "The Design, Implementation, and Evaluation of a Compiler Algorithm for CPU Energy Reduction," in International Conference on Programming Language Design and Implementation, 2003.
[16] C.-H. Hwang and A. Wu, "A Predictive System Shutdown Method for Energy Saving of Event-driven Computation," in International Conference on Computer-Aided Design, 1997, pp. 28-32.
[17] S. U. Khan and I. Ahmad, "A Powerful Direct Mechanism for Optimal WWW Content Replication," in 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2005.
[18] S.U. Khan and I. Ahmad, "Non-cooperative, Semi-cooperative, and Cooperative Games-based Grid Resource Allocation," in 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.
[19] B. Khargharia, S. Hariri, F. Szidarovszky, M. Houri, H. El-Rewini, S. U. Khan, I. Ahmad, and M. S. Yousif, "Autonomic Power & Performance Management for Large-Scale Data Centers," NSF Next Generation Software Program Workshop, in 21th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2007.
[20] D. G. Luenberger, Linear and Nonlinear Programming, Addison- Wesley, 1984.
[21] C. Montet and D. Serra, Game Theory and Economics, Palgrave, 2003.
[22] J. Nash, "The Bargaining Problem," Econometrica, vol. 18, pp. 155-162, 1950.
[23] J. Nash, "Non-Cooperative Games," Annals of Mathematics, vol. 54, pp. 286-295, 1951.
[24] M. J. Osborne and A. Rubistein, A Course in Game Theory, MIT Press, Massachusetts, U.S.A., 1994.
[25] C. H. Papadimitriou and M. Yannakakis, "On the Approximability of Trade-offs and Optimal Access of Web Sources," in 41st IEEE Symposium on Foundations of Computer Science, 2000, pp. 86-92.
[26] E. Pinheiro, R. Bianchini, E. V. Carrera and T. Heath, "Load Balancing and Unbalancing for Power and Performance in Cluster-Based Systems," in Workshop on Compilers and Operating Systems for Low Power, 2001.
[27] Q. Qiu and M. Pedram, "Dynamic Power Management Continuous-time Markov Decision Processes," in 36th Design Automation Conference, 1999, pp. 555-561.
[28] L. Schrage, Linear, Integer, and Quadratic Programming with LINDO, The Scientific Press, USA, 1986.
[29] T. Simunic, "Dynamic Management of Power Consumption", in Power Aware Computing, pp. 101-125, 2002.
[30] M. Srivastava, A. Chandrakasan and R. Brodersen, "Predictive System Shutdown and other Architectural Techniques for Energy Efficient Programmable Computation," IEEE Transactions on VLSI Systems, vol. 4, pp. 42-55, 1996.
[31] A. Stefanescu and M. W. Stefanescu, "The Arbitrated Solution for Multiobjective Convex Programming," Rev. Roum. Math. Pure Applicat., vol. 29, pp. 593-598, 1984.
[32] T. E. Truman, T. Pering, R. Doering and R. W. Brodersen, "The InfoPad Multimedia Terminal: A Portable Device for Wireless Information Access," IEEE Trans. Computers, 47(10):1073-1087, 1998.
[33] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, 3ed, Princeton University Press, 1953.
[34] M. Weiser, B. Welch, A. J. Demers and S. Shenker, "Scheduling for reduced CPU Energy," in Symposium on Operating Systems Design and Implementation, Nov. 1994, pp. 13-23.
[35] H. Yaiche, R. R. Mazumdar and C. Rosenberg, "A Game Theoretic Framework for Bandwidth Allocation and Pricing in Broadband Networks," IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 667-678, 2000.
[36] Y. Yu and V. K. Prasanna, "Power-Aware Resource Allocation for Independent Tasks in Heterogeneous Real-Time Systems," in 9th IEEE International Conference on Parallel and Distributed Systems, 2002.