Set Associative Cache

2005-01-27T03:00:00.001-08:00

Whenever we talk about cache design an interview question always comes to my mind.

There is a parking lot for 100 cars. How do you arrange these slots efficiently so that you could park 1000 cars. Assuming only 100 cars needs to be parked at a time.
To make things simpler lets say, the car number plates starts from 1 to 1000, and their car keys also has that number printed on them, just to help the valets, assume the parking lot has valet parking.

Solution 1 :

Lets start with a direct approach, there are 1000 cars and 100 slots. Each slot could take 10 cars. So we divide cars by there number plate number.

From 1 to 10 will be parked at slot 1
From 11 to 20 will be parked at slot 2
From 21 to 30 will be parked at slot 3
..
...
.....
From 991 to 1000 will be parked at slot 100

This is a pretty simple scheme, when the car 22 arrives, it will be parked at slot 3. Whenever the owner wants to take out his car the valet will take his car key, find out his car number and go to that particular slot and take out the car.
In this scheme searching for a car in the slots is pretty fast, each car is indexed.
Now there will be problem if car 22 and 23 both arrive at the same time, or car 35 arrived while car number 37 already occupying the 4^th slot.
The flaw in the first design is visible now, if all the cars arrive belong to the same slot we have a real problem.

Solution 2 :

To overcome design flaws discussed above, we make the design simpler on the other extreme. Lets say we allow all the slots to all the cars, as they arrive. Now we do not have any problem as at a time, the need is to park only 100 cars and there are 100 slots. Then why did we think about the first design in the first place ? Well lets say car no 55's owner wants to take out his car. The valet person has no clue where this car is parked, it could be in the 1^st slot or may be in the 30^th slot. The valet person has to search through the entire slots in the worst case scenario.

The advantage of the second scheme is we could store all the cars at any point of time. But to find out where we have parked the car is a real problem. Here the problem is searching for a particular car number.

Solution 3:

A more efficient design would be a compromise of the above two extreme designs. Here lets say we divide the slots in to separate sets. Lets say,
From 1 to 50 will be parked in slots [1, 2, 3, 4, 5]
From 51 to 100 will be parked in slots [6, 7, 8, 9, 10]
.....
........
From 951 to 1000 will be parked in slots [96, 97, 98, 99, 100]

Now in this design we have some flexibility in terms of parking cars belonging to the same set. If car 25 and 45 arrives at the same time we could park them at slot 1 and 2, still we will have empty slots to park 3 more cars belonging to that set.

Search a particular car number say 77, we know it belongs to the 2^nd set and we go and search slots [6, 7, 8, 9, 10]. Each car is in a broader sense indexed to a particular set. So we have better search results.

This is again not the ultimate Utopian design. Imagine 6 cars arrived at the same time which belongs to the first set. The limitation here is at a time we could park only 5 cars in any slot. Same way, search is also not fully indexed, there is a minimum search of iterating 5 slots for a particular car. If we increase the slot sizes, we at a time could park more cars, but search would be expensive. On the other hand if we reduce the set size we could store less cars belonging to the same set, but the search would be faster. In a way we could say, this 3^rd design is a hybrid of the above two designs and above two designs are the extreme cases of the 3^rd design.
Now some theory, the first design we discussed is called, Direct Mapped Cache, the second design is called Fully Associative Cache and the third design we discussed N-Way Set Associative Cache.
There is a critical trade-off in cache performance that has led to the creation of the various cache mapping techniques described in the previous section. In order for the cache to have good performance you want to maximize both of the following:

Hit Ratio: You want to increase as much as possible the likelihood of the cache containing the memory addresses that the processor wants. Otherwise, you lose much of the benefit of caching because there will be too many misses.
Search Speed: You want to be able to determine as quickly as possible if you have scored a hit in the cache. Otherwise, you lose a small amount of time on every access, hit or miss, while you search the cache.

The performance of the above 3 designs could be best summarized by the diagram below.

In the "real world", the direct mapped and set associative caches are by far the most common. Direct mapping is used more for level 2 caches on motherboards, while the higher-performance set-associative cache is found more commonly on the smaller primary caches contained within processors.

Introduction to technologies

2005-01-23T02:04:00.000-08:00

This is a blog on my tech interests. I have mostly worked on server side java technologies, with a avid interest in network technologies. Also I have worked on peer to peer technologies recently. I would like to share some of my experiesnces and designs I have worked on, with my friends through this blog. I hope I could post regularly to this blog.

Gautam's Tech World

Set Associative Cache

Introduction to technologies