Given continually increasing core counts, multiprocessor software scaling is critical. One set of applications that is especially difficult to parallelize efficiently are those that operate on hierarchical data. In such applications, correct execution relies on all threads coordinating their accesses within the hierarchy. At the same time, high-performance execution requires that this coordination be efficient and that it maximize parallelism.

As a file system ages, it can experience multiple forms of fragmentation. Fragmentation of the free space in the file system can lower write performance and subsequent read performance. Client operations as well as internal operations, such as deduplication, can fragment the layout of an individual file, which also impacts file read performance. File systems that allow sub-block granular addressing can gather intra-block fragmentation, which leads to wasted free space. Similarly, wasted space can also occur when a file system writes a collection of blocks out to object storage as a single large object, because the constituent blocks can become free at different times. The impact of fragmentation also depends on the underlying storage media. This article studies each form of fragmentation in the NetApp ® WAFL ® file system, and explains how the file system leverages a storage virtualization layer for defragmentation techniques that physically relocate blocks efficiently, including those in read-only snapshots. The article analyzes the effectiveness of these techniques at reducing fragmentation and improving overall performance across various storage media.

Given the enormous disparity in access speeds between main memory and storage media, modern storage servers must leverage highly effective buffer cache policies to meet demanding performance requirements. At the same time, these page replacement policies need to scale efficiently with ever-increasing core counts and memory sizes, which necessitate parallel buffer cache management. However, these requirements of effectiveness and scalability are at odds, because centralized processing does not scale with more processors and parallel policies are a challenge to implement with maximum effectiveness. We have overcome this difficulty in the NetApp Data ONTAP WAFL file system by using a sophisticated technique to simultaneously allow global buffer prioritization while providing parallel management operations. In addition, we have extended the buffer cache to provide a soft isolation of different workloads' buffer cache usage, which is akin to buffer cache quality of server (QoS). This paper presents the design and implementation of these significant extensions in the buffer cache of a high-performance commercial file system.

Voltage/Frequency Scaling (VFS) and Device Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. VFS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g., memory or I/O devices) to low-power/sleep states at runtime, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using VFS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a VFS-enabled CPU and using multiple devices. Specifically, by adopting a generalized system-level energy model, we characterize the variations in different components of the system energy as a function of the CPU processing frequency. Then, we propose a provably optimal and efficient algorithm to determine the optimal CPU frequency as well as device state transition decisions to minimize the system-level energy. We also extend our solution to deal with workload variability. The experimental evaluations confirm that substantial energy savings can be obtained through our solution that combines VFS and DPM optimally under the given task and energy models.

Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) techniques form the basis of numerous energy management schemes proposed for real-time embedded systems. DVS targets reducing the dynamic CPU energy consumption, while DPM attempts to reduce theenergy consumption of idle devices by putting them to low-power states over sufficiently long intervals. It is imperative that the system-wide energy management schemes efficiently integrate DVS and DPM while exploiting the subtle trade-off dimensions. In this paper, we develop and propose a unified framework for periodic real-time tasks where DVS and DPM are judiciously combined. The framework, called DFR-EDF, assumes a general system-level energy model and includes both static and dynamic(online) components. The static part is based on the extension of the recently proposed Device Forbidden Regions (DFRs) approach to Earliest-Deadline-First (EDF) scheduling. The online component integrates the predictive DPM techniques and offers a generalized slack reclaiming mechanism that can be used by DVS and DPM simultaneously. Our experimental evaluation indicates significant gains of DFR-EDF at the system-level compared to the state-of-the-art solutions. Finally, this research effort makes another contribution by formally showing that optimally solving the DPM problem in periodic real-time execution settings is NP-Hard in the strong sense, even in the absence of DVS.

In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings, we prove that no online algorithm can achieve a competitive factor greater than 1 - emax/E, where emaxis the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm EC-EDF* which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these settings. We also extend our analysis to other settings, including those with non-uniform value densities and dynamic voltage scaling capability.

Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. DVS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g. memory or I/O devices) to low-power/sleep states at run-time, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using DVS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a DVS-enabled CPU and using potentially multiple devices. Specifically, by adopting a generalized system-level energy model and taking into account the non-trivial time/energy overheads involved in device transitions, we characterize the variations in different components of the system energy as a function of the CPU processing speed. Then, we propose a provably optimal algorithm to determine the optimal CPU speed as well as device state transition decisions to minimize the system-level energy. Our algorithm runs in O(m log m) time, where m is the number of devices used by the application. The evaluations with realistic system parameters indicate that our solution, which combines DVS and DPM optimally, can lead to substantial energy savings when compared to previous solutions.

Dynamic power management (DPM) techniques are crucial in minimizing the overall energy consumption in real-time embedded systems. The timing constraints of real-time applications and non-trivial time/energy transition overheads introduce significant challenges, as the device sleep intervals should be longer than a minimum threshold (called the break-even time) to ensure energy-efficiency. In this paper, we present a novel approach to the real-time DPM problem by explicitly enforcing long device sleep intervals for different devices, called device forbidden regions. We focus on the application of our technique to task systems with rate-monotonic priorities, and develop our algorithm DFR-RMS. Our solution includes a static component where the duration and frequency of forbidden regions are determined through the extended time-demand analysis to preserve the temporal correctness of all the tasks, while enhancing the energy savings. Then, we present a sophisticated on-line component which interacts with existing prediction-based DPM schemes to realize the full potential of device forbidden regions. Further, our scheme can be used with or without dynamic voltage scaling (DVS). Our experimental evaluation hints that significant energy gains can be obtained, when compared to the existing prediction-based techniques. Another contribution of this research effort is to show that the general problem of generating feasible schedules for preemptive periodic real-time tasks where all device sleep intervals are longer than the device break-even times is NP-hard in the strong sense.

In this paper, we consider the system-wide energy management problem for a set of periodic real-time tasks running on a DVS-enabled processor. Our solution uses a generalized power model, in which frequency-dependent and frequency-independent power components are explicitly considered. Further, variations in power dissipations and on-chip/off-chip access patterns of different tasks are encoded in the problem formulation. Using this generalized power model, we show that it is possible to obtain analytically the task-level energy-efficient speed below which DVS starts to affect overall energy consumption negatively. Then, we formulate the system-wide energy management problem as a non-linear optimization problem and provide a polynomial-time solution. We also provide a dynamic slack reclaiming extension which considers the effects of slow-down on the system-wide energy consumption. Our experimental evaluation shows that the optimal solution provides significant (up to 50%) gains over the previous solutions that focused on dynamic CPU power at the expense of ignoring other power components