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

Direct Mapped Cache – Problem 2 (Tag Bits and Tag Directory)

1. Problem Statement

The system follows a direct mapping cache technique. The memory is byte addressable, meaning every byte in memory has a unique address.

Given information:

  • Main Memory Size = 256 KB
  • Cache Size = 214 bytes
  • Block Size = 210 bytes

Questions:

  • How many tag bits are required?
  • What is the total size of the tag directory?

2. Convert Main Memory Size

Main memory size is given as 256 KB.

256 KB = 2⁸ × 2¹⁰
       = 2¹⁸ bytes

Since memory is byte addressable, every byte requires an address.

Therefore the physical address must generate:

2¹⁸ addresses

So the physical address length = 18 bits.

3. Physical Address Structure

The physical address consists of two parts:

  • Frame Number
  • Frame Offset

Block size = 2¹⁰ bytes.

To address all bytes in a block:

2¹⁰ addresses → 10 bits

So:

  • Offset = 10 bits

Total physical address = 18 bits, therefore:

Frame Number = 18 − 10
             = 8 bits

4. Cache Lines

Cache size = 2¹⁴ bytes

Block size = 2¹⁰ bytes

Number of cache lines:

Cache Lines = Cache Size / Block Size
            = 2¹⁴ / 2¹⁰
            = 2⁴
            = 16 lines

To address 16 lines:

2⁴ → 4 bits

So the line number field = 4 bits.

5. Tag Bits

The frame number (8 bits) is divided into:

  • Tag
  • Line Number
Tag Line Number Offset
4 bits 4 bits 10 bits

Therefore the number of bits in the tag field = 4 bits.

6. Shortcut Method

Total frames in RAM:

Frames = Main Memory / Block Size
       = 2¹⁸ / 2¹⁰
       = 2⁸ frames

Total lines in cache:

Lines = Cache Size / Block Size
      = 2¹⁴ / 2¹⁰
      = 2⁴ lines

Frames mapped to each cache line:

Frames per Line = 2⁸ / 2⁴
                = 2⁴

To distinguish between 2⁴ possibilities, we need:

Tag Bits = 4

7. Tag Directory Size

Each cache line stores a tag.

The tag directory contains all tag values together.

Formula:

Tag Directory Size =
Number of Cache Lines × Tag Bits

Substitute values:

= 2⁴ × 4 bits
= 16 × 4 bits
= 64 bits

Convert to bytes:

64 bits / 8 = 8 bytes

Total Tag Directory Size = 8 bytes

8. Final Answers

  • Tag Bits = 4 bits
  • Total Tag Directory Size = 8 bytes

This represents the total storage required to maintain all tag values across the cache memory.