An Analysis of the Performance Impact of Wrong-Path Memory Referenceson Out-of-Order and Runahead Execution ProcessorsOnur Mutlu Hyesoon Kim David N. Armstrong Yale N. PattHigh Performance Systems GroupDepartment of Electrical and Computer EngineeringThe University of Texas at AustinAustin, Texas 78712-0240TR-HPS-2005-001January 2005This page is intentionally left blank.An Analysis of the Performance Impact of Wrong-Path Memory Referenceson Out-of-Order and Runahead Execution Processors∗Onur Mutlu Hyesoon Kim David N. Armstrong Yale N. PattDepartment of Electrical and Computer EngineeringThe University of Texas at Austin{onur,hyesoon,dna,patt}@ece.utexas.eduAbstractHigh-performance out-of-order processors spend a significant portion of their execution time on the incorrect pro-gram path even though they employ aggressive branch prediction algorithms. Although memory references generatedon the wrong path do not change the architectural state of the processor, they can affect the arrangement of data inthe memory hierarchy. This paper examines the effects of wrong-path memory references on processor performance.It is shown that these references significantly affect the IPC (Instructions Per Cycle) performance of a processor. Notmodeling them can lead to errors of up to 10% in IPC estimates for the SPEC2000 integer benchmarks; 7 out of 12benchmarks experience an error of greater than 2% in IPC estimates. In general, the error in the IPC increases withincreasing memory latency and instruction window size.We find that wrong-path references are usually beneficial for performance, because they prefetch data that will beused by later correct-path references. L2 cache pollution is found to be the most significant negative effect of wrong-path references. Code examples are shown to provide insights into how wrong-path references affect performance. Wealso find that it is crucial to model wrong-path references to get an accurate estimate of the performance improvementprovided by runahead execution and to avoid errors of up to 63% in IPC estimates for a runahead processor.1. IntroductionHigh-performance processors employ aggressive branch prediction techniques in order to exploit high levels ofinstruction-level parallelism. Unfortunately, even with low branch misprediction rates, these processors spend a sig-nificant number of cycles fetching instructions from the mispredicted (i.e. wrong) program path. The leftmost bar in∗This work is an extended version of the work presented in the 2004 Workshop on Memory Performance Issues [16]. Section 3.2, whichexamines the effects of hardware prefetching; Section 5, which analyzes the effects of wrong-path memory references on runahead processors; andSection 6, which gives a survey of related research in speculative execution, are the major extensions to [16]. Section 4.4 is also extended in thiswork. Other sections are edited to include more explanations and data.1Figure 1 shows the percentage of total cycles spent fetching wrong-path instructions in the SPEC2000 integer bench-marks. The middle and rightmost bars of Figure 1 show the percentage of instructions fetched and executed on thewrong path1. On average, even with a 4.2% conditional branch misprediction rate, the evaluated processor spends47% of its total cycles fetching wrong-path instructions. 53% of all fetched instructions and 17% of all executedinstructions are on the wrong path. 6% of all executed instructions are wrong-path data memory access instructions(loads and stores).05101520253035404550556065707580859095100Percentage (%)% (cycles on wrong path / total cycles)% (fetched wrong path insts / all fetched insts)% (exec wrong path non-mem insts / all exec insts)% (exec wrong path mem insts / all exec insts)gzip vpr gcc mcf crafty parser eon perlbmk gap vortex bzip2 twolf ameanFigure 1. Percentage of total cycles spent on the wrong path, percentage of instructions fetched on the wrongpath, and percentage of instructions (memory and non-memory) executed on the wrong path in the baselineprocessor for SPEC 2000 integer benchmarks.Although wrong-path data and instruction memory references do not change the architectural state of the machine,they can affect the arrangement of data in the memory hierarchy. In this paper, we examine the effect of wrong-pathmemory references on the performance of a processor. In particular, we seek answers to the following questions:1. How important is it to correctly model wrong-path memory references? What is the error in the predicted perfor-mance if wrong-path references are not modeled?2. Do wrong-path memory references affect performance positively or negatively? What is the relative significanceon performance of prefetching, bandwidth consumption, and pollution caused by wrong-path references?3. What kind of code structures lead to the positive effects of wrong-path memory references?4. How do wrong-path memory references affect the performance of a runahead execution processor [7, 17], whichimplements an aggressive form of speculative execution?Our results indicate that wrong-path memory references significantly affect processor performance and not model-ing them may lead to errors of up to 10% in IPC estimates for an out-of-order processor and up to 63% in IPC estimates1Machine configuration and simulation methodology are described in Section 2.2for a runahead execution processor. Although they have a positive effect on performance for most of the benchmarksdue to prefetching, wrong path references negatively impact performance for a few others. We analyze the causes forthe positive and negative performance impact. We identify pollution in the L2 cache as the dominant negative effect ofwrong-path references and present code examples to illustrate the prefetching effects. We also find that not modelingwrong-path references result in the significant underestimation of the performance improvement provided by runaheadexecution.2. Experimental MethodologyWe use an execution-driven simulator capable of accurately fetching and executing instructions on the wrong pathand correctly recovering from mispredictions that occur on the wrong path. The baseline processor we model is an8-wide out-of-order processor with an instruction window that can hold 128 instructions. The conditional branchpredictor is a hybrid branch predictor composed of a 64K-entry gshare [13] and a 64K-entry PAs [24] predictor witha 64K-entry selector along with a 4K-entry branch target