Using Thread-Level Speculation
to Simplify Manual Parallelization
Manohar K. Prabhu

Kunle Olukotun

Stanford University
Computer Systems Laboratory
Stanford, California 94305

Stanford University
Computer Systems Laboratory
Stanford, California 94305

mkprabhu@stanford.edu

kunle@stanford.edu

ABSTRACTIn this paper, we provide examples of how thread-level
speculation (TLS) simplifies manual parallelization and enhances
its performance.
A number of techniques for manual
parallelization using TLS are presented and results are provided
that indicate the performance contribution of each technique onseven SPEC CPU2000 benchmark applications. We also provide
indications of the programming effort required to parallelize eachbenchmark. TLS parallelization yielded a 110% speedup on ourfour floating point applications and a 70% speedup on our three
integer applications, while requiring only approximately 80
programmer hours and 150 lines of non-template code perapplication.
These results support the idea that manual
parallelization using TLS is an efficient way to extract fine-grain
thread-level parallelism.

Categories and Subject Descriptors
D.1.3 [Programming Techniques]: Concurrent Programming –parallel programming; D.2.2 [Software Engineering]: Design
Tools and Techniques; C.1.2 [Processor Architectures]:Multiple Data Stream Architectures (Multiprocessors) – multipleinstruction-stream, multiple-data-stream processors (MIMD);
C.1.4 [Processor Architectures]: Parallel Architectures.

General Terms
Design, Algorithms, Performance, Measurement.

Keywords
Chip multiprocessor, data speculation, manual parallel
programming, multithreading, feedback-driven optimization.

1. BACKGROUND
As the number of transistors that can fit within a die hasgrown according to Moore’s Law, computer hardware has grownin complexity. While hardware can rapidly evolve, operating
systems and software must vary more slowly for a number of
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. To copy
otherwise, or republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.
PPoPP’03, June 11-13, 2003, San Diego, California, USA.
Copyright 2003 ACM 1-58113-588-2/03/0006…$5.00.

reasons. First, successful computer architectures support a largebase of legacy applications, which are difficult to port to new
platforms. Additionally, programmers become familiar with a few
standard languages and hardware interfaces and seldom want tomigrate to new ones. Finally, the efficient development ofapplications often requires complex code development tools, andthe creation or purchase of these tools can be a significant barrier
to entry for innovative hardware platforms.
As a result, often most applications do not utilize the newest
features of a hardware platform. For example, multiprocessor
computers are becoming increasingly common, with even someconsumer desktop systems utilizing dual processors. However,few applications currently make efficient use of multiple
processors to enhance single application performance. Rather,processors are assigned to separate applications, resulting in
suboptimal single application performance and frequent processor
idle cycles from having too few applications available to execute.
The primary problem is that creating parallelized versions oflegacy code is difficult. Even with a good tool chain including
profilers and parallelizing compilers [1][2][9][11], automatedparallelization has proven to be a very difficult problem [19].
While successful for certain scientific applications, automatedparallelization has typically provided poor parallel performanceon general-purpose applications, especially integer ones. Manual
parallelization can provide good performance on a much wider
range of applications, but typically requires a different initialprogram design and programmers with additional skills. Parallel
programs require data structures and algorithms intended forparallel processing. Data placement and data replication must be
considered more extensively to minimize interprocessor access
contention and latency. Likewise, algorithms must be designed toallow concurrent and synchronized accesses without data races ordata access hot spots. For example, single counters may need tobe replaced with distributed counters, and multiple entry points
may need to be added to linked lists that would have performed
well with only a single entry point in a uniprocessor algorithm.
In this paper we show that the use of thread-level speculation(TLS) for manual parallelization, along with only minimal
additional support in the software development tool chain, canprovide much of the ease of automated parallelization. At thesame time, it achieves the high performance and broad
applicability characteristic of conventional (non-TLS) manual
parallelization. In conventional manual parallelization, softwaredevelopment is best targeted to a parallel platform from the start.
Otherwise, extensive redesign of applications to use explicitlyFigure 1. Thread-level speculation
parallel data structures and algorithms is often required. In
contrast, we demonstrate large parallel speedups on a diverse setof uniprocessor applications, while changing or adding very few
lines of code. With TLS-driven manual parallelization almost allof the application design is done for a uniprocessor target, andonly a small effort is required at the end to transform theapplication into a high-performance parallel application. This
simple transformation to parallel code is possible because TLS
automatically detects and prevents data races, one of the main
hazards that makes conventional manual parallelization so
difficult. In this way, manual parallelization with TLS provides
programmers with a new and incremental approach toincorporating parallel performance into legacy applications.
The rest of this paper is organized as follows. In the next
section we will explain TLS, our architecture and the benchmarks
we chose to parallelize. In Section 3, we discuss two simple
examples of code containing thread-level parallelism (TLP), toshow the simplicity and performance advantages of applying TLS
to manual parallelization, rather than using conventional non-TLS
manual parallelization. We also use these examples to introduce
some useful source code transformations that allow TLS to extract
TLP from many types of code that exhibit parallelism. Section 4
focuses upon the results of parallelizing the benchmarks. Section
5 frames the current research within the context of previous work,
and Section 6 presents our conclusions.

2. TLS AND THE TEST PLATFORM
This section begins with an explanation of the theory andmechanisms of thread-level speculation (TLS). Next it discusses
the specific TLS implementation simulated in our experiments.
Finally, it describes our simulator and compilation environment.
TLS is the process of speculatively executing interdependent
threads out-of-order, while appearing to have executed them inorder. In this paper, the threads will be formed by splitting the
dynamic execution path of a single-threaded application into
multiple ordered threads. A loop in a single-threaded application
is a common place to create TLS threads, one for each iteration of
the loop body, as shown in Figure 1. Because each TLS thread isa portion of the dynamic execution path of the original single
thread, the TLS threads are both interdependent and also orderedaccording to their order in the original single-threaded
application. To enforce correctness, hardware must make eachthread appear to have executed sequentially in the original order.

In a typical TLS system [7][13][17][21], several consecutive
threads are executing at any moment. The first in order isnonspeculative; the rest are speculatively executing ahead in time.
When the nonspeculative thread completes, the next thread inorder becomes nonspeculative. Speculative reads and writes arehandled specially. Each speculative thread must have its writes
buffered until the time that it becomes nonspeculative, at whichtime it commits the writes. Additionally, speculative threads mustensure that any values that they read include the effects of writes
stored in buffers of less speculative threads, but not writes from
more speculative threads. For example, if a speculative thread
creates and buffers a new value that a more speculative thread
subsequently reads, the new value must be forwarded to the more
speculative thread (Case j in Figure 1). On the other hand, if a
new value is created, but the old value has already been used by amore speculative thread, that thread and all threads following it
must discard their results and restart execution with the new,correct value (Case k). This is known as a data dependence
violation, and, as shown in Figure 1, the cost of discarded
execution time plus the thread restart overhead can waste time andcause large performance losses. Hence, reducing violations isimportant in any code with frequent inter-thread dependences.
The TLS hardware implementation used for this paper is the
Stanford Hydra chip multiprocessor (CMP). This CMP comprises
four pipelined MIPS-based R3000 processor cores, each withprivate L1 instruction and data caches (Figure 2). The four
processors share an on-chip, unified L2 write-back cache, andeach processor executes a single thread. Each processor’s L1 data
cache is write-through, and the other processors snoop the bus
connecting the processors and the L2 cache to permit data
dependence violation detection. Dependences are tracked on aCentralized Bus Arbitration Mechanisms

