Cache access assignment - 60 points

Due Friday 3 April 2015 - 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 won't be accessing them.

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	0	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 the 8 byte ( 4 cell by 2 line) cache like the example below. Each cell in cache is 1 byte storage.

	segment tag	cell 0	cell 1	cell 2	cell 3		hit/miss	i cntr	code being executed
line 1
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 should allow the each worksheet to print on a single page. In Firefox, you can also preview the printed page and scale to fit the 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. Also, cirle byte in cache line that is actually being accessed by program.

Each copy of the cache includes the current code line being executed and the values of index counters at thee particular time in the program. These are always stated on the 1st line of the table 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, 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 have run. I have limited writing back 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.

Remember to CIRCLE THE BYTE in the cache being accessed by the program.

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.