Memory Reference Traces

A memory reference trace is simply a list of page numbers in the order that they are referenced. Because memory addresses are most commonly expressed in hexadecimal (base 16), the traces are lists of hexadecimal numbers. Because OOT does not appear to support hexadecimal numbers and all you need to do is compare two numbers for equality, you may treat them as strings. Alternatively, you can use the function strintok to convert the hexadecimal number as you read them in to integers.

REALLY NEW: Because it takes too long for some of you to run your programs on the first four big traces (qsort, lu, mm32, mm16), you are not required to hand in results for these traces. If you already have results, please hand them in. If not, please spend your remaining time working on the report instead of running the experiments.

NOTE: You are still expect to hand in results for a few memory sizes for the final 5 traces. They should not take very much time at all to run.

IMPORTANT: Do not print out the traces. Some of these files are pretty big and printing them will waste a lot of paper for no reason. One suggestion was to write the main program such that it prompts for the memory size and the name of the trace file. Then the main program can open the trace file and read from it. Do not hand in printouts of the trace files. The trace files that you create to test your program will be much smaller, and you should hand in the traces you create annotated to explain what you expect the trace to show.

Sorting: qsort
This trace is from running a program that uses the quicksort function in the Unix library. This trace has 524 page references, and 192 unique page numbers.
LU Decomposition: lu
The program used to generate this trace is an LU decomposition algorithm that was designed to run on a parallel processor. This trace has 41832 references, and 531 unique page numbers.
Matrix Multiply: mm32, mm16
Two traces of matrix multiply were generated. The first trace used 32x32 matrices. It has 67235 references to 1667 unique pages. The second trace used 16x16 matrices. It has 9075 references to 515 unique pages.

Another set of traces

These traces were constructed by hand. They are smaller and simpler than the other set of traces, and should be useful for comparing the behaviour of the three paging algorithms (LRU, FIFO, and your own invention).

These traces were inspired by a java applet that demonstrates a memory reference sting for different bits of code. Note that you cannot access this applet from the cdfpc lab because the applet is not on a University of Toronto web page. If you have a separate internet account with web access, you will be able to see it.

Linear Search: search
This trace has 16 unique pages and shows sequential accesses to the same page.
Sawtooth: sawtooth
This trace also has 16 unique pages and the pattern formed by accesses resembles a zig zag, sawtooth shape.
Diagonal Sweep: diag
This trace traverses 16 unique pages covering the lower diagonal matrix.
Row Matrix Multiply: rowmat
This trace mimics the matrix access pattern for a matrix multiplication wher the matrix is stored by row. Each of the three matrices is an 8x8 matrix where 8 elements (a row) are stored on a page. (Hence, there are 24 unique pages.
Column Matrix Multiply: colmat
This trace also mimics the matrix access pattern for matrix multiplication when the matrices are stored by column (one column per page). There are 24 unique pages in this trace.

Karen Reid

Last modified: Thu Jun 19 11:08:06 EST