Modeling value speculation: an optimal edge selection problem

Techniques for value speculation have been proposed for dynamically scheduled and statically scheduled machines to increase instruction-level parallelism (ILP) by breaking flow (true) dependences and allowing value-dependent operations to be executed speculatively. The effectiveness of value speculation depends upon the ability to select and break dependences to shorten overall execution time, while encountering penalties for value misprediction. To understand and improve the techniques for value speculation, we model value speculation as an optimal edge selection problem. The optimal edge selection problem involves finding a minimal set of edges (dependences) to break in a data dependence graph that achieves maximal benefits from value speculation, while taking the penalties for value misprediction into account. Based on three properties observed from the optimal edge selection problem, an efficient optimal edge selection algorithm is designed. From the experimental results of running the optimal edge selection algorithm for the 20 most heavily executed paths selected from each SPECint95 benchmark, several insights are shown. The average critical path reduction is 9.61 percent on an average and 25.57 percent at its maximum. Surprisingly, 66 percent of the edges selected by the optimal algorithm have value prediction accuracies over 99 percent. Moreover, most of the selected edges cross the middle of the data dependence graph. The selected producer operations thereby tend to reside in the upper portion of the data dependence graph, while the selected consumer operations appear toward the lower portion.