The problem of target prediction for indirect branches has been investigated for C and C++ programs. Calder and Grunwald proposed a 2-bit strategy for updating the branch target buffer (BTB) [18]. The target address entry in the BTB is updated only when two consecutive predictions at that target address are incorrect. This strategy as opposed to the default strategy of updating the entry on each misprediction was shown to improve the performance. Emer and Gloy present several single-level predictors based on a combination of the values of program counter, stack pointer, register number and stack address [19]. They performed their study on SPECint95 programs.
Previous research has shown the use of correlation information from path history to predict the execution of direct branches [8,16]. Recently, the path history information has been used to predict indirect branches [17,20]. Chang, Hao and Patt proposed a target cache that uses the branch history to distinguish different dynamic occurrences of each indirect branch [17]. Their study was performed on select SPECint95 programs. Their work also shows the correlation between higher misprediction rates and slower execution speed. In this paper, we make use of this observation and focus on improving misprediction rates. The object oriented programs in C++ and Java use indirect branches with a much higher frequency than in SPECint95 programs. Target address prediction for indirect branches using a suite of C++ programs and SPECint95 was performed in [20]. Their study investigated the impact of various hardware constraints on the performance of a path history based predictor. Our work uses a similar approach in investigating the indirect branch behavior of Java programs. Unlike the previous efforts, the focus of this work is confined to the target prediction of indirect branches that occur due to the virtual method invocations. The best way to improve the performance of virtual method invocations is to eliminate the virtual calls by inlining or statically binding them [14]. However, only a portion of the calls can be safely bound statically [15]. We identify Java code characteristics that enable the use of path based predictors in identifying the target of the virtual calls.
Since virtual method invocation has been identified as one of the major bottlenecks for the performance of Java code [11,13], the impact of the various parameters of the path history predictor on prediction accuracy is investigated in this work. It was observed in [11] that the proportion of virtual methods is likely to increase due to the trend towards fine-grained object design in Java applications. In such an environment, big objects become many smaller objects. Consequently big methods become many smaller methods. This causes many more method invocations and method invocation increasingly becomes a performance bottleneck. In [13], profiling of various Java benchmarks was done to identify virtual methods as one of the bottlenecks in Java execution. This work also investigated the receiver type locality at virtual method call sites.
Java performance studies have been performed in [9], [10] to investigate the need for architectural support for Java execution. In [10], it was concluded based on their study of Java interpreters that it may be premature to provide hardware support for Java execution. The results of this paper indicate that the micro-architectural resources such as branch predictors can be enhanced to support Java execution. However, it must be noted that the support proposed here is based on the Java language characteristics rather than just the interpreter characteristics analyzed in [10].
| Benchmark | BTB | 2-bit BTB |
| misses (%) | misses (%) | |
| Javac | 4.8 | 3.9 |
| Javadoc | 3.5 | 2.4 |
| Richards | 23.4 | 27.1 |
| Deltablue | 1.7 | 1.2 |
| Heap | 2.6 | 2.1 |