CPU 0
L1 I$

CPU 1

CP2

L1 D$ + SpecCPU 0 Mem Control

L1 I$

CP2

L1 D$ + SpecCPU 1 Mem Control

CPU 2
L1 I$

CPU 3

CP2

L1 D$ + Spec

L1 I$

CPU 2 Mem Control

CP2

L1 D$ + SpecCPU 3 Mem Control

Write-through Bus (32b)#0Speculation Write Buffers#1#2#3
retireRead/Replace Bus (128b)
DMA

On-chip L2 Cache

SDRAM Memory Interface

I/O Bus Interface

Main Memory

I/O Devices

Figure 2. Hydra chip multiprocessor

Table 1. Memory system specifications

Table 2. Loop-only TLS overheads

Memory system

Characteristic

L1 cacheL2 cache

Main memory

Separate
I & D SRAM
cache pairs foreach CPU
16 KB each

Shared,on-chip
SRAM cache

Off-chipDRAM

Bus width

32-bitconnection
to CPU

256-bit read bus
and32-bit write bus

Access time

1 CPU cycle

5 CPU cycles

Associativity
Line size

4-way
32 bytes
Writethrough,no write
allocate

4-way
64 bytes
Writeback,allocate on
writesInclusion
enforced by L2
on L1 caches

Configuration
Capacity

Write policy
Inclusion

2 MB

N/A

256 MB
64-bit
SDRAM
at half ofCPU speed
At least
50 cycles
N/A
4 KB pages“Writeback”(virtualmemory)Includes allcached data

per-word basis, thereby eliminating almost all violations due tofalse sharing. Speculative result buffering is achieved bybuffering speculative writes to the L2 cache in a group of 32cache-line buffers, one for each processor. These buffers also
monitor read requests made to the L2 cache. This allows them toforward data created by writes from less speculative processors tosatisfy the requests of more speculative processors. Other
hardware in the L1 data caches enforces the TLS protocols, suchas the detection and processing of dependence violations. While
the CMP hardware follows a partial store ordering memory
consistency model, the TLS system causes the CMP to appear tothe programmer like a single out-of-order processor, so theprogrammer need not consider memory consistency issues.
Further details of this design can be found in Table 1 and [13].
The support for TLS is implemented in a combination of
hardware and software for ease of implementation andadaptability of the protocols, although this does increase thethread control overheads. Table 2 provides information on thesesoftware overheads. The first three can be statically analyzed, andoccur whenever a speculative loop is started or ended andwhenever iterations in a speculative loop are committed. The
remaining four overheads occur dynamically due to violations
detected on this CPU or on less speculative CPUs and due tostalls for speculative threads resulting from buffer constraints or
the handling of an exception. The TLS system allows speculation
A) Tree structure in memory
Node

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Address stored

A4

A2

A6

A1

A3

A0

A5

null

null

null

null

null

null

null

null

A4

Node 0(“form”)

B) Implicit structure

A2

A1C) Data elements in memory

Node 1(“has”)

Node 3(“tree”)

A3

null

null

null

Node 7

Node 8Node 9

A6

Node 4(“the”)

null

A0

null

Node 2(“here”)

Node 5(“the”)

null

A5

null

Node 6(“shown”)

null

Node 10 Node 11 Node 12 Node 13 Node 14

Figure 3. Organization of the heap array

A0

“the”

A1

“tree”

A2

“has”

A3

“the”

A4

“form”

A5“shown”

A6“here”

Software handler

Instruction
countStart loop
End of eachloop iteration
Finish loop
Violation: local
Violation: receive from another CPU
Hold: buffer fullHold: exception~30

Overheads forloop-only TLS
RegulareventsIrregular
events

12
~22
7
7
12
17 + OS

only on loops and at a single level, i.e. not speculation on a loop
nested within another speculative loop. The system could haveconducted procedural speculation via the use of different software
handlers [13], but loop-only speculation was chosen for its lower
overheads. As a result, the performance losses resulting from thespeculation software handler overheads are typically quite small.
To simulate this TLS system, a cycle-accurate, executiondriven simulator was used to execute all application instructions,
including the speculation software handlers. The simulator canaccurately model a realistic memory system, including the effectsof bus contention and memory access queuing. A perfect memory
model was also simulated to gauge the performance losses due tonot scaling the memory system with the number of processors
running in parallel. All performance measurements presented
here were done using applications compiled by GCC 2.7.2 with
optimization level -O2 on an SGI workstation running IRIX 5.3.

3. METHODS FOR USING TLS
In this section, we will use two simple examples to illustrate
many important points about how a programmer can use TLS toparallelize applications. First, we will show the ease of using TLS
versus conventional (non-TLS) manual parallelization. Second,
we will discuss the performance advantages of using even simple
TLS parallelization versus a thorough redesign of applications
using conventional parallelization. We will also show theperformance advantages of manual over purely automatic TLS
parallelization. Third, we will explain several types of sourcecode transformations that can expose more of the TLP inherent inapplications. Fourth, we will illustrate the very different codedevelopment cycle experienced by a manual TLS programmer.
A) Tree structure in memory
Node

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Previous address stored

A4

A2

A6

A1

A3

A0

A5

null

null

null

null

null

null

null

null

null

null

null

null

Step 1

A4

Final address stored

Step 2

A2

Step 3

A3

A6

A1

A2

Node 0(“has”)null

A0B) Implicit structure

A3

A1

null

null

Node 7

Node 8

null

null

A5

null

null

null

null

C) Data elements in memory

Node 1(“the”)

Node 3(“tree”)

Step 4

A6

A0

Node 4null

null

Node 2(“here”)

Node 5(“the”)

null

A5

null

Node 6(“shown”)

null

A0

“the”

A1

“tree”

A2

“has”

A3

“the”

A4

“form”

A5“shown”

A6“here”

Node 9 Node 10 Node 11 Node 12 Node 13 Node 14

Figure 4. Top node removal and update of the heap

3.1 Heap Sort Example
The first example is C code that implements the mainalgorithm for a heap sort. In this algorithm, an array of pointers todata elements is used to sort the elements. Encoded in memory asa simple linear array (Figure 3A), the node array is actuallyinterpreted as a balanced binary tree by the algorithm (Figure 3B).
Tree sibling nodes are recorded consecutively in the array, whilechild nodes are stored at indices approximately twice that of theirparents. For example, Node 2 is located directly after its sibling(Node 1) in the array, while Node 2’s children (Nodes 5 and 6)
are located adjacent to each other with indices approximately
twice that of Node 2. This structure allows a complete binary tree
to be recorded without requiring explicit pointers to connect
parent and child nodes together, because the tree structure canalways be determined arithmetically. In this example, each nodeof the tree consists of a single pointer to a variable-length data
element located elsewhere in memory (Figure 3C).
The heap is partially sorted. The element pointed to by any
parent is always less than the element pointed to by each of thechildren, so the first pointer always points to the smallest element.
Nodes are added to the bottom of the tree (highest indices) andbubble upwards, switching places with parents that point togreater valued elements. Final sorting is conducted by removing
the top node (first pointer) and iteratively filling the vacancy byselecting and moving up the child pointer that points to the lesser
1:2:#define COLWID (30)char *result, *node[];

3:
4:
5:
6:

