A lockup-free cache is a common requirement for most latency-hiding techniques, including prefetching, relaxed consistency models, non-blocking loads, and multithreading. The complexity of implementing a lockup-free cache depends on which of these techniques it is intended to support (as described in detail by Laudon ). For example, if the goal is simply to support multiple outstanding prefetches, then it is not strictly necessary for the processor to maintain state on outstanding transactions, as long as the cache is prepared to receive prefetch responses from outside the processor while the processor may be simultaneously issuing new requests. In contrast, supporting multiple outstanding stores (as with relaxed consistency models) or loads (if they are non-blocking) does require that special state be maintained for each outstanding access. For stores, the stored data must be merged into the cache line when it returns. For loads, the requested data must be forwarded directly to a register-thus requiring state to associate each outstanding access with the register(s) waiting for the value-and any future uses of that register must interlock if the value has not returned yet.
Kroft  presented the original lockup-free cache design, which adds structures called ``miss information/status handling registers'' (MSHRs) to keep track of outstanding misses. Each MSHR contains enough state to handle one or more accesses of any type to a single memory line. Due to the generality of the MSHR mechanism, the amount of state involved is non-trivial, including the address, pointers to the cache entry and destination register, written data, and various other pieces of state. The majority of subsequent lockup-free cache proposals have been a variation of this original MSHR scheme . An alternative approach is to maintain the state of outstanding misses in the cache tag array itself , thereby permitting a larger number of outstanding misses.
For the uniprocessor architecture used in Chapter , the lockup-free cache supports a single load or store miss (since loads and stores directly stall the processor) and up to sixteen prefetch misses. The state of outstanding prefetch misses is maintained in a sixteen-entry prefetch issue buffer. This structure is simpler than a normal MSHR because it contains only the prefetch addresses and any state necessary to track or control outstanding misses. It does not contain any data, since the prefetched data is placed directly into the cache hierarchy.
To illustrate how the prefetch issue buffer is used, we will walk through the steps of processing a prefetch. When the processor executes a prefetch instruction, the primary data cache is checked during that cycle. If the data is already present in the cache, then the prefetch is considered completed at that point. Otherwise, the prefetch addresses is then compared against the addresses already in the prefetch issue buffer. If there is a match, then the prefetch is dropped. Otherwise, a new entry is allocated in the prefetch issue buffer for the new prefetch. At this point, the prefetch will proceed through the memory hierarchy to first find the data and then place it in the primary cache, as was discussed in Section . An entry in the prefetch issue buffer is deallocated as soon as the prefetch completes (as opposed to waiting for the data to actually be referenced).
Although a prefetch issue buffer is not strictly necessary, it offers the following performance advantages. First, in cases where the prefetch miss cannot be serviced immediately (perhaps because of a limited number of MSHRs), it allows the processor to continue executing by buffering the prefetch request. Second, by keeping track of the prefetches that are already outstanding, it provides a mechanism for merging subsequent prefetch and memory references to matching cache lines. Merging a prefetch with a previous prefetch simply means dropping the subsequent prefetch. This helps to avoid unnecessary bandwidth consumption further down the memory hierarchy, similar to the benefit of checking the primary cache when searching for the prefetched data (as discussed earlier in Section ). However, with selective prefetching, the compiler is generally good at avoiding back-to-back redundant prefetches (at least for these scientific codes). The more important benefit occurs when a load is merged with a previous prefetch that was partially completed, since this allows the load to benefit from whatever partial latency-hiding the prefetch has been able to accomplish. This is especially important for cases where data or control-flow dependencies make it impossible to issue prefetches early enough to hide the entire memory latency, which can occur frequently in pointer-based codes such as PTHOR (e.g., when attempting to prefetch a linked list).
Figure shows how the prefetch issue buffer is incorporated into our uniprocessor architecture. In this figure, we have shown distinct MSHRs to allow for the possibility that misses are handled separately from the buffering of prefetch requests. Note that in our model, a prefetch remains in the prefetch issue buffer until it is completed by its MSHR. In our experiments so far, we have assumed a sixteen-entry deep prefetch buffer and seventeen MSHRs (one for each prefetch and one for either a load or store). We chose these large parameters to minimize their effect on performance. We will now examine how many prefetch issue buffer entries and MSHRs are actually needed for our benchmarks.
Before running these experiments with reduced prefetch buffering and MSHR capacities, we can gain insight into what to expect by examining the number of outstanding prefetches in the original ``full-capacity'' architecture. Figure plots the distribution of prefetch misses already outstanding during each prefetch miss for the original architecture. As we see in Figure , the distributions vary considerably across applications. On the one extreme is EP, where there is almost never more than one outstanding prefetch. On the other hand there are programs like CHOLSKY, where the distribution is spread out over larger numbers of previously outstanding prefetches (i.e. the distribution has a significant tail). We would expect these latter types of applications to benefit from having multiple MSHRs and deep prefetch buffers.
To measure the actual impact on performance, we first varied the number of MSHRs while holding the depth of the prefetch issue buffer fixed at sixteen entries. Figure shows the results of these experiments. A single MSHR corresponds to a ``blocking'' cache (i.e. one that is not lockup-free), while seventeen MSHRs corresponds to the original architecture. Note that with fewer than seventeen MSHRs, there may potentially be more outstanding miss requests (up to seventeen) than can be serviced at a given time, in which case prefetch misses must compete with load and store misses for the MSHRs. We resolved such cases by giving load or store misses (which directly stall the processor) priority for the next available MSHR-otherwise, the oldest unserviced prefetch will be awarded the next available MSHR.
As we see in Figure , the benefits of a lockup-free cache are often substantial. Seven of the thirteen applications showed at least an 15%performance improvement by going from one to two MSHRs. In six of those seven cases, there was at least a 5%additional improvement from having four MSHRs. The benefits of moving from four to seventeen MSHRs were typically quite small. These performance improvements correspond to what we would expect from the distributions shown in Figure . In particular, the largest improvements occur in the benchmarks with the largest tails in their distributions (e.g., CHOLSKY, GMTRY, VPENTA, and CG). Therefore we see that it is important to have a lockup-free cache, and that four outstanding misses are sufficient to capture most of the benefits for these applications.
Given that four MSHRs are sufficient, the next question is whether buffering additional prefetch requests beyond that is advantageous, or whether the prefetch issue buffer should also be reduced to four entries. To evaluate this, we simulated the performance when the number of prefetch issue buffer entries is reduced, while holding the number of MSHRs fixed at four. Figure shows the two cases (CHOLSKY and VPENTA) where this caused a noticeable difference in performance (in six of the other cases, there was less than a 2%difference between four and eight buffer entries, and no difference between eight and sixteen buffer entries). CHOLSKY showed the largest improvement, with a 6%speedup when going from four to eight buffer entries, and 5%speedup beyond that for having sixteen entries. VPENTA showed a 5%speedup between four and eight entries, and 1%additional speedup with sixteen entries. Therefore we see that additional prefetch buffering is beneficial in a small number of cases. However, given that this benefit is relatively small and infrequent, the hardware cost would also have to be quite small for it to be justified.