techtud's picture

Cache Mapping Techniques

Cache mapping techniques

By caching data, operating systems want to minimize delay to fetch next data or instruction. Cache mechanisms use principle of locality to bring in data which may be accessed next, based on currently accessed data, for faster access. There are two locality principles:
Temporal locality:  data which is used recently may be used again in near future.
Spatial locality:  data near to current accessed data may be accessed in near future.
There are three mapping techniques : Direct mapping, fully associative and set associative mapping.
Direct mapping:
In a direct mapped cache, lower order line address bits are used to access the directory. Since multiple line addresses map into the same location in the cache directory, the upper line address bits (tag bits) must be compared with the directory address to ensure a hit. If a comparison is not valid, the result is a cache miss, or simply a miss. The address given to the cache by the processor actually is subdivided into several pieces, each of which has a different role in accessing data.

Fully associative:
In fully associative mapping, when a request is made to the cahce, the requested address is compared in a directory against all entries in the directory. If the requested address is found (a directory hit), the corresponding location in the cache is fetched and returned to the processor; otherwise, a miss occurs. 

Set associative mapping:
The set associative cache operates in a fashion somewhat similar to the direct-mapped cache. Bits from the line address are used to address a cache directory. However, now there are multiple choices: two, four, or more complete line addresses may be present in the directory. Each of these line addresses corresponds to a location in a sub-cache. The collection of these sub-caches forms the total cache array. In a set associative cache, as in the direct-maped cache, all of these sub-arrays can be accessed simultaneously, together with the cache directory. If any of the entries in the cache directory match the reference address, and there is a hit, the particular sub-cache array is selected and outgated back to the processor. 


Direct Mapping

associative memory mapping
Content covered: 

associative memory mapping 

More Less
set associative memory mapping
Content covered: 

set associative memory mapping 

More Less

  • This quiz contains 5 questions on the topic Cache Mapping Techniques
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  basic
No. of Questions:  5
RAHUL TIWARI rtiwari95 1 Jan 2017 02:41 pm

where is the quiz ?

Amit Jindal amitj 2 Jan 2017 10:51 pm

Please explain question 1 of quiz. Here is the question.

Consider a 2 way set associative memory consisting of 2c memory blocks and 2c cache blocks. The cache location for the memory block K is 


Shivesh Kumar Roy shiveshroy 4 Jan 2017 10:16 pm

No. of blocks in cache=  2c and 2-way set associative is given so no. of sets in cache = 2c/2 =c sets

So the cache locatio of memory block k = k mod c

saurabh ghosh saurabh2612 3 Jan 2017 07:34 pm

where is all other videos? no updates.... 



Gourav Jain gouravjain 4 Jan 2017 10:36 pm

Please explain Quiz Questions???

Shraddha shraddhagami 12 Jan 2017 12:24 am

1.Consider a 2 way set associative memory consisting of 2c memory blocks and 2c cache blocks. The cache location for the memory block K is 

=>No. of blocks in cache=  2c 

2-way set associative is given So, no. of sets in cache = 2c/2 =c sets

Therefore cache location of memory block k = k mod c


2. The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ?

=>PA=40 bits

Tag =19-bits


let sets=x, and block_offset=y



cache size=sets*(No.of lines per set)*block_offset


                        =8*2x+y (x+y=21)



Therefore cache is 24 -bits


3.Consider main memory of size 32GB and blocks of size 32KB. If the propagation delay of comparator is 10T ns (T is the number of tag bits) and the propagation delay of OR gate is 10 ns. What will be the Hit Latency in ns. ?



Tag=20-bits       (Tag=35-15)

no. of comparators=20     (b'cz no. of comparator = no. of tag bits)

Pd of Comparator=20*10


Pd of Or=10

Hit Latency=200+10=210


4. A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits for the TAG field is


Number of sets = cache size / sizeof a set

Size of a set = blocksize * no. of blocks in a set 
= 8 words * 4 (4-way set-associative)
= 8*4*4 (since a word is 32 bits = 4 bytes)
= 128 bytes.

So, number of sets = 16 KB / (128 B) = 128

Now, we can divide the physical address space equally between these 128 sets. So, the number of bytes each set can access
= 4 GB / 128 

4 GB space is divided between 128 sets equally.
So each set contains 4GB / 128 = 32 MB.
Set is 4-way set associative , so contains 4 block / set.

8 M words = 1 M blocks. (220 blocks)
So, we need 20 tag bits to identify these 220 blocks. 

Mayank gwal mayu0987 7 Jan 2017 07:15 pm

In 2nd quiz qwes it's the tag bits which is asked in a 512 Kb 8-way set associative cache.. so how could u take tag = 19 bits ??

akshay goel akshay94 9 Jan 2017 09:08 pm

By watching videos we can not any of the questions,videos are of no help.

akshay goel akshay94 11 Jan 2017 04:33 pm

Better see ravindra babu ravula videos on youtube

Sarvottam patel512 12 Jan 2017 12:00 am

@shraddhagami In question 3 i think 15 bits is word offset and not block offset

Sarvottam patel512 12 Jan 2017 12:32 am

@shraddhagami how did you get tag bit as 19 initially

Shraddha shraddhagami 12 Jan 2017 12:39 am

Width of tag field is given as 512KB(219)