2-way Cache access assignment - 60 points

Due Friday, 7 November 2014 - In class by start of class.

Below is the pseudo-code for a simple program that will access each element of a data array stored in memory. The program will read and accumulate the values stored in memory. It will occasionally write the current accumulation back to memory. If the program writes to a memory location it has not read from (not already in the cache), assume the system will write directly to memory without caching it. If you update a memory location that is currently in the cache, also update main memory - write through. All math is regular decimal based math.

i = 0 # i is an index register in CPU
j = 0 # j is a counter register in CPU
A = 0 # A is an accumulator style register in CPU
m(i) # represents the memory location being accessed m(3) = @3

A = 0;

for j = 0 through 2

do
  for i = 0 through 2 (3 iterations)

  do
    A += m(i+j);
    A += m(i+j+14);
  done

  m(j+8) = A; 

  A = 0;
done

On the work sheets (accessible via the links below) you will find a snapshot of the real memory. Fill in the 1st 6-7 bytes of the main memory with the numeric portion of your z-id. Don't worry about empty memory cells, we either won't be accessing them or they are for write-through.

If your z-id is z912730, then the memory would look like:

Memory @	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Data	9	1	2	7	3	0							0	0	1	2
Memory @	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
Data	3	4	5	6	7	8	0	0	0	0	0	0	0	0	0	0

There will also be several images of a eight byte ( 2 cell by 2-way by 2 line) cache like the exampel below. Remember each cell is a 1 byte storage in the cache. This is a 2-way cache meaning that you can actually have two different line 0s in the cache at the same time.

	segment tag	cell 0	cell 1		segment tag	cell 0	cell 1		hit/miss	i cntr	code being executed
line 0
line 0

Click here, here, and here to view and print the three work sheets for the assignment. Setting your fonts to Times Roman, size = 16 or using scaling in preview to print mode should allow the each worksheet to print on a single page.

You are to "execute" the code above. Each time a memory location is accessed, you will fill in the contents of the cache tables. Specify the tag in binary but use decimal for the data cells. In addition to the tag and cell fields, the cache tables contain fields to note whether a particular access to the cache line was a hit or miss. You are to indicate H for hit, M for miss, or - if the line of the cache was not accessed. The h/m flag applies to either copy cached. Finally, cirlce the byte in the cache being accessed at that point in the program.

Each image of the cache also includes the current code line being executed and the values of index counters at each step. These are always stated on the 1st line of the cache image and their position does NOT indicate which cache line is being accessed.

First fill the main memory table as described above. Draw a heavy line between each segment of memory and write the tag id for each above/below the memory table at the appropriate place. Remember memory address start at 0. Start the tag id at 0. Also, remember there are only 2 bytes on a line.

Also, in each segment, draw a line to distinguish each block of main memory that would be treated as a cache line and specify the line number as 0 and 1.

Then start executing the program code provided. When a memory access occurs, determine the tag id and cache line represented by the address of the memory being accessed.

Using that information, fill in the appropriate cache line. Assume the cache line shows contents after any action taken. The memory table at the top of the work sheet represents the memory contents before the commands on the work sheet have run and the memory table at the bottom will represent the memory contents once all the commands on that work sheet haver run. I have limited writing cack to memory to single command on each work sheet.

Remember, when moving data between the cache and main memory, all cells of the line need to be moved but only for the line being accessed.

Record the tag of the memory being accessed. If this tag is different from the tag already recorded in the cache or the cache line is empty (invalid), it is a miss and you should record this in the appropriate field.

When modifying data in cache lines, use write through. If an instruction changes the contents of a cached memory cell, change the cached cell and its match in main memory. Remember, changes to A, i, and j do NOT affect the contents of the cache or main memory, only access to a memory location, m( x ).

If a main memory reference can not be matched in the cache, it is a miss and the new data must be fetched into the appropriate cache line. If you have been using write through correctly, you can just fetch the new line of data into the cache. Remember to change the tag field at the same time.

If both copies of a particular line are full, use FIFO (first in first out) to select which line to replace.

Print out the three tables and fill them in. To do the complete program may take more than the three sheets of tables but three will be sufficient to simulate the cache function.

Remember to draw the contents of both cache lines in each instance of the cache table even if the values have not changed.