cars , love and music

cars , love and music

beauty of tropical trees

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 classification. 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 energyefficient 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 fixed-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-fidelity 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 fixed 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 finishes 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 finishes earlier, we increase F C further with the slack cycles δ defined 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 find a new speed in the range constrained by ACF and SC. When defining the new speed, we can look ahead at any number of future ACF step points to find 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 fixed number of ACF points and assign a constant speed to the new speed.more than three points in the example because we cannot find 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 defined 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 define 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 significant 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 definition of P depends on the specific hardware. We shall not assume any fixed 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.