博弈论优化：能源消耗与响应时间的协同计算网格策略

需积分: 1 17 浏览量更新于2024-08-02 收藏 3.53MB PDF 举报

本文主要探讨了"合作博弈理论在大型计算网格中联合优化能源消耗与响应时间的应用"。随着计算机数量的爆炸性增长和电力供应的日益紧张，降低大规模计算系统中的能源消耗已成为一个关键的研究课题。作者Samee Ullah Khan和Ishfaq Ahmad，两位IEEE会员，针对这一问题提出了一个新的解决方案。他们关注的是如何有效地将任务分配到计算网格上，同时最小化能源消耗和满足任务的截止日期以及架构需求。作者采用博弈论中的纳什均衡谈判解（Nash Bargaining Solution, NBS）概念作为核心策略。在这个合作博弈游戏中，机器作为一个整体，共同决定一个对整个系统最优的任务分配，确保既能实现能源效率又能控制总执行时间的最优化。他们证明，通过严格的数学分析，这个基于NBS的博弈理论方法可以在O(nm log(m))的时间复杂度内（其中n是任务的数量，m是系统中机器的数量）得出一个NBS，从而提供了一个有效且高效的算法。这种方法强调了合作的重要性，机器之间通过协商达成共识，使得资源分配既公平又高效，有助于平衡各参与方的利益，同时也最大化了系统的整体性能。论文深入研究了博弈论模型如何应用于计算网格的资源管理，特别是在资源分配决策过程中考虑多目标优化问题。它不仅提供了理论框架，还可能为实际的系统设计和运营提供有价值的指导，推动能源效率和计算性能的双重提升。对于那些关注云计算、绿色计算和分布式系统优化的科研人员来说，这篇论文无疑提供了重要的理论支持和技术参考。

relationships seem to be a bit exaggerated, because 1) the

relationships are not continuous, they rather progresses as a

stepwise function relative to the scaling of the voltage and

2) the power or energy consumed by the processor does not

take into account the amount of power or energy spent on

memory accesses that in any computational environment is

a necessary condition. As mentioned in [2], the frequency of

a processor is approximately proportional to the supply

voltage; hence, all the subsequent relationships in (2) and

(3) are a mere approximation.

3.2 The System Model

The system is a collection of machines that comprise the

computational grid and the collection of tasks.

Machines. Consider a computational grid comprising of

a set of machines, M ¼fm

; ...;m

g. Assume that each

machine is equipped with a DVS module. Each machine is

characterized by 1) The frequency of the CPU, f

, given in

cycles per unit time. With the help of a DVS, f

can vary

from f

min

to f

max

, where 0 <f

min

max

. From frequency,

it is easy to obtain the speed of the CPU, S

, which is

approximately proportional to the frequency of the ma-

chine. (This relationship between speed and the frequency

of a processor is a widespread approximation, e.g., [14],

[32].) 2) The specific machine architecture, Aðm

Þ. The

architecture would include the type of CPU, bus types, and

speeds in GHz, I/O, and memory in bytes.

Tasks. Consider a metatask, T ¼ft

; ...;t

g, where t

is a task. Each task is characterized by 1) The computational

cycles, c

, that it needs to complete. The assumption here is

that the c

is known a priori. 2) The specific machine

architecture, Aðt

Þ, that it needs to complete its execution.

3) The deadline, d

, before it has to complete its execution.

Moreover, we also assume that the metatask, T, also has a

deadline, D, which is met if and only if the deadlines of all

its tasks are met.

Preliminaries. Now, suppose we are given a computa-

tional grid and a metatask, T , and we are required to map T

on the computational grid such that all the characteristics of

the tasks and the deadline constraint of T are fulfilled. We

term this fulfillment as a feasible task to machine mapping.

A feasible task to machine mapping happens when 1) Each

task t

2 T can be mapped to at least one m

subject to all

the constraints associated with each task—computational

cycles, architecture, and deadline. 2) The deadline con-

straint of T is also satisfied.

The number of computational cycles required by t

execute on m

is assumed to be a finite positive number,

denoted by c

. The execution time of t

under a constant

speed S

, given in cycles per second is t

¼ c

. For the

associated data and instructions of a task, we assume that

