L-3.14: Gate 2014 Question on Set Associative Cache Mapping | Computer Organisation and Architecture

[@prasasus]

Total number of words in main memory = 4GB/4B = 2^30 Total no of words in Cache = 16 KB/ 4B = 2^12 Totol no of blocks in cache = 2^12/8 = 2^9 Total number of sets = 2^9/4 = 2^7 Total bits = 30 Set bits = 7 block offset bits = 3 Therefore, tag bits = 30-(7+3) = 20

[@sisirmondal3162]

Sir, i think you have to cheak this video once again .My request to you sir making a correct video of this problem. This video can confuse to a new learner. big fan of you sir ..

[@muttarameshchandraprem1478]

I think address size should be 30 bit and block offset should be 3 bit.

[@bijeshkumar8977]

agree

[@sadafjahan-wd5yo]

4 GB= 2^2 * 2^30 i.e. 32 bits needed for representing address

[@S4hil_Yadav]

​@@sadafjahan-wd5yo u have to take the unit as word not bit

[@tanushreemalviya964]

Thanks so much, sir, the 'cache' is very clear now. :) can solve gate ques :) nicely explained each concept so well in the playlist.

[@SARTHAKMangate-k2m]

Solution- Given- Set size = 4 lines Cache memory size = 16 KB Block size = 8 words 1 word = 32 bits = 4 bytes Main memory size = 4 GB Number of Bits in Physical Address- We have, Main memory size = 4 GB = 2^32 bytes Thus, Number of bits in physical address = 32 bits Number of Bits in Block Offset- We have, Block size = 8 words = 8 x 4 bytes = 32 bytes = 2^5 bytes Thus, Number of bits in block offset = 5 bits Number of Lines in Cache- Number of lines in cache = Cache size / Line size = 16 KB / 32 bytes = 2^14 bytes / 2^5 bytes = 2^9 lines = 512 lines Thus, Number of lines in cache = 512 lines Number of Sets in Cache- Number of sets in cache = Number of lines in cache / Set size = 512 lines / 4 lines = 2^9 lines / 2^2 lines = 2^7 sets Thus, Number of bits in set number = 7 bits Number of Bits in Tag- Number of bits in tag = Number of bits in physical address - (Number of bits in set number + Number of bits in block offset) = 32 bits - (7 bits + 5 bits) = 32 bits - 12 bits = 20 bits Thus, number of bits in tag = 20 bits

[@Travel_learn_vdDiksha]

U r grt sir....u hv made this very easy.... before I ignore COA bt coz of u ...I m used to vd this subject.... thnx alot sir 😍💞💞😘 u r a truly SMASHER😍

[@sarveshwarans8037]

This is the way i thought of it, The main memory has a total size of 4 GB, which is equivalent to 2^32 bytes. Each block in the main memory contains 8 words (2^3 words). So, the addressable range in the main memory is from 0 to 2^29 (2^32 divided by 2^3). We use 3 bits to address the 8 words in a block since 2^3 = 8. The cache memory also has a block size of 8 words (2^3 words), just like the main memory. This means the offset in the cache is also 3 bits. The cache size is 16 KB, which equals 2^14 bytes (2^4 * 2^10 bytes). To determine the number of cache lines, we divide the total cache size by the block size, which is 2^3. So, the cache contains 2^11 cache lines (2^14 / 2^3). Additionally, since 4 lines form a set, the total number of sets in the cache is 2^9 (2^11 divided by 2^2). To address these sets, we use 9 bits. With a total address of 32 bits, 3 bits are used for the offset, and 9 bits are used for the sets. The remaining bits (32 - 9 - 3 = 20 bits) are used for the tag. Give a like to help future members if right, else reply to this comment if wrong. Thanks so much for your help Gate Smashers, I am in love with this series!

[@HimanshuLikhar55]

I think you have mixed up 2 approaches. According to me, if you do it using only words or using Bytes, the answer should be the same. This is how I did it using only words: For RAM, size = 4GB and 1 word = 4B. This means, RAM is 1G words = 2^30. Hence our Physical Address is 30 bits. For offset, we need 3 bits for 8 words. For cache, you have taken the cache size in KB and divided it by number of words per block, which is wrong as they (words) are not same as number of bytes. So, we take 16KB = 4K words. That leaves us with a 4K word cache and we have 8 words per block. That gives us 2^9 cache lines. Therefore, the no. of sets = 2^9/4 = 2^7. Hence, set bits = 7. So tag bits = PA - Set Bits - Tag Bits = 30 - 7 - 3 = 20 bits. The answer is same as that explained in the video. Hope this helps.

[@BHANUPRAKASHbhanu_amy]

@sarveshwarans8037 Although you got the answer but you made a basic mistake with regards to units cancellation. In 3rd line your division is "2^32 Bytes / 2^3 Words" and in 8th Line "2^14 Bytes / 2^3 Words" - here the units don't cancel out to give you the number of blocks and lines respectively. Though we neglect the unit almost every time but its inherent. Hence, your approach is wrong. Had it been no. of sets asked, your answer 2^9 would have been wrong as no. of sets are 2^7. Hope this helps.

