Fully Associative Mapping | Practice Problems

Fully Associative Mapping-

 

Before you go through this article, make sure that you have gone through the previous article on Cache Mapping.

 

In fully associative mapping,

  • A block of main memory can be mapped to any freely available cache line.
  • This makes fully associative mapping more flexible than direct mapping.
  • A replacement algorithm is needed to replace a block if the cache is full.

 

In this article, we will discuss practice problems based on fully associative mapping.

 

Also Read- Practice Problems On Direct Mapping

 

PRACTICE PROBLEMS BASED ON FULLY ASSOCIATIVE MAPPING-

 

Problem-01:

 

Consider a fully associative mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find-

  1. Number of bits in tag
  2. Tag directory size

 

Solution-

 

Given-

  • Cache memory size = 16 KB
  • Block size = Frame size = Line size = 256 bytes
  • Main memory size = 128 KB

 

We consider that the memory is byte addressable.

 

Number of Bits in Physical Address-

 

We have,

Size of main memory

= 128 KB

= 217 bytes

Thus, Number of bits in physical address = 17 bits

 

 

Number of Bits in Block Offset-

 

We have,

Block size

= 256 bytes

= 28 bytes

Thus, Number of bits in block offset = 8 bits

 

 

Number of Bits in Tag-

 

Number of bits in tag

= Number of bits in physical address – Number of bits in block offset

= 17 bits – 8 bits

= 9 bits

Thus, Number of bits in tag = 9 bits

 

 

Number of Lines in Cache-

 

Total number of lines in cache

= Cache size / Line size

= 16 KB / 256 bytes

= 214 bytes / 28 bytes

= 26 lines

 

Tag Directory Size-

 

Tag directory size

= Number of tags x Tag size

= Number of lines in cache x Number of bits in tag

= 26 x 9 bits

= 576 bits

= 72 bytes

Thus, size of tag directory = 72 bytes

 

Problem-02:

 

Consider a fully associative mapped cache of size 512 KB with block size 1 KB. There are 17 bits in the tag. Find-

  1. Size of main memory
  2. Tag directory size

 

Solution-

 

Given-

  • Cache memory size = 512 KB
  • Block size = Frame size = Line size = 1 KB
  • Number of bits in tag = 17 bits

 

We consider that the memory is byte addressable.

 

Number of Bits in Block Offset-

 

We have,

Block size

= 1 KB

= 210 bytes

Thus, Number of bits in block offset = 10 bits

 

 

Number of Bits in Physical Address-

 

Number of bits in physical address

= Number of bits in tag + Number of bits in block offset

= 17 bits + 10 bits

= 27 bits

Thus, Number of bits in physical address = 27 bits

 

 

Size of Main Memory-

 

We have,

Number of bits in physical address = 27 bits

Thus, Size of main memory

= 227 bytes

= 128 MB

 

Number of Lines in Cache-

 

Total number of lines in cache

= Cache size / Line size

= 512 KB / 1 KB

= 512 lines

= 29 lines

 

Tag Directory Size-

 

Tag directory size

= Number of tags x Tag size

= Number of lines in cache x Number of bits in tag

= 29 x 17 bits

= 8704 bits

= 1088 bytes

Thus, size of tag directory = 1088 bytes

 

Also Read- Practice Problems On Set Associative Mapping

 

Problem-03:

 

Consider a fully associative mapped cache with block size 4 KB. The size of main memory is 16 GB. Find the number of bits in tag.

 

Solution-

 

Given-

  • Block size = Frame size = Line size = 4 KB
  • Size of main memory = 16 GB

 

We consider that the memory is byte addressable.

 

Number of Bits in Physical Address-

 

We have,

Size of main memory

= 16 GB

= 234 bytes

Thus, Number of bits in physical address = 34 bits

 

 

Number of Bits in Block Offset-

 

We have,

Block size

= 4 KB

= 212 bytes

Thus, Number of bits in block offset = 12 bits

 

 

Number of Bits in Tag-

 

Number of bits in tag

= Number of bits in physical address – Number of bits in block offset

= 34 bits – 12 bits

= 22 bits

Thus, Number of bits in tag = 22 bits

 

 

To watch video solutions and practice more problems,

Watch this Video Lecture

 

Next Article- Set Associative Mapping | Implementation & Formulas

 

Get more notes and other study material of Computer Organization and Architecture.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Fully Associative Mapping | Practice Problems
Article Name
Fully Associative Mapping | Practice Problems
Description
Practice Problems based on Fully Associative Mapping. Fully Associative Cache employs fully associative cache mapping technique. Fully Associative Mapping is a cache mapping technique that allows to map a block of main memory to any freely available cache line.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-