Highly accurate data value prediction

Data dependences (data flow constraints) present a stubborn resistance to the amount of instruction-level parallelism that can be exploited from a program. Recent work has suggested that the limits imposed by data dependences can be overcome to some extent with the use of data value prediction. That is, when an instruction is fetched, its result can be predicted so that subsequent instructions that depend on the result can use this predicted value. When the correct result becomes available, all instructions that are data-dependent on that prediction can be validated. This paper investigates a variety of techniques to carry out highly accurate data value predictions. The first technique investigates the potential of using correlation in data value predictions. The second technique investigates the potential of monitoring the strides by which the results produced by different instances of an instruction change. The third technique investigates the potential of pattern-based two-level prediction schemes. The paper also presents the results from a simulation study that we conducted to verify the potential of the investigated prediction schemes. The results show that highly accurate data valve predictions are possible with two of the investigated schemes