Algorithmic Issues in Power Management by Speed Scaling (APM)

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.