Visualization enables the programmer to reduce cache misses

Many programs execution speed suffer from cache misses. These can be reduced on three different levels: the hard ware level, the compiler level and the algorithm level. Much work has been done on the hardware level and the compiler level, however relatively little work has been done on assisting the programmer to increase the locality in his programs. In this paper, a method is proposed to visual ize the locality which is not exploited by the cache hard ware, based on the reuse distance metric. Visualizing the reuse distances allows the programmer to see the cache bottlenecks in its program at a single glance, which al lows him to think about alternative ways to perform the same computation with increased cache efficiency. Fur thermore, since the reuse distance is independent of cache size and associativity, the programmer will focus on op timizations which increase cache effectiveness for a wide range of caches. As a case study, the cache behavior of the MCF program, which has the worst cache behavior in the SPEC2000 benchmarks, is visualized. A simple op timization, based on the visualization, leads to consistent speedups from 24% to 48% on different processors and cache architectures, such as PentiumII, Itanium and Alpha