Select Page

Computer Organization

Memory Organization
Interrupt
DMA Controller

# Direct Mapping

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.

For example

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

So,

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

Where,

```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)

## Numerical:

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

Cache Lines

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

Shortcut Formula’s

• 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

Problem 02:

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.

Help Other’s By Sharing…