Check out the new USENIX Web site. next up previous
Next: Background Up: Tuning Branch Predictors to Previous: Abstract

Introduction

Java is a class-based object oriented language that is used extensively for building networked applications. Some of the features of Java such as the use of virtual methods, dynamic loading and symbolic resolution that make it suitable for developing networked software applications also slow the execution speed of Java code. In this paper, we focus on addressing the performance issues involved with the use of virtual methods in Java.

The use of virtual methods as the default method invocation mechanism results in the execution of frequent indirect branch executions. The invokevirtual JVM bytecode [1] that is used to perform virtual method calls constitutes 5% of the Java bytecodes executed on an average for the benchmarks shown in Table 2. Many of the current JVM implementations such as Sun's JDK interpreter and CACAO Just-in-Time Compiler[2] use a dispatch table to implement the invokevirtual bytecode. When a virtual method is invoked, the target address is obtained from a fixed index into the the dispatch table of the current object. Finally, an indirect branch instruction is executed to jump to the fetched target address. Thus, an indirect branch is executed for every virtual method invoked. The accurate prediction of these indirect branches is critical to the performance of Java virtual machine (JVM) implementations executing on deeply pipelined systems. Speculative execution is used in such architectures to avoid the performance loss associated with the execution of branch instructions. Accurate branch predictors are essential to avoid discarding the results of the speculative execution following a misprediction.

Current processors employ a branch target buffer (BTB) based mechanism to predict the indirect branches [12]. The misprediction rates for virtual method calls using the branch target buffer is found to range up to 27% as shown in Table 1 for the studied benchmarks. Previous researchers have successfully used path history information to improve the prediction of direct branches [8,16]. In this paper, the path history of virtual method calls is used to predict target addresses of virtual method invocations. The path history provides the capability to distinguish between different dynamic executions of the same virtual method. In the path history based predictor, a hashing function of the path history of target addresses and the virtual method call site address is used to index a target cache. The cached entry provides the predicted target address of the virtual call.

The paper is organized as follows. Section 2 discusses the background and motivation for this work. In section 3, the path history based target address predictor is introduced. Next, the experimental strategy and benchmarks used in this study are explained in section 4. The effect of the various parameters of the path-history based target address predictor on the performance of the predictor is studied using the benchmarks in Section 5. Starting from a fully associative target buffer of unlimited size, the parameters are optimized sequentially to account for the hardware constraints such as buffer size and limited associativity. The number of history buffers, the path history length, the number of target address bits, the hashing function, and the buffer structure were the parameters varied. Concluding remarks are provided in Section 6.


next up previous
Next: Background Up: Tuning Branch Predictors to Previous: Abstract
Vijaykrishnan Narayanan
1999-02-24