CSCI 237

Computer Organization

Home | Schedule | Assignments | Links | Williams CS

Lab 5: Exploring Cache Memories

Optional Collaboration

You may openly consult with a single classmate on this lab. However, you much each submit your own code in your own repository. If you wish to consult with a partner, please update your repository's README.md with the statement "I collaborated with {partner's name}". Discussion groups of three or more are not permitted. If you choose to consult with a partner, make sure that you can both attend the same lab session.

By consult, what we mean is that you may discuss your design, debugging strategies, and C syntax without restriction. You may also view your partner's code while engaging in these activities. However, you may not copy code. All code that you write must be typed by yourself based on your own understanding. In other words, when writing your own code, you may not look at any code that you did not author yourself. And discussion of your code with your partner should not be used to generate new code, only to improve and refine code that you have written.

Lab Overview

This lab will help you explore the operation of cache memories and the impact they can have on the performance of your C programs. You will write a small C program (about 200-300 lines) that simulates the behavior of a cache memory. In order to build a working cache simulator, you will also use C structs, malloc()/free(), and C file reading.

Repository Organization

Inside your repository, you will find a number of files. To complete this lab, you only need to modify one file inside this directory, csim.c. However, you are free to add and submit additional files if they help you to complete your implementation.

To compile your lab, type:

         $ make clean; make
    

Note: make clean is optional. See the Makefile for more details.

Reference Trace Files

The traces subdirectory contains a collection of reference trace files that you will use to evaluate the correctness of the cache simulator that you will write. The trace files are generated by a Linux program called valgrind. For example, if you are on a lab machine, typing:

        $ valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l
    

on the command line runs the executable program "ls -l", captures a trace of each of its memory accesses in the order they occur, and prints them on stdout. You do not need to run valdrind yourself in order to complete this lab (we provide several trace files to you), but you may find it interesting to create new traces and test them out on your cache implementation.

Valgrind memory traces have the following form:

         I  0400d7d4,8
          M 0421c7f0,4
          L 04f6b868,8
          S 7ff0005c8,8
	

Each line denotes one or two memory accesses. The format of each line is:

         [space]operation[space] address,size
    

The operation field denotes the type of memory access:

• "I" denotes an instruction load
• "L" a data load
• "S" a data store, and
• "M" a data modify (i.e., a data load followed by a data store).

In the format above, [space] denotes the possibility of a space. There is never a space before an "I", and there are two spaces after. There is always a space before an "M", "L", and "S", and there is only one space after. The address field specifies a 64-bit hexadecimal memory address. The size field specifies the number of bytes accessed by the operation.

Writing Your Cache Simulator

The goal of this lab is to write a cache simulator in csim.c that takes a valgrind memory trace as input, simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions.

We have provided you with the binary executable of a reference cache simulator, called csim-ref, that simulates the behavior of a cache with arbitrary size and associativity on a valgrind trace file. It uses the LRU (least-recently used) replacement policy when choosing which cache line to evict.

The reference simulator takes the following command-line arguments:

         Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>
    

• -h: Optional help flag that prints usage info
• -v: Optional verbose flag that displays trace info
• -s <s>: Number of set index bits (S = 2^s is the number of sets)
• -E <E>: Associativity (number of lines per set)
• -b <b>: Number of block bits (B = 2^b is the block size)
• -t <tracefile>: Pathname of the valgrind trace file to replay

The command-line arguments are based on the notation (s, E, and b) from CSAPP (see page 617). Figure 6.25 on page 616 is also helpful. For example:

         $ ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
         hits:4 misses:5 evictions:3
    

The same example in verbose mode:

         $ ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace
         L 10,1 miss
         M 20,1 miss hit
         L 22,1 hit
         S 18,1 hit
         L 110,1 miss eviction
         L 210,1 miss eviction
         M 12,1 miss eviction hit
         hits:4 misses:5 evictions:3
    

Your job is to fill in the csim.c file so that it takes the same command line arguments and produces identical output as the reference simulator. Notice that the version of csim.c that we provided is almost completely empty. You'll need to implement most functionality from scratch.

Programming Rules for your Cache Simulator

• Your csim.c file must compile without warnings in order to receive credit. You can compile with make. The instructors and TAs can help you diagnose any compiler warning messages that are unclear, but interpreting the compiler's output is a skill that you are hopefully developing through experience.
• Your simulator must work correctly for arbitrary values of s, E, and b. This means that you will need to allocate heap memory for your simulator's data structures using the malloc() function. Type man malloc at the terminal for information about this C library function. (When reading the manual, the arrow keys scroll, and the `q' key quits.)
• For this lab, we are interested only in data cache performance, so your simulator should ignore all instruction cache accesses (lines starting with "I"). Recall that valgrind always puts "I" in the first column (with no preceding space), and "M", "L", and "S" in the second column (with a preceding space). This rule should help you parse the trace.
• To receive credit for this lab, the ouput when you call the function printSummary, with the total number of hits, misses, and evictions, should match the output of our simulator. This is done at the end of the main function in cachelab.c:

  	      printSummary(hit_count, miss_count, eviction_count);
  	    

