Exploiting Method-Level Parallelism in Single-Threaded Java Programs
Michael K. Chen and Kunle Olukotun
Computer Systems Laboratory, Stanford University
Stanford, CA 94305-4070
http://www-hydra.stanford.edu/

Method speculation of object-oriented programs attempts
to exploit method-level parallelism (MLP) by executing sequential method invocations in parallel, while still maintaining correct sequential ordering of data dependencies and memory accesses. In this paper, we show why the Java virtual machine is aneffective environment for exploiting method-level parallelism, anddemonstrate how method speculation can potentially speed up
single-threaded, general purpose Java programs. Results fromour study show that significant speedups can be achieved ondata-parallel applications with minimal programmer and compiler effort. On control-flow dependent programs, moderate speedups have been achieved, suggesting more significant performance
improvements on these types of programs may come from more
careful analysis or re-coding of the application. For both classesof applications, we discover performance debugging drastically
improves speedups by eliminating or minimizing dependencies
that limit the effectiveness of method speculation.

1

Introduction

threadbus-based multiprocessor
methodchip multiprocessor
loop

instruction

superscalar

1M

number of instructions

100k

10k

1k

100

10

In this paper, we investigate the effectiveness of using method
speculation running on a chip multiprocessor [12] to exploit methodlevel parallelism (MLP) in single-threaded, general purpose Java
programs. Method speculation might be thought of as the next
logical step beyond current superscalar processors that exploit
instruction-level parallelism (ILP). As depicted in Figure 1, methods
correspond to blocks of many instructions. Coarse grain parallelism
found between method blocks can potentially lead to speedups
not available to superscalar processors. Studies [18] [9] haveshown that instruction level parallelism (ILP) in superscalar
processors is ultimately bounded by the limited size of the instruction
window and control-flow dependencies. The lack of hardware for
effective memory disambiguation also limits the parallelism
available to these processors. Even with large instruction windows,
current superscalar processors are architecturally designed toresolve dependencies between registers, not memory locations.
Likewise, bus-based multiprocessors may be good at exploiting
thread-level parallelism, but they are ineffective on loop-level andmethod-level parallel tasks because of the relatively high cost ofcommunication. With a low-latency communication network andmethod speculation support, a speculative chip multiprocessor
configuration can exploit levels of parallelism not available tosuperscalar processors or traditional bus-based multiprocessors[12].
Current microprocessors [5] exploit instruction level parallelism
using out-of-order execution. The processor selects instructions
from a large instruction window, speculatively executes these
instructions out-of-order, and buffers the results in a reorder buffer.
The instructions are then committed to the permanent architecturalstate in the original program order. In the case of instructions thatare incorrectly executed due to branch mispredictions or the use ofstale values, the processor must back up and restart execution.
Whereas the granularity of an entry in the reorder buffer of asuperscalar machine corresponds to a single instruction, such an
entry for a speculative multiprocessor analogously corresponds
to a single speculative task. In method speculation, sequential
method invocations are mapped to speculative tasks that are
executed in parallel with the in-order thread. When execution
reaches a method marked as speculative, the in-order thread
continues to execute that method, but forks off a new speculative
task that executes in parallel starting from the method return(continuation). Speculative memory stores and register file writes
encountered during execution are buffered with each speculativetask. These changes are committed to the head, in-order threadwhen sequential execution reaches the point at which the
speculative task would have executed normally without speculationlevels of parallelism

Abstract

Figure 1 - A single chip multiprocessor can exploit levels ofparallelism not available to traditional superscalar
processors or bus-based multiprocessors.

Copyright 1998 IEEE. Published in the Proceedings of PACT'98, 12-18 October 1998 in Paris, France. Personal use of this material is permitted. However, permission toreprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any
copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane
/ P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 732-562-3966.

support.
To guarantee correct parallel execution of these speculative
tasks, our hardware ensures stores from earlier tasks are forwarded
to reads by later tasks. Because this special hardware guarantees
correct sequential ordering of memory references, we can forgo
any explicit synchronization that is usually required for correct
parallel execution on traditional parallel architectures. If a memory
read-after-write (RAW) violation occurs (caused by a preemptive
load by a later speculative task to a shared memory location written
late by an earlier speculative task), the speculative task is aborted
and restarted so that it can load the correct value from this memory
location. To restart a speculative task, buffered stores from theaborted speculative task are discarded, and the register file andprogram counter (PC) are restored to their state prior to the start of
speculative execution.
Franklin and Sohi first proposed the basis of hardware
speculation in the context of the Wisconsin Multiscalar project[16] [3]. Their architecture is tailored more to speculating on
relatively fine-grained tasks. Our work is based on a speculation
model proposed for a chip multiprocessor, a design targeted to
speculate on coarser-grained tasks [4]. Details of this design andmore careful analysis of assumptions are discussed in [4] and [14].
We believe the Java language and virtual machine environment
can serve as a vehicle to explore capabilities of speculation in a realsystem. Java will enable us to examine speculation performancefor object-oriented programs (OOP), create a clean execution model
for method speculation, and develop a realistic runtime system todynamically manage method speculation.
Results from our study show that significant speedups canbe achieved through method speculation on data-parallel
applications with minimal programmer and compiler effort. On
control-flow dependent programs, moderate speedups have beenachieved, suggesting more significant performance improvementson these types of programs may come from more careful analysis
or re-coding of the application. For both classes of applications,
we discovered performance debugging drastically improves
speedups by eliminating or minimizing dependencies that limit theeffectiveness of method speculation.
In Section 2, we describe our motivation for studying method
speculation under Java. The assumptions about the target
architecture and simulation methodology used to evaluate
speculation are discussed in Section 3. In Section 4, we describe
our benchmark suite, with the results of our study given in Section
5. Closing remarks are made in Section 6, and future plans arepresented in Section 7.

