How to calculate access time for a cache simulation

I think ANSI C dictates that multi-dimensional arrays are allocated to memory in row-major order. That means elements in a row are contiguous in memory, which is to say a[0][0] is adjacent to a[0][1] in memory.

The way associative caches work is that some of the address bits tell you which line of the cache the item is on, and some other bits of the address tell you which set the item goes in. You need to know the line-width to know how many bytes are on a line, and you need to know how many lines each set contains.

Lets say you didn't have an associative cache (i.e. you had associativity = 1). Lets also say you had 32 bytes per line, and 16 lines. So your total cache size would be 16 * 32 = 512 bytes. If your a[0][0] was allocated to memory such that it was on a cache line boundary (i.e. it's address was divisible by 32), then the line it brought in would contain a[0][0] through a[0][31] assuming the cardinality of the second dimension was that big. If on the other hand the cardinality of the second dimension was say 16, the a[0][0] row would contain a[0][0] ... a[0][15], a[1][0] ... a[1][15]. And so on.

However your array is dimensinoed, after 512 bytes, you're going to be full and the 513th byte offset from a[0][0] is going to blow away the row containing a[0][0]. Unless your cache is associative. In that case, your 513th entry is going to go into the next set, and that's going to keep happening for as many ways associative your cache is. Only after exhausting the sets will you wrap back around and blow away a[0][0]. Now, obviously for the same size cache, increasing associativity will effectively reduce the number of lines per set. So the access pattern determines whether it's helpful or not. Mileage may vary.

When they say that the cache block size is two words, that means that 2 words, or 8 bytes of data is transferred to the cache whenever a miss occurs. You can think of main memory as being divided into groups of 8 bytes, on 8-byte boundaries (0-7, 8-15, 16-23, etc.). Whenever any byte in one of those groups is accessed, the entire group is loaded into a cache block.

So, for example, when byte 12 is accessed, all of the bytes from 8 to 15 are loaded into the cache. As long as that block remains in the cache, any subsequent accesses to any of those bytes will result in a cache hit, rather than a miss.

Note that the cache can only hold a total of 8 blocks (16 words / 2 words per block). This means that if you access a byte that's in a ninth block, you're going to have to remove a block from the cache first. Selecting which block to remove is an entirely separate topic that is the subject of much debate. Since the problem doesn't specify a cache replacement strategy, I'm guessing that it doesn't matter for this particular example.