[@subhasisbiswal4874]

Always good content. ❤

[@chiragshilwant886]

Good sir you made changes 👍👍

[@sratnamanjari244]

Thank You soo much Sir... 😊😊👌👏👏👏👏.....Superb explanation.... Sir..

[@yamisharma7226]

Stay blessed sir. Thanku

[@rounak3239]

Gurujee shandar jabardast zindabaad

[@nouman8639]

I just watched all of your previous lecture, and tried to solve this question without your help and guess what? My answer is absolutely correct, Thank you Man Respect from Pakistan :-)

[@EatCodeTravel]

Nouman jilani love from FAST,lahore for you

[@nouman8639]

@@EatCodeTravel haha so we are from the same batch :-)

[@iqrakanwal8276]

You are a best teacher in the world plz 🙏 keep it up

[@manjotkaur5463]

yeah solved by myself on the basis of contents of last set associative video.... thank you so much sir.... awsm explaination

[@rahulanand3226]

sir,in previous lecture u told that it is word addresable,so if we take 5 bits for block offset then it will be byte addresable why can we not consider physical address to be of 30 bits?? because there will be 2^27 memory blocks and each block will contain 8 words. so we can take 27 bits for block no and 3 bits for block offset. now the physical address is 30 bits and we can give 3 bits to block offset considering word addressable,7 bits to set no.so for tag the bits will be 30-(7+3)=20 so 20 comes from this approach also, which approach is correct considering byte addressable or word adressable??can u please clear this doubt

[@tanmaykumar9277]

