Lab 4: Cache Geometries

Assigned	Thursday, May 12, 2016
Due Date	Friday, May 20, 2016 at 11:59PM
Files	lab4.tar.gz
Submissions	Submit (1) a PDF file containing your answers and (2) your modified cache-test.skel.c file using the course's Assignment Drop Box.

Part I: An Experiment in C and Java

Learning Objectives

• Evaluate a claim made in the lecture slides that two seemingly equivalent ways of writing a program can have vastly different performance.
• Get a feel for the relative performance of Java and C.
• Get a feel for the effectiveness of turning on C compiler optimizations.

Overview

Let's test the claim that understanding the memory hierarchy can be useful in writing efficient programs. An example in the first-day lecture slides said that interchanging two loops has no effect on the correctness of the results, but can give a 21x difference in performance. Let's see about that.

Here's the important part of the code. It computes exactly the same thing no matter which of the two loops is outermost.

int rep;
int i, j;

// ...

    for (i = 0; i < 2048; i++) {
        for (j = 0; j < 2048; j++) {
            // src[i][j] = i * rep;
            dst[i][j] = src[i][j];
        }
    }

You will download a set of three tiny programs—one in C and two in Java—that contain those loops. You'll compile them and time how long it takes them to run. For the C program, you'll compile both with and without compiler optimizations enabled, so in total you will have four programs to compare at a time (two Java programs + one C program compiled two ways).

You will do this several times, making small modifications to see what differences they make—how the choice of language affects performance and how effective the compiler can be at optimizing your code when you:

• interchange the order of the i and j loops
• uncomment the commented line
• change the size of the array being copied from 2048 x 2048 to 4096 x 4096 (change both the array size and the bounds of the loop that copies the arrays)

You'll run each version of the code and measure how long it takes to complete. With all the permutations (4 executables x 2 loop orderings x 2 commented/uncommented line versions x 2 array sizes), that's 32 versions. (It will be easy—just read all the way through these instructions first.)

You'll then turn in a short document, described below, in which you summarize your test results and answer a few questions.

Details

Downloading

Fetch the files, which are provided as a tar archive: lab4.tar.gz . Save them to a directory in which you want a new directory (containing the files) created.

Now issue the command tar xzf lab4.tar.gz. That will un-archive the files, creating directory lab4. In that directory you will find these files (as well as files for part two):

File	Description
cacheExperiment.java	Rows 'Java' in your tables of test results (see below)
cacheExperimentInteger.java	Rows 'JavaInteger' in your tables
cacheExperiment.c	Rows 'C' and 'Optimized C' in your tables
run.pl	See “Automating” below

Compiling

To compile the C program without optimizations, cd to the lab4 directory and type:

gcc -Wall cacheExperiment.c

That produces an executable named a.out. To compile the program with optimizations, type:

gcc -Wall -O2 cacheExperiment.c

(that is the capital letter o, not the number zero), which also produces an executable called a.out (overwriting the previous one).

