THE JRPM SYSTEM FOR
DYNAMICALLY PARALLELIZINGSEQUENTIAL JAVA PROGRAMSAS INSTRUCTION-LEVEL PARALLELISM WITH A SINGLE THREAD OF CONTROLAPPROACHES ITS PERFORMANCE LIMITS, DESIGNERS MUST FIND OTHERARCHITECTURAL IMPROVEMENTS TO SPEED UP PROGRAM EXECUTION. THE

JRPM SYSTEM TAKES ADVANTAGE OF RECENT DEVELOPMENTS TO ENABLE A
NEW APPROACH TO AUTOMATIC PARALLELIZATION. JRPM CAN EXPLOIT
THREAD-LEVEL PARALLELISM WITH MINIMAL PROGRAMMER EFFORT.

Michael K. Chen
Kunle Olukotun
Stanford University

26

The quest to automatically parallelize general-purpose programs is a longstanding problem in the microarchitecturecommunity. Solving this problem is critical tocontinued architectural improvements in
microprocessor performance, as instructionlevel parallelism with a single thread of control
approaches its performance limits. We’ve
developed a solution that relies on four key
technologies: chip multiprocessors, threadlevel speculation, dynamic compilation, andhardware-based profiling. We can combine
these technologies and manage them inside aJava virtual machine (JVM). The resulting
system, the Java runtime parallelizing machine(Jrpm), can parallelize a wide range of integer, multimedia, and floating-point Javabenchmarks with excellent performance.
Jrpm is a complete system for parallelizing
sequential programs automatically for threadlevel parallelism. This dynamic parallelization
system overcomes the limitations of conventional parallelizing compiler and multiprocessor technology.

Published by the IEEE Computer Society

The parallelization problem
In wide-issue superscalar and very-longinstruction-word processors, instruction-level
parallelism faces diminishing returns (fromone to 10s of instructions). Processor architects are exploring coarser granularities, suchas fine-grained thread-level parallelism (from10 to thousands of instructions) to speed up
sequential-program execution. Multiprocessor architectures and parallelizing compilers
have both been around for some time now,
but neither is effective at exploiting threadlevel parallelism automatically.
Traditional small-scale multiprocessors (fromtwo to 16 processors) have effectively exploited very coarse-grained parallelism (greater thantens of thousands of instructions). Unfortunately, current multiprocessor architectures
must communicate dependencies throughout
the multiple layers of memory hierarchy. This
generates interprocessor communication latencies greater than hundreds of CPU cycles thatcompletely eliminate potential speedups fromfiner-grained parallel tasks.

0272-1732/03/$17.00  2003 IEEE

Traditional multiprocessors must also handle synchronization overheads for mutual
exclusion and event synchronization. Conservative synchronization preserves program
correctness, but too much synchronization
can greatly degrade multiprocessor performance. This can be a serious problem for
automatic program parallelization using parallelizing compilers.
Traditional parallelizing compilers use arraydata-dependence analysis.1 Data dependence
analysis determines dependence relationships
for pairs of array references in a program. A
compiler can use these results to reorder the
program to exploit coarse-grained parallelism
on a multiprocessor while correctly generating the same results as the original program.
Such compilers have successfully parallelized
Fortran-like numerical applications (whichhave considerable regular, well-structured parallelism) on traditional multiprocessors.
Unfortunately, data dependence analysis isoften complex and expensive. Furthermore,general integer programs have characteristics
such as complex control flow, irregularly structured loops, and significant pointer use thatmake them unsuitable for automatic compiler parallelization. These characteristics ultimately cause dependence analysis to return
imprecise dependency information for reference pairs, forcing the insertion of conservative, performance-degrading synchronization
into the generated code to safely handle
potential dependencies.

