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

计算网格中能源消耗和响应时间最优结合的合作博弈理论摘要：随着计算机的普及以及电力供应的不足，减少大型计算机系统能源的消耗已成为一个最重要的研究课题。文章在研究计算网格的任务分配问题的同时力求能源消耗最小化并使完工时间符合期限和任务架构要求的限制。基于纳什讨价还价解（Nash bargaining solution）的观念我们从合作博弈论的角度提出一种解决方法。在合作博弈论中，机器的任务分配对系统来说达到集体最佳状态，保证了这种任务分配在能量消耗和时间相应上都是最佳的。经过严格的数学证明得到我们提出的合作博弈理论仅在O(nm log(m)时间内就产生一个保证帕累托最优的纳什讨价还价解(NBS)。实验结果表明，与贪婪启发式和线性松弛启发式理论(the Greedy and Linear Relaxation (LR) heuristics)相比，这种技术可以达到一种非常完美的性能，并使小型问题在计算机上达到最优解。索引词：能量感知系统，分布式系统，约束最优化，凸规划(convex programming)1 引言在这种大型计算机系统中，比如计算网格需要消耗大量能量且冷却成本也很高9，能量消耗已经成为一个关键问题。除了节能外，这些系统的设计必须满足功能和时间的要求32。计算网格由一系列异构机器组成，这些地理上分布的异构多重处理器可以实现应用的任务级并行性。由于要达到最后期限的限制和系统的异构性，计算网格的资源分配也已成为一个很具挑战性的问题。而当增加了能源管理这一额外的设计目标时，这个问题就变得更有挑战性，因为系统的能源消耗必须很好的与其他性能进行权衡32。资源分配和调度的传统研究只是论述了固定的CPU速度和性能优化，因此并不适用于能量性能优化问题。通过动态能源管理（DPM）或者动态电压调度（DVS）调节即时能源消耗可以实现能源的管理。使用DPM方法可使处理器进入掉电状态，即只有计算机系统的某些特定部分（例如，始终脉冲振荡和时间电路）运行，而处理器处于闲置状态。DVS方法利用了CPU供电电压和电量消耗的凸关系。DVS技术的基本原理是通过CPU频率和减低电压（voltage reduction.）得到任务执行时间。本文研究了能量感知型任务分配（EATA）问题，分别分配给具有DVS特征的计算网格一组任务。由于DVS模块只能改变瞬时功率，机器上任务的能源消耗就等于任务执行时间间隔乘以机器的瞬时功率。EATA问题是广义分配问题（GPA）多约束多目标的延伸问题。因此EATA问题可以使用基于著名的纳什讨价还价解（NBS）15的合作博弈理论中的一个新方法来解决。这种解决方案的概念可以缩写为NBS-EATA。据我们所知，这是使用博弈理论解决计算网格的能量感知型任务分配问题所做的第一个工作。主要贡献。模型的发展和EATA问题的解决方法主要如下：l 问题之一是在维持机器特定性能（比如最后期限约束和任务结构要求）要求的同时使得瞬时功率（与能源消耗相关）和完工时间的最小化。解决这个问题属于系统级，相对于高度复杂性最小-最小-最大优化问题（具体详见3.1节）。l 使用合作博弈理论技术，即，多目标凸规划（定理3），可以将最小-最小-最大问题转化为低复杂度的最大-最大-最小优化问题（详见5.1节）。这种低复杂度转化的最大巨大优势就在于可以保证最大-最大-最小优化问题存在一个讨价还价点，因此可以产生帕累托最优状态。我们定义帕累托最优状态如下：给出一系列可选的解决方法，从一个方法移动到另一个方法可以至少得到一个更好的解决方法并保证不会使得其他方法变坏，这叫做帕累托改进。当没有更好的帕累托改进出现时，这个解决方法即帕累托最优。l 尽管可以解决转化得到的最大-最大-最小优化问题以保证讨价还价点的存在，传统的合作博弈理论技术，即纳什公理化技术15，由于低收敛速度和高复杂度19的原因不能直接用于定义讨价还价点。传统的纳什公理化技术优于合作博弈的开创性的解决方案，称为NBS。纳什在他文章里说明了传统的纳什公理化技术可以为任何合作博弈提供解决方法。l 由于传统纳什公理化技术的低收敛率和高复杂度，我们使用拉格朗日乘数法获得基于库恩-塔克条件（定理5和6）的多目标凸问题的必要和充分条件，这是为了在一个快速周转时间内定义讨价还价点。通过比较和分析实验结果，说明了基于拉格朗日算子的NBS方法与传统纳什公理化技术相比较的有效性。l 使用模拟和理论分析，以上提到的NBS-EATA博弈也和其他的最优解作出比较，LINDO22以及贪婪32和线性松弛(LR)32试探法。文章的其他部分安排如下：第2节简要讨论了相关的工作。第3节讨论了EATA问题公式化和相关的背景信息。第4节提供了一些适合于合作博弈的基本信息。第5节模拟一个用于机器任务分配的合作博弈模型以同时最小化能源消耗和完工时间。第6,7节分别讲述了模拟结果和结论。2 相关工作大多DPM技术利用瞬时功率管理硬件支持的功能。例如，文献1中，作者通过一个自适应功率管理器（APM）扩展操作系统的电源管理器，APM主要是使用处理器的DVS能力来减少或者增加CPU频率以最大限度的减少能源消耗3。文献7提到了处理器级的DVS技术和集群级的开/关技术在保持反应时间的同时达到高功率的节省。文献20中，作者介绍了一项计划，即集中于集群中有限数量服务器的工作量以使其他服务器可以处于开关关闭状态一段较长的时间。尽管文献8已提到了结合设备电源来建立一个完整系统的模型的最接近技术，我们所用方法的目的在于建立一个自主电源和性能管理的一般框架，可以从整个系统的角度集合利用现有的设备电源管理技术。此外，大多数电源管理技术不是利用基于启发式的方法9, 10, 11, 17, 25就是利用随机优化技术6, 22, 24, 30，而我们使用博弈理论找出与传统方法相比根本上快速有效地解决方法，比如，启发式，基因算法，线性和动态规划，分支界限法。3 问题公式化3.1背景信息下面这个公式说明了CMOS电路的电量消耗： ,(1)其中V，f和CEFF 分别表示电源电压，时钟频率和电路有效交换电容。公式可以理解为，完成一个操作的时间与时钟频率成反比32。这种关系可以进一步理解处理器的能量消耗即能量是时间和功率的乘积。因此，每一个操作的能量Eop和V2成正比。这意味着，降低电源电压将以二次方的倍率降低系统的能量消耗。但是，降低电源电压一样会降低最大可达时钟频率。更具体的说，f是（大约）和V成正比2： and （2）以较低的时钟频率运行设备的CPU可以明显降低计算设备的瞬时功率消耗。降低电源电压同时降低时钟频率可以明显消除空闲周期并节省能源。因为，我们有以下公式： and （3）其中t是完成一个操作的时间。因此，减低电源电压可以减少能源的传播，也将大大的减少完成一个操作的时间。文献32中也有提到，从公式(1)，（2），（3）可以明显知道以线性增加延时（降低速度）的代价可以以二次方的倍率减少能源消耗或者以三次方的倍率减少瞬时功率消耗。这种关系看起来似乎有些夸张，因为1)这种关系不是持续的，他们只是作为电压调节的渐进功能2)处理器消耗的电量或者能源并没有考虑内存访问所消耗的电量或者能源，而这是任何计算环境的必要条件。文献2提到，处理器的频率大约和电源电压成正比，因此，公式（2）和（3）的所有推导关系都是近似的。3.2系统模型该系统是包含计算网格和任务集合的一些列机器集合。机器。考虑一个包含一系列机器的计算网格，M=m1,m2,mm。假设每一个机器都有DVS模块。机器有如下特点：1）CPU的频率，即fj,给出单位时间的周期。动态电压调节可使fj可以从到变化（）。根据频率大小可以很容易得到CPU的速度Sj, Sj与机器的频率成正比。（一个处理器速度和频率之间的关系是一种广泛的逼近，例如文献14,32）。2）机器的特定结构，包括CPU类型，总线类型，GHz的速度，输入/输出，内存大小。任务。考虑一个元任务，T=t1,t2,，tn，其中ti代表一个任务。每一个任务有如下特点：1）计算周期Ci ，这里假设Ci是已知的。2）特定的机器结构，A(ti) ，需要完成执行。3）最终期限，di ，必须在最后期限之前完成执行。此外，我们假定元任务T也有一个最后期限D，当且仅当所有任务在截止日期前完成T才算在D之前完成。初始化。现在，假设给出一个计算网格和一个元任务T，我们需要映射T到计算网格上并保证所有任务的特点且满足最后期限限制T。我们说这是机器映射的可行任务。机器映射的可行任务有如下特点：1）每一个任务至少映射到一个机器mj上并满足这个任务的所有约束条件计算周期，结构和最后期限。2）截止日期限制T也要得到满足。假定在机器mi上执行任务ti所需的计算周期数是一个有限正数，记为Cij 。在恒速Sij下的执行时间，记为周期每秒。对于给定的数据和任务指令，我们假定处理器总是从初级数据高速缓存进行检索。任务ti在机器mj上执行产生的瞬时功率记为Pij 。降低瞬时功率会降低CPU频率，因此会导致CPU速度的降低而可能使得任务ti不能满足最终期限的限制。为了简便起见，假定切换开销和CPU频率小到可以忽略不计。每一个任务结构要求可以看做是一个元祖的每一个的每个元素的特定要求，例如，1）任务执行所要求的处理器是怎样的？2）任务和机器匹配的结构亲和程度。我们假设结构要求的映射是一个布尔运算。就是说结构映射当且仅当所有的结构限制都满足时才得到满足，否则就不满足。3.3 公式化最小-最小-最大问题给出一个计算网格和一个元任务T。找出任务和机器的映射，1）计算网格的累计瞬时功率降到最低2）元任务T的完工时间也最小化。以数学公式可以表示如下：最小化 并且最小化约束条件（4）是映射约束，其中，任务ti映射于机器mj。约束条件（5）体现了映射要求的结构条件，说明了只有结构映射成功时任务和机器之间的映射才存在。约束条件（6）和每一个任务的需要满足的最后期限有关，约束条件（7）说明最后期限和任务执行实际时间的布尔关系。约束条件（8）说明了当且仅当所有任务di（i=1,2，n）的最后期限都得到满足时元任务的最后期限才会有所保证。3.4 示例方案4 合作博弈理论的基本知识合作博弈。假设有m个竞争者。是竞争者j（j=1,2，,m）的目标函数。是一个从X到R的函数，是一个非空闭合的凸集。6 模拟实验，结果和讨论我们使用真实的任务组来模拟研究（后面有相关的讲述）。我们为模拟研究设置了两大目标：1）衡量和比较NBS-EATA和最优解，贪婪和线性松弛启发式理论的性能。2）测量发生变化（比如工作量地增加）对系统变量的影响。我们选择和贪婪启发式理论以及线性松弛启发式理论作比较是因为他们和其他启发式理论相比较表现出极好的性能。现在，我们简单描述一下这两种技术。贪婪启发式。贪婪启发式理论是高引用Min-Min启发式理论的延伸4。修改后的理论使得系统的能量消耗最小化。初始化一个为分派任务集U。第一步，对于每一个为分派任务，启发式理论找到可以消耗最小能量执行这个任务的机器。第二步，从第一步中找出的（任务，机器）对中选择消耗能量最小的对。所选对的任务排队等待所选对的机器执行。执行后从集合U中删除这个任务并继续进行第一步。线性松弛启发式。线性松弛启发式理论的输入是一般指派问题（GAP)而输出机器匹配的任务。LR启发式的基本理论在于把匹配任务看做是一棵树的查找结构（多一条边地树，多出的边可以是空闲的边，形成一个环）。查找是在任务和机器的二分图上完成的。LR开始于一对二分图结点的匹配。然后继续增加另一个单一的任务到机器映射中并且改变现有的所有映射以找到一个可行的任务和机器映射以消耗最少量地能量。由于LR的输入是一个GAP(我们的EATA问题也是GAP规划)，能量限制和其他限制都自动考虑。基于问题的大小，模拟被分成两部分。对于小型问题，我们使用一种整数线性规划工具LINDO22，LINDO对于小型问题最优解问题很有效。因此，对于小型问题，NBS-EATA，贪婪和LR技术的相对性能和LINDO相比较。而对于大型问题，利用LINDO来计算最优解决方案变得很不实际。因此，我们只考虑和贪婪以及LR启发式之间的比较。7 结论本文提出了一种计