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 2

In this problem we analyze a system that uses Fully Associative Cache Mapping. The objective is to determine the tag size, the tag directory size, and the number of comparators required.

Given Parameters

Parameter Value
RAM Size 512 KB
Cache Size 32 KB
Block Size 256 Bytes
Addressing Type Byte Addressable
Cache Mapping Associative Mapping

Since the system is byte-addressable, every byte in RAM has its own unique address.

Step 1 — Physical Address Size

The RAM size determines the number of address bits required. 


RAM Size = 512 KB

512 KB = 2^9 × 2^10
       = 2^19 bytes

Because each byte has an address: 


Physical Address Size = 19 bits

Step 2 — Offset Bits

The block size determines how many bits are required to select a byte within the block. 


Block Size = 256 bytes

Offset bits = log2(256)
            = 8 bits

Step 3 — Tag Size

In associative mapping, the tag represents the frame number. 


Tag bits = Physical Address Bits − Offset Bits

Tag bits = 19 − 8
         = 11 bits

Therefore: 


Tag Size = 11 bits

Step 4 — Number of Cache Lines

The number of cache lines is calculated from the cache size and block size. 


Cache Size = 32 KB = 2^15 bytes

Number of Cache Lines =
Cache Size / Block Size

= 2^15 / 2^8
= 2^7
= 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 × 11 bits
= 1408 bits

Convert to bytes: 


1408 / 8 = 176 bytes

Final result: 


Tag Directory Size = 176 bytes

Step 6 — Number of Comparators

In Fully Associative Cache, the tag of the requested address must be compared with the tag stored in every cache line.

To perform this quickly, the comparisons are executed in parallel. 


Number of Comparators =
Number of Cache Lines

= 128 comparators

Final Results

Parameter Result
Tag Size 11 bits
Cache Lines 128
Tag Directory Size 176 bytes
Comparators Required 128

Key Takeaways

  • Associative mapping allows any memory block to be stored in any cache line.
  • The tag stores the frame number of the block.
  • The number of tag bits depends on the physical address size and block offset.
  • The tag directory stores one tag for each cache line.
  • Fully associative caches require one comparator per cache line.