Sandy Irani
Sandeep Shukla
Rajesh Gupta
Abstract
This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.
- Bansal, N., Kimbrel, T., and Pruhs, K. 2007. Speed scaling to manage energy and temperature. J. ACM 54, 1, 1. Google Scholar
Digital Library
- Benini, L., Bogliolo, A., and De Micheli, G. 2000. A survey of design techniques for system-level dynamic power management. IEEE Trans. Very Large Scale Integr. Syst. 8, 3, 299--316. Google ScholarDigital Library
- Hong, I., Qu, G., Potkonjak, M., and Srivastava, M. B. 1998. Synthesis techniques for low-power hard real-time systems on variable voltage processors. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). IEEE Computer Society, Washington, DC. 178. Google ScholarDigital Library
- Irani, S., Shukla, S., and Gupta, R. 2003. Online strategies for dynamic power management in systems with multiple power saving states. Trans. Embedded Comput. Syst. 2, 3, 325--346. Google ScholarDigital Library
- Irani, S., and Karlin, A. 1997. Online computation. In Approximation Algorithms for NP-Complete Problems. PWS Publishing, Boston, 521--559. Google ScholarDigital Library
- Ishihara, T., and Yasuura, H. 1998. Voltage scheduling problem for dynamically variable voltage processors. In Proceedings of the International Symposium on Low Power Electronics and Design (ISPLED). ACM Press, New York, 197--202. Google ScholarDigital Library
- Karlin, A., Manasse, M., McGeoch, L., and Owicki, S. 1990. Randomized competitive algorithms for non-uniform problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 301--309. Google ScholarDigital Library
- Keshav, S., Lund, C., Phillips, S., Reingold, N., and Saran, H. 1995. An empirical evaluation of virtual circuit holding time policies in IP-over-ATM networks. IEEE J. Selected Areas Commun. 13, 8, 1371--1382. Google ScholarDigital Library
- Lu, Y.-H., Benini, L., and Micheli, G. D. 2000. Low-Power task scheduling for multiple devices. In Proceedings of the 8th International Workshop on Hardware/Software Codesign (CODES). ACM Press, New York, 39--43. Google ScholarDigital Library
- Quan, G., and Hu, X. 2001. Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors. In Proceedings of the 38th Conference on Design Automation (DAC). ACM Press, New York, 828--833. Google ScholarDigital Library
- Raghunathan, V., Spanos, P., and Srivastava, M. B. 2001. Adaptive power-fidelity in energy-aware wireless embedded systems. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS). IEEE Computer Society, Washington, DC, 106. Google ScholarDigital Library
- Ramanathan, D., Irani, S., and Gupta, R. 2000. Latency effects of system level power management algorithms. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), IEEE Press, Piscataway, NJ, 350--356. Google ScholarDigital Library
- Rockwell Scientific. 2007. http://www.rockwellscientific.com/hidra/.Google Scholar
- Simunic, T. 2001. Energy efficient system design and utilization. Ph.D. thesis, Stanford University. Google ScholarDigital Library
- Srivastava, M., Parker, B., Schott, B., and Chen, C. 2007. Power considerations for sensor network. http://www2.parc.com/spl/projects/cosense/csp/slides/Srivastava.pdf.Google Scholar
- Yao, F., Demers, A., and Shenker, S. 1995. A scheduling model for reduced CPU energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Washington, DC, 374. Google ScholarDigital Library
Index Terms
- Algorithms for power savings
Recommendations
Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of $$s^\alpha $$ s when running at speed $$s$$ s , where $$\alpha \ge 2$$ 2 . The problem is to dispatch jobs to processors and determine the speed and jobs to run for ...
Algorithms for power savings
SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithmsThis paper examines two different mechanisms for saving power in battery-operated embedded systems. The first is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an ...
Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness
It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|rj,...
Comments