What is your status on

Cache Mapping Techniques

?
Content: 

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

Content covered: 

associative memory mapping 

Responses

please post some good quality videos.

Content covered: 

set associative memory mapping 

Responses

More Comments

A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c − byte chunks are mapped on consecutive banks with wrap-around. All the k banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes k2ns.The latency of one bank access is 80 ns. If c=2 and k=24

, the latency of retrieving a cache block starting at address zero from main memory is:

  1. 92 ns
  2. 104 ns
  3. 172 ns
  4. 184 ns
hradeshpatel's picture

here  each iteration requires decoding the bank number= K/2 = 24/2 = 12ns

 and for c =1 => (latency+ decoding ) = 80+ 12= 92ns

 and c= 2 =>  92ns 

so the latency of retrieving a cache block starting at address zero from main memory is 184 ns 

option D is correct

am not geeting it ?? kindly plz conclude it 

7th day 's topic ???????/

Sir tell me, next video will come or not 

  • 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

Awesome, you did good to complete todays course.

To continue your preparation while we publish tomorrow’s topic,

please subscribe to our youtube channel.

 
Back to Course

Responses

rtiwari95's picture

where is the quiz ?

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 

 

shiveshroy's picture

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

saurabh2612's picture

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

 

 

Please explain Quiz Questions???

shraddhagami's picture

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

PA=Tag+sets+Block_offset

let sets=x, and block_offset=y

40=19+x+y

x+y=21

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

                  =2x*8*2y

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

                  =23+21

                  =224

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. ?

PA=35-bits

Word_offset=15bits

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

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

Pd of Comparator=20*10

                             =200

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.
32M/4

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

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 ??

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

Better see ravindra babu ravula videos on youtube

patel512's picture

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

patel512's picture

@shraddhagami how did you get tag bit as 19 initially

shraddhagami's picture

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

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.