TEST: A Tracer for Extracting Speculative Threads
Michael K. Chen
Stanford University
mikey@hydra.stanford.edu

Kunle Olukotun
Stanford University
kunle@ogun.stanford.edu

Abstract

synchronization. With TLS, a sequential program can be
decomposed into threads to be run on the processors
without regard to memory dependencies. The threads aresequenced in the order in which they would execute
sequentially, but are actually executed in parallel. Data
speculation hardware support ensures that true
dependencies between memory accesses are honored
across threads by backing up and restarting threads that
execute an inter-thread dependent load too early.
We have designed Hydra, a chip multiprocessor (CMP)
with thread speculation support [15]. The granularity of
speculative threads targeted by Hydra ranges from 10s to
1000s of instructions. We would like decompositions to
be chosen automatically because such fine-grained threads
are impractical to manually identify in large programs andare smaller than threads that should be explicitly coded bya programmer.
A CMP with speculation support allows us to approach
automatic parallelization differently. Chip multiprocessors
combine several CPUs onto one die with a tightly coupledmemory interface. The high-bandwidth, low latencyinterconnect and small number of processors (four) in
Hydra reduces the importance of parallelizing compiler
optimizations like blocking and loop reordering thatminimize inter-processor communication in traditional
multiprocessors. Potential write-after-read (WAR) andwrite-after-write (WAW) hazards, which must be
identified and correctly ordered by the compiler intraditional multiprocessors, are automatically handled by
the speculation hardware and never exact performance
penalties.
TLS simplifies many automatic parallelization
challenges, but there are significant constraints that must
be considered. On Hydra, the major constraints are:• True inter-thread data dependencies, or read-after-write(RAW) hazards, always limit speedup from parallel
execution of speculative threads.
• Speculative read and write state that is buffered by the
hardware may overflow for large, long-runningspeculative threads, forcing speculative execution tostall until a load or store can be performed safely.
• Only one thread decomposition may be active (e.g. one
loop in a loop nest) at a given time.
• Compiled speculative thread code introduces sequential

Thread-level speculation (TLS) allows sequential
programs to be arbitrarily decomposed into threads thatcan be safely executed in parallel. A key challenge for
TLS processors is choosing thread decompositions thatspeedup the program. Current techniques for identifying
decompositions have practical limitations in real systems.
Traditional parallelizing compilers do not work effectively
on most integer programs, and software profiling slows
down program execution too much for real-time analysis.
Tracer for Extracting Speculative Threads (TEST) is
hardware support that analyzes sequential program
execution to estimate performance of possible thread
decompositions. This hardware is used in a dynamic
parallelization system that automatically transforms
unmodified, sequential Java programs to run on TLS
processors. In this system, the best thread decompositions
found by TEST are dynamically recompiled to run
speculatively. This paper describes the analysis performed
by TEST and presents simulation results demonstrating its
effectiveness on real programs. Estimates are also
provided that show the tracer requires minimal hardware
additions to our speculative chip-multiprocessor (< 1% of
the total transistor count) and causes only minor
slowdowns to programs during analysis (3-25%).

1. Introduction
Modern compilers that perform array datra-dependence
analysis can automatically parallelize Fortran-likenumerical applications on traditional multiprocessors[2][5][14][27]. Unfortunately, numerous challenges havemade automatic compiler parallelization of general integer
programs difficult. Analyzing pointer aliasing, control
flow, irregular array accesses, and dynamic loop limits aswell as handling inter-procedural analysis complicate static
dependence analysis [3][21]. These difficulties introduce
imprecision into dependence relations, limit the accuracyof parallelism estimates, and force conservativesynchronization to safely handle potential dependencies
when running on a traditional multiprocessor.
Thread-level speculation (TLS) is a technique thatenables parallel execution of sequential applications ontightly coupled multiprocessors without explicit© 2003 IEEE. Published in the Proceedings of CGO’03, 24-26 March 2003 in San Francisco, CA, USA. Personal use of this material is permitted. However,
permission to reprint/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.

