1、Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems,Wanghong Yuan, Klara Nahrstedt Department of Computer Science University of Illinois at Urbana-Champaign,Mobile Multimedia Devices,Challenges Manage resources to save energy while supporting multimedia quality CPUOpportunit
2、ies Dynamic frequency/voltage scaling (DVS) Applications release job periodically and meet deadline statistically (e.g., 95%),GRACE-OS,Enhanced CPU scheduler Soft real-time scheduling + DVS Which application, when, how long, how fast Stochastic scheduling decisions Minimize energy while supporting q
3、uality,Architecture,CPU,monitoring,scheduling,speed scaling,demand distribution,GRACE-OS,SRT Scheduler,Speed Adaptor,Profiler,Multimedia Applications,stochastic requirements,time constraint,Three Subproblems,Profiler: demand prediction Basis for scheduling and DVS SRT scheduler: stochastic schedulin
4、g Which app, when, and how long to executeSpeed adaptor: stochastic DVS How fast to execute,Demand Prediction,Online profiling and estimation 1. Count number of cycles used by each job 2. Group and count occurrence frequency,Cmin=b0,br=Cmax,1,br-1,cumulative probability,CDF F(x) = P X x,Observations
5、,Demand distribution is stable or changes slowly,Three Subproblems,1. Profiler: demand prediction Basis for scheduling and DVS 2. SRT scheduler: stochastic scheduling Which app to execute, when, and how long3. Speed adaptor: stochastic DVS How fast to execute,Stochastic Allocation,How many cycles to
6、 allocate per job? Application requires percent of deadlines Each job meets deadline with probability Allocate C cycles, such that F(C)=PXC ,Scheduling,Earliest deadline first (EDF) scheduling Allocate cycle budget per job Execute job with earliest deadline and +budget Charge budget by number of cyc
7、les consumed Preempt if budget is exhaustedWhich job to execute, when, how long,Three Subproblems,1. Profiler: demand prediction Basis for scheduling and DVS 2. SRT scheduler: stochastic scheduling Which app to execute, when, and how long3. Speed adaptor: stochastic DVS How fast to execute,How Fast
8、?,Intuitively, uniform speed Minimum energy if use the allocated exactly However, jobs use cycles statistically Often complete before using up the allocated Potential to save more energy Stochastic DVS,Stochastic DVS,For each job Allocate timeFind speed Sx for each allocated cycle x Time is 1/Sx and
9、 energy is (1 - F(x)S2x,such that,Speed Schedule,Piece-wise approximation Uniform speed within group Change speed at group boundaries, b0,bk Speed schedule List of points (cycle bi, speed Sbi)Change speed to Sbi at bi cycles,Example,0 100 MHz,1 x 106 200 MHz,2 x 106 400 MHz,cycle: speed:,Three Subpr
10、oblems,1. Profiler: demand prediction Basis for scheduling and DVS 2. SRT scheduler: stochastic scheduling Which app to execute, when, and how long3. Speed adaptor: stochastic DVS How fast to execute,SRT + DVS,speed,A1,A1,execution,speed up within job,context switch Store speed for switched-out New
11、speed for switched-in,new job,A2,Implementation,Hardware: HP N5470 laptop Athlon CPU (300, 500, 600, 700, 800, 1000MHz) Round speed schedule to upper boundGRACE-OS: extension to Linux kernel 2.4.18 716 lines of C code,process controlblock,standard Linux scheduler,SRT-DVS modulesPowerNow speed scalin
12、gSoft real-time scheduling,system call,Evaluation,Compare GRACE-OS with schemes performing deterministic allocation or DVS,Metrics,Quality evaluation Deadline miss ratio Applications require to meet 95%Energy evaluation CPU time distribution at speeds Flautner02 More time in low speeds betterNormali
13、zed energy,GRACE-OS consumes least energy However, limited due to few speed options,Normalized Energy,Time Distribution (concurrent run),GRACE-OS spends most busy time at lowest,GRACE-OS bounds miss ratio,Deadline Miss Ratio,Conclusion,GRACE-OS Energy-efficient soft real-time scheduler Lessons Effec
14、tive for multimedia applications Periodic with stable demand distribution Limited by few speed optionsFuture work Extension to manage network bandwidth GRACE http:/rsim.cs.uiuc.edu/grace,Backup,speed,1,t,2t,deadline,E = p(1) x t = t,1/2,t,2t,deadline,E = p(1/2) x 2t = (1/2)3 x 2t= t/4,Power P(s) s3 Energy E(s) s2,