Jrpm approach
Jrpm is a dynamic parallelization systemthat overcomes the difficulties of applying current technologies and approaches for the automatic parallelization of general programs.
Jrpm parallelizes programs with almost no
input from the user or programmer. A custom
runtime system with special hardware support
analyzes dynamic execution for parallelism
and correctly handles dynamic dependencies.
Figure 1 shows the system’s key components:• Chip multiprocessor. Jrpm is based on the
Hydra chip multiprocessor (http://wwwhydra.stanford.edu).2 Decreasing featuresize and increasing transistor counts
make chip multiprocessors possible.3-6
Chip multiprocessors combine several

processors onto one die with a tightly
coupled memory interface. In this configuration, interprocessor sharing andcommunication costs are low, making
fine-grained thread-level parallelism
plausible.
• Thread-level speculation. Hydra supports
TLS,2,7-9 which allows arbitrary divisionof a sequential program into threads forparallel execution while still ensuring thatmemory accesses between threads maintain the original sequential program
order. Thus, TLS enables aggressive parallelization relative to traditional multiprocessors.
• Hardware profiler. Static parallelizing
compilers have insufficient information
to analyze dynamic dependencies effectively. Dynamic analysis to find parallelism complements a TLS processor’s
ability to parallelize optimistically and touse hardware to guarantee correctness.
TEST (Tracer for Extracting Speculative
Threads) support analyzes sequentialprogram execution in real-time to findthe best regions to parallelize with minimum hardware support.10• Virtual machine. Virtual machines suchas Sun’s JVM and Microsoft’s .NET VM
have become commercially popular forsupporting platform-independent applications. In our system, the JVM acts as
an abstraction layer that hides the
dynamic analysis framework and threadlevel speculation from the program, letting us seamlessly support a new
execution model without modifying thesource binaries.
Following Figure 1, the compiler derives acontrol flow graph (CFG) from program bytecodes and analyzes it to identify potential
thread decompositions.11 A single Hydra
processor executes, as a sequential program, aprogram that has been dynamically compiled
with instructions annotating local variables
and possible thread decompositions. Trace
hardware collects statistics in real time for theprospective decompositions. Once this hardware has collected sufficient data, the dynamic compiler recompiles into speculative
threads those regions predicted to have thelargest speedup and most coverage.

NOVEMBER–DECEMBER 2003

27

MICRO TOP PICKSJava bytecode

Application

1

Native codeandannotation
instructions

Control-flow graphanddataflow graphJust-in-timecompilerJava
virtualmachineHardware4
Profile analyzer

2

SoftwareHydra
chip
microprocessor

Nativethread-level
speculation
code

5
3
TEST profiler

TEST profiler

Figure 1. Overview of the Jrpm system, including hardware and software components. Programs running on Jrpm execute the following steps: 1. Identify thread decompositions byanalyzing bytecodes, and compile natively with annotation instructions. 2. Run annotatedprogram sequentially, collecting TEST (Tracer for Extracting Speculative Threads) profile statistics on potential thread decompositions. 3. Postprocess profile statistics and choose
thread decompositions that provide the best speedups. 4. Recompile code with thread-level
speculation (TLS) instructions for selected thread decompositions. 5. Run native TLS code.

Although the primary goal of our dynamic parallelization system is to automatically
speed up program execution, the system also
benefits from additional properties that are
attractive to both programmers and systemdesigners:• Reduced programmer effort. Manually
identifying fine-grained parallel decompositions can be time-consuming, especially for programs without obvious
critical sections. Because Jrpm automatically selects and guarantees the correct
behavior of executing parallel threads,
programmers can focus on performance
debugging instead of the usual complexities of parallel programming.
• Portability. Jrpm works with unmodified
sequential-program bytecodes. Because
the system doesn’t modify the binaries
explicitly for TLS, the code retains its
platform independence.
• Retargetability. Because parallel decompositions are not explicitly coded, Jrpm
can dynamically adapt decompositions at

28

IEEE MICRO

runtime for future chip multiprocessors
with more processors, larger speculative
buffers, or different cache configurations.
• 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
from both floating-point and difficultto-analyze integer applications.

Chip multiprocessor with TLS support
Hydra,2 shown in Figure 2, is a chip multiprocessor consisting of four single-issue,
pipelined MIPS processors, each with private
L1 data and instruction caches. High-speed,
low-latency read and write buses make threadlevel parallelism practical, even with substantial interprocessor sharing. An integrated,on-chip, shared L2 cache minimizes cache
misses when processors work on shared data.
TLS allows the division of a sequential program into threads for parallel execution.
Although speculative threads can include

CPU 0L1 I cache(16 Kbytes)

CP 2

L1 D cache +spec tags(16 Kbytes)

CPU 1

L1 I cache(16 Kbytes)

CP 2

CPU 2

L1 D cache +spec tags(16 Kbytes)

CP 2

CPU 3

L1 D cache +spec tags(16 Kbytes)

L1 I cache(16 Kbytes)

DRAM
interfaceI/O businterface

DRAM
main memory

I/O
devices

L1 I cache(16 Kbytes)

CP 2

L1 D cache +spec tags(16 Kbytes)

Write-through bus
Read/replace bus

Comparator bank
TEST

0

1

2

3

4

Store buffers (2 Kbytes each)On-chip L2 cache (2 Mbytes)

Figure 2. Hydra chip multiprocessor. Bold lines indicate additions for TLS support; dotted lines indicate additions for TEST profiling; CP means coprocessor.

loops, method call returns, or general regions,2
most research has focused on decompositions
based on loops. As Figure 3 (next page) shows,a speculative thread loop (STL) is a loop
decomposed into threads, with one loop iteration assigned to each thread. Data speculation hardware ensures that the threads
maintain the original sequential program’s
memory ordering.
The STL model designates the CPU executing the logically earliest thread as the nonspeculative head CPU. The model assigns logicallylater iterations, in order, to the other CPUs for
speculative execution. Once the head CPU
completes its iteration, it commits its state andstarts speculatively executing the next unassigned iterations; the CPU executing the logically next iteration then becomes the head CPU.
Speculative-thread support in Hydra consists of• a coprocessor (CP) in each CPU withextra registers, logic, and instruction support to control thread speculation;• extra speculative tag bits added to theprocessor L1 data caches to detect
interthread data dependency violations;and• store buffers attached to the secondary
cache to hold speculative data until a
speculative thread can either safely com-

mit them to the secondary cache or discard them.2
A running application controls TLS throughinstruction-set-architecture extensions andspecial stores issued onto the write bus. For aloop that has been transformed into speculative threads (as in Figure 3), overheads occur
at the start and end of speculation, at the endof every iteration, and on dynamic read-afterwrite (RAW) violations.

Tracer for extracting speculative threads
TLS simplifies many automatic parallelization challenges, but we had to consider certain constraints when selecting regions for thisexecution model. With the Hydra chip multiprocessor, the major constraints are as
follows:• True interthread data dependencies, orread-after-write hazards, always limit
speedup from parallel execution of speculative threads.
• Speculative read and write states bufferedby the hardware cannot be discarded during speculative execution and must fit
into the on-chip hardware structures.
Attempts to drop an L1 cache line with
speculative state or to write to a full store
buffer will force a speculatively executing

NOVEMBER–DECEMBER 2003

29

MICRO TOP PICKS

i=0

CPU 1

CPU 3

CPU 2

i=0
i=2

STORE X0

i=1

STORE Y2
STORE X2STORE Z2

1

STORE Y1
LOAD X1i=1

i=3
LOAD Z2

Time

CPU 0

CPU 0

3

i=3

2

X0
i=2

Y1

X2Y2 Z2

LOAD Z2(b)(a)

Figure 3. Sequential loop (a) transformed into a speculative thread loop (b) that uses speculative hardware to maintain thefollowing memory orderings: 1. For variable X, buffered writes are available only to sequentially later threads, preventing
write-after-read violations. 2. For variable Y, committing buffered speculative writes in threads according to the original program order maintains write-after-write ordering. 3. For variable Z, forwarding data to sequentially later threads, and forcing athread to restart when a speculative thread reads a value too early and violates sequential memory ordering, guarantees correct read-after-write ordering.

thread to stall until the thread becomesthe nonspeculative head thread and safe
execution of a load or store is possible.
• Only one thread decomposition (forexample, one loop in a loop nest) can be
active at a time.
• Compiled speculative thread code introduces sequential overheads from speculative-thread-management routines andforced communication of interthreaddependent local variables, limiting
speedups under TLS for very small threads(say, with less than 10 instructions).2,9These constraints impose conflicting
requirements for selecting thread decompositions. Speculating on small loops limits parallel coverage and suffers from higher
speculative-thread overheads relative to thework performed. Speculating on large loops
increases the probability of speculation buffer
overflows and could incur higher relative
dependency-violation penalties.
Dynamic analysis to identify STLs complements a TLS processor’s ability to parallelize
optimistically and to use hardware to guarantee correctness. The primary goal here, unlikewith traditional parallelizing-compiler analysis, is to identify where parallelism usually exists

30

IEEE MICRO

rather than where it is guaranteed to exist. Profiling can provide accurate statistics on dynamic dependency behavior, thread size, and buffer
requirements for most types of programs.

Analysis overview
The compiler examines a method’s CFG to
identify all natural loops that could be apotential STL.11 Two types of trace analyses
characterize an STL’s potential: load dependency and speculative-state overflow.
By examining executing loads and stores,
load dependency analysis looks for interthreaddependencies for an STL. TEST records thetime stamp when a memory or local-variable
store occurs; on subsequent loads to the same
address, TEST retrieves this time stamp. By
comparing this value with the thread-start
time stamp, it is possible to detect the frequency of interthread dependency arcs andidentify critical arcs. (A critical arc is the shortest dependency arc that limits parallelism
between a given pair of threads.)
Speculative-state-overflow analysis checks
that the speculative state generated by an iteration of an STL will fit within the limits of
the L1 caches and store buffers. TEST maintains a history of cache lines accessed by loads
and stores. Later, we can determine if subse-

quent accesses to the same cache line will
require allocating a new buffer state to the current speculative thread. By maintaining counters tracing these requirements, we canestimate how frequent a given STL will overflow its speculative buffer limits.
Once TEST has collected enough profilingdata (for example, at least thousands of iterations of an STL under analysis), it computes
the estimated speedup for an STL from thedependency arc frequencies, thread sizes, critical arc lengths, overflow frequencies, andspeculative overheads. Using statistics fromthe two analyses and the computed speedup,
Jrpm considers for recompilation into speculative threads only those loops that have average iterations per entry far greater than 1,
speculative buffer overflow frequency far lessthan 1, predicted speedup greater than 1.2,
and coverage greater than 0.5 percent during
sequential execution. It is often possible tochoose multiple decompositions in a loop
nest. In this case, Jrpm selects the best STL
by comparing the estimated execution time
for the different STL decompositions.

Hardware-software support for TESTThe hardware we designed to minimize
profiling overheads and improve accuracy analyzes a sequentially executing program andworks when speculation is disabled.
Annotation instructions that the dynamic
compiler inserts into native code mark important events relevant to trace analyses. Annotations mark a potential STL’s entry, exit, anditeration end. TEST uses explicit annotations
to track local variables in the same calling context as a potential STL that could cause dependencies. This simplifies the tracking of thesevariables in optimized compiled code. A
processor automatically communicates memory load and store events to the tracing hardware when tracing is enabled. At the end of
an STL (for example, an exit from a loop),
special routines read the collected statistics
from TEST for use by the runtime system.
The annotation instructions communicate
events to the comparator banks. The comparator banks carry out the bulk of the dependency and overflow trace analyses. One
comparator bank tracks the progress for a given
STL. Each bank, primarily comprising comparators and counters, analyzes and collects sta-tistics on incoming loads and stores. An arrayof comparator banks allows the tracing of multiple potential STLs that execute concurrently, as in nested loops. Our calculations suggestthat an implementation of the TEST hardware
with eight comparator banks would add lessthan 1 percent to the transistor count of theHydra chip multiprocessor with TLS support.
The speculative store buffers, which are idle
during sequential nonspeculative execution,
hold a history of previous time stamp events
during profiling. The buffers retrieve anaddress’ time stamp on an annotating memory or local variable instruction for use in thecomparator banks. The store buffers, organized as first-in, first-out (FIFO) buffers during tracing, effectively hold a limited historyof memory and local-variable accesses.

Compiling selected regions into
speculative threads
Jrpm’s Java runtime system is based on the
open-source Kaffe virtual machine(http://kaffe.org), but we used our own justin-time compiler, microJIT, and a garbage collector to make up for the original virtual
machine’s performance limitations. We augmented the microJIT compiler to generate
speculative thread code. The dynamic compiler inserts speculative-thread-control routines
into the STLs chosen by TEST analysis. In
addition to the fixed speculative-handler overheads, additional overheads are possible in certain circumstances. The master processor must
communicate STL initialization values to theslave processors by saving them to the runtime
stack. Certain optimizations must insert
cleanup code at the entry and exit of STLs. Furthermore, the compiler must force local variables that could cause interthread (loop-carried)dependencies in an STL to communicate
through loads and stores in a runtime stackshared between all speculative processors.
When possible, Jrpm’s dynamic compiler
automatically applies optimizations toimprove speculative performance for selected
STLs. Table 1 summarizes these compiler
optimizations.

Parallelizing real programs using Jrpm
Table 2 summarizes the characteristics of
the STLs automatically chosen from TEST
analysis. Overall, we found significant diver-

NOVEMBER–DECEMBER 2003

31

MICRO TOP PICKS

Table 1. Summary of low-level TLS compiler optimizations.
Optimization
Loop-invariant register
allocation
Noncommunicating loop
inductor
Resetable loop inductor

Reduction

Synchronizing lockMultilevel decompositions

Function
Register allocatesmemory load that always
returns the same value
Locally computes loop
inductor value for a thread

BenefitEliminates redundant
memory load per iteration

Cost
Load of value into theregister at init and restartComputation of inductor
value at init and restart

Locally computes loop
inductor-like value fora thread
Computes associative
operations locally

Eliminates frequent RAW
violations for loop inductors
incremented at end of iteration
Eliminates frequent RAW
violations for loop
inductor-like values
Eliminates dependencies for
associative operations

Protects loop-carried
dependencies fromspurious RAW violations
Switches selected STLs
between an outer andinner loop in a nested loop

Eliminates RAW violations
from frequent
dependencies
Improves load balancing for
irregularly structured
nested loops

sity in the coverage of selected STLs. Althoughmany programs have critical sections, Assignment, NeuralNet, euler, and mp3 have many
STLs that contribute equally to total execution time. Several programs have more selected STLs than those shown in the table, but
the omitted decompositions do not have any
significant coverage. The mp3, db, jess, andDeltaBlue benchmarks have significant sections of serial execution that are not coveredby any potential STLs, limiting the total
speedup for these applications.
These benchmarks come from thejBYTEmark (http://www.byte.com), SPECjvm98 (http://www.specbench.org/jvm98/),
and Java Grande (http://www.epcc.ed.ac.
uk/javagrande/) suites, as well as real applications found on the Internet.
TLS can simplify program parallelization,
but not all programs can benefit from it. Some
integer benchmarks evaluated using TESTshow no potential for speedup using speculation. Programs with system calls in critical code
do not speed up on Jrpm, because our implementation of TLS cannot handle system calls
speculatively. Several other integer programs
contain only loops that consistently overflowed
the speculative state, executed too few iterations for speculation, or contained an unoptimizable serializing dependency.

32

IEEE MICRO

Computation of loop
inductor-like value atinit and restart
Merge locally computed values
for final reduction value at
exit
Wait and signal overheadof the lock for every
threadInit and exit overhead forswitching between
STL decompositions

The larger programs contain so many loops
that manual identification of STLs would havebeen too time-consuming. A visual analysis of
the source code revealed that a traditional parallelizing compiler could analyze less than half
the benchmarks.

Performance results
We ran each benchmark as a sequential
annotated program on Jrpm with the TEST
profiling system enabled. The dynamic compiler then recompiled the benchmark and executed it using speculative threads with the
STLs selected by TEST. Figure 5 shows slowdown during profiling, the predicted TLS execution time from TEST analysis, and actual
TLS performance. Figure 6 compares total
program speedup (adding compilation,
garbage collection, profiling, and recompilation overheads) normalized with respect tonormal serial execution (including compilation and garbage collection overheads) for agiven benchmark run.
During profiling, most benchmarks experience no more than a 10 percent slowdown, andonly two applications have slowdowns approaching 25 percent, as Figure 5 shows. These slowdowns are reasonable, especially considering therelatively short period of time that most programs must spend on profiling to select an STL.

Simulations of this system show that ourapproach has significant potential for automatically exploiting thread-level parallelism.
From our wide set of Java benchmarks, we can
exploit thread-parallelism in integer, floatingpoint, and multimedia benchmarks. The best
speedups, approaching 4×, occur with thefloating-point applications. The speedups
achieved on multimedia and integer programs
are also significant, between 1.5× and 3×, butvary widely and are generally less than thoseachieved for floating-point applications.
Overall, TLS execution characteristics suchas average thread size and number of threads
per loop entry (see Table 2) vary widely fromprogram to program. Despite this, the average thread size for most benchmarks is at least
100 cycles. We conducted our experiments
using single-issue MIPS cores. The average
thread size appears large enough to suggestthat programs could benefit further fromsuperscalar cores that exploit instruction-level
parallelism relatively independent of thecoarse-grained parallelism that TLS targets.
The overheads for profiling and dynamic
recompilation are small, even for the shorter-running benchmarks. Contributing factors include the low-overhead profilingsystem, the limited profiling information
required to make reliable STL choices, andthe small amount of code that must berecompiled to transform a loop. In ourbenchmarks, selected STLs vary little withthe amount of profiling information collected, once TEST collects enough data to overcome local variations in RAW violations,buffer overflows, and thread sizes. The reason for this stability is that most selected
STLs are invariant to the input data set. For
benchmarks with STLs sensitive to the input
data set, the input data sets remain stable forthe duration of the benchmark. In real-worldcases, in which the input data sets can change
during runtime, Jrpm could trigger reprofiling and recompilation when a selected STL
sensitive to the input data set consistently
experiences unexpected behavior.
We also measured the effect of optimizations
and improvements that impact all STLs. We
found that the reduction in overheads improves
speculative performance more than 5 percent
on 10 applications. Loop-invariant register allocation improves performance only 2 percent toTable 2. Description and characteristics of integer benchmarks
evaluated on the Jrpm system.
Loop

No. ofcount

selected loops

Resource allocation

32

11

Bit array operations

42

compress

Compression

28

4

db

Database37

6deltaBlue

Constraint solver

22

5

EmFloatPnt

Floating-point emulation

7

1

HuffmanCompression

14

6

IDEA

Encryption

2

1
4

BenchmarkDescription

Assignment
BitOpsjess

Expert system

134

JLex

Lexical analyzer generator

128

7

MipsSimulator

CPU simulator

192monteCarlo

Monte Carlo simulation

15

5

NumHeapSort

Heap sort

5

2

raytrace

Ray tracer

14

1

euler

Fluid dynamics

32

13

fft

Fast Fourier transform

52

FourierTest

Fourier coefficients

2

1

LuFactor

LU factorization

13

7

moldynMolecular dynamics

81

NeuralNet

Neural net

19

8

shallow

Shallow water simulation

113

decJpeg

Image decoder

61

21

encJpeg

Image compression

62

9

h263dec

Video decoder

54

3

mpegVideoVideo decoder

69

9

mp3

Mp3 decoder

98

17* Average loop height is the number of nested loops between a selected loop and theinnermost loop.

4 percent for five applications. In addition,
without the noncommunicating loop inductor, performance generally suffers far too muchto make meaningful comparisons.
We had to resolve several correctness or performance bottleneck issues in interfacing the
SVM and the Hydra CMP with TLS support.
These modifications have a more significant
effect on benchmark performance than specialized compiler optimizations. Parallelizing
memory allocator access and removing synchronized object locks during speculation significantly affects performance on six integer
benchmarks. In general, the opportunities toapply specialized compiler optimizations arelimited to specific STLs in integer programs,
but the cumulative impact of the optimizations is significant.

NOVEMBER–DECEMBER 2003

33

MICRO TOP PICKS

Profiling

1.25

Predicted

Actual

1.00
0.75
0.50

Integer

mp3

mpegVideo

encJpeg

h263dec

decJpegshallow

moldynFloating point

NeuralNet

LuFactor

FourierTest

fft

eular

raytrace

NumHeapSort

monteCarlo

MipsSimulator

jLex

jess

IDEA

Huffman

EmFloatPnt

deltaBluedb

BitOps0.00

compress

0.25
Assignment

Normalized execution time

1.50

Multimedia

BenchmarkFigure 5. Simulation results of slowdown during profiling, predicted TLS performance, and actual TLS performance on Hydra(four CPUs) normalized to the original sequential program’s execution time.

Future work on Jrpm will focus on threeareas: dynamic reoptimization of runningapplications, performance enhancements on
applications that currently perform below
expectations using TLS, and scaling of the system to work on larger multiprocessor systems(more than four CPUs). We are also looking
at running additional applications on Jrpm tofurther demonstrate the system’s ability to
speed up a wide variety of programs.
MICRO
Acknowledgments
We thank Lance Hammond for his valuable
feedback and simulator support, and Tim
Wilkinson for his support of the Kaffe virtual
machine. US Defense Advanced Research Projects Agency Air Force contract F29601-01-20085 and National Science Foundation grant
CCR-0220138 provided research funding.

References
1. R. Allen and K. Kennedy, Optimizing
Compilers for Modern Architectures: A
Dependence-Based Approach, Morgan
Kaufmann, 2001.
2. L. Hammond, M. Willey, and K. Olukotun,“Data Speculation Support for a Chip
Multiprocessor,” Proc. 8th Int’l Conf.
Architectural Support for Programming
Languages and Operating Systems(ASPLOS VIII), ACM Press, 1998, pp. 58-69.

34

IEEE MICRO

3. “SiByte SOCs: BCM1125H and BCM1250,”
Broadcom Corp., http://sibyte.broadcom.
com/public/chips/index.html#bcm1250.
4. J. Emer, “Ev8: The Post-Ultimate Alpha,”
Proc. Int’l Conf. Parallel Architectures andCompilation Techniques (PACT 01), IEEE CS
Press, 2001, keynote address.
5. J. Kahle, “Power4: A Dual-CPU Processor
Chip,” Proc. Microprocessor Forum, In-Stat
MDR, 1999.
6. M. Tremblay, “MAJC: Microprocessor
Architecture for Java Computing,” Proc.
11th Ann. Int’l Symp. High-Performance
Chips (Hot Chips XI), IEEE CS Press, 1999.
7. M. Cintra, J.F. Martinez, and J. Torrellas,“Architectural Support for Scalable
Speculative Parallelization in SharedMemory Multiprocessors,” Proc. 27th Ann.
Int’l Symp. Computer Architecture (ISCA 27),
ACM Press, 2000, pp. 13-24.
8. P. Marcuello and A. Gonzalez, “ClusteredSpeculative Multithreaded Processors,”
Proc. ACM Int’l Conf. Supercomputing (ICS99), ACM Press, 1999, pp. 365-372.
9. J.G. Steffan et al., “A Scalable Approach toThread-Level Speculation,” Proc. 27th Ann.
Int’l Symp. Computer Architecture (ISCA 27),
ACM Press, 2000, pp. 1-12.
10. M. Chen and K. Olukotun, “TEST: A Tracer
for Extracting Speculative Threads,” Proc.
Int’l Symp. Code Generations andOptimization (CGO 03), IEEE CS Press,

Application

GC

CompileRecompile

Profiling

Normalized execution (%)

100

75

50

25

Integer

Floating point

mp3

MpegVideo

h263dec

encJpeg

decJpegshallow

NeuralNet

moldynLuFactor

FourierTest

fft

eular

raytrace

NumHeapSort

monteCarlo

MipsSimulator

jLex

jess

IDEA

Huffman

EmFloatPnt

deltaBluedb

compress

BitOpsAssignment

0Multimedia

BenchmarkFigure 6. Total program speedup with compilation, garbage collection, profiling, and recompilation overheads using default
benchmark data sets.

2003, pp. 301-312.
11. S. Muchnick, Advanced Compiler Design
Implementation, Morgan Kaufmann, 1997.

Michael K. Chen is a PhD candidate in electrical engineering at Stanford University. His
research interests include high-performanceand parallel computer architectures, and optimizations for improving the performance ofmodern programming language features, suchas garbage collection and dynamic compilation. Chen has a BS and MS in electrical engineering, and an MS in industrial engineering,
all from Stanford University. He is a memberof the IEEE and the ACM..
Kunle Olukotun is an associate professor ofelectrical engineering at Stanford University,where he leads the Hydra project. His researchinterests include the design, analysis, and verification of computer systems using ideas fromcomputer architecture and CAD. Olukotun
has a BS in computer engineering from CalvinCollege and an MS and PhD in computerengineering from the University of Michigan.
He is a member of the IEEE and the ACM.
Direct questions and comments about thisarticle to Michael K. Chen, Stanford University, Gates Bldg. 3A-316, Stanford, CA,94305-9030; mikey@hydra.stanford.edu.

For more information on this or any othercomputing topic, visit our Digital Library at
http://www.computer.org/publications/dlib/.

NOVEMBER–DECEMBER 2003

35