A two-way cache changes one conflict pattern

If three arrays fit in a cache by total byte count, can their accesses still miss repeatedly? Yes. A cache assigns each memory block to a set, and each set has a limited number of candidate lines. Associativity changes that placement constraint, but the access order and replacement policy still determine which blocks survive.

We will compare direct-mapped, two-way and four-way versions of one hypothetical cache. Each stores 1,024 data bytes in sixteen-byte lines and receives sixteen-bit byte addresses. All examples are simulated reads, starting empty, with immediate whole-line fills. They contain no writes, prefetching, coherence traffic or measured timing. You need integer division and the distinction between a memory block and its candidate cache set.

Keep capacity fixed while changing the number of ways

There are sixty-four lines in every version because 1,024 divided by sixteen is sixty-four. Direct mapping gives sixty-four sets with one line each. Two-way associativity gives thirty-two sets with two lines each. Four-way associativity gives sixteen sets with four lines each. Increasing ways without reducing sets would increase capacity and answer a different question.

For this declared low-bit indexing rule, divide a byte address by sixteen and discard the remainder to get its memory block number. The set index is that block number modulo the number of sets. Every way in the selected set is a candidate; the address does not select one particular way in advance. A hit occurs when one candidate already contains the requested block.

Chris Terman’s Computation Structures lecture develops set associativity as a search over several candidate lines at one index. The pinned gem5 indexing policy likewise returns the candidate entries for the selected set. These sources explain the placement rule; our dimensions and access sequences are original examples.

Use the first bytes of three hypothetical arrays: A at 0x0000, B at 0x0400 and C at 0x0800. Their block numbers are zero, sixty-four and 128. All three select set zero in each of our cache versions. Only those first blocks are accessed; we have not loaded the arrays’ entire contents. The active blocks contain forty-eight bytes, well below the cache’s total capacity.

Give a frequently reused block a chance to survive

Consider the six requests A B A C A B. A direct-mapped cache misses on all six because every request replaces the sole line in set zero with a different block. The two-way cache can keep two blocks there, so it needs a rule for choosing a victim when both candidate lines are occupied.

Use exact least recently used replacement, LRU. Keep each set’s resident blocks ordered from oldest use to newest use. A hit moves the touched block to the newest end. A miss uses an empty slot if one exists; otherwise it evicts the oldest block, then inserts the requested block as newest. Recency changes on hits as well as fills.

After A and B fill the two slots, the order is A then B. The third request hits A and changes the order to B then A. C then misses and evicts B, leaving A then C. The next A hits and changes the order to C then A. Finally B misses and evicts C. The result is two hits and four misses, with A surviving both intervening fills.

View full-size image ↗

This order is replacement metadata, not a statement that physical data bytes move between ways on every hit. Hardware can update information about which line is older while leaving its data in place. The pinned gem5 LRU implementation records last-touch ticks and chooses the candidate with the oldest tick. Our ordered list gives each sequential access an unambiguous recency position; it does not reproduce simulator tick ties or execute gem5.

Run the same requests through explicit policies

The following Python model accepts the three declared associativities. It stores complete memory block numbers for readable traces; actual cache tags can omit the bits already implied by the selected set. Its returned order lists aligned block addresses from oldest to newest. The evicted field is None when no resident block was removed.

def simulate(addresses, ways, policy="lru"):
    if type(ways) is not int or ways not in (1, 2, 4):
        raise ValueError("this experiment supports 1, 2 or 4 ways")
    if policy not in ("lru", "fifo"):
        raise ValueError("policy must be lru or fifo")
    sets = 64 // ways
    residents = [[] for _ in range(sets)]
    rows = []
    for address in addresses:
        if type(address) is not int or not 0 <= address < 65536:
            raise ValueError("address must be a built-in 16-bit unsigned integer")
        block = address // 16
        index = block % sets
        order = residents[index]
        hit = block in order
        evicted = None
        if hit:
            if policy == "lru":
                order.remove(block)
                order.append(block)
        else:
            if len(order) == ways:
                evicted = order.pop(0) * 16
            order.append(block)
        rows.append({"address": address, "set": index, "hit": hit,
                     "evicted": evicted,
                     "order": tuple(item * 16 for item in order)})
    return rows


def misses(rows):
    return sum(not row["hit"] for row in rows)


A, B, C = 0x0000, 0x0400, 0x0800
hot = [A, B, A, C, A, B]
assert [misses(simulate(hot, ways)) for ways in (1, 2, 4)] == [6, 4, 3]
assert misses(simulate(hot, 2, "fifo")) == 5
assert [row["evicted"] for row in simulate(hot, 2)] == [None, None, None, B, None, C]
print(*simulate(hot, 2), sep="\n")

First-in, first-out replacement, FIFO, preserves insertion order on a hit. In this trace, touching A at the third request does not protect it. C evicts A at the fourth request, so the fifth request now misses. FIFO has one hit and five misses. Forgetting to update recency on a hit silently changes the algorithm, even if the code and documentation still call it LRU.

Neither policy knows the future. The example demonstrates the benefit of retaining A for this supplied sequence, not that LRU wins on every workload. The cache lecture discusses both policies and the cost of maintaining exact recency. A real processor may use an approximation or a different insertion policy; knowing its associativity does not identify its victim-selection algorithm.

Three rotating blocks still overflow two candidates

Now repeat A B C three times. Under two-way LRU, C evicts A, the next A evicts B, and the next B evicts C. Every request misses. Direct mapping also misses every time. Four ways fit all three blocks in set zero: the first three requests miss and the remaining six hit.

This failure is about occupancy in one set, not the total forty-eight-byte working set. Empty lines in other sets cannot be borrowed under the declared placement rule. It also shows why two-way associativity does not mean “two accesses per cycle.” Ways describe candidate storage locations; ports, banks and pipeline design determine access throughput.

Run the next block after the first. It also tests a second placement where the cache with more ways has more misses despite equal total capacity.

rotating = [A, B, C] * 3
assert [misses(simulate(rotating, ways)) for ways in (1, 2, 4)] == [9, 9, 3]

C_other = 0x0200
merged = [A, B, C_other] * 3
assert [misses(simulate(merged, ways)) for ways in (1, 2, 4)] == [7, 9, 3]
assert [row["set"] for row in simulate([A, B, C_other], 1)] == [0, 0, 32]
assert [row["set"] for row in simulate([A, B, C_other], 2)] == [0, 0, 0]
print([misses(simulate(merged, ways)) for ways in (1, 2, 4)])

More ways can also merge previously separate sets

Move only C’s requested block to 0x0200, block number thirty-two. Direct mapping sends it to set thirty-two while A and B still fight over set zero. After C’s initial miss, its later two requests hit because A and B cannot evict it. That gives seven misses in nine requests.

The two-way cache has thirty-two sets, so block thirty-two wraps to set zero. All three blocks now compete for two lines, and rotating them produces nine misses. Associativity increased, but the number of sets fell and the placement changed. A claim that more ways can never hurt needs assumptions this fixed-capacity comparison does not satisfy.

View full-size image ↗

The table reports request counts only. Fewer misses need not imply a proportional runtime improvement: hit latency, miss overlap, lower-level behavior and the rest of the program are absent. More candidate tag comparisons, selection logic and replacement state can also change implementation cost. This model supplies neither nanoseconds nor area or energy estimates.

For an exercise, keep the rotating order but move C to 0x0010, block one. It now selects set one in all three versions. Predict the misses before running the model: direct mapping still has seven, while two-way and four-way each have three. A and B fit together only in the associative versions, and C remains separate. This small change isolates placement from access order; it is not a general recommendation to pad real arrays without checking the processor’s actual cache indexing and address translation.