2

Method Speculation of Java Programs

While this paper concentrates on using Java for method
speculation, it is important to briefly discuss why we believe a chip
multiprocessor architecture is an ideal platform for general, highperformance Java computing. A chip multiprocessor architecture
supports low latency communication between processors [12].

Such a parallel architecture is ideal for supporting many features of
the Java language and Java virtual machine:• Explicit thread model and synchronization primitives in the Java
language allow the programmer to easily write programs to
exploit the underlying multiprocessor hardware.
• Low latency inter-processor communication can reduce theoverhead for accessing locks in the virtual machine. Our evaluations confirm Hölzle et al.’s findings that show such overheads
can represent a significant fraction of overall execution time [7].
• Virtual machine data structures shared between application
threads can be cached in the shared L2 cache, reducing accesslatency to these system resources.
• The overheads of many coarse-grained virtual machine operations like class loading, bytecode verification, garbage collection and just-in-time (JIT) compilation could be hidden by executing them concurrently with actual application execution.
Many obvious levels of parallelism exist in the virtual machine.
Unfortunately, most of the coarse-grained parallelism present in
the virtual machine only represents single event parallelization
opportunities. As Amdahl’s Law tells us, the effects of speedingup these phases of execution will have a smaller performance impact
on long running applications because most of the execution time
will be spent executing application code. While multithreaded
Java applications will clearly benefit from a multiprocessor, method
speculation can provide the following additional advantages:• Facilitates easy and straightforward parallelization. Modern
parallelizing compilers have been most successful with scientific applications. For many classes of general applications,though, these compilers fail because they cannot analyze nonuniform memory accesses patterns and cannot resolve memory
pointer ambiguities. Without a compiler, significant programmer effort is required to explicitly hand-parallelize applications
using Java thread and synchronization primitives. Worst of all,parallelization results in programs that are difficult to understand. Method speculation is a simpler programming modelthat can expose loop-level and method-level parallelism in theapplication so that it can be exploited by the underlying hardware. As we shall see, most programs can use method speculation with little or no modification to the original application.
• Reduces parallelization overheads. Thread and synchronization primitives generally introduce significant overheads into
the execution time not present in the sequential version of aprogram. Method speculation can guarantee that dynamic execution dependencies will always be correct, with smaller
overheads then those introduced by locks and barriers. Without these costly synchronization overheads, we can also expect to see speedups on finer grains of parallelism that would
not be possible using traditional parallelization methods.
• Can speed up control-flow limited programs that have very little
obvious parallelism. Programmers should be able to benefit
from the multiprocessor architecture even when running singlethreaded applications with very little fine- or coarse-grained
parallelism.

Java will enable us to examine method speculation performancefor object-oriented programs (OOP), create a clean execution model
for method speculation, and develop a realistic runtime system todynamically manage method speculation.
Using procedure or function calls as a framework to parallelize
programs was first mentioned by Knight in the context of Lisp [8].
Oplinger et al. has also examined loop and procedural speculation
through a limit analysis based on C programs using an ideal
environment with many simplifying assumptions [13]. The focusof their study was to show that general applications exhibit
significant amounts of loop- and procedural-level parallelism. Since
this paper is more concerned with implementing a real system, ouranalysis will rely on more realistic assumptions given in Section 3.

void main () {...
...

method1()...
...
method2()

Object-oriented programs represent a class of applications
that may behave differently from general C programs under method(procedure) speculation. A study by Calder et al. shows thecharacteristics of C and C++ programs to be significantly different[2]. They show the dynamic function size of C programs to be fourtimes that of C++ programs, and the frequency of procedure calls
and returns in C++ to be three times that of C programs. Thesefindings support our understanding of how object-oriented
programs are written. The encapsulation model increases thefrequency of small method calls, reducing the dynamic function
size and increasing the number of method calls and returns.
These characteristics suggest that method invocations canefficiently expose loop- and method-level parallelism in objectoriented programs. Method speculation uses the notion of
speculative tasks. When a method marked as speculative isencountered, the current processor executes the method and aforked speculative task executes in parallel starting from the method
return (continuation). This mapping of methods to speculative
tasks is depicted in Figure 2. If the method call returns a value, thespeculative task executes assuming a predicted return value basedon previous executions of that method. If this predicted return
value turns out to be incorrect or there is a RAW violation in theheap due to the ordering of field loads and stores between tasks
executing in parallel, then the speculative task must be terminatedand restarted.
Method speculation is most effective for frequently executed
methods that return void or a predictable return value. Thesetypes of return values are frequently found in methods returning
boolean values that check for infrequent cases, but are notcrucial to the flow of program execution. A method call like
isValid() might do checks to make sure certain conditions aremet, returning true 95% of the time. Another example is a method
isEOF() that signals the presence of another value in the data
stream. This method will almost always return true when iterating
through a large data structure.
Method speculation can permit sequences of read only or
write only methods to execute in parallel without worrying about

this.method2();

head

register
state

...
RAW

viola

tions

...
specTask 1

load resolution
main mem

register
state

RAW

}

viola

tions
specTask 2

load resolution

2.1 Method Speculation on Object-Oriented
Programs

rvalue = this.method1();

return value

