Profit-driven uniprocessor scheduling with energy and timing constraints

ABSTRACT

Energy-aware scheduling has received much attention in recent years, especially for systems with serious considerations on energy consumption. While most previous work focuses on the minimization of energy consumption, this paper exploits the maximization of the entire system profit under energy and timing constraints. We propose a greedy approximation algorithm with a 2-approximation ratio. A fully polynomial time approximation scheme (FPTAS) is also proposed, which is an optimal approximation algorithm unless P = NP. For each specified amount of error tolerant to users, the approximation algorithm could provide trade-offs among the specified error, the running time, the approximation ratio, and the memory space complexity. It provides ways for system engineers to trade performance with implementation constraints.

REFERENCES

• 1: A. Chandrakasan, S. Sheng, and R. Broderson. Lower-power CMOS digital design. IEEE Journal of Solid-State Circuit, 27(4):473--484, 1992.
• 2: X. Fan, C. S. Ellis, and A. R. Lebeck. Synergy between power-aware memory systems and processor voltage scaling. Technical report, Duke University, November 2002.
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Gene H. Golub , James M. Ortega, Scientific Computing and Differential Equations: An Introduction to Numerical Methods, Academic Press, Inc., Orlando, FL, 1991
• 5: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 6: S. Irani , R. Gupta , S. Shukla, Competitive Analysis of Dynamic Power Management Strategies for Systems with Multiple Power Savings States, Proceedings of the conference on Design, automation and test in Europe, p.117, March 04-08, 2002
• 7: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 9: Gang Qu, What is the limit of energy saving by dynamic voltage scaling?, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 10: Cosmin Rusu , Rami Melhem , Daniel Mossé, Maximizing the System Value while Satisfying Time and Energy Constraints, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.246, December 03-05, 2002
• 11: Marcus T. Schmitz , Bashir M. Al-Hashimi, Considering power variations of DVS processing elements for energy minimisation in distributed systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500060]
• 12: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 13: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Proceedings of Symposium on Operating Systems Design and Implementation, pages 13--23, 1994.
• 14: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995
• 15: Dakai Zhu , Rami Melhem , Bruce Childers, Scheduling with Dynamic Voltage/Speed Adjustment Using Slack Reclamation in Multi-Processor Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.84, December 03-06, 2001

INDEX TERMS

Keywords:
embedded systems, energy-aware scheduling, power management, real-time process scheduling