Memory Hierarchy
Size and access time are 2 key factors.
Internal Memory:
Attached on CPU CHIPS
1. Registers are very small for storage.
Directly associated with the CPU(MOST USED PART)
2. Cache memory: Static ram(Sram)
Primary memory:
MainMemory(RAM) : DRAM:
Secondary storage:
Usb/Flash: Solid state drive, access time is fast.
Hard disk:
CACHE MAPPING
The Main memory has got the data, which then loads into RAM and then RAM loads into CACHE.
The important point of cache being near to CPU is due to High speed of CPU which can only be
managed by cache.
Ram has blocks called words, while cache has lines.
So when data from SM goes into RAM, it fits into blocks and those blocks are sent into CACHE lines.
The arrangement where to fit, and hot to fit is known as Cache mapping.
Direct mapping:
Architecture of Main memory:
We divide it into blocks, and each block carries 4 words.
B0,B1…B31 are total blocks if we say 32.
and in B0: W0,W1,W2,W3
B1: W4,W5,W6,W7
And so on.
128 words are to be fitted in how many blocks?
Each block has 4 words hence 128/4=32 blocks needed.
We divide it into lines.
Lines and blocks are same thing and, size is also equal to block’s size.
Line size=4.
16/4=4 lines needed.
L0,L1..L3
K mod n.
k > Block no.
n > No of Lines.
Example, let’s hande where the block 0 of memory shall go in cache?
k=0.
N=4.
0 mod 4 = 0.
It will go into L0
Example: block 15 is going in L3.
15 mod 4 = 3.
Hence L3.
Do note 3 remainder means L3.
Don’t confuse if 3 remainder so l2 as l3 is 4th line.****
Referencing:
I need this word, or access to this word.
We generate physical address in Main memory.
128 is the total size of Main memory.
0-127 words range.
2^7 = 128.
7 here is the total number of bits***
Physical address is of 7 bits.
For Main memory:
We divide it into:
Block no and block offset(size)
.
Now carefully:
the initial 5 bits were for to identify block number which yields 2 which the is the block number.
The last 2 bits are for block offset which is 2; It is the index number on 2nd block.
For Cache:
Same 7 bits of physical address but division is into 3 blocks rather than 2.
Tag, Line no, block offset.(order matters)
Block offset comes from the previous example which is 2.
Line no:
Total number of lines in cache block is 4.
2^2= 4
2 bits for line number.
2+2=4 -7 = 3 bits for tag.
Tag duty:
It tells go to line number 4 but there are already many blocks in it so which block?
Ex:
L2 has B2, B6, B10 so is it b10 or b14?
Tag tells that.
Tricky part starts here”
Bits division.
Tag will tell us about the block in that line.
Line no will tell us which line in cache memory, while block off set will tell us block no.
Examples:
Now, how to know which Block?
32 means W32 not B32
Therefore, search for W32 and it lies in B8.
That is what confusing.
Another example:
Also note, directly from tag:
001 = 1 so check 1 index in cache memory of line 0 which is B5
Explanation:
The tag can directly tell which block on line no but if you calculate whole value through decimal of
tag+ln+off you will get direct Word.
Cache hit and cache miss.
Hit: when you search for W20 so you go for B5 and there are W20 but if you want W32 which is in B9
and you go for B5, so it is cache miss.
32 bits address
[Line size = block size]
Here block size is 32 bytes there fore line size is also same.
So, total 32KB(total)/32 B = 1000 = 2^10 = Line no=10 bits.
Last:
10 bits for ln+5 bits for b.o= 15-32 =17 for tag.
IMPORTANT:
Are total lines 10 and total b.o 5?
NO:
2^10 and 2^5!!!!!
Cache indexing is also called line number:
Assume that we have a main memory of size 2MB and word Size (Each block size) is one byte. The
size of cache is 16Kb and in each block of cache a 1Kb identify how many bits are require for Tag,
Index and offset
Main memory size = 2MB = 2^21 bytes Word size (block size) = 1 byte
Cache size = 16Kb = 2^14 bytes Each block of cache is 1Kb
To determine how many bits are required for tag, index, and offset, we
need to use the following formula:
Block size = Tag + Index + Offset
We know that the block size is 1KB = 2^10 bytes. Therefore, we can
write:
2^10 = Tag + Index + Offset
We also know that the cache size is 16KB = 2^14 bytes, and each block of
cache is 1KB = 2^10 bytes. Therefore, the number of blocks in the cache
is:
2^14 / 2^10 = 2^4
Now we can determine how many bits are required for index:
Index bits = log2(Number of blocks) = log2(2^4) = 4 bits
Next, we can determine how many bits are required for offset:
Offset bits = log2(Block size) = log2(2^10) = 10 bits
Finally, we can determine how many bits are required for tag:
Tag bits = Total address bits - Index bits - Offset bits = log2(Main memory
size) - Index bits - Offset bits = 21 - 4 - 10 = 7 bits
Therefore, the number of bits required for tag, index, and offset are 7, 4,
and 10 bits respectively.
Check in the end, tag is evaluated with the help of total memory as tag is supossedly outside each
cache.
Fully associative mapping:
Any block can be any where in cache!
Means, we reduce the chances of number of conflicts, as we fill the memory on empty places.
The tag size increases here.
Note: Line size = block size;;; Each line will have 4 words
block size = 32, 2^5 hence 5 bits for line size.
In direct mapping, we divided the address of cahce in 3 parts, tag, ln,off but here nothing such.
We will only divide in 2 parts: tag+offset.
Reason why no ln?
because we don’t even know which ln has has which particular block; that is what fully associative is.
Total address length= 128 words = 2^7 = 7 bits.
How to divide?
first for physical memory
[Block size , block offset]
Offset: 2^2 as each block as 4 words.
Rest bits for block size
[5,2]
As we said earlier, block size = line size hence for cache address.
[ tag, block offset]
[5,2]
Example:
Set Associative Mapping
Basic block is of:
Block no is further divided into Tag, set no, and then offset.
Set no: total size of cache/size of each block.
Set no mapped onto:
k mod n
k is block #, while n is total set.
Let’s say 2 way sets then,
We want to check where will block 3 go?
3 mod 2 = 1 means SET NUMBER NOT LINE NUMBER 1.
Now in set 1 which line?
we don’t know that.
Tag: It tells us how many blocks can be mapped on in block.
4 bits= 2^4= 16 blocks can be mapped.
: Suppose we have cache for a ram whose address size is 8 bit and have one byte word size and cache
has 8Bytes block size and total size of cache is 32 bytes now identify tag index and offset for direct
mapping and 2-way set associative mapping also for the following addresses identify whether its hit,
Miss, or miss with replacement also identify the miss type (Compulsory, Conflict, or Capacity. (Note:
initially consider cache is empty)
