Set-associative Mapped Cache: Working and Implementation

In this tutorial, we will learn about the working of a set-associative mapped cache with a diagram, the steps of implementation, and a problem based on the set-associative cache. By Monika Jha Last updated : May 08, 2023

What is Set-associative Mapped Cache?

In this mapping technique, blocks of cache are grouped to form a set and a block of main memory can go into any block of a specific set.

Working of Set-associative Mapped Cache

CPU generates a memory request then the set number field of the address is used to access the particular set of the cache.
The tag field of the processor address is then compared with the tags of all K lines within that set.
If these two tags do not match the tag of any cache line, a cache miss occurs.
If these two tags match, a cache hit occurs.
In case of a cache miss, the required word has to be brought from the main memory.
If the cache is full, a replacement is made according to the employed replacement policy.

A diagram to show the implementation of set-associative mapped cache as follows,

Implementation of Set-associative Mapped Cache

The following are the steps to implement set-associative mapped cache:

Step 1

Each multiplexer scans the set number from the generated physical address using its select lines in parallel.
The number of select lines of each multiplexer should be S to read the set number of S bits.

Step 2

After reading the set number, every multiplexer goes to the corresponding set within the cache memory.
After that, every multiplexer goes to the lines of that set using its input lines in parallel.
Number of input lines of every multiplexer = Number of lines in one set

Step 3

Each multiplexer outputs the tag but it's elect from the lines of elect set to the comparators using its output line.
The number of output lines in every multiplexer = one.
Each electronic device selects the tag bit that it's been designed and outputs on the output line as multiplexer is designed to read the tag little bit of specific line at a specific location.
So, the tags as a whole are transmitted to the comparators for comparison in parallel.

Step 4

Comparators compare the tags coming back from the multiplexers with the tag of the generated address.
This comparison takes place in parallel.
If there are k lines in one set (thus k tags), then the number of comparators required = k.
Size of each comparator = Number of bits in the tag.
The output result of each comparator is fed as an input to an OR Gate.
OR Gate is usually implemented using 2 x 1 multiplexer.
If the output of OR Gate is 0, a cache miss occurs and if the output is 1 then a cache hit occurs.

Hit Latency

The time taken to search out whether or not the specified word is available within the Cache Memory or not is termed as hit latency.

For set-associative cache mapping: Hit latency = Multiplexer latency + Comparator latency + OR Gate latency.

Problem Based on Set-associative Mapped Cache

If there is a 4-way set associative mapped cache with block size 4 KB and the size of main memory is 16 GB and also 10 bits in the tag. Find,

Size of cache memory
Tag directory size

Solution

We are considering that the memory is byte addressable.
Block size or Frame size or Line size = 4 KB

Number of Bits in Physical Address-
Size of main memory
= 16 GB
= 2³⁴ bytes
Hence, num of bits in physical address = 34 bits

Number of Bits in Block Offset-
Block size
= 4 KB
= 2¹² bytes
Hence, Number of bits in block offset = 12 bits

Number of Bits in Set Number
= Num of bits in physical address – 
(Num of bits in tag + Num of bits in block offset)
= 34 bits – (10 bits + 12 bits)
= 34 bits – 22 bits
= 12 bits
Hence, Number of bits in set number = 12 bits

Number of Sets in Cache-
Total num of bits in set number = 12 bits
Hence, the total number of sets in cache = 2¹² sets
And each set consists of 4 lines

Hence, total number of lines in cache 
    = Total number of sets in cache x Number of lines in each set
= 2¹² x 4 lines
= 2¹⁴ lines
 
Size of cache memory = Total number of lines in cache x size of line
= 2¹⁴ x 4 KB
= 2¹⁶ x 2²KB
= 64 MB
So, Size of cache memory = 64 MB

Tag directory size = Number of tags x size of tag
= the total num of lines in cache x total number of bits in tag
= 2¹⁴ x 10 bits
= 163840 bits
= 20480 bytes
= 20 KB
Hence, size of tag directory = 20 KB

References

Direct Mapped Cache: Working and Implementation

Difference Between CPU and GPU