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.