Cars Love Music: February 2013

Sunday, February 24, 2013

Sunday, February 17, 2013

Saturday, February 16, 2013

WHAT MUST WE READ TO KNOW MORE ABOUT WIRELESS AND PORTABLE DEVICES?

[1] H. Aydin, R. Melhem, and D. Mosse. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Euromicro Conference on RealTime Systems, Delft, The Netherlands, June 2001. [2] H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Alvarez. Dynamic and aggressive scheduling techniques for poweraware real-time systems. In Real-time System Symposium, London, UK, Dec. 2001. [3] R. Ernst and W. Ye. Embedded program timing analysis based on path clustering and architecture classiﬁcation. In Internatioal Conference on Computer Aided Design, San Jose, CA, Nov. 1997. [4] K. Govil, E. Chan, and H. Wasserman. Comparing algorithms for dynamic speed-setting of a low-power CPU. In International Conference on Mobile Computing and Networking, Berkeley, CA, Nov. 1995. [5] F. Gruian. Hard real-time scheduling using stochastic data and DVS processors. In International Symposium on Low Power Electronic and Design, Huntington Beach, CA, Aug. 2001. [6] F. Gruian and K. Kuchcinski. Lenes: Task scheduling for low-energy systems using variable supply voltage processors. In International Symposium on Low Power Electronic and Design, Huntington Beach, CA, Aug. 2001. [7] D. Grunwald, P. Levis, K. I. Farkas, C. B. Morrey III, and M. Neufeld. Policies for dynamic clock scheduling. In Symposium on Operating Systems’ Design and Implementation, San Diego, CA, Oct. 2000. [8] I. Hong, D. Kirovshi, G. Qu, M. Potkonjak, and M. B. Srivastava. Power optimization of variable voltage core-based systems. In Design Automation Conference, San Francico, CA, June 1998. [9] I. Hong, M. Potkonjak, and M. B. Srivastava. On-line scheduling of hard real-time tasks on variable voltage processors. In International Conference on Computer-Aided Design, San Jose, CA, Nov. 1998. [10] I. Hong, G. Qu, M. Potkonjak, and M. B. Srivastava. Synthesis techniques for low-power hard real-time systems on variable voltage processors. In Real-time System Symposium, Madrid, Spain, Dec. 1998. [11] D.-I. Kang, S. Crago, and J. Suh. Power-aware design synthesis techniques for distributed real-time systems. In ACM Workshop on Languages, Compilers, and Tools for Embedded Systems, Snowbird, UT, June 2001 [12] D.-I. Kang, S. Crago, and J. Suh. Technique for energyefﬁcient real-time systems. In Real-time System Symposium, Austin, TX, Dec. 2002. [13] J. P. Lehoczky and S. Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in ﬁxed-priority preemptive systems. In Real-time System Symposium, Phoenix, AR, Dec. 1992. [14] J. W. S. Liu. Real-time Systems. Prentice Hall, 2000. [15] Y. Liu and A. Mok. An integrated approach for applying dynamic voltage scaling to real-time systems. Technical Report TR-03-YBL-01, University of Texas at Austin, Mar. 2003. [16] J. Lorch and A. J. Smith. Improving dynamic voltage scaling algorithms with PACE. In Joint International Conference on Measurement and Modeling of Computer Systems, Cambridge, MA, June 2001. [17] T. Pering, T. Burd, and R. W. Brodersen. The simulation and evaluation of dynamic voltage scaling algorithm. In International Symposium on Low Power Electronic and Design, Monterey, CA, Aug. 1998. [18] P. Pillai and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In ACM symposium on operating systems principles, Banff, Canada, Oct. 2001. [19] V. Raghunathan, P. Spanos, and M. Srivastava. Adaptive power-ﬁdelity in energy-aware wireless embedded systems. In Real-time System Symposium, London, UK, Dec. 2001. [20] C. Rusu, R. Melhem, and D. Mosse. Maximizing the system value while satisfying time and energy consumption. In Real-time System Symposium, Austin, TX, Dec. 2002. [21] Y. Shin and K. Choi. Power conscious ﬁxed priority scheduling for hard real-time systems. In Design Automation Conference, New Orleans, LA, June 1999. [22] M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Symposium on Operating Systems’ Design and Implementation, Monterey, CA, Nov. 1994. [23] F. Yao, A. Demers, and S.Shenker. A scheduling model for reduced CPU energy. In Symposium on Foundations of Computer Science, Milwaukee, WI, Oct. 1995. [24] F. Zhang and S. Chanson. Processor voltage scheduling for real-time tasks with non-preemptible sections. In Real-time System Symposium, Austin, TX, Dec. 2002. [25] D. Zhu, R. Melhem, and B. Childers. Scheduling with dynamic voltage/speed adjustment using slack reclamation in mutli-processor real-time systems. In Real-time System Symposium, London, UK, Dec. 2001

