CSE 378 - Winter 2002

Machine Organization and Assembly Language Programming

Assignment #7

Due Wednesday, March 13 and Friday, March 15

This assignment has two parts, a cache design and implementation part and a set of problems taken from the book. The design and implementation part will give you your last practice in designing datapath and control with SMOK, and the problem part will give you practice in designing and evaluating caches and virtual memory mechanisms. Since this is the last assignment and it has two distinct portions, the SMOK part will be due Wednesday, March 13, and then you'll have two extra days to finish the problem part which is due Friday, March 15.

The Cache Implementation Part

For this assignment, you will be using your friend SMOK to design and implement a level 1 data cache. It 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 hardware will have to check the cache on each data memory reference, decomposing its address into tag, index, and byte offset components. Next, it takes 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 data cache controller will also keep some statistics on data cache performance, specifically,

• the number of references
• the number of hits
• the number of compulsory misses
• the number of block replacements

You should write a program to do sorting, but the choice of algorithm is up to you. It should sort an array of unsigned integers (but you can assume all numbers are less than 2³¹ so there are no sign issues). You should follow register conventions in writing this code -- you'll need the base address of the array and the size in the argument registers. The smokmem file you turn in should include an array to be sorted that contains 128 entries. At the end of your sorting algorithm, you'll likely not have everything written back to main memory--you wont be able to look at main memory and see if everything got sorted, because some data will still be in the cache. You should find a way to verify that the array is sorted, probably by forcing everything in the cache to be written back to memory.
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.

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

Again, there is 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 your sorting algorithm, and include details like the arguments to your algorithm, and where the array is located in your smokmem. 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 in memory and the tag, etc, information for your cache. Its 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'll need to implement a cache controller which will stall the rest of the machine on a miss, and fetch the appropriate data into the cache. The design of this is the major component of this homework. A hit (and any necessary updates to your cache) should execute in one cycle, without stalling the machine.
• 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.

The Problem Set Part

Do the following problems from the book.

• 7.14
• 7.15
• 7.19
• 7.20
• 7.27
• 7.28
• 7.32
• 7.33