Problem 4.1: A set-associative cache consists of 64 lines, or slots, divided into four-line sets. Main memory contains 4K blocks of 128 words each. Show the format of main memory addresses. Hint: This is a 4-way set associative cache, because we have 4 choices for where to put items in each set. Its as if we had 16 direct-mapped caches, each with 4 entries. So its 16 sets x 4 lines/set = 64 lines. So the problem is reduced to the following questions:

How many bits are needed to identify which set number? _______

How many bits are needed to address the 4K blocks in memory? ______

Subtract (a) from (b) and you have the bits from the address that arent accounted for in the set # and therefore must be accounted for in your tag. How many bits is that? ______

Next, once you are narrowed down to a set and further to a particular line within a set, you find 128 words of data. How many bits do you need to narrow down to the specific word you want? ______

Lastly, because the computer always deals in words, not just bytes, everything we do in cache is built around the size of the CPUs registers, which is the same as its bit architecture. Assuming this is a 32-bit architecture (which if you already understand why this cannot possibly be true, please pretend its OK for now), when we go to memory (including cache), were always dealing with 32 bits of data at a time. Thats our smallest unit of data well pull towards the CPU or receive from the CPU. However, our RAM is built around bits, 8 bits each. How many bits are needed to track the number of bytes that span 32 bits? _______. Thats our offset.

Put it all together by filling out the following diagram

Tag Set or Index Word Offset