1 Introduction

This lab will help you understand the functioning of cache memories, and the impact that they can have on the performance of your C programs. You will also learn how to write C programs that can be run from the Unix command line.

The lab consists of three parts. You will first write several traces to test the behavior of a cache simulator. Next, you will write a small C program (about 200-300 lines) that simulates the behavior of a hardware cache memory. Finally, you will optimize a matrix transpose function, with the goal of minimizing the number of cache misses.

This is an individual project.  You should work on this lab on the Shark machines, which you can access via an SSH connection. You can find a list of all Shark machines at https://www.cs.cmu.edu/~213/ labmachines.html.

1.1 Downloading the assignment

From this lab onwards, you will need to have a GitHub account to access lab materials. You can use an existing GitHub account with your personal email, or create a new GitHub account using your school email—either is fine. To create an account, visit https://github.com/join.

To get started, make sure you are signed into the GitHub account you want to use. Then click “Download handout” on Autolab, and follow the instructions. You will receive an email invitation to the repository within a few minutes. It will be located at:

https://github.com/cmu15213-m22/cachelab-m22-yourgithubid

Once you accept the invitation, log onto a Shark machine, and change directories to a protected directory in AFS, such as ~/private/15213. Then, “clone” (create a local copy of) your GitHub repository by entering the following command, substituting the URL of your specific repository:

$  git  clone  https://github.com/cmu15213-m22/cachelab-m22-yourgithubid   This will create a directory containing the lab handout at cachelab-m22-yourgithubid .

1.2 Handout contents

Consult the file README for further descriptions of the handout files. For this lab, you will modify the following files:

traces / traces /tr1 . trace

traces / traces /tr2 . trace

traces / traces /tr3 . trace

csim . c

trans . c

The csim .c and trans .c files will be compiled into C programs. You can do so by running make. Note that the file csim .c doesn’t exist in your initial handout directory. You’ll need to create it from scratch and check it in (git  add  csim .c).

2 Writing Traces for a Cache Simulator (10 points)

2.1 Overview

A cache simulator is a program which simulates the behavior of a cache given a series of memory operations (loads and stores). The series of memory operations is called a trace.

In this part of the lab, you will write three traces that should produce specific types of cache behavior. We have provided you with a simulator (csim-ref) to test the traces with, but you must write them in the format it expects.

Note: We have already created empty trace files for you. They can be found in the traces/traces/ subdirectory of your lab handout. The test driver will read trace files from that location. This directory also contains an example trace file, example .trace, which should give you an idea of how to begin.

2.2 Trace File Format

csim-ref expects traces to be text files with one memory operation per line. Each line must be in the format: Op Addr,Size.

Op denotes the type of memory access. It can be either L for a load, or S for a store.

Addr gives the memory address to be accessed. It should be a 64-bit hexadecimal number, without a leading

0x.

Size gives the number of bytes to be accessed at Addr. It should be a small, positive decimal number.

Here is a short example:

L  4f6b868 ,4

S  7ff005c8 ,8

This trace instructs the simulator to simulate a load of four bytes from address 0000 0000 04f6 b868 and then a store of eight bytes to address 0000 0000 7ff0 05c8.

Note: Trace files do not specify the actual values being loaded or stored, only the number of bytes. This is because the simulator does not need to know the values. (Why?)

Note: The reference simulator only understands trace files in the format shown above. There is no way to write comments in trace files. The only valid Op codes are uppercase L and uppercase S. The comma between Addr and Size is required, as is the space between Op and Addr. There should be no spaces on either side of the comma.

2.3 Traces To Be Written

Your job for this part of the assignment is to write three traces, in the format described above, which produce certain cache actions. This part should take no more than a few hours. For each of the following, you are to create a file with the specified file name in the traces directory.

tr1 .trace: The cache will be a direct-mapped cache with 8 sets and 16 byte blocks. Your trace should result in two hits and one eviction (any number of misses is okay). You are allowed a maximum of five operations.

tr2 .trace: The cache will be a 3-way set associative cache with two sets and 16 byte blocks. Your trace should have two hits and two misses (any number of evictions is okay). You are allowed a maximum of five operations.

tr3 .trace: The cache will be a 3-way set associative with four sets and 16 byte blocks. Your trace should

result in exactly 5 hits, 4 misses, and one eviction. You are now allowed a maximum of ten operations. The specifications are summarized in this table:

If a requirement is not specified, then that value can be anything (e.g. tr1.trace must have 2 hits and 1 eviction but any number of misses, dirty bytes, etc.).

2.4 Evaluation

