/LHD

Simulation code for the LHD cache replacement policy as published in NSDI 2018.

Primary LanguageC++OtherNOASSERTION

Welcome!

This repository gives the simulation code for LHD (Least Hit Density),
a cache replacement policy described in the paper "LHD: Improving
Cache Hit Rate by Maximizing Hit Density" published at NSDI 2018.

To build the simulator, simply run

$ make

in this directory. This will produce ./bin/cache, which will run the
simulator by

$ ./bin/cache example.cfg

However, for this example to run, you first need to obtain trace
files. example.cfg references MSR trace src1_1, but you can supply any
trace you like. The expected format of the trace file is given in
parser.hpp: we use a binary format to encode traces for efficiency,
but you can define your own format easily in parser.hpp. You then need
to modify cache.cpp to point the simulator at the right path to your
trace file.

example.cfg gives reasonable default parameters for LHD. Except for
associativity, we found that LHD is insensitive to these parameters
across large values, but feel free to experiment yourself (and please
send us any exceptions you find!).

To summarize the contents of this repository, the main files are:

- cache.cpp: main().

- cache.hpp: The cache simulator itself that calls into the
  replacement policy. We model an idealized cache without
  fragmentation.

- repl.hpp: A generic replacement policy interface. update() is called
  when an object is referenced. replaced() is called when an object is
  evicted. rank() is called to get the next victim when the cache is
  full.

- lhd.hpp: The LHD replacement policy definition. It implements the
  ReplPolicy interface.

- lhd.cpp: The LHD replacement policy implementation. The core of the
  policy is implemented in the first 200 lines; the remaining lines
  are for debugging and infrequent configuration (see comments).

The other files are:

- bytes.hpp: Helper function for printing large values as KB, MB, GB,
  etc.

- candidate.hpp: Data type to uniquely identify objects in the cache
  (ie, replacement "candidates").

- config.hpp: Config file parser.

- constants.hpp: Simulation constants. Mostly unused in this release.

- example.cfg: A starter config file (see above).

- LICENSE: This software is released under the MIT license.

- lru.hpp: Baseline LRU replacement policy. Can be selected in
  example.cfg by setting repl.type to "LRU".

- Makefile: Build instructions.

- parser.hpp: Trace parser. See above.

- rand.hpp: Fast linear-congruential random number generator.

- repl.cpp: Initialization function to create different replacement
  policies (only LRU and LHD in this release).