overheads [22][29] from speculative thread
management routines and forced communication ofinter-thread dependent local variables.
These constraints impose conflicting requirements
when selecting thread decompositions. While threads canbe composed in many ways [23][7][15], most research has
focused on decompositions based on loops because
experimentally, they have yielded the most performancegains. A speculative thread loop (STL) is a loop
decomposed into threads where one loop iteration is one
thread. Applying the constraints to these decompositions,speculating on small loops limits parallel coverage andsuffers from higher speculative thread overheads relative
to work performed. Speculating on large loops increases
the probability of speculation buffer overflows and may
incur higher dependency violation penalties.
Previous studies of TLS processors have relied on
simulation and profiling to identify appropriate STLs
[23][29]. In these studies, cycle-accurate CPU simulatorswith dependence analysis of executing memory referenceswere used to deduce performance estimates of potential
STLs. These results were used to select the best STLs for
actual speculative execution. This type of dynamic
analysis is computationally expensive, slowing execution
over 100x during analysis, but is effective and bypasses
the difficulties of static compiler analysis.
Dynamic analysis to identify STLs complements a TLS
processor’s ability to parallelize optimistically and use
hardware to guarantee correctness. The primary goal is to
identify where parallelism usually exists. As stated earlier,integer program characteristics force dependency analysis
using static compilers to be conservative and imprecise,making it difficult deduce program parallelism. These
characteristics also make it difficult to statically estimate
thread size and buffer requirements essential to predicting
speculative performance. Profiling, on the other hand, canprovide accurate statistics on dynamic dependency
behavior, thread size, and buffer requirements for mosttypes of programs.
In this paper, we present Tracer for Extracting
Speculative Threads (TEST), hardware support in Hydra
for low-overhead profiling of potential STLs. Along witha Java virtual machine (JVM), Hydra with TEST and TLS
support are used together to create the Java Runtime
Parallelizing Machine (Jrpm), a complete system that uses
speculative threads to dynamically parallelize sequential
Java programs.
Virtual machines (VMs) like the JVM and Microsoft’sRotor (for C#) have become commercially popular inrecent years as a way of supporting applications without
being tied to a specific operating system or processor
architecture.
Our system demonstrates how thisvirtualization can be used in a novel way to seamlessly
support new execution models without modifying existing
platform independent program sources. Key to making

this work is the VM’s platform-independent bytecode
representation and dynamic recompilation support.
In the Jrpm system, the compiler derives a control-flow
graph from program bytecodes and analyzes it to identify
potential STLs. A program that has been dynamicallycompiled with instructions annotating local variables andSTL boundaries is executed as a sequential program on asingle processor of Hydra. The trace hardware collects
statistics for the prospective STLs. The JVM takes resultsfrom TEST analysis to identify the best code sub-sections
to dynamically recompile into speculative threads. By
relying on dynamic execution profiles collected by TEST,a simple scalar compiler is all that is required to generate
the speculative threads.
The contributions of this paper are:
• We show how potential STLs are selected from Java
programs and describe a simple trace algorithm toselect optimal decompositions quickly. The analysis
extracts speculative thread coverage, data dependence
timing, and speculative state requirements frompotential STLs, and identifies the best decompositions
by comparing the collected statistics. The analysis also
generates dependency profiles for directing compiler
optimizations and performance tuning by aprogrammertoimprovespeculative
threadperformance.
• We describe the hardware and software for
implementing the trace algorithm on Hydra. During
analysis, this implementation introduces only minimal
slowdowns (3-25%) to sequentially executing Java
programs. A similar software-only implementation
would be unacceptable for use in a dynamic
compilation system because it slows execution over
100x during analysis. Total hardware requirements for
implementing TEST are minimal because it utilizes
some of the hardware normally used only for
speculation, and only requires addition of a small
hardware comparator array (< 1% of the total CMP
transistor count) and support for a few additional
processor instructions.
The outline of this paper is as follows: Section 2
describes related work in TLS, dynamic dependence
detection, and dynamic parallelization systems. Section 3
is a brief introduction and overview of the Jrpm system.
We describe the algorithms for analyzing traces andselecting STLs in Section 4 and provide details of the
TEST hardware implementation in Section 5. In Section 6,
we present results from applying TEST to real programs.
Finally, conclusions are discussed in Section 7.

2. Related Work
The Multiscalar paradigm [11] was the first complete
description and evaluation of an architecture with TLS
support. Several architectures for TLS using CMPs havebeen proposed [9][15][20][29]. These implementations

have mostly targeted coarser grains of granularity than theMultiscalar architecture. Similar to TLS, software-based
dynamic dependence detection has been proposed for
traditional multiprocessor systems to preserve correctness
for loops executed in parallel that may have complex
dependency patterns [12][25][26][28].
There has been some related work on selecting
decompositions for TLS processors. The Multiscalar [32]compiler focused on compile-time heuristics to increase
intra-procedural task sizes and intra-task dependency
scheduling to increase task parallelism.
These
optimizations are sufficient for the smaller threads targetedby Multiscalar, but do not address the memory
disambiguation and decomposition selection difficulties ofcompiling for coarser-grained TLS systems. Trace-driven
simulation was used by Oplinger et al. to study the limits
of TLS [23], and by Steffan and Mowry for manual
selection of loops to be executed speculatively on the
Stampede TLS machine [29]. Neither study specificallyaddresses how their technique can be used for automatic
speculative compilation or how their analysis can be
performed without significant simulation overheads.
Chaudhry et al. [6] provide few details about how
decompositions are selected for the MAJC TLS processor
and Cintra et al. [9] restrict speculative decompositions intheir TLS architecture to the inner-most loop of a loop
nest.
There has also been research on improving performanceof STLs once they are selected. These techniques include
hardware synchronization and value prediction schemes tominimize violations [10][30], and compiler scheduling toincrease distances between inter-thread dependencies[30][34].
Numerous commercial and research compilers based onarray dependence analysis for parallelizing Fortranprograms have been developed [2][5][14][27]. Several
studies have looked at how these compilers might beapplied to general programs [4][17][24]. The Jrpm system
exploits parallelism exposed to the hardware analyzer with
only a simple scalar compiler. Additional use of an arraydata-dependence compiler might further improve parallel
performance of STLs chosen by TEST and uncover hidden
parallelism, but this is beyond our current scope.
There has been other loosely related research that has
used feedback to dynamically parallelize programs. Ko et
al. [18] identified optimal decompositions through bruteforce incremental execution of all possible decompositions
in multi-level parallel programs.
There have been
numerous systems designed to tune parallel performanceon traditional multiprocessors [1][13][19], but they haverelied on off-line, rather than real-time, dependency
analysis of memory traces.

3. Java Runtime Parallelizing Machine(Jrpm)
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 STLs by analyzing bytecodes and compile
natively with annotation instructions.

2

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

3

Post-process profile statististics and choose STLs thatprovide the best speedups.

4

Recompile code with TLS instructions for selected STLs.

5

Run native TLS code.

Figure 1 – Block diagram of Jrpm.

A block diagram of Jrpm outlining its various softwareand hardware components is shown in Figure 1. The
compiler chooses possible STLs by analyzing a program
control-flow graph. A program that has been dynamicallycompiled with instructions annotating local variables andSTL boundaries is executed as a sequential program on
one processor of Hydra. The trace hardware analyzes
prospective STLs. The code is dynamically recompiled
into speculative threads on regions that are predicted tohave the largest speedup and most coverage. Section 3.1
and Section 3.2 provide a brief overview of the Hydra
CMP and the microJIT dynamic compiler.

3.1. Hydra CMP with Speculative Thread
SupportHydra [15][22], shown in Figure 2, consists of four
single-issue pipelined MIPS processors, each with private
L1 data caches, attached to an integrated on-chip L2 cachewith separate read and write buses. Speculative thread
support in our CMP consists of special coprocessor
instructions, extra speculative tag bits added to each line of
the L1 data caches, and a set of secondary cache write
buffers. The coprocessor instructions provide an interface
to the thread speculation control hardware, the tag bits
detect data dependency violations between threads, and thewrite buffers hold speculative data until it can be safely
committed to the secondary cache or discarded. The
physical limits of buffered speculative state are given in
Table 1.

Central bus arbitrator

CPU0
L1 ICache(16kB)CP2

CPU1

L1 DCache +Spec tags (16kB)

L1 ICache(16kB)CP2

CPU2

L1 DCache +Spec tags (16kB)

L1 ICache(16kB)CP2

CPU3

L1 DCache +Spec tags (16kB)

L1 ICache(16kB)CP2

L1 DCache +Spec tags (16kB)

applied when possible.
Details on these speculative
compiler optimizations will
be presented in a future
paper.

4. TEST Algorithms
Write bus (64b)
Read bus (256b)
Comparator banks

TEST

#0

#1

#2

#3

SDRAM
interfaceI/O businterface

DRAM Main
MemoryI/O Devices#4

Write buffers
On-chip L2 cache (2MB)

Figure 2 – Block diagram of our CMP. TLS support blocks shown in dotted lines. TEST
hardware blocks shown in dark blocks.
Table 1 – Thread-level speculation buffer limits.
BufferLoad bufferStore buffer

Per-thread limit
16kB (512 lines x 32B)
2kB (64 lines x 32B)

Associativity
4-way
Fully

Table 2 – Thread-level speculation overheads.
TLS Operation
Loop startup

Overhead/ delay
25 cycles

Loop shutdown

25 cycles

Loop end-of-iteration
Violation and restart

5 cycles5 cyclesStore-load
communication

10 cycles

Additional overheads
Initialize loop local variables
Load register-allocated loop
invariants
Complete sum and min/max
reductions
Increment loop iterators
Load register-allocated loop
invariants

3.2. microJIT Dynamic CompilerThe
open-source
Kaffe
virtualmachine(http://www.kaffe.org/) was chosen for our Java runtime
system. The microJIT compiler [8] was augmented togenerate both annotated code for TEST analysis andspeculative thread code. Once a STL is chosen, thecompiler inserts assembly routines, shown in Table 2, thatstart, control, and terminate speculative threads. Theseroutines introduce some overheads relative to the original
sequential code. The compiler also performs optimizations
and transformations on the selected STLs. Inter-thread
local variable dependencies are globalized and local
variable initializers are communicated to each thread.
Optimizations that improve speculative performance, likeregister allocating loop invariants, using non-violating loop
inductors,
insertingsynchronization
locks,
andtransforming reduction operations (e.g. sum, min/max), areThis section describes indepth the trace analyses
performed on potential
thread decompositions andthe decision process used to
select thread decompositions
from collected statistics.
Section 5 describes the
hardware and software
support required to support

the trace analyses.

4.1. Identifying Potential Decompositions
Speculative threads can be composed from loops,
method call returns, and general regions [7][15][23]. The
remainder of this paper will focus only on decompositions
formed from loops. Our experiments so far have not foundmany method call return or general region decompositions
that are either not covered by similar loop decompositionsor have significant coverage to impact total execution time.
The compiler chooses potential STLs by examining amethod’s control-flow graph to identify all natural loops[21]. Loops are chosen optimistically, relying instead on
TEST results to identify desirable decompositions. Anyloop without obvious loop-carried dependencies thatwould completely eliminate speedup (e.g. end-of-loop
store and start-of-loop load) is considered a potential STL.
Loop inductors [21], which are dependencies that can beeliminated by the compiler, are ignored so that potentiallyparallel loops are not overlooked. Scalar analysis is used
to identify simple dependencies, but we forgo advanced
techniques that require analyzing array access patterns,
control flow, or memory accesses to find dependencies.

4.2. Trace Analyses
This section describes the two trace analyses performed
to characterize the potential of a STL, the load dependency
analysis and the speculative state overflow analysis. TEST
analysis relies on the notion of event timestamps, or thetime when an event occurs. Timestamps from different
events are compared against each other to computespecific statistics.

1

Inter-thread (loop-carried)dependency due to in_p results in
a dependency arc length of 8.

2

Dependency due to out_p results
in a dependency arc of length 9.
The dependency arc length of in_p
is the critical arc because it isshorter.

3

After many threads have executed,
the accumulated counter values
generate statistics that are used to
predict speculative performance of
this STL.

Speculative threads
Accumulated statistics

thread 2
time op
14 start

thread 3
time op
24 start

do {

do {

do {

3

=8
26 – 18

2

LD in_p1

16

LD in_p4

ST in_p88=

18

ST in_p20
21
22

LD out_p
32 – 21 = 11
ST out_p} while (LD in_p);

23

end

16
Thread size

Original loop// outer loop (selected STL)do {n = root;// inner loop
while (tree[n].left != -1) {if(in.getBit(in_p) == 0) {n = tree[n].left;} else {n = tree[n].right;}
in_p++;}
out[out_p++] = tree[n].char;} while (in_p < in.size());

thread 1
time op
0 start

–

–
20

8

ST in_p101112

LD out_p
ST out_p} while (LD in_p);

13

end

=
11

9

2

Counters
Elapsed time in loop
Thread countLoop entry count
Critical arc count to previous thread
Accum. critical arc lengths to previous thread
Critical arc count to earlier thread
Accum. critical arc lengths to earlier thread# cycles# threads# entries# critical arcs to t-1
Σ critical arc lengths to t-1# critical arcs to <t-1
Σ critical arc lengths to <t-1

Values derived from counters
Avg. thread size
Critical arc frequency to previous thread
Avg. critical arc length to previous thread
Critical arc frequency to earlier thread
Avg. critical arc length to earlier thread
Avg. iterations per loop entry# cycles / # threads# critical arcs to t-1 / (# threads – 1)
Σ critical arcs lengths to t-1 / # critical arcs
# critical arcs to <t-1 / (# threads – 1)
Σ critical arcs lengths to <t-1 / # critical arcs
# threads / # entries

26

LD in_p

30
31
32
33
34

ST in_p35

end

LD out_p
ST out_p} while (LD in_p);

Thread
2
23
2
1
1
8
0
0

1
13
1
1
0
0
0
0

3
35
3
1
2
16
0
0

Derived values after thread 3
11.6
1.0
8
0
0
3

Figure 3 – Example (Huffman decode) of the load dependency analysis. Analysis is performed on the outer loop in this example.
Loop-carried dependencies are bold in source code. Arrows represent dependency arcs. Critical arcs shown in darker arrows.

(c)

0x8
0x20
0x8
0x8

0x0
0x2
0x0
0x2

N
Y
N

5

0x8
0x4
0x20
0x20
0x8

0x0
0x2
0x2
0x2
0x0

Y
N

15

N

Y
Y
Y

10
40
30

Overflow++ if (f) > LD limitor (g) > ST limit(b)

ST counter++ on ST if not (b)or not (e)(a)

LD counter++ on LD if not (a)or not (e)Old timestamp

Index

LD/ST in current
thread?
is (c) > (d) ?

ST timestamp hit

Tag

Thread start time

LD timestamp hit

Op
New thread
LD 0x20000
ST 0x10040
LD 0x20008
LD 0x20040
New thread
LD 0x20000
LD 0x10040
ST 0x10040
ST 0x10048
LD 0x20000

4.2.2 Speculative state overflow analysis.
The
speculative state overflow analysis checks that speculative
state for a STL can fit within the L1 caches and store
buffers. Each L1 data cache line includes additional tag
bits to record a processor’s speculative read state. Eachspeculative store buffer, with L1 cache line sized entries,
collects all speculative heap writes made by a processor.
Dropping a L1 cache line with speculative state or
overflowing a store buffer forces a speculatively executing
thread to stall until reads or writes can be performed safely(when the thread becomes the non-speculative “head”
thread).

(bits 10:5 for ST)(bits 13:5 for LD)

Time
0
5
10
15
20
25
30
35
40
45
50

shortest arc and limits parallelism between the threads.

(bits 31:11 for ST)(bits 31:14 for LD)

4.2.1 Load dependency analysis. The load dependency
analysis looks for inter-thread dependencies for a STL, as
illustrated in Figure 3. A store timestamp is recorded on amemory or local variable store, and retrieved on asubsequent load to the same address. The store timestamp
is checked against thread start timestamps to determine if
an inter-thread dependency arc exists to the previous
thread (t-1), or an earlier thread (< t-1). If an inter-threaddependency arc is detected, the arc length, the difference
between the current time and the store timestamp, isrecorded.
While many dependency arcs may exist
between any two given speculative threads, we only record
the critical arc (dark arrows in figure), which is the

(d)
0
“
“
“
“
25
“
“
“
“
“

(e)

(f)

(g)

(h)

Y
N
N
Y
Y

0
1
1
1
2
0
1
2
2
2
2

0
0
1
1
1
0
0
0
1
1
1

0
0
0
0
0
0
0
0
0
0
0

Figure 4 – Illustration of the speculative state overflow analysis. Thread start time (column d) and counters (columns f & g)
are reset for every new thread. Arrows show conditions that cause counters to be incremented.

base_speedup =spec_time=

speedup

=



4



critical_arc_freq t • 
t = all_prev_threads
avg_thread_size avg_thread_size − avg_critical_arc_distance
t






avg_critical_arc_distance t
avg_thread_size

3
> 
4






avg_critical_arc_distance t
3
<= 
avg_thread_size
4(startup _ and _ shutdown _ overhead • # entries + orig _ time + eoi _ overhead • # threads) •  overflow_freq +1 − overflow _ freq 
base_speedup orig _ time
spec _ time∑

Equation 1 – Estimated speedup for a STL.

An example of the overflow analysis on a set of STL
memory references is shown in Figure 4. The speculative
state overflow analysis relies on timestamps associatedwith cache lines. A cache line timestamp and cache line
tag is recorded for the cache line a heap load or store
would have hit. Subsequent memory accesses check for apreviously recorded cache line timestamp with a matchingcache line tag (columns a & b). If no timestamp exists or
if it is less than the current thread start timestamp of a STL(column e), counters tracking buffer requirements are
incremented to reflect new buffer state required by thecurrent thread. The load counter (column f) tracks new
speculatively read cache lines, and the store counter(column g) tracks new store buffer entries. The overflow
counter (column h) is incremented if either counter for thecurrent thread exceeds buffer limits.

4.3. Selecting Thread Decompositions
The statistics shown in Figure 3 and Figure 4 areaccumulated over time and analyzed to predict theperformance of a STL. The estimated speedup for a STL,
shown in Equation 1, is derived from average critical arc
frequencies, thread sizes, critical arc lengths, overflow
frequencies, and speculative overheads.
Speedup is limited to four in Hydra (or total number ofprocessors in the CMP). Note that we expect maximal
speedup if the average critical arc length is at least ¾ theaverage thread size (or (p-1)/p where p is the number ofprocessors). This is the point at which the processors arecompletely utilized and the inter-thread dependencies are
separated enough not to limit speedup.
There are multiple possible decompositions that can bechosen in a loop nest. For example, in Figure 3, either theouter loop or the inner loop can be transformed into
speculative threads, but not both at the same time. We
select the best STL by comparing the estimated execution
time using speculative threads for a STL against theestimated execution time using speculative threads for any
nested STL decompositions instead, plus any nonspeculative serial execution, as shown in Equation 2.
Table 3 shows how this equation is applied to theexample loop in Figure 3.

timethis _ tsd
speedupthis _ tsd<> timethis _ tsd +
1
times • 
− 1speedups
s = nested _ tsd∑

Equation 2 – Comparison function for choosing an optimal
STLs.
Table 3 – Application of Equation 2 to the loops from
Figure 3 chooses the outer loop as the better STL.
Sequential time
(cycles)
Speedup
TLS time (cycles)
Total time (cycles)

Outer
loop
18941K

Inner
loop
13774K

1.85
10238K
10238K

1.30
10595K
15762K<

Serial
5167K
1.00
5167K

5. TEST Hardware Implementation
Simulations indicate program execution slows over
100x when profiling using a software-only implementationof the trace analyses described in Section 4.2. Overheads
result from callback annotations on every memory andlocal variable access, and comparisons required to resolveinter-thread dependencies and compute speculative state
requirements.
This magnitude of slowdown is
unacceptable in a real dynamic compilation system, even if
the analysis is only performed on a limited basis.
Furthermore, the significant software overheads introduce
imprecision into the analysis, making difficult to derive
accurate thread size and dependency arc lengths.
The overheads and imprecision of software-only
analysis led us to consider how hardware support could
speedup profiling and improve accuracy. The hardware
we designed analyzes a sequentially executing program
and works when speculation is disabled. Annotation
instructions inserted by the dynamic compiler (Section 5.1)
into native code mark important events. The annotation
instructions communicate events to the hardware
comparator banks that perform the actual trace analyses(Section 5.2). The speculative store buffers, which are idle
during sequential non-speculative execution, holdtimestamps of previous events (Section 5.3).

end of a STL (e.g. exit from a loop),
special routines read the collected
Instruction
Description
NormalTrace operation (when enabled)
statistics from TEST.
operation
Program execution slowdown
lw|lb|lbu|lh
Load
Load
Get memory access store timestamp and cachelhu|lwc1 addrline timestamp
resultsfromlocal
variable
Record memory access cache line timestamp
annotations and overheads to readsw|sb|sh|
Store
Store
Get previous cache line timestamp
collected statistics at the end of a
swc1 addr
Record memory access store timestamp andSTL, as shown in Figure 6. Several
cache line timestamp
lwl vnLocal
none
Get store timestamp for local variable vn
optimizations were performed byvariable load
the JIT compiler to reduce
swl vnLocal“
Record store timestamp for local variable vn
slowdowns of the annotated native
variable store
code. Only the first local variablesloop nStart loop“
Allocate comparator bank
Increment current bank pointerload in a block or a loop is
Set current thread start timestamp
annotated since it would result in
Reserve n local variable store timestamps
the shortest dependency arc, if one
eoi
Loop end-of“
Shift thread start timestamps for current bankexisted. Within loop nests, calls toiteration
Set current thread start timestamp for current
bankread collected statistics at the end of
eloop nEnd loop“
Free comparator banka STL are hoisted to the outer-mostDecrement current bank pointerloop when there is only one loop at
Free n local variable store timestamps
each level. After performing these
optimizations, most benchmarks
experience
no
more
than
10% slowdown, and only 2
int lcl_v = 10;li$s1, 101while( lcl_v > 0 ){sloop
1applications
have
slowdowns
approaching 25%.
if( call() != 0 ){loop_top:
Table 4. Summary of annotating instructions and associated operations.

lcl_v--;}
else{
this.val++;}}Original loop
1 Mark start of loop and allocate 1
local variable timestamp slot for
lcl_v.
2 Local variable annotations markaccesses to lcl_v.
3 lw and sw automaticallycommunicated to profiler.
4 Mark end of loop and free local
variable timestamp. Jump toroutine to read collected
statistics.

lwl
blez
jal
bnez
lwl
addi
2
swl
b
if_fail:
lw
addi
3
sw
loop_eoi:
eoibloop_exit:
eloop
4
jal

1
$s1, loop_exit
call$v0, if_fail1$s1, $s1, -1
1loop_eoi$t0, 8($s0)$t0, $t0, 1$t0, 8($s0)

loop_top1
read_statistics

Instrumented machine code

Figure 5 – A sample loop compiled with annotating
instructions.

5.1. Annotating Instructions
The annotating instructions, shown in Table 4 andFigure 5, mark events relevant to the trace analyses
described in Section 4.2. Memory load and store events
are automatically communicated to the tracing hardware
when tracing is enabled. sloop, eloop, and eoi
instructions mark the entry, exit and end-of-iteration of apotential STL. Local variables in the same calling context
as a potential STL are tracked with explicit annotations tosimplify tracking of named variables that move between
registers and the runtime stack in optimized compiled
code.
Block-local and temporary variables are notannotated because they never cause a dependency. At the

5.2. Comparator Array
The comparator banks carry out the bulk of thedependency and overflow trace analyses. One comparator
bank, shown in Figure 7, tracks the progress for a given
STL. Each bank, primarily composed of comparators andcounters, analyzes incoming loads and stores. An array ofcomparator banks allows us to trace multiple potential
STLs executing concurrently, as would be the case whenanalyzing nested loops. Comparators are used to compare
thread start timestamps against incoming cache line
timestamps to check for speculative state overflows andagainst store timestamps to identify critical arcs. At theend of each thread of a STL, arc lengths, critical arc
counts, and buffer overflows are accumulated into
counters.
In a real implementation of TEST with multiple banks,
logic in the critical arc calculation block can be shared
between banks. A given load access can be a dependency
for only one STL. For example, in a nested loop, a load
dependency may exist to a previous iteration in the current
loop or iteration in an enclosing loop, but not to both.
Consequentially, only one critical arc calculation block in
an array of comparator banks will be active for a given
load access. To share this block, the critical arc
calculation block is pipelined after dependency arc
identification, as shown in Figure 8a.
Multiple comparator banks are assigned in loop nests
when multiple potential STLs execute concurrently. The
finite number of comparator banks restricts the number ofloops in a loop nest that can be analyzed concurrently.
Several mechanisms help ensure the banks are still appliedcollected to predict behavior for a
STL, the annotations marking it
can be disabled dynamically (e.g.
overwriting JIT compiled code50%
with nop instructions). This
ensures the system can eventually
collect
informationon25%
decompositions deep within aloop nest.
Pipelining access to the0%
critical arc calculation block alsoenables TEST to provide detailed
dependency information that canbe used for optimization. In an
Integer
Floating
point
Multimedia
Benchm ark
extended implementation of
Read Counters
Locals Annotations
TEST, the registers and countersin the critical arc calculation
Figure 6 – Execution slowdown during profiling of benchmarks. For each application,
block are replaced with accesses
the 1st column is base annotations and the 2nd column is optimized annotations.
to content addressable SRAM, aseffectively. Precedence is initially given to the outer-mostshown in Figure 8b. This configuration allows critical arc
loop, and analysis of deeply nested loops is disabled whenlengths, accumulated critical arc lengths, and critical arc
there are no comparator banks left or no room left for local
counts to be binned by the load instruction PC to be later
variable timestamps (see sloop and eloop in Table 4).
analyzed by a programmer or compiler.
When a comparator bank consistently predicts speculative
We estimated how much logic would be consumed bybuffer overflows for an outer STL, it can be freed to be
an implementation of TEST. Transistor counts wereused deeper in a loop nest. When sufficient data has been
LD access time
ST access time

Cache line
timestamps(2kB, direct map)

1

Local var store
timestamps(2kB, 64 lines)

Memory store timestamps(6kB, 192 line FIFO)

mp3

mpegVid

Index by address

encJpeg

h263decshallow

decJpegmoldynNeuralNet

LuFactor

fft

FourierTest

euler

raytracemonteCarlo

NumHeapSort

MipsSimulator

jess

jLex

IDEA

Huffman

EmFloatPnt

db

deltaBlue

BitOpscompress

Assignment

Slowdown

75%

Key

>?

Comparator: (bottom) = (top) > (right) ?

register

Register: load (top) if (right); (bottom) = current value

counterCounter: add +1 if (left); reset to 0 if (right); bottom =current value
ALU: (bottom) = (top1) + (top2)

Last line LD

Last line ST

Speculation store buffers
Last ST timestamp-

thread start timestamp (t)thread start timestamp (t)

>? >?

>?
# loaded cache lines

max # load
lines

>

critical arc length (<t-1)>?

critical arc length (t-1)

thread start timestamp (t-1)>?

>?

thread start timestamp (0)>Buffer overflow
detection2# overflows# threads

>?

4

>0

>0
accum. arc length (<t-1)

accum. arc length (t-1)# critical arcs (<t-1)# critical arcs (t-1)

Dependency arc
identification

max #store lines

Critical arc calculation# stored cache lines3

One (of multiple) STL comparator banks
Enter STL
5
Start new thread
1

Event timestamps are held in store buffers
for later retrieval.

32Store timestamps are compared against
thread start timestamps to identify adependency arc (Section 4.2.1).

This logic examines cache line timestamps
for buffer overflows (Section 4.2.2).

4

Determines if a dependency arc is a criticalarc (Section 4.2.1).

5

Reset appropriate counters on STL entries
and on new threads

Figure 7 – Block diagram of one comparator bank.

CycleIncoming
LD/ST

~1

~2

~3

Store buffer
accessDependency arc
identification

Critical arc
calculation

Store buffer
access

Buffer overflow
detection

6. Benchmark Analysis

Load dependency
analysis6.1. Benchmark Results

Speculative state
overflow analysis

(a)
Cycle

Incoming
LD/ST

~1

~2

~3

~4

~5

Store buffer
accessDependency arc
identification

CAM/SRAM
read

Critical arc
calculation

CAM/SRAM
write

Store buffer
access

Buffer overflow
detection

Load dependency
analysis
Speculative state
overflow analysis(b)

Figure 8 – Comparator bank (a) base pipeline design (b) extended
pipeline design.
Table 5 – Transistor count estimates Hydra with TLS and TEST
support.
Transistors
Total

Structure

Count

Each

CPU + FP core

4
4
1
5
8

2500K
1573K
98304K
172K
39K

16kB I / 16kB D Cache

2MB L2 cache
Write buffer
Comparator bankTotal

10000K
6291K
98304K
861K
322K
115778K

% of
total
8.64%
5.43%
84.91%
0.74%
0.28%
100.00%derived from the logic required for a implementation witheight comparators eight. As Table 5 suggests, TEST
hardware would add less than 1% to the transistor count of
the Hydra CMP with TLS support.

5.3. Store Buffers
The five store buffers (see [15] for an explanation of
why there are five) that normally hold writes during
speculative execution hold timestamps during profiling.
Each store buffer is 2KB (64 32B cache lines). The store
buffers are statically partitioned, with three buffers holding
heap access store timestamps, one holding cache line
timestamps, and one holding store timestamps to local
variables. An address’ timestamp is returned whenrequested by an annotating memory or local variable
instruction.
Store timestamps in the store buffers, organized as
FIFO (first-in, first-out) during tracing, effectively hold alimited history of memory and local variable accesses. For
heap access store timestamps, 192 cache lines, or 6KB, ofwrite history can be held.
To keep logic additions for the speculative state
overflow analysis simple, the lower bits of an address
index the store buffer holding cache line timestamps andcache line tags like a direct mapped cache. The actual
speculation store buffers are fully associative and the L1
caches are 4-way set associative. Not accounting for
associativity introduces some error into the overflow
analysis, but should not affect its usefulness in estimating
speculative state requirements.

Table 6 lists benchmarks we have evaluated using
TEST, including applications from the jBYTEmark(http://www.byte.com/),
SPECjvm98(http://www.specbench.org/),andJava
Grande(http://www.epcc.ed.ac.uk/javagrande/javag.html)
benchmarks suites. The columns on the right of this graphsummarize the characteristics of the STLs chosen by
TEST. Figure 10 shows graphically the coverage andexpected speedups of selected STLs.
Overall, the selected STLs exhibit significant thread
size (column h) and coverage diversity. MipsSimulator,
raytrace, IDEA, EmFloatPnt and FourierTest have very
coarse threads while moldyn and NeuralNet have veryfine-grained threads. Ignoring inter-thread dependencies,
analysis of the selected STLs suggest that the thread size
is primarily constrained by the limited store buffer size
rather than the speculative load state in the L1 cache lines.
While many 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 (column e) than shownin the table, but the omitted decompositions do not haveany significant coverage (< 0.5%). mp3, db, jess, and jLex
have significant sections of serial execution not covered byany potential STLs, limiting total speedup for theseapplications.
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 a thirdof the benchmarks can be analyzed by a traditional
parallelizing compiler (column a) (e.g. programs that
resemble Fortran floating point code w/ affine array
accesses, no dynamic objects/pointers, bounded loops, andlittle control flow). The average height of selected loops
from the inner loop (column f) suggests that desired STLs
have granularities larger than the inner-most loop in a loop
nest. The maximum depth of loop nests executed (columnd) indicates that eight comparator banks are sufficient toanalyze most of the benchmark programs without
intervention from the runtime system.
Apart from simplifying parallelization of floating point
programs for a CMP and automatically selecting STLs in
integer applications that are difficult to analyze statically,
our experiments suggests that dynamic parallelization hasother potential benefits. One advantage is that STL
selections can be made that account for input data set sizes.
We noticed several applications where selecteddecompositions can change according to input data sizes(column b). In these benchmarks, multiple levels ofparallelism exist in key loops. Assignment, NeuralNet,
LUFactor, euler, and shallow use a nested loop to traverse

Table 6 – Benchmarks evaluated with STLs selected by TEST.

Thread size (cycles)

35x8x8256x256

Threads / STL entry

101x101

Avg. selected loop
height33x9
1024.

Selected loops (>0.5%
coverage)

Image decoder
Image compression
Video decoder
Video decoder
mp3 decoder

5000.

Loop depth

Fluid dynamics
Fast fourier transform
Fourier coefficients
LU factorization
Molecular dynamics
Neural net
Shallow water sim

51x51

Loop countResource allocation
Bit array operations
Compression
Database
Constraint solver
FP emulation
Compression
Encryption
Expert system
Lexical analyzer gen
CPU simulator
Monte carlo sim
Heap sort
Raytracer(h)Data set sensitive

Description(d)TEST Analysis
(e)
(f)
(g)

Analyzable forparallelism

BenchmarkInteger
Assignment
BitOpscompressdb
deltaBlue
EmFloatPnt
Huffman
IDEA
jess
jLex
MipsSimulatormonteCarlo
NumHeapSort
raytrace
Floating point
euler
fft
FourierTest
LuFactor
moldynNeuralNet
shallow
Multimedia
decJpeg
encJpeg
h263dec
mpegVideo
mp3

Data set

Category

Characteristics
(a)
(b)
(c)

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

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

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

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

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

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

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

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

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

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

2-dimensional data arrays. For these programs, loops
lower in a loop nest must be chosen with larger data sets
because the number of inner loop iterations will rise,increasing the probability of overflowing speculative state
when speculating higher in a loop nest. Choosing STLs
dynamically also allows selected STLs to change as CMP
designs evolve. For example, larger STLs that would
cause speculative buffer overflows in our current system
could be chosen during runtime by a future Hydra design
with larger speculative store buffers and L1 caches.

6.2. Imprecision Effects
Each benchmark was run speculatively on Hydra using
the STLs selected by TEST. Figure 11 shows our analysis
does a good job of predicting speculative performance. A
comparison of speculative performance and results fromTEST suggests disparity results mostly from selected STLs
with highly varying thread sizes and large violation rates
during actual speculative execution. One should keep inmind, though, that relative speedup estimates to otherpotential STLs are more important. The primarily role of
TEST is to identify the best STLs, so absolute values are
not critical.

Precision is lost
during the accumulation
and binning of thread
statistics.
With ouralgorithm,
temporaldependency information
is lost that could detect
multi-iteration
parallelism, as illustrated
in Figure 9. In nonconstant sized loops orin loops where work
increases or decreases
monotonicallybyiteration, accumulating
statistics for a STL
averages thread sizes
and dependency arc
lengths, hiding perthread variance or linearchanges in these values.
Finally, the limited
history of heap accessstore timestamps andcollecting dependency
statistics in only twobins (t-1 and < t-1) limit
the analysis’ accuracyondistant
threaddependencies.

for( i=0; i < limit; i++ ){if( i % n != 0){
A[i] = A[i-1];}}
Figure 9 –TEST analysis may incorrectly conclude this loop
to be non-parallel. Parallelism exists at every nth iteration,
but the count of dependencies to the previous iteration ishigh.

In practice, the lost precision does not appear to
decrease TEST’s ability to identify good STLs. Parallel
loops with complex dependencies that might fool TEST
analysis were not found in any critical regions of thebenchmark programs. While many of the benchmarks,
particularly the integer programs (e.g. MipsSimulator,
Huffman, db and NumHeapSort), exhibit STLs with highly
varying thread sizes and dependency arc lengths, this did
not affect our ability to identify the best decomposition.
The accuracy of distant thread dependencies was also not
critical. For floating point applications, parallelism existed
at many levels and granularities, and selecteddecompositions were mostly limited by speculative buffer
limits. In integer applications, we found that available

Normalized execution time

1.00

0.75

0.50

0.25

Benchm ark

Integer

NeuralNet U
Pshallow O
P
decJpeg O
P
encJpeg OP
h263dec O
P
mpegVideo O
P
mp3 O
P

FourierTest O
P
LuFactor O
Pmoldyn O
P

raytrace O
P
euler OP
fft O
PMipsSimulatorP
monteCarlo O
P
NumHeapSort
P

IDEA OP
jess OP
jLex OP

Assignment O
P
BitOps O
P
compress O
P
db O
PdeltaBlue O
P
EmFloatPnt OP
Huffman O
P

0.00

Floating point

Multimedia

Figure 10 – Graphical representation of selected STLs. The 1st column (O) is sequential execution and the 2nd column (P) is
predicted speculative execution. Each block in a column represents one STL and its contribution to execution time. The
bottom dark block represents non-parallelizable serial execution (if any).

parallelism was mostly determined by dependency
behavior to recent, not distant, past threads.

7. Conclusions
This paper describes Tracer for Extracting Speculative
Threads (TEST), a hardware tracer that analyzes potential
speculative-thread loops (STLs) in running Javaapplications. The proposed hardware requires minor
additions to our CMP with speculation support and incurs
only moderate slowdown of a program during analysis.
The results show that the proposed hardware can selectdecompositions that maximize speedup and parallel
coverage without exceeding speculative buffer limits. The
Java runtime system can then dynamically recompile
selected decompositions into speculative threads.
Using this approach, we can identify speculative
parallelism dynamically in integer and floating-point
applications. A traditional parallelizing compiler would be

6.3. Guiding Optimization

h263dec
mpegVideo
mp3

FourierTest
LuFactor
moldynNeuralNet
shallow
decJpeg
encJpeg

MipsSimulatormonteCarlo
NumHeapSort
raytrace
euler
fft

db
deltablue
EmFloatPnt
Huffman
IDEA
jess
jlex

Assignment
BitOpscompress

Normalized execution time

TEST generates statistics that aid compiler optimizationof selected STLs. The extended implementation of TEST
can bin STL dependencies according to the load PC (andconsequently, to specific program regions and variables).
Dependency critical arc lengths relative to the thread size
can also be collected. For frequently occurring criticalarcs significantly less than the size of the loop, thesestatistics direct the compiler to variables where optimized
placement of loads and stores can extend critical arcs
[30][10] or where synchronization can be inserted tominimize violations [22].
These statistics are also invaluable for speculative
programmer
optimizations
beyond that which can be
1.25
uncoveredbycompileranalysis or can be performed
1.00
safelybyautomatictransformations.
Feedback
0.75
from our simulations of TEST
has helped identify false
0.50
dependencies and aided the
optimizationofseveral0.25
benchmarks,
specifically
0.00
NumericSort, Huffman, db,
and MipsSimulator. In theseapplications, the statistics
quickly identified one or two
B enchmar k
critical dependencies that
Integer
Floating point
could be restructured or
Predicted
Actualremoved to expose parallelism
to the speculation hardware.
Figure 11 – Estimated speedup versus actual speedup.

Multimedia

challenged because of the difficulty of analyzing integer
programs statically, and profiling techniques without
hardware support would execute too slowly for run-time
analysis. Our experiences with the analyzer also suggest it
can enhance compilation by providing statistics to guide
speculative optimizations and by producing feedback to
aid programmers with optimizations that cannot be
performed automatically.

8. Acknowledgements[15] Hammond, L., Willey, M., and Olukotun, K. Data Speculation
Support for a Chip Multiprocessor. In ASPLOS’98, San Jose, CA,
October 1998.
[16] Jouppi, N. P. Improving direct-mapped cache performance by theaddition of a small fully-associative cache and prefetch buffers. In
ISCA-17, pp. 364-373, Seattle, WA, June 1990.
[17] Knobe, K. and Sarkar, V. Array SSA form and its use in
Parallelization. In POPL’98, San Diego, CA, January 1998.
[18] Ko, W. et al. Effective Cross-Platform, Multilevel Parallelism via
Dynamic Adaptive Execution. In 7th Workshop on High-Level
Parallel Programming Models and Supportive Environments. Ft.
Lauderdale, FL, April 2002.

This work was supported by DARPA Air ForceContract F29601-01-2-0085.

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

9. References[20] Marcuello, P. and Gonzalez, A.
Clustered Speculative
Multithreaded Processors. In ICS’99, Rhodes, Greece, June 1999.

[1]

Adve, V. S. et al. An integrated compilation and performance
analysis environment for data parallel programs. In SC‘95, San
Diego, CA, November 1995.

[21] Muchnick, S. Advanced Compiler Design Implementation. Morgan
Kaufmann Publishers, San Francisco, CA, 1997.

[2]

Adve, V. S. et al. High Performance Fortran Compilation
Techniques for Parallelizing Scientific Codes. In Supercomputing‘98. November 1998.

[3]

Allen, R and Kennedy, K. Optimizing Compilers for Modern
Architectures: A Dependence-based Approach. Morgan Kaufmann,
San Francisco, CA, 2001.

[4]

Artigas, P. et al.
Automatic Loop Transformations andParallelization for Java. In ICS’2000, Santa Fe, NM, May 2000.

[24] Wu, P. and Padua, D. Containers on the Parallelization of Generalpurpose Java Programs. In PACT’99, Newport Beach, CA, October
1999.

[5]

Blume, W. et al.
Polaris: Improving the Effectiveness ofParallelizing Compilers. In 7th Workshop on Languages andCompilers for Parallel Computing. Ithaca, NY, August 1994.

[25] Rauchwerger, L. and Padua, D. The LRPD Test: Speculative RunTime Parallelization of Loops with Privatization and Reduction
Parallelization. In SIGPLAN’95, La Jolla, CA, 1995.

[6]

Chaudhry et al. Space-Time Dimensional Computing for Java
Programs on the MAJC Architecture. In Java Microarchitectures,
Kluwer Academic Publishers, Boston, MA, April 2002.

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

[7]

Chen, M. and Olukotun, K. Exploiting Method-level Parallelism inSingle-threaded Java Programs. In PACT’98, Paris, France,
October 1998.

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

[8]

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

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

[9]

Cintra, M., Martinez, J. F., and Torrellas, J. Architectural Support
for Scalable Speculative Parallelization in Shared-Memory
Multiprocessors. In ISCA 27, Vancouver, BC, June 2000.

[29] Steffan, J. G. et al. A Scalable Approach to Thread-Level
Speculation. In ISCA-27, Vancouver, BC, June 2000.

[10] Cintra, M. and Torrellas, J. Eliminating Squashes ThroughLearning Cross-Thread Violations in Speculative Parallelization for
Multiprocessors. In HPCA 2002, Anaheim, CA, February 2002.
[11] Gopal, S. et al. Speculative Versioning Cache. In HPCA-4, Las
Vegas, NV, February 1998.
[12] Gupta, M and Nim, R. Techniques for Speculative Run-Time
Parallelization of Loops. In SC’98, November 1998.
[13] Hall, M. W. et al. Experiences using the ParaScope Editor: an
interactive parallel programming tool. In PpoPP’93, pages 33-43,
May 1993.
[14] Hall, M. W. et al. Maximizing Multiprocessor Performance with
the SUIF Compiler. In IEEE Compuer, December 1996.

[22] 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.
[23] Oplinger, J. T., Heiner, D. L., and Lam, M. S. In Search ofSpeculative Thread-Level Parallelism. In PACT’99, Newport
Beach, CA, October 1999.

[30] Steffan, J. G. et al. Improving Value Communication for ThreadLevel Speculation. In HPCA’02, Cambridge, MA, February 2-6,
2002.
[31] Tremblay, M. MAJC: Microprocessor Architecture for Java
Computing. In HotChips’99, Stanford, CA, August 1999.
[32] Vijaykumar, T. N. and Sohi, G. S. Task Selection for a Multiscalar
Processor. In MICRO’98, Chicago, IL, August 10-13, 1998.
[33] Wolfe, M. J. High Performance Compilers for Parallel Computing.
Addison-Wesley, Redwood City, CA, 1996.
[34] Zhai, A. et al.
Compiler Optimization of Scalar Value
Communication Between Speculative Threads. In ASPLOS’02,
San Jose, CA, October, 2002.