Three way set associative cache with LRU replacement

Question

So I am going through a homework exercise, and I am not understanding the solution to the problem. We are given a sequence of memory references and we are to use a three-way set associative cache with two-word blocks and a total size of 24 words. (For reference question is here). According to their solution, the offset is 1 bit, index is two bits, and the tag is the remaining bits.

First, to make sure I understand, there are four sets because each set contains 3 blocks (three way set associative), and there are a total of 12 memory references, so 12/3 = 4 sets, so the indices in binary would be 00, 01, 10, and 11 each with three "slots" for data.

Second, the memory references are from another problem where it is stated that the references are given as "word addresses". Does this mean that they are word addressable, not byte addressable? If so, I thought that since the cache has two word blocks (8 bytes) then the offset would be 3 bits (2^3)? What is the significance of having two-word or one-word blocks?

My main difficulty is understanding how offset bits are calculated in different cache mappings. I understand the replacement method in that the last recently used element is the one to be replaced by an incoming element.

Answer 1

While the problem does not specifically say so, you can typically assume word-addressable memory when dealing with this kind of cache problem. Thus, in order to calculate the size of the offset, you need to know the size of a block in words, which in this case is given as 2. Thus, you need 1 bit (clog2[block_size_in_words]) to determine which of the 2 words in a block you are addressing, as the problem solution uses.

Your analysis for the number of sets seems accurate, but just to be clear: as we know the total size of the cache is 12 blocks (24 words / 2 words per block) and there are 3 blocks per set, there must be 4 sets (12 blocks / 3 blocks per set). Thus, you need 2 bits (clog2[number_of_sets]) to index the sets.

Its important to note that the size of a word is architecture-dependent. A word can be any number of bits long, typically 8, 16, 24, 32 or 64 depending on the processor (See: http://en.wikipedia.org/wiki/Word_(computer_architecture)). The problem does not define a word size, so you cannot determine how big the blocks are in bytes. As you said, they could be 8 bytes with a 32-bit word, but they could be 4 bytes with a 16-bit word. As the problem did not specify the word-size, you cannot assume you know it unless it is specified somewhere else that applies to the problem (ie, the professor says to always assume a 32-bit word size in this class/on this test).