The Jrpm System for Dynamically Parallelizing Java Programs
Michael K. Chen
Stanford University
mikey@hydra.stanford.edu

Kunle Olukotun
Stanford University
kunle@ogun.stanford.edu

Abstract

analysis can parallelize Fortran-like numericalapplicationson
traditional
multiprocessors[2][5][20][38].
Unfortunately, numerous challenges
have made automatic compiler parallelization of general
integer programs difficult. Analyzing pointer aliasing,
control flow, irregular array accesses, and dynamic loop
limits as well as handling inter-procedural analysis
complicate static dependence analysis [3].
Thesedifficulties introduce imprecision into dependence
relations, limit the accuracy of parallelism estimates, andforce conservative synchronization to safely handle
potential dependencies.
Our paper describes the Java runtime parallelizing
machine (Jrpm), a complete system that automaticallyparallelizes sequential programs using thread-level
parallelism. This system takes advantage of recent
developments that now enable a different approach toautomatic parallelization for small multiprocessors (2 – 8CPUs). The key components of this system are: a chip
multiprocessor that provides low-latency inter-processor
communication, thread speculation support that allows us
to parallelize optimistically, a hardware profiler for
identifying parallel loops from program execution, and avirtualmachineenvironment
where
dynamic
optimizations can be performed without modifying
source binaries.
• Chip multiprocessor – Jrpm is based on the
Hydra chip multiprocessor (CMP) [32]. Decreasing
feature size and increasing transistor counts now allow
chip multiprocessors to be a reality [6][14][24][42].
Chip multiprocessors combine several CPUs onto one
die with a tightly coupled memory interface. In thisconfiguration,inter-processor
sharing
andcommunication costs are significantly less than in
traditional multiprocessors. The reduced communication
costs make it possible to take advantage of fine-grained
thread-level parallelism.
• Thread-level speculation – Hydra includes
supportforthread-level
speculation(TLS)[10][21][29][40]. TLS allows a sequential program to be
divided into arbitrary chunks of code, or threads, to be
executed in parallel. TLS hardware ensures memory
accesses between threads maintain the original sequential
program order.
Traditional multiprocessors must synchronize
conservatively to preserve correctness when static
analysis cannot determine with complete certainty that adependency does not exist. For non floating-point
applications, this makes it difficult to find regions thatcan be parallelized safely and still achieve good
speedups. With TLS, it is possible to parallelize

We describe the Java runtime parallelizing machine(Jrpm), a complete system for parallelizing sequential
programs automatically. Jrpm is based on a chip
multiprocessor (CMP) with thread-level speculation(TLS) support.
CMPs have low sharing andcommunication
costs
relativetotraditional
multiprocessors, and thread-level speculation (TLS)
simplifies program parallelization by allowing us toparallelize optimistically without violating correct
sequential program behavior. Using a Java virtual
machine with dynamic compilation support coupled witha hardware profiler, speculative buffer requirements andinter-thread dependencies of prospective speculative
thread loops (STLs) are analyzed in real-time to identify
the best loops to parallelize. Once sufficient data has
been collected to make a reasonable decision, selected
loops are dynamically recompiled to run in parallel.
Experimental results demonstrate that Jrpm can
exploit thread-level parallelism with minimal effort fromthe programmer. On four processors, we achieved
speedups of 3 to 4 for floating point applications, 2 to 3
on multimedia applications, and between 1.5 and 2.5 on
integer applications. Performance was achieved byautomatic selection of thread decompositions by the
hardware profiler, intra-procedural optimizations oncode compiled dynamically into speculative threads, andsome minor programmer transformations for exposing
parallelism that cannot be performed automatically.

1. Introduction and Overview
As the limits of instruction-level parallelism (1 – 10sof instructions) with a single thread of control areapproached [44], we must look elsewhere forarchitectural improvements that can speedup sequential
program execution. Coarser grained parallelism, likefine-grained thread-level parallelism (10 – 1,000s of
instructions), is a potential area for exploration. This
type of parallelism is not exploited today due tolimitations of current multiprocessor architectures andparallelizing compilers.
Traditional symmetric multiprocessors (SMPs)[13][22] have been most effective at exploiting coarse
grained parallelism (>1,000s of instructions). The highcost of inter-processor communication in these systems,
generally >100s of cycles, eliminates any potential
speedups for fine-grained parallel tasks that either havetrue dependencies or closely shared cache lines.
Modern compilers that perform array dependence© 2003 IEEE. Published in the Proceedings of ISCA-30, 9-11 June 2003 in San Diego, CA, USA. 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.

aggressively rather than conservatively. Since sequential
ordering is guaranteed for parallel execution of any
program decomposition under TLS, the problem ofcompilation is reduced to finding regions of program
execution with significant parallelism.
• Hardware profiler – Static parallelizing compilers
often have insufficient information to analyze dynamic
dependencies effectively. Dynamic analysis to findparallelism complements a TLS processor’s ability toparallelize optimistically and use hardware to guarantee
correctness. Tracer for Extracting Speculative Threads(TEST) [9] is hardware support in Jrpm that analyzes
sequential program execution in real-time to find the best
regions to parallelize. This system provides accurate
estimates of dynamic dependency behavior, thread size,and buffering requirements that are needed for selecting
good decompositions and that would be difficult toderive statically. Estimates show the tracer requires
minimal hardware additions to our CMP and causes only
minor slowdowns to programs during analysis.
• Virtual machine – The Java virtual machine(JVM) [28] acts as an abstraction layer to hide dynamic
analysis and thread-level speculation from the program.
Virtual machines like the JVM and Microsoft’s .NET
VM have become commercially popular recently forsupporting platform independent applications. Binaries
are distributed as portable, platform independent
bytecodes [28] that are dynamically compiled into native
instructions of the underlying architecture and run within
the protected environment of the VM. This virtualization
allows us to seamlessly support a new execution model
without modifying the source binaries.
Java bytecode

Application

1

Native code+
Annotation
instructions

Java VM

Hydra CMP

CFG / DFG

Profile analyzer

2

Native TLS
code

JIT Compiler

TEST profiler

3

4
5

TLS support

1

Identify possible thread decompositions by analyzing
bytecodes and compile natively with annotation
instructions.

2

Run annotated program sequentially, collecting TEST
profile statistics on potential thread decompositions.

3

Post-process profile statististics and choose thread
decompositions that provide the best speedups.

4

Recompile code with TLS instructions for selected
thread decompositions.

5

Run native TLS code.

Figure 1 – Block diagram of Jrpm.