the processor always retrieves it from the level-1 (primary)

data cache. A task, t

, when executed on machine m

draws,

amount of instantaneous power. Lowering the instanta-

neous power will lower the CPU frequency and conse-

quently will decrease the speed of the CPU and hence cause

to possibly miss its deadline. For simplicity, assume that

switching the overhead, the CPU frequency is minimal, and

hence, ignored.

The architectural requirements of each task are recorded

as a tuple with each element bearing a specific requirement,

for instance, 1) what processor does the task require for its

execution? 2) The architectural affinity matching of the task

to the machine. We assume that the mapping of architec-

tural requirements is a Boolean operation. That is, the

architectural mapping is only fulfilled when all of the

architectural constraints are satisfied, otherwise not.

3.3 Formulating the Min-Min-Max Problem

Given is a computation grid and a metatask T . Find the task

to machine mapping, where 1) the cumulative instanta-

neous power utilized by the computational grid is

minimized such that 2) the makespan of the metatask, T ,

is minimized.

Mathematically, we can say

minimize

i¼1

j¼1

and minimize max

1jm

i¼1

subject to

2f0; 1g;i ¼ 1; 2; ...;n; j ¼ 1; 2; ...m; ð4Þ

! m

; 8i; 8j;ifAðt

Þ¼Aðm

Þ; then x

¼ 1; ð5Þ

 d

; 8i; 8j; x

¼ 1; ð6Þ

ðt

 d

Þ2f0; 1g; ð7Þ

i¼1

ðt

 d

Þ¼1; 8i; 8j; x

¼ 1: ð8Þ

Constraint (4) is the mapping constraint, when x

¼ 1,a

task, t

, is mapped to machine, m

. Constraint (5) elaborates

on this mapping in conjunction to the architectural

requirements, and it states that a mapping can only exists

if the architecture is mapped. Constraint (6) relates to the

fulfillment of the deadline of each task, and constraint (7)

tells us about the Boolean relationship between the deadline

and the actual time of execution of the tasks. Constraint (8)

relates to the deadline constraints of the metatask that will

hold if and only if all the deadlines of the tasks, d

i ¼ 1; 2; ...n, are satisfied.

The above problem formulation is in a form of multi-

constrained multiobjective optimization problem, where the

preference is given to one optimization over the other.

Because we are more interested in minimizing the instanta-

neous power consumption, we give preference to the first

objective that is the instantaneous power consumption. This

formulation is in the same form as that of a GAP except for

constraints of (6), (7), and (8). The major difference between

EATA and GAP is that the capacity of resources in EATA,

in terms of the utilization of instantaneous power, is

defined in groups, whereas in the case of GAP, it is defined

individually. The EATA problem is formulated as a multi-

objective optimization problem. In the literature, there are

two standard ways to tackle such problems: 1) optimize

objectives concurrently and 2) optimize one objective first,

then make that as a constraint of the second objective. To

optimize objectives concurrently, the classical method to

tackle such problems is to use Lagrange multipliers. The

Lagrangian will converge the two (in our case) or multiple

objectives to a saddle point [12]. To optimize one objective

first, then make that as a constraint of the second objective,

348 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 20, NO. 3, MARCH 2009

剩余14页未读，继续阅读

lujianzhu

粉丝: 0

博弈论优化：能源消耗与响应时间的协同计算网格策略

"基于Unity引擎的多人合作休闲游戏设计与优化研究

"基于褚健学术研究的高校合作与优势分析

"数据融合的协作频谱感知方法研究：认知无线电新技术探索"。

A Cooperative Game Based Allocation for Sharing Data Center Networks

Incentive MeIncentive Mechanism for Cooperative Content Discovery in Mobile Wireless Networks: A Repeated Cooperative Game-theoretic Approach

Wireless Energy Harvesting and Information Processing in Cooperative Wireless Sensor Networks”

Cooperative Control and Optimization

Boosting Cooperative Coevolution for Large Scale Optimization With a Fine-Grained Computation Resource Allocation Strategy

A Model for Cooperative Mobility and Budgeted QoS in MANETs

CATS: Cooperative Allocation of Tasks and Scheduling of Sampling Intervals for Maximizing Data Sharing in WSNs

最新资源