yeah, actually i am also getting correct answer, total length = 30 bits, tag bit = 20 set bit = 7 offset = 3 ( 20 + 7 + 3 = 30 ) this method is for word addressable All blocks exist in secondary storage so total number of blocks = 2^32/((2^2)*(2^3) = 2^27 How tag bit came: (total number of blocks that exist)/(total number of set) => 2^27/2^7 == 2^20 and log( 2^20) = 20 thus tag bit = 20

[@SARTHAKMangate-k2m]

Solution- Given- Set size = 4 lines Cache memory size = 16 KB Block size = 8 words 1 word = 32 bits = 4 bytes Main memory size = 4 GB Number of Bits in Physical Address- We have, Main memory size = 4 GB = 2^32 bytes Thus, Number of bits in physical address = 32 bits Number of Bits in Block Offset- We have, Block size = 8 words = 8 x 4 bytes = 32 bytes = 2^5 bytes Thus, Number of bits in block offset = 5 bits Number of Lines in Cache- Number of lines in cache = Cache size / Line size = 16 KB / 32 bytes = 2^14 bytes / 2^5 bytes = 2^9 lines = 512 lines Thus, Number of lines in cache = 512 lines Number of Sets in Cache- Number of sets in cache = Number of lines in cache / Set size = 512 lines / 4 lines = 2^9 lines / 2^2 lines = 2^7 sets Thus, Number of bits in set number = 7 bits Number of Bits in Tag- Number of bits in tag = Number of bits in physical address - (Number of bits in set number + Number of bits in block offset) = 32 bits - (7 bits + 5 bits) = 32 bits - 12 bits = 20 bits Thus, number of bits in tag = 20 bits

[@himanshubarnwal7811]

You can also solve this by converting physical address to only till kB and making it to cache as the cache memory is in kB.... Shortcut tricks.....

[@abishekbabu9247]

WOW Brilliant sir jiiiiiiiiiiii Thank you so Much!!!!!!!!!!!

[@kalamayilai6499]

Nice sir very clear explanation 👍👏

[@easylearning.....3189]

🙏🤞✌👌 Can you please teach automata... Hardly request sir.. If possible... Want to be a good future lecturer like you🙏

[@GateSmashers]

will try to start in next month.. because already lot of assignments are pending..

[@sohamshinde1258]

​@@GateSmashers

[@Maajwalagi]

very good idea sir g thanks

[@irshadahammed5459]

as the word is the minimum addressable memory unit, 3 bit needed to represent 8 words. , with 5 bits we can represent 32 words .but we don't have 32 minimum addressable memory unit in single block. sir please clarify

[@mysticlunala8020]

I know its late but its for future students. I THINK -- We need to consider this as Byte Addressable by default since its not stated if it is Byte of Word addressable.

[@notgeo3912]

@@mysticlunala8020 The way I did it was that I took 3(or)5 in Offset field depending on if it's Word addressable or Byte addressable and in that way, I got 22(or)20 as the answer in Tag field out of which only one was the answer. I think it's safe to opt for this method in the exam as it could take not too long to solve and reduces a lot of conflict in our head.

[@mysticlunala8020]

@@notgeo3912 What I think is that I don't need to think about COA anymore since I've already passed the semester and I'll probably never encounter this shit again.

[@notgeo3912]

@@mysticlunala8020 Haha, good for you! But just as you said, the comment wasn't aimed only for you, but in a hope that future students could benefit ;)

[@mysticlunala8020]

@@notgeo3912 I know. I'm just joking here.

[@adityasalvi9208]

Your lecture is awesome Jay shree ram

[@DimpleChovatiya]

Amazing videos .. Sir👍👍

[@anilnarayana5468]

sir block offset is 3 bits as 8 words in each block and no lines in cache is 2^14/8= 2^11 and they will be 4 sets hence 2^9 lines 9 bits for set and 20 bit for tag. Pls clarify how come the block offset id 5 bits

[@harshavenkat5355]

How to identify whether a question is byte addressable or word addressable? In all the previous tutorials, you referred to memory in words(w0,w1,w2....) and calculated the offset accordingly. Now you are converting to bytes. In addition, it is mentioned that block size is 8 words, which means memory in block is counted in words. So, shouldn't it be word addressable instead?

[@sarveshwarans8037]

I had the same question, any answers here?

[@BHANUPRAKASHbhanu_amy]

@@sarveshwarans8037 it should be word addressable as per the Previous lecture of gate smasher. Block Size = 8 words * 32Bits/word = 2^5 Bytes ; Total number of Blocks in RAM = 2^32 Bytes/2^5Bytes = 2^ 27. Hence we need 27bits to identify the Block and 3 Bits to Identify the word. So 30bits are required to find any word in RAM.

[@vivekraj529]

I had seen this video one day before semester exam and exact same question came in my exam . BEU 4th sem 2023

[@raj1307]

Sir here word length is given 32 means 2^5 so each block should be 5*8 ?

[@anuragpandey3341]

32 bit and not byte....so jut divide your ans by 8......hence you will get 5

[@ajmalkhaniit]

Thank you sir I request you to make videos on pipelining architecture!

[@namitsharma3449]

Thanks sir g 👍

[@alpishjain1317]

sir sahi mai bhaut demoralization hota abhi 3 weeks pehle OS kiya but kaafi saare concepts nikal gaye dimag se! Fir se revise karna padega😥

[@HelloWorld40408]

Thank You SIr

[@adityaishxn]

nice

[@pratik6089]

Thank u sir❤️

[@ayushiydvKG]

8:07 tq

[@golang2351]

Sir ,how can we know that main memory is byte addresable or word addresable. plz explain sir . In your question there is no clue for this and you take it as byte addresable . So another question is can we always take byte addresable if there is no clue ?... Plz sir explain

[@PraveenKr1992]

we should take it byte-addressable unless specified explicitly.

[@sohamshinde1258]

​ @Gate Smashers plz clear this doubt … pending since long time

[@konainali7593]

You are legend

[@PratimaYadav23]

thanku sir

[@danger_133]

Sir, please do start sm sort of online speed test for kvs /ugc /gate computer science ..

[@rahularyan1117]

i solved it wrong but got the right answer :D

[@shubhamSharma-un1py]

abhi tk acha chal rha tha ...but yha confuse kr diya

[@theresilientpianist7114]

🙏🙏🙌🙌

[@gauravghosh6562]

block offset is to denote number of words in a block which is 8 so it should be 3 bits right?

[@apeethasrinivasan3712]

how to convert block to words, suppose if the main memory size is given in blocks?

[@gurdassindora5076]

Sir Iss traha ke oor example kon c sitta pr millegi

[@gauravgaurav4455]

answers is correct but solution is wrong

[@ankitasen6354]

sir set associative mapping video is not available.

[@VISHALRAJ-nu6yg]

Sir for ESE EE , what is the best material to practice the objective Thanx a lot for making such a effective video

[@csreenivasulu4821]

Hi sir, In cache lines we are mapping the main memory blocks, for finding set number you have divided 16 KB with 32B, that means each line of size 32B. How can we get that sir?

[@learncseasily3385]

I know i am late but for future aspirants Line size = block size Since block size is given 32B So line size is also 32B

[@timepassscript]

@@learncseasily3385 block size is 32bits not 32B

[@surajdhiman2022]

sir here you are saying block size is 32 bits buts actually its 35 bits or 32 bytes please check

[@Periyar_The_Great]

U said no. Of lines divided by k - way associative , but u divided 2^9/2^2 , where as it should be 9/4 ?!?!

[@maxsteel3208]

Sir, can u solve this ,i tried to solve it getting the answer 19 bits i think its wrong.... please solve this . An 8-way set associative cache memory unit with a capacity of 64 KB is built using a block size of 32 words. The word length is 32 bits. The size of the physical address space is 4 GB. Find the number of bits for the TAG field.

[@asutoshdubey1388]

Sir mera diploma cs final year h kya future me rrb je it ke liye form apply kr skta hu please reply

[@GateSmashers]

Yes you are eligible for that..

[@arvindjindal1913]

the sequence of your video is little bit wrong

[@Geethapgasst]

Sir plz explained in English

[@codingwithdill]

set number you found is 7 while none of option is 7 in above example, kindly elaborate this Thanks

[@kratozeus6358]

we need to find tag not set number

[@saketkumar4972]

Wrong explanation