void compileResults() {char *last, *inRes;
long cmpPt, oldCmpPt, cnt;
int sLen;

7:// INITIALIZATION
inRes = result; last = node[0]; cnt = 0;

8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

// OUTER LOOP - REMOVES ONE NODE EACH ITERATION
while (node[0]) {// IF NEW STRING, WRITE LAST STRING AND COUNT// TO RESULT STRING AND RESET COUNT
if (strcmp(node[cmpPt=0], last)) {strcpy(inRes, last);sLen = strlen(last);
memset(inRes+sLen, ' ', COLWID-sLen);inRes += sprintf(inRes+=COLWID,"%5ld\n",cnt);
cnt = 0;last = node[0];}cnt++;//INNER LOOP - UPDATE THE HEAP, REPLACE TOP NODE
while (node[oldCmpPt=cmpPt] != NULL) {cmpPt = cmpPt*2 + 2;
if (node[cmpPt-1] && !(node[cmpPt] &&strcmp(node[cmpPt-1], node[cmpPt]) >= 0))--cmpPt;
node[oldCmpPt] = node[cmpPt];}}// WRITE FINAL STRING AND COUNT TO RESULT STRING
25: strcpy(inRes, last);
26: sLen = strlen(last);
27: memset(inRes+sLen, ' ', COLWID-sLen);
28: sprintf(inRes+=COLWID, "%5ld\n", cnt);
29: }Figure 5. Code for top node removal and heap update

element (Figure 4). We will focus only on this final sorting,which typically dominates the execution time of heap sort.
The code is provided in Figure 5. It can be used to count the
number of appearances of each (linguistic) word in a passage oftext. It has been optimized for uniprocessor performance, so thatparallelization with TLS can only derive speedups due to true
parallelism and not due to more efficient code design. The code
processes the pre-constructed heap node[], where each node(e.g. node[3]) is a pointer to a string (line 2). As each top nodeis removed and replaced from the remaining heap, a count is keptof the number of instances of each string dereferenced by thenodes (line 17). Each string and its count are written into a(previously allocated) result string (line 2) at the position pointed
to by inRes (lines 9-16). To do this, the top node of the heap
(node[0], which points to the alphabetically first string) isremoved and compared to the string pointed to by the previous
top node removed (lines 8 and 9). If they point to dissimilar
strings, then all nodes pointing to the previous string have been
removed and counted, so the string and its count are written to theresult string and the count is reset (lines 9-16). In all cases, thecount for the current string is incremented (line 17) and the heap
is updated/sorted in the manner described above (lines 18-23).
The heap is structured so that below the last valid child on any
tree descent, the left and right child are always two NULL pointernodes (line 18). This whole counting and sorting process isconducted until the heap is empty (line 8). Then the results forthe last string are written to the result string (lines 25-28).

3.2 Parallelizing with TLS
When parallelizing with TLS, the programmer first looks forparts of the application with some or all of the following qualities.
These parts should dominate the execution time of the application
with that time concentrated in one or more loops, preferably witha number of iterations equal to or greater than the number ofprocessors in the TLS CMP. These loops should contain fairly
independent tasks (few inter-task data dependences), with eachtask requiring from 200 to 10,000 cycles to complete, and all tasks
being approximately equal in length for good load balancing. For
the example program, we see that the two loop levels where wecan parallelize this code are either the inner loop or the outerloop, i.e. within a single event of removing node[0] andupdating the heap (lines 8-24), or across multiple such events.
The first is not good due to the small parallel task sizes involved,
which are better targeted with techniques that exploit ILP. The
second level is much better suited to the per-iteration overheads of
the TLS system. But, parallelizing across multiple node removals
and heap updates requires each thread to synchronize the readingof any node (lines 8, 9, 15, 18, 20, 22) with the possible updatesof that node by the previous threads (line 22). The top node will
always require synchronization, while nodes at lower levels will
conflict across threads with a decreasing likelihood at each level.
This example can be parallelized using TLS simply bychoosing and specifying the correct loop to parallelize. In thisexample, changing line 8 to use the special keyword pwhilerather than while can be used with a fairly simple source-tosource translator to trigger the automatic generation of TLS
parallel code [13]. The translator performs several operations.
First, it analyses the loop to determine loop-carried dependences,i.e. dependences that span iteration boundaries. In this example,

these can occur for the variables node, last, inRes, and cnt,
and also for any access to data dereferenced from a pointer. Allvariables and accesses that can have loop-carried dependences
appear in boldface type in Figure 5. Then, it transforms the code
so that during every iteration the initial load from and the final
store to these variables or to dereferenced pointers occur from or
to memory, preventing the data from being register-allocatedacross iteration boundaries. By forcing data to memory, thetransformed source code ensures that the TLS system can detect
inter-thread data dependence violations. Meanwhile, all variables
without loop-carried dependences are made private to each thread
to prevent false sharing and violations. Additionally, for peak
performance, the source code is transformed to register-allocate
variables having loop-carried dependences in all places other than
the first load and the final store in each iteration.
This parallelized TLS code was executed upon a heap
comprising the approximately 7800 words in the U.S.
Constitution and its amendments. The TLS CMP provides a
speedup of 2.6 over a single-processor system with the same,
unscaled, realistic memory system. Very little of the difference
between the achieved speedup and a “perfect” speedup of 4 is due
to not scaling the memory system, as the speedup when both havea perfect memory system is only 2.7. Likewise, the requirementthat shared variables not be register-allocated causes only a 2%
slowdown, if the code is executed sequentially. This is what wecall the base TLS parallelization.

3.3 Ease of TLS Parallelization
The base case illustrates the simplicity of TLS programmingand the efficiency of its resultant programs, in contrast to thecomplexity and overheads of conventional parallelization. Like
TLS, conventional parallelization requires that loop-carried
dependences be identified. However, once this has been done, thedifficult part of conventional parallelization begins.
Accesses to any dereferenced pointer or variable with loopcarried dependences could cause data races between processors
executing different iterations in parallel. While synchronizationmust be considered for each access, to avoid poor performance
only accesses that could actually cause data races should be
synchronized with each other. However, determining whichaccesses conflict requires either a good understanding of thealgorithm and its use of pointers or a detailed understanding of thememory behavior of the algorithm. Pointer aliasing and control
flow dependences can make these difficult. Finally, a method forsynchronizing the accesses must be devised and implemented.
This typically requires changes in the data structures or algorithms
and must be carefully considered to provide good performance.
None of this is necessary when parallelizing with TLS.
In this example, one set of accesses that must be explicitly
synchronized when using conventional parallelization are the readaccesses of the nodes (lines 8, 9, 15, 18, 20, 22) with the possible
updates of those nodes by earlier iterations (line 22). To do this a
new array of locks could be added, one for each node in the heap.
However, this would introduce large overheads. Extra storage
would be required to store the locks. Each time a comparison ofchild nodes and an update of the parent node were to occur, an
additional locking and unlocking of the parent and testing of locks
for each of the child nodes would need to be done. Furthermore,
doing this correctly would require careful analysis. The orderingof these operations would be critical. For example, unlocking theparent before locking the child to be transferred to the parent node
would allow for race conditions between processors. Worse yet,these races would be challenging to correct because they would be
difficult to detect, to repeat and to understand.
One could attempt a different synchronization scheme tolower the overheads. For example, each processor could specify
the level of the heap that it is currently modifying, and processors
executing later iterations could be prevented from accessing nodes
at or below this level of the heap. While this would reduce thestorage requirements for the locks to just one per processor, it
would introduce unnecessary serialization between accesses tonodes in different branches of the heap. Another alternative
would be to have each processor specify only the node which is
being updated, so processors executing later iterations would stall
only on accesses to this node. But, locking overheads would still
exist in either case, and care would still need to be taken toprevent data races. Alternatively, the choice could be made tocompletely replace the uniprocessor heap sort with a newalgorithm designed for parallelism from the start. But, this would
likely be more complex than any solution discussed so far, and the
support for parallelism will still introduce overheads into any
algorithm that has inter-thread dependences. As this example
shows, parallelization without TLS can be much more complex
and error-prone than parallelization with TLS. Because thecomplexity of redesign versus incremental modification becomes
greater for larger, more complex programs, its simplicity is evenmore of a benefit for real-world applications.

