Lab 4: Cache Geometries
Assigned | Wednesday, November 18, 2015 |
---|---|
Due Date | Monday, November 30, 2015 at 5:00pm |
Files | lab4.tar.gz |
Submissions | Submit a PDF file containing your answers and your modified cache-test.skel.c file here. |
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
andj
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:
- Compile and measure each of the Java implementations as they come in the distribution. Compile and measure the C program with and without optimizations.
- Edit each source file to uncomment the assignment to
array
src
. Re-compile and re-measure. - Edit to switch the order of the
i
andj
loops. Recompile and re-measure. - Edit to re-comment out the statement assigning to
array
src
(with thei
andj
loops still reversed). Re-compile and re-measure. - 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:
- 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.
- 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 200 copies of
these tables easier if they're all laid out the same way.)
Array Size Performing
src
assignment?App Time with i
thenj
Time with j
theni
2048 No Java JavaInteger C Optimized C - Q&A
Answer these questions:- What are the source code differences among the two Java implementations?
- 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.)
- [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
and compile/run unoptimized and optimized.printf("Sum is %d\n", sum);
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 attu, the CSE VM, the lab computers, or your own personal 64-bit computer.
Instructions
Specifically, each of these "processors" is provided as an object
file (.o file) against which you will link your code. See the file
mystery-cache.h
for documentation of the function interface
that these object files export. 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. 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
and the files will be extracted into a new subdirectory of the current
directory named lab4. 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 - i.e. 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
.
Tips
Note that the exact style of for
loops with which you may be
familiar from Java was not allowed in C until a later standard. Instead of
writing:
for (int i = ...; ...; ...) { ... }
write this instead, declaring your loop variable outside the loop header (and at the top of your function body):
int i; ... for (i = ...; ...; ...) { ... }
There is also a flag to tell the compiler to allow the first version, but the second version will work either way.
Submitting Your Work
Part I: Please turn in a PDF file containing your answers to Part I to the Catalyst Drop Box for this assignment. We will not accept submissions that are not in PDF format.
Part II: Submit your modified version
of cache-test-skel.c
to
the
Catalyst Drop Box for this assignment.