Next: Summary Up: Dropping Prefetches Previous: TLB Miss

Full Prefetch Issue Buffer

For our experiments in Chapter , we assume that if the processor attempts to issue a prefetch while the prefetch issue buffer is full, the processor stalls until an entry becomes available. We now consider what happens if prefetches are instead dropped on a full prefetch issue buffer.

In the architectural model presented so far, the memory subsystem has a finite (16-entry) prefetch issue buffer to hold outstanding prefetch requests. In our model, a prefetch is inserted into the buffer only if it misses in the primary cache and there is not already an outstanding prefetch for the same cache line. Also, a prefetch is removed from the issue buffer as soon as it completes (i.e. the buffer is not a FIFO queue); reordering may occur due to variations in miss latencies. Despite some of these optimizations, the buffer may still fill up if the processor issues prefetches faster than the memory subsystem can service them.

Once the prefetch issue buffer is full, the processor is unable to issue further prefetches. At that point the choices are either to stall the processor until a buffer entry becomes available, or else drop the prefetch and continue executing. Intuitive arguments might be presented to support either approach. On one hand, if the data is needed in the future and is not presently in the cache (since only prefetches that miss go into the buffer), it may appear to be cheaper to stall now until a single entry is free rather than to suffer an entire cache miss sometime in the future. On the other hand, since a prefetch is only a performance hint, perhaps it is better to continue executing useful instructions.

To understand this issue, we ran each of our uniprocessor benchmarks again using a model where prefetches are dropped rather than stalling the processor when the prefetch issue buffer is full. We ran this model for both the indiscriminate and selective prefetching algorithms. Figure shows the cases where this affected performance. We begin by focusing on the indiscriminate algorithm, and then later focus on the selective algorithm.

For all seven cases where the performance of the indiscriminate algorithm changed (shown in Figure (a)), the performance improved by dropping prefetches. The improvement is dramatic in the two cases that had previously stalled the most due to full buffers (CFFT2D and CG). There are two reasons why the performance improves substantially for the indiscriminate prefetching algorithm. The first reason is that dropping prefetches increases the chances that future prefetches will find open slots in the prefetch issue buffer. The second is that since the indiscriminate algorithm has a larger number of redundant (i.e. unnecessary) prefetches, dropping a prefetch does not necessarily lead to a cache miss. It is possible that the algorithm will issue a prefetch of the same line before the line is referenced. Dropping prefetches has the effect of sacrificing some amount of coverage (and therefore memory stall reduction) for the sake of reducing prefetch issue overhead. This effect is most clearly illustrated in the case of CG (see Figure (a)), where memory stall time doubles for the indiscriminate algorithm once prefetches are dropped.

The selective prefetch algorithm, in contrast, did not improve from dropping prefetches since it suffered very little from full prefetch issue buffers in the first place. In fact, in the three cases shown in Figure (b), the selective algorithm performed slightly worse when prefetches are dropped. The reason why is that since selective prefetching has eliminated many of the redundant prefetches, it is more likely that dropping a prefetch would translate into a subsequent cache miss. However, as we have already seen in Figure , the selective algorithm tends to suffer very little from full issue buffers, and therefore performs well in either case.

Next: Summary Up: Dropping Prefetches Previous: TLB Miss

Sat Jun 25 15:13:04 PDT 1994