Online Reclaim Algorithm

The off-line algorithm is based on the worse-case budget. At runtime, slack cycles are generated if a job uses less than the worst-case budget. We can easily adopt our technique to reclaim slack cycles. The idea is that, when a job ﬁnishes with δ less cycles compared with the static schedule at time t, this can be interpreted as if t 0 S(x)dx is increased by δ. Beginning at time t, we have the same speed optimization problem with ACF and RCF constraints. In other words, a new optimal solution can be found at any time during run time. Based on the off-line speed function, faster algorithms can be used online. We propose such an algorithm which has time complexity O First, we need to save some additional information: the current speed which may be different from the off-line speed, the accumulated cycles F C up to the curren time and SC which is the accumulated cycles calculated from the off-line speed function. The algorithm follows the off-line speed function and updates the information at each scheduling point; we use scheduling point to refer to any time when a job becomes available, is completed, or is preempted. Normally, F C is increased by the CPU cycles supplied at the current speed. However, when a job ﬁnishes earlier, we increase F C further with the slack cycles δ deﬁned above. Thus, F C − SC represents the slack cycles at current time t0. At this point ACF(t0) ≥ F C still holds. If F C > SC, we reduce CPU speed so that F C will approach SC. Once F C = SC again, we can follow the off-line speed function from then on. Since we keep F C ≥ SC all the time and SC ≥ RF C, no job will miss its deadline as long as we keep ACF ≥ F C. Note that the online algorithm tries to ﬁnd a new speed in the range constrained by ACF and SC. When deﬁning the new speed, we can look ahead at any number of future ACF step points to ﬁnd a new speed. The more ACF points we check, the smoother the new speed is and the more energy is saved. If we check all ACF points up to the end of a hyper period, we have the optimal solution. This is a trade-off between runtime cost and energy savings. To keep the runtime cost constant, we look at a ﬁxed number of ACF points and assign a constant speed to the new speed.more than three points in the example because we cannot ﬁnd a constant new speed that causes no extra idle cycles. To our best knowledge, we note that in previous research, a reclaim algorithm can look ahead only one task period. Our method has no such limit, hence more energy reduction can be achieved by our approach. Also note that our algorithm reclaims slack cycles from multiple jobs of different task. Our algorithm depends on ACF and a off-line speed function. Besides the optimal speed function, it applies to any valid speed function deﬁned off-line, including what we call the speculative speed function [

Wireless and portable devices

Wireless and portable devices depend on the limited power supplied by the battery. Dynamic Voltage Scaling (DVS) is an effective method to reduce CPU power consumption. For real-time systems, DVS algorithms must not only provide enough CPU cycles, but also guarantee that no job misses its deadline. In this paper, we propose an integrated approach for applying DVS to real-time systems. We deﬁne two functions, the available cycle function (ACF) and the required cycle function (RCF), to capture the CPU workload of the real-time tasks. We then formulate the DVS scheduling problem for real-time systems as a nonlinear optimization problem and propose an optimal off-line algorithm to solve this problem. We also propose a novel online algorithm with time complexity O(1) to further reduce power consumption when a job uses fewer execution cycles than the worst-case budget. The algorithms in this paper are based solely on ACF and RCF, and may be applied to different scheduling policies. We illustrate the generality of our approach over previous research by applying our method to EDF and RM scheduling policies and deriving the optimal off-line DVS algorithms for them. Our simulation results show signiﬁcant improvement over previous work

Processor Model

We assume the processor can change its voltage continuously. In other words, a processor can operate at any normalized speed from 0 to 1. When the speed is 0, the processor is in shutdown mode. We shall ignore the speed switching overhead which in general is small [18]. From the Introduction section, we note that P, the power consumed per CPU cycle is proportional to V 2 f, and f is proportional to (V −Vt) 2 /V , where V is the supply voltage, f the frequency, and Vt the voltage threshold. The exact deﬁnition of P depends on the speciﬁc hardware. We shall not assume any ﬁxed form for P, except that it is a strictly convex function of the frequency. We use P(S) to denote that P is a function of speed S.

WIRELESS AND PORTABLE DEVICES DEPEND ON???

Many wireless and portable devices depend on the limited power supplied by the battery. Dynamic voltage scaling (DVS) is an effective method to increase battery life by reducing the power consumption of a processor. Speciﬁcally, DVS reduces the energy consumption of a CMOS processor by dynamically controlling its supply voltage. The power consumed per CPU cycle can be expressed as P = kCV 2 f, where k is a constant, C the total capacitance of wires and transistor gates, V the supply voltage, and f the clock frequency. DVS technology has already been incorporated into many processors produced by companies including Transmeta, AMD, and Intel. Changing a processor’s supply voltage also changes its speed, since the relationship between clock frequency and supply voltage is f ∝ (V − Vt) 2 /V , where Vt is the threshold voltage. As a result, DVS may hurt the performance of some systems in a signiﬁcant way, in particular, real-time systems where some deadlines are hard. In past work, many algorithms have been proposed to apply DVS to general purpose and soft real-time systems only, Applying DVS to hard real-time systems is more difﬁ- cult. When a DVS algorithm reduces CPU speed to save energy, it must guarantee that all jobs still meet their deadlines. In the past few years, a large number of algorithms are proposed, e.g., [23, 8, 9, 10, 21, 1, 11, 5, 6, 18, 19, 25, 12, 20, 24]. Although these algorithms have demonstrated the beneﬁts of applying DVS to hard real-time systems, they generally only apply to some speciﬁc real-time scheduler. There has not been any algorithm designed to work with different real-time schedulers. The objective of this paper is to propose an integrated approach for applying DVS to hard real-time systems. Using this approach, we derive uniﬁed algorithms that work with different real-time schedulers. We illustrate the generality of the approach by applying it to RM and EDF schedulers; we shall derive the optimal off-line DVS algorithms for these real-time scheduling policies. Speciﬁcally, we shall propose the deﬁnition of two functions: the available cycle function (ACF) and the required cycle function (RCF). The values of these two functions are derived from the parameters of the task set and the scheduling policy used to dispatch the tasks of the system. These functions help us to capture the workload of a real-time system by characterizing an envelope: they constrain the range of a speed function so that if the CPU executes at the speed deﬁned by the function, then there is no idle cycle and no job misses its deadline. Using ACF and RCF, we formulate the energy minimization problem as a constrained nonlinear optimization problem. We prove that for strictly convex power functions, which are the case for all known power models, we can simplify the formulation of the problem. We propose an algorithm to solve the problem and to derive the optimal speed function that minimizes energy consumption. The algorithm is shown to work with both EDF and RM. Since the static algorithm is based on the worst-case budget, we also propose a novel, online, dynamic algorithm to reclaim slack cycles which are generated by early completion of jobs; by a job, we mean an instance of a recurring task (periodic or otherwise) in a schedule. The dynamic algorithm lowers CPU speed whenever slack cycles are available; the new speed will not cause any missed deadline or extra idle cycles. The time complexity of the algorithm is O(1). Furthermore, the algorithm may trade runtime cost for energy savings. It can be improved, with added complexity so that an optimal CPU speed solution is always found at any time. Again, the dynamic algorithm works with both EDF and RM.