store
bufferregister
state

store
bufferFigure 2 - Mapping of methods to speculative methods.
RAW violations. Traditional loop-level parallelism can even be
exploited within our method speculation framework with minimal
programmer effort or with modern parallelizing compilers, as weshall show later.

2.2 Mapping Speculation to Method
Invocations
Using method calls as the granularity of speculative tasks
conveniently allows us to exploit characteristics of the Java virtual
machine specification so that no transformations to the sourceclassfiles are required for speculative execution. In Oplinger et al.’s
study, static analysis of the C source programs was required toconvert a normal program into a single-program-multiple-data
program suitable for running on a speculative machine [13] [14].
This analysis can be simplified considerably in Java. The Java
Virtual Machine Specification [10] states:• A method can only access its private Java stack and locals, orheap allocated objects. A callee method shares values from thecaller only through explicitly passed arguments using a copying, pass-by-value convention and a single return value. Arguments and return values may include references to heap allocated objects shared between the caller and callee.
• Specific Java bytecodes (getfield, putfield, getstatic,
putstatic, arrayload, and arraystore) make object (heap)
accesses explicit and distinct from Java stack and local operations (load, store, push, pop, etc.).
These restrictions allow us to simplify our simulator by
eliminating Java stack and local accesses from our dependency
analysis. Since caller and callee methods work with their own
private Java stack and locals, RAW violations can only occur
between speculative tasks through objects dynamically allocatedin the heap. This simplified analysis is not possible with C programs
since the ability to manipulate pointers makes it impossible toguarantee that heap and execution stack accesses are well-behaved.

3

2.3 Dynamic Management of Method
Speculation
Previous performance results for speculation [13] assumed
optimally chosen method granularities taken from the dynamic
execution profile. Our simulations suggest that choosing theappropriate methods for method speculation can dramatically affectperformance gains. The Java virtual machine serves as an ideal
platform for investigation of a runtime profiling system that candynamically identify methods for method speculation from Java
bytecodes using some set of heuristics.
Our system would be similar to the runtime system of the
HotSpot Java virtual machine that uses dynamic method callfrequencies to identify methods to compile just-in-time [7] [17].
Relevant statistics collected during runtime would be fed back tomark or unmark methods to speculate on so that our system candynamically adapt to new data sets, or converge on an optimum
runtime configuration. Profile information collected during execution
could also be returned to the programmer and/or user to help
increase the effectiveness of speculation.
We have developed a basic profiling system used to help
identify methods to speculate on. An effective runtime profilingsystem preserves a delicate balance between collecting the mostaccurate and detailed data, and limiting the overhead data collection
incurs on overall execution time. Since our goal is to identify large
regions in the application program suitable for method speculation,
we do not insert our profile annotations on small methods, methods
returning unpredictable values (e.g. float, long and double),and methods included in the java.* package. This reduced our
profile annotations to only methods that we expect could possibly
benefit from speculation. Data collected from annotations placedon these methods are shown in Table 1. Simulations comparing
execution times indicate only minimal impact (< 1%) on the overall
execution time from these profiling annotations. While we expectthat in the future, profile data would be used in algorithms todynamically identify speculative methods, data collected fromprofiling is only used as a heuristic in this study to statically identify
methods for speculation prior to execution.

An n o t a t i o n

Ac t i o n

Simulation Methodology

We use trace-driven simulations to evaluate the performanceof method speculation for Java programs. Annotated traces fromsequential execution of Java benchmarks running on a virtual
machine are fed into a simulator that models a speculative
multiprocessor. Although our trace-driven simulator does notmodel low-level details of the speculation hardware and memory
system, it provides accurate estimates of the performance of method
speculation.

3.1 Choosing a Virtual Machine
For a performance critical application like a virtual machine, anintrusive mechanism to generate traces would have skewed our
results. SimOS allows us to generate traces with no overhead
because it fully models the operating system and hardware units insoftware [15]. SimOS has complete support for the MIPS ISA and
IRIX operating system, so our choice of virtual machines was
narrowed to the two virtual machines available for this platform:
the freely available kaffe (ver. 0.9.2) [19], and the Sun JDK1.1.3 port
to IRIX. Both of these virtual machines support just-in-time (JIT)
compilation and Sun’s JDK1.1 APIs. We chose kaffe because we
could not obtain the full source code for Sun’s Java virtual machine(JVM), and this study and future work require modifications to thevirtual machine.
Only results for method speculation with the JIT compiler
enabled are presented for two reasons. We believe that speculationis only useful to further enhance speedups achieved by proventechniques like JIT compilation. Furthermore, our analysis has
shown that results from simulations based on interpretive execution
do not accurately reflect the performance of method speculation
with JIT compilation.

3.2 Speculative Hardware Model
Hardware support for speculation makes it possible for thechip multiprocessor to correctly resolve memory dependencies,
and to back-out of memory violations and restore the memory
system to a previous, known state. Our evaluation of method
speculation uses the underlying assumptions for a speculativeP u rp o s e

As s e m b l y
In s t r u c t io n s p e r
Me th o d

Me mo ry R e fe re n c e s
p e r Me th o d

2

no ne

L o a d p o i nte r to p ro fi le d a ta
b uffe r
C o unt c a ll fre q ue nc y o f g i ve n
Id e nti fy fre q ue ntly e xe c ute d m e tho d s
m e tho d
C o unt num b e r o f ne s te d m e tho d s Id e nti fy m e tho d s wi th e la p s e d e xe c uti o n ti m e s
c a lle d fro m g i ve n m e tho ds ui ta b le fo r s p e c ula ti o n