To run a.out, you would type ./a.out. (Note: You don't actually want to do this. See the next heading about obtaining timings.)

To compile cacheExperiment.java type:

javac -Xlint cacheExperiment.java

which produces cacheExperiment.class. Do the same thing for the other Java programs.
To run it, type:

java -Xmx640M -cp . cacheExperiment

(Again, this is a command you need to time, so read on.)

Timing

On Linux, you can measure the CPU time consumed by any execution using the time program. For example:

$ /usr/bin/time ./a.out
0.12user 0.03system 0:00.16elapsed 95%CPU (0avgtext+0avgdata 66704maxresident)k
0inputs+0outputs (0major+8287minor)pagefaults 0swaps

This executes the command (./a.out) and then prints information about the resources it consumed. (Type man time to obtain more information about the time program and ways to format its output.)

The only information we'll use is the user time ('0.12user', meaning 0.12 seconds of CPU time consumed while not in the operating system) and the system time ('0.03system', meaning 0.03 CPU seconds spent by the operating system doing things for this application). The measured time we want is the sum of those two. For this example, the measured time would be 0.15 seconds.

Measured times are likely to vary quite a bit from one run to the next, even without changing anything. (This course will explain some of the reasons why.) Note that all the programs wrap the two array-copying loops with another loop that causes the copy to be performed 10 times. One goal of that is to reduce the amount of variability in the measurements.

Automating

The distribution includes an optional script, run.pl, that automates some of the chore of running the four executables and gathering measurements. To run it, type ./run.pl. It compiles each of the source files (and cacheExperiment.c twice; with and without optimizations), runs each with the time command, and reports the sum of the user and system times.

run.pl should work in most environments (including the CSE virtual machine). It should work for you, but it is an optional (and unsupported) tool.

So, to summarize:

1. Compile and measure each of the Java implementations as they come in the distribution. Compile and measure the C program with and without optimizations.
2. Edit each source file to uncomment the assignment to array src. Re-compile and re-measure.
3. Edit to switch the order of the i and j loops. Recompile and re-measure.
4. Edit to re-comment out the statement assigning to array src (with the i and j loops still reversed). Re-compile and re-measure.
5. Edit to put the loops back in the original order. (At this point the code is the same as it was when you first fetched it.) Change the code to copy an array of size 4096 x 4096 (change both the size of the arrays and the loop bounds). Then repeat steps 1–4 above.

Test Results

Collect your results in a short PDF document with the following sections:

1. The Test System
   • A short string describing the system you ran on (e.g., “my Mac laptop” or “the CSE home VM on my Windows laptop” or “lab Linux workstation”).
   • What the CPU is on that system. You can obtain that on any Linux system by issuing the command cat /proc/cpuinfo. Give us the model name, as listed.
2. Test Results Four tables of numbers giving the measured CPU time consumed when executing each of the four executables under the different configurations. Each table should look like this. (It doesn't have to be exactly this, to every detail of formatting, but please keep your information in the same order; it makes reading 100 copies of these tables easier if they're all laid out the same way.)

   Array Size	Performing src assignment?	App	Time with i then j	Time with j then i
   2048	No	Java
   		JavaInteger
   		C
   		Optimized C

3. Q&A
   Answer these questions:
   1. What are the source code differences among the two Java implementations?
   2. Pick a single pair of results that most surprised you. What is it about the results that surprised you? (That is, from the 32 measurements you collected, pick one pair of measurements whose relationship is least like what you would have guessed.)
   3. [Optional extra credit] None of these programs appear to actually do anything, so one is tempted to optimize them by simply eliminating all code (resulting in an empty main()). Is that a correct optimization? Related to that, try compiling this C program, with and without optimization, and then time running it:

      #include <stdio.h>
      
      #define SIZE 1000000
      
      int main() {
          int i, j, k;
          int sum = 1;
      
          for (i = 0; i < SIZE; i++) {
              for (j = 0; j < SIZE; j++) {
                  for (k = 0; k < SIZE; k++) {
                      sum = -sum;
                  }
              }
          }
      
          printf("hello, world\n");
      
          return 0;
      }
      

      Now replace the printf line with

      printf("Sum is %d\n", sum);

      and compile/run unoptimized and optimized.

      It may also be interesting to explore what happens to this code using the Compiler Explorer tool we told you about earlier. Try changing sum = -sum to some other operation, such as sum++ and tell us what happens.

Part II: Inferring Mystery Cache Geometries

Learning Objectives

• Gain basic familiarity with cache geometries and how different associativities and line sizes present themselves.

Overview

Chip D. Signer, Ph.D, is trying to reverse engineer a competitor's microprocessors to discover their cache geometries and has recruited you to help. Instead of running programs on these processors and inferring the cache layout from timing results, you will approximate his work by using a simulator.

This lab should be done on a 64-bit machine. Use the CSE VM, attu, CSE lab computers, or your own personal 64-bit computer.

Instructions

Each of the “processors” is provided as an object file (.o file) against which you will link your code. The file mystery-cache.h defines the function interface that these object files export. It includes a typedef for a type addr_t (an unsigned 8-byte integer) which is what these (pretend) caches use for "addresses", or you can use any convenient integer type.

typedef unsigned long long addr_t;
typedef unsigned char bool_t;
#define TRUE 1
#define FALSE 0

/** Lookup an address in the cache. Returns TRUE if the access hits,
    FALSE if it misses. */
bool_t access_cache(addr_t address);

/** Clears all words in the cache (and the victim buffer, if
    present). Useful for helping you reason about the cache
    transitions, by starting from a known state. */
void flush_cache(void);

Your job is to fill in the function stubs in cache-test-skel.c which, when linked with one of these cache object files, will determine and then output the cache size, associativity, and block size. You will use the functions above to perform cache accesses and use your observations of which ones hit and miss to determine the parameters of the caches.

Some of the provided object files are named with this information (e.g. cache_65536c_2a_16b.o is a 65536 Byte capacity, 2-way set-associative cache with 16 Byte blocks) to help you check your work. There are also 4 mystery cache object files, whose parameters you must discover on your own.

You can assume that the mystery caches have sizes that are powers of 2 and use a least recently used replacement policy. You cannot assume anything else about the cache parameters except what you can infer from the cache size. Finally, the mystery caches are all pretty realistic in their geometries, so use this fact to sanity check your results.

You will need to complete this assignment on a Linux machine with the C standard libraries (e.g. the CSE VM, attu). All the files you need are in lab4.tar.gz. To extract the files from this archive, simply use the command tar xzf lab4.tar.gz to extract the files into a new subdirectory of the current directory named lab4. However, you presumably already did this for Part I and you do not need to do it again. The provided Makefile includes a target cache-test. To use it, set TEST_CACHE to the object file to link against on the command line. That is, from within the lab4 directory run the command:

make cache-test TEST_CACHE=cache_65536c_2a_16b.o

This will create an executable cache-test that will run your cache-inference code against the supplied cache object. Run this executable like so:

./cache-test

and it will print the results to the screen.

You may find this script that makes and runs cache-test with all the object files useful. But you are not required to use it and it is provided without support.

Your Tasks

Complete the 3 functions in cache-test-skel.c which have /* YOUR CODE GOES HERE */ comments in them.

Additionally, determine the geometry of each of the four mystery caches and list these in a comment, along with your name, at the top of your modified cache-test-skel.c.

Submitting Your Work

Part I: Submit a PDF file containing your answers to Part I to the course's Assignment Drop Box. We will not accept submissions that are not in PDF format.

Part II: Submit your modified version of cache-test-skel.c to the course's Assignment Drop Box.