Set Associative Cache Mapping is a combination of direct mapping and associative cache mapping. In set-associative cache mapping, the cache is divided into multiple sets. Each set contains one or more lines.
Each block in the main memory is direct-mapped to a particular set in the cache. But as we mentioned above, each set contains multiple lines. Therefore, the block can occupy any line of that particular set.
Basically, we are using direct mapping to map a block to a set but inside a set, we are using associative mapping.
Let’s take an example for better understanding.
The above diagram represents a set associative cache system.
- Page/Block Size = 2 KB
- Main Memory Size = 16 KB
- Cache Size = 8 KB
- Number of Lines in Cache = ( Cache Size ) / ( Page Size ) = 4
- Number of Blocks in Main Memory = ( Main Memory Size ) / ( Page Size ) = 8
In the above cache system, the cache is divide into 2 sets. Each set consists of 2 cache lines. Each block of main memory is directly mapped to a set in the cache. For example, Block 0, Block 2, Block 4, and Block 6 can only occupy the cache line that belongs to Set 0. Similarly, Block 1, Block 3, Block 5, and Block 7 can only occupy the cache line that belongs to Set 1.
Set Number of a Main Memory Block = ( Block Number ) % ( Number of Set in Cache )
It is the exact formula that we use in direct cache mapping. The only difference is instead of mapping each block to a single line, we are mapping each block to a set of lines.
Now we will discuss how CPU handles block requests in set associative cache.
- Suppose initially the cache is empty.
- The CPU requests Block 0. Block 0 is not in the cache. CPU brings Block 0 from main memory to cache. Block 0 occupies Set 0, Line 0.
- The CPU requests Block 4. Block 4 is not in the cache. CPU brings Block 4 from main memory to cache. Block 4 occupies Set 0, Line 1.
- After that CPU requests Block 2. Block 2 is not in the cache. Block 2 is mapped to Set 0, but both lines of Set 0 are already occupied. In this case, the CPU will choose one of the lines in Set 0 and replace it with Block 2. We generally use LRU ( Least Recently Used ) algorithm to choose which line to replace.
- Note that Set 1 is empty but we cannot use lines of another set to store Block 2 since it is direct-mapped to Set 0.
Addressing in Set Associative Mapping
In set associative mapping, the physical memory address is divided into 3 parts
The word offset is used to identify which word of the block we want to access. In the above example, we assumed 1 word = 1 byte. The block size is 2 KB. Therefore, we will need 11 bits to uniquely identify each word.
The set number is used to identify which block in the main memory is mapped to which set in the cache. In the above example, there are only 2 sets. Therefore, we need only 1 bit to identify the set.
As we saw in the above example, a block can occupy any line in its designated set. Tag is used to uniquely identify each block in a set. Each block in a set has a unique tag number. But two blocks belonging to different sets may have the same tag number. In the above example, the number of blocks mapped to a set is 4. Thus, we need 2 bits to uniquely identify each block.
We can calculate the number of tag bits by simply subtracting word offset and set number bits from main memory bits.
Tag Number = 14 – 1 ( Set Number ) – 11 ( Word Offset ) = 2 bits
The least significant bits of the main memory address are used for word offset and most significant bits are used for tag number. The bits in the middle are used for set number.
K Way Set Associative Cache
K way set associative cache means that each set in the cache consists of K-lines. In this section, we will look at set associative mapping in a more general way.
Main Memory Size, M = 2m words
Cache Size, C = 2c words
Number of Lines in a Set, K = 2k lines
Block Size, B = 2b words
Number of Lines in Cache = 2c / 2b = 2c-b
Number of Sets in Cache = 2c-b / 2k = 2c-b-k
Number of Blocks in Main Memory = 2m / 2b = 2m-b
Word Offset = Number of bits to identify each word in a Block = b
Set bits = Number of bits to map each block to a cache set = c – b – k
Tag = Bits required to uniquely identify blocks mapped to the same set = m – (Word Offset) – (Set Number) = m – (b) – (c-b-k) = m – c + k
We can find cache tag bits using another way
Number of Blocks Mapped to a Set = Number of Blocks in Main Memory / Number of Set in Cache = 2m-b / 2c-b-k = 2m-c+k blocks
Since 2m-c+k blocks are mapped to each set, we will need (m – c + k) bits to identify each block.
Tag = m – c + k
i : block number of a main memory block
j : set number that ith block is direct-mapped to
j = i MOD (number of sets in cache)
j = i % 2c-b-k
It is exactly the way we mapped blocks to lines in direct mapping.
Consider a 4-way set-associative cache of size 8MB. The size of the main memory is 32GB. The size of each main memory block is 4KB. The memory is byte addressable.
Our goal is to find
- Number of bits in word offset field
- Number of bits in set number field
- Number of bits in tag field
- Block number of address 0xAF008740
- Set number of address 0xAF008740
- Tag number of address 0xAF008740
Main Memory = 32GB = 235
Cache Size = 8MB = 223
Block Size = 4KB = 212
The number of bits in the word offset field is nothing but the number of bits to identify each byte in a block. Since the size of the block 212 bytes, the number of bits to identify each byte is 12.
Number of bits in word offset field = 12
The number of bits in the set field is nothing but the number of bits to identify each set in the cache.
Number of sets in cache = Cache Size / Block Size = 211
Number of bits in set field = 11
We can calculate the tag bits by simply substracting set number bits and word offset bits from main memory address.
Number of tag bits = 32 – 11 – 12 = 9
We need to find block number of 0xAF008740. The ‘0x’ is the beginning denotes that the address is in hexadecimal format.
Block number is obtained by removing the word offset from the address. We have to remove the 12 least significant bits from the address to obtain block number.
Block number = 0xAF008
We need to find to which set 0xAF008740 is mapped to. First, we will convert it to binary
Address in binary = 10101111000000001000011101000000
The least significant 12 bits are used for word offset, so we can ignore them. The next 11 bits are used for set number.
Set number = 00000001000 = 8
The most significant 9 bits are used for tag bits.
Tag number = 101011110 = 850
- On increasing the block size, the word offset increases, the set number bits decreases and the number of tag bits remains the same.
- On increasing the cache size, the number of set bits increases but the tag bits and word offset remain the same.
- On increasing the main memory size, the tag bits increases, the set bits, and the word offset remain the same.