Introduction
Cache Basics Direct Mapped Cache Direct Mapped Example 1 Direct Mapped Example 2 Direct Mapped Problem 1 Direct Mapped Problem 2 Direct Mapped Problem 3 Direct Mapped Problem 4 Direct Mapped Comparators Direct Mapped Disadvantages Direct Mapped Locality Direct Mapped UVM Example Associative Mapped Cache Associative Mapped Problem 1 Associative Mapped Problem 2 Associative Mapped Problem 3 Associative Mapped Problem 4 Set Associative Mapped Cache Set Associative Mapped Comparators Set Associative Mapped Problem 1 Set Associative Mapped Problem 2 Set Associative Mapped Problem 3 Set Associative Mapped Problem 4 Set Associative Mapped Problem 5 Other Mapping Problem - Example 1 Cache Replacement Algorithms LRU Cache Replacement Algorithm FIFO Cache Replacement Algorithm MRU Cache Replacement Algorithm PLRU Cache Replacement Algorithm Round Robin Cache Replacement Algorithm
UVMArena

Associative Mapped Cache – Problem 3

In this problem we analyze a Fully Associative Cache system where the cache size, block size, and tag size are given. The objective is to determine the RAM size, tag directory size, and the number of comparators required.

Given Parameters

Parameter Value
Cache Size 256 KB
Block Size 2 KB
Tag Size 17 bits
Cache Mapping Fully Associative
Addressing Type Byte Addressable

Step 1 — Offset Bits

The number of offset bits depends on the block size. Since each block stores multiple bytes, the offset selects a specific byte inside the block. 


Block Size = 2 KB

2 KB = 2^11 bytes

Offset bits = log2(2^11)
            = 11 bits

Step 2 — Physical Address Size

In associative mapping, the tag represents the frame number. Therefore, the physical address is composed of: 


Physical Address = Tag + Offset


Tag bits   = 17
Offset bits = 11

Total Physical Address =
17 + 11 = 28 bits

Step 3 — RAM Size

Because the system is byte-addressable, each address corresponds to one byte. 


Total Addresses = 2^28

RAM Size = 2^28 bytes

Converting to megabytes: 


2^28 bytes

= 2^8 × 2^20
= 256 MB

Final result: 


RAM Size = 256 MB

Step 4 — Number of Cache Lines

The number of cache lines is obtained by dividing the cache size by the block size. 


Cache Size = 256 KB
Block Size = 2 KB

Number of Cache Lines =
Cache Size / Block Size

= 256 / 2
= 128 lines

Step 5 — Tag Directory Size

Each cache line stores one tag. Therefore the tag directory size is: 


Tag Directory Size =
Number of Cache Lines × Tag Size

= 128 × 17 bits
= 2176 bits

Convert to bytes: 


2176 / 8 = 272 bytes

Final result: 


Tag Directory Size = 272 bytes

Step 6 — Number of Comparators

In a Fully Associative Cache, the requested tag must be compared against the tag stored in every cache line.

Therefore each cache line requires its own comparator. 


Number of Comparators =
Number of Cache Lines

= 128 comparators

Final Results

Parameter Result
Physical Address Size 28 bits
RAM Size 256 MB
Cache Lines 128
Tag Directory Size 272 bytes
Comparators Required 128

Key Concepts

  • In associative mapping, the tag represents the frame number.
  • The physical address is divided into tag + offset.
  • The offset size depends on the block size.
  • The tag directory stores one tag per cache line.
  • Fully associative caches require one comparator per cache line.