The Predictability of Computations that Produce Unpredictable Outcomes

We study the dynamic stream of slices that lead to branches that foil an existing branch predictor and to loads that miss and measure whether these slices exhibit locality (i.e. repetition). We argue that this regularity can be used to dynamically extract slices for an operation-based predictor that speculatively pre-computes a load address or branch target (i.e. an outcome) rather than directly predicting the outcome based upon the history of outcomes. We study programs from the SPEC2000 suite and find they exhibit good slicelocality for these problem loads and branches. Moreover, we study the performance of an idealized operation-based predictor (it can execute slices instantaneously). We find that it interacts favorably with an existing sophisticated outcome-based branch predictor, and that slice-locality provides good insight into the fraction of all branch mispredictions it can potentially eliminate. Similar observations hold for operation-based prefetching of loads that miss. On average slice locality for branches and loads was found to be above 64 % and 76 % respectively when recording the 4 most recent unique slices per branch or load over a window of 64 committed instructions, and close to 61 % and 73 % for branches and loads respectively when we look at slices over a window of up to 128 committed instructions. The idealized operation predictor was found to correct approximately 68 % of branch mispredictions or prefetch about 67% of loads that miss respectively (slices detected over a window of 64 instructions). At the same time, on average, the branch operation predictor mispredicts less than 0.6 % of all branches that are correctly predicted by an existing branch predictor