3

1 lo a d , 1 s to r e

6 + 1 * m e tho dc a lls

2 lo a d s , 2 s to r e s

L o o p c o unte r

C o unte r num e rb e r o f b a c k wa rdb ra nc he s ta k e n i n g i ve n m e tho d

4 + 1 * m e tho dc a lls

1 lo a d , 1 s to r e

P re d i c ti o n a c c ura rc y
c o unte r

C o unt num b e r o f m i s p re d i c te dre turn va lue s

2 ( c o r r e c t)
6 ( m i s p r e d i c t)

2 lo a d s ( c o r r e c t)
2 lo a d s , 2 s to r e s( m i s p r e d i c t)

F i x e d o v e rh e a d
D yna m i c a c c e s s
c o unte r
Ne s te d m e tho dc o unte r

Id e nti fy m e tho d s wi th e la p s e d e xe c uti o n ti m e ss ui ta b le fo r s p e c ula ti o n o r m e tho d s tha t c a n
b e m o d i fi e d to run und e r s p e c ula ti o n
Id e nti fy m e tho d s tha t wi ll no t fre q ue ntly c a us e
re turn va lue m i s p re d i c ti o n vi o la ti o ns und e r
s p e c ula ti o nTable 1 - Profile annotations used to identify suitable methods for speculation.

S ta rt s p e c ula ti ve m e tho d
E nd s p e c ula ti ve m e tho d
RAW vi o la ti o n

Op e r a t io n s

Ov e r h e a d in
C y c le s

C re a te a nd s a ve c he c k p o i nt o f re g i s te r fi le to m e m o ry, fo rk a fre e p ro c e s s o r
tha t e xe c ute s s p e c ula ti ve ly, lo a d c he c k p o i nt i nto ne w p ro c e s s o r.
C o m m i t s p e c ula ti ve d a ta , c he c k a c tua l re turn va lue a g a i ns t g ue s s a nd re s ta rt
i f ne c e s s a ry.
D i s c a rd s p e c ula ti ve d a ta , re lo a d c he c k p o i nt, re s ta rt s p e c ula ti ve ta s k

~5 0
~5 0
~5 0

Table 2 - Speculation overheads per speculative method.
generated code that cannot represent true dependencies between
chip multiprocessor [4] to define the high-level behavior of
speculative tasks.
speculative methods:
This sparse trace is generated by modifying the JIT compiled• The system has four single-issue, in-order MIPS R4000 procescode generated by kaffe. Illegal instructions, used as markers, aresors, permitting up to three speculative tasks to execute in paradded to the generated code immediately after loads and stores
allel with the main thread. Future designs of the chip multiproassociated with field accesses during JIT compilation. During
cessor could potentially use out-of-order processors with higher
execution under SimOS, these marker instructions are trapped withinissue width, so that the system could exploit both ILP and MLP.
SimOS. The trapped instructions call a routine to log to our execu• New speculative tasks are created only from the most speculation trace file the addresses of the memory locations accessed bytive task, or from the in-order thread, if no speculative task
the real loads and stores. Because SimOS is a full software simulaexists. Although not discussed here, our hardware can actuallytion environment, we can force these marker instructions to disapsupport other models of speculation [4].
pear from simulated execution. Thus, the only side effect from our• Memory store buffers can hold up to 1kByte (256 words) ofannotation methodology is mild code expansion of the JIT comwrites to memory for each speculative task.
piled code during simulated execution.
• A RAW memory violation forces a restart of the speculative
The start and end of speculative methods are marked in atask on which the violation occurred and termination of specusimilar fashion. Speculative methods are chosen statically prior tolative tasks that occur sequentially after this task. This involves
execution using statistics collected from the basic profiling system
flushing all the corresponding memory store buffers and restordescribed in Section 2.3 and another program that takes dynamic
ing the initial register state and PC of the speculative task thatmethod calls from the execution trace to generate a readable method
caused the violation.
call graph with call frequencies and associated execution times.
• The unit of coherency that RAW violations in memory are
Speculative methods are identified to the virtual machine by dedetected is one word (4 bytes). Consequentially, byte accesses
noting one of the unused method attribute flags as the methodin the same word could potentially cause false violations.
speculation flag. These attribute flags are normally used to iden• A simple return value prediction scheme is implemented thattify certain characteristics of the method (e.g. private, static,
predicts using the last value returned for a given method [11].
synchronized). Classfile binaries are modified prior to simula• Speculation overheads are incurred for starting new speculation with the method speculation flag raised on methods that havetive tasks and for restarting tasks due to RAW violations or
been chosen to be speculative. When our modified JVM encounreturn value mispredictions [4]. These overheads are describedters the speculation flag raised during JIT compilation of a given
in detail in Table 2.
method, the JIT compiler inserts assembly code to mark the begin3.3 Trace-Driven Simulationning and end of the speculative region. This code is used togenerate appropriate entries in the execution trace and to deterTo simulate method speculation, we use kaffe running undermine if the return value is correctly predicted. In a real system, theSimOS to generate an execution trace containing data relevant to
JIT compiler would insert assembly code at these points to invoke
method speculation. Embra, the fastest but least detailed SimOS
method speculation on the actual hardware.
CPU model, was used to minimize simulation time. The execution
Our initial simulation results were difficult to interpret because
trace is fed into a simulator that reconstructs execution under method
we could not associate violation addresses that our simulator genspeculation, with appropriate detection of RAW violations anderated with actual variables in the program. This led us to develop
return value mispredictions. To generate this trace, we utilize thean extensive non-intrusive symbol facility under SimOS to aid inannotation capabilities of SimOS and modified the native code
performance debugging. This is more challenging than looking for
generated by the JIT compiler.
symbols in a standard program binary. Java symbols for method
As described in Section 2.2, our execution model simplifies
calls and static fields from a classfile have to be resolved dynamidata dependency analysis to heap object and array accesses becally to the corresponding addresses generated for these structween speculative methods. The execution trace only records thesetures at runtime. Addresses for new objects and arrays createdheap accesses, which can be easily distinguished from Java stackfrom program execution also have to be resolved to the correand local access. This eliminates the need to examine loads andsponding text symbol. SimOS annotations [6] set on stub funcstores to non-heap allocated memory (e.g. execution stack actions in kaffe are used to collect symbol and address information
cesses, constant loads, and method lookups) in the dynamicallyduring execution into a symbold file so that these dynamicallyallocated objects can be identified. To simplify symbol resolution,
we also disable garbage collection so that objects are not relocatedduring runtime.
Virtual machine support functions are eliminated from theexecution traces that we analyzed so that we can focus on the
behavior of the JIT compiled application code under speculation.
In addition to disabling the garbage collector, methods are loaded
and compiled into the virtual machine in advance to avoid pauses
during program execution. Overheads from small functions to
implement new object allocations, lock operations and symbol
lookups are also removed from the traces.
The execution trace files are analyzed offline using our method
speculation simulator. The simulator reconstructs execution undermethod speculation from the sequential execution trace with marked
speculative regions and object accesses. This trace-driven simulator correctly handles RAW violations and return value
mispredictions. It also incorporates assumptions about the behavior of the underlying hardware described in Section 3.2. A
symbol resolver works in conjunction with the simulator, taking
information from the symbol file to associate dynamically allocatedobjects with the appropriate text symbol. Using this system,
textual information can be produced to associate a violation address with a specific object, and with the method and call nestingfrom which the reference was made.