3.4 Performance of TLS Parallelization
The base case also illustrates the second point of this section,that parallelization with TLS can often yield better performance
than parallelization without TLS [14]. This occurs for two
reasons. First, the hardware-assisted automatic detection andcorrection of dynamic dependence violations reduces
communication overheads. Furthermore, it is often possible tospeculate beyond potential dependences, eliminating all
synchronization stall time when the potential violations do not
actually occur. We call this optimistic parallelization. It can bemuch more efficient than the pessimistic static synchronization
used in conventional parallelization, which synchronizes on all
possible dependences, no matter how unlikely.
It is worth considering this point further. Very often, TLS
can improve the performance of an application that has alreadybeen manually parallelized by allowing some optimistic
parallelization [10]. Less apparent is that a single-threaded
application only incrementally modified using manual TLS
parallelization can sometimes provide better performance than anapplication that has been completely redesigned for optimal
parallel performance using only conventional manual
parallelization. This is because code optimized for non-TLS
parallel performance introduces overhead over uniprocessor codeto support low-contention parallel structures, algorithms andsynchronization. The advantage that results from this redesign forconventional parallelism can be less than the combined
advantages of using TLS and starting with more efficient, optimal
uniprocessor code. Given the difficulty of redesigning legacy
code and of parallel programming, this can make manualCompared to non-TLS parallel programming, parallelization
with TLS allows the programmer to more quickly transform a
portion of code. The key to this is that TLS provides the ability toeasily test the dynamic behavior of speculatively parallel code
(while it correctly executes in spite of dependence violations) andget specific information about the violations most affecting
performance. The programmer can then focus only on thoseviolations that most hamper performance, rather than being
required to synchronize each potentially violating dependence to
avoid introducing data races into the program.
Before discussing specific code transformations for
performance enhancement, we will summarize the generalapproach to reducing performance-limiting violations. Typicallyparallel performance is most severely impacted by a small numberof inter-thread data dependences. Moving the writes as early as
possible within the less speculative thread and the reads as late as
possible within the more speculative thread usually reduces the
chance of experiencing a data dependence violation. For loopbased TLS, this corresponds to moving performance-limiting
writes toward the top of the loop and delaying performancelimiting reads toward the end of the loop; in the limit, the firstload of a dependent variable occurs just prior to the last store,
forming a tiny critical region. Furthermore, moving this criticalregion as close as possible to the top of the loop minimizes theexecution discarded when violations do occur.
Finally,
constructing the loop body to ensure that the critical region
always occurs approximately the same number of cycles into the
execution of the loop and requires a fairly constant time tocomplete allows the speculative threads to follow each other witha fixed inter-thread delay without experiencing violations. In

We will now consider optimizations that can be done
automatically. More than three violations per committed thread
occur while executing the base parallelization. The store of lastin line 15 often violates the speculative read of last in line 9.
The same occurs with cnt (the store in line 17 violates the loadin line 13), inRes, and several other variables. To reduce these
violations, we can minimize the length of the critical regions fromfirst load to last store. For example, the store of last in line 15
can be moved right after the load in line 9. Because each thread
optimally executes with a lag of one-quarter iteration from theprevious thread on a four-processor CMP, this makes it unlikelythat any other thread will be concurrently executing the same
critical region. To hoist the store of last, the previous value
must first be saved in a temporary variable for lines 10 and 11.
Research shows that this transformation can be automated [19].
We can also move these critical regions as early in each thread as
possible For example, line 17 (the increment of cnt) can be
moved above the conditional block (lines 9-16). Automaticallydetermining and conducting this is complex [19]. However, we
will assume that automated parallelization can conduct all thesetransformations optimally to strengthen the argument that manual
TLS programming can still further improve performance.
When these transformations have been completed for all
variables that can benefit, surprisingly the performance remains
virtually unchanged. Upon inspecting the violation report, we seethat most of the lines which were causing violations before are nolonger significant sources of losses, but now previously
unimportant load-store violation pairs dominate performance by
causing much larger losses than before. Threads now progress
farther per violation, but nonetheless violate anyway before they
can successfully commit. This results in a lower violation count,but more discarded execution time per violation. This is shown in
Figure 6, which shows speedup results with real and perfectmemory systems and the number of violations per committed
thread, for each version of the example application.
Unfortunately, the performance at this point (a speedup of
2.6) represents an optimistic upper bound on the current
capability of automated TLS parallelization. We have optimallyused all the automated methods of which we are aware that can
Perfect memory system speedup

Real memory system speedup

Violations per thread (real memory)
400%

4.00

350%

3.50

300%

3.00

250%

2.50

200%

2.00

150%

1.50

100%

1.00

50%

0.50

.

First, a programmer conducts the base TLS parallelization, as
described above, and then executes the resultant code against a
representative data set. The TLS hardware is capable of reporting
instances of dependence violations, including data on which
processors were involved, the address of the violating data
element, which load and store pairs triggered the violation, andhow much speculative work was discarded. This data is thensorted by each load-store violation pair. By totaling the cycles
discarded for each pair and sorting the pairs by these totals, thecauses of the largest losses can be known. Using this ranking, a
programmer can better understand the dynamic behavior of theparallel program and more easily reduce violation losses.

3.6 Automatic Optimization

0%

0.00

Base

Load-store
movement

Complex value
Delayed non- Alternating branchprediction
violating execution
descent

Figure 6. Performance of incremental optimizations

Violations per thread

We will now cover a variety of methods for achieving better
TLS parallel performance. This will allow us to focus on threemain points: 1) introducing the reader to the process of parallel
programming using TLS, which is substantially different fromconventional parallel programming; 2) demonstrating several
categories of source code transformations that allow extraction of
more of the inherent TLP from applications; and 3) indicating
situations in which a minor manual adjustment can substantiallyoutperform the automatic base parallelization. We will show how
the programmer can detect and understand sources of performanceloss and use this to conduct incremental changes to the original
source code to improve performance. This process is repeateduntil no further TLP can be exposed to the TLS hardware.

.

3.5 Optimizing TLS Performance

contrast, critical sections that occur sometimes early andsometimes late increase violations due to late stores in lessspeculative threads violating early reads in more speculative ones.

Speedupparallelization with TLS a better alternative than application
redesign using conventional manual parallelization.

benefit this example. However, manual TLS parallelization can
provide still more speedup (a final speedup of 3.4) with aminimum of code transformation. This is because a programmer
can do more complex value prediction than an automatedparallelizer. Also, automated parallelization is constrained toallow only transformations that appear to preserve the original
execution ordering and data structures, even if a minor, obvious
change in them could enhance performance. This arises because
the original program was targeted to a uniprocessor, where data
contention or value prediction was never an issue, so often a small
and obvious change can lessen contention or reduce dependences.
The techniques to be discussed below require an increasingly
detailed understanding of the application. However, it should be
noted again that these performance optimizations are optional andfor improved performance only. Unlike conventional manual
parallelization, TLS programming does not require a thoroughunderstanding of the application to ensure correctness.

