CSE 378 - Autumn 2002

Machine Organization and Assembly Language Programming

Assignment #7

Due Monday, December 9

The goal of this assignment is to teach you to design and implement the datapath and control needed to build and evaluate a level-1 data cache.

Again, this is a group project. Your partner should be someone that you have not worked with before, and you should turn in one copy of the assignment.

For this assignment, you will be using SMOK to design and implement the level-1 data cache. You can install this cache in your Homework 6 machine.  You'll need the set-less-than operations, which you didn't have to implement for homework 6, so you should include it now. The cache should have the following configuration:

• 256 bytes (yes, it's small, but we want you to have some conflict misses)
• 2-way set-associative
• 8-byte blocks
• write-back memory update policy
• LRU block replacement policy

The cache controller will have to check the cache on each data memory reference, decomposing its address into tag, index, and byte offset components. Next, it should take the appropriate action, for example, change valid or dirty bits, replace blocks, etc., depending on whether the reference was a load or store and whether there was a cache hit or miss. If a miss, then the hardware should get the data from memory.

The cache controller should stall the rest of the machine on a miss, and fetch the appropriate data into the cache. A hit (and any necessary updates to your cache) should execute in one cycle, without stalling the machine. The design of the cache controller is the major component of this homework.

In addition to correctly handling data assesses, the data cache controller should also keep some statistics on data cache performance. Implement integer counters that will enable you to report on the following statistics:

• the miss ratio
• the read hit ratio
• the average memory access time
• the number of memory updates in this cache and in a same-sized cache with a write-through memory update policy.

For the purposes of debugging, you are encouraged to test your program on a smaller size cache.

Again, you should turn in a short written report (one page is sufficent). In it please describe how you built your cache design in SMOK, and how you tested it. Describe how your search algorithm works as well as where the array and three-symbol sequence is located in your smokmem file.  Include the data cache performance statsitics above that are based on the values in your performance counters. Also give the distribution of work between partners.

Turn in the code using the turnin form here . The written portion will be due in class. You should turn in your smok and smokmem files for the cached machine and sorting example. Please make sure to turn in any additional memory or support files. Also, turn in the assembly code for your sorting algorithm.

Hints:

• The widest SMOK can make memory is 4 bytes, so you'll need to use multiple memories to store the data and the tag, etc., for your cache. It's a good idea to encapsulate this in a container (which can handle the bit combining and extraction too), since you could then use two instances of it, one for each set.
• Since these caches are so small, you may use either register files or memories for them.
• You should be able to design your cache as a stand-alone component. If you find it easier, you may develop it in your single cycle machine and then install it into your pipelined machine.
• You'll want to initialize your cache so it has no valid data in it on startup. You can do this by loading a memory file of zeros.
• To get statistics, you can make counters (a register and an adder) or use debugoutputs and then count different cases at the end.
• If you're interested, you can mail me with a request for my solution to homework 6.