CSCE 614 Fall 2019 Project

The project for our class will be a cache replacement contest. You may work on this project in groups of up to four people, or you may work on the project individually. The project proposal is due October 18, 2019. The final project is due on December 2, 2019.

The Project

You will implement a cache replacement and bypass policy. You will use a simulation infrastructure that will be distributed to implement your policy. The basic idea is this: a cache simulator will call your code to decide which among n blocks in a set should be evicted when a replacement is needed in a given level of the 3-level cache hierarchy. Your code will return a number from 0 through n-1 to indicate the block number (way) of the victim block, or -1 to indicate that no block should be replaced, i.e. that the incoming block should bypass the cache. Your code will also be consulted when a block is referenced so that it may update its state. Your code will be consulted for all 3 levels of the cache hierarchy. Your code can know which level it is in by the associativity: 4 for L1, 8 for L2, and 16 for L3. The cache hierarchy is exclusive. That is, a block may only be in up to one level of the cache hierarchy at a time. The simulator can be downloaded from the TAMU github through this link. The traces are here (tar file) and here (individual files). Note that the traces are quite large so the tar file is about 10GB. If you would rather not download them, you can access them on the CS network through ~djimenez/traces. Maybe. If don't know if that works. Let me know. The README.md file has more information about how to use the infrastructure.

How To Choose A Cache Replacement Policy

This project is on high-performance cache replacement for an exclusive cache hierarchy. To my knowledge, there are no such policies published in the literature so you will have to be a little creative. I recommend you start by adapting one of the many policies that have been developed for inclusive and non-inclusive caches. For example:
  1. Qureshi et al., ISCA 2007, Adaptive Insertion Policies for High Performance Caching.
  2. Xie and Loh, ISCA 2009, PIPP: Promotion/Insertion Pseudo-Partitioning of Multi-Core Shared Caches
  3. Petoumenos et al., SAMOS 2009, Instruction-Based Reuse-Distance Prediction for Effective Cache Management
  4. Jaleel et al., ISCA 2010, High Performance Cache Replacement Using Re-Reference Interval Prediction
  5. Khan et al., MICRO 2010, Sampling Dead Block Prediction for Last-Level Caches
  6. Wu et al., MICRO 2011, SHiP: Signature-Based Hit Predictor for High Performance Caching
  7. Khan et al., HPCA 2014, Improving Cache Performance by Exploiting Read-Write Disparity
  8. Teran et al., MICRO 2016, Perceptron Learning for Reuse Prediction
You may propose another paper, or if you like, your own novel replacement policy. In this case you will need to submit an informal proposal by email to the professor or discuss it in person. You may not turn in a project using a simple replacement policy such as LRU, random, etc. Your project must attempt to improve over such simple policies.

Optimizing Your Policy

You are responsible for implementing the technique in the paper you choose, but beyond that you may feel free to implement additional optimizations. For instance, some of the papers do not do bypassing; you may augment the technique to decide when to do bypassing.

What Is Due for the Project

You will turn in a project proposal and a final project writeup, as well as your code.

The Proposal

The proposal is due on October 18, 2019. The proposal should be a document giving the approach the group (or individual) will take to accomplish the project. The following questions should be answered:
  1. Who are the group members? List one to four people.
  2. What algorithm will be used for cache replacement at each level?
  3. What experiments will you do to tune your algorithm?
  4. How will work be divided among the group members?
  5. What papers have you read to inform your algorithm? List at least three papers.
Turn in the proposal through eCampus.

The Final Project

The final project is due on December 2, 2019. The project writeup should give an introduction, related work, main idea of the replacement policy, methodology, results with bar charts, and conclusion. The writeup must be written in the style of an IEEE conference paper, with an introduction, methodology, background and related work, section describing the algorithm, results, conclusion, and references sections.

You will also turn in your source code: the files replacement_state.cpp and replacement_state.h. Your code must compile and run cleanly under the unmodified simulation infrastructure. It must not make any output. We will not accept any other code. Your code must compile and run with no modifications to any other part of the infrastructure. The code should compile cleanly under g++ version 4.8.5 (availble on linux.cse.tamu.edu). Turn in the writeup and code through eCampus.

Hardware Budget

There is no specified hardware budget for this project. Use a reasonable amount of storage (i.e., the cache is 4MB so if you find yourself using several megabytes, that is unreasonable).

How Is The Contest Judged?

The contest will be won by the entry that has the best geometric mean speedup over the LRU policy. That is, for each trace we will divide the IPC given by your technique by the IPC given by LRU, then find the geometric mean of all of these speedups. The highest one wins.

Due Date

The project proposal is due on October 18, 2019. The final project is due on December 2, 2019.