Energy Efficient Resource Allocation in Distributed Computing Systems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:53414", author = "Samee Ullah Khan and C. Ardil", title = "Energy Efficient Resource Allocation in Distributed Computing Systems", 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.", volume = "3", number = "8", pages = "1946-7", }
