A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids
A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids
复制标题
DOI：
10.1109/tpds.2008.83
复制
发表时间：
2009-03-01
影响因子：
5.3
通讯作者：
Ahmad, Ishfaq
中科院分区：
文献类型：
--
作者：
Khan, Samee Ullah;Ahmad, Ishfaq
随着计算机的爆炸式增长和电力供应的日益短缺，降低大规模计算系统的能耗已成为首要的研究课题。在本文中，我们研究的问题分配到一个计算网格的任务，目的是同时最小化的能源消耗和完工时间的约束期限和任务的架构要求。我们提出了一个解决方案，从合作博弈论的基础上的纳什谈判解决方案（NBS）的概念。在这个合作游戏中，机器共同做出一个决定，该决定描述了对系统来说最好的任务分配，确保分配既优化了能量又优化了制造时间。通过严格的数学证明，我们表明，提出的合作游戏在仅仅O（nmlog（m））时间（其中n是任务的数量，和m是系统中的机器的数量）产生一个NBS，保证帕累托最优。仿真结果表明，该技术实现了上级性能相比，贪婪和线性松弛（LR）算法和竞争力的性能相对于最优解UNDO实现的小规模问题。
With the explosive growth in computers and the growing scarcity in electric supply, reduction of energy consumption in large-scale computing systems has become paramount research issue. In this paper, we study the problem of allocation of tasks onto a computational grid, with the aim to simultaneously minimize the energy consumption and the makespan subject to the constraints of deadlines and tasks' architectural requirements. We propose a solution from cooperative game theory based on the concept of Nash Bargaining Solution (NBS). In this cooperative game, machines collectively arrive at a decision that describes the task allocation that is collectively best for the system, ensuring that the allocations are both energy and makespan optimized. Through rigorous mathematical proofs we,show that the proposed cooperative game in mere O(nmlog(m)) time (where n is the number of tasks, and m is the number of machines in the system) produces a NBS that guarantees Pareto optimally. The simulation results show that the proposed technique achieves superior performance compared to the Greedy and Linear Relaxation (LR) heuristics and with competitive performance relative to the optimal solution implemented in UNDO for small-scale problems.