计算网格中能源消耗和响应时间最优结合的合作博弈理论

1、计算网格中能源消耗和响应时间最优结合的合作博弈理论 摘要：随着计算机的普及以及电力供应的不足，减少大型计算机系统能源的消耗 已成为一个最重要的研究课题。文章在研究计算网格的任务分配问题的同吋力求 能源消耗最小化并使完工时间符合期限和任务架构要求的限制。基于纳什讨价还 价解（nash bargaining solution）的观念我们从合作博弈论的角度提出一种解 决方法。在合作博弈论中，机器的任务分配对系统来说达到集体最佳状态，保证 了这种任务分配在能量消耗和时间相应上都是最佳的。经过严格的数学证明得到 我们提出的合作博弈理论仅在0（nm log（m）吋间内就产生一个保证帕累托最优 的纳什讨价还

2、价解（nbs） o实验结果表明，与贪焚启发式和线性松弛启发式理论 （the greedy and linear relaxation （lr） heuristics）相比，这种技术可以达到一 种非常完美的性能，并使小型问题在计算机上达到最优解。索引词：能量感矢口系统,分布式系统，纟勺束最优化，凸规划（convex programming）1引言在这种大型计算机系统中，比如计算网格需要消耗大量能量且冷却成本也很高9，能 量消耗已经成为一个关键问题。除了节能外，这些系统的设计必须满足功能和时间的要求 32。计算网格由一系列异构机器组成，这些地理上分布的异构多重处理器可以实现应用的 任务级并行性。由

3、于要达到最后期限的限制和系统的异构性，计算网格的资源分配也己成为 一个很具挑战性的问题。而当增加了能源管理这一额外的设计口标吋，这个问题就变得更有 挑战性，因为系统的能源消耗必须很好的与其他性能进行权衡132o资源分配和调度的传统 研究只是论述了固定的cpu速度和性能优化，因此并不适用于能量性能优化问题。通过动 态能源管理（dpm）或者动态电用调度（dvs）调节即时能源消耗可以实现能源的管理。 使用dpm方法可使处理器进入掉电状态，即只冇计算机系统的某些特定部分（例如，始终 脉冲振荡和时间电路）运行，而处理器处于闲置状态。dvs方法利用了 cpu供电电压和电 量消耗的凸关系。dvs技术的基本原

4、理是通过cpu频率和减低电压（voltage reduction.）得 到任务执行时间。木文研究了能量感知型任务分配（eata）问题，分别分配给具有dvs特征的计算网格 一-组任务。由于dvs模块只能改变瞬时功率，机器上任务的能源消耗就等于任务执行时间 间隔乘以机器的瞬吋功率。eata问题是广义分配问题（gpa）多约束多h标的延伸问题。 因此eata问题可以使用基于著名的纳什讨价还价解（nbs） i的合作博弈理论中的一个 新方法來解决。这种解决方案的概念可以缩写为nbs-eatao据我们所知，这是使川聘弈理 论解决计算网格的能蜃感知型任务分配问题所做的第一个工作。主要贡献。模型的发展和eata

5、问题的解决方法主要如下： 问题z是在维持机器特定性能（比如最后期限约束和任务结构耍求）耍求的同 时使得瞬时功率（与能源消耗和关）和完工时间的最小化。解决这个问题属于系 统级，相对于高度复杂性最小最小最人优化问题（具体详见3.1节）。 使用合作博弈理论技术，即，多目标凸规划（定理3）,可以将最小-最小-最大问题 转化为低复杂度的最大-最大-最小优化问题（详见5.1节）。这种低复杂度转化的鼓 人巨人优势就在于可以保证最人最人最小优化问题存在一个讨价还价点，因此可 以产生帕累托最优状态。我们定义帕累托最优状态如下：给出一系列可选的解决 方法，从一个方法移动到另一个方法可以至少得到一个更好的解决方法并

6、保证不 会使得其他方法变坏，这叫做帕累托改进。当没有更好的帕累托改进出现吋，这 个解决方法即帕累托最优。 尽管可以解决转化得到的最人最人最小优化问题以保证讨价还价点的存在，传统 的合作博弈理论技术，即纳什公理化技术15,由于低收敛速度和高复杂度19的 原因不能直接用于定义讨价还价点。传统的纳什公理化技术优于合作博弈的开创 性的解决方案，称为nbs。纳什在他文章里说明了传统的纳什公理化技术町以为 任何合作博弈提供解决方法。 由于传统纳什公理化技术的低收敛率和高复杂度，我们使川拉格朗fi乘数法获得 基于库恩-塔克条件(定理5和6)的多目标凸问题的必要和充分条件，这是为了 在一个快速周转时间内定义讨