3.7 Complex Value Prediction
In the current example, one of the main variables suffering
violations is inRes. Complex value prediction can reduce these
violations. Note that the result string is constructed out of fixedwidth columns. The first column is COLWID characters wide andcontains the word (lines 10-12). The next column is fivecharacters wide and contains the final count of the number of
instances of the string, followed by a carriage return (line 13).
From the code a programmer can determine that the final value ofinRes will always be COLWID+5+1 characters greater after line
13 than it was in line 10, but an automated parallelizer would
have difficulty deciphering this. Using this prediction of the final
value of inRes, the programmer is able to hoist the final updateof inRes above the many function calls in lines 10-13, once
again reducing both the chance of a violation occurring and theexecution time discarded if a violation does occur.
This violation could perhaps be alleviated automaticallyusing a combination of profiling, violation tracking and a stride
predictor. A more challenging example would be if the count of
instances were printed to a variable, rather than fixed, length field.
Complex value prediction could quickly determine the final valueof inRes based upon the number of digits used to print cnt, but
this would be difficult to do automatically using a stride predictor.
Likewise, if the count had been printed to a variable-length
field, the programmer could have chosen to change the format to a
fixed length to allow for complex value prediction. This could
occur if the output format was not critical and could tolerate achange. If so, this would also show how a small change in thealgorithm and data structures can allow further optimization on a
program exhibiting contention due to its having been designed
without parallel execution in mind. This change would not
generally be allowed for an automatic parallelizer.

3.8 Algorithm Adjustments
By this point almost all loads and stores to the same variable
are placed close to each other and close to the top of each
iteration, and yet the performance has not improved significantly.
Upon closer examination, we see that many of the violations
would never occur if each thread did not execute lines 9-16 and if
it maintained a spacing of one quarter iteration from the threads

immediately previous to and following it. The problem is thatwhen lines 9-16 are executed, a large number of cycles are
consumed to store a word and its count to the result string. Only
after completing this, the thread updates the top of the heap (line22). This violates all more speculative processors, due to the loadin line 8, and causes them to discard all their execution during thetime the result string was being updated. While conducting an
early update on the top node of the heap could yield some benefit,
nodes further down would still likely cause violations.
The optimization to alleviate this problem is to move as
much of the execution in lines 9-16 to the position following line
23. By minimizing the work conducted before lines 17-23, we
can reduce or eliminate many of the violations. In particular, only
the updates of data locations with loop-carried dependences
should occur before line 17, i.e. updates to inRes, last andcnt. The strcpy, strlen, memset and sprintf functions
can be conducted later, after lines 17-23, without causing
violations. This is similar to moving load-store pairs closer to thestart of each iteration, but instead we are making algorithm
changes to move non-violating work closer to the end of each
iteration. Specifically, we are moving these four functions frombefore to after the heap update, which repeatedly dereferences
dynamically determined pointers. It may be obvious to theprogrammer that resultString and the heap are neverintended to have intersecting addresses; hence no violations
should occur. However, it appears the compiler would need to
conduct either an advanced general analysis or an analysis quite
specific to this situation to assert this non-intersection in all cases.
Therefore, this is a change in algorithms that may not be possible
for an automated compiler to conduct. As Figure 6 shows, thisoptimization greatly improves performance, raising the speedupfrom 2.6 to 3.2 and also halving the number of violations.
After this optimization, we observe that the dominantremaining violations are the loads in line 20 with the store in line
22. We observe that this is in part due to the fact that when thetwo child nodes point to equal strings (a common occurrence atthe top of the heap), the second (right, higher-index) node isalways selected. This leads to frequent contention for all nodes
near the top of the heap and resultant violations, as each thread
descends down the same path through the heap.
We can easily change the algorithm so that each speculative
thread chooses the opposite direction from the thread immediately
before it. Consecutive threads will alternate between always
selecting the left or always selecting the right node in cases of
equality, thereby descending down the opposite path from theimmediately previous thread. Again, a parallelizing compiler
could not make this change, because it alters the behavior of the
program, even though in this case the program will still produce
exactly the same final result string. This final optimization resultsin slightly improved performance and less frequent violations.
Note that including all the transformations so far would yield a
4% slowdown if the code were executed on a uniprocessor.
Hence, a perfect, linear speedup on this code would correspond toa speedup of only 3.85 versus the original sequential program.
Further attempts at optimization were unsuccessful. Yet,
violations do remain, because they occur infrequently enough that
their losses are less than the overheads of reducing them. For
example, attempts at synchronizing on the most frequentviolations, using locks similar to those used in conventional
parallelization, generated excessive waiting times. This supports
the assertion that TLS parallelization often performs better thanmanual parallelization without TLS due to its optimistic executionof code that only occasionally causes violations.

3.9 Additional Automatic Optimizations
Several additional automatic techniques exist for improving
TLS parallel performance. These were not used in the heap sortexample, but will be discussed briefly here for completeness;more details can be found in [3][5][6][8][12][14][15][17]. The
techniques comprise loop chunking, loop slicing, parallel
reductions and explicit synchronization. Loop chunking refers tounrolling multiple small loop iterations to form each TLS
iteration, usually to amortize per-iteration overheads. Loopslicing is the opposite, i.e. splitting each large iteration into
multiple, more manageable ones, a technique that represents a
simple and automatically transformable case of speculative
pipelining described below. Parallel reduction transformations
allow certain iterative functions to be parallelized. For example,
iterative accumulations into a single summation variable could be
instead transformed into four parallel summations that are
combined at the end of the loop. Explicit synchronization works
much like locks in conventional parallelization to protect avariable and can be used on a frequently violated variable toreduce the violation frequency and the associated discarding ofexecution [3][5][12].
Unlike its use in conventional
parallelization, it is used for performance and not correctness. If
the violation data for a TLS parallel application indicates that aread is frequently violated by a write from a less speculative
thread, then these two instructions can be explicitly synchronized.
By eliminating frequent violations, it trades a large quantity of
discarded execution time for a smaller quantity of waiting time.
for (x=0; x<1000; x++) {if ((x%10) == 0)
for (y=0; y<10; y++)InnerLoopOneThousandCyclesOfWork();
OuterLoopOneThousandCyclesOfWork();}

Figure 7A. Original code with independent tasks
shared_threadChoice = shared_y = 0;
for (shared_x=0; shared_x<1000;) {threadChoice = shared_threadChoice;x = shared_x;
if ((x%10) == 0) {y = shared_y++;if (y == 0) {threadChoice=shared_threadChoice=1;} else if (y >= 10) {threadChoice=shared_threadChoice=0;
shared_x++;
shared_y = 0;}
} elseshared_x++;switch (threadChoice) {case 0:OuterLoopOneThousandCyclesOfWork();break;
case 1:
InnerLoopOneThousandCyclesOfWork();break;}}

Figure 7B. Speculative pipeline ready for loop-only TLS

Table 3. Benchmark characteristics
Benchmark

CFP
2000

177.mesa
179.art183.equake
188.ammp

CINT
2000

175.vpr181.mcf
300.twolf

Application category
3-D graphics library
Image recognition/neural networks
Seismic wave
propagation simulation
Computational chemistry
FPGA circuit
placement and routing
Combinatorial optimization
Place and route simulator

Lines ofcode
61,343
1,270
1,513
14,657
17,7292,412
20,4593.10 Speculative Pipelining
Finally we will describe one other very important codetransformation, speculative pipelining. Until now, we havefocused on single-level, loop-based speculation, because loops are
an obvious and easy form of parallelism to extract and because the
TLS software speculation overheads for single-level loop-only
speculation are low. However, TLS can also extract parallelism
from tasks that are not associated with a single loop. For
example, Figure 7A shows how parallelism can exist at multiple
levels within a set of nested loops, making single-level
parallelization suboptimal. Here we assume that each of thethousand-cycle routines is a fairly independent task. If only either
the outer loop or the inner loop is parallelized using single-level
parallelization, half the TLP that exists will not be extracted.
Similarly, TLP can exist between a procedure and the code
following the procedure call. In the past this has been exploitedwith procedural speculation [13], but speculative pipelining can
extract this parallelism with lower overhead. Finally, fairly
independent, sequential tasks that are not part of a loop can beparallelized. This is similar to the TLS conducted by Multiscalar[12][21], but because the programmer explicitly selects theparallel tasks and the TLS hardware support is less closely
coupled to the processor cores, speculative pipelining focuses on
longer threads. In some cases, speculative pipelining can be
automatically applied (loop slicing, procedural speculation), but
in other cases the technique must be conducted manually
In speculative pipelining we break the dynamic execution
path of a uniprocessor program between fairly independent tasks
and make each task an iteration of a newly constructed loop. To
do this, we create a loop shell that chooses between the tasks each
iteration by using a switch-case statement directed by adynamically updated thread-choice variable.
Figure 7B
demonstrates how multi-level speculation can be implemented.
The outer loop body is represented by case 0 and the inner loop
body by case 1. The selection between them is made by thethreadChoice variable, which is updated each time program
flow switches between executing iterations of the outer loop andthe inner loop. New shared variables allow each thread to update
early the next thread's value of x, y and threadChoice while
maintaining a private copy of the variables to be used for
conducting the thread's remaining execution.
The overhead of speculative pipelining is very small; thisexample has less than 12 extra dynamic instructions per thread, orroughly 1% overhead. But, speculative pipelining allows great
flexibility in constructing threads. Unlike regular loop-based
speculation, it can create threads that start and end in different

Table 4. Code transformations
SPEC CFP2000
Transformation
Loop
chunking/slicing
Parallelreductions
Explicit
synchronization

177
mesa

Table 5. Speedup from each additional transformation

SPEC CINT2000

179
art

183
equake

188
ammp

X

X

X

X

Speculative
pipelining
Adapt algorithms
or data structures
Complex value
prediction

175
vpr

300
twolf

Application

X
X

X

181
mcf

X

X

X

X

X

X

X

X

X

X

CFP
2000

The SPEC2000 benchmark suite was chosen for this study,
as it contains a selection of applications that are representative of
CPU-intensive workloads executed on high-performance
processors and memory systems.
All four floating point
applications coded in C were selected, as they were expected to be
more challenging to parallelize than the Fortran benchmarks.
Three integer benchmarks were selected on the basis of sourcecode size and indications of amenability to manual parallelization,such as a concentration of execution time within a small numberof functions. While a few of the other integer benchmarks lookamenable to manual parallelization, it is clear that several would
be very difficult or impossible to manually parallelize without an
extensive understanding of the algorithms and data structures inuse. Information on the selected benchmarks is given in Table 3.
We utilized the reference input data sets. Due to the longexecution times of these data sets, complete execution was notpossible for any of the benchmarks. Since previous research on
SPEC benchmarks [16] has demonstrated both the difficulty andthe importance of choosing carefully the portion of execution tosimulate for applications that exhibit large-time-scale cyclic
behavior, we followed the recommendation to simulate one ormore whole application cycles. The total of all simulation
samples was at least 100 million instructions from each original(non-parallelized) application. One should note that all speedup
and coverage results presented below are based upon an
extrapolation of these samples of whole application cycles back to
the entire application. The extrapolation was conducted by firstprofiling the full application using similar real hardware and thesame compiler as the Hydra CMP. Full application speedup wasthen calculated assuming the simulated speedup on the portion of
execution time corresponding to the application cycles, andassuming no speedup on the portion of the original execution timethat was not a part of the application cycles we sampled.

4.2 Results of Parallelization
In this section we will present results from simulations of ourbenchmarks once the transformations discussed above were

Incremental
speedup

Basic

115%

179.
art

Basic
Parallel reductions
Loop chunking/slicing

48%
104%
135%

38%
15%

183.
equakeBasicLoop chunking/slicing

134%
143%

4%

Basic

35%

Speculative pipelining
Loop chunking/slicing

52%
60%

Basic
Complex value
prediction
Parallel reductions,
explicit synchronization

7%

175.
vpr
(place)4. SPEC CPU2000 BENCHMARKS
4.1 Benchmark Selection and Simulation

Cumulative
speedup

177.
mesa

188.
ammp

functions or that are from portions of the program that do notiterate at all. As a result, speculative pipelining is one of the mostpowerful and difficult techniques for enhancing TLS performance.

Lasttransformation
applied175.
vpr(route)
CINT
2000

Basic
Speculative pipelining
Algorithm/data structurechangesComplex value
prediction

13%
5%

55%

44%

111%

36%

0%
16%

16%

48%

28%

63%

10%

181.
mcf

Basic
Loop chunking/slicing
Parallel reductions

38%
45%
47%

5%
1%

0%
18%

18%

300.
twolf

Basic
Speculative pipelining
Parallel reductions,
explicit synchronization,
algorithm/data structurechangesComplex value
prediction

39%

18%

77%

27%

performed. We will discuss the performance and the programmer
effort required for parallelization. We will also characterize thethreads and the reasons for performance losses in the TLS system.
Each application was initially parallelized using baseparallelization of loops and automatic load-store placement.
Table 4 lists the additional transformations that were then used.
The first three are simple and can be automated; the second three
are complex, requiring manual programming.
The data demonstrate that the simple transformations are
beneficial for both floating point and integer applications.
However, the complex ones are beneficial mainly for the integer
applications. This was because the execution times of the floating
point applications were all dominated by easily parallelizable
loops, except for ammp. Therefore, the complex transformations
added little or no benefit. In contrast, all the integer applications
benefited from the code transformations, and two of the threebenefited from complex ones. Notably, explicit synchronization
was not very valuable, enhancing performance for just two
applications and both times only when used in combination withsome other technique. This is for two reasons. First, it does notwork well for infrequent violations, as discussed in Section 3.9.
Second, many of the violations typically prevented by explicit
synchronization are instead better eliminated through the use ofcomplex methods that do not cause serialization.

Table 6. Speculative thread lengths, regions and coverage
Application

Dynamic
thread length(instructions)

Number of
speculative
regions

7,735
453
1,055
140

1
7
6
1

Percent
executiontimecoverage
84%
95%
100%
86%

5,061

1

100%

177.mesa
179.art183.equake
188.ammp

CFP
2000

175.vpr(place)175.vprCINT(route)2000
181.mcf
300.twolf
Column mean

1,309

1

97%

238
784
2,097

5
1
3

91%
100%
94%