To evaluate your code, we will run the reference simulator with the options specified in the table above, using the traces that you write. For each trace, you will get all of the specified points if your trace meets the requirements and no points otherwise.

We have provided several tools to help you test your traces.

traces-driver.py: This is the program Autolab will use to evaluate this part of the assignment. If you run it yourself, it will tell you the results of your traces and how many points you will receive. To run it use the command ./traces-driver .py. For more information, use the -h flag.

csim-ref: This is the reference cache simulator that the driver will run. More information on this program is available later in this document.

3 Writing a Cache Simulator (60 points)

3.1 Overview

In the second part of this lab, you will write a cache simulator that simulates the behavior of a cache, given a trace in the same format you used above.

Your simulator should be able to simulate the behavior of a cache memory with arbitrary size and associativity. It should use the LRU (least-recently used) replacement policy when choosing which cache line to evict, and follow a write-back, write-allocate policy.

At the end of the simulation, it should output the total number of hits, misses, and evictions, as well as the number of dirty bytes that have been evicted and the number of dirty bytes in the cache at the end of the simulation.

As a reminder, a dirty byte is any byte in a cache block that has been modified but not yet written back to main memory. All of the bytes in a modified cache block are considered to be dirty even if that specific byte was not modified. The number of dirty bytes in the cache and the number of dirty bytes that have been evicted are therefore always a multiple of the cache block size. A dirty bit, on the other hand, is a bit associated with each cache line that tracks whether the block held by that cache line has been modified but not yet written back to main memory.

3.2 Writing a Command-Line Tool from Scratch

You may or may not have already learned how to write command-line tools: programs designed to be invoked from the Unix shell and vary their behavior based on arguments they receive on startup. The cache simulator you will write in this part of the lab is expected to be just such a tool. Because you might never have needed to do this before, in this lab we ask you to write the cache simulator from scratch. The file csim .c does not exist in the starting repository; you must create it and write everything that goes in it.

The standard C runtime library contains many functions that are helpful when writing command-line tools. Functions that are useful for this lab, that you may not have needed before, include getopt, strtoul, strtok, fopen, fclose, and fgets. You can read more about these functions in their man pages: type “man  3  function -name” at a shell prompt. The 3 means “show me the documentation for a C function, not a shell command.” If you get an error saying “No manual entry for function-name in section 3”, or if the documentation that comes up doesn’t seem to be about a C function, try changing the 3 to a 2. (For historical reasons, the C library’s documentation is split across two “sections.”)

Man pages can also be read on the Web in several places:  we recommend looking first at https: //www.man7.org/linux/man-pages/index.htmlwhich has (a newer edition of) the same man pages found on the sharks. Another well-written collection of man pages can be found at https://man.openbsd.org/. These were written for OpenBSD, not Linux, but the C library works mostly the same.

If you would prefer to read a manual organized by topic, rather than with a page for each individual function, we recommend the GNU C Library Reference Manual, which is also on the Web: the table of contents is at https://www.gnu.org/software/libc/manual/html_node/index.html#SEC_Contents and an index of individual functions is at https://www.gnu.org/software/libc/manual/html_node/Function-Index. html.

The cache simulator you used in the first part of the lab (csim-ref) can be used as a reference for correct command-line behavior. If you run it with no arguments, it prints the following message:

Mandatory  arguments  missing  or  zero .

Usage :   ./ csim - ref   [ -v]  - s - E    -b - t  

./ csim - ref  -h

The   - s,  -b,  -E,  and   - t  options  must  be   supplied   for  all   simulations .

This message tells you that csim-ref requires arguments to do anything useful, and then tersely summarizes these arguments. The second and third lines of the message show two different valid command line invocations

of csim-ref. You can supply all four of the -s, -b, -E, and -t options, each of which takes a value, and optionally also the -v option, which doesn’t take a value. (The options are listed in one particular order, but csim-ref will accept them in any order, as long as each option is immediately followed by its value, if any.) Or you can supply the -h option, which doesn’t take a value, and nothing else.

The message goes on to tell you what each of the options mean.  -h makes csim-ref print the same message that it prints if you don’t give it any arguments (but without the initial “Mandatory arguments missing or zero” error). -v makes csim-ref be verbose and tell you details of what it is doing as it does it. These are both common options: many Unix command line tools interpret -h and -v the same way csim-ref does.

-s, -b, and -E specify the size parameters of the cache to be simulated. (The letters were chosen to match the s, b, and E notation used on page 617 of the CS:APP3e textbook.) The value for each is described as a “number.” -t specifies the file name of the memory trace to process. These options are specific to csim-ref; the same letter codes might mean something completely different to a different command line program.

