David Tam Winnie Tsang Catalin Drula CSC2228 Project - First Progress Report Dynamic Voltage Scaling in PDA Devices ====================================== October 14, 2003 Project Web Page: http://www.eecg.toronto.edu/~tamda/csc2228/ 1.0 Problems Encountered ==================== We could not find any commercial PDA device that supports dynamic voltage scaling. While most PDAs have CPUs that can scale their frequency, none of the architectures we have looked seem to have support for changing the voltage level, or at least it is not documented. We believe this is due to the requirement for system board level support for a variety of voltages, which is a feature that handheld-computer manufacturers do not seem to focus on as of yet. Other projects that focused on measuring energy savings due to DVS on real platforms had to design custom boards which seems to confirm our assertion above. The LART project [3] uses a StrongARM 1100 processor embedded on a custom-designed board to allow for different voltage levels. Grunwald et al. [4] had to modify the Itsy Pocket Computer to support two different voltage levels. We looked at a number of PDAs based on the Intel XScale CPU since it allows for voltage ranges of 0.9 to 1.7 volts (and frequency ranges of 100 - 400 MHz). However, we found that none of these PDA devices seem to exploit its dynamic voltage scaling capability. Indeed, for this processor also, custom boards have to be designed for varying the voltage level [5]. 1.1 Solution -------- Therefore, as a compromise, we have decided to make use of Catalin's laptop instead since it supports dynamic voltage scaling. It is a Mobile Intel Pentium 4 - M with Enhanced SpeedStep and thus it supports two voltage/frequency settings (shown below, with the corresponding power consumption): 1.60 GHz 1.30 V 30.0 W 1.20 GHz 1.20 V 20.8 W We are fairly confident that our work will still be relevant. For example, although Yuan et al. [1] have recently examined DVS algorithms and performance on a laptop device, their approach is slightly different from ours. First of all, they added soft-real time scheduling to the core OS while we plan to make no significant changes to the scheduler. Second, their modifications are based on an older kernel version (2.4), while we plan to make use of a new voltage/frequency scaling API proposed in the almost-released 2.6 kernel. Their changes are much more sophisticated (and complex) whereas we are attempting a slightly simpler and non-invasive approach (by not modifying the core behaviour of the scheduler). And not least, in the process, it is possible that our work will become a contribution to the Linux kernel since there are currently no "dynamic" voltage/frequency "governors" written for the new Linux voltage/frequency scaling API. Third, they used a laptop with a much larger range of voltage scaling (AMD PowerNow: 32 voltage steps from 0.925 to 2.00 V), thus making it easier to achieve energy savings. We will be using the Intel SpeedStep technology that supports only 2 voltage steps, making it a more challenging task (for better or worse). 2.0 Progress Summary ================ We have dedicated our effort to researching in the following areas: 1) Existing DVS algorithms for implementation 2) LINUX: CPUFreq governor 3) LINUX: OS scheduler In the following sections, we will give a detailed description for each of the above areas. 2.1 DVS Algorithms -------------- We got familiar with a variety of DVS algorithms and the required information needed from the OS scheduler. Research into DVS algorithms can be divided into two categories: ones that attempt to estimate the future utilization of the processor based on past information, and others that use task deadlines to guide performance-setting decisions. The disadvantage of the former is its unresponsiveness to dynamic changing workloads, but arguably simpler in their implementation. Initially, we planned to implement a few commonly used ones to compare their performance, namely, PAST, PEAK, and FLAT [2]. If time permits, we will further investigate to improve upon these algorithms for better prediction and smoothing of future workload. 2.2 Linux CPUFreq API ----------------- CPUFreq [6] is an on-going project for implementing clock and voltage scaling in the Linux kernel. It consists of three components: the core, the cpu drivers and the cpu governors. The CPUFreq core offers a standardized interface to CPUFreq drivers (architecture-specific code) and notifiers (parts of the kernel or device drivers that need to be informed about frequency changes). The CPUFreq drivers implement the generic API for a particular CPU/chipset. A CPUFreq governor is the component that makes decisions about when and how voltage/frequency should be changed (i.e. they implement the various DVS algorithms). By abstracting the CPU hardware into drivers, this API allows any governor to be used with any architecture. This allows for easy experimentation with different CPU technologies. For example, the effectiveness of a DVS algorithm can be evaluated on Intel, AMD, and Crusoe platforms by simply swapping the drivers. In fact, if in the future PDAs with the Intel XScale will have support for DVS at the board level we could obtain such a PDA, install Linux and simply run our experiments to determine effectiveness. We talked to the Linux developers who are involved with dynamic voltage/frequency scaling to determine the feasibility of our DVS project. They have been very supportive [7] and encouraged us to pursue the writing of an intelligent "dynamic" governor. So far there are only two simplistic governors, one that sets the speed to the maximum available and one that sets it to the minimum. 2.3 Linux OS Scheduler ------------------ We got familiar with the Linux scheduler code and associated data structures. We have a good idea of where to make additions to obtain information need by the DVS algorithms. The main source code files that were examined are kernel/sched.c and include/sched.h. These two files constitute the OS scheduler. The task_struct data structure is the process descriptor (aka Process Control Block) and contains per process data. The main scheduling function is schedule(). Since our modifications do not involve altering the core functionality of the scheduler, we believe our task should be straightforward. Upon a task switch, we want to do a bit of accounting work and send the resulting information to the voltage/frequency "governor". We will not be altering scheduling decisions made by the scheduler. In summary, we simply want to listen in on the scheduler in order relay information to the governor. We have been trying to determine the common pieces of information required by all DVS algorithms. That way, we can extract these pieces of information from the OS scheduler and present it to any/all DVS algorithms. We believe that some of the important data can be obtained from the following fields in the task_struct data structure of each task: sleep_avg, timestamp, time_slice, and first_time_slice. 3.0 Left To Do ========== We appear to be mostly on track with our original proposed schedule. We need to follow the rest of our milestones. 3.1 Milestones ---------- * Sept 23 - Oct 21 (Week 1 - 4) o Research the purchase of a PDA capable of dynamic voltage scaling. Nevermind! Using a laptop with DVS support instead. o Install LINUX on the laptop and get familiar with the OS scheduler. o First progress report (Oct 14) * Oct 21 - Nov 18 (Week 4 - 8) o Determine and test suitable laptop application workloads. o Implement 3 to 4 DVS algorithms in the OS scheduler. o Test & debug the system o Second progress report (Nov 11) * Nov 18 - Nov 25 (Week 8 - 9) o Run experiments, collect, evaluate, analyze results. * Nov 25 - Dec 15 (Week 9 -11) o Presentation (Dec 2) o Final Report (Dec 15) References ========== [1] Wanghong Yuan, Klara Nahrstedt, "Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems", SOSP 2003. http://www.cs.rochester.edu/sosp2003/papers/p168-yuan.pdf [2] Kinshuk Govil, Edwin Chan, Hal Wasserman, "Comparing Algorithms for Dynamic Speed-Setting of a Low-Power CPU", In Proceedings of the First ACM International Conference on Mobile Computing and Networking (MOBICOM 95), pages 13-25, November 1995. http://www-flash.stanford.edu/~kinshuk/MCN95.ps [3] LART clock and voltage scaling project - Delft University of Technology, Netherlands. http://www.lart.tudelft.nl/projects/scaling/ [4] Dirk Grunwald, Philip Levis, Keith I. Farkas, Charles B. Morrey III, Michael Neufeld, "Policies for dynamic clock scheduling", In Proceedings of the Forth Symposium on Operating System Design and Implementation OSDI'2000, October 2000. http://www.usenix.org/events/osdi2000/full_papers/grunwald/grunwald.pdf [5] Voltage Scaling Hardware for Intel Xscale 80200 Evaluation Platform http://www.ee.ucla.edu/~shalabh/pads/vscaling.html [6] Linux CPUFreq ftp site to obtain latest source code. ftp://ftp.linux.org.uk/pub/linux/cpufreq/ [7] Email reply from Alex Brodowski regarding DVS on PDAs. http://www.eecg.toronto.edu/~tamda/csc2228/email_brodowski.txt