Nathan Beckmann, Phillip B. Gibbons, Bernhard Haeupler, Charles McGuffey
Carnegie Mellon UniversityThe literature on cache replacement, while both detailed and extensive, neglects to account for the flow of data to storage. Motivated by emerging memory technologies and the increasing importance of memory bandwidth and energy consumption, we seek to fill this gap by studying the Writeback-Aware Caching Problem. This problem modifies traditional caching problems by explicitly accounting for the cost of writing modified data back to memory on eviction.
In the offline setting with maximum writeback cost ω > 0, we show that writeback-aware caching is NP-complete and Max-SNP hard. Moreover, we show that Furthest-in-the-Future, the optimal deterministic policy when ignoring writebacks, is only (ω + 1)-competitive. These negative results hold even for the simple variant of the problem in which data items have unit size, unit miss cost, and unit writeback cost (ω = 1). To overcome this difficulty, we provide practical algorithms to compute upper and lower bounds for the optimal policy on real traces.
In the online setting, we present a deterministic replacement policy called Writeback-Aware Landlord and show that it obtains the optimal competitive ratio. Our bounds on the optimal offline policy and our optimal competitive ratio hold even for the most general variant in which data items have variable sizes, variable miss costs, and variable writeback costs. Finally, we perform an experimental study on real-world traces showing that Writeback-Aware Landlord outperforms state-of- the-art cache replacement policies when writebacks are costly, thereby illustrating the practical gains of explicitly accounting for writebacks.
FULL CONFERENCE PAPER: pdf