Finally, csim-ref reminds you that you must supply all four of the -s, -b, -E, and -t options “for all simulations”—that is, csim-ref will only run a simulation if all four of these options are given. This is abnormal for Unix command line tools: “options” are supposed to be optional. But csim-ref really does need to know all four of these options’ values to run a simulation.

Incidentally, ‘2**n’ is a conventional way of writing ‘2n ’ when you can’t use superscripts. Sometimes people use ‘ 2^n’ for this, but in C that means XOR, so the authors of csim-ref didn’t want to use it here.

3.2.1 Processing Command Line Arguments

Your first task in this part of the lab is to write a program that accepts the same set of command line arguments that csim-ref does. Command line arguments are supplied to C programs as the argv array argument to main, which has argc elements.

# include  

int  main(int  argc ,  char  ** argv)

{

for   (int  i  =  0;  i  < argc; i++) {

printf (" Command   line  argument  %d  is  %s\n",  i,  argv[i]); }

return  0;

}

(Element 0 of argv is special. What does it contain?)

You need to find the various options, and their values, in the array, turn the numeric values from strings into machine numbers, and put all the values into variables. Don’t worry about doing anything with these variables yet, except maybe print them back out to make sure you got it right. You don’t have to duplicate csim-ref’s help message exactly, but you should print something useful when -h is the only argument.

You also need to detect incorrect invocations, such as:

● Not all of -s, -b, -E, and -t were supplied.

● The value for -s, -b, -E, or -t is missing.

● The value for -s, -b, or -E is not a positive integer, or is too large to make sense. (How many bits are there in an address? What does that tell you about the sum s + b?)

● An option (argument beginning with ‘ - ’) was given that isn’t in the list of recognized options.

● Arguments were given that aren’t options or values for options.

Play around with incorrect invocations of csim-ref; you will find that it gives errors for all of the above cases and perhaps others.

As a reminder, the C library functions getopt and strtoul may be helpful for this first task.

3.3 Parsing trace files

Your second task is to write a parser for memory access trace files like the ones you wrote in the first part of the lab, and arrange to run this parser on the trace file specified on the command line. As with the command line arguments, don’t worry about doing anything with the data you parse yet, except maybe print it back out to make sure you got it right.

Memory access traces are an example of a line-oriented file format. Refer to Section 2.2for a detailed description of trace file syntax. You do not have to be flexible when parsing—for instance, it’s fine to insist that there be exactly one space after the Op code. (However, it might be nice to be a little flexible. What does csim-ref do?)

You should detect and reject input that is completely incorrect, such as:

● Lines that don’t have all three of Op Addr,Size.

● Lines with trailing junk after Size.

● Lines where Op is neither ‘L ’ nor ‘ S’ .

● Lines where Addr or Size is out of range or not a number at all.

Line-oriented files are relatively easy to parse using standard C library functions. You can use fopen and fclose to access the file, fgets to read each line from the file, and, again, strtoul to turn strings into machine numbers. The strtok function may be useful in splitting up the line into fields, but it’s not strictly necessary. Remember that a string in C is just an array of characters: you can write things like ‘s[0]  ==  ’L’’ to find out if the first character in a string is ‘L’ .

Resist the temptation to use fscanf or sscanf. These functions may, on first glance, appear to save you a lot of trouble, but it is more difficult to detect incorrect input with them than with strtok and strtoul.

A skeleton of your parser function might look something like this:

/**  Process  a  memory - access   trace   file .

*

*     @param   trace       Name  of  the   trace   file   to  process .

*     @return                  0  if  successful ,   1  if  there   were   errors . */

int  process_ trace_ file ( const  char  * trace )

{

FILE  *tfp  =  fopen (trace ,  "rt");

if   (! tfp)  {

fprintf (stderr ,  " Error  opening   ’%s ’:  %s\n",

trace ,  strerror ( errno ));

return   1;

}

char   linebuf [ LINELEN ];    //  How  big  should  LINELEN  be?

int  parse_ error  =  0;

while   ( fgets (linebuf ,  LINELEN ,  tfp ))  {

//  Parse   the  line  of  text  in   ’linebuf ’ .

//  What  do  you  do  if  the  line  is  incorrect ?

//  What  do  you  do  if  the  line  is  longer   than

//       LINELEN - 1  chars ?

}

fclose (tfp );

//  Why  do  I  return  parse_ error  here  and  not  0?

return  parse_ error ;

}