• For this this lab, you can assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries. By making this assumption, you are free to ignore the request sizes in the valgrind traces.

Evaluation

We will run your cache simulator using different cache parameters and traces. There are eight test cases, each worth 3 points, except for the last case, which is worth 6 points:

         $ ./csim -s 1 -E 1 -b 1 -t traces/yi2.trace                                                                                  
         $ ./csim -s 4 -E 2 -b 4 -t traces/yi.trace                                                                                   
         $ ./csim -s 2 -E 1 -b 4 -t traces/dave.trace                                                                                 
         $ ./csim -s 2 -E 1 -b 3 -t traces/trans.trace                                                                                
         $ ./csim -s 2 -E 2 -b 3 -t traces/trans.trace                                                                                
         $ ./csim -s 2 -E 4 -b 3 -t traces/trans.trace                                                                                
         $ ./csim -s 5 -E 1 -b 5 -t traces/trans.trace                                                                                
         $ ./csim -s 5 -E 1 -b 5 -t traces/long.trace

You can use the reference simulator csim-ref to obtain the correct answer for each of these test cases. During debugging, use the -v option for a detailed record of each hit and miss.

For each test case, outputting the correct number of cache hits, misses and evictions will give you full credit for that test case. Each of your reported number of hits, misses and evictions is worth 1/3 of the credit for that test case. That is, if a particular test case is worth 3 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 2 points.

Hints and Details

We have provided you with an autograding program, called test-csim, that tests the correctness of your cache simulator on the reference traces. Be sure to compile your simulator before running the test:

         $ make
         $ ./test-csim
    
         Your simulator Reference simulator
         Points (s,E,b) Hits Misses Evicts Hits Misses Evicts
              3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace
              3 (4,2,4) 4 5 2 4 5 2 traces/yi.trace
              3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace
              3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace
              3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace
              3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace
              3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace
              6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace
             27

For each test, it shows the number of points you earned, the cache parameters, the input trace file, and a comparison of the results from your simulator and the reference simulator.

Here are some hints and suggestions for working on the Lab:

• Write out your design on paper. What are the important operations? What are the important data structures? C does not support classes, but you can define your own types as C struct data types. How will you represent a cache line? A cache set? Your entire cache? We are expecting good design, where you use structs to represent the logical entities that are the components of your cache.
• Break your functionality into discrete tasks that you can compile and test individually. How will you verify that you have parsed arguments, read a trace, replayed a trace, etc.? Compile and run incrementally and often.
• The stdint.h header defines C data types with fixed widths. Alternatively, an unsigned long long int is a 64-bit unsigned integer.
• Do your initial debugging on the small traces, such as traces/dave.trace. We strongly encourage you to create a helper method that prints out the current state of the cache; this function can potentially be called after each access of the cache to help you debug. For example, the output from our debugging function looks like this:

  	      ***** SET 0 *****
  	      Element 0: tag 0 valid 1 lru 3
  	      Element 1: tag 2 valid 1 lru 2
  	      Element 2: tag 8 valid 1 lru 0
  	      Element 3: tag 10 valid 1 lru 1
        	      ***** SET 1 *****
  	      Element 0: tag 1 valid 1 lru 1
  	      Element 1: tag 9 valid 1 lru 0
  	      Element 2: tag 0 valid 0 lru -1
  	      Element 3: tag 0 valid 0 lru -1
  	      *****************
  	    

• The reference simulator takes an optional -v argument that enables verbose output, displaying the hits, misses, and evictions that occur as a result of each memory access. You are not required to implement this feature in your csim.c code, but we strongly recommend that you do so. It will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator on the reference trace files.
• Think about what command line arguments you need to specify (s, E, b, v, etc.), and what values you can derive from those arguments.
• You should you use the getopt function to parse your command line arguments. Use "man getopt" for details, or see the gnu.org documentation (getopt_long is probably not necessary, but the first two links are likely very helpful!). You'll need to include the following header files to use getopt:

  	      #include <getopt.h>
  	      #include <stdlib.h>
  	      #include <unistd.h>
  	    

• Each data load (L) or store (S) operation can cause at most one cache miss. The data modify operation (M) is treated as a load followed by a store to the same address. Thus, an M operation can result in two cache hits, or a miss and a hit plus a possible eviction.
• Your cache should use the LRU cache replacement policy. Where will you store the "timestamp" to track access recency? What data type will you use to represent that "timestamp"? What actions require which timestamps to change (and how)?

Resources

• Example C code and accompanying data file
• Jeannie's cachelab hints from 2017