How Does Direct-Mapped Cache Use Modulo Indexing?

A direct-mapped cache assigns each main memory block to exactly one specific cache line using modulo arithmetic. By dividing the memory block address by the total number of cache lines and taking the remainder, the hardware determines the exact index where the block must be stored. This approach simplifies cache lookup and hardware design, though it can lead to conflict misses when multiple active blocks map to the same index.

Memory Address Structure

In classical computing, a physical memory address is divided into three distinct fields to support cache operations: the tag, the index, and the block offset.

\[\text{Memory Address} = [\text{Tag} \mid \text{Index} \mid \text{Block Offset}]\]

The block offset specifies the exact byte or word within a cache line. If each cache line holds \(B = 2^b\) bytes, the lowest \(b\) bits of the address form the block offset. Removing these offset bits leaves the block address, which identifies the specific block in main memory:

\[\text{Block Address} = \left\lfloor \frac{\text{Memory Address}}{B} \right\rfloor\]

Modulo Index Arithmetic

A direct-mapped cache contains \(N\) cache lines, where \(N\) is typically a power of two (\(N = 2^k\)). To determine which cache line holds a given memory block, the cache controller computes the remainder of the block address divided by \(N\):

\[\text{Cache Index} = \text{Block Address} \bmod N\]

Because \(N = 2^k\), this modulo operation does not require an expensive division circuit in hardware. Instead, taking the remainder modulo \(2^k\) is mathematically identical to extracting the lowest \(k\) bits of the block address. The remaining upper bits of the block address become the tag:

\[\text{Tag} = \left\lfloor \frac{\text{Block Address}}{N} \right\rfloor\]

Hardware Lookup and Tag Comparison

When the processor requests data at a memory address, the cache controller uses the extracted index bits to directly access one of the \(N\) cache lines. It then compares the tag stored in that cache line against the tag bits from the requested memory address.

If the valid bit of the cache line is set to \(1\) and the tags match, a cache hit occurs, and the requested byte or word is selected using the block offset. If the valid bit is \(0\) or the tags do not match, a cache miss occurs. The cache controller fetches the required block from main memory and writes it into the cache line at that same index, overwriting any previous data stored there.

Advantages and Conflict Misses

The primary advantage of modulo indexing in a direct-mapped cache is speed and simplicity. Because each memory block has only one possible location, the hardware needs only a single comparator to check the tag, minimizing both access latency and power consumption.

However, this rigid mapping creates a vulnerability to conflict misses. If a program repeatedly accesses two different memory blocks whose addresses are separated by a multiple of \(N \times B\) bytes, both blocks produce the same cache index:

\[\text{Block}_1 \bmod N = \text{Block}_2 \bmod N\]

As a result, the two blocks continually evict each other from the cache, even if other cache lines remain completely empty.