4

Benchmarks

Benchmark selection was largely limited by the availability ofrepresentative Java applications. In general, Java applications that
represent traditional benchmark-style programs with computeintensive kernels and critical sections of code were difficult tolocate. To date, Java has been most successful as a high-level
development language used to implement user-interfaces.
Unfortunately, user-interactive programs are not amenable tocompute intensive benchmarking. We also included some small
kernels in our benchmarks, but we avoided toy benchmarks like
CaffeineMarks that do not reflect the structure or behavior ofreal Java programs.
The results in this paper are based on the benchmarks listed
in Table 3. StringBuffer and Hashtable are frequently
encountered core Java libraries that can be sped up using method
speculation. IDEA and NeuralNet are two benchmarks takenfrom the jBYTEmark suite [1], and LinpackApp is a popular floatingpoint kernel. The remaining programs represent popular, full scale
applications.

5

Performance Results

The results of our simulations of method speculation on achip multiprocessor with four single-issue processors are shownin Table 4. Speedups are measured relative to one single-issue
MIPS R4000 processor executing the benchmark. We show results with and without the speculation overheads (see Table 2)

included in the analyzed traces. Average utilization is also computed, providing a measure of the occupancy on the available
processors. As we would expect, applications that frequently
abort large speculative regions due to memory RAW violations or
return value mispredictsion will have significantly higher processor utilization relative to the actual speedup achieved.
These results represent the best performance that wasachieved by varying which methods to speculate on. The pool ofsuitable candidates for speculation were identified by our call graphtool discussed in Section 3.3 and basic profiling system describedin Section 2.3.

5.1 Performance Analysis
Speedups appear to be split between the two types of applications represented in our benchmarks. Method speculation iseffective for speeding up data-parallel applications like IDEA,
NeuralNet, RayTrace and LinpackApp that have significant
coarse-grained parallelism. With very few data dependencies between speculative tasks, almost no memory violations are seen
during execution of these programs.
RayTrace is the only benchmark of these four that has little
ILP. Since NeuralNet, IDEA, and LinpackApp have significant
ILP, it could be argued that similar speedups on these programs
could be achieved on a superscalar processor. What is important
to note is that method speculation can achieve these speedups
without true compiler support. Most JIT compilers found in Javavirtual machines only translate bytecodes into native code, sacrificing high-level optimizations that improve code quality in orderto keep compilation times short. Superscalar processors, unfortunately, must rely on time consuming instruction scheduling andoptimizations from a good compiler to fully exploit ILP. We believe
this distinction can allow the speculative chip multiprocessor tooutperform a superscalar machine on these types of data-parallel
applications when only a simple JIT compiler is used.
Control-flow based programs, unfortunately, only benefit
modestly from method speculation. Speedups on these programs
do not exceed 1.4 on our chip multiprocessor with four CPUs.
Compared to data-parallel applications, they have significantly
higher violation and restart rates (see Table 4), reflecting the control and data dependent nature of these programs. Low processor
utilization numbers also indicate that speedup is limited due in part
nameHashtable
IDEA
Jasmin
JavaCUP
javac
javap
LinpackApp
NeuralNet
OROMatcher
RayTrace
StringBuffer

binary # methods(bytes)(static)

17507
18637
64635
117471573120172505
5109
25867
61277
13319
5906

19
26
309
355
1492
259
15
33
202
53
36

# classes # methods(static)(dynamic)

description