7、价还价点。通过比较和分析实验结果，说明了某于 拉格朗li算子的nbs方法与传统纳什公理化技术相比较的有效性。 使用模拟和理论分析，以上提到的nbs-eata博弈也和其他的最优解作出比较， lindo122以及贪焚32和线性松弛(lr)32试探法。文章的其他部分安排如下：第2节简要讨论了札i关的工作。第3节讨论了 eata 问题公式化和相关的背景信息。第4节提供了一些适合于合作博弈的基本信息。第5 节模拟一个用于机器任务分配的合作博弈模型以同时最小化能源消耗和完工时间。第 6,7节分别讲述了模拟结果和结论。2相关工作人多dpm技术利用瞬时功率管理硬件支持的功能。例如，文献屮，作者通过一个自 适应

8、功率管理器(apm)扩展操作系统的电源管理器，apm主要是使用处理器的dvs能 力来减少或者增加cpu频率以最大限度的减少能源消耗。文献提到了处理器级的dvs 技术和集群级的开/关技术在保持反应时间的同时达到高功率的节省。文献20中，作者介绍 了一项计划，即集屮于集群屮有限数量服务器的工作量以使具他服务器可以处于开关关闭状 态一段较长的时间。尽管文献8已提到了结合设备电源来建立一个完整系统的模型的最接近技术，我们所 用方法的fi的在于建立一个口主电源和性能管理的一般框架，可以从整个系统的角度集合利 用现有的设备电源管理技术。此外，大多数电源管理技术不是利用基于启发式的方法9, 10, 11,

9、17, 25就是利用随机优化技术,22, 24, 30,而我们使用博弈理论找出与传统方法 相比根木上快速有效地解决方法，比如，启发式，基因算法，线性和动态规划，分支界限法。3问题公式化3背景信息下面这个公式说明了 cmos电路的电量消耗：p = v2 x f x cm',(1)其屮v, f和ceff分別表示电源电压，吋钟频率和电路有效交换电容。公式可以理解为，完 成一个操作的时间与时钟频率成反比32。这种关系可以进一步理解处理器的能量消耗即能 量是时间和功率的乘积。因此，每一个操作的能量e°p和v?成正比。这意味看，降低电源 电压将以二次方的倍率降低系统的能量消耗。但是，降低

10、电源电压一样会降低最人可达吋钟 频率。更具体的说，f是(大约)和v成正比2：p cc f3 and eop oc /2(2)以鮫低的时钟频率运行设备的cpu可以明显降低计算设备的瞬时功率消耗。降低电源电压同时降低时钟频率可以明显消除空闲周期并节省能源。因为炉厂i,我们有以下公式：p oc r-3 and eop oc t'2（3）其中t是完成一个操作的时间。因此，减低电源电压可以减少能源的传播，也将大大的减少 完成一个操作的时间。文献32中也有提到,从公式,（2）, （3）可以明显知道以线性增加延时（降低速度） 的代价可以以二次方的倍率减少能源消耗或者以三次方的倍率减少瞬时功率消耗。这

11、种关系 看起來似乎有些令张，因为1）这种关系不是持续的，他们只是作为电压调节的渐进功能2） 处理器消耗的电最或者能源并没有考虑内存访问所消耗的电量或者能源，而这是任何计算环 境的必要条件。文献2提到，处理器的频率大约和电源电压成正比，因此 公式（2）和（3） 的所有推导关系都是近似的。3.2系统模型该系统是包含计算网格和任务集合的一些列机器集合。机器。考虑一个包含一系列机器的计算网格，m=mbm2,-,rnmo假设每一个机器都有 dvs模块。机器有如下特点:dcpu的频率，即&给出单位时间的周期。动态电压调节可 使乌可以从fn到f貯变化（0 v 們 < /.max ）0根据频率大

12、小可以很容易得到cpu的 速度sj,sj与机器的频率成正比。（一个处理器速度和频率之间的关系是一种广泛的逼近，例 如文献14,32）。2）机器的特定结构,a（mj）,包括cpu类型，总线类型，ghz的速度, 输入/输出，内存大小。任务。考虑一个元任务,t=tj2,j 其中q代表一个任务。每一个任务有如下特 点：1）计算周期ci ,这里假设ci是己知的。2）特定的机器结构，a（0 ,需耍完成执行。 3）最终期限，di ,必须在最后期限之询完成执行。此外，我们假定元任务t也有一个最后 期限d,当h仅当所冇任务在截止日期前完成t才算在d z前完成。初始化。现在，假设给出一个计算网格和一个元任务t,我

