There are four different programs that can be found in /u/csc369h/summer/pub/a3 on the teach.cs machines:
simpleloop.c – loops over an array allocated in the heap (You can also modify the code to run the same loop using stack memory)
repeatloop.c – loops over a heap-allocated array multiple times
matmul.c – naive matrix multiply with the ability to change the element size to change the memory access behaviour
blocked.c – a more memory aware matrix multiply that should exhibit a better hit rate under some page replacement algorithms
Valgrind has an option that will allow you to print out the memory reference trace of a running program, and you can see how we use it by looking at
the shell script run.sh .
There are two aspects of the output of valgrind that are unsatisfactory for our purposes. First, it includes the entire program memory trace including
loading the program and libraries into memory which makes is harder to focus on the access patterns of the algorithm. To address this problem, we
have added special variables to the programs whose only purpose is to serve as a marker, so that we will only keep the reference trace between the
two markers. The python program trimtrace.py carries out this task. These address level traces for the four programs are stored in
/u/csc369h/summer/pub/a3/traces/addr-*.ref . These are the trace files that you will analyze in Part 1.
This still produces a massive trace because it displays every memory reference, even if they are to the same page. The fastslim.py program
reduces the size of the traces and focus on page accesses. These traces can be found in /u/csc369h/summer/pub/a3/traces/page-*.ref . You will
use these traces to run your page replacement algorithms in Part 2.
You can also find all traces in compressed archive format at /u/csc369h/summer/pub/a3-traces.tar.gz . Use scp or rsync to download them to your
machine. The file can normally be unpacked by a program on your system by clicking on it, or you can use tar -xzf a3-traces.tar.gz .
The directory includes all of the code to build and generate the traces, so that you can try it out on different programs if you like. If you want to do
this, you will need to copy the files to your account. Remember not to commit trace files to your repo because some of them are quite large.
Your task is to read the programs to get a picture of how they are using memory and write a short program in the language of your choice to analyze
the trace output. Then compare your counts to the program to match the access pattern to variables and operations in the program.
The resulting address trace files have the following format, where the first character indicates whether the access is an Instruction, Store, Load, or
Modify, the second value is the address in hex, and the third value is the size of the access:
Your analysis program will translate each memory reference into a page number assuming pages are 4096 bytes. It will output a table of each
unique instruction pages with a count of the number of accesses for each page, and a table of unique data pages with a count of the number of
accesses for each page. Each of the two tables must be sorted in descending order by the number of accesses.
For example, the above snippet will produce the following:
What to submit for Part 1:
The program you wrote to produce the table with instructions for how to run it on the teach.cs machines.
A text file called analysis.txt containing the following information about each of the provided traces:
The number of instruction pages (I).
The number of data pages (S, L, M).
In analysis.txt , identify which pages are accessed the most and explain briefly which variables (data) or code from the program might be
stored in these pages. Identify and explain any notable patterns you see in the tables with the number of accesses per page.
Note: The intent is that you should be able to do this exercise in a couple of hours. You do not need to write more than a few sentences.