43779 java.util.Hashtable
414051 encryption/decryption [1]63585648 Java assembler
40
540034 yacc-like compiler
174
236357 Java compiler
38295726 classfile disassembler
213190 Linpack FP kernel
497332 neural net simulation [1]2096735 Perl 5 regexp
6 1541478 raytrace of scene
24800 java.lang.StringBuffer*NOTE: These statistics do not include calls to core JDK methods or classes.

Table 3 – Benchmark programs.

speedup (nospeculation
overhead)average utilization(on 4 CPUS)

violations (% ofspeculative tasks)

restarts (% ofspeculative tasks)

violation (% ofspeculative cycles)

restart (% ofspeculative cycles)

average cycles /speculative task

average cycles /violation

1.59

1.69

2.54

50.1

0.0

55.0

0.0

2271

2490

average cycles /restartspeedup (withspeculation
overhead)(original)

benchmarkHashtable
Hashtable(modified)

2.30

2.47

2.72

3.2

0.0

14.2

0.0

2348

10239

IDEA

(original)

n/a

n/a

n/a

n/a

n/a

n/a

n/a

n/a

n/a

IDEA

(modified)

3.60

3.76

3.76

0.0

0.0

0.1

0.0

8164

52773

1.23

1.24

1.35

41.0

7.8

26.8

4.0

1663

1086

850

Jasminnotes

0 frequent violations on Hashtable.count0 moved loop-carried dependency
n/a speculative tasks were too large, resulting in store buffer overflow
0 transformed loop bodies into methods

javac

1.15

1.15

1.68

29.9

4.4

59.6

18.1

23147

46097

9 6 2 40

JavaCUP

1.23

1.23

1.57

16.1

12.4

33.1

25.8

2909

5958

6037

javap

1.29

1.29

1.84

38.9

3.5

62.8

2.5

5854

9456

4190

LinpackApp

2.04

2.09

2.21

4.7

1.9

2.8

6.7

5163

3071

18606 large sequential section reduces speedup from > 3 in the kernel

NeuralNet(original)

1.61

1.55

2.18

54.5

0.0

53.2

0.0

27726

27059

0 violations concentrated on certain variables

NeuralNet(modified)

2.82

3.10

3.11

0.2

0.0

0.7

0.0

2679

8361

0 transformed loop bodies into methods
70 violations concentrated on certain variables

OROMatcher

1.22

1.18

1.33

10.3

12.0

45.2

0.3

2427

10606

RayTrace(original)

1.01

1.01

1.95

99.9

0.0

98.8

0.0

20408

20169

RayTrace(modified)

2.77

2.80

2.80

0.0

0.0

0.0

0.0

15745

0

0 frequent violations on Point.x
0 eliminated false loop-carried dependency

StringBuffer(original)

1.47

1.63

2.43

65.2

0.0

56.2

0.0

1709

1471

0 frequent violations on StringBuffer.countStringBuffer(modified)

2.14

2.46

2.68

7.8

0.0

13.6

0.0

1375

2420

0 moved loop-carried dependency

Table 4 - Performance results.
to the few available opportunities to use method speculation. A
that we believe will be remedied as we continue to develop our
cursory examination confirms that these applications have proporsystem.
tionally fewer methods with void and predictable return values
5.2 Modifying Source Code to Improvethan data-parallel programs. This suggests that with more time to
Performance
understand and modify the source code so that processor utilization is increased, it may be possible to see better performance on
We were disappointed with our initial results on unmodified
control-flow based programs.
sourcecode. We found low processor utilization numbers for our
We discovered that the size of methods chosen for speculadata-parallel
benchmarks and frequent memory violations on contion plays an important role in performance and processor utilizatrol-flow
basedbenchmarks that had very regular loops. This led
tion. Small speculative tasks are less likely to cause memory violaus
to
look
more
closely at the program source code. With sometions, but only produce small speedups. Two factors seem toexperimentation,
we found that relatively simple modifications tocontribute to this phenomenon. Since small speculative regions
the
code
could
significantly
boost performance under method
are short-lived, there is less opportunity to overlap speculative
speculation.
tasks, resulting in low utilization of the processors. Secondly, small
For data-parallel applications, we discovered that the original
speculative regions suffer a larger relative penalty from the fixed
methods
often represented regions that were too large to specuspeculation overheads.
lateon.
Inspectionof the code revealed smaller data-parallel loops
In general, we found better results come from speculating onthatareclosertogranularitiesof parallelism suitable for our system.
larger speculative tasks. Large speculative regions execute longer,To
exposethisloop-level
parallelism
under method speculation,
so that there is a greater chance of having numerous speculative
weencapsulate
the
loop
body
that
we
want to represent a single
methods executing concurrently. Unfortunately, large regions have
task
as
a
nestedmethod
call,
as
shown
in Example 1. IDEA,
more memory references, increasing the amount of parallel, overNeuralNet
andLinpackAppshowsignificant
improvements bylapping loads and stores to the execution heap. Large speculative
speculating on these finer-grained parallel tasks.
regions also tend to move memory references further apart in time
Our simulator also identified variables that frequently caused
from their original positions in sequential execution. Consequently,
memory violations under speculation for certain control-flow-based
speculating on larger methods increases processor utilization, but
applications. For Hashtable and StringBuffer, these violaplaces a greater strain on the memory system and speculation
tions corresponded to variables that are written to late in a method,
hardware. As expected, we found that choosing excessively large
precluding significant overlap between successive iterations. As
speculative regions results in speculation buffer overflows andillustrated in Example 2, moving writes to the dependent variable
unacceptable rates of memory RAW violations.
to an earlier point and reads to this variable to a later point in the
Speedups never approach four, the number of processors inmethod can increase overlap. For Raytrace, we eliminated a false
our system, even for our data-parallel benchmarks. Our simple
inter-method dependency by moving a write from the loop bodyscheduling algorithm bypasses speculative methods and executes
into the body of the method, as shown in Example 3. By moving
them sequentially when no more free processors are available,
such dependencies between speculative methods in our benchresulting in idle gaps that limit speedup. This limitation is due to anmarks, violations are either eliminated, or occur earlier in execution,inefficiency in our current model for speculative methods in loops

