Name
Abstract | ||
|---|---|---|
Motivated by emerging memory technologies and the increasing importance of energy and bandwidth, we study the Writeback-Aware Caching Problem. This problem modifies the caching problem by explicitly accounting for the cost of writing data to memory. In the offline setting with maximum writeback cost omega > 0, we show that the writeback-oblivious optimal policy is only (omega + 1)-competitive for writeback-aware caching, and that writeback-aware caching is NP-complete and Max-SNP hard. In the online setting, we present a deterministic online replacement policy, called Writeback-Aware Landlord and show that it obtains the optimal competitive ratio. Finally, we perform an experimental study on real-world traces which shows that Writeback-Aware Landlord outperforms state-of-the-art cache replacement policies when writebacks are costly. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3323165.3323169 | SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019 |
Field | DocType | Citations |
Online algorithm,Computer science,Cache,Bandwidth (signal processing),Landlord,Distributed computing,Competitive analysis | Conference | 0 |
PageRank | References | Authors |
0.34 | 54 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathan Beckmann | 1 | 352 | 19.46 |
| Phillip B. Gibbons | 2 | 6863 | 624.14 |
| Bernhard Haeupler | 3 | 628 | 54.00 |
| Charles McGuffey | 4 | 0 | 0.34 |