The number of target addresses of the virtual methods registered in each history buffer is called as the history path length, p. When p=0, the two-level path history predictor becomes a single level predictor similar to the BTB strategy. The variation in path length can help in determining whether the correlation among the target addresses of virtual methods is long-term or short-term. The effect of path length variation was studied with a fully associative target buffer of unlimited size along with a global path history. Figure 6 shows the results of this study for the different benchmarks.
The path length affects the misprediction rate in two ways. Firstly, misses occur when the path length is too small to capture a long-term dependence. Secondly, longer paths take a longer time to adapt to branch behavior changes and this results in start-up misses. Thus, a longer path would capture more long term dependence but would have more start-up misses. In contrast, a shorter path fails to capture the long-term regularities in method invocation targets but adapts quickly to changes in branch behavior.
The javac benchmark reflects this tradeoff clearly. The misprediction rate reduces from 4.6% when the path length is zero to a misprediction rate of 2.6% when the path length is two. In this phase, the effect of capturing more regularities dominates the effect of start-up misses. However, the misprediction rates increase when the path length is increased beyond two, specifically from 2.6% to 5.1% when path length is increased from two to seven. The start-up misses begin to dominate any improvement obtained by capturing virtual method history dependence longer than two. This indicates that most path history patterns used in javac have a relatively short period. The javadoc benchmark also exhibits a similar behavior.
The heap benchmark does not benefit from the path history information. It is observed that the branch target buffer scheme performs better than the predictor with the path history. This is due to the relatively constant target addresses at the call sites in the heap benchmark. Hence, the path history information only adds to the start-up misses and does not benefit from capturing any additional regularities. In contrast, the richards and deltablue benchmarks benefit from long path lengths. The misprediction rates keep decreasing as path lengths increase from 0 to 8. This shows that these benchmarks have a long-term correlation that enables the overshadowing of start-up misses associated with longer paths. These results indicate that the optimum values for the path length differ based on the benchmark.
 |