Achieving utility arbitrarily close to the optimal with limited energy

ABSTRACT

Energy is one of the limited resources for modern systems, especially the battery-operated devices and personal digital assistants. The backlog in new technologies for more powerful battery is changing the traditional system design philosophies. For example, due to the limitation on battery life, it is more realistic to design for the optimal benefit from limited resource rather than design to meet all the applications' requirement. We consider the following problem: a system achieves a certain amount of utility from a set of applications by providing them certain levels of quality of service(QoS). We want to allocate the limited system resources to get the maximal system utility. We formulate this utility maximization problem, which is NP-hard in general, and propose heuristic algorithms that are capable of finding solutions provably arbitrarily close to the optimal. We have also derived explicit formulae to guide the allocation of resources to actually achieve such solutions. Simulation shows that our approach can use 99.9% of the given resource to achieve 25.6% and 32.17% more system utilities over two other heuristics, while providing QoS guarantees to the application program.

REFERENCES

• 1: T.D. Burd, T. Pering, A. Stratakos, and R. Brodersen. A Dynamic Voltage-Scaled Microprocessor System. IEEE International Solid-State Circuits Conference, February, 2000.
• 2: A. Chandrakasan , V. Gutnik , T. Xanthopoulos, Data driven signal processing: an approach for energy efficient computing, Proceedings of the 1996 international symposium on Low power electronics and design, p.347-352, August 12-14, 1996, Monterey, California, United States
• 3: R.L. Cruz. Quality of Service Guarantees in Virtual Circuit Switched Networks. IEEE Journal on Selected Areas in Communications, Vol.13, No.6, pp. 1048-1056, August 1995.
• 4: Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
• 5: I. Hong , G. Qu , M. Potkonjak , M. B. Srivastava, Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors, Proceedings of the IEEE Real-Time Systems Symposium, p.178, December 02-04, 1998
• 6: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 7: E. Macii, M. Pedram, and F. Somenzi. High-Level Power Modeling, Estimation, and Optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.17, No.ll, pp. 1061-1079, November 1998.
• 8: W. Namgoong, M. Yu, T. Meng. A high-efficiency variable-voltage CMOS dynamic dc-dc switching regulator. IEEE International Solid-State Circuits Conference Digest of Technical Papers, pp. 380-381, 489, February 1997.
• 9: Gang Qu , Malena Mesarina , Miodrag Potkonjak, System Synthesis of Synchronous Multimedia Applications, Proceedings of the 12th international symposium on System synthesis, p.128, November 01-04, 1999
• 10: R. Rajkumar , C. Lee , J. Lehoczky , D. Siewiorek, A resource allocation model for QoS management, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.298, December 03-05, 1997
• 11: R. Rajkumar , C. Lee , J. P. Lehoczky , D. P. Siewiorek, Practical Solutions for QoS-Based Resource Allocation, Proceedings of the IEEE Real-Time Systems Symposium, p.296, December 02-04, 1998
• 12: Scheduling for quality of service guarantees via service curves, Proceedings of the 4th International Conference on Computer Communications and Networks, p.512, September 20-23, 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Performance