Algorithmic Issues in Power Management by Speed Scaling (APM)

速度调节 (APM) 电源管理中的算法问题

• 批准号: EP/E028276/1
• 负责人: Prudence Wong
• 金额: $ 21.52万
• 依托单位: University of Liverpool
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2007
• 资助国家: 英国
• 起止时间: 2007 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FE028276%2F1
• 关键词: Algorithmic; Issues; Power; Management; Speed

New technologies for mobile devices like 3G and Wi-Fi has brought new life changing user experiences. However, this development can be hindered by battery life, for instance, using 3G communication can shorten the talk time of mobile phones by up to 75%. Battery capacity is not able to catch up with the continuous growth of power requirements for devices. Furthermore, a large amount of heat is generated by device operation. In general, the more powerful the device is, the more heat is generated. Overheating can damage the life of electronic devices. Therefore, power management has imposed important design constraints on modern computing devices. To reduce energy consumption without sacrificing performance significantly, energy awareness'' becomes a crucial concept: a system should only deliver the required service so as to avoid superfluous energy consumption.Dynamic voltage / speed scaling (DVS) becomes a common technique to manage power consumption, e.g., current processors from AMD, Intel and Transmeta allow the processors to operate at various processor speeds. The motivation of DVS is due to the well known cube-root-rule which states that the power consumed is roughly the cube of the operating speed. Simply having processors that support DVS does not solve the problem because the most important question is How to dynamically adjust the speed of processor to maintain performance with the minimal energy and temperature?'' Although some algorithmic solutions have been proposed, most of them assume that the processor can operate at any (unbounded) speed, which is obviously not the case in practice. Furthermore, the models considered so far optimize either energy or temperature but not both. The current proposal aims at providing algorithmic solutions so as to facilitate more powerful, yet energy effective, devices. Specific objectives include1. developing an accurate abstract model of energy and temperature efficient scheduling,2. designing algorithms with mathematically provable performance guarantees, and3. providing a comprehensive evaluation of the proposed algorithms.The success of this project will impact on extending the battery life of mobile devices thus improving the services (e.g., multimedia) that they can support. The experience of Dr.\ Wong on job scheduling, in particular, her preliminary study on energy efficient deadline scheduling serves as a good foundation and is expected to be crucial for the success of the project.

3G和Wi-Fi等移动设备的新技术带来了改变用户生活的新体验。然而，这种发展可能会受到电池寿命的阻碍，例如，使用3G通信可以缩短手机通话时间高达75%。电池容量已经跟不上设备不断增长的用电需求。此外，设备运行会产生大量的热量。一般来说，设备的功率越大，产生的热量就越多。过热会损害电子设备的寿命。因此，电源管理对现代计算设备施加了重要的设计约束。为了在不显著牺牲性能的情况下降低能耗，“能源意识”成为一个至关重要的概念：系统应该只提供所需的服务，以避免多余的能源消耗。动态电压/速度缩放（DVS）成为管理功耗的常用技术，例如，目前来自AMD、Intel和Transmeta的处理器允许处理器以不同的处理器速度运行。分布式交换机的动机是由于众所周知的立方根法则，即消耗的功率大致是运行速度的立方。简单地拥有支持分布式交换机的处理器并不能解决问题，因为最重要的问题是如何动态调整处理器的速度，以最小的能量和温度保持性能？“虽然已经提出了一些算法解决方案，但大多数都假设处理器可以以任何（无界）速度运行，这在实践中显然不是这样的。此外，目前考虑的模型要么优化能量要么优化温度，但不是两者都优化。目前的提案旨在提供算法解决方案，以促进更强大，更节能的设备。具体目标包括：建立了一种精确的能源和温度高效调度抽象模型；设计具有数学上可证明的性能保证的算法；对所提出的算法进行了全面的评估。该项目的成功将对延长移动设备的电池寿命产生影响，从而改善它们可以支持的服务（例如多媒体）。黄博士在作业调度方面的经验，特别是她在节能截止日期调度方面的初步研究，为项目的成功奠定了良好的基础。

项目成果

Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines

针对任意大小和截止日期的作业的多处理器速度扩展

• DOI: 10.1007/s10878-013-9618-8
• 发表时间: 2013
• 期刊: Journal of Combinatorial Optimization
• 影响因子: 1
• 作者: Bell P

Optimizing throughput and energy in online deadline scheduling

• DOI: 10.1145/1644015.1644025
• 发表时间: 2009-12
• 期刊: ACM Trans. Algorithms
• 作者: H. Chan;W. Chan;T. Lam;Lap-Kei Lee;Kin-Sum Mak;Prudence W. H. Wong

Automata, Languages and Programming

自动机、语言和编程

• DOI: 10.1007/978-3-540-70583-3_9
• 发表时间: 2008
• 作者: Berger M

Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy

基于活动作业计数的在线速度扩展，以最大限度地减少流量和能源

• DOI: 10.1007/s00453-012-9613-y
• 发表时间: 2012
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Lam T

On-line maximum matching in complete multi-partite graphs with an application to optical networks

完整多部分图中的在线最大匹配及其在光网络中的应用

• DOI: 10.1016/j.dam.2014.10.040
• 发表时间: 2016
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Shalom M