13、们需要映射t到计算网格 上并保证所有任务的特点口满足最后期限限制t。我们说这是机器映射的可行任务。机器映 射的可行任务有如下特点：1）每一个任务力e t至少映射到一个机器mj上并满足这个任务 的所有约束条件一计算周期，结构和最后期限。2）截止日期限制t也要得到满足。假定在机器mi上执行任务ti所盂的计算周期数是一个冇限正数，记为cij o在恒速sij 下的执行时间，记为周期每秒tij = cij/s/ o对于给定的数据和任务指令，我们假定处理器总 是从初级数据高速缓存进行检索。任务ti在机器mj上执行产牛.的瞬时功率记为pij o降低 瞬时功率会降低cpu频率，因此会导致cpu速度的降低而可能

14、使得任务ti不能满足最终期 限的限制。为了简便起见，假定切换开销和cpu频率小到可以忽略不计。每一个任务结构要求可以看做是一个元祖的每一 个的每个元素的特定要求，例如，1） 任务执行所要求的处理器是怎样的？ 2）任务和机器匹配的结构亲和程度。我们假设结构要 求的映射是一个布尔运算。就是说结构映射当月仅当所冇的结构限制都满足时才得到满足, 否则就不满足。3.3公式化最小最小最大问题给出一个计算网格和一个元任务t。找出任务和机器的映射，1）计算网格的累计瞬时 功率降到最低2）元任务t的完工时间也最小化。以数学公式可以表示如卞：” 加最小化»旳并且最小化subject toxij e ()

15、/ = 1,2,., rz; j = 1,2,. . rn,ti >im() = 4(®);then 工订=1,(5)t'jxij di、vl, v/ hij = 1，(tijij < di) e 0,1,nh仏产u < 仏)=l,vz,vj,xy = 1.(8)i=l约束条件（4）是映射约束，具中厲门 =u,任务心映射于机器叫。约束条件（5）体现了 映射要求的结构条件，说明了只冇结构映射成功时任务和机器z间的映射才存在。约束条件（6）和每一个任务的需要满足的最后期限有关，约束条件（7）说明最后期限和任务执行实 际时间的布尔关系。约束条件（8）说明了当且仅当

16、所有任务di （1=1,2,，n）的最后期 限都得到满足时元任务的最后期限才会冇所保证。3.4示例方案4合作博弈理论的基本知识合作博弈。假设有m个竞争者。山 是竞争者j（j=l, 2,m）的目标函数。小则 是一个从x到r的函数，入匚況°是一个非空闭合的凸集。6模拟实验，结果和讨论我们使用真实的任务组來模拟研究（后血有相关的讲述）0我们为模拟研究设置了两大目标:1）衡量和比较m3s-eata和最优解，贪婪和线性松弛启发式理论的性能。2）测量发生变化（比如工作虽地增加）对系统变量的影响。我们选择和贪婪启发式理论以及线性松弛启发式 理论作比较是因为他们和其他启发式理论相比较表现出极好的性能

17、。现在，我们简单描述一 卜-这两种技术。贪婪启发式。贪婪启发式理论是高引用min-min 发式理论的延伸4。修改后的理论 使得系统的能虽消耗最小化。初始化一个为分派任务集u。第一步，对于每一个为分派任务, 启发式理论找到可以消耗最小能量执行这个任务的机器。第二步，从笫一步中找出的（任务, 机器）对中选择消耗能量最小的対。所选对的任务排队等待所选对的机器执行。执行后从集 合u中删除这个任务并继续进行第一步。线性松弛启发式。线性松弛启发式理论的输入是一般指派问题（gap）而输出机器匹配的 任务。lr启发式的垄木理论在于把匹配任务看做是一棵树的查找结构（多一条边地树，多 出的边可以是空闲的边，形成一

18、个环）。杳找是在任务和机器的二分图上完成的。lr开始于 对二分图结点的匹配。然后继续增加另一个单一的任务到机器映射中并口改变现有的所有 映射以找到一个可行的任务和机器映射以消耗最少量地能量。由于lr的输入是一个gap（我 们的eata问题也是gap规划），能蜃限制和其他限制都自动考虑。基于问题的人小，模拟被分成两部分。对于小型问题，我们使用一种整数线性规划工具 lindo22, lindo对于小型问题最优解问题很有效。因此，对于小型问题,nbs-eata,贪 婪和lr技术的相对性能和ltndo相比较。而对于大型问题，利用ijnd0來计算授优解决方 案变得很不实际。因此 我们只考虑和贪焚以及lr启发式之间的比