Energy-efficient soft real-time CPU scheduling for mobile multimedia systems

ABSTRACT

This paper presents GRACE-OS, an energy-efficient soft real-time CPU scheduler for mobile devices that primarily run multimedia applications. The major goal of GRACE-OS is to support application quality of service and save energy. To achieve this goal, GRACE-OS integrates dynamic voltage scaling into soft real-time scheduling and decides how fast to execute applications in addition to when and how long to execute them. GRACE-OS makes such scheduling decisions based on the probability distribution of application cycle demands, and obtains the demand distribution via online profiling and estimation. We have implemented GRACE-OS in the Linux kernel and evaluated it on an HP laptop with a variable-speed CPU and multimedia codecs. Our experimental results show that (1) the demand distribution of the studied codecs is stable or changes smoothly. This stability implies that it is feasible to perform stochastic scheduling and voltage scaling with low overhead; (2) GRACE-OS delivers soft performance guarantees by bounding the deadline miss ratio under application-specific requirements; and (3) GRACE-OS reduces CPU idle time and spends more busy time in lower-power speeds. Our measurement indicates that compared to deterministic scheduling and voltage scaling, GRACE-OS saves energy by 7% to 72% while delivering statistical performance guarantees.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Adve and et al. The Illinois GRACE Project: Global Resource Adaptation through CoopEration. In Proc. of Workshop on Self-Healing, Adaptive and self-MANaged Systems, June 2002.
	2	AMD. Mobile AMD Athlon 4 processor model 6 CPGA data sheet. http://www.amd.com, Nov. 2001.
	3	Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
	4	Mohit Aron , Peter Druschel, Soft timers: efficient microsecond software timer support for network processing, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.232-246, December 12-15, 1999, Charleston, South Carolina, United States
	5	Hakan Aydi , Pedro Mejía-Alvarez , Daniel Mossé , Rami Melhem, Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.95, December 03-06, 2001
	6	Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
	7	A. Chandra, M. Adler, P. Goyal, and P. Shenoy. Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In Proc. of 4th Symposium on Operating System Design and Implementation, Oct. 2000.
	8	A. Chandrakasan, S. Sheng, and R. W. Brodersen. Low-power CMOS digital design. IEEE Journal of Solid-State Circuits, 27:473--484, Apr. 1992.
	9	Kenneth J. Duda , David R. Cheriton, Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.261-276, December 12-15, 1999, Charleston, South Carolina, United States
	10	Krisztián Flautner , Trevor Mudge, Vertigo: automatic performance-setting for Linux, Proceedings of the 5th symposium on Operating systems design and implementation Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060300]
	11	Jason Flinn , M. Satyanarayanan, PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.2, February 25-26, 1999
	12	Mark K. Gardner , Jane W. Liu, Probabilistic analysis and scheduling of critical soft real-time systems, 1999
	13	Pawan Goyal , Xingang Guo , Harrick M. Vin, A hierarchial CPU scheduler for multimedia operating systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.107-121, October 29-November 01, 1996, Seattle, Washington, United States
	14	Flavius Gruian, Hard real-time scheduling for low-energy using stochastic data and DVS processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.46-51, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383092]
	15	D. Grunwald, P. Levis, K. Farkas, C. Morrey III, and M. Neufeld. Policies for dynamic clock scheduling. In Proc. of 4th Symposium on Operating System Design and Implementation, Oct. 2000.
	16	Claude-Joachim Hamann , Lars Reuther , Jork Wolter , Hermann Härtig , Jork Löser , Sebastian Schönberg, Quality-Assuring Scheduling-Using Stochastic Behavior to Improve Resource Utilization, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.119, December 03-06, 2001
	17	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]
	18	K. Jeffay , F. D. Smith , A. Moorthy , J. Anderson, Proportional Share Scheduling of Operating System Services for Real-Time Applications, Proceedings of the IEEE Real-Time Systems Symposium, p.480, December 02-04, 1998
	19	Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
	20	S. Krantz, S. Kress, and R. Kress. Jensen's Inequality. Birkhauser, 1999.
	21	KURT. UTIME-- micro-second resolution timers for linux. http://www.ittc.ku.edu/kurt, Mar. 2003.
	22	C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
	23	Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
	24	J. Lorch and A. Smith. Operating system modifications for task-based speed and voltage scheduling. In Proc. of the 1st Intl. Conf. on Mobile Systems, Applications, and Services, May 2003.
	25	Jason Nieh , Monica S. Lam, The design, implementation and evaluation of SMART: a scheduler for multimedia applications, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.184-197, October 05-08, 1997, Saint Malo, France
	26	Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
	27	Trevor Pering , Thomas Burd , Robert Brodersen, Voltage scheduling in the IpARM microprocessor system, Proceedings of the 2000 international symposium on Low power electronics and design, p.96-101, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344530]
	28	Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
	29	R. Rajkumar, K. Juvva, A. Molano, and S. Oikawa. Resource kernels: A resource-centric approach to real-time systems. In Proc. of SPIE Multimedia Computing and Networking Conference, Jan. 1998.
	30	Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
	31	Amit Sinha , Anantha P. Chandrakasan, Dynamic Voltage Scheduling Using Adaptive Filtering of Workload Traces, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.221, January 03-07, 2001
	32	Bhuvan Urgaonkar , Prashant Shenoy , Timothy Roscoe, Resource overbooking and application profiling in shared hosting platforms, Proceedings of the 5th symposium on Operating systems design and implementation Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060312]
	33	Shengquan Wang , Dong Xuan , Riccardo Bettati , Wei Zhao, Differentiated Services with Statistical Real-Time Guarantees in Static-Priority Scheduling Networks, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.289, December 03-06, 2001
	34	M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Proc. of Symposium on Operating Systems Design and Implementation, Nov. 1994.
	35	Wanghong Yuan , Klara Nahrstedt, Integration of dynamic voltage scaling and soft real-time scheduling for open mobile systems, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507685]
	36	W. Yuan, K. Nahrstedt, S. Adve, D. Jones, and R. Kravets. Design and evaluation of cross-layer adaptation framework for mobile multimedia systems. In Proc. of SPIE Multimedia Computing and Networking Conference, Jan. 2003.
	37	Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.15-26, October 05-08, 1997, Saint Malo, France

Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading