|
Athanasios E. Papathanasiou, and Michael L. Scott .
Computer Science Department
Paper Presentation,
5th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'03),
October 9-10, Monterey, California, USA.
|
|
|
Traditional operating systems use resource management policies that smooth out fluctuations in resource demand as a way of improving overall throughput and latency. Although smooth access patterns can improve performance we have found that they can often hurt energy efficiency. In contrast, the deliberate creation of bursty access patterns can decrease energy consumption in several cases, without having a significant negative impact on performance, if implemented carefully. In the remainder of the talk, I will explain how burstiness can improve the energy efficiency of a disk file system. |
|
|
Several important devices, such as hard disks and wireless networks, support low-power modes that can save significant energy if the device is inactive for relatively long periods of time (typically tens of seconds). Failure to remain in the low power state for a sufficient period of time, called the breakeven time period, leads to increased energy consumption due to the cost of returning to the active state. Unfortunately, modern file systems are typically designed to maximize throughput and to minimize I/O latency, not to minimize energy. The result is that even under a light workload, idle times tend to be too short to exploit for energy savings. |
|
|
As an example of file system behavior, consider how the Linux kernel reacts during 5 minutes of mp3 playback. The kernel's conservative prefetching algorithm requests 128KB of data approximately every 8 seconds. The result is that 66% of the total idle time appears in intervals of 8 seconds or less, while only 12% appears in intervals larger than 12 seconds, which is the spin-down breakeven point for a Hitachi disk. This is unfortunate given that the disk's sustainable bandwidth significantly exceeds that required by MP3 playback. During periods of activity the disk is used at less than 1% of its sustainable bandwidth. Despite the extra disk bandwidth we are not able to save energy by powering the disk down for long periods. This type of file system behavior also appears during light write workloads. During a CD copy operation, 92% of the total disk idle time appears in intervals that shorter than 5 seconds. |
|
|
Intuitively, increased system memory should allow the OS to prefetch sequential files more aggressively, allowing the disk to spin down and save energy. But this wouldn t improve performance, so existing kernels don t do it. As an example consider what happens during MPEG playback in Linux. Increasing the system s memory size from 64 to 500MB results in practically no disk energy savings. |
|
|
We believe that a central goal of operating systems used in mobile platforms should be to create a bursty access pattern that increases the average length of idle intervals for devices with low power modes and maximizes the device's utilization when it is active. As shown in the graph a bursty file system gathers multiple requests depending on memory availability and services them periodically in a single disk burst. This significantly increases the total amount of time that the disk can spend in a low-power state, and reduces the number of expensive power-up transitions. |
|
|
In our work we have modified the Linux OS in order to increase the burstiness of disk activity. Our goals are, first, to maximize the length of idle phases by prefetching aggressively and by batching writes. Second, coordinate I/O requests across all running applications, so that they are serviced by the disk within the same small window of time. And finally, hide the possible negative performance impact of increased burstiness and disk power mode transitions through disk preactivation. |
|
|
The key idea behind our energy efficient prefetching and caching mechanism is the introduction of an epoch-based algorithm in the basic memory management system of the Linux kernel. Each epoch consists of two phases: a request generation phase and an idle phase. During the request generation phase the system attempts to load into memory data that are going to be accessed in the near future. For this purpose the total amount of memory that can be used for prefetching and buffering of dirty data has to be estimated and future accesses of data and metadata have to be predicted. When the request generation phase completes the idle phase of the epoch begins. During the idle phase the system keeps track of the progress of each running application and the status of the file cache. The goal is to predict the time to the next I/O request, and if the predicted time is long enough power down the disk. In order to maintain responsiveness, the next request generation phase is scheduled so that data not yet in memory are prefetched well in advance. The new prefetching cycle has to start early enough to hide any application perceived delays that can be caused because of the disk power-up penalty or disk congestion. A new epoch can be triggered by the initiation of a new prefetching cycle, a demand-miss, in which case the prefetching algorithm has failed to load in memory all necessary data, the expiration of one or more dirty buffers, or the depletion of memory resources, in which case the page freeing logic hast to be executed. |
|
|
The first problem we had to address in our work was deciding what to prefetch. For certain common applications such as copying, encoding and MP3 or MPEG playback the decision is easy. Such application exhibit sequential access patterns that can be detected easily. In our current research, we explore applications with random access patterns or accesses to multiple files. In such cases prefetching accuracy can be improved by hints. New applications can explicitly provide hints to the operating system through a system call. Older applications are supported through a monitoring system that predicts future accesses based on past behavior. Prefetching in this case can afford to be very speculative: one saved spin-up operation will pay for a LOT of unnecessary reads. |
|
|
In order to dynamically control the amount of memory used for prefetching we have extended the traditional LRU memory cache with a new data structure, the prefetch cache, which maintains recently prefetched data. Intuitively the size of the prefetch cache should be large enough to contain all predicted data accesses, without causing the eviction of pages that are going to be accessed sooner than the prefetched data. Since our goal is to maximize the length of disk idle intervals we use the type of the first miss during an epoch s idle phase in order to determine the prefetch cache size for the next epoch.
We categorize misses as: In order to identify eviction misses we use a new data structure, the eviction cache, which stores metadata of recently evicted pages along with a unique serial number, the eviction number. In case of an eviction miss the difference between the first miss's eviction number and the starting eviction number of the current epoch provides an estimate of the prefetch cache size for the upcoming epoch. The prefetch cache size does not change in case of compulsory misses and is increased by a constant in case of prefetch misses. |
|
|
Idle interval length can be limited because of a lack of coordination among requests generated by different applications. Writes and page-out requests can easily be clustered because they are issued by a single entities: the update and the swap daemons, respectively. However, read and prefetching requests are generated within a process context independently of other applications. To coordinate prefetching requests we introduce a centralized entity that is responsible for generating prefetching requests for all running applications, the prefetch thread. This way the problem of request coordination is reduced to the problem of coordinating three daemons. |
|
|
Another cause that can limit the length of disk idle intervals is the behavior of the update daemon. The update daemon of the original Linux kernel executes every five seconds and flushes all dirty buffers that are older than 30 seconds. Such a policy limits idle interval lengths to just 5 seconds during write workloads. In our system, we have modified the update daemon to flush all dirty buffers once per minute. In addition, we have extended the open system call with a flag that indicates that write behind to a certain file can be postponed until close. This type of direction is useful for applications without strict reliability constraints, such as compilations and encoding operations. |
|
|
A final goal of our system is to maintain responsiveness by hiding the negative effects of disk power-up penalties and disk congestion. For this purpose during the idle phase of an epoch the system monitors the data production and consumption rates of each application and the amount of data remaining in the prefetch cache. Based on this information the system attempts to initiate a prefetch cycle well in advance, before applications consume their in-memory data. To be able to maintain responsiveness in case of unpredicted demand-misses a prioritized disk queue is necessary, in order to identify and service quickly such misses during periods of high disk congestion. |
|
|
For our experimental evaluation we used a DELL Inspiron 4100 laptop with 512MB of total memory and a Hitachi DK23DA hard disk. Power measurements were collected by instrumenting the hard disk s power supply lines and integrating current over time. We used two workload scenarios. The first one was MPEG playback of two 70MB files. The second one involved the concurrent execution of MPEG playback and MP3 encoding. We used the same input for MPEG playback. The input to the MP3 encoder was 10 WAV files with a total size of 626MB and the output was 10 MP3 files with a total size of 42.9MB. Our Linux disk power management policy spins down the disk after 10 seconds of idle time. The power management policy of our system, which we will call Bursty in the remainder of the talk, spins down the disk based on a predictive algorithm that monitors application progress and file cache state. |
|
|
Our first graph shows the disk energy savings for the two workloads as a function of memory size. Increasing the total system memory has practically no impact on energy savings in the case of the Linux kernel. However, for our Bursty system, disk energy savings scale with memory size leading to 78.5% savings for the first workload and 62.5% for the concurrent workload when memory reaches 492MB. |
|
|
The next graph shows the cumulative distribution function of idle time intervals during the execution of the second workload. As memory size increases, most of the idle time appears in longer intervals. The increased idle interval length provides more opportunities to the hard disk to enter a low power state and remain in that state for a longer time period. We do not show the case for respective graphs for Linux because, idle time appears in intervals of less than 1 second for all memory size and workloads. |
|
|
This graph presents a power consumption snapshot of the hard disk during the execution of the MPEG playback. In the case of the original Linux kernel (red line) the disk remains constantly in the ative power state. However, in the case of our system, the disk manages to switch to lower power states for longer time periods as memory increases. This is a direct effect of increasing the idle interval length. We show results for a 64MB system (green line) and 128MB system (blue line). Note that at the 128MB system the disk spends most of its time in the spun-down mode, while on the 64MB system the disk makes use of both an intermediate idle mode and the suin-down mode. Also notice that the number of transitions is reduced in the 128MB system. |
|
|
Finally, we present performance results for the second workload. Across all memory sizes and workloads our system stays within 3% of the execution time on Linux. With only 64MB of memory, Bursty is still less than 5% slower than Linux with 492MB. |
|
|
Our prototype implementation works well with predictable applications. Our disk energy savings scale with memory size. Bursty achieves up to 78.5% disk energy savings for the workloads used with less than 5% performance penalty across all workloads and memory sizes. Our current research focuses on applications with less predictable access patterns. We believe that for such applications support for guiding the prefetching system is essential. New applications can provide prefetching hints explicitly. For older applications an on-line monitoring system can analyze previous execution instances and provide hints on behalf of the applications. For such applications, very speculative prefetching algorithms can be used in order to minimize the number of false negatives , since even a high false positive to true positive ratio has a small negative effect on energy consumption. |
|
|
Although in this talk we focused on hard disks, the idea of burstiness can be applied to other devices. Wireless network interfaces are an obvious example, but they introduce new complications. First, several wireless interfaces support varying levels of broadcast power in addition to standby modes. Second, since energy consumption depends on the channel s quality, communication bursts can be scheduled during periods of high channel quality. Finally the requirement to accommodate externally initiated traffic has a significant impact on the transport and physical layer protocols. An additional example arises in the case of RDRAM memory chips. One has the option to increase the burstiness on a certain chip, maximizing at the same time the idle interval lengths on the rest. Finally, burstiness may become important in the processor domain as well. On a multi-clock domain processor one can save dynamic power by slowing down the integer unit in a floating point application or schedule instructions for burstiness and save both dynamic and static energy by gating off voltage to the integer unit. |
|
|
For more information and publications on the topic visit the URL on the slide. |
|