CS/ECE 354, Assignment 3

Description

The purpose of this assignment is to understand more about how caches work,
learning a bit about simulation along the way,
and picking up introductory skills in generating a Makefile.

Please read this entire assignment specification before starting
on the first step.

Description

For this assignment, you will use a program called pin
that produces cache performance statistics,
given cache parameters and an executable.

pin runs the executable to internally produce a series of
address traces.
These are the ordered set of addresses that a program generates
as it runs.
They represent the addresses read from or written to as the program runs.
Each address may represent a read for the instruction fetch
or a read or write to a variable stored in memory.

The address traces are then used internally with a cache simulator.
The cache simulator is a program that acts as if it is a cache,
and for each trace, does a look up to determine if that address
causes a cache hit or a cache miss.
The simulator tallies the hits/misses, and when it has completed
simulation of all the traces, it prints these statistics for
you.

To run a simulation, use a command line similar to

/p/course/cs354-common/public/cache/pin -t /p/course/cs354-common/public/cache/source/tools/Memory/obj-ia32/allcache.so -is 16384 -ia 1 -ib 64 -ds 16384 -da 1 -db 64 -- yourexe

In this command, you would need to replace “yourexe” with the name of your executable file.
The first time you run this command, you should copy,
paste, and then alter this command,
instead of typing it in, to reduce errors.
The arrow keys on your keyboard can be your friend here,
before you generate a Makefile.
Once you put a target for this command line into your Makefile,
your life gets easy!

6 of these command line arguments specify cache parameters to pin.
The simulator presumes separate I-cache and D-cache.
The I-cache holds only the machine code instructions,
as read when doing an instruction fetch.
The D-cache holds all other data read or written while a program runs.

For the I-cache, specify

• -ia 1
  
  This causes the set associativity of the cache to be 1,
  or direct mapped. This is the only value we will use in this assignment.
• -is N
  
  Substitute a power of 2 for N.
  This sets the capacity for this cache.
  For all our simulations, use a 16KB (16384) size.
• -ib N
  
  Substitute a power of 2 for N.
  N is the number of bytes per block.
  You will be changing this parameter in this assignment.

For the D-cache, specify

• -da 1
  
  This causes the set associativity of the cache to be 1,
  or direct mapped. This is the only value we will use in this assignment.
• -ds N
  
  Substitute a power of 2 for N.
  This sets the capacity for this cache.
  For all our simulations, use a 16KB (16384) size.
• -db N
  
  Substitute a power of 2 for N.
  N is the number of bytes per block.
  You will be changing this parameter in this assignment.

As you work your way through this assignment, you will be
answering questions that are in the file:

   /p/course/cs354-common/public/html/handouts/a3questions

Copy this file to your own directory, and add your answers to this file.
The file will be turned in.

Write a very small C program called cache1D.c
that sets each element
of an array of 100,000 integers to the value of its index.
The statement that sets a single array element will be something like

  arr[i] = i;

The resulting executable program will be used with pin
to generate statistics about cache usage for your analysis.
To make the analysis easier, the C program is required to

• Declare the array as a global variable, so the declaration will
  be outside of main() (and prior to main()
  within the source code file).
  This requirement will cause the array to be within the global data segment,
  and not on the stack.
• Place a for loop inside main()
  to set each element of the array.
  One array element is set during each iteration of the for loop.

Compile your program with

  gcc -o cache1D cache1D.c -Wall -m32

Notice that this command differs slightly from the compilation
that we did for assignment 1 this semester.
It does NOT have the -O option, so
the compiler is not going to do optimizations. It is important that you do not use the -O option.
Use these same compiler options for all the programs in this assignment.

Before you go any further, it is time to figure out how to do
this compilation using
make: a powerful tool that helps us to automate our
compilation, as well as automate many other sets of commands.

To help you put together a Makefile, try one or more of

• 
  A brief tutorial about make
  by Hector Urtubia can start you on your way.
• Within the online textbook written by our own Arpaci-Dusseau professors,
  see the
  
  Laboratory: Tutorial.
  You’ll benefit from pages 1-8 of this tutorial, although pages 5-8 specifically
  discuss make.
