Cache behavior in the presence of speculative execution: The benefits of misprediction.
James Edward Pierce · Deep Blue (University of Michigan) · 1995
Cache performance analysis is becoming increasingly important in microprocessor design. This work examines the effect of mispredicted-path memory references on cache performance and proposes a new algorithm to prefetch instruction cache lines. The first cache study describes the effects of deep speculation on data cache miss rates and memory traffic. The major result was that traffic is only slightly increased by speculation--less than 15% for most SPEC benchmarks even when executing 50 instructions down a mispredicted path. Cache misses are not significantly increased because the mispredicted paths references act as prefetch operations for later correct path references. The latter result led to the development of a new instruction cache prefetching algorithm called wrong-path prefetching. Using trace-driven simulation, wrong-path prefetching was found to offer higher performance than other prefetching algorithms at an equivalent or lower hardware cost. The algorithm reduced CPU cycle time by up to 16% in current-generation cache configurations. While prefetching does increase bus traffic, reallocating hardware resources to increase bus bandwidth in conjunction with the use of a prefetch scheme is shown to reduce the required cache size by up to a factor of 4 with only a minor increase in bus utilization. It is also shown that prefetching algorithms become even more effective (over 20% cycle reduction) on next-generation microprocessors characterized by long memory latencies, high IPC rates, and multiple memory ports. An analytical cache model is extended to predict the miss rates of a prefetched cache. The accuracy of the model verifies the behavior of the prefetch algorithms. The work also includes a survey of instrumentation programs which are used to gather execution traces for trace-driven performance simulation. The different approaches to designing the tools as well as the problems encountered when building them are discussed. Two instrumentation tools, IDtrace and spex, which were built for the Intel Architecture, are described in detail.