6

private void do_mid_forward(int patt){for (int neurode = 0; neurode < MID_SIZE; neurode++){do_mid_forward_iteration(patt,neurode);}}
private void do_mid_forward_iteration(int patt, int neurode){
double sum = 0.0;
for (int i = 0; i < IN_SIZE; i++){sum += mid_wts[neurode][i] * in_pats[patt][i];}sum = 1.0 / (1.0 + Math.exp(-sum));
mid_out[neurode] = sum;}

Example 1 - Loop body of do_mid_forward() transformed
into a nested method call.
resulting in improved speedups.
In future studies, we hope to show that program sites that
may benefit from these types of optimizations can be identified
automatically, with minimal effort from the programmer.

5.3 Limitations of Our Study
Our choice to use the kaffe virtual machine dictated the absolute performance of our system. Our experiments have shown that
Sun’s JDK with JIT compiler support is about 20-30% faster thankaffe. For this study, though, we believe a reasonably implemented
JIT is sufficient for comparing the relative performance of a chip
multiprocessor with method speculation to a conventional singleissue processor.
The effects of virtual machine support functions were eliminated from the traces used to generate results. Including thesefunctions would make it more difficult to interpret the results since
they tend to reflect overheads specific to the kaffe Java virtual
machine implementation. In a real system, it is also hard to predict
how these support functions will affect performance, since they
could either be hidden by speculation or extend sections of sequential execution.
We will examine the effects of optimized JIT compiler codeand inclusion of virtual machine support functions on method
speculation as our system becomes more fully developed.

specTask nload rx,[m]specTask n
specTask n+1
specTask n+1

store v,[m]load rx,[m]specTask n+2

load rx,[m]store v,[m]load rx,[m]timestore v,[m]load rx,[m]specTask n+2

load rx,[m]store v,[m]timestore v,[m]store v,[m]original codetransformed code

Example 2 - Moving a loop carried dependency to improvemethod speculation performance.

Conclusions

This study describes how the Java virtual machine can be aneffective environment for exploiting method-level speculation. In
our model, method invocations are used as a convenient abstractionof the tasks that we would like to speculate on. Not only does thisframework simplify data dependency analysis, but it also results ina clean execution model. In conjunction with a JIT compiler, thissystem can invoke method speculation with virtually no modification
to the source bytecode program.
We show that speculation based on method invocations canachieve significant speedups on data-parallel applications withminimal programmer and compiler effort. For control-flow limited
applications, we show that method speculation can produce modest
speedups. For both application classes, we find that analysis ofruntime behavior helps to eliminate and minimize dependencies
that limit speedup gains. Our preliminary experiences suggest that
more study is required to understand how non-data-parallel
applications behave under method speculation so that performanceon these type of applications can be improved.
Although superscalar processors may perform as well as our
system on data-parallel applications that have significant
instruction level parallelism (ILP), instruction scheduling from smart
compilers are usually required to fully exploit ILP on superscalar
processors. Since JIT compilers generally sacrifice these highlevel optimizations for faster compilation, we believe that a
speculative chip multiprocessor can outperform a superscalar
processor in this configuration. It should also be noted thatspeedups from method-level parallelism (MLP) are largely
orthogonal to those resulting from ILP, so that an implementationof a speculative chip multiprocessor using superscalar processors
could take advantage of both types of parallelism.

7

Future Work

Continued research on method speculation of Java programs
will progress along two related fronts: improving the performanceof method speculation on Java programs, and implementation of avirtual machine targeted for a chip multiprocessor architecture thatcan dynamically manage method speculation.
Improving the performance of method speculation on Javaapplications without obvious data parallelism appears to be themost interesting and challenging area of further study. We expectthat additional performance improvements on these programs will
result from combining incremental speedups from several
techniques that we are currently exploring. These techniques
include using algorithms to reliably identify methods that benefit
from speculation, applying general code transformations, such as
those described in Section 5.2, that improve speculation
performance, and expanding the applicability of speculation to alarger set of method call sites.
We have also started development on a Java virtual machine
designed specifically for a chip multiprocessor architecture. An

public class RayTrace {Point cor;void Trace(Point point1, Point point2, int i, byte[] ab, int k) {. . .
cor.x = xValue;
cor.y = yValue;cor.z = zValue;ab[k++] = (byte)(cor.x * 255);
ab[k++] = (byte)(cor.y * 255);
ab[k++] = (byte)(cor.z * 255);}

public void run() {byte ab[] = new byte[601];
int k = 0;
for (int j = 0; j < 200; j++){for (int i1 = 0; i1 < 200; i1++){
Trace(point2, point1, 0);ab[k++] = (byte)(cor.x * 255);
ab[k++] = (byte)(cor.y * 255);
ab[k++] = (byte)(cor.z * 255);
d2 += d1;}
k = 0;}}}

