MIPS - Cache & Associativity

We learned in class that since matrix multiply accesses both the columns and rows of a matrix,that one or the other will not fit nicely into our caches; that is, either the stride of the rows or thestride of the columns will be big and therefore will have poor locality.We want to use the MARS cache simulator (under tools tab) to show that we can improve theperformance of caches by 1) increasing their associativity and 2) by modifying our program to fitbetter in the cache.

Part 1. Take your matrix multiply program C = AxB and change it to use 8x8 matrices. Dont read in the matrices, just initialize them in the array declarations. First run it with a cache containing 64 words direct mapped.Then run it with 64 words 2-way set associative. Change the cache size and/or block size ifnecessary so that when you change the associativity (but not the size keep the total cachesize the same!) between runs that the performance improves (lower miss rate).

Part 2.

Now block your matrix multiply routine to do the 8x8 multiply using blocking with four(4) 4x4matrices (4x4 blocks).Stated more graphically,For A, B and C matrices,First compute C = A*B and compare the performance for direct-mapped and 2-way setassociative caches, then using 4x4 blocks, compute

A1 | A2 B1 | B2 C1 | C2

-------- * -------- = -------- = C

A3 | A4 B3 | B4 C3 | C4

A1, A2, B1, also matrices

Using the same cache size that you used in part 1, again, compare the result using direct-mappedand 2-way set associative. Change the cache size and/or block size if necessary so that theresult improves after blocking. Comment on the results. Upload the program and include the cache parameters you used so that I can recreate your result.