• University of Maryland has a nice
  
  introduction to make;
  especially helpful will be to look at the topic of dummy targets.
  You will want to add a dummy target for each of your simulations.
• UW-Madison alumni Professor Newhall explains
  
  using make in helpful and concise prose.

Make sure that you have a single target to make the cache1D
executable.
(And for each 2 subsequent programa, add a new target, and then
use make. You will be turning in your Makefile.
Please name your target with the name of the executable,
which should be the same as your source code, but without
the .c file name extension.)

Run the 3 simulations needed to answer the questions in the
a3questions file.
Then, answer the questions.
Running the simulations will be amazingly easy, if you
put a target for each block size simulation into your Makefile!
So, do it!

Repeat what you did for the 1 dimensional array with two
programs that set elements of a 2-dimensional array.
Many students will not have used 2-dimensional arrays in C before;
the K&R book, section 5.7-5.9, starting on page 110 will be a
good reference for declaring and using 2D arrays.

First, write a C program called cache2Drows.c that
sets each element of a 3000 row by 500 column array of
integers to the sum of the row index and the column index.
The statement that sets an element will be something like

  arr2d[row][col] = row + col;

Use a set of nested for loops,
where the inner loop works its way through the elements of single row of
the array, and the outer loop iterates through the rows.

Run the cache analysis requested in the
a3questions file.

Second, write another C program called cache2Dcols.c that
does the same thing as cache2Drows.c did,
but in a different order.
This program has the inner loop work its way through the elements of a single column
of the array, and the outer loop iterates through the columns.
If you truly understand your code, it should be close to trivial
to copy cache2Drows.c and modify it to become
cache2Dcols.c.

Last step will be to figure out, understand, and explain
why these 2 programs (that accomplish exactly the same thing)
result in different cache performance.

Handing In the Assignment

We will use your Makefile to compile.
We will compile the 3 source files using following commands:

make cache1D
make cache2Drows
make cache2Dcols

Make sure the targets in your makefile are named appropriately so
that the 3 make commands work.
Copy all these files into your handin directory.
Your handin directory for this project is

/p/course/cs354-common/public/spring15.handin/login/p3

where login is your login.

If you are working as part of a pair,
you must turn in an extra file.
This file will contain the names and sections of both students
in the pair.
As an example, if Kevin worked with Haseeb on this assignment,
the contents of the extra file for both Kevin and Haseeb would be

Kevin Zhang   section 1
Haseeb Tariq  section 2

The name of this file is specialized to help the 354 automated
grading tools identify who worked together.
This file name is composed of the CS logins of the partners
separated by a period.
The file name is of the form <login1>.<login2>.
Kevin’s login is kzhang, and Haseeb’s login is
haseeb.
The file name that both use will be kzhang.haseeb ;
please have both partners use the same file name.
It does not matter which partner’s name is first within this
file name.

Requirements

1. Include a comment at the top of the source code of both programs with your
   name and section
   (and your partner’s name and section, if working in a pair).
2. Use the instructional Linux machines for this assignment!
   A penalty will be imposed for any program that was obviously edited
   on a Windows machine and transferred to the Unix machines
   for turning in.
   It is annoying to see Windows line endings (^M) at the
   end of every line. Points will be taken off for such mistakes.
3. Your programs must compile
   on an instructional Linux machine as indicated in this specification
   without warnings or errors.
   When grading, we will use your Makefile, so make sure that it works!

About Copying Code and Academic Misconduct

Don’t cheat. Read this link carefully.

Do not post your assignment solutions (or drafts) on any
publicly accessible web sites.
This specifically includes GitHub.
It is academic misconduct to post your solution.

For almost any C program that does something useful,
someone has already written this program and
further, has posted it for others to use.
These programs do not do much that is useful,
and are not likely posted anywhere.
Still, it is academic misconduct for you to copy or use some or
all of a program
that has been written by someone else.

The penalty for academic misconduct on this assignment
(and all CS/ECE 354 assignments)
will be a failing grade in the course.
This penalty is significantly more harsh than if you simply do not
do the assignment.
You will gain much more by doing the assignment
than by copying, possibly modifying,
and turning in someone else’s effort.