public void run() {byte ab[] = new byte[601];
int k = 0;
for (int j = 0; j < 200; j++){for (int i1 = 0; i1 < 200; i1++){
Trace(point2, point1, 0, ab, k);d2 += d1;}
k = 0;}}

specTask n+1

store v,[m]load rx,[m]timevoid Trace(Point point1, Point point2, int i) {. . .
cor.x = xValue;
cor.y = yValue;cor.z = zValue;}

specTask nload rx,[m]specTask n+2

store v,[m]load rx,[m]store v,[m]original code
specTask n
specTask n
specTask nstore v,[m]timepublic class RayTrace {Point cor;load rx,[m]store v,[m]load rx,[m]store v,[m]load rx,[m]}transformed codetransformed codeoriginal code

Example 3 - Eliminating a false loop carried dependency (to ab[], an array of bytes).
integrated low overhead profiling and feedback system with a new
JIT compiler will dynamically manage method speculation. The
new compiler will addresses performance limitations of our current
JIT [7] [17], and will allow us to study the effectiveness of speculation
on optimized JIT code. This virtual machine will also look beyond
explicit Java threads to parallelism within the virtual machine. By
enabling concurrent execution of explicitly coarse-grain virtual
machine tasks like the JIT compiler, class loader, garbage collector
and bytecode verifier, this virutal machine, together with the chip
multiprocessor, will be able achieve speedups even on single
threaded applications.

Acknowledgments
The authors wish to thank Basem Nayfeh for discussions
that led to many of the ideas that appear in this paper. This work
was supported by DARPA contract DABT63-95-C-0089.

References[1] Byte Magazine. jBYTEmarks v0.9. Available at http://
www.byte.com/, 1995.
[2] Brad Calder, Dirk Grunwald, and Benjamin Zorn. “Quantifying Behavioral Differences Between C and C++ Programs.”
Technical Report, University of Colorado, Boulder, Jan 1994.
[3] M. Franklin and G.S. Sohi. “The Expandable Split Window
Paradigm for Exploiting Fine-Grain Parallelism.” In Proceedings of 19th Annual ISCA, pages 56-67, Gold Coast, Australia,
May 1992.
[4] Lance Hammond and Kunle Olukotun. “Data Speculation
Support for a Chip Multiprocessor.” To appear in Proceedings of ASPLOS-VIII.
[5] J. L. Hennessy and D. A. Patterson. Computer Architecture,
A Quantitative Approach 2nd Edition. Morgan Kaufmann
Publishers, Inc., San Francisco, California, 1996.
[6] Stephen A. Herrod, Mendel Rosenblum, Edouard Bugnion,
Scott Devine, Robert Bosch, John Chapin, Jinshuk Govil,
Dan Teodosiu, Emmett Witchel, and Ben Verghese. The
SimOS Simulation Environment. Available at http://simos.stanford.edu/, Feb 10 1996.
[7] Urs Hölzle, Lars Bak, Steffen Grarup, Robert Griesemer, andSrdjan Mitrovic. “Java On Steroids: Sun’s High-PerformanceJava Implementation.” In Hot Chips IX, Stanford California,
August 25-26 1997.
[8] Tom Knight, “An Architecture for Mostly Functional
Languages,” Proceedings of the ACM Lisp and Functional
Programming Conference, pages 500-519, August 1996.
[9] M. S. Lam and R. P.Wilson. “Limits of Control Flow on
Parallelism.” In Proceedings of 19th Annual ISCA, pages 4657, Gold Coast, Australia, May 1992.
[10] Tim Lindholm and Frank Yellin. The Java Virtual Machine
Specification. Addison-Wesley, Reading, Massachusetts,
1997.
[11] M. H. Lipasti, C. B. Wilkerson, and J. P. Shen. “Value
locality and load value prediction.” In Proceedings of
ASPLOS-VII, pages 138-147, Cambridge MA, October, 1996.
[12] Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken
Wilson and Kun-Yung Chang. “The Case for a Single-Chip
Multiprocessor.” In Proceedings of ASPLOS-VII, October
1996.
[13] Jeffrey Oplinger, David Heine, Monica S. Lam and Kunle
Olukotun. “In Search of Speculative Thread-Level Parallelism.” Computer Systems Laboratory Technical Report CSLTR-98-765, Stanford University, July 1998.
[14] Jeffrey Oplinger, David Heine, Shih-Wei Liao, Basem A.
Nayfeh, Monica S. Lam and Kunle Olukotun. “Software andHardware for Exploiting Speculative Parallelism in Multiprocessors.” Computer Systems Laboratory Technical Report
CSL-TR-97-715, Stanford University, February 1997.
[15] Mendel Rosenblum, Stephen A. Herrod, Emmett Witchel,and Anoop Gupta. Complete Computer Simulation: The
SimOS Approach. In IEEE Parallel and Distributed
Technology, Fall 1995.
[16] G. Sohi, S. Breach, and T. Vijaykumar. “Multiscalar
Processors.” In Proceedings of 22nd Annual ISCA, pages 414425, Ligure, Italy, June 1995.
[17] David Ungar and Randall B. Smith. “Self: The Power of
Simplicity.” In Proceedings of OOPSLA ’87, ACM SIGPLAN
Notices, pages 227-242, December 1987.
[18] D.W. Wall. “Limits of Instruction-Level Parallelism.” Digital
Western Research Laboratory, WRL Research Report 93/6,
November 1993.
[19] Tim Wilkinson. The kaffe Virtual Machine v0.9.2. Available
at http://www.kaffe.org/ or http://www.transvirtual.com/,
1997.