Table 5 details the speedups achieved for each application as
the transformations were sequentially added.
Ideally, theincremental speedup due to each transformation could be listed.
However, the transformations interact with each other. For
example, on vpr (place) explicit synchronization yielded no
speedup after base parallelization with additional value prediction.
However, applying it together with the parallel reduction
transformation provided a sizeable advantage. Due to theinteractions and the many permutations of transformations, wehave instead listed the speedups along the single path oftransformations we actually followed. Note that because vpr is aplace and route application and the two portions of the application
are very different, we have listed results for them separately.
Table 5 more clearly highlights that simple transformations
parallelize floating point applications well, but that integer
applications require complex transformations. In fact, most if not
all of the speedup for each floating point application is alreadyrealized using only basic parallelization, while the opposite holds
true for the integer applications, which often require complex
transformations to get any significant speedup at all.
Figure 8 shows the speedups that were achieved using three
TLS/memory systems. The first is a realistic system, the second
assumes a perfect memory system and the third assumes a perfectmemory system with a zero-overhead TLS implementation. The

300.twolf

181.mcf

175.vpr (route)

Perfect, No Overhead

175.vpr (place)

188.ammp

183.equake

Perfect

179.art

3.5
3.25
3
2.75
2.5
2.25
2
1.75
1.5
1.25
1

177.mesa

Speedup.

Real

Figure 8. Speedups with real memory, perfect memory andperfect memory with no TLS overhead

Table 7. Breakdown of parallelized execution times
Application
177.mesa
CFP
179.art2000
183.equake
188.ammp

Useful
70%
98%
78%
50%

Discarded
28%
0%
16%
40%

Waiting
2%
1%
5%
6%

Overhead
0%
1%
1%
4%

175.vpr(place)CINT 175.vpr(route)2000
181.mcf
300.twolf
Column mean

63%

36%

0%

1%

47%

35%

10%

8%

65%
55%
66%

24%
23%
25%

6%
20%
6%

5%
2%
3%

average (arithmetic mean) floating point speedup with the real
memory system is 2.1, and the average integer speedup is 1.7.
Comparison of these speedups with those generated by previous
studies on automatic parallelization with TLS is difficult, due tothe different architectures, compilers and execution segments
utilized. Since TLP is mostly orthogonal to ILP, a roughcomparison of speedups can be done using systems with different
processor cores and compilers, but different memory systems will
still affect the results. With these caveats, a comparison withresults from [17][18][21] indicates that the manual parallelization
has provided very good parallel performance, well in excess of
automatic extraction of TLP at similar thread granularities.
The results for the realistic and perfect memory systems in
Figure 8 indicate a sensitivity to memory system delay that varies,
with some application speedups fairly insensitive to thecharacteristics of the memory system and others more strongly
affected. The perfect memory system results usually provide an
upper bound on the performance that can be achieved by scaling
the memory system with the number of processors. An unusual
exception occurs for ammp, because the faster memory systemcauses a large number of violations on a load-store pair thatwould otherwise have experienced far fewer violations. Likewise,
the results for the perfect memory systems with and without
speculation overheads indicate the performance losses caused by
the use of a TLS system with speculation software handlers.
These results indicate that fully hardware-based speculation
would improve performance fairly little for these applications.
Table 6 characterizes the speculative threads created withineach application. Thread sizes span almost two orders ofmagnitude. The number of distinct speculative regions is small,demonstrating that for many representative applications a large
portion of the total execution time can be parallelized by selecting
only a few locations in the code. The parallel coverage of theoriginal sequential execution time is uniformly high, even for the
integer applications. Parallel coverage typically increases as moresophisticated transformations are applied to the applications.
Similarly, thread lengths can also increase safely as violations are
reduced. Because longer threads expose more work to losses fromviolations, as violations become less frequent, thread lengths canbe safely increased, for example, by loop chunking. This reduces
speculation overheads and the serialization enforced by the inorder commit at the end of each thread. Correspondingly,
applications for which the TLS thread lengths are large and theparallel coverage high tend to have good speedups. But, if either
quality is absent, then the performance will usually besubstantially diminished. Amdahl’s Law explains why coverageTable 8. Lines of code added to parallelize applications
Application
CFP
2000

177.mesa
179.art183.equake
188.ammp

175.vpr181.mcf
300.twolf
Column mean

CINT
2000

Original
lines
61,343
1,270
1,513
14,657

Lines
added
20
140
130
130

Percent
added
0%
11%
9%
1%

Prog. hours
required
33
24
18
107

17,7292,412
20,459

160
120
320
146

1%
5%
2%
4%

102
165
112
80

must be high, while the poorer performance for small thread
lengths can be explained by their correlation with high violation
rates and greater speculation overheads and commit serialization.
Table 7 provides the breakdown of execution times spent in
the parallelized sections of code. The useful work done is
generally quite high, the TLS system overhead is negligible, andviolations (discarded time) waste over four times as many cycles
as load imbalances (waiting time). The remaining violations
tended to be due to variables that had frequent accesses
distributed amongst the threads, where each access unpredictablycaused a violation a small percentage of the times it dynamicallyoccurred.
This prevented any benefits from explicit
synchronization, because it causes too much execution
serialization. Likewise, these qualities would prevent the dynamic
dependence detector described in [3] from providing any benefit,
although the one proposed in [12] could work, but only if thedependence distances defined in their paper could be used todevelop a reliable dependence predictor for these specificdependences. Dynamic load imbalance, due to size-mismatchedthreads that must wait to be committed in order, is the source of
the waiting losses. Both vpr (route) and twolf show large
losses due to load imbalances. This is especially a problem forapplications that have been parallelized with small thread sizes.
Part of the useful work done includes the execution of theadditional instructions required for the parallel transformations
and to support the interprocessor communication and control. In
general, the programmer must make a choice between the cost of
supporting each additional transformation and the cost of theviolations that occur from not using it, instead. These extra
instructions limit the maximum speedup, even though for thesebenchmarks the losses due to the extra work were fairly small.
Table 8 provides an indication of the programmer effort
required for the parallelization of these benchmarks. It lists thenumber of lines of code added and the total number of hours spent
analyzing, parallelizing and debugging each application. Whilethe hours required are highly dependent on the capabilities of the
programmer, these data provide at least an order-of-magnitudegauge of programmer effort involved, and no better metric isapparent. We only counted lines of code that were new andunique, or at least substantially changed. We did not count lines
of code that were changed or added to implement the automaticbase parallelization, i.e. we did not count lines of code that wereeffectively replicated from the original application or lines oftemplate code that were inserted purely to support the simulator.
The number of lines of code added remains fairly small andconstant across applications, almost always less than two hundred.

For these applications, the number of lines required has little
correlation with the size of the application. However, this may
not hold true for larger, more complex applications, which may
require the parallelization of more speculative regions, i.e. loops.
The number of hours required to parallelize each application was
also quite small, in comparison to the number of hours that wereoriginally required to develop them. This strongly supports ourclaim that manual parallelization with TLS allows programmers tocode for a uniprocessor target in a straightforward way, and thenwith minimal effort port the entire optimized application to a TLS
CMP platform to realize good parallel performance.
TLS parallelization depends primarily on an application'salgorithms and source code and the TLS and memory systems,
rather than the processor architecture. Therefore, the final
parallelized application should port easily to other CMP systems
that support loop-based TLS and explicit synchronization. For
equivalent speedups, they should have low interprocessor
communication delays, low speculation overheads and similarly
sized caches and write buffers. A CMP with fewer processors will
generally not require significant code changes in order to run
efficiently, but more processors may necessitate modifications to
use all the processors. This will be examined in future research.

5. RELATED WORK
Research on automatic parallelization [2][9] and speculation[4][13][14][17][21] is underway at various universities. Several
projects share our focus on general purpose applications.
However, they primarily investigate parallelization that can be
automated, while in this paper we use techniques that cannot beeasily automated to explore the full potential of TLS. The
Wisconsin Multiscalar team achieves excellent speedups on
general purpose applications, including integer applications[12][21].
However, Multiscalar allows register-to-registercommunication between the processors at the cost of more
complex and high-speed hardware. So, their research explores adifferent hardware/software design space, generally utilizing finergranularity threads. Research by the CMU STAMPede team
[17][18][19] and at the University of Illinois at UrbanaChampaign [4][5][20] explores different design points with lessclosely coupled processors, more similar to our TLS CMP.
Relevant research done by Rauchwerger, Padua and Amatoconsidered software-based schemes of speculation andparallelization [15], while later work in conjunction with Zhang
and Torrellas utilized hardware support, as well [20]. Other
studies [4][18] have focused on achieving highly scalable
parallelization. These studies differ from ours in that they either
focus on using software only, or on using hardware support
specific to the code transformation applied, i.e. hardware for
conducting reductions or for achieving scalable speedups. Also,much of their research has centered on scientific, floating-pointintensive Fortran applications, while our research considers both
floating point and integer programs that are all written in C.
Finally, substantial work on exploiting value prediction anddynamic
synchronization
has
been
conducted
in[3][5][6][8][12][17]. We incorporate the benefits of these studies
where possible and extend upon them. For example, the earlier
value prediction studies explore only predictions of values that do
not change or are in a simple stride. In this study, we explore
predictions of values that evolve in a more complex manner.

6. CONCLUSION
In this paper, we described the way in which TLS manualprogramming is done and three of the most useful manual TLS
code transformations: complex value prediction, data structure/algorithm changes and speculative pipelining. These techniques
were applied to several applications in SPEC CPU2000 to assess
the performance and difficulty of using TLS on well-known
processor benchmarks. While simple (automatic) transformations
were useful for many applications, complex transformations wereable to provide further large performance benefits. This was
especially true for integer applications, some of which would haveexperienced no significant speedup with only automaticparallelization. We also show that real-world applications can beparallelized with very little effort with manual TLS programming.
Our experience shows that TLS can dramatically reduce theprogrammer effort required for application parallelization, while
yielding performance gains similar to, if not exceeding, thoseobtainable using conventional manual parallelization. This
enables a new approach to parallel programming. In thisparadigm, the majority of the programming effort can focus onconventional single-threaded application design, with a relatively
small effort at the end to port the application to a multiprocessor
platform using manual parallelization with TLS.

[7] S.W. Keckler et al., “Exploiting fine-grain thread level
parallelism on the MIT multi-ALU processor,” ISCA-25,
Barcelona, Spain, pp. 306-317, June 1998.

[8] K.M. Lepak, G.B. Bell, and M.H. Lipasti, “Silent stores andstore value locality,” IEEE Transactions on Computers, vol.
50, pp. 1174-1190, Nov. 2001.

[9] S.W. Liao, et al., “SUIF Explorer: An Interactive andInterprocedural Parallelizer,” Proc. Sym. PPOPP 1999, pp.
37-48, Atlanta, Georgia, Aug. 1999.

[10] J.F. Martinez and J. Torrellas, “Speculative synchronization:
applying thread-level speculation to explicitly parallel
applications,” Proc. 10th Intl. Conf. on Architectural
Support for Programming Languages and Operating
Systems (ASPLOS), San Jose, California, Oct. 2002.

[11] B.P. Miller, et al., “The Paradyn Parallel Performance
Measurement Tools,” IEEE Computer, 28(11):37-46, Nov.
1995.

[12] A. Moshovos, S.E. Breach, T.N. Vijaykumar, G.S. Sohi,“Dynamic speculation and synchronization of data
dependences,” ISCA-24, Denver, Colorado, pp. 181-193,
June 1997.

[13] K. Olukotun, L. Hammond, and M. Willey, “Improving the

7. ACKNOWLEDGMENTS
This work was supported by Air Force contract F29601-012-0085, NSF contract CCR-0220138, the Intel graduate
fellowship program and the Alliance for Innovative
Manufacturing at Stanford. The authors would also like to thankLance Hammond for extensive discussions and key insights on
this paper and support of the Hydra CMP simulator.

performance of speculatively parallel applications on the
Hydra CMP,” Proc. 13th ACM International Conference on
Supercomputing (ICS), Rhodes, Greece, pp. 21-30, June
1999.

[14] C.-L. Ooi, et al., “Multiplex: unifying conventional andspeculative thread-level parallelism on a chip
multiprocessor,” ICS-15, June 2001.

[15] L. Rauchwerger, N. Amato, and D. Padua, “Run–time

8. REFERENCES[1] V.S. Adve, et al., “An integrated compilation andperformance analysis environment for data parallel
programs,” Supercomputing 1995, San Diego, California, pp.
1370-1404, Nov. 1995.

[2] B. Blume, et. al, “Restructuring programs for high-speed
computers with Polaris,” Proc. 1996 ICPP Workshop on.
Challenges for Parallel Processing, pp. 149-161, Aug. 1996.

[3] G.Z. Chrysos and J.S. Emer, “Memory dependence
prediction using store sets,” Proc. 25th Annual Intl. Sym. on
Computer Architecture (ISCA), Barcelona, Spain, pp. 142153, June 1998.

[4] M. Cintra, J. Martínez and J. Torrellas, “Architectural
support for scalable speculative parallelization in sharedmemory multiprocessors,” ISCA-27, Vancouver, Canada, pp.
13-24, June 2000.

[5] M. Cintra and J. Torrellas, “Eliminating squashes throughlearning cross-thread violations in speculative parallelization
for Multiprocessors,” Proc. 8th Intl. Sym. on HighPerformance Computer Architecture (HPCA), Cambridge,
Massachusetts, Feb. 2002.

[6] F. Gabbay and A. Mendelson, “Using value prediction toincrease the power of speculative execution hardware,” ACM
Transactions on Computer Systems, vol. 16, pp. 234-270,
Aug. 1998.

methods for parallelizing partially parallel loops,” ICS-9,
Barcelona, Spain, pp. 137-146, July 1995.

[16] T. Sherwood and B. Calder, “Time varying behavior ofprograms,” Tech. Rep. No. CS99-630, Dept. of Computer
Science and Eng., UCSD, Aug. 1999.

[17] J.G. Steffan, C.B. Colohan, A. Zhai, and T.C. Mowry,“Improving value communication for thread-level
speculation,” HPCA-8, Cambridge, Massachusetts, Feb.
2002.

[18] J. Steffan, C. Colohan, A. Zhai, and T. Mowry, “A scalable
approach to thread-level speculation,” ISCA-27, Vancouver,
Canada, pp. 1-12, June 2000.

[19] A. Zhai, C.B. Colohan, J.G. Steffan, and T.C. Mowry,“Compiler optimization of scalar value communication
between speculative threads,” ASPLOS-10, San Jose,
California, Oct. 2002.

[20] Y. Zhang, L. Rauchwerger, and J. Torrellas, “Hardware for
speculative parallelization of partially-parallel loops in DSM
multiprocessors,” HPCA-5., Orlando, Florida, pp. 135-141,
Jan. 1999.

[21] C. Zilles and G. Sohi, “Execution-based prediction using
speculative slices,” ISCA-28, Goteborg, Sweden, pp. 2-13,
July 2001.