These basic components are used to create a systemthat can automatically compile programs to exploit
thread-level parallelism. A block diagram of Jrpm
outlining how the various software and hardware
components work together is shown in Figure 1. The
compiler derives a control-flow graph from program
bytecodes and analyzes it to identify potential thread
decompositions. A program that has been dynamicallycompiled with instructions annotating local variables andthread decompositions is executed as a sequential
program on a single Hydra processor. The trace
hardware collects statistics in real-time for theprospective decompositions. Once sufficient data has
been collected by the trace hardware, regions predicted
to have the largest speedup and most coverage are
dynamically recompiled into speculative threads.
This dynamic parallelization system has otherpotential benefits:• Reduced programmer effort – Explicit coding ofparallelism is better suited for coarser grained anddistinct tasks. Manually identifying fine-grained parallel
decompositions can be a time-consuming effort for
programs without obvious critical sections.
• Portability – The code maintains platform
independence because the binaries are not modified
explicitly for thread speculation.
• Retargetability – Decompositions can be tailoreddynamically for specific hardware or data. Different
decompositions may be chosen for future CMPs withmore CPUs, larger speculative buffers, and different
cache configurations.
In some applications,decompositions can also be optimized for specific data
set sizes.
• Simplified analysis – Compared to traditional
parallelizing compilers, the Jrpm system relies on more
hardware for TLS and profiling support, but reduces thecomplexity of the analysis required to extract exposed
thread-level parallelism.
Simulations demonstrate Jrpm’s ability to exploit
thread-level parallelism automatically with minimal
effort from the programmer. On our CMP with fourCPUs, we achieve speedups of 3 to 4 on floating point
applications, 2 to 3 on multimedia applications, andbetween 1.5 and 2.5 on integer applications. Selection of
appropriate thread decompositions by the hardware
profiler, low-level optimizations on code dynamicallycompiled into speculative threads, and some manualprogrammer transforms for exposing parallelism when it
cannot be found automatically are all key to getting good
performance.
The remainder of this paper details the major
components of Jrpm and provides results fromsimulation. Section 2 introduces the Hydra CMP with
speculation support. Section 3 describes the hardware
profiling system used to select good speculative
decompositions. Section 4 shows compiler optimizations
performed on selected speculative thread loops. Section
5 explains performance and correctness issues forrunning thread speculation within a JVM. Section 6presents the results of running real programs on Jrpm.
Section 7 compares related work and Section 8summarizes our findings.

2. CMP with TLS Support
Hydra [32], shown in Figure 2, is a chip
multiprocessor consisting of 4 single-issue, pipelined
MIPS processors, each with private L1 data andinstruction caches. High-speed read and write buses
enable low-latency inter-processor communication that

safely committed to the secondary
cache or discarded [21]. The physical
CPU0
CP2
CPU1
CP2
CPU2
CP2
CPU3
CP2
limits of buffered speculative state in
Hydra are given in Figure 2.
L1 ICache
L1 DCache +L1 ICache
L1 DCache +L1 ICache
L1 DCache +L1 ICache
L1 DCache +(16kB)
Spec tags (16kB)(16kB)
Spec tags (16kB)(16kB)
Spec tags (16kB)(16kB)
Spec tags (16kB)
TLS is controlled in an
Memory controller
Memory controller
Memory controller
Memory controller
application
through
specialinstructions
that
accesstheWrite-through bus (64b)coprocessor and through special storesissued onto the write bus. For a loop
Read/replace bus (256b)transformed into speculative threads,
SDRAM
I/O bus
there are overheads for starting andComparator banks
#0
#1
#2
#3
#4
interfaceinterfaceshutting down speculation, at the end
TESTStore buffersof every iteration, and on dynamic
On-chip L2 cache (2MB)
DRAM Main
I/O Devices
MemoryRAW violations, as shown in Table 1.
Access
Latency (cycles)
This table shows improvements in the
L25
Buffers
Per-thread limit
Associativity
software handlers (New) compared to
Load buffer
16kB (512 lines x 32B) 4-way
Interprocessor 10
Store buffer
2kB (64 lines x 32B)
Fully
Main memory
50
overheads reported previously for our
runtime system (Old). The significant
Figure 2 – Block diagram of our CMP. TLS support blocks shown in dotted lines.
reduction in overheads results fromTEST profile hardware blocks shown in dark blocks.
improved coding of the speculative
makes it possible to take advantage of thread-level
control routines and more efficient speculation control
parallelism even when there is substantial inter-processor
instructions.
sharing.
An integrated on-chip shared L2 cacheminimizes cache misses to lower memory when the
3. Selecting Thread Decompositions
processors work on shared data.
Table 1 – Thread-level speculation overheads.
A speculative thread loop (STL) is a loop
Overheaddecomposed
into threads, where each loop iteration is(cycles)
one thread.
Because hardware guarantees correct
TLS Operation
Work performed
parallelexecutionof speculative threads, compiling for
STL_STARTUP
41
23
Clear store buffers
this execution model involves finding regions in(Master CPU
Set speculative event handlers
programs where thread-level parallelism can be exploited
only)Store $fp & $gp
within our hardware constraints:
Wake up slave CPUs
Enable TLS• Inter-thread data dependencies, or RAW hazards,
limit parallel execution of speculative threads.
STL_SHUTDOWN
46
16
Wait to become head CPU(Master CPU
Disable TLS• Speculative read and write state buffered by the
only)
Kill slave CPUs
hardware can overflow and force speculative
STL_EOI
14
5
Wait to become head CPU
execution to stall until reads or writes can be
End-of-iteration
Commit store buffer
performed safely (e.g. when the thread becomes the
Clear cache speculation tag bits
non-speculative “head” thread).
Start new thread• Code compiled as speculative threads introduces
STL_RESTART
13
6
Clear store buffers
Violation andoverheads from speculation handlers andClear cache speculation tag bits
restartcommunication of inter-thread (loop-carried)
Restore $fp & $gp
dependent local variables.
Thread-level speculation (TLS) allows a sequential• Only one STL (e.g. one loop level in a loop nest)
program to be divided into threads to be executed in
may be active at a given time.
parallel. Data speculation hardware ensures memory
These constraints impose conflicting objectives
ordering of the original sequential program is maintained
when selecting STLs. Speculating on small loops limits
by the threads. Read-after-write (RAW) dependencies
coverage, precludes speculation on outer loops, andare guaranteed by forwarding data to sequentially later
suffers from proportionally higher speculative thread
threads, and forcing restarts of threads when aoverheads. Speculating on large loops can increase
speculative thread reads a value too early and sequential
speculation buffer overflows and incur high penalties formemory ordering is violated.
By buffering andlate RAW violations.
committing speculative writes in threads according to the
As discussed earlier, detecting parallelism withoriginal program order, write-after-write (WAW)
static compilers in large, general programs is challenging
ordering is maintained. Finally, buffered writes are only[3]. Jrpm relies on dynamic analysis to find parallelism,
available to sequentially later threads, preventing writewhich complements a TLS processor’s ability toafter-read (WAR) violations.
parallelize optimistically and use hardware to guarantee
Speculative thread support in Hydra consists ofcorrectness. The Tracer for Extracting Speculative
coprocessors for each CPU that control thread
Threads (TEST) [9] profiles sequential program
speculation, extra speculative tag bits added to the
execution and collects dependency timing, thread length,
processor L1 data caches to detect inter-thread dataand speculative buffer usage estimates to find the best
dependency violations, and a set of secondary cacheloops to transform into STLs. TEST support requires
store buffers to hold speculative data until it can either be
New

Old

Central bus arbitrator

little hardware support and incurs only minimal
slowdown to programs during analysis. Section 3.1 is an
overview of the analysis used to select STLs and Section
3.2 briefly shows how the analysis is implemented in
hardware and software.

3.1 Selecting Good Decompositions
TEST analysis is applied to any loop which does nothave any obvious serializing dependency.
TEST
analysis relies on comparing event timestamps fromdifferent events during sequential execution to derive
statistics for a potential STL.
Two primary analysis are performed by TEST to
characterize the effects of real constrains on a potential
STL. The load dependency analysis looks for interthread dependencies that limit parallelism. Timestamps
recorded on previous memory or local variable stores are
retrieved during a load to the same address and comparedto thread start timestamps to determine if an inter-threaddependency arc exists. The dependency with thesmallest arc distance arc is also recorded as the criticalarc that limits parallelism between the threads.
The speculative state overflow analysis ensures that
speculative state for a STL can fit within the L1 caches
and store buffers, preventing potential TLS stalls due to
speculative state overflows. In this analysis, a cache line
timestamp and cache line tag is recorded for the cacheline a heap load or store would have hit. Subsequent
memory accesses check for a previously recorded cacheline timestamp with a matching cache line tag. If notimestamp exists or if it is less than the current thread
start timestamp of a STL, a counter, either the loadcounter for speculatively read cache lines or store
counter for store buffer entries, is incremented to reflect
new buffer state required by the current thread. The
overflow counter is incremented if either counter for thecurrent thread exceeds hardware buffer limits.
The results of the load dependency analysis and thebuffer overflow analysis are accumulated over time andused to predict the performance of a potential STL. Twoheuristics signal that sufficient data has been collected
for a potential STL: at least 1000 iterations have been
executed or outer potential STLs are predicted toconsistently overflow speculative state.
Once enough profiling data has been collected, theestimated speedup for a STL is computed using averagedependency arc frequencies, thread sizes, critical arc
lengths, overflow frequencies and speculative overheads.
Only loops that have average iterations per entry >> 1,
speculative buffer overflow frequency << 1, andpredicted speedups > 1.2 are recompiled into speculative
threads. In a loop nest, where we are limited to
speculating at one loop level at a time, we select the best
STL from those possible by comparing the estimatedexecution times of speculating at different levels in theloop nest.

3.2 Hardware Profiling Support
Without hardware support, our simulations indicate
execution slows over 100x when applying this analysis

with software alone. This magnitude of slowdown is
unacceptable in a real dynamic compilation system, andthe sizeable software overheads introduce significant
imprecision into the collected statistics.
Table 2. Annotating instructions and associated operations.
Instruction

lw|lb|lbu|lh
lhu|lwc1 addr
sw|sb|sh|swc1 addr
lwl vnswl vnsloop neoi
eloop nNormaloperation

Annotation (when enabled)

Load

Load

Store

Store

none
“
“
“
“

Local variable load
Local variable store
Start loop
Loop end of iteration
End loop

int lcl_v = 10;
while( lcl_v > 0 ){if( call() != 0 ){lcl_v--;}
else{
this.val++;}}Original loop
1Mark start of speculative region
and allocate 1 local variable
timestamp slot for lcl_v.

2

Local variable annotations markaccesses to lcl_v.

3lw and sw automaticallycommunicated to profiler.

4Mark end of speculative region
and free local variable
timestamp. Read collected
statistics from profiler.

li
sloop
LOOP_TOP:
lwl
blez
jal
bnez
lwl
2
addi
swl
b
IF_FAIL:
lw
3
addi
sw
LOOP_EOI:eoib
LOOP_EXIT:
4
eloop
jal
1

$s1, 1011$s1, LOOP_EXIT
call$v0, IF_FAIL
1$s1, $s1, -1
1
LOOP_EOI$t0, 8($s0)$t0, $t0, 1$t0, 8($s0)

LOOP_TOP
1
READ_STATISTICS

Instrumented machine code

Figure 3 – Example of an annotated loop.

TEST hardware works when speculation is disabled
and requires only minor hardware additions to our CMP
design. The additions are new annotation instructions to
be inserted by the dynamic compiler and hardware
comparator banks that perform the trace analysis. The
speculative store buffers, which are idle during nonspeculative execution, hold timestamps for the profiler.
Estimates indicate the hardware support adds less than
1% to the total transistor count of Hydra.
Annotating instructions, listed in Table 2, areautomatically inserted by the JIT compiler.
The
compiler derives a control-flow graph (CFG) from Java
bytecodes. All natural loops [31] identified from the
CFG are marked as prospective STLs and denoted withspecial annotations, as illustrated in Figure 3. Aftercompiler optimizations to eliminate unnecessary
annotations, benchmarks experience an average 7.8%
slowdown during profiling, and only 2 applications haveslowdowns approaching 25%, as shown later in Figure 8.
Higher profiling overheads are seen in some programs
due to the cost of annotations on potential STLs withsmall loop bodies.
Store buffers that normally hold writes during
speculative execution hold timestamps during TEST
profiling. The store buffers are statically partitioned sothat three buffers hold heap access store timestamps, one
holds cache line timestamps, and one holds store

timestamps to local variables. An address’ timestamp isreturned when requested by a memory access or local
variable annotation.
The comparator banks carry out the bulk of the realtime dependency and overflow analyses. Memory loadand store instructions and the special annotating
instructions are automatically communicated through thememory system to the banks during profiling. One
comparator bank tracks the statistics for one potential
STL by analyzing timestamps from the executing
memory and local variable loads and stores. An array ofeight comparator banks allows us to analyze multiple
potential STLs executing simultaneously in loop nests.
Comparators compare thread start timestamps against
incoming cache line timestamps to check for speculative
state overflow and against incoming store timestamps to
identify critical arcs. At the end of each thread of apotential STL, critical arc lengths, critical arc counts, andbuffer overflows are accumulated into counters. The
accumulated statistics are read from TEST upon exitfrom a potential STL.

4. Compiling Thread Decompositions
4.1 microJIT Dynamic Compiler
Our Java runtime system is based on the opensource Kaffe VM (http://www.kaffe.org/), but we used ourown JIT compiler and garbage collector to address
performance limitations of the original VM.
We
developed microJIT [8], a fast, dataflow compiler thatcan generate code 30% faster than the Sun-client
dynamic compiler [17], which performs only limited
optimizations, and over 10x faster than Sun-server
compiler [12], an optimizing static single assignment(SSA) dynamic compiler [31]. Code generation speed
was achieved without sacrificing code quality byinterleaving compilation stages and minimizing compiler

1

2

3

(slave startup/shutdown code omitted)
STL_STARTUP:
scop_cmd enable_spec
mtc2$fp, saved_fpb
STL_INITSTL_RESTART:
scop_cmd reset_cachesmem_cmd kill_buffer
mfc2$fp, saved_fp
STL_INIT:<< init code, if any >>STL_TOP:bge<< cond >>, STL_SHUTDOWN<< loop body >>STL_EOI:
scop_cmd advance_cachesmem_cmd commit_buffer_and_headb
STL_TOP
STL_SHUTDOWN:
scop_cmd disable_spec
smem_cmd commit_buffer

CPU0(Master)

CPU1(Slave)CPU2(Slave)CPU3(Slave)4

1 Master CPU enters STL, enables TLS, and wakes up slave CPUs.
2 CPU waits to become the head, or non-speculative CPU, at which point it commits it

store buffer and then jumps to STL_TOP to start a new thread.
3 On loop exit condition, a speculative CPU jumps here, where it waits to become thehead processor before disabling speculation, killing slave CPUs, and returning control
to the sequentially executing master CPU.
4 On a RAW violation, a speculative CPU jumps to STL_RESTART where it kills CPUs

that are more speculative than itself, discards its store buffers, and then restarts
execution of the current thread at STL_TOP.

Figure 4 – Illustration of STL code executed by the processors.

passes. Code optimizations performed by our compiler
include common sub-expression elimination, copy
propagation, constant propagation, loop invariant code
motion, inlining and global register allocation. The
resulting code generated by microJIT is competitive withcommercial JIT compilers. Our experiments that show
the generated code is 20% faster than Sun-client
generated code and is within 25% of the performance ofSun-server generated code [8].
For the Jrpm system, the microJIT compiler wasaugmented to generate speculative thread code.
Speculative thread control routines from Table 1 areinserted into STLs chosen by TEST analysis, as
illustrated in Figure 4. In addition to the fixed overheadsof the speculative handlers, additional overheads may beintroduced in specific circumstances. STL initialization
values must be saved to the runtime stack by the masterprocessor and then loaded by the slave processor.
Cleanup code must be inserted at STL_STARTUP and
STL_SHUTDOWN by some of the optimizations below.
Local variables that may cause inter-thread (loop carried)dependencies in a STL must be communicated throughforced loads and stores in the runtime stack.

4.2 Optimizations for Improving Speculative
Performance
Optimizations
that
improvespeculative
performance, like register allocating loop invariants,using
non-violating
loop
inductors,
insertingsynchronization locks, and identifying reduction
operations, are applied automatically to selected STLs
when possible.
These compiler optimizations aredescribed below.
4.2.1 Loop invariant register allocation. Traditionally,
register allocating loop invariants eliminates the need toreload a read-only value every time it is used in asequential loop. Register allocating loop invariants
in STLs provides similar benefits, but is a little
trickier to implement. On a RAW violation, theregister state of a speculative thread is unknown
because it was interrupted in mid-execution.
Registers must be restored to their original thread
start value before the thread can be restarted. One
possible way of accomplishing this is by
maintaining a shadow register file that holds thethread start register state so that it can be quickly
restored on restart. Unfortunately, this approachrequires a significant amount of extra hardware to
mirror all the architectural registers and complex
logic to restore register state in a minimal numberof cycles. We accomplish similar functionality with
software only. Register allocated loop invariants
are saved to the runtime stack during TLS startup.
On a RAW violation, only relevant registers arerestored by a custom STL_RESTART handler, as
illustrated in Figure 5.
4.2.2 Non-communicating loop inductors. Loopinduction variables are always incremented thesame amount in every loop iteration.
Loopfor( i = 1;i < limit;
i += 2 ){<< loop body >>}1

Original loop
1 Master CPU stores initial valueof i = 1 on stack.
2 Load loop invariant in STL_INIT.
The loop invariant is reloaded on
a RAW violation since register
state is unknown after a violation.
3 Load inductor value in STL_INIT
using special iteration register (setto zero on STL startup,
incremented on every threadcommit).
4 Compute inductor value for next
thread locally (2*(4 CPUs) = 8).

(slave startup/shutdown code omitted)
STL_STARTUP:
li$t0, 1sw$t0, 0($fp)
swlimit, 4($fp)...
STL_RESTART:...
2
STL_INIT:STL_TOP:lw$s2, 4($fp)
lw$s1, 0($fp)
bge$s1, $s2, STL_SHUTDOWN<< loop body >>STL_EOI:
addiu$s1, $s1, 2
sw$s1, 0($fp)...
b
STL_TOP
STL_SHUTDOWN:...

STL_STARTUP:
li$t0, 1sw$t0, 0($fp)
swlimit, 4($fp)...
STL_RESTART:...
STL_INIT:lw$s2, 4($fp)
3
STL_TOP:lw$s1, 0($fp)
bge$s1, $s2, STL_SHUTDOWN<< loop body >>STL_EOI:
addiu$s1, $s1, 2
sw$s1, 0($fp)
4...
b
STL_TOP
STL_SHUTDOWN:...

STL_STARTUP:
li$t0, 1sw$t0, 0($fp)
swlimit, 4($fp)...
STL_RESTART:...
STL_INIT:
mfc2$s1, iterationsll$s1, $s1, 1
lw$t0, 0($fp)
addu$s1, $s1, $t0lw$s2, 4($fp)
STL_TOP:bge$s1, $s2, STL_SHUTDOWN<< loop body >>STL_EOI:
addiu$s1, $s1, 8...
b
STL_TOP
STL_SHUTDOWN:...

Base STL assembly+ Loop invariant register allocation+ Non-communicating loop inductors

Figure 5 – Illustration of two optimizations. Arrows show how code is moved by the optimizations.

inductors can be a performance problem for thread
speculation on loops because they result in a inter-thread(loop carried) dependency. Communication of inductors
introduces serialization between loop iterations and cancause RAW violations. Previous proposals [11][41][45]have used value prediction or scheduling to eliminate
these negative effects.
We use software and a simple hardware iteration
counter to completely eliminate communication of loop
inductors. To keep software and hardware requirements
low, our runtime system distributes loop iterations of a
STL to processors in a simple round robin order [33].
For four CPUs, this implies that CPU0 always handles
iterations 0, 4, 8, …, CPU1 always handles iterations 1,
5, 9, …, and so forth. This configuration allows us toeasily compute the next value of the loop inductor locallyfor the next speculative thread that a processor handles,
as shown in Figure 5. Like loop invariant register
allocation, the value of register allocated inductors must
be properly recovered after a thread restart. To achievethis, the STL_RESTART handler can compute the correct
current value of the inductor using a simple countertracking the current speculative thread iteration being
executed by a CPU.
4.2.3 Reset-able non-communicating loop inductors.
Non-communicating loop inductors can also be extended
to handle variables that look like loop inductors, but
occasionally have an unpredictable value at an unknown
loop iteration. The code to handle this is similar to thecode to handle normal loop inductors, except that when
the rare condition is encountered, the correct current
value is written and a violation and restart is forced tolater speculative threads. Within the STL_RESTART
handler, the restarted speculative threads can then load
the correct, updated value.
4.2.4 Thread synchronizing lock. Previous studies
have shown that minimizing violation frequency can
improve TLS performance [11][41]. For a frequent loop
carried dependency, it is often better to wait for thecorrect value than to get an incorrect one, violate, andthen have to restart. We can protect such a variable
using a synchronization lock that stalls speculative

threads until the variable has been properly updated, as
shown in Figure 6. This lock uses a special instruction,
lwnv (load word, non-violating), that acts like a normal
lw to return the most recently written value, even if it isspeculative, but can never cause a violation and restart.
Jrpm automatically inserts a synchronizing lock into
compiled code when the TEST profile result for a STL
shows a frequently occurring inter-thread dependency(e.g. > 80%) that has an average dependency arc length
much less than the average thread size.
(slave startup/shutdown code omitted)
STL_STARTUP:
sw$r0, 0($fp)
1...
STL_RESTART:...
STL_TOP:bge$s1, $s2, STL_SHUTDOWN
mfc2$t0, iteration
STL_WAIT:
Original loop2
lwnv
$t1, 0($fp)
bne$t0, $t1, STL_WAIT
1 Clear lock variable.
<< loop carried dep >>STL_SIGNAL:
2 Spin on lock value using lwnv
3
addiu
$t0, $t0, 1(load-word, non-violating) until thesw$t0, 0($fp)
value is equal to current iteration
STL_EOI:
number.
...
b
STL_TOP
3 After executing the protected
region, write the next iteration
STL_SHUTDOWN:
number to the lock.
...
lock = 0;
for( i = 0;i < limit;i++ ){
STL_WAIT( lock );<< loop carried dep >>STL_SIGNAL( lock );}+ Synchronizing lockFigure 6 – Illustration of a thread synchronizing lock.

4.2.5 Reduction operator optimization. Reduction
operations [3], like computing sums or finding min/max
values, are loop carried dependencies that can be easilytransformed so they do not result in inter-threaddependencies. Reductions can be computed locally forthe speculative threads that a given processor is handling.
The locally computed value from each processor can bemerged at the end of a STL to get the correct final value.

STL_STARTUP
for( ){ // outer loop<< outer loop body >>if( rare condition ){STL_SWITCH_STARTUP
for( ){ // inner loop<< inner loop body >>STL_EOI}STL_SWITCH_SHUTDOWN}
STL_EOI}STL_SHUTDOWN

Figure 7 – STL assembly for multilevel STL decompositions.

4.2.6 Multilevel STL decompositions. Multilevel STL
decompositions are useful in irregularly structured nested
loops, like the one shown in Figure 7. The two loops
here both contain significant parallelism, but the inner
loop, contained within a conditional block, is executed
infrequently. We would normally choose to speculate on
the outer loop, but speculating on the outer loop while
executing the infrequent inner loop could lead to load
imbalance between iterations that degrade speculative
performance.
Our compiler can insert low-overhead handlers sothat the selected STL can be switched to the inner loop
and then restored to the outer loop upon completion of
the inner loop. Multilevel STL decompositions can beapplied automatically when TEST profiling shows thatthe inner loop is executed infrequently (e.g. the loop
iteration count of the outer loop is much larger than theloop entry count of the inner loop).
4.2.7 Hoisted startup and shutdown routines. If thenumber of iterations per entry into a STL is low, then theoverhead of the STL_STARTUP and STL_SHUDOWN
handlers can be proportionally high. More than half of
this handler code wakes up the other CPUs (which areidle or interrupted from another process) and initializes
the speculation hardware. This code does not need to be
re-executed in regions of code that may have several
STLs or when a STL is entered multiple times, like aselected STL within a loop nest. In these cases, startup
and shutdown overheads can be reduced by hoistingsome of the STL startup and shutdown handler code to
the entry and exit of a given method, or to the outer-mostloop.

5. Virtual Machine Considerations
5.1 Exception Handling
One of the nice properties of thread-level
speculation is that it preserves the sequential execution
behavior even for unexpected events like exceptions.
Threads may generate false exceptions during TLS
because computations are based on speculative memoryreferences (e.g. a thread with a null pointer exception
may be restarted to execute with different memory
values). Consequently, a speculative thread with an
exception must wait until it becomes the non-speculative“head” thread [21]. Only when this happens is the

exception real and must be handled. In Java, hardware
and software exceptions are “thrown” up the call stack
until it is caught by a catch handler [16]. Nothing
special needs to happen if an exception thrown during
speculation is caught within an executing STL by acatch handler.
If an exception thrown during
speculation is not caught within a STL, exception
handling code must properly terminate speculative
execution before jumping to an exception handler
external to the STL.

5.2 Garbage Collection
Originally, memory allocation during speculationinterfered with performance in several benchmarks. Our
JVM uses a fast concurrent mark-and-sweep garbage
collector [23]. Unallocated objects are stored in a linked
free list. Allocating objects on every speculative threadof a STL caused a serializing dependency on this linked
list. To deal with this, we parallelized access to theallocator during speculation. This was achieved bymaintaining several free lists that can be accessedprivately by each processor during speculative execution.
Similar techniques could be applied to prevent serializing
dependencies in JVMs that use copying garbage
collectors [23].

5.3 Synchronized Objects
In Java, method invocations can be explicitly
synchronized to an object (using the synchronizedkeyword [16]) to prevent concurrent accesses frommultiple explicit Java threads. A simple object lock willcause an inter-thread dependency if it is locked andunlocked on every iteration during speculation. Such alock is unnecessary during speculative execution because
the correct sequential ordering of accesses by
concurrently executing speculative threads is guaranteed.
Unfortunately, object locks cannot be omitted fromcompiled code because they may be compiled into
methods called from a STL during speculation, but themethod may also be called during normal nonspeculative execution. We re-implemented the lockroutine to prevent object synchronization from causing
serialization during speculation, while maintaining thecorrect behavior during normal execution.

6. Performance Results
Table 3 lists benchmarks we ran on Jrpm, including
applications from the jBYTEmark (http://www.byte.com/),
SPECjvm98 (http://www.specbench.org/), Java Grande(http://www.epcc.ed.ac.uk/javagrande/javag.html)
benchmarks
suites, as well as real applications found on the internet.

6.1 Selected Speculative Thread Loops
Table 3 summarize the characteristics of the STLs
chosen from analysis. Overall, we found significant
diversity in the coverage of selected STLs. While many
programs have critical sections, Assignment, NeuralNet,
euler and mp3 have many STLs that contribute equally tototal execution time. Several programs have moreselected STLs (column e) than are shown in the table, but
the omitted decompositions do not have any significant
coverage (< 0.5% of total execution time). mp3, db, jess,and DeltaBlue have significant sections of serial
execution (column i) not covered by any potential STLs
that limits the total speedup for these applications.
TLS can simplify program parallelization, but not all
programs can benefit from it. Some integer benchmarks
evaluated using TEST showed no potential for speedup
using speculation. Programs with system calls in criticalcode, like I/O intensive programs, currently cannot
benefit from TLS because system calls cannot be
handled speculatively in our system. Several programs
had loops with characteristics that suggested little or no
thread-level parallelism.
Pizza, a Java source tobytecode compiler, and jack, a parser generator,
contained loops that were both too large and executed
too few iterations for speculation. Richards, a taskscheduler, contained a serializing dependency within its
critical STL that could not be optimized. Of two
different raytracer programs we looked at, one had aparallel loop that was predicted to consistently overflow
the speculative buffers, while the other had a parallel
loop that fit within the speculative buffers. This last
example suggests that the way a program is written canstrongly affect how well it can be automaticallyparallelized using TLS.
The larger programs contain significant numbers ofloops (column c) that would have made manual
identification of STLs a time consuming task. A visual
analysis of the source code identified that less than halfof the benchmarks can be analyzed by a traditional
parallelizing compiler (column a) (e.g. they resemble
floating point code w/ regular array accesses, no dynamic
pointers, bounded loops, and little control flow). The

average height of selected STLs (column f) have
granularities larger than the inner-most loop in a loop
nest. The maximum loop nesting depth column (columnd) indicates that eight comparator banks are sufficient toanalyze most of the nested loop structures in thebenchmark programs. When deeply nested loops with adepth greater than eight must be analyzed, banks are
initially allocated to the outer-most loops, but are freed
to be used by inner loops when the outer loops
eventually predict speculative buffer overflow.
Our experiments suggest that our dynamic
parallelization system can make STL selections that
account for input data set sizes. We noticed several
applications where the best decompositions can change
according to input data sizes (column b). In thesebenchmarks, multiple levels of parallelism exist in key
loops. Assignment, NeuralNet, LUFactor, euler, andshallow use a nested loop to traverse a 2-dimensional
data array. For these programs, loops lower in a loop
nest must be chosen with larger data sets because thenumber of inner loop iterations will rise, increasing theprobability of overflowing speculative state when
speculating higher in a loop nest.

6.2 Speculative Thread Performance
Each benchmark was run as a sequential annotatedprogram on Jrpm with the TEST profiling systemenabled. The benchmark was then recompiled andexecuted using speculative threads with the STLs
selected by TEST. Figure 8 displays the slowdown
during profiling, the predicted TLS execution time fromTEST analysis, and actual TLS performance. Figure 9shows total program speedup (adding compilation,
garbage collection, profiling, and recompilation
overheads) compared to serial execution for a given

199
29
546
510
501
20127
108
6307
339
2699
1313
119
555
158

1%
0%
0%
3%
22%
0%
0%
0%
27%
7%
0%
5%
0%
9%

1.2
1.1
4.1
7.8
6.5
11.0
2.0
1.9
6.6
4.1
11.3
2.4
3.4
0.0

0.2 11% 2%
0.8 73% 10%
128%
3.1 2% 1%
2.9 2% 2%5%
2.9 1%
9.5
0.8 18%2%
2.2
2.8 1% 1%
2.4
1%
4.4 1%
0.8 3%
27% 18%
3.5 2% 1%
0.0 6% 1%

Y
Y
Y
Y
Y
Y
Y

Y
Y
N
Y
N
Y
Y

32
5
2
13
8
19
11

2
3
2
3
2
4
3

13
2
1
7
1
8
3

1.1
2.0
2.0
1.6
1.0
1.9
1.0

66
187
100
64
1026
9
257

304
231
167802
455
96
617
1420

1%
0%
0%
0%
2%
1%
0%

4.8
1.4
4.3
1.9
2.0
1.7
7.8

1.6 5%
3.8 2%
3.5
0.6 3%
0.0 10%2.5 6%
6.2 1%

N
N
N
N
N

N
N
N
N
N

61
62
54
69
98

5
8
5
8
6

21
9
3
9
17

2.2
1.6
3.0
1.4
2.3

34
54
165
23
55

124
121
212
701
181

13%
1%
10%
47%
14%

2.5
2.8
4.0
4.1
3.1

1.0
1.6 10%2.2 3%
3.7
1.4 6%

29%

31%

3%

65%
11%

88%
2%
2%

4%
2%

42%
44%
1%

16%

8%

3%

(u)

Manual

29
7646
93755
23142
82
255
502
242
166
71
51931
942
6081
65

JVM – Java lock

2.0
1.0
1.8
1.7
2.6
2.0
1.3
2.0
5.3
3.0
3.5
1.4
2.0
1.0

(t)

JVM - Allocation

11
2
4
6
5
1
6
1
4
7
2
5
2
1

Opt - Resetable ind.

5
2
4
5
4
3
3
2
11
6
4
3
3
4

Opt - Sync

32
4
28
37
22
7
14
2
134
128
19
15
5
14

Opt - Reduction

Y
N
N
Y
N
N
N
N
N
N
N
N
N
N

Opt - MultilevelOpt - Loop inv.

N
N
N
N
N
N
N
Y
N
N
N
N
N
N

Opt - HoistingOpt - Overheads

Avg. store buffer sz.

Speedups from TLS Optimizations(m) (n) (o)(p) (q) (r ) (s)Avg. load buffer sz.

(l)Serial exection(k)Thread size (cycles)(j)Threads / STL entry(i)Avg. loop depth

TLS Statistics(g)(h)

Selected loops(f)Loop depth

TEST
(e)

Loop count(d)Data set sensitive

BenchmarkDescription
Integer
Assignment Resource allocation 51x51
BitOpsBit array operations
compress
Compressiondb
Database
5000.
deltaBlue
Constraint solver
EmFloatPnt FP emulation
HuffmanCompression
IDEA
Encryption
jess
Expert system
jLex
Lexical analyzer gen
MipsSimulator CPU simulatormonteCarlo Monte carlo sim.
NumHeapSort Heap sort
raytrace
Raytracer
Floating point
euler
Fluid dynamics
33x9
fft
Fast fourier trans.
1024.
FourierTest Fourier coefficients
LuFactor
LU factorization
101x101
moldynMolecular dynamics
NeuralNet
Neural net
35x8x8shallow
Shallow water sim. 256x256
Multimedia
decJpeg
Image decoder
encJpeg
Image compression
h263dec
Video decoder
mpegVideoVideo decoder
mp3
mp3 decoder

Characteristics
(a)
(b)
(c)

Analyzable

Data set

Category

Table 3 – Characteristics and performance statistics for benchmarks evaluated with STLs selected by TEST.

8%

8%
79%

17%
74%
245%

because they are computed locally, and is simpler
because it does not require significant hardware support
or instruction scheduling.
Table 3 shows the effect of specialized compiler
optimizations and VM modifications on the benchmarks.
VM modifications appear to have a more significant
impact. Parallelizing memory allocator access andremoving synchronized object locks during speculation
significantly affects performance on six benchmarks.
In general, the opportunities to apply compiler
optimizations are limited to specific STLs in integer
programs, but the sum impact is significant. The
resetable non-communicating loop inductor dramatically
improves BitOps due to the removal of a loop-carried
dependency from the relatively small threads in its
critical STL. Multilevel STL decompositions improve
mp3 and, to a much lesser degree, Assignment. Threadsynchronizing lock prevents performance-degrading
violations on monteCarlo and db. The opportunity toapply this optimization is less than we hoped for, but thelimited impact seems consistent with other studies thathave looked at techniques for minimizing violations[11][41]. The only compiler optimization that seems tohave little effect is hoisting startup and shutdown
handlers. This optimization would likely be most usefulin a nested loop with small number of iterations per entry
into the loop. The two loops in NeuralNet that use thisoptimization do not have the ideal characteristics, andonly benefit slightly from it.
Also included in Table 3 is the effect of manualtransformations to improve speculative performance.
For six of the integer benchmarks, some programmer
assistance is needed to expose parallelism.
The
transformations were achieved with the assistance of
TEST feedback. TEST profiling results that summarized
critical potential STLs and associated dependency arc
frequencies and lengths facilitated quick identification of
performance bottlenecks in the source code. The
resulting transformations, listed in Table 4, significantly
improve performance and do not slowdown the original
sequential execution. Only three of these benchmarks
require significant manual transforms, while the otherthree need only trivial modifications. Examination of the
program sources suggest most of these modifications can

1.25
1.00
0.75
0.50
0.25

Integer
Profiling

Benchm ark
Predicted

Floating point
Actualmp3

mpegVideo

h263dec

encJpeg

decJpegshallow

NeuralNet

moldynLuFactor

FourierTest

fft

euler

raytrace

NumHeapSort

monteCarlo

MipsSimulator

jlex

jess

IDEA

Huffman

EmFloatPnt

deltablue

db

compress

BitOps0.00

Assignment

Normalized execution timebenchmark run.
The results show relatively good speculative
performance for selected STLs. Overall, TLS execution
characteristics like average thread size, number of
threads per loop entry, and speculative buffers required(columns g, h, j & k) vary widely from program toprogram. The average thread size for most benchmarks
is at least a hundred or more cycles. Given that ourexperiments were conducted using single-issue MIPS
cores, the average size of threads is sufficiently large tosuggest that programs may further benefit fromsuperscalar cores that can exploit instruction-level
parallelism relatively independent of the coarser-grained
parallelism being targeted by TLS.
We found the overheads for profiling and dynamic
recompilation small, even for the shorter runningbenchmarks. This is possible due to the low-overhead
profiling system and relatively small amount of collected
profiling information required to make reliable STL
choices. In our benchmarks, selected STLs varied little
with the amount of profiling information collected once
enough data was collected to overcome local variationsin RAW violations, buffer overflows and thread sizes.
This is due to the fact that most selected STLs wereinvariant to the input data set and the input data sets werestable for the duration of the benchmark.
Forbenchmarks with STLs sensitive to input data set sizes,
changing in mid-execution to a larger input data set
could cause frequent speculative buffer overflows. For
these benchmarks, a potential solution would be trigger
reprofiling and recompilation when a selected STL
consistently experiences unexpected buffer overflows.
Table 3 shows the effect of optimizations andimprovements that impact all STLs. Reduced overheads
improve speculative performance more than 5% on 10
applications. Loop invariant register allocation only
improves performance 2-4% for five applications. The
effect of the non-communicating loop inductor is notshown because without this critical optimization,
performance suffers far too much to make a meaningfulcomparison.
While similar benefits of optimizing
inductor variables in speculative loops were shown by[11][41][45], our approach has advantages. Our scheme
suffers no overhead for communicating inductors

Multimedia

Figure 8 – Shows simulation results of slowdown during profiling, predicted TLS performance, and actual TLS performance on
the Hydra (4 CPUs) normalized to execution time of the original sequential program.

overflow appear to besmaller. For EmFloatPnt,
jLex, and MipsSimulator,
75%
wait-used state is due toload imbalance.
Since
50%
speculative
threaditerations must commit in25%
order, load imbalance
forcesspeculative
0%
processors to wait if
iterations ahead of it have
still
not
completed.
Predicted
speculative
performance does not
Integer
Floating point
Multimedia
Benchm ark
account for wait-used state
Application
GC
CompileProfiling
Recompile
because of the averaging
effects of accumulating
Figure 9 – Total program speedup with compilation, garbage collection, profiling, andrecompilation overheads.
counters.
Over ten applications,
not be performed automatically because they requireparticularly compress, Huffman, and mpegVideo, havehigh-level understanding of the program.
significant amounts of run-violated and wait-violated
Table 4 – Difficulty and potential for compiler automation ofstate that significantly degraded performance. Since wemanual transformations performed that improve speculative
derive predicted speculative performance by computing
performance.
parallelism from ideal scheduling of inter-threaddependencies, our analysis does not account for the costof violations. In actual speculative execution, violations
near the end of a speculative thread can cause a thread to
BenchmarkModified operations
restart and re-execute all its work, thereby losing any
NumHeapSort
Low N
7
Remove loop carriedparallelism that may have existed. Examinations ofdependency at top of sorted
program sources suggest that thread violations in theseheapbenchmarks are truly dynamic and cannot be mitigated
Huffman
Med N
22Merge independent streams
by thread synchronization or value prediction.
to prevent sub-wordLinesmodificed

Compiler
optimizable

Difficulty

Assignment
BitOpscompressdb
deltaBlue
EmFloatPnt
Huffman
IDEA
jess
jLex
MipsSimulatormonteCarlo
NumHeapSort
raytrace
euler
fft
FourierTest
LuFactor
moldynNeuralNet
shallow
decJpeg
encJpeg
h263dec
mpegVidmp3

Normalized Execution

100%

MipsSimulator

Med

N

70

db

Low

Y

4

compress

Low

N

13

monteCarlo

Med

N

39

dependencies during
compression. Guess next
offset when uncompressing
data stream.
Minimize dependencies forforwarding load delay slot
value
Schedule loop carried
dependency
Guess next offset whencompressing/uncompressing
data
Schedule loop carried
dependency

Overall, the results show TEST analysis does areasonable job of predicting speculative performance andcan effectively choose STLs that result in good speedups,
but differences between predicted and actual speculative
execution were found. To further understand thediscrepancy between predicted and actual TLS
performance from Figure 8, we looked at time spent invarious states during speculative execution, shown in
Figure 10. The primary differences appear to be from
effects that cannot be accounted for when predicting
speculative performance.
In EmFloatPnt, fft, jLex, and MipsSimulator,
significant processor time is spent in wait-used state.
For fft, this comes from buffer overflow stalls for large
STL iterations. While TEST analysis properly accounts
for overflow, its effects are predicted to be smaller
because the accumulated statistics make iterations that

7. Related Work
The Multiscalar paradigm [15] was the firstcomplete description and evaluation of an architecturewith TLS support. Several other architectures for TLS
using CMPs have been proposed [10][21][29][40][42].
These implementations have mostly targeted coarser
grains of granularity than the Multiscalar architecture. In
a similar vein, software-based dynamic dependence
detection has been proposed for traditional
multiprocessor systems as a way to preserve correctness
for loops executed in parallel that may have complex
dependency patterns [18][36][37][39].
There are numerous commercial and researchcompilers based on array dependence analysis forparallelizing Fortran programs [2][5][20][38]. Several
studies have looked at how these compilers might beapplied to general programs [4][25][35].
There is a growing body of related work on TLS
compilation addressing different architectures andaspects of the problem. The Multiscalar [43] compiler
focuses on compile-time heuristics to increase intraprocedural task sizes and intra-task dependency
scheduling to increase task parallelism.
These
optimizations are sufficient for the small threads targetedby Multiscalar, but do not address the memory
disambiguation and decomposition selection difficulties
of compiling for coarser-grained TLS systems.
A study of TLS limits by Oplinger et al. [34] andNormalized Execution

8. Conclusions

0.75

Our
paper
describes the Javaruntime parallelizing
machine (Jrpm), a
0.25
complete system that
automatically
0.00
parallelizes sequential
programs using threadlevel parallelism. Thissystem uses a chipInteger
Floating point
Multimedia
Benchm ark
multiprocessor, threadSerial
Run Used
Wait Used
Overhead
Run Violated
Wait Violated
level
speculation,
hardwareprofiling,State
Meaning
SerialTime spent not running speculatively
anddynamic
Run-used
Committed speculative CPU time used for application computationcompilation
togetherWait-used
Committed speculative CPU time waiting to become head or stalling due to buffer overflow
to enable a different
Overhead
TLS startup, eoi, restart and shutdown handler overheads
Run-violated
Speculative CPU time discarded due to RAW violation used for application computation
approach to automatic
Wait-violated
Speculative CPU time discarded due to RAW violation spent waiting to become head or stalling due to buffer overflow
parallelizationforFigure 10 – Breakdown of actual speculative execution by time spent in various states.
small-scalechip
Steffan and Mowry’s work on the Stampede TLS
multiprocessors. Simulation results demonstrate Jrpm’s
processor [40] have, like us, used simulation andability to automatically select and optimize appropriate
profiling to identify good thread decompositions. These
thread decompositions with minimal effort from thestudies used cycle-accurate CPU simulators that analyze
programmer. On our CMP with four processors, we
dependencies of all executing memory references toachieve speedups of 3 to 4 on floating point applications,deduce performance estimates of potential STLs.
2 to 3 on multimedia applications, and between 1.5 andNeither study specifically addressed how their technique
2.5 on integer applications.
could be used for automatic speculative compilation or
Future work will involve trying more applications
how their analysis could have been performed without
out on Jrpm and further investigation on how muchsignificant simulation and profiling overheads.
profiling is needed before recompilation into speculative
There has also been research on improving thethreads. We are also looking into new techniques toperformance of STLs once they are selected. Several
improve performance on applications with significant
studies [11][33][41] showed that minimizing inter-thread
dynamic violation frequencies that cannot be minimized
violations using hardware synchronization and value
by thread synchronization or value prediction.
prediction can significantly improve speculative
9. Acknowledgements
performance. Zhai et al. [45] found that compiler
scheduling to increase distances between inter-threadThis work was supported by DARPA Air Forcedependencies is most beneficial for minimizing
Contract F29601-01-2-0085 and NSF Grant CCRsynchronization stall time of induction variables, but
0220138.
scheduling of other inter-thread dependencies did not
improve performance significantly.
10. References
Tremblay et al. previously proposed a JVM system[1] Adve, V. S. et al. An integrated compilation and performancewith speculative thread support [7][42], but there are
analysis environment for data parallel programs. In SC‘95, Sansignificant differences from Jrpm.
Their CMP, theDiego, CA, November 1995.
MAJC processor, has only two processors and only
[2] Adve, V. S. et al. High Performance Fortran Compilation
supports TLS with inefficient software routines. They
Techniques for Parallelizing Scientific Codes.
In SC’98,
also do not propose how speculation can be appliedOrlando, FL, November 1998.
automatically to programs.
There has been other related research that has[3] Allen, R and Kennedy, K. Optimizing Compilers for Modern
Architectures: A Dependence-based Approach.
Morganconsidered how feedback can be used to dynamically
Kaufmann Publishers, San Francisco, CA, 2001.
parallelize programs. Ko et al. [26] identified optimal
decompositions through brute-force incremental[4] Artigas, P. et al.
Automatic Loop Transformations andParallelization for Java. In ICS’2000, Santa Fe, NM, May 2000.
execution of all possible decompositions in multilevel
parallel programs. Numerous systems have also been
[5] Blume, W. et al. Polaris: Improving the Effectiveness ofdesigned to manually tune parallel performance on
Parallelizing Compilers. In 7th International Workshop on
traditional multiprocessors [1][19][27][30], but they have
Languages and Compilers for Parallel Computing. Ithaca, NY,
August 1994.
relied on off-line, not real-time, dependence analysis ofmemory traces.
[6] Broadcom Corporation.
The Sibyte SB-1250 Processor.
mp3

mpegVideo

encJpeg

h263dec

decJpegshallow

moldynNeuralNet

LuFactor

FourierTest

fft

euler

raytrace

NumHeapSort

monteCarlojlex

MipsSimulator

jess

IDEA

Huffmandeltablue

EmFloatPnt

db

BitOpscompress

Assignment

0.50

http://www.sibyte.com/mercurian.
[7]

Chaudhry, S. et al. Space-Time Dimensional Computing for Java

Programs on the MAJC Architecture. In Java Microarchitectures,
Kluwer Academic Publishers, Boston, MA, April 2002.

High-Level Parallel Programming Models and Supportive
Environments. Ft. Lauderdale, FL, April 2002.

[8]

Chen, M. and Olukotun, K. Targeting Dynamic Compilation for
Embedded Environments. JVM’02, San Francisco, CA, August
2002.

[27] Liao, S. W. et al.
SUIF Explorer: An Interactive andInterprocedural Parallelizer. In PPoPP’99, Atlanta, GA, May
1999.

[9]

Chen, M. and Olukotun, K. TEST: A Tracer for Extracting
Speculative Threads. In CGO’03, San Francisco, CA, March
2003.

[28] Lindholm, T. and Yellin, F.
The Java Virtual Machine
Specification. Addison Wesley, Reading, MA, 1997.

[10] Cintra, M., Martinez, J. F., and Torrellas, J. Architectural
Support for Scalable Speculative Parallelization in SharedMemory Multiprocessors. In ISCA-27, Vancouver, BC, June
2000.
[11] Cintra, M. and Torrellas, J. Eliminating Squashes ThroughLearning Cross-Thread Violations in Speculative Parallelization
for Multiprocessors. In HPCA-8, Anaheim, CA, February 2002.
[12] Click, C.
High-Performance Computing with the Server
Compiler for the Java HotSpot Virtual Machine. In JavaOne
2001, San Francisco, CA, June 2001.
[13] Culler, D.E. et al.
Parallel Computer Architecture: A
Hardware/Software Approach. Morgan Kaufmann Publishers,
San Mateo, CA, 1998.
[14] Emer, J. Ev8: The post-ultimate alpha (keynote address). In
PACT’01, Barcelona, Spain, September 2001.
[15] Gopal, S. et al. Speculative Versioning Cache. In HPCA-4, Las
Vegas, NV, February 1998.
[16] Gosling, J., Joy, B., and Steele, G. The Java Language
Specification. Addison Wesley, Reading, MA, 1996.
[17] Griessemer, R. and Mitrovic, S. The Java HotSpot Virtual
Machine Client Compiler: Technology and Application. In
JavaOne 2001, San Francisco, CA, June 2001.

[29] Marcuello, P. and Gonzalez, A.
Clustered Speculative
Multithreaded Processors. In ICS’99, Rhodes, Greece, June
1999.
[30] Miller, B. P. et al.
Measurement Tools.
November 1995.

The Paradyn Parallel Performance
In IEEE Computer, 28(11):37-46,[31] Muchnick, S. Advanced Compiler Design Implementation.
Morgan Kaufmann Publishers, San Francisco, CA, 1997.
[32] Olukotun, K. et al. The case for a single chip multiprocessor. In
ASPLOS-VII, Cambridge, MA, October 1996.
[33] Olukotun, K., Hammond, L., and Willey, M. Improving the
Performance of Speculatively Parallel Applications on the Hydra
CMP. In ICS’99, Rhodes, Greece, June 1999.
[34] Oplinger, J. T., Heine, D. L., and Lam, M. S. In Search ofSpeculative Thread-Level Parallelism. In PACT’99, Newport
Beach, CA, October 1999.
[35] Wu, P. and Padua, D. Containers on the Parallelization ofGeneral-purpose Java Programs. In PACT’99, Newport Beach,
CA, October 1999.
[36] Rauchwerger, L. and Padua, D. The LRPD Test: Speculative
Run-Time Parallelization of Loops with Privatization andReduction Parallelization. In PLDI’95, La Jolla, CA, June 1995.

[18] Gupta, M and Nim, R. Techniques for Speculative Run-Time
Parallelization of Loops. In SC’98, November 1998.

[37] Saltz, J., Mirchandaney, R., and Crowley, K.
Runtimeparallelization and scheduling of loops. In IEEE Transaction on
Computers, 40(5):603-612, May 1991.

[19] Hall, M. W. et al. Experiences using the ParaScope Editor: an
interactive parallel programming tool. In PPoPP’93, pages 33-43,
May 1993.

[38] Sarkar, V. The PTRAN Parallel Programming System. In
Parallel Functional Programming Languages and Compilers,
ACM Press Frontier Series, pages 309-391, 1991.

[20] Hall, M. W. et al. Maximizing Multiprocessor Performance with
the SUIF Compiler. In IEEE Computer, December 1996.

[39] So, B., Moon, S., and Hall, M. W. Measuring the Effectivenessof Automatic Parallelization in SUIF. In ICS’98, Melbourne,
Australia, July 1998.

[21] Hammond, L., Willey, M., and Olukotun, K. Data Speculation
Support for a Chip Multiprocessor. In ASPLOS-VIII, San Jose,
CA, October 1998.
[22] Hennessy, J. L. and Patterson, D. A. Computer Architecture: A
Quantitative Approach, Third edition.
Morgan Kaufmann
Publishers, Inc. San Mateo, CA, 2002.
[23] Jones, R. and Lins, R. Garbage Collection: Algorithms for
Automatic Dynamic Memory Management. John Wiley & Sons,
Chichester, UK, 1996.
[24] Kahle, J.
Power4: A Dual-CPU Processor Chip.
Microprocessor Forum ’99, October 1999.

[40] Steffan, J. G. et al. A Scalable Approach to Thread-Level
Speculation. In ISCA-27, Vancouver, BC, June 2000.
[41] Steffan, J. G. et al. Improving Value Communication for ThreadLevel Speculation. In HPCA-8, Cambridge, MA, February 2002.
[42] Tremblay, M. MAJC: Microprocessor Architecture for Java
Computing. In HotChips’99, Stanford, CA, August 1999.
[43] Vijaykumar, T. N. and Sohi, G. S. Task Selection for a
Multiscalar Processor. In MICRO’98, Chicago, IL, August 1998.

In[44] Wall, D. Limits of Instruction-Level Parallelism. DEC Western
Research Lab WRL-TN-15, December 1990.

[25] Knobe, K. and Sarkar, V. Array SSA form and its use in
Parallelization. In PoPL’98, San Diego, CA, January 1998.

[45] Zhai, A. et al.
Compiler Optimization of Scalar Value
Communication Between Speculative Threads. In ASPLOS-X,
San Jose, CA, October, 2002.

[26] Ko, W. et al. Effective Cross-Platform, Multilevel Parallelism via
Dynamic Adaptive Execution. In 7th International Workshop on