TRANSACTIONALCOHERENCE AND CONSISTENCY:SIMPLIFYING PARALLEL
HARDWARE AND SOFTWARETCC SIMPLIFIES PARALLEL HARDWARE AND SOFTWARE DESIGN BY
ELIMINATING THE NEED FOR CONVENTIONAL CACHE COHERENCE ANDCONSISTENCY MODELS AND LETTING PROGRAMMERS PARALLELIZE A WIDERANGE OF APPLICATIONS WITH A SIMPLE, LOCK-FREE TRANSACTIONAL MODEL.

Lance Hammond
Brian D. Carlstrom
Vicky Wong
Michael Chen
Christos Kozyrakis
Kunle Olukotun
Stanford University

92

With uniprocessor systems running
into instruction-level parallelism (ILP) limits
and fundamental VLSI constraints, parallela rc h i t e c t u res provide a realistic path tow a rdscalable performance by letting programmers
exploit thread-level parallelism (TLP) in more
explicitly distributed architectures. As a result,
single-board and single-chip multipro c e s s o r s
a re becoming the norm for server and embedded computing, and are even starting to appear
on desktop platforms. Ne ve rtheless, the complexity of parallel application development andthe continued difficulty of implementing efficient and correct parallel architectures have
limited these architectures’ potential.
Most existing parallel systems add hardware
to give programmers an illusion of a single
shared memory common to all processors.
Programmers must divide the computation
into parallel tasks, but all tasks work on a single data set resident in the shared memory.
Unfortunately, the hardware required to support this model can be complex. To provide a
coherent view of memory, the hardware must

determine the location of the latest version of
any particular memory address, re c over thelatest version of a cache line from anywhere
within the system when a load from it occurs,and efficiently support interprocessor communication of numerous small, cache-linesized data packets. It must do all this withminimal latency, too, because individual loadand store instructions depend on each communication event. Fu rther complicating matters is the problem of sequencing the various
communication events constantly passing
through the system at the fine-grained leve lof individual load and store instructions. Fors o f t w a re synchronization routines to work ,hardware designers must devise and correctly
implement sets of rules known as m e m o ry con sistency models. Over the years, these models
h a ve progressed from easy-to-understand but
sometimes performance-limiting sequentialconsistency schemes to more modern schemes
such as relaxed consistency.
The complex interaction of coherence, synchronization, and consistency makes the job

Published by the IEEE Computer Society0272-1732/04/$20.00  2004 IEEE

Figure 1. Transactional coherence and consistency (TCC) in hardware: the transaction cycle (a) and a diagram of sample TCCenabled hardware (b).

of parallel programming difficult. Ex i s t i n g
a p p roaches re q u i re programmers to manage
parallel concurrency directly by creating andexplicitly synchronizing threads. The difficulty stems from the need to achieve the often
conflicting goals of functional correctness andhigh performance. In particular, using a few
coarse-grained locks can make it simpler tocorrectly sequence accesses to variables shared
among parallel threads. On the other hand,
having numerous fine-grained locks often
a l l ows higher performance by reducing theamount of time wasted by threads as they
compete for access to the same variables,
although the larger number of locks usually
incurs more locking overhead.
Transactional coherence and consistency(TCC) simultaneously eases both parallel
programming and parallel architecture design
by relying on programmer-defined transac tions as the basic unit of parallel work, communication, memory coherence, andmemory consistency. Although several
re s e a rchers have proposed using hard w a retransactions instead of locks or other parallel
programming constructs individually,4-6 TCC
unifies these ideas into an “all transactions,
all the time” model that allows significant
s i m p l i fications of both parallel hardware3 ands o f t w a re . 2 As parallel arc h i t e c t u res become
i n c reasingly pre valent and a wider variety of
h a rd w a re designers and programmers must
deal with their intricacies, this advantage will
i n c rease TCC’s import a n c e .

TCC hardware
Processors operating in a TCC-based multiprocessor execute speculative transactions in
a continuous cycle (illustrated in Fi g u re 1a)on multiprocessor hard w a re similar to that
depicted in Fi g u re 1b. A transaction is asequence of instructions marked by softwarethat is guaranteed to execute and complete
only as an atomic unit. Each transaction pro-NOVEMBER–DECEMBER 2004

93

MICRO TOP PICKS

duces a block of writes, which the processor
buffers locally while the transaction executes,
committing them to shared memory only as
an atomic unit after the transaction completes.
Once the transaction is complete, hard w a remust arbitrate system-wide for permission tocommit the transaction’s writes. After winning
the arbitration, the processor can exploit highbandwidth system interconnect to broadcast
all of the transaction’s writes to the rest of thesystem, as one packet. This broadcast canmake scaling TCC to numerous processors achallenge. Meanwhile, other processors’ local
caches snoop on the write packets to maintain system coherence. Snooping also lets theprocessors detect when they have used datathat another processor has subsequently modified—a dependence violation. Combining allof the transaction’s writes imparts latency tolerance because it reduces the number of interp rocessor messages and arbitrations andbecause flushing the writes is a one-way operation. The commit operation can also provide
i n h e rent synchronization for programmers
and a greatly simplified consistency protocol
for hardware engineers. Most significantly, thiscontinual cycle of speculative buffering,b roadcast, and (potential) violations lets us
replace both conventional coherence and consistence protocols.
Consistency protocols can be simplified
because communication can occur only atoccasional, programmer-defined commit
points, instead of at each of the numero u sloads and stores used by conventional models. This has significant implications for both
hardware and software. For hardware designers, TCC simplifies the design by drasticallyreducing the number of latency-sensitive arbitration and synchronization events that must
be sequenced by consistency-management
logic in a typical multiprocessor system. To
p rogrammers or parallelizing compilers,
explicit commit operations mean that softw a re can orchestrate communication much
m o re precisely than with conventional consistency models. Simplifying matters further
for most programmers, imposing an order on
the transaction commits and backing up
uncommitted transactions if they have specu l a t i vely read data modified by other transactions effectively lets the TCC system provide
an illusion of uniprocessor execution. As far

94

IEEE MICRO

as global memory and software is concerned,
all memory references from a transaction thatcommits earlier effectively occurred before allof the memory references of a transaction thatcommitted later. This is true even if their actual execution was interleaved in time, because
all writes from a transaction become visible toother processors only at commit time.
This simple, pseudo-sequential consistencemodel allows for a simpler coherence model,t o o. During each transaction, stores areb u f f e red and kept within the transaction’s
p rocessor node to maintain transaction atomicity. Processor caches do not use conventional
modified/exc l u s i ve / s h a re d / i n valid (MESI)style protocols to maintain lines in shared or
exclusive states at any point, so many processor nodes can legally hold the same line simultaneously in either an unmodified or
speculatively modified form. At the end ofeach transaction, the pro c e s s o r’s commit
b roadcast notifies all other processors about
its changed state. During this process, theother processors perform conventional invalidation (if the commit packet contains only
addresses) or update (if it contains addresses
and data) to keep their cache state coherent.
Simultaneously, they must determine whether
they have read from any of the committed
addresses. If they have, they must restart andreexecute their current transactions with theupdated data. This protects against true data
dependencies. At the same time, because later
processors’ transactions do not flush out any
data to memory until their own turn to commit, data antidependencies are not an issue.
Until a transaction commits, transactions thatcommit earlier do not see its effectively later
results (avoiding write-after-read dependencies), and processors can freely overwrite previously modified data in a clearly sequenced
manner (handling write-after-write dependencies legally).
TCC will work in a wide variety of multiprocessor hardware environments, including
various chip multiprocessor configurations
and small-scale multichip multiprocessors.
Within these systems, individual pro c e s s o r
c o res and their local cache hierarchies needfeatures that provide speculative buffering of
memory re f e rences and commit arbitration
control. Most significantly, a mechanism forgathering all modified cache lines from eachtransaction into a commit packet is required.
This mechanism can be a write buffer completely separate from the caches or an address
buffer that maintains a list of tags for lines
containing data to be committed. The buffer
must hold approximately 4 to 16 Kby t e sworth of cache lines. If it fills during the execution of a long transaction, the pro c e s s o r
must declare an ove rf l ow and stall until it
obtains commit permission, when it can continue executing while writing its results dire c tly to shared memory. Of course, thiswrite-through behavior means that no otherprocessors can commit while the transaction
completes, to maintain atomicity. This effectcan cause serious serialization if it occurs frequently, but is acceptable on occasion.
In the caches, all of the included lines must
maintain the following information in someway:
• Read bits. Bits set on loads to indicate thata cache line (or portion thereof) has beenread speculatively during a transaction.
A processor’s coherence logic snoops theread bits while other processor nodes
commit to determine when the pro c e ssor has speculatively read any data too
early. If it snoops and sees a write committed by another processor modifying
an address cached locally with its read bit
set, it must violate its current transaction
and restart.
• Mo d i fied bits. Eve ry cache line has at least
one modified bit. St o res set the modifie d
bit to indicate when any part of the line
has been written speculatively. The
p rocessor uses these bits to simultaneously invalidate all speculatively writtenlines when it detects a violation.
Additional bits can improve performance,
but are not essential for correct execution. A
p rocessor cannot flush cache lines with set
read bits from its local cache hierarchy in midtransaction; if it does, the processor must stall
for an ove rflow. Set modified bits will cause
similar ove rflow conditions if the write bufferholds only addresses.

TCC software
TCC parallelization requires only a few new
p rogramming constructs. It is simpler thanparallelization with conventional thre a d e dmodels because it needs fewer code transformations for typical parallelization efforts. In
particular, it lets programmers make informed
trade-offs between programmer effort andperformance. In simplified form, pro g r a mming with TCC is a three-step process:1. Divide the pro g ram into tra n s a c t i o n s. To
c reate a parallel program using TCC, ap rogrammer coarsely divides the program into transactions that can run concurrently on different processors. In thisrespect, parallelizing for TCC is like conventional parallelization, which also
re q u i res finding and marking parallelcode regions. Howe ve r, with TCC theprogrammer does not need to guaranteethat parallel regions are independent, as
hardware will catch all dependence violations dynamically. Our interface lets
programmers divide their program into
parallel transactions using loop iterations
and/or a forking mechanism.
2. Specify transaction ord e r. The default
transaction ordering is to have transactions commit results in the same order as
they would in the original sequential program, because this guarantees that thep rogram will execute correctly. Howe ver, if a programmer can verify that thiscommit order constraint is unnecessary,he or she can relax it completely or partially to improve performance. The interface also provides ways to specify theapplication’s ordering of constraints in
useful ways.
3. Tune perf o rmance. After selecting ando rdering transactions, the pro g r a m m e r
can run the program in parallel. The TCC
system can automatically provide feedback
about where violations occur in the program, which can direct the programmer
to perform further optimizations.
We describe the interface in C, but it canbe readily adapted to any programming language (for example, we also used Java).

Loop-based parallelization
We introduce loop parallelization in thecontext of a simple sequential code segmentthat calculates a histogram of 1,000 integer

NOVEMBER–DECEMBER 2004

95

MICRO TOP PICKS

percentages using an array of corre s p o n d i n gbuckets:/* input */int *in = load_data();
int i, buckets[101];for (i = 0; i < 1000; i++) {buckets[data[i]]++;}
Figure 2. Sample schedule
for transactional loops.

/* output */print_buckets(buckets);

The compiler interprets this program as one
large transaction, exposing no parallelism to
the TCC hardware. We can parallelize the forloop, howe ve r, with the t_for keyword:...
t_for (i = 0; i < 1000; i++) {...

With this small change, we now have a parallel loop that is guaranteed to execute identically to the original sequential loop. A similar
t_while k e y w o rd is also available forwhile loops. Each loop body iteration
becomes a separate transaction that can execute in parallel but must commit in the original sequential ord e r, such as the pattern inFigure 2. When two parallel iterations try to
update the same histogram bucket simultaneously, the TCC hard w a re causes the later
iteration to violate when the earlier iterationcommits, forcing the later one to re e xe c u t eusing updated data and preserving the original sequential semantics.
In contrast, a conventionally parallelize dsystem would re q u i re an array of locks to protect the histogram bins, resulting in much
more extensive changes:
int* in = load_data();
int i, buckets[101];/* Define & initialize locks */LOCK_TYPE bucketLock[101];for (i = 0; i < 101; i++) {LOCK_INIT(bucketLock[i]);}for (i = 0; i < 1000; i++) {LOCK(bucketLock[data[i]]);

96

IEEE MICRO

buckets[data[i]] ++;UNLOCK(bucketLock[data[i]]);}print_buckets(buckets);

If any of this locking code is omitted or buggy,
the program might fail—and not necessarily inthe same place every time—significantly complicating debugging. Debugging is especially difficult if the errors occur only during infrequent
memory access patterns. The situation is potentially even trickier if an application must holdmultiple locks simultaneously within a criticalregion, because programmers can easily write
code with locking sequences that might deadlock in these cases.
Although sequential ordering is generally
useful because it guarantees correct execution,
in some cases—such as this histogram example—it is not actually re q u i red for correctness.
In this example, the only dependencies among
the loop transactions are through the histogram bin updates, which are perf o r m a b l e
in any order. If programmers can verify thatno dependencies are order-critical, or if therea re simply no loop-carried dependencies, they
can use the t_for_unordered andt_while_unordered k e y w o rds to allow
the loop’s transactions to commit in any order.
A l l owing unord e red commits is most useful
in more complex programs with dynamicallyvarying transaction lengths, because it eliminates much of the time that processors spend
waiting for commit permission betwe e nunbalanced transactions.

Fork-based parallelization
Although the simple parallel loop API will
w o rkfor many programs, some less-structured
p rograms might need to generate transactions
more flexibly. For these situations t_fork,
a transactional fork similar to conve n t i o n a lthread-creation APIs, is useful:void t_fork(void(*child_function_ptr)(void*),
void *input_data,
int child_sequence_num,
int parent_phase_increment,
int child_phase_increment);/* Which forks this off: */when necessary. Howe ve r, because sequencing requirements often vary in small but critical ways from program to program, this is still
This call forces the parent transaction to com- an active area of development as we evaluatemit, and then creates two completely new—and more applications with TCC.
We control transaction ordering by assignparallel—transactions in its place. One (the newparent) continues executing the code immedi- ing two parameters to each transaction:
ately following the t _ f o r k,while the other sequence and phase. These two numbers control(the child) starts executing the function at the ordering of transaction commits. Tr a n s a cchild_function_ptr with input_ tions with the same sequence number might
data. Other input parameters control order- need to commit in a programmer-defineding of forked transactions in relation to other order, whereas transactions in differe n ttransactions, as we discuss in the following sec- sequences are always independent. We can use
tion. We demonstrate this function with a the child_sequence_num parameter
parallelized form of a simple two-stage processor within a t_fork call to produce a child transpipeline, which we simulate using the functions action with a new sequence number. Within
i_fetch for instruction fetch, i n c r e- each sequence, the phase number indicates
ment_PC to select the next instruction, and each transaction’s re l a t i ve age. TCC hardware
execute to execute instructions. The child will only commit transactions in the oldest
transaction executes each instruction while the a c t i ve phase (lowest value) from within eacha c t i ve sequence. Using this notation, an
new parent transaction fetches another:ord e red loop is simply a sequence of transactions with the phase number incremented by/* Initial setup */one each time, whereas an unordered loop uses
int PC = INITIAL_PC;
transactions with the same phase number.
int opcode = i_fetch(PC);We can impose more arbitrary transaction
phase ordering with the following calls:/* Main loop */void child_function(void *input_data);

while (opcode ! = END_CODE){t _ f o r k(execute, &opcode,
1, 1, 1);increment_PC(opcode, &PC);
opcode = i_fetch(PC);}This example creates a sequence of ove rlapping transactions similar to those in Figu re 3. The t_fork call g i ves enoughflexibility to divide a program into transactions in virtually any way. It can even be used
to build the t_for and t_while constructs, if necessary.

Explicit transaction commit ordering
The simple ordered and unordered modes
might not always suffice. For example, a programmer might desire partial orderingexecuting unord e red most of the time, but
occasionally imposing some ordering. This israre with transactional loops, but quite common with forked transactions. To handle thesecases, we have developed a simple model for
explicitly controlling transaction sequencing

Figure 3. Simple fork example, where the parameters
are sequence:phase.

void t_commit(
int phase_increment);
void t_wait_for_sequence(int phase_increment,
int wait_for_sequence_num);

The t_commit routine implicitly commits
the current transaction and then immediately
starts another on the same processor with
its phase number incremented by thephase_increment parameter. The mostcommon phase_increment parameter is0, which simply breaks a large transaction into
two. However, using a phase_incrementof 1 or more forces an explicit transaction commit ordering. This can be used in many ways,
but the most common is to emulate a conventional barrier among all transactions in asequence using transactional semantics. The similar t_wait_for_sequence call performs
a t_commit and waits for all transactions inanother sequence to complete. Programmers
typically use this call to let a parent transaction
sequence wait for a child sequence to complete,similar to a conventional thread join operation.

NOVEMBER–DECEMBER 2004

97

MICRO TOP PICKS

Table 1. Key parameters in our simulations (all cycle values are in CPU cycles).

SystemDescription

InterCPU

Commitbandwidth

overhead

Violationdelay(bytes per cycle)(cycles)(cycles)

0

0

Ideal

“Perfect” TCC multiprocessor

Chip multiprocessor (CMP)

Realistic multiprocessor on a single chip

16

5

0

Symmetric multiprocessor (SMP)

Realistic multiprocessor on a board

4

25

20

Table 2. Characteristics of applications used for our analysis.
Lines
SourceApplication

language Benchmark

description

SourceInput

Resource allocation

jBYTEmark51 × 51

Java

Assignment

solver
MolDynN-body code-

LUFactor

Matrix factorization

RayTrace
SPECjbbchangedTCC

code(percent)

parallelization

556

5.8

Loop: two ordered,

615

3.3

Loop: nine

516

1.9

Loop: two ordered,

1,233

4.9

Loop: nine

27,2491.3

Fork: five calls (onearraynine unorderedJava Grande

2,048

jBYTEmark101 × 101

3D ray tracer

Java Grande

150 × 150

Transaction

SPECjbb

230 iterations

modeling particles

particles

and triangular solver

unorderedmatrixfour unorderedpixel image
processing
C

art

Image recognition/

unorderedwithout

serverper task type)randomization
SPEC2000 FP

Reference.1

1,270

8.9

Loop: 11 chunked

SPEC2000 FP

Reference

1,513

0.8

Loop: threeneural network
equakeSeismic wave

PrimaryLines ofand unordered

propagation

unorderedsimulation
tomcatv

Vectorized mesh

SPEC95 FP

256 × 256 array

346

2.0

Loop: seven

Mediabenchmei16v2.m2v

9,834

4.6

Fork: one call

generation
MPEGdecodeVideo bitstream

unordered

decoding

Performance evaluation
We used our TCC programming constructs
to parallelize applications from va r i o u s
domains. We then used simulation to evaluate and tune their performance for large- andsmall-scale TCC systems.
Our exe c u t i o n - d r i ven simulator models ap rocessor executing at a fixed rate of one
instruction per cycle while producing tracesof all transactions in the program. We analyzed the traces on a parameterized TCC system simulator that includes 4 to 32 processors
connected by a broadcast network. The
TLP-oriented benefits of TCC parallelization
are fairly orthogonal to speedup from superscalar ILP extraction techniques within indi-

98

IEEE MICRO

vidual processors, so our results can scale forsystems with processors faster (or slower) than
1.0 instructions per cycle, until the commit
broadcast bandwidth is saturated.
Table 1 lists the values of three key systemparameters that describe three potential TCC
c o n figurations: ideal ( i n finite bandwidth, zero
overhead), single-chip/CMP (high bandwidth,
low overhead), and single-board/SMP (medium bandwidth, higher overhead).
Table 2 presents the applications we used in
the study. These applications exhibit a dive r s e
set of concurrency patterns, including denseloops (LUFactor), sparse loops (equake), andtask parallelism (SPECjbb). We modified the C
applications to use transactions manually. Incontrast, we parallelized most Java applications
automatically using the Jrpm dynamic compilation system,4 and then ran them on top of aversion of the Kaffe Ja va virtual machine(http://kaffe.org) customized to use transactions instead of locks. The only exception was
SPECjbb, which we manually parallelized byf o rking transactions for each warehouse task(such as orders and payments). Although mostp rogrammers assign separate warehouses toeach processor to parallelize this benchmark,
TCC let us parallelize within a single warehouse, a virtually impossible task with conventional techniques. In all cases, we only
needed to modify a modest percentage of theoriginal code to make it parallel.

Parallel performance tuning
After a program is divided into transactions,most problems will tend to be with perf o rmance, not correctness. To obtain good performance, programmers must optimize theirtransactions to balance a few competing goals:• Ma x i m i zeparallelism.Programmers mustb reak as much of the program as possible
into parallel transactions, which should
be of roughly equal size to maintain goodload balancing across processors.
• Minimize violations. To avoid the costly
discarding of work after violations, programmers should avoid parallel transactions that communicate frequently.
Keeping transactions reasonably small tominimize the amount of work lost when
violations occur can also help.
• Mi n i m i ze transaction ove rh e a d. On theother hand, programmers should generally avoid very small transactions becauseof the overhead associated with starting,ending, and committing transactions.
• Avoid buffer ove rflows. Buffer ove rf l ow s
can cause serialization by requiring
processors to hold commit permission fora long time. Hence, programmers should
stay away from transactions that read or
write large amounts of state.
Figure 4a shows application speedups as weapplied successive optimizations for CMP configurations with 4, 8, 16, and 32 pro c e s s o r s ,and Fi g u re 4b breaks down execution time forthe eight-processor case into “useful work,”“waiting for commit,” “losses to violations,”
and “idling” caused by too few parallel transactions for the available processors—usuallycaused by sequential code regions. Although
the baseline results showed significant speedup,
they often needed improvement. Where possible, we first optimized with unordered loops.
However, because load balancing was rarely aproblem in the applications we selected, as ourlow “waiting to commit” times show, this did
not significantly improve performance.
We used results from initial application
runs to guide our optimization efforts. These
runs produced violation re p o rts that summarized the load-store pairs and data addre s s e scausing violations, prioritized by the amountof time lost. We then used gdb to determine
exactly which variables and variable accesses
caused the violations. This information is sign i ficantly more useful than feedback available
on current shared-memory systems, whichtends to be mostly in terms of coherence protocol statistics. This feature can gre a t l yincrease programmer productivity by guidingthem directly to the most critical communication. Violation reports can lead to a wide
variety of optimizations, many adapted fromtraditional parallelization techniques.
One of the most common optimizations is
the privatization of shared variables that cause
unnecessary violations. For example, we
improved SPECjbb by privatizing someshared temporary buffers. The most common
type of privatization, howe ver, was to privatize the loop-carried “sum” variable used as a
reduction target within loops that are otherwise good targets for parallelization. In our
statistics, the “sum” variables caused frequentviolations. Howe ver, many of the reduction
operations are associative, such as addition
and multiplication, and can there f o re be
reordered safely. Programmers can expose parallelism by privatizing a “sum” variable within each processor and then combining theprivate copies only at loop termination.
Although transactions should usually bemonolithic, it is sometimes more helpful tob reak large transactions into a transactionalgroup of two or more smaller transactions
which must execute sequentially on one
p ro c e s s o r. A programmer can use at_commit(0) call to mark each breakpoint
between the individual transactions. Because

NOVEMBER–DECEMBER 2004

99

MICRO TOP PICKS

Figure 4. Evaluation results: improvements in CMP configuration speedup provided by the various optimizations for four to
32 processors (a), and processor utilization breakdowns for the eight-processor case (b).

this operation splits the original transaction
into two separate atomic regions, the programmer must not place t_commits in the
middle of critical regions that must e xe c u t eatomically. Despite this limitation, the technique can help solve three problems:• In s e rting at _ c o m m i t takes a new rollback checkpoint, limiting the amount ofwork lost to a violation. This is helpful with
SPECjbb, which has large transactions andfrequent, unavoidable violations.
• It lets the processor commit and broadcast changes made by a transaction toother parallel processors early, when theoriginal transaction would only havebeen partially completed.
• Because each commit flushes the pro c e ss o r’s TCC write buffer, judicious
t_commits can pre vent or re d u c ebuffer overflows.

100

IEEE MICRO

Loop adjustment techniques can also be critical when optimizing code for TCC. Loop
unrolling, fusion, fission, and renesting are common parallelizing compiler tricks that can all
prove helpful. Although the techniques are thesame, the patterns used typically differ somewhat, with optimal transaction sizes being theusual goal. In addition, with loop nests a programmer must carefully choose the proper loop
nesting level to use as the source of transactions,because our model does not support nested
transactions. Outer loop bodies provide large,coarse-grained transactions, but these loop bodies can easily be too large, causing frequent buffer
overflows. On the other hand, using inner loop
bodies can make the transactions too small,incurring exc e s s i ve startup and commit ove rheads. Meanwhile, critical loop-carried dependencies can occur at any level. For example,
tomcatv’s inner loops had many dependencies
and were small, forcing us to use outer loops.

Figure 5. Overall speedup obtained using different hardware configurations.

Overall results
Figure 5 presents the best achieved speedups
for three TCC system configurations (ideal,
CMP, and SMP) using 4 to 32 processors.
While results are generally quite good, combinations of unavoidable violations andregions with insufficient parallel transactions,causing extra processors to idle, limit some
applications. In addition, large sequential code
regions limit Assignment and RayTrace.
For most benchmarks, CMP performanceclosely tracks ideal performance for all pro c e ssor counts. The CMP configuration is worse
than the ideal only when insufficient commit
bandwidth is available, which generally occurs
only with 32 or more processors. This causes
processors to stall while waiting for access tothe commit network. Si m i l a r l y, the SMP
TCC configuration achieves very little benefit beyond four- to eight-processor config u r ations because of its significantly reduced global
bandwidth. Of our applications, only Assignment, SPE C j b b, and tomcatv used more
p rocessors to significant advantage. This result
is still promising, howe ve r, because online
server applications such as SPECjbb would
most likely be the primary applications running on TCC systems larger than CMPs.
The most significant TCC hardware is the
addition of speculative buffer support. The
amount of state read and written by an average transaction must be small enough for local
buffering. Figure 6 shows the buffer size needed to hold the state read (Figure 6a) or written (Figure 6b) by 10, 50, and 90 percent ofeach application’s transactions, sorted by the
90-percent limit’s size, generally from 6 to 12
K bytes for read state and 4 to 8 Kbytes forwrite state. All applications have a few ve rylarge transactions that will ove rflow, but TCC
hardware should be able to achieve good performance as long as this does not occur often.

In the future, we plan to explore softwareand hardware techniques for scaling TCC
to large-scale parallel systems, so that programmers can use a single programming paradigm on any parallel machines, from small
CMPs to large SMPs. We will complement
this work by investigating dynamic optimization techniques that will help automate theotherwise time-consuming parallel performance tuning of larger and more complex
TCC programs. Ultimately, we see the combination of TCC hardware and highly automated TCC programming language support
as forming a new programming paradigm thatwill provide a smooth transition from today’ssequential programs to tomorrow’s parallels o f t w a re. This paradigm will be an import a n t
catalyst in transforming parallel processing
from a niche activity to one that is accessible
MICRO
to the average software developer.

Acknowledgments
This work was supported by US National
Science Foundation grant CCR-0220138 and
DARPA PCA program grants F29601-01-20085 and F29601-03-2-0117.
References

1. R. Rajwar and J. Goodman, “Transactional
Lock-Free

Execution

Programs,”

Proc.

of

10th

Lock-Based
Int’l

Conf.

Architectural Support for Programming
Langua ges

andOperating

Systems

NOVEMBER–DECEMBER 2004

101

MICRO TOP PICKS

Figure 6. State read (a) or written (b) by individual transactions, with a cache/buffer granularity of 64-byte lines, for 10, 50,
and 90 percent of the iterations.

(ASPLOS 02), ACM Press, 2002, pp. 5-17.
2. M. Herlihy and J. Moss, “Transactional
Memory: Architectural Support for LockFree Data Structures,” Proc. 20th Int’l Symp.
Computer Architecture (ISCA 93), ACM
Press, 1993, pp. 289-300.
3. J. Martinez and J. Torrellas, “Speculative
Synchronization: Applying Thread-Level
Speculation to Parallel Applications,” Proc.

Brian D. Ca r l s t rom is a PhD candidate incomputer science at Stanford University. His
re s e a rch interests include transactional programming models and other aspects of modern programming language design andimplementation. Carlstrom has a master’s
degree in electrical engineering and computer science from the Massachusetts Institute ofTechnology. He is a member of the ACM.

10th Int’l Conf. Architectural Support for
Programming Languages and Operating
Systems (ASPLOS 02), ACM Press, 2002,
pp. 18-29.
4. M.K. Chen and K. Olukotun, “The Jrpm
System for Dynamically Parallelizing Java
Programs,” Proc. 30th Int’l Symp. Computer

Vicky Wong is a PhD candidate in computerscience at St a n f o rd University. Her researchi n t e rests include parallel computer architectures and probabilistic reasoning algorithms.
Wong has an MS in computer science fro m
Stanford University.

Architecture (ISCA 03), IEEE CS Press, 2003,
pp. 434-445.
5. L. Hammond et al., “Programming withTransactional Coherence and Consistency(TCC),” Proc. 11th Int’l Conf. Architectural
Support for Programming Languages andOperating Systems (ASPLOS 04), ACM
Press, 2004, pp. 1-13.
6. L. Hammond et al., “Transactional Memory

Michael Chen performed this work while
completing his PhD in electrical engineering
at St a n f o rd Un i ve r s i t y. He is now a staff
researcher in the Programming System Lab at
In t e l’s Mi c ro p rocessor Re s e a rch Labs. His
research interests include optimization techniques for compiling high-level languages tothe Intel IXP network processors.

Coherence and Consistency,” Proc. 31st
Int’l Symp. Computer Architecture (ISCA 04),
IEEE CS Press, 2004, pp. 102-113.

102

IEEE MICROC h ristos Kozyrakis is an assistant professor ofelectrical engineering and computer scienceat Stanford University. His research interests
include architectures, compilers, and programming models for parallel systems ranging from embedded devices to supercomputer.
Kozyrakis has a PhD in computer sciencefrom the University of California, Berkeley.
Kunle Ol u k o t u n is an associate professor ofelectrical engineering and computer scienceat Stanford University. His research interests
include computer arc h i t e c t u re, parallel programming environments, and formal hard-ware verification. Olukotun has a PhD incomputer science and engineering from the
University of Michigan.
Direct questions and comments about thisarticle to Kunle Olukotun, Stanford University, Gates Bldg. 3A-302, St a n f o rd, CA,94305-9030; kunle@stanford.edu.
For further information on this or any othercomputing topic, visit our Digital Library at
http://www.computer.org/publications/dlib.

Get accessto individual IEEE Computer Society
documents online.
More than 100,000 articles
and conference papers available!
US$9 per article for members
US$19 for nonmembers

http://computer.org/publications/dlib/

NOVEMBER–DECEMBER 2004

103