Due Wednesday, 2 April 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. Assume the system will cache the memory being written and immediately write it back to main storage - write-through. If you update the cached line, also update main memory.
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) # repesents the memory location being accessed m(3) = @3
while j < 10
do
i = j
m(i) = A # Write contents of register A back to memory
j = j + 3
To create the array in main memory, interlace the least significant 6 digits your Z-id with the number 654321.
If your zid is z0137299, then the array would look like:
| 1 | 6 | 3 | 5 | 7 | 4 | 2 | 3 | 9 | 2 | 9 | 1 |
A four byte ( 2 cell by 2 line ) cache can be represented by the following table.
| segment tag | cell 0 | cell 1 | hit/miss | i cntr | code being exectued | ||
| line 0 | |||||||
| line 1 |
Click here, here, and here to view and print the three work pages containing a set of tables representing the main memory array described above and a set of tables representing the cache over a period of time. Your assignment is to fill in the current cache contents each time memory is accessed. 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 tables also include the current code line being executed and index counter value at each step. 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 page of memory and write the tag id for each above the table at the appropriate place. Remember memory address start at 0. Start the tag id at 0. Also treat the line numbering 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 above the cache table contains the memory contents before the command and the memory table below the cache table contains the memory contents after the command.
Remember, when moving data between the cache and main memory, both 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 modifiying 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.
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.
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.