635109361-34-Cache-memory-Block-Identification-in-Direct-Mapping-Associate-Mapping-and-Set-Associate-06-03-2.pdf

Fufufhlf

1. Computer Architecture and
Organization
•Course Code: BCSE205L
•Course Type: Theory (ETH)
•Slot: A2+TA2
•Timings:
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Monday 14:00-14:50
Wednesday15:00-15:50
Friday 16:00-16:50

2. Module:4
Memory System Organization and Architecture
Cache Memory: Mapping and BLOCK
IDENTIFICATION
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

3. Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

4. •Aitemfoundtobeinthecacheissaidtocorrespondtoacachehit
•Itemsnotcurrentlyinthecachearecalledcachemisses
•Theadditionalnumberofcyclesrequiredtoservethemissiscalled‘miss
penalty’
•????????????��??????�??????�=
??????����������������������??????��ℎ����ℎ�
??????�����������������??????����������
•????????????���??????�??????�=
??????������������������??????���������ℎ����ℎ�
??????�����������������??????����������
•????????????��??????�??????�+????????????���??????�??????��=1

5. Block Placement
Direct Mapping
Set Associative
Fully Associative
Block Identification
Tag
Index
Offset
Block Replacement
FCFS
LRU
Random
Update Policies
Write Through
Write back
Write around
Write allocate
Cache Memory Management Techniques

6. Block IdentificationBlock Identification TagTag
IndexIndex
OffsetOffset
Cache Memory Management Techniques

7. How to manage the cache and main memory collectively
(together).
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
•Paging is the management of the hard drive and main memory together.
•A page can fit into one frame when MM memory is broken up into units
known as frames. (Note: Pages are used to organise secondary memory.)
•In same way, the cache is divided into what are referred to as lines in order to
manage the main memory and cache. Here The main memory is organised
into units referred to as blocks.
•Now, each blocksize will be determined so that it is equal to the line size.
Note:
➢It is possible to divide MM into blocks and frames.
➢While talking about the HDD and Main memory we are taking about the page movement.
➢While talking about the MM and cache we talk about blocks

8. How to manage the cache and main memory collectively
(Example).
Word:Smallestaddressableunitinthememory.
Block:Collectionofoneormorewords
Assume,thewordsizeis1Byte.Thatis1word=1Byte.Whichmeansthissystemisbyteaddressable.
Consider that the MM is 64 words. Assume that there are 16 words in the cache.
There are four words in each block.
1 Block=4 words.
How many blocks are there in the MM if one block is four words?
Blocks in MM = 64 words / 4 = 16 blocks.
Cache number line: 16/4 = 4 Lines
There are 64 words. Address lines or physical addresses are 6 bits since 2^(6)=64.

9. How to manage the cache and main memory collectively
(Example).
•ConsiderthattheMMis64words.
Assumethatthereare16wordsinthe
cache.
•Therearefourwordsineachblock.
•1Block=4words.
•Howmanyblocksarethereinthe
MMifoneblockisfourwords?
•BlocksinMM=64words/4=16
blocks.
•Cachenumberline:16/4=4Lines
•Thereare64words.Addresslinesor
physicaladdressesare6bitssince
2^(6)=64.
WhatdoesitsignifywhentheCPUcreatesanaddress?
Tofindtheworditneeds,theCPUconstructsa6bitPhysicalAddress(PA).Findingoutifthewordisinthecacheor
notfromthisPAisthefirststep.Ifitisn'talreadyinthecache,theCPUwillgetdatafromthemainmemory.
Ifthereisacachehit,theCPUwillretrieveitfromthecache.WemoveontotheMMtoretrievethecacheifitis
missed.

10. How to manage the cache and main memory collectively
(Example).
•IftheCPUproducedsomethingsimilarto
000101.WhatdoestheCPUactually
want?
•CPUrequeststheword"5".
•HowCPUgetthewordfive?
•MMisdividedinformofblocks.So,how
CPUyouacquirewordnumberfive?
•Thereare16blocks(2^4),eachblock
sizeis4words(2^2).Hence,Therefore
CPUgeneratedaddressisdividedinto
twoparts.
000101➔ 0 0 0 101
Block number Block offset

11. How to manage the cache and main memory collectively
(Example).
000101➔ 0 0 0 101
Block number Block offset
Thetwoleastsignificantbitswillgiveyouavalueknownas
Blockoffset.Blockoffsetreferstothetermthatiscontained
withintheblock.
Thefourbitswiththemostsignificancewillgiveyouablock
number.BlocknumberreferstheblockwheretheCPU-required
wordispresent.
Look into block number 1 because of 0001 and then block Here 01 means 1.
Words in the block start from 0. So 1 means the second word, that is 5.

12. How to manage the cache and main memory collectively
(Example).
Another example, 001010
001010
CPU required word is 10
From block address, 0010 ➔it is second block
From block offset, 10➔2, it third (because word
numbering start from zero) word in that block.

13. How to manage the cache and main memory collectively
Whenincludingthecachememory,thentheprocesswillincludewhetherthat
particularblocklookingforispresentinthecacheornot.
•Blockoffsetisutilisedtoobtaintheneededwordifitisalreadyinthecache.
•Ifitisn'tthere,obtainthatspecificblockfromMMandaddittothecache.
WeareawarethatMMhasalargercapacity(highernumberofblocks)than
cachememory.Naturally,itisnotpossibletoputallthewordsfromMMina
cache.

14. Cache: Mappings (Cache Memory Management Techniques)
Mapping:Isacachememorymanagementtechniques.Eachmemoryblockinthemain
memoryismappedtoalineinthecacheisknownasmapping.
•Mappingwillanswerthefollowingthings:
•What(whichblock)andhowcanthenbestoredincachememory?Thisideaisknown
asmapping.
•WherearetheMM-blocksgoingtobemaintainedifyouhavetoplacetheminthe
cache?
•Thismeans,whichlineofthecachedoesoneblockofMMholds?
There are various kinds of mappings proposed.
•Direct Mapping
•Associative or Fully Associative mapping
•Set Associative Mapping

15. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Block Placement Direct Mapping
Set Associative
Fully Associative
Cache Memory Management Techniques

16. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping
•A particular block of main memory can map only to a particular line of the
cache.
•The line number of cache to which a particular block can map is given by-
Cache line number = ( Main Memory Block Address ) Modulo (Number of lines in Cache)
Division of Physical Address-
In direct mapping, the physical
address is divided as-

17. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping
Cache line number = ( Main Memory Block Address ) Modulo (Number of lines in Cache)
Division of Physical Address-
In direct mapping, the physical
address is divided as-

18. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping (Example Explanation)
•Caches of 0 to 3 lines (1 Block=4 words, 16 words in the cache, and
Cache number line: 16/4 = 4 Lines) and MM blocks of 0 to 15 (This is
because MM is 64 words, and 1 Block equals 4 words.) are examples
from the previous example.
•Caches Line 0 to 3 will first be filled with main memories 0 to 3
•after that, next time again MM's 4 to 7 blocks fill them once more from
Line 0 to 3.
•Like this, all blocks of MM’s are occupied in lines of cache.
•Finally, the MM's blocks 0, 4, 8, and 12 will map to line 0 of cache
memory.
•It is many to one functions.

19. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping (Example
Explanation)
•Ifyoueverwanttogeteither0or
4or8or12blockstheyshould
alwaysbeplacedinlinenumber0
ofthecache,nowhereelse.
•Similarly,MMblocks1,5,9,and
13alwaysbeplacedinline
number1.

20. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping (Example
Explanation)
Ifweexaminetheaddressesfrom
CPU(Fromoldexample),theyare6
bits,andoutof6bitsBlocknumbers
comein4bits,andblockoffsetcomes
in2bits.
Ifweconsider
block4bitsthen
wehavethe
followingbinary
pattern.

21. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Direct mapping
(Example Explanation)
Ifweconsiderblock
4bitsthenwehave
thefollowingbinary
pattern.
Blocks0,4,8,and12getintoline
number0ofthecache.Ifyou
observetheblock4bitsleasttwo
significantbitsare00.Bythis,wean
findthelinenumberofeachblock.
Therefore,from6bitsCPUaddressline,thefirsttwoleastsignificantbitsindicatetheblockoffset(i.e.,
wordlocationinblock)andtheNextfourbitsindicatetheblockaddress.Intheblocknumberfield,the
firsttwoleastsignificantbitsindicatethelinenumberofthecacheandtheremainingtwobitsindicates
thetagdirectory.

22. Cache: Mappings (Cache Memory Management Techniques)
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
From 6 bits CPU address line,
•The first two least significant bits indicate the block offset (i.e., word location in
block) and the
•Next four bits indicate the block address.
•In the block number field, the first two least significant bits indicate the line
number of the cacheand
•The remaining two bits indicates the tag directory.
•Blockaddresscanbeusedtodeterminetheblocknumberinthiscase,andblockoffsetis
usedtodeterminewherethewordislocatedinsidetheblockinMM.
•ThefirsttwoLSBoftheblocknumberrepresentthelinenumberofthecache,which
identifiesthelinenumberonwhichthatwordcanbefoundthere.
•WhatusedoestheTAGfield,whichiscreatedfromtheremainingbitsoftheblock
number,thenserve?
Direct mappingTAG field in Block Identification

23. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Whydowerequireatagfield?
•Eachlineisdividedintofourblocks.
•Asaresult,oneoffourwordscouldbecontainedinsideacacheline
(fromtheconsideredexample,line-0couldbeanyofoneblockfrom
block-0,4,8,and10).
•TheTag2bitswillthereforerevealwhichofthefourispresent.
Theblocksinthetagthatcanbeidentifiedareasfollows.

24. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
•Letusconsider,theaddressgeneratedbytheCPUlikethis:
110101
•ThenwhatthewillCPUtrytodois,itwillfirstcheckin
thecache,whetherthatparticularblockispresentornot.
•Fromthegivenaddress,itgoestothelinenumberthatis
middle01bits.
•Itis1,thenitlooksintoline-1.
•Andthenitcomparesthetagwithbits11.
•ThentheCPUwillunderstandthatinlinenumber01(i.e.,
1inDecimal),therequiredblockispresentthereforeIget
intothesecondlocationandthenitgets.
Direct mapping (Hit and Miss Example Explanation)

25. Block IdentificationBlock Identification TagTag
IndexIndex
OffsetOffset
Cache Memory Management Techniques

26. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Q: Given MM size=128KB and cache size=16KB, block size=256B then find tag bits and Tag directory size.
Tag bits in physical address. Here memory is byte addressable
Here memory is byte addressable, which means Every address should able to produce all the bytes present in that memory size.
From given 128KB, there are 128K Bytes are present.
Then we convert the 128K in 2^? to get the number of bits. 128K=2
7
*2
10
=2
17
➔17bits
The physical address (PA) for 28KB MM size is =17bits
Initially, According to the MM, This
PA will represent two things that is
block offset and block number.
According to the cache, this
PA will be represented as
PA=17bits, cache size is 16KB and block size is 256B
Block offset to represent the block size of 256B=2^8➔8bits

27. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Q: Given MM size=128KB and cache size=16KB, block size=256B then find tag bits and Tag directory size.
Tag bits in physical address. Here memory is byte addressable
The physical address (PA) for 28KB MM size is =17bits
Block size is 256B, Block offset
to represent the block size of
256B=2^8➔8bits
Number of lines or Line numbers= Total cache
size/Block size or Line size =
16KB/256B=2
4
*2
10
/2
8
=2
6
So 6bits are used to represent the line number.
Totally bits are 17, except Line
number 6 bits and Block offset 8bits
remaining (17-(6+8)=3) 3 bits are
tag bits.
Or
That size of MM/size of cache
=128KB/16KB=2
7
*2
10
/2
4
*2
10
=2
3
➔3 bits
Tag Directory size: each tag information is going to be 3 bits. And Every line is containing
tag. So tag directory size is 3*Number of lines=3*2
6
bits.

28. •MainMemorySize=2
m
•MainMemoryblockSize=2
n
•CacheSize=2
k
•NumberofblockinMainMemory
=(2
m
)/(2
n
)=2
m-n
•NumberoflinesinaCache
=(2
k
)/(2
n
)=2
k-n
•MainMemorySize=2
m
•MainMemoryblockSize=2
n
•CacheSize=2
k
•NumberofblockinMainMemory
=(2
m
)/(2
n
)=2
m-n
•NumberoflinesinaCache
=(2
k
)/(2
n
)=2
k-n
Tag Index Offset

29. •Candidates(mainmemoryblock)foreachcache
line(Tag)
=2
m-n
i.e2
m-k
2
k-n
•NumberoflinesinaCache(Index)
=(2
k
)/(2
n
)=2
k-n
•Eachcachelinecontainsthesamenumberof
bytesasinamemoryblock.
•Offsetis=n;Index=k-n;tag=m-k
•Candidates(mainmemoryblock)foreachcache
line(Tag)
=2
m-n
i.e2
m-k
2
k-n
•NumberoflinesinaCache(Index)
=(2
k
)/(2
n
)=2
k-n
•Eachcachelinecontainsthesamenumberof
bytesasinamemoryblock.
•Offsetis=n;Index=k-n;tag=m-k
Tag (m-k) Index(k-n) Offset (n)

30. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
If memory block number is mand number of cache lines are nthen m
th
block present in k
th
line of the cache.
K=m%n
W.K.T physical address is directly divided into
two parts Block number filed and Block offset
Explanation
If block number consists of m bits,
then number of blocks are 2
m
Inblocknumberfield,theleastsignificantof
somebits(letasassumelbits)areusedto
representthelinenumberinthecache.
Therefore,numberoflines=2
l
We have m bit number which is block number.
In this m bit numbers the least significant l bits are line
number bits
If this mbits are representing some number x. then the
least significant l bits then the line number where the
block is present is = x mod 2
l
Which means if we take the MM block number and then divided
with 2
l
then the remainder is nothing but the line number.

31. Cache: Mappings(Cache Memory Management Techniques) : Direct mapping
If memory block number is mand number of cache lines are nthen m
th
block present in k
th
line of the cache.
K=m%n
For instance, where are you putting the 100th MM block if there are 4 cache lines?
The 100th MM block will be in the 0th line of the cache, because 100mod4=0.
So, if there is any x
th
block main memory will be place in x mod #cachelinesor x mod 2
#cach bits
If the cache has 4 lines (line 0 to line 3). Then according to the direct mapping where the following blocks are present. 5, 6, 4,
8, 9, 12, 15, and 20
➢5 is present at 5%4=1➔Line 1
➢6 is present at 6%4=2➔Line 2
➢4 is present at 4%4=0➔Line 0
➢8 is present at 8%4=0==Line 0, but the 4th block is already present there. Here 8th block
conflicts with the 4th block, therefore line-0 4th block is going to replace by the 8th block.
➢9 is present at 9%4=1==Line 1, but the 5th block is already present there. Here 9th block
conflicts with the 5th block, therefore line-1 5th block is going to replace by the 9th block.
➢12 is present at 12%4=0==Line 0, but the 8th block is already present there. Here 12th block
conflicts with the 8th block, therefore line-0 8th block is going to replace by the 12th block.
➢15 is present at 15%4=3➔Line 3

32. Direct Mapping
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
14
15
0
1
2
3
4
5
6
7
Main Memory
Cache
=(MM Block address)
mod
(Number of lines in a cache)
(12) mod (8) =4
•Ifeachblockhasonlyoneplaceitcan
appearinthecache,thecacheissaidtobe
directmapped.

33. Drawback of direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
The drawback of direct mapping is conflict miss.
Consider a example, If the cache has 4 lines (line 0 to line 3). Then according to the direct mapping where
the following blocks are present. 4, 8, 16, 16, 20, 12, and 24.
4 is get into 4%4=0==Line 0
8 is get into 8%4=0==Line 0
Even if there are many lines in the cache, they will never be used due to the direct mapping restriction. This
is the conflict miss issue with direct mapping.

34. Drawback of direct mapping
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
The drawback of direct mapping is conflict miss.
•Conflict miss is different than capacity miss.
•Capacity miss is, in case the cache doesn’t have the capacity then come
across them is a capacity miss.
•Conflict miss means, even though there is a lot of other space you are not
going to use that space and replace a place that will be missed later.
•In Direct mapping, the miss is because of the conflict not because of the
capacity.

36. Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore