Each block of main memory is map to a specific line in the cache which is called Direct mapping.
As Size of Block is equal to line size so,
Which block will be in which line? Is calculated by the following formula K MOD N
Here “K” is Block Number and “N” is the Total number of lines in Cache.
- If the Block No =0 then (0 MOD 4) = 0 It means Block 0 will be in Line 0.
- and If the Block No =7 then (7 MOD 4) = 3 It means Block 7 will be in Line 3.
- and If the Block No =10 then (10 MOD 4) = 2 It means Block 10 will be in Line 2.
The one of the following block will be in Line zero (L0) B0, B4, B8, B12, B16, B20, B24, B28 The One of the following blocks will be in Line zero (L1) B1, B5, B9, B13, B17, B21, B25, B29 The One of the following blocks will be in Line zero (L2) B2, B6, B10, B14, B18, B22, B26, B30 The One of the following blocks will be in Line zero (L3) B3, B7, B11, B15, B19, B23, B27, B31
Address Mapping from RAM to Cache
Let suppose there is a Main Memory (RAM) of size 128 Words and a Cache of size 16 Words. Main Memory and Cache are dived into blocks and Lines respectively. The size of each block Lines is of 4- words as shown in the following diagram.
To represent 32 blocks, 5-bits are require.
and To represent 4-words in the block offset, 2-bits are require.
and To represent 4-lines in cache memory, 2 bits are require.
For Example, if an address of Word 0 of block 22 in the main memory is (1011000) given below
Block offset: Represent Block size Block No: Represent Total No of Block In main memory Line No: Represent Total No. of Lines in Cache Tag: Represent possible Blocks in each Line
Tag Explanation: As there are 32 blocks in the main memory. So, only 8 blocks can come in L0, 8 Blocks in L1, 8 Blocks in L2, 8 Blocks in L3 but one block in one line at a time. So to represent 8 blocks for each line only 3 bits required.
Note: if there are 8 words then 3 bits required for block offset.
Searching for a block through Tag (Cache Hit or miss)
Suppose CPU generate an address 0010100 for 128-word main memory.
First two bits (00) represent Block offset, next two bit (01) are use to represents Block number and last three bits (001) represents the Tag in Cache memory.
To find the Particular block in cache memory
- First, find the line where the required Block is present in cache memory
- Second, Compare the tag bits of CPU generated address with the tag bits of the line where the actual Block is present. If it matches then Cache Hit otherwise cache miss.
Note: Only one comparator is require in direct mapping to find cache hit or miss. As we know the exact block through K MOD N formula. We match the tag of given address with the tag of particular cache line only Once. So Comparator value in direct mapping is always one.
Explain with Example
For address 0010100 in the following diagram, it is a cache Hit. But if the address is 1010011 then it is a cache miss because last three Tag bits (101) are not found in the tag bits of cache lines.
Note: if cache misses then we replace the block of that line (in cache) with required block (from main memory)
Q1: If memory size is 128 KB and memory is Byte addressable then how many bits required to Represent Physical address of main Memory
128KB = 217B
So 17 bits required for physical address (PA) of main memory
Q2: If memory size is 128 KB and memory is word addressable and word size is 8 byte then how many bits required to Represent Physical address of main Memory
128KB/8B = 214B
So 14 bits required for physical address (PA) of main memory
Block Offset / Line Offset
Q3: If we have 8 words in block and each word is f 32 bit then how many Bits are required for Block offset? Main memory is Byte addressable
Total words * size of word in bytes = 8*4= 32= 25B
So, 5 bits required for Block Offset/Line offset
Q4. If we have 8 words in block and each word is f 32 bit then how many
Bits required for Block offset. Main memory is word addressable
Total words = 8 = 23B
So, 3 bits required for Block Offset/Line offset
Q5. if cache size is 64KB and Block/Line size is 8B then how many
bits are require to represent lines of cache memory
Total lines = Cache size/Block size = 64KB/8B = 213B
So, 13 bits are require to represent lines in cache
Q6. if we have PA, Block Offset and Line Bits then we can calculate
Tag through the following equation in Direct Mapping
Physical Address (PA) = Block Offset + Line + Tag
- Cache memory = total bits for line representation+ total bits for block offset
- Tag bits for direct mapping= size of main memory/cache memory
- Tag Directory = tag bits * total no. of lines
- Comparator = 1
Problem 01: Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generated 32 bits addresses. Find the no of bits required for cache indexing and tag bits respectively.
Block Size = 32B = 25 B (5 bits are use for Line or Block offset)
Cache size = 32 KB
Total cache lines = Cache size / Block size = 32KB/32B = 210B (so 10 bits are require for cache indexing or cache lines)
As we know
Physical Address (PA) = Tag + Line + Block Offset
32 bit = Tag + 10bit + 5bits
Tag = 32-10-5 = 17bits
The advantage of direct mapping is Checking of cache Hit or Miss is very simple in the Direct Mapping method. If we have a physical address of a word then we go to that word line number in Cache and compare the Tag of this word and cache line tag. If both are similar than the cache hit otherwise cache miss.
The disadvantage is conflict miss. We know that it is fixed for each block to come in a particular cache line. If Block (B1) is load in Line 1 and B5 comes. Then it replaces the B1 rather to move in other lines even other lines are empty at that time.