Increasing Cache BandWidth
1. Pipelined caches
	A. Pipelining
    B. Miss Status Handling Register (MSHR)
2. Nonblocking caches
3. Multibanked caches

1. Pipelined caches

A. Pipelining

A processor's clock cycle can be no shorter than its slowest single step (the critical path). A cache access is one of the slowest steps: decode the index, read the arrays, compare tags, select the data. If the whole access has to fit in one cycle, it limits the clock speed of the entire CPU.

The idea: split the cache access into stages

Pipelining the cache works like an assembly line. The access is cut into stages, for example index → read → tag compare → data out, with latches between them. Each stage is short, so the clock can be faster. A new access can enter the cache every cycle, while earlier ones are still in later stages.

Two things change, and it's important to keep them apart:

• Bandwidth goes up: more accesses finish per nanosecond, one per (shorter) cycle.
• Latency does not improve: each access still takes about the same real time, a little more because of latch overhead. Measured in cycles, a hit now takes k cycles instead of 1.

1stage

2stages

3stages

4stages

What to notice as you go from 1 to 4 stages:

The clock cycle shrinks, from about 2.1 ns to 0.6 ns, so the whole CPU can run faster.
Bandwidth more than triples, because a new load starts every cycle.
Hit latency in real time rises slightly, from 2.1 ns to 2.4 ns, because each latch adds overhead. Pipelining never makes a single access faster.
Hit latency in cycles grows from 1 to 4, which is where the costs come from.

Each step allowed a much higher clock rate. The Pentium 4 was designed for very high GHz, which is why it pipelined the cache (and everything else) so deeply.

The two costs in your notes

1. More cycles between issuing a load and using its data (load-use delay)
   With a 4-cycle hit, an instruction that needs the loaded value must wait extra cycles, the yellow "wait" boxes in the widget:

lw   r1, 0(r2)     # load, takes k cycles
add  r3, r1, r4    # needs r1, so it stalls k-1 cycles

The processor hides this by doing independent work in the gap. The compiler schedules other instructions between the load and its use, or out-of-order execution (which the Pentium Pro introduced) runs later instructions that don't depend on the load. If there's nothing independent to run, the stall shows up.

2. Greater penalty on mispredicted branches
   The instruction cache is pipelined too, so fetching instructions takes more stages, and the whole CPU pipeline gets longer. When a branch is mispredicted, every instruction fetched after it is wrong and must be thrown away, and the pipeline must refill from the correct address. More stages mean more wasted cycles per mistake. On a very deep pipeline like the Pentium 4's, this penalty is large, so good branch prediction becomes essential.

Pipelining the cache trades latency in cycles for higher clock rate and bandwidth. It pays off when the processor can keep the pipeline full with independent instructions and correct branch predictions, and it hurts when it can't.

B. Miss Status Handling Register (MSHR)

The bookkeeping hardware: MSHRs

A Miss Status Handling Register (MSHR) records one outstanding miss. There is one MSHR per cache block being fetched, and inside it a small list of every load and store waiting for that block.

Fields of one MSHR:

Fields of each load/store entry:

Two kinds of misses use these:

Primary miss: the first miss to a block. A new MSHR is allocated and a memory request is sent.
Secondary miss: a later miss to a block that is already being fetched. No new request is sent; an entry is added to the existing MSHR.
How it operates, step by step

Use Next to walk through a sequence of accesses. The cache has 2 MSHRs, each with room for 3 waiting loads or stores, and 64-byte blocks.

The operation rules from your slide, matched to the walkthrough
On a cache miss:

1. Search the MSHRs for the same block address.

   • Found (secondary miss, step 3): just add a new load/store entry to that MSHR. No new memory request is sent.
   • Not found (primary miss, steps 1 and 4): allocate a free MSHR, write the block address and the first load/store entry, and send the request to memory (Issued = 1).

2. If no MSHR is free, or the MSHR's entries are full, stall (step 5). The number of MSHRs sets how many misses can overlap.

When one word (or sub-block) of the line arrives (steps 6 and 7):
1. Check which entries are waiting for that word, using their block offsets.
2. Forward the data to the CPU. A load writes its destination register; a store merges its store-buffer data into the block.
3. Mark those entries invalid.
4. Write the word into the cache.

When the last word of the line arrives (step 8):

• Mark the MSHR invalid, so it is free for the next miss.

2. Nonblocking caches

A non-blocking cache (also called lockup-free) keeps working while it waits for a miss. The idea starts with what the CPU can do during a miss.

Why it's useful: out-of-order execution

An in-order CPU must stop when a load misses, because the next instruction may need that data. An out-of-order CPU can look ahead and run later instructions that don't depend on the missing data. Many of those are also loads and stores, so they need the data cache.

With a normal blocking cache, the cache refuses all requests until the miss is resolved. The CPU has independent work ready, but the cache won't serve it, so the CPU sits idle anyway.

A non-blocking cache keeps serving requests during a miss. The timeline below shows four loads: A (miss), B (hit), C (miss), D (hit). A hit takes 1 cycle, and a miss takes 10.

Three levels of non-blocking

Blocking: while A is missing, the cache ignores every request. B and D are hits, but they still have to wait.

Hit under miss: the cache serves hits while one miss is pending. B and D no longer wait for A. A second miss (C) still stalls the cache until A finishes, because only one miss can be tracked at a time.

Miss under miss (hit under multiple miss): the cache tracks several misses at once, so C's memory request is sent while A's is still in progress. Their waiting times overlap, and that gives the biggest saving.

The miss penalty for each individual miss doesn't change; A still takes 10 cycles. What drops is the effective miss penalty, the time the CPU actually loses, because useful work and other misses fill the waiting time.

The costs (from your notes):

• More complex cache controller. It must track many outstanding misses at once, remember which loads and stores are waiting for each one, and deliver data to the right place when it returns.

• The lower level must accept several requests at once. If memory can handle only one request at a time, the second miss waits anyway. That's why memory is split into multiple banks, so different misses can be served by different banks in parallel.

3. Multibanked caches

A banked cache is split into several independent pieces (banks), and each bank can serve its own access in the same cycle. Here is what that means and how addresses are spread across the banks.

The problem: one cache, one access at a time
A cache built as a single block of memory can handle one access per cycle. That becomes a bottleneck when many requests arrive together:

• An out-of-order CPU may issue several loads and stores per cycle.
• A non-blocking cache (the previous topic) has misses returning while new hits are being served.
• A multicore/multithreaded chip has many cores sharing one L2.

The solution: split the cache into independent banks
Divide the cache into several banks. Each bank has its own decoder and data array, so it can do its own access. If four requests go to four different banks, all four are served in the same cycle, giving four times the bandwidth.

Example: Sun T1 ("Niagara"). This chip has 8 cores running 32 threads, all sharing one L2. A single-ported L2 would be swamped, so it is split into 4 banks that work in parallel.

Which address goes to which bank? Sequential interleaving
Banking helps only if requests spread out across the banks. If they all land in the same bank, they must wait in line, which is called a bank conflict.

The simple mapping from your notes spreads consecutive blocks across banks in rotation:

bank number      = block address mod (number of banks)
position in bank = block address ÷ (number of banks)

With 4 banks, blocks 0, 1, 2, 3 go to banks 0, 1, 2, 3, then block 4 wraps back to bank 0, and so on. Since programs often access neighboring blocks (arrays, instruction streams), consecutive requests naturally hit different banks.

To get the block address from a byte address, divide by the block size first. For example, with 64-byte blocks, byte address 448 → block 448 ÷ 64 = 7 → bank 7 mod 4 = bank 3.

Pick an access pattern below (or click blocks to choose your own) and see how many cycles it takes to serve the requests.

The patterns show the point from your notes, that the address-to-bank mapping decides how well banking works. Sequential accesses spread out perfectly. Strides that are a multiple of the number of banks (like stride 4 with 4 banks) all pile into one bank and lose the whole benefit. That's why some designs use a hashed mapping (for example, XOR-ing some address bits) to break up such patterns.

Don't confuse ways and banks

Both split a cache into parts, but for different reasons: