How to know which element replaces which for a cache?
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.