Choosing the right references to prefetch is only one part of maximizing the prefetching benefit-making those prefetches effective at eliminating cache misses is also critical. The measure of success for effective prefetching is that all prefetched references should find their data in the cache. The first step toward this goal is timing the arrival of the prefetched data in the cache to maximize the likelihood of it being found there by the subsequent reference. Ideally, prefetches should arrive in the cache ``just in time'' to be referenced, since prefetches arriving too late obviously cannot prevent misses, and prefetches arriving too early are susceptible to being replaced by other references. The second step toward effective prefetching is avoiding excessive cache conflict problems that can render ineffective even prefetches that are scheduled the proper amount of time in advance.
The prefetching algorithm described so far addresses only the first of
these two goals, and it does so by computing the proper number of
iterations to software-pipeline prefetches ahead (see
Section 
). This task is made difficult only by
the variability in both memory access times and path lengths through the
loop body. To be conservative, the compiler schedules for the largest
expected memory latency (300 cycles in our experiments) and the shortest
loop body path. Therefore the prefetched data can potentially arrive quite
early in the cache if it is found close to the processor. However, despite
being conservative, the compiler is usually quite successful at scheduling
prefetches effectively.
In the cases where prefetches are ineffective, the
problem is caused more by excessive cache conflicts than by the timing of
the prefetches. The intuitive explanation for this is that although
prefetches may arrive early, the number of other lines that are brought
into the cache during this interval is relatively small compared to the
cache size. Therefore it is only likely that prefetched data will be
displaced if the frequency of cache mapping conflicts is unusually high. To
address this problem, we will now focus on techniques for coping with these
cache conflicts.