Project 3 Caching Solution

Read the entire document before starting. There are critical pieces of information and hints along the way.

Caches are complex memory and sometimes di cult to understand. One way to understand them is to build them. However, due to time constraints and lack of hardware expertise, we will instead write a cache simulator. In this project, you will be implementing a cache simulator. We have provided you the following les:

src/cachesim_driver.c - Program to runs the simulator and for a trace and calls the methods in cachesim.c.

src/cachesim.h - Header  le for simulator.

src/cachesim.c - The cache simulator, missing some vital portions of code. This is the only le you should modify.

Makefile - Compiles your project.

traces/ - Contains the sample Spec Benchmark workloads.

solutions/ - The solution generated by the TAs. The run_script.sh will produce output that you should compare to stats.log for a nal con rmation your cache works. Your simulator should produce output that exactly matches this. For debugging along the way, you can use the detailed trace les that say whether each access is a hit or a miss with the default cache con guration for each policy.

run_script.sh - A shell script to run all the test cases.

You will be lling in the functions in the cachesim.c le, and then validating your output against the given outputs in the solutions folder.

This assignment that will check your understanding of how caches work. However, keep in mind that your choice of data structure used will greatly impact the di culty of implementing the cache. If you are struggling with writing the code, then step back and review the concepts. Be sure to start early, ask Piazza questions, and visit us in o ce hours for extra help!


    • Cache Speci cations

Here are the speci cations that your simulator must meet:

    1. The simulator must model a cache with 2C bytes of data storage, with 2B byte blocks with 2S blocks per set.

Note: S = 0 implies a direct mapped cache, and S = C - B is a fully associative cache.

    2. The cache implements a write back, write allocate policy. Think about what this means in terms of dirty bits.

    3. There is a valid bit for each block. This should be set to 0 at the start of the simulation.

    4. The cache should be able to implement both an LRU replacement and FIFO replacement policy. A command line ag will be used to choose which replacement policy your simulation should use.

    5. All memory addresses are 64 bits.

    6. The cache is byte addressable.
Project 3 - Caching    CS 2200 - Systems and Networks     



    • Implementation

Your task is to    ll out the following functions in cachesim.c:

    1. cache_init()

    2. cache_access()

    3. cache_cleanup()

    4. get_tag()

    5. get_index()

Each function listed above has helpful comments in the cachesim.c le. You may add any global variables or helper functions you deem necessary. You also may need to alter the structs in cachesim.c to t your needs. You should not change anything outside of cachesim.c or add any new les. You do not need to and should not use any math libraries to split up addresses in get_tag() and get_index().

A trace of memory access (a memory address and whether it is a read or a write) is given in each of the les in the traces folder. The driver will rst run the cache_init() function, which then will run your cache_access() with the address for each memory access. Since this is just a simulator, you will not have to worry about any data storage. You will only need to keep track of metadata to simulate the cache accesses. Once the simulator has performed all of the accesses, the simulator will call cache_cleanup() and print the statistics.


    • Statistics

The output from your nal cache is the statistics that your cache calculates for each workload. Here is the list of elds inside the cache_stats_t struct and their meaning:

    1. accesses - The total number of memory accesses your cache gets

    2. reads - The number of accesses that were reads

    3. read_misses - The total number of reads that were cache misses

    4. writes - The total number of accesses that were writes

    5. write_misses - The total number of writes that were cache misses

    6. misses - The total number of cache misses (both reads and writes)

    7. write_backs - The total number of times data was written back to memory

    8. cache_access_time - The access time of the cache (3ns)

    9. memory_access_time - The miss penalty for a cache miss (120ns)

    10. miss_rate - The miss rate for the cache

    11. avg_access_time - The average access time for your cache, aka AAT

The driver will format and print the contents of the stats struct to the console. You only need to ll in the stats structure passed in the cache access and cache cleanup functions.
Project 3 - Caching    CS 2200 - Systems and Networks     



    • Validation Requirement

We have provided sample outputs in the solutions directory. You must run your simulator and debug until your output perfectly matches all the statistics given in the sample outputs. Use the instructions in section 6.4 to compare your simulator’s output against our samples.


    • How to Run / Debug Your Code

6.1    Environment

Your code will need to compile under Ubuntu 16.04 LTS. You can develop on whatever environment you prefer, so long as your code also works in Ubuntu 16.04 (which we will use to grade your projects). Non-compiling solutions will receive a 0! Make sure your code compiles with no warnings. We recommend downloading VirtualBox and setting up a new virtual machine with Ubuntu 16.04 if you are on Mac OS or Windows. If you are having trouble with this, come to o ce hours.


6.2    Compiling and Running

We have provided a Make le that will run gcc for you. To compile your code with no optimizations (which you should do while developing, it will make debugging easier), just run

$  make    debug

from the main project directory. This will produce the cachesim executable, which you can run with

$  ./ cachesim    -C

< cache    size >

-B  < block    size >

-S

< set

associativity >

-r  < LRU

or  FIFO >  -i

< trace  name >

All arguments are optional. Additionally, the -p ag can be used to make your simulator output every memory access and the cache behavior, allowing you to identify individual bugs by comparing to the given solution les for each trace.


6.3    Debugging Tips

You can use valgrind and gdb (GNU Debugger) to help debug your project. Valgrind is a program that helps detect memory management bugs, and GDB is a command line interface that will allow you to set breakpoints, step through your code, see variable values, and identify segfaults. There are tons of online guides, click here (http://condor.depaul.edu/glancast/373class/docs/gdb.html) for one.

To use valgrind, run:

$  valgrind    ./ cachesim    -C  15  -B  4  -S  2  -r  FIFO  -i  traces / mcf . trace

To start your program in gdb, run:

$  gdb  ./ cachesim

Within gdb, you can run your program with the run command, see below for an example:

( gdb )  r  -C  15  -B  4  -S  2  -r  FIFO  -i  traces / mcf . trace

Feel free to ask about valgrind or gdb and how to use it in o ce hours and on Piazza. Do not ask a TA or post on Piazza about a segfault without rst running your program through both.
Project 3 - Caching    CS 2200 - Systems and Networks     



6.4    Verifying Your Solution

You can ensure your cache simulator works by testing it and comparing it to the given les in the solutions folder. An example of this work ow is given below. You could also use the same tools to check the detailed output traces.

    • make  clean

    • make

$  ./ r u n _ s c r i p t    >  my_stats . log

$  diff  -u  my_stats . log    s ol ut io ns / stats . log

The commands above rebuild the project. They then use the ./run_script.sh script to run your cache with several di erent con gurations. The > character redirects the output of the script from stdout to a le called my_stats.log. Then, the diff program will identify the lines that di er between your output and the given solutions in solutions/stats.log.


    • How to Submit

Please submit all of the following    les in a .tar.gz archive. You must turn in:

Make le

src/cachesim.c src/cachesim.h

src/cachesim driver.c


Run make submit to automatically package your project for submission.

Always re-download your assignment from T-Square after submitting to ensure that all nec-essary les were properly uploaded. If what we download does not work, you will get a 0 regardless of what is on your machine.

This project will be demoed. In order to receive full credit, you must sign up for a demo slot and complete the demo. We will announce when demo times are released.