Cache Replacement Policies

This book summarizes the landscape of cache replacement policies for CPU data caches. The emphasis is on algorithmic issues, so the authors start by defining a taxonomy that places previous policies into two broad categories, which they refer to as coarse-grained and fine-grained policies. Each of these categories is then divided into three subcategories that describe different approaches to solving the cache replacement problem, along with summaries of significant work in each category. Richer factors, including solutions that optimize for metrics beyond cache miss rates, that are tailored to multi-core settings, that consider interactions with prefetchers, and that consider new memory technologies, are then explored. The book concludes by discussing trends and challenges for future work. This book, which assumes that readers will have a basic understanding of computer architecture and caches, will be useful to academics and practitioners across the field.