CSE 378 - Spring 1999

Machine Organization and Assembly Language Programming

Problem Set #8

Due Friday, June 4, 1999

Complete the following program, and turn in both electronic and paper copies of your program by the start of class on Friday, June 4.

For this assignment, you will be using SPIM and MIPS assembly language to write a simple trace-driven simulator for assessing cache performance. Trace-driven simulation is commonly used to assess performance of memory hierarchy designs.

A general simulator works as follows.

Given:

A trace (sequence) of memory references
One or more cache descriptions (I-cache, D-cache, cache hierarchy) including size, associativity, block size, and replacement policy for each cache
A write policy
Access times of components in the memory hierarchy

Process each memory reference, decomposing it into tag, index, and offset components. Check if the reference hits in the appropriate cache (note that the simulator does not actually bring data in or out of its simulated cache; rather, it pretends that it has the data there). Take the appropriate action (change valid/dirty bits, replace blocks, etc.) and record the statistics.

The output will be a set of statistics, including read hit ratio, write hit ratio, average memory access time, and so forth.

Your assignment will simulate a D-cache only, and will do the following:

Given as Input:

A series of data references with the following format: <operation> <address> where operation has value 1 for read and 2 for write, and address is a 32-bit byte-address. The trace is terminated with the pair 0 0.

at most 1024 memory references

You will model a 256 byte, 2-way set-associative cache, with a block size of 2 words, a write-back policy, and an LRU replacement algorithm.

You will output to the SPIM console:

Total number of data references
Number of compulsory (cold-start) misses
How many references hit in the D-cache
Number of blocks you needed to write back

For the purposes of debugging, you are encouraged to test your program on smaller cache sizes and smaller input traces first.

Input specification:

Input will be given as a series of integer pairs (at most 1024 pairs), where each pair will correspond to <load/store> <address>. For example,

1 20 1 40 1 32 2 23 1 34 1 20 1 22 0 0

means

<lb 20> <lb 40> <lb 32> <sb 23> <lb 34> ...

You have to read this as a series of integers (using system call for read_int). Note that you can now disregard the line in the original assignment that says "operation is a byte... address is a word" because everything will (by default) be read as a word.