Programming withTransactional Coherence and Consistency (TCC)
Lance Hammond, Brian D. Carlstrom, Vicky Wong, Ben Hertzberg, Mike Chen,
Christos Kozyrakis, and Kunle Olukotun
Computer Systems Laboratory
Stanford University
Stanford, CA 94305{lance, bdc, vicwong, elektrik, broccoli, kozyraki, kunle}@stanford.edu
ABSTRACTTransactional Coherence and Consistency (TCC) offers a way tosimplify parallel programming by executing all code within transactions. In TCC systems, transactions serve as the fundamental
unit of parallel work, communication and coherence. As eachtransaction completes, it writes all of its newly produced state toshared memory atomically, while restarting other processors thathave speculatively read stale data. With this mechanism, a TCCbased system automatically handles data synchronization correctly,
without programmer intervention. To gain the beneﬁts of TCC,
programs must be decomposed into transactions. We describe twobasic programming language constructs for decomposing programs
into transactions, a loop conversion syntax and a general transaction-forking mechanism. With these constructs, writing correct parallel programs requires only small, incremental changes to correct
sequential programs. The performance of these programs may theneasily be optimized, based on feedback from real program execution, using a few simple techniques.

Categories and Subject Descriptors

C.5.0 [Computer System Implementation]: General.
D.1.3 [Programming Techniques]: Concurrent Programming— parallel programming.

General Terms

top platforms. Multiprocessor systems provide a good match to thecoarse-grain parallelism available in applications such as enterpriseservices, bio-computing, telecommunications, and multimedia.
Nevertheless, the key factor limiting the potential of parallel architectures is the complexity of parallel application development.
Existing parallel programming approaches require the programmer
to manage concurrency directly by creating and synchronizing parallel threads. The difﬁculty stems from the need to achieve the often
conﬂicting goals of functional correctness and high performance.
With shared memory systems [25], a small number of coarse-grain
locks makes it simpler to correctly sequence accesses to variables
shared among parallel threads. On the other hand, more numerous
ﬁne-grain locks often allow higher performance by reducing theamount of time wasted by threads as they compete for access to thesame variables, although the larger number of locks used usually
incurs more locking overhead. A similar trade-off exists with message-passing programming [10]. High performance requires earlyscheduling of all communication events, while correct execution
requires a programmer to carefully match send and receive requests
across threads, even for applications with dynamic and unpredictable communication patterns. Managing this trade-off makes parallel programming more time-consuming and error-prone than writing an equivalent sequential program.

With uniprocessor systems running into instruction-level parallelism (ILP) limits and fundamental VLSI constraints [2], parallel architectures provide a realistic path towards scalable performance byallowing one to take advantage of thread-level parallelism (TLP) in
more explicitly distributed architectures. Single-board and singlechip multiprocessors are becoming the norm for server [18, 31] andembedded [5] computing, and are starting to appear even on desk-

This paper introduces parallel programming techniques for transactional coherence and consistency (TCC) systems [12]. TCC relies
on programmer-deﬁned transactions as the basic unit of parallel
work, communication, memory coherence, memory consistency,
and error recovery. TCC hardware speculatively executes transactions in parallel using local buffering. After a transaction completes, the hardware commits all its writes to shared memory as
an atomic unit. At this point, the writes become visible to othertransactions, which may rollback due to dependency violations.
TCC simpliﬁes parallel hardware design by eliminating the needfor cache line ownership tracking in the cache coherence protocol.
It also replaces the need for numerous small, low latency messages
for cache coherence with fewer large, high-bandwidth messages foratomic commit.

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 proﬁt or commercial advantage and that copies
bear this notice and the full citation on the ﬁrst page. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior speciﬁc
permission and/or a fee.
ASPLOSʼ04, October 7–13, 2004, Boston, Massachusetts, USA.
Copyright 2004 ACM 1-58113-804-0/04/0010...$5.00.

TCC simpliﬁes parallel programming by eliminating the need for
manual orchestration of parallelism using locks or messages. Programmers simply need to divide computation into potentially parallel transactions and then specify any ordering dependencies thatmust be observed between those transactionsʼ commits. TCC hardware guarantees correct synchronization always occurs by automatically restarting transactions on dependency violations. Therefore, decomposing code into transactions is primarily a matter of

Performance, Design, Languages.

Keywords

Transactions, feedback optimization, multiprocessor architecture.

1. INTRODUCTION

performance tuning, and not a matter of correct�����������
ness. The use of a single abstraction for paral������
lelism, communication, and synchronization
also simpliﬁes performance tuning by allowing ��
programmers to use simple transaction statistics(violations, buffer requirements, overheads) to
identify and remove performance bottlenecks.
To our knowledge, this work is the ﬁrst proposal
for parallel programming using transactions as
the central programmer abstraction for both parallelism and synchronization in a shared mem- �����������
ory system, completely eliminating the need for ���������
locks and allowing for much more automated ��������
sequencing of parallel code regions. The spe������
ciﬁc contributions of this paper are:������

��

Stores
Only

Loads andStoresProcessor Core

Local Cache Hierarchy�������
����

Write
BufferRenameRead M

V

Tag

Node
#0

Data

���� ���
��������������

Snoopingfrom other nodes

Commits

Commit Control
Node 0:Node 1:
Node 2:

Sequence

Phase������
to other nodes• Transactional programming constructs: We������
identify two methods for deﬁning transactions and specifying commit orders. The ﬁrst ��������
������
Broadcast Bus or Network
one is appropriate for loop-based code, while
the second one resembles general thread
Figure 1: a) A transaction cycle (time ﬂows downwards) andforking. The constructs can express ordered, partially ordered,b) a diagram of sample TCC-enabled hardware.
and unordered commit successions. We show that the two conAfter this permission is granted, the processor can take advantage
structs can express the parallelism in a diverse set of C and Javaof high-bandwidth system interconnect to broadcast all writes forapplications, ranging from array computations to an online servthe entire transaction out as one large packet to the rest of the syser benchmark.
tem. Meanwhile, the local caches in other processors snoop on• Transactional performance tuning: We show how the programthese store packets to maintain coherence in the system. Snoopmer can tune application performance using feedback on transing also allows them to detect when they have used data that has
action behavior (violations, buffering requirements, overheads)
subsequently been modiﬁed by another processor — a dependence
obtained during initial, unoptimized runs of the program. We
violation. Combining all writes from the entire transaction together
propose a set of simple source code optimizations that can leadminimizes the latency sensitivity of this scheme, because fewer into additional performance improvements without affecting apterprocessor messages and arbitrations are required, and because
plication correctness.
ﬂushing out the writes is a one-way operation. At the same time, thecommit operation can also be leveraged to provide inherent syn• High application performance: We use simulation to demonchronization and a greatly simpliﬁed consistency protocol, since
strate that, despite its simplicity, parallel programming with
we have to control only the ordering between entire transactions
TCC allows excellent speedups for chip multiprocessor (CMP)
instead of individual loads and stores.
across a range of 4–32 processors and board-level symmetricmultiprocessor (SMP) systems for 4–8.
This continual cycle of speculative buffering, broadcast, and (potential) violations, described in further detail in [12], allows us to
The rest of the paper is organized as follows. Section 2 provides anreplace both conventional coherence and consistence protocols:
overview of the operation of a TCC-based parallel system. Section
3 introduces TCC programming techniques, and discusses correct• Consistence: Instead of using rules that control ordering beness and performance tuning. In Section 4, we demonstrate the use
tween individual memory reference instructions, as with mostof the programming techniques in parallelizing a diverse set of apcoherence schemes, TCC just controls ordering between transplications. Section 5 discusses related work and we conclude inaction commits. This can drastically reduce the number of latenSection 6.
cy-sensitive arbitration and synchronization events required by
low-level protocols in a typical multiprocessor system. Imposing an order on the transaction commits and backing up uncom2. TCC HARDWARE OVERVIEW
mitted transactions if they have speculatively read data modiﬁed
Processors operating in a TCC-based multiprocessor continuallyby other transactions effectively lets the TCC system provide an
execute speculative transactions, using a cycle illustrated in Figillusion of uniprocessor execution to the sequence of memoryure 1a on multiprocessor hardware with additions similar to thosereferences generated by software. As far as the global memory
depicted in Figure 1b. A transaction is a sequence of instructions
and software is concerned, all memory references from a transmarked by software that is guaranteed to execute and complete
action that commits earlier happened “before” all of the memory
only as an atomic unit. Each transaction produces a block of writes
references of a transaction that commits afterwards, even if their
which are buffered locally while the transaction executes and are
actual execution was interleaved in time, because all writes fromthen committed to shared memory only as an atomic unit, after thea transaction become visible to other processors only at commit
transaction completes. Once the transaction is complete, hardware
time, all at once.
must arbitrate system-wide for the permission to commit its writes.

• Coherence: Stores are buffered and kept within the processor
node for the duration of the transaction in order to maintain theatomicity of the transaction. No conventional MESI-style cache
protocols are used to maintain lines in “shared” or “exclusive”
states at any point in the system, so it is legal for many processor
nodes to hold the same line simultaneously in either an unmodiﬁed or speculatively modiﬁed form. At the end of each transaction, the broadcast notiﬁes all other processors about whatstate has changed during the completing transaction. During thisprocess, the other 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 if they may have usedshared data too early. If they have read any data modiﬁed by thecommitting processor during their current transaction, they areforced to restart and update their copy of the data. This protects
against true data dependencies. At the same time, data antidependencies are handled simply by the fact that later processors
will eventually get their own turn to ﬂush out data to memory.
Until that point, their “later” results are not seen by transactions
that commit earlier (avoiding WAR dependencies) and they areable to freely overwrite previously modiﬁed data in a clearly sequenced manner (handling WAW dependencies in a legal way).
Effectively, the simple, sequentialized consistence model allows
the coherence model to be greatly simpliﬁed.
Transactional hardware hides many of the difﬁculties associatedwith parallel programming from typical programmers, but in orderto get good performance programmers do need to keep a few basic
goals in mind when dividing applications into transactions:• Minimize Violations: Programmers should try to avoid paralleltransactions that read and write the same variables frequently, inorder to avoid costly discarding of work that occurs after violations. Keeping transactions reasonably small, to minimize theamount of work lost when violations occur, can also help.
• Minimize Transaction Overhead: On the other hand, verysmall transactions should generally be avoided when possible
because of the overhead associated with starting, ending, andcommitting transactions.
• Avoid Buffer Overﬂows: TCC hardware must buffer all writes
made by a processor during a transaction. Our previous resultsin [12] indicate that most applications naturally divide intotransactions of reasonable size, but when very large transactions
occur it is possible to overﬂow the ﬁnite buffer space. While
the system is always able to handle these situations correctly
when they occur, simply by having the processor request accessto the broadcast network and then hold it while writing throughdirectly to memory for the remainder of the transaction, this canobviously have a negative impact on performance and should be
avoided if possible.
Other than these few factors, which mostly affect performancetuning, programmers can generally ignore the hardware. This contrasts well against conventional parallel systems, where they would
have to carefully consider issues such as the layout of data in themachineʼs memory, latency and bandwidth requirements for allcommunication, and other machine-speciﬁc factors that can havean impact on both correctness and performance. This allows them
to focus more on writing correct code.

3. PROGRAMMING TECHNIQUESTCC parallelization is a series of simple steps that requires only a
few new programming constructs. This process is simpler than parallelization with conventional threaded models because it reduces
the number of code transformations needed for typical parallelization efforts. In particular, it allows programmers to make informed
tradeoffs between programmer effort and performance. Basic parallelization can quickly and easily be done in a way that is guaranteed to be safe. Programmers can then use feedback obtained fromviolation reports produced during initial parallel program execution
to insert program reﬁnements and constraint relaxation in order toget signiﬁcantly greater speedups. In a simpliﬁed form, programming with TCC can be summarized as a three-step process:• Divide into Transactions: The ﬁrst step in the creation of a parallel program using TCC is to coarsely divide the program into
blocks of code that can run concurrently on different processors. In this respect, parallelizing for TCC is very similar to conventional parallelization, which also requires that programmers
ﬁnd and mark parallel regions. However, the actual process is
simpler with TCC because the programmer does not need toguarantee that parallel regions are independent, since the TCC
hardware will catch all dependence violations during execution.
The interface presented in this section allows programmers to
divide their program into parallel blocks on loop iterations andby forking of transactions. Currently, our interface supports only
“ﬂat” transactions, and not “nested” ones [9].
• Specify Order: The default ordering for transactions is to havethem commit results in the same order as the original sequential program, since this guarantees that the program will executecorrectly. However, if a programmer is able to verify that thiscommit order constraint is unnecessary, then it can be relaxedcompletely or partially in order to provide better performance.
The interface also provides ways to specify the ordering constraints of the application in useful ways.
• Performance Tuning: After transactions are selected and ordered, the program can be run in parallel. The TCC system can
automatically provide informative feedback about where violations occur in the program, which can direct the programmer toperform further optimizations.
While the interface is described in C, it should be noted that these
constructs can be readily adapted to any programming language(for example, we have also adapted it to Java) in order to allow it totake advantage of TCCʼs features.

3.1. Loop-Based Parallelization

The parallelization of loops will be introduced in the context of asimple sequential code segment that calculates a histogram of 1000
integer percentages using an array of corresponding buckets:
int* data = load_data();
int i, buckets[101];/* input */for (i = 0; i < 1000; i++) {buckets[data[i]]++;}
print_buckets(buckets);/* output */Unlike the TCC version, if any of this locking code isomitted or buggy, then the program may fail—and notnecessarily in the same place every time—signiﬁcantly
����
��
���
�
�
��
complicating debugging. Debugging is especially hard if������ � � ���� � � ��the errors only happen for patterns of memory accesses
���
��
���
that occur only rarely, due to non-deterministic interpro�������
cessor timing. The situation is potentially even trickier�����������
������
if multiple locks need to be held simultaneously within���a critical region, because one must be careful to avoid
locking sequences that may deadlock [25]. It is clear that
Figure 2: Illustrations of scheduling for transactional loops,
TCC
can
both
simplify the parallelization of loops and reduce the
chunked loops, and a simple fork example. The numbers in cʼsruntimeoverhead
associated with conventional locking and syntransactions are sequence:phase.
chronization structures—since they largely disappear.
�����

���

�����

���

��

���

The compiler interprets this program as one transaction, so it exposes no parallelism to the underlying TCC hardware. The obvious
candidate for parallelization is the for loop.
. . .
t_for (i = 0; i < 1000; i++) {. . .

The only thing that changed is the for loop keyword, which has
been replaced with its transactional version, t_for. With thissmall change, we now have a parallel loop that is guaranteed to
execute the original sequential code correctly. Each iteration of theloop body will now become a separate transaction that will commit
in the original sequential order, in a pattern like that in Figure 2a.
This behavior preserves the original sequential order of the code by
deﬁning an ordering between the transaction commits. Althougha later iteration may run in parallel with an earlier one, it cannot
commit its transaction out of order. Therefore, if an earlier iteration
updates a histogram bucket which is also updated by later iterations, when the earlier iteration commits, the TCC hardware willcatch any dependence violations with data used by the “later” parallel iterations and restart them, forcing them to re-execute using
updated data in order to preserve the original sequential semantics.
For example, there may occasionally be collisions during accessto the histogram bins in this program. TCC will handle these automatically, without any extra code.
The programmer ease-of-use of this paradigm compares favorably with similar schemes previously proposed. It is similar to
the thread-level speculation (TLS) pfor construct [29], but does
not allow forwarding of modiﬁed data between active speculativetransactions. A conventionally parallelized system, however, would
require an array of locks to protect the histogram bins, resulting in
our example growing to something much uglier, with signiﬁcant
locking code, like this:int* data = load_data();
int i, buckets[101];/* Deﬁne & 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]]);buckets[data[i]]++;UNLOCK(bucketLock[data[i]]);}print_buckets(buckets);���However, this simple application of TCC will not always result ingood performance, so further modiﬁcation may be desired. The ﬁrst
problem in this example stems from the size of the loop transactions. We now have 1002 transactions, one for the code before theloop, 1000 for the loop iterations, and 1 for the code after the loop.
However, the loop body transactions are very small. To amortize
the overheads associated with starting and ending transactions,t_for can be replaced with t_for_n, where the “n” allows thenumber of iterations to be included in a transaction to be speciﬁedby the programmer:. . .
t_for_n (i = 0; i < 1000; i++; 20) {. . .

Now we we have “chunked” 1000 transactions into 50 transactions,each executing 20 iterations of the original loop, for a total of 52
transactions, as is depicted in Figure 2b. This type of transformation
is equivalent to unrolling the original loop and applying a t_for
to the unrolled loop. A compiler or runtime environment shouldbe able to perform this optimization automatically, since merging
transactions while preserving ordering always maintains program
correctness. By specifying the unrolling factor as a variable expression, the degree of “chunking” may even be set at run time, in response to characteristics of the input dataset.
Although sequential ordering is generally useful because it guarantees correct execution, in some cases—such as this histogram example—it is not actually required for correctness. In this case, there
are no dependencies among the loop transactions except throughadditions to histogram elements, which is an associative operationthat does not demand any particular ordering. When programmers
can determine that this is the case, they can use slight variations
on the basic t_for construct, t_for_unordered and t_for_
unordered_n, to allow the main loop body transactions to run
and commit in any order. While the transaction lengths are equalin this example, allowing unordered commits is most useful when
the transaction lengths are dynamically variable, because it will
decrease unnecessary time spent waiting for commit permission
between transactions.
The test clause of any t_for_unordered has an additional
requirement that it must be possible to determine the termination
result in a distributed manner, so that all processors will be able
to detect it, no matter what order they complete. For example, in aloop with an i++ incrementor, a test clause of “i < 1000”
would be ﬁne, since all processors will detect the end-of-loop condition after i reaches 1000, but “i != 1000” would result in onlya single processor detecting the termination condition because iwould subsequently be incremented to 1001.
For loops with an indeterminate number of loop iterations, there
is also a t_while loop structure, which is similar to a standard
while loop, and comes in the same four ﬂavors as t_for, withthe same restrictions:t_while<_mode> (i < 1000) {. . . is equivalent to . . .

t_for<_mode> (; i < 1000;) {3.2. Fork-Based Parallelization

While most sequential programs can be easily divided into parallel transactions using only the simple parallel loop API, there aresome less structured programs that need to generate transactions
in a more ﬂexible manner. Therefore, in addition to the loop parallelization, the TCC programming interface provides t_fork,
a transactional fork similar to most conventional thread creation
APIs. The interface is centered around a standard C function thatstarts a new, parallel transaction:
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 off a child function of the form: */void child_function(void *input_data);

This call forces the “parent” transaction to commit, to guaranteethat we cannot roll back and “cancel” the t_fork, and then creates two completely new, parallel transactions. One (the “new parent”) continues execution of the code immediately following thet_fork, while the other (the “child”) starts executing a child_function-style function at child_function_ptr with the
input pointer input_data. Other input parameters control ordering of forked transactions in relation to other transactions, and are
discussed in more detail below in Section 3.3.
To demonstrate this function, consider a simple example where wewant to simulate a two stage processor pipeline in parallel. This issimulated using the functions opcode = i_fetch(PC) for
instruction fetch, increment_PC(opcode, PC) to adjust the
PC and handle branching, and execute(opcode) to execute
other instructions. The “child” transaction executes each instruction while the “new parent” transaction goes ahead and fetches thenext one:/* Deﬁne an ID number for the EX sequence */#deﬁne EX_SEQ 1/* Initial setup */int PC = INITIAL_PC;
int opcode = i_fetch(PC);/* Main loop */while (opcode != END_CODE){
t_fork(execute, &opcode, EX_SEQ, 1, 1);
increment_PC(opcode, &PC);
opcode = i_fetch(PC);}This example creates a sequence of overlapping transactions likethose in Figure 2c. While it is more complicated to use than thelooping structures, t_fork gives enough ﬂexibility to divide a
program into transactions in virtually any way. It can even be used
to build the various t_for and t_while constructs, althoughthose are useful so often that it is helpful to have the fundamental
constructs described previously.

3.3. Explicit Transaction Commit Ordering

When using fork-based parallelization and some loop-based parallelizations, the simple “ordered” and “unordered” ordering modes
may not be sufﬁcient. For example, a programmer may desire aparallel loop that is only partially ordered, executing unordered iterations most of the time, but occasionally forcing one transaction
or another to complete before others. In our experience with loopbased TCC programming, these ordering requirements are usuallyrare, but support must be provided for the occasional exception. On
the other hand, forked transactions usually require explicit orderingof some sort.
In order to provide ordering support, we deﬁne a simple interface
that controls transaction ordering by assigning two parameters toeach transaction: the sequence and phase of transactions. These are
two numbers assigned to each transaction that control the orderingof transaction commits. The sequence speciﬁes which transactions
require that commits must be ordered in relation to each other (i.e.,
have the same sequence ID number) and which are completely
independent in their ordering (i.e., have a different sequence ID).
The child_sequence_num parameter in a t_fork call canbe used to produce two sequence groups of transactions that areordered independently. When this is a positive integer, a “child”
transaction with the new sequence number is produced, while the“new parent” transaction continues to use the old sequence number.
Alternatively, the “child” and “new parent” may also be kept within
the same ordering sequence using the T_SAME_SEQUENCE constant. Within each sequence, the phase indicates the relative “age”
of each transaction. TCC hardware will only commit transactionsin the oldest active phase (lowest value) from within any sequencethat is executing on the system. Using this notation, an ordered loop
is just a sequence of transactions with the phase incremented by
one every time, while an unordered loop has transactions all withthe same phase number.
Unlike the simpler loop constructs, a t_fork call allows complete control over the phase of the subsequent new parent andchild transactions using the parent_phase_increment andchild_phase_increment parameters, respectively. For the
new parent transaction, this value is always a phase increment overthe phase of the parent. For the child, this can either be a phaseincrement over the parent, if we use the T_SAME_SEQUENCE constant for selecting the sequence, or over the phase of the youngest
active transaction already present within the childʼs sequence, if
a sequence is explicitly supplied. For example, in the instruction
simulator example from Section 3.2, we speciﬁed a phase increment of 1 for the “new parent” to ensure that the PC increments
performed by the various “parent” transactions were all ordered
properly within the parent sequence, and also speciﬁed an increment of 1 for the “children” so the various EX stages were required
to commit their results to memory in the order they were forked
within the separate EX_SEQ sequence.

More arbitrary phase ordering of transactions can also be imposedusing the following two calls:
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 witha phase incremented by the phase_increment parameter. The
most common phase_increment parameter used is 0, which
is simply used to take a new checkpoint and to ﬂush out the write
buffers, at the programmerʼs request. However, it can also be usedwith a phase_increment of 1 or more in order to force an explicit transaction commit ordering. One use for this is to emulate
a conventional barrier among all transactions within a sequence
using transactional semantics. Unlike normal barriers, deadlock is
not possible with this interface, as the “oldest” transaction in the sequence can always commit. Of course, these t_commits can stillcause “fast” processors to stall while waiting to commit the transaction following the t_commit, potentially reducing performance.
This stall time is usually much less than that caused by conventional barriers, however, due to the fact that processors only stall ifthey get more than a full transaction ahead of their slower partners.
In essence, these “transactional barriers” automatically act like thespeculative barriers described in [26].
The t_wait_for_sequence call performs the same function as a t_commit, but also waits for all transactions within thewait_for_sequence_num sequence to complete before starting the next new transaction in the callerʼs sequence. This call isusually used to allow a “parent” sequence of transactions to wait
for a “child” sequence to complete, similar to a thread join inconventional parallel programming. For example, the instruction
simulator example from Section 3.2 requires the following code
within the increment_PC routine to ensure that data-dependent
branches are properly executed:
if (opcode == ANY_BRANCH_INSTRUCTION){
t_wait_for_sequence(1, EX_SEQ);
execute_branch(opcode, &PC);}
else
PC = PC + 1;

In this case, if the instruction is a branch, then the “parent” transaction sequence, which is handling the PC increments, is forced
to wait until all previously initiated instruction simulations in the
EX_SEQ sequence have completed, so that the branch instruction
may only execute with the properly updated input values. For thecommon case of a non-branch instructions, however, the parent
and child instruction sequences are allowed to commit transactions
asynchronously, allowing us to take advantage of possible parallel
speedup.

3.4. Performance Tuning

After a programmer divides a program into transactions with thefundamental TCC language constructs, most problems that occur
will tend to be with performance, and not correctness. Since transactions automatically ensure that accesses to variables occur atomically, the only two ways that a programmer can write an incorrect

TCC program are either by relaxing commit scheduling constraints
too much or by accidentally putting a transaction break in the middle of a critical region. The former error can be avoided simply byalways using explicitly ordered transactions if there is any doubt
as to whether or not transactions can be safely executed in an unordered manner. Conventional parallel programming requires not
only that one avoid breaking critical regions, but also that all critical regions be explicitly marked with locking code, a much moreerror-prone task than the TCC alternative.
Because it is very easy to get a program to at least run in parallel
under TCC—although perhaps inefﬁciently—the usual way that
TCC programs are optimized is to use actual execution to test initial parallelization attempts. Results from these initial runs can thenprovide useful feedback to aid further optimization through reportssummarizing all violations that occur. These violation reports summarize time lost to transaction pairs causing conﬂicts, including information about the individual load-store pairs and data addresses
that are violating. These addresses can be fed into a symbolic debugging environment like gdb to determine which variables andvariable accesses caused the violations. This report can be summarized based upon the amount of execution time lost to each violation in order to prioritize and pinpoint the most important violation
problems. This information tells programmers exactly which variables—and even which accesses to them—are limiting parallelism,
unlike current shared memory systems, that tend to give feedback
mostly in terms of coherence protocol statistics. This information
can greatly increase programmer productivity by automatically directing programmers to the data dependencies that cause the mostviolations between transactions, instead of making them pore over
all of the code in a program to determine the critical dependencies manually. Just as helpful, programmers may simply choose
to ignore minor dependencies that only occur rarely, leaving these
unimportant dependencies for the transactional hardware to handle
with an occasional violation when they do occur. Information about
load imbalance is also reported in terms of the time spent waiting at
the end of each transaction deﬁned by the source code.
Violation and waiting reports from initial program runs might lead
only to some ﬁne tuning of how certain variables are used, or it
could lead to more major code changes. A common technique is tosimply combine small transactions into larger ones (usually using
the _n options). The program might also need some minor code
restructuring to remove false sharing between transactions or code
motion to allow better partitioning of transactions in order to avoid
load imbalance or to reduce the amount of serial code between parallel regions, since a TCC system is still subject to Amdahlʼs law
speedup limitations from such code. During the course of parallelizing several applications, we also found that several common
techniques were very useful, many adapted from ones also usedduring traditional parallelization:
Reduction Privatization: Operations that reduce values to a loopcarried sum variable are frequently used within loops that are otherwise good targets for transactional parallelization. These operations show up in our statistics through frequent violations on thesum variable. However, many of the operations are associative,
such as addition, multiplication, and minimum/maximum, and cantherefore be reordered to maximize parallelism. By privatizing thesum variable within each processor and only combining these variables to a sequential sum after the end of the loop, signiﬁcant paral-

lelism can be exposed. This is a process that can often be automatedin ﬂoating-point applications. The low-level runtime environment
needs to provide only a pair of functions that return system parameters (int t_processor_count() and int t_processor_id()) to support this functionality.

Table 1: Key parameters of our simulations. All cycle values
are in CPU cycles.

Shared Buffer Privatization: While our TCC compilation andhardware could automatically privatize most stack variables, someloops use large temporary buffers elsewhere in memory. In thesecases, it may be necessary to allocate N buffers for N parallel processors in order to avoid spurious violations when unrelated variables are allocated at the same addresses within a shared buffer.
The same techniques used to generate privatized sum variables for
reductions can also be used to provide private temporary buffers.
Hardware, compiler, or runtime environment support to automate
privatization is a topic for further research. Without this support, it
was necessary to manually privatize some buffers in our selectionof applications.

Ideal

Loop Level Adjustment: We may choose to parallelize at different
levels of loop nests in order to take advantage of the characteristics
that different levels may offer. Outer loops provide large granularity, but can sometimes get too large, because realistic TCC systems
have ﬁnite amounts of per-transaction buffering. Inner loops canoften be too small to effectively use without combining iterations,due to startup/commit overheads. Either may have critical loop-carried dependencies that prevent it from being a good target.
Loop Fusion/Fission/Renesting: In order to help make better transactions, any of these common parallelizing compiler tricks that adjust the execution pattern of loops may prove helpful. While thetechniques are the same, the patterns used are usually somewhat
different, with “optimal” transaction sizes being the usual goal.
Splitting Transactions into Transactional Groups: Normally, transactions do not commit results until after they complete entirely.
While this is often desirable behavior, there are times when it ismore helpful to break “obvious” transactions, such as loop iterations, into two or more parts. This can be performed simply by using a t_commit(0) call to break the transaction into two smallertransactions. We call the resulting transactions, that are forced to
execute one after another on the same processor, a “transactionalgroup.” Because other, parallel transactions may commit results
between the hardware transactions within a transactional group,
the programmer must ensure that no t_commits are placed in the
middle of critical regions of the code that must execute atomically,or incorrect execution may result. Despite this limitation, we foundthat this technique was quite helpful in solving three different kindsof problems. First, inserting a t_commit takes a new rollback
checkpoint, limiting the amount of work that can be lost if a violation occurs. This can be very important for applications with long“obvious” transactions and frequent violations. Second, ﬂushingout the write state clears the TCC write buffer associated with theprocessor. If an applicationʼs transactions tend to produce a lot of
data, then judicious t_commit operations can prevent the systemserialization and slowdown that would otherwise occur when write
buffers overﬂow. Finally, it may be desirable to update changes toglobal memory as early as possible, and a t_commit can ﬂush
out new changes to the globally visible state at any point within atransactional group, providing a sort of “forwarding” of modiﬁed
data to other transactions running in parallel.

Inter-CPU
Bandwidth(bytes/cycle)

CommitOverhead(cycles)

Violation
Delay(cycles)“Perfect” TCC multiprocessor

∞

0

0

CMP

Realistic multiprocessor, if on a single chip

16

5

0

SMP

Realistic multiprocessor, if on a board

4

25

20

SystemDescription

4. PERFORMANCE EVALUATION

In order to evaluate the utility of the transactional programming
constructs, we used them to parallelize C and Java applications froma variety of domains. Then, we used simulation to evaluate and tune
their performance for large and small-scale TCC systems.

4.1. Methodology

Our evaluation infrastructure includes an execution-driven simulator that models a processor that executes at a ﬁxed rate of one
instruction per cycle. The simulator produces an execution trace
for all transactions in the program, including ones from sequential
code regions, and captures statistics for all loads and stores except
for stack references, which are guaranteed to be private within eachtransaction. We then use a trace analyzer to simulate the behaviorof running transactions in parallel on a parameterized TCC systemthat includes multiple processors (4–32) connected through a network that supports broadcasts (e.g., a bus). We do not model further details of the core processor pipeline in this study because the
TLP-oriented beneﬁts of TCC parallelization are fairly orthogonal
to the acceleration of each individual transactionʼs execution that
occurs when using ILP techniques within individual processors. As
a result, ILP-based execution of individual transactions faster (orslower) than 1.0 instructions per cycle should simply improve (ordecrease) TCC system performance proportionally, at least until theavailable commit packet broadcast network is saturated, when no
further improvement from either ILP or TLP is possible. In addition to varying the number of processors, we also vary the value of
three key TCC system parameters: the amount of bandwidth available on the network, the overhead of arbitration for commit order,
and the latency of violation recovery. Table 1 presents the values
selected for the parameters in order to describe three potential TCC
conﬁgurations: ideal (inﬁnite bandwidth, zero overheads), singlechip/CMP (high bandwidth, low overheads), and single-board/SMP(medium bandwidth, higher overheads).
Table 2 presents the applications used for this study and the transaction programming constructs employed to parallelize them. We
selected these applications because they represent a diverse set ofconcurrency patterns including dense loops (LUFactor), sparseloops (equake), task parallelism (SPECjbb), and producer-consumer parallelism (MPEGdecode). This diversity is important toassess the usefulness and completeness of TCC programming. For
the Java applications, we used the Kaffe JVM [38] within the execution driven simulator.
The Kaffe JVM required some simple modiﬁcations to be transaction friendly. We removed Java monitors used for synchronizedTable 2: Characteristics of applications used for our analysis.
SourceLanguage

BenchmarkApplication Description

Source

Input

Java

Assignment

Resource allocation solver

jBYTEmark [6]MolDynN-body code modelingparticles

LUFactorC

Lines of
Code

Primary TCC
Parallelization

51x51 array556

Loop: 2 ordered, 9
unorderedJava Grande [17]2048 particles

615

Loop: 9 unordered

LU factorization and triangular solve

jBYTEmark [6]101x101 matrix

516

Loop: 2 ordered, 4
unordered

RayTrace

3D ray tracer

Java Grande [17]150x150 pixel
image

1,233

Loop: 9 unordered

SPECjbb

Transaction processing
serverSPECjbb [34]230 iterations
w/o random

27,249

Fork: 5 calls (one pertransaction type)

art

Image recognition / neuralnetwork

SPEC2000 FP [35]

ref.1

1,270

Loop: 11 unordered& chunked

equakeSeismic wave propagation
simulation

SPEC2000 FP [35]

ref

1,513

Loop: 3 unordered

tomcatv

Vectorized mesh generation SPEC95 FP [35]256x256

346

Loop: 7 unordered

MPEGdecodeVideo bitstream decoding

mei16v2.m2v

9,834

Fork: 1 callMediabench [24]Table 3: Summary of optimizations used in our applications. Results are for the 8 processor CMP conﬁguration.

BenchmarkAssignment

MolDyn

LUFactor
RayTrace

SPECjbbart

equaketomcatv

Optimization

Cumulative
Lines
Cumulative
ChangedSpeedup

Useful%Wait%

Violate%Idle%

Median / Mean
Transaction Size
(instructions)

75% Write
State (64B
lines)

Base

11

2.58

32.3

11.9

51.9

4.0

+ unordered

20

2.75

34.4

3.7

55.3

6.6

+ private reductions

32

6.46

80.8

9.7

—

9.5

Base

4

5.93

74.1

8.6

1.9

15.4

+ unordered

8

6.33

79.1

2.0

2.0

16.8

+ private reductions

20

6.46

80.8

2.1

—

17.2

Base

6

5.03

62.9

9.3

15.9

12.0

+ unordered

10

5.24

65.5

7.3

14.4

12.9

Base

1

3.73

46.6

19.0

0.4

34.0

+ unordered

2

4.28

53.5

3.2

1.3

42.0

+ private reductions

6

4.48

56.0

3.4

—

40.6

Base + objCount

13

1.87

23.4

—

37.7

38.9

—

148,244

195+ privatization

33

3.87

48.4

0.1

46.3

5.2

—

144,054190+ two t_commit

35

5.62

70.3

0.2

22.9

6.6

—

76,72894

Base (chunked loop)

11

1.05

13.1

1.8

82.4

2.8

1777

33

+ private reductions

101

6.21

77.6

9.1

—

13.3

1781

33

+ loop fusion

113

6.91

86.4

0.6

—

13.0

2065

33

Base

6

3.60

45.6

0.4

54.0

—

471

2

+ t_commit

8

7.38

91.2

4.6

4.2

—

146

1

+ loop fusion

12

7.49

91.5

4.2

4.3

—

131

180

1

Inner loop (chunked)

16

2.26

28.3

4.6

57.9

9.2

59

88

3

Outer loop

7

7.83

97.9

0.3

—

1.8

12,268

14,584

97

454

5.89

73.6

17.1

0.1

9.2

—

626,060

154

MPEG-decode Base + prescanning

1
850

1097

1
1
0

76

77

0
0

44

459

2
2
2

147

167

2
2

1880

130

��
���� ������
��������

�������

���������������
�����������
���������

�

����
�
�

� �� ��

�� �� ��

�� �� ��

�� �� ��

�� �� ��

�� �� ��

�����������

��������

��������

������

����������� �� ��

�������� �� ��
�������

�� �� ��

�����������

Figure 3: Improvements in CMP conﬁguration speedup provided by the various optimizations, for varying numbers of processors.
The 8-processor column graphs values from column 4 of Table 3.
��������� ��������

�
����
����

��������
�������

���������
��������������

������

��������

�������

���������

�������

���������������

�����������

��������������

��������������

��������������

���������������

����������

������������

���������������

�����������

���������������

���������������

�����������

���������������

�����������

���������������

������������

Figure 4: How the time breakdowns changed as optimizations were applied to the 8-processor CMP conﬁguration. These are thevalues from columns 5–8 of Table 3, in graphical form.
objects, because transactions can be used to inherently guarantee
atomic access. We also modiﬁed memory allocation routines toeliminate the chance of spurious violations caused by multiple processors accidentally allocating the same portion of the heap as different data objects simultaneously. This just required dividing theotherwise shared heap into separate “allocation pools” for each processorʼs memory routines, a change that is also necessary to build
efﬁcient non-transactional parallel memory allocation routines.

4.2. Application Studies

Table 3 presents the performance results for the 8 processor CMP
conﬁguration. For each benchmark, it lists the number of lineschanged and the speedup over a single processor system. Figure
3 shows the same speedups graphically, along with ones for CMP
conﬁgurations with different numbers of processors. Table 3 andFigure 4 also break down the average execution time on each processor into time executing useful transactions, time waiting fortransactions to commit, time spent on transactions that violate, andtime idling due to lack of parallelism (i.e. sequential code). We also
list the 75th percentile of the buffer space required for a transaction(reported in 64-byte cache lines). Most applications require lessthan one Kbyte of write buffer. However, even the largest transactions for an unoptimized version of SPECjbb require less than 32
KBytes, which are reasonable to implement in modern processors.
Further analysis of buffer space requirements is in [12].
Table 3 and the two ﬁgures include both the baseline results andthose after applying optimizations described in Section 3. The baseline results show signiﬁcant speedup with minimum modiﬁcations
to the sequential code, but are typically not optimal. We obtained
feedback information about transaction violations and overheads

from the baseline TCC runs and used it to focus performance tuningon transactions with problematic behavior. The optimized applications achieve speedups ranging from 4.5 to 7.8 on an 8 processor
CMP-conﬁguration TCC system. The main contribution of the optimizations was to reduce the amount of time lost to violations, toadjust transaction sizes, and/or to limit buffer requirements. Notethat the optimizations required that less than 5% of the original
sequential source code lines be modiﬁed in all applications except
assignment and art, which required slightly more.
The following sections discuss our insights on parallelizing andoptimizing each application. The analysis is broken up into fourparts, based on input source language (Java or C) and the type ofparallelization (loop or fork) used.

4.2.1. Automatically Parallelized Java Loops

We automatically parallelized loop-based Java applications using the Jrpm dynamic compilation system [7]. Jrpm used orderedtransactional loops in all cases. After examining the initial resultsfrom the ordered loops, we focused on the most signiﬁcant loops todetermine whether they could safely be executed in an unorderedmanner. Where possible and safe, we guided Jrpm to use unordered
loops for performance improvement. Finally, after successfullyparallelizing each application with Jrpm, we simulated each benchmark on top of the modiﬁed Kaffe JVM described in Section 4.1.
Assignment: This application includes largely parallel loops with
only occasional dependencies, which are difﬁcult to analyze statically using a conventional compiler. Most loops are 2-level nested.
Jrpm usually generated transactions from the outer loop, because
the inner loops were typically too small to parallelize. The baselinespeedup with ordered transactions is 2.58. Reduction privatization
eliminates nearly all transaction violations and boosts speedup to
6.46. Reduction privatization is even more critical for greater numbers of processors, as the length of the critical dependency arcs
imposed by the unmodiﬁed reduction limits speedups to less than 3,
no matter how many processors are used. Higher speedup cannot be
achieved primarily due to sequential portions of the application.
MolDyn: Moldyn includes parallel loops with infrequent dynamic
dependencies. The most signiﬁcant optimization was loop chunking due to the small size of loop iterations. Jrpm automatically performed chunking in the baseline version. Unordered transactions
and reduction privatization provide small additional beneﬁts.
LUFactor:This application contains many parallel loops, with twoof them dominating the execution time. Unlike most other applications in our suite, the lengths of the transactions within each parallel loop varies signiﬁcantly. Both have loop-carried dependencies,
but the distance is large enough so that it only limits performancefor large processor counts.
RayTrace: This application spends most of its time in a single loop.
Unordered transactions and reduction privatization provide some
improvement over the baseline speedup. Nevertheless, the overall
speedup (4.48) is limited by the large sequential code regions.

4.2.2. Java with Forking: SPECjbb

SPECjbb is a server-side Java benchmark that simulates order processing in a 3-tier enterprise system. Its execution is divided up
into separate “warehouses,” which are essentially explicitly parallel. Hence, parallelization across warehouses is trivial for all kindsof parallel systems, including TCC. For this study, we parallelized
SPECjbb within each warehouse, which is much more difﬁcult withtraditional means. Each warehouse involves task-queue processing
with hard-to-analyze dependencies through inventory records. The
main loop of SPECjbb for a warehouse iterates over ﬁve task types:
new orders, payments, order status, deliveries, and stock levels.
New orders and payments are weighted to occur ten times more
often than other tasks, and the actual order of transactions is randomized. We parallelized this loop by generating unordered transactions for each task using the fork mechanism, achieving an initial
speedup of 1.87.
Feedback-based tuning of this application consisted of several different steps targeting idle time reduction and removal of violations.
The ﬁrst step removed some remnants of an unnecessary object
counter that caused spurious violations. We also found two key
variables that needed privatization in order to work well in an unordered manner. The ﬁrst was the seed to the random number generator used to generate tasks. The second was scratch-space objects,
which were reused from one task to the next in the original codein order to avoid memory allocation. Finally, we found two opportunities where the judicious use of t_commit allowed us to split
payment and new order tasks into two transactions, one for inventory processing and one for output display formatting. Because of
the large size of transactions in SPECjbb, the smaller transactions
that were created by this splitting signiﬁcantly reduced the amountof useful work that was discarded when violations did occur, a factor that was especially critical with larger numbers of processors.
Splitting also had the additional beneﬁt of reducing write buffer
requirements for the application by about half.

4.2.3. Manually Parallelized C Loops

We parallelized three SPEC ﬂoating-point applications with loop
level parallelism. All three have nested loops of various depths thatcan be parallelized using variations of t_for.
art: This program ﬁrst trains a neural network and then uses it tomatch images. Both of its phases iterate over a routine that includes
a ﬁve-level nested loop that computes the output of the neural network. We parallelized the loops that iterate over neurons in the F1layer because all other loop levels had limited parallelism or loopcarried dependencies. These loops contain critical reduction variables, hence signiﬁcant speedups were achieved only after privatizing reductions. Loop fusion provided some additional improvement
for an overall speedup of 6.91. The use of unordered transactions,while possible, did not provide any signiﬁcant beneﬁts for this application.
equake: This benchmark consists of series of loops operating ona sparse matrix. The baseline version used unordered transactions
to automatically handle load balancing across transactions andachieved a speedup of 3.60. The main optimization for equake wastransaction splitting, which reduced the frequency of violations, atthe cost of an increase in commit overhead due to the signiﬁcantly
shorter transactions. To counter this, we fused loops together where
possible to lengthen the transactions again, achieving a slight increase in performance that became more signiﬁcant with larger
numbers of processors. The overall speedup was 7.49.
tomcatv: This application includes ﬁve two-level nested loops that
operate on the entire mesh. The inner loops require ordered transactions to handle the loop-carried dependencies correctly, which tend
to limit performance to less than 3 no matter how many processors
are used. Outer loops, on the other hand, can be parallelized with
unordered transactions, leading to near perfect speedup. The drawback of outer-loop parallelization is that the large transactions needlarger write buffers, which could be an issue with larger datasets
since the size of these outer loop transactions is proportional to thesize of the input array.

4.2.4. C with Forking: MPEG-2 Decode

MPEG-2 decode exhibits non-trivial concurrency patterns withcomplex dependencies. Its code iterates over frames, slices, andmacroblocks. At the macroblock level, parallelism is too ﬁnegrained and is better targeted by ILP techniques in each processor.
On the other hand, parallelizing at the frame level would exceedbuffer limitations in most reasonable TCC systems. Hence, we parallelized at the slice level, which results in very large transactions,but ones that are still feasible because they write out only a reasonable amount of state (less than 10KB, allocated as 64-byte lines)
and do not have any dependencies.
The primary difﬁculty in MPEG-2 decode is the sequential dependencies due to the use of the variable-length codes in the input bitstream. Until a slice has been decoded, the starting position of thenext one is unknown. This behavior lends itself naturally to forking, where a serial parent does bitstream decoding and then forks atransaction to process the decoded data for each slice. This follows
the same model as the example in Figure 2c, with the bitstream
decoding in the IF blocks and data processing in the EX blocks. To
reduce the serialization effect due to sequential bitstream decoding,we also applied a prescan algorithm that requires the sequential

32
Ideal

24

Speedup

CMP

16

SMP

8
0

4

8 16 32

4

Assignment

8 16 32

4

MolDyn

8 16 32

4

LUFactor

8 16 32

4

RayTrace

8 16 32

4

SPECjbb

8 16 32art

4

8 16 32
equake4

8 16 32

4

8 16 32

tomcatv

mpeg-decode

Figure 5: Overall speedup obtained in different hardware conﬁgurations.
��������� ��������

�
����

����
��������

����������

������������� �� ��

����������

�� �� ��

�������� �� ��

��������

�� �� ��

��������

�� �� ��

�������

�� �� ������� �� ��

������

�� �� ��

�� �� ��

�������

�����������

Figure 6: Breakdown of how different numbers of parallel processors spent their time, in the CMP conﬁguration.
parent to identify only slice boundaries, and not fully decode theinput bitstream [4]. The overall speedup for MPEG-2 decode was
5.89, with most of the source code changes going into implementing the prescanning algorithm.

4.3. Overall Performance

Figure 5 presents the best achieved speedups for three conﬁgurations of a TCC system (ideal, CMP, SMP) with the number of processors ranging from 4 to 32. Figure 6 complements these resultswith the ﬁnal execution time breakdown for all different processor
counts in the case of the CMP conﬁguration.
For six out of nine benchmarks (Assignment, LUFactor, RayTrace,
SPECjbb, tomcatv, and MPEG-2 decode), CMP performance closely tracks ideal performance for all processor counts. All six applications achieve speedups of 8 or above with 16 processors. LUFactor
and SPECjbb are limited for large processor counts by a combination of unavoidable violations and some regions that lacked enoughparallelism for the increased processor count, causing extra processors to idle. Assignment and RayTrace are mostly limited by thelarge sequential code regions, which result in an immense amountof processor idle time with larger numbers of processors. On theother hand, tomcatv scales perfectly to 32 processors, with only
small increases in idle and waiting time and virtually no transaction
violations. Finally, MPEG-2 decode speedup ﬂattens at 16 processors, because in our sample input stream there were only 16 slices
per frame, so any additional processors were idle. Overall, theseresults demonstrate that high performance can often be achieved
with TCC through only minor modiﬁcations to sequential code.
For MolDyn, art, and equake, the ideal conﬁguration has a signiﬁcant advantage over the CMP conﬁguration for the 32 processor
case. As shown in Figure 6, the 32-processor CMP conﬁguration

incurs a large amount of waiting time. In this case, it is not due toload imbalance, but instead due to insufﬁcient commit bandwidth.
Too many of the 32 processors are trying to commit simultaneously
at any point in time, resulting in serialization for access to the commit network. Luckily, solving bandwidth problems like this should
generally be straightforward within a chip, especially for TCC systems that exchange only large messages between nodes.
The SMP TCC conﬁguration achieves good speedups for 4–8 processors across the board, but exhibits little beneﬁt with more processors for most applications. Of our applications, only assignment,
SPECjbb, and tomcatv managed to use the additional processors
to signiﬁcant advantage, with SPECjbb notably almost completely
unaffected by the conﬁguration limits. This is actually a promising
result, as online server applications like SPECjbb would probably
be the primary application class that might drive the development of
TCC on systems larger than CMPs. For the rest of the applications,the major bottleneck is again commit bandwidth, as four bytes per
cycle is often too little for communicating between 16–32 paralleltransactions. However, with higher commit bandwidth, the SMP
conﬁguration could achieve speedups similar to the CMP one, since
the higher overheads incurred by board-level arbitration had muchless effect on the overall speedup than the commit bandwidth.

5. RELATED WORK

TCC builds on ideas from previous hardware-based transaction
work, designs for hardware thread-level speculation, databasetransaction processing, software-only transactional memory, andother forms of transactional programming, generally from the areaof reliability research. This section discusses related work fromthese varied ﬁelds, focusing mostly on issues relating to parallel
application development.

Previous Hardware Transaction Proposals: Transactions have beenused in previous proposals to allow execution through locks or pastbarriers in order to reduce the pressure for optimal placement ofsynchronization primitives in conventional multithreaded code [15,20, 26, 30]. TCC improves on this work by using transactions all
the time. In addition to simplifying hardware by eliminating conventional cache coherence, it completely eliminates the need forconventional locks and barriers in the application code, using theabstraction of transactions to describe all synchronization.
Thread-level Speculation (TLS): Several groups have demonstrated
speculative parallelization of sequential code using TLS hardware[11, 22, 33, 36]. Even though TCC draws upon TLS work, TCC
differs in two basic ways. From the hardware perspective, TLS layers speculative execution of threads on top of a conventional cachecoherence and consistency protocol, and generally allows speculative threads to communicate results to other speculative threads
continuously. On the other hand, TCC completely replaces the underlying coherence and consistency protocol, and allows transactions to make their write state visible only at commit time, whichshould generally make it scalable to larger numbers of processors.
From the software perspective, TLS always requires that threads
commit in a single, predeﬁned order [29], while TCC allows programmers to have full control over transaction sequencing, so thatthey can specify no or partial ordering for transaction commit.
The similarity of support for speculation in TCC and TLS leads tosimilar issues during performance tuning. Techniques for minimizing data dependencies and optimizing transaction size to deal withoverheads and buffering requirements, much like those we usedwith TCC-based parallelization, have also been considered in thecontext of TLS in [27, 37].
Database Transaction Processing: The usefulness of transactions
as an abstraction for concurrency, atomicity, consistency, and isolation has been extensively studied by the database community [9].
TCC borrows the notion of transactions from databases in order tosimplify the development of general parallel programs. However,database transactions are typically heavyweight and are only usedin large transaction processing systems. In contrast, TCC transactions are lightweight, have direct hardware support, and are fully
visible to application programmers. Nevertheless, the speculative
execution of transactions in TCC is based on the idea of optimistic
concurrency control from databases [23].
Software-only Transactional Memory: Several researchers have explored software-only transactional memory or transactional datastructures [13, 14, 32]. The focus of this work has been to replace
locks with non-blocking primitives implemented with software
buffering or versioning. In contrast, our transactions execute at all
times and are accelerated by direct hardware support. In addition,
TCC transactions provide memory consistency similar to that oflazy and delayed consistency models [8, 19, 21], which postpone
communicating and processing of consistency events until release
points in the program code.
Transactional Programming for Reliability: The Tran-C programming language in the IBM Encina system includes built-in transactional semantics [16]. However, Tran-C uses transactions forapplication-level failure atomicity and recovery. For parallel programming, Tran-C relies on conventional threads with locks andmutexes. In a similar vein, the Java language provides the “try-catch-ﬁnally” programming construct which allows programmers
to specify application level error detection and recovery code [3].
Oplinger and Lam used this construct along with TLS mechanisms
to provide a low-overhead transactional programming model for
error recovery [28]. In contrast to these efforts, TCCʼs all-transactional approach provides a uniﬁed approach for both optimistic
parallelism and failure atomicity, an area of further research for us.
The use of a single abstraction for both goals greatly simpliﬁes application development.

6. CONCLUSIONS

We have shown that by using TCC, it is possible to parallelize awide range of applications with a few simple programming language constructs. Instead of using explicit synchronization withlocks, these constructs rely instead on the atomic property oftransactions to guarantee exclusive access to shared variables.
Furthermore, because TCC allows for speculative transactions, theprogrammer does not have to guarantee that the transactions are
independent to get correct program behavior. On the other hand,
one aspect of transaction programming that the programmer mustspecify for correct program operation is the commit ordering oftransactions (ordered, unordered or partially ordered); however, weview this as the key insight that programmers should be able toprovide when parallelizing programs. Of course, one can always
retain ordered transactions for safety purposes if there is ever any
uncertainty. Furthermore, we believe that reasoning about transaction order is much simpler than reasoning about individual loads
and stores, which is required with programming for conventional
memory consistency models [1].
Improving the parallel performance of an application is a key component of parallel programming, and is often required for TCC programs. However, unlike conventional shared memory parallel programing, where performance improvement is largely a process oftrial and error, we expect TCC systems to provide speciﬁc performance feedback in the form of transaction rollback statistics. Thesestatistics are much more meaningful to the programmer than cache
misses would be in a conventional shared memory multiprocessor because they are associated with programmer-deﬁned transactions and variables. We have shown that these statistics can be used
to direct the use of programming optimization techniques such as
loop chunking, reduction and buffer privatization, and transaction
splitting to improve TCC application performance signiﬁcantly.
The performance we have obtained with these optimizations overa wide range of applications is excellent, and demonstrates boththe programming ease and performance potential of TCC. Also,
although we performed these optimizations manually, since manyrequire only fairly mechanical adjustments to code that can be pinpointed by feedback, we expect that most will eventually be applied automatically by either a static or dynamic compiler, which
will further reduce the burden on the programmer.
Finally, we view the use of TCC hardware and TCC programming
language support as a synergy of hardware and software that will
provide a much gentler transition from sequential programming toparallel programming than that provided by any previous parallel
programming paradigm. As a result, TCC hardware and software
will be an important catalyst in transforming parallel processing
for speedup of individual applications from a niche activity to awidespread technique.

7. ACKNOWLEDGEMENTS

This work was supported by NSF grant CCR-0220138 and DARPA
PCA program grants F29601-01-2-0085 and F29601-03-2-0117.

8. REFERENCES[1]

S. V. Adve and K. Gharachorloo, “Shared Memory Consistency
Models: A Tutorial,” IEEE Computer, Vol. 29 No. 12, pp. 66–76,
December 1996.
[2] V. Agarwal, S. Hrisikesh, D. Burger, and S. Keckler, “Clock Rate
vs IPC: The End of Road for Conventional Microarchitectures,”27th Intl. Symposium on Computer Architecture, pp. 248–259,
Vancouver, Canada, June 2000.
[3] K. Arnold, J. Gosling, and D. Holmes, The Java Programming
Language, Third Edition, Addison-Wesley Professional, 2000.
[4] A. Bilas, J. Fritts, and J. P. Singh, “Real-time parallel MPEG2
decoding in software,” Proc. 11th International Parallel Processing
Symposium, Geneva, Switzerland, 1997.
[5] Broadcom Corp., “The Broadcom BCM-1250 Multiprocessor,”
Presentation at 2002 Embedded Processor Forum, April 2002.
[6] Byte Magazine, jBYTEmark Benchmark, http://www.byte.com,
CMP Media LLC, 1999.
[7] M. K. Chen and K. Olukotun, “The Jrpm System for Dynamically
Parallelizing Java Programs,” Proceedings of the 30th International
Symposium on Computer Architecture (ISCA-30), pp. 434–445,
June 2003.
[8] M. Dubois, et. al., “Delayed Consistency and Its Effects on theMiss Rate of Parallel Programs,” Proceedings of Supercomputing
ʼ91, November 1991.
[9] J. Gray and A. Reuter, Transaction Processing: Concepts andTechniques, Morgan Kaufmann, 1993.
[10] W. Gropp, E. Lusk, and A. Skjellum, Using MPI: Portable
Parallel Programming with the Message Passing Interface, MIT
Press, 1994.
[11] L. Hammond, B. Hubbert, M. Siu, M. Prabhu, M. Chen, and K.
Olukotun, “The Stanford Hydra CMP,” IEEE MICRO Magazine,
pp. 71–84, March-April 2000.
[12] L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis,
B. Hertzberg, M. K. Prabhu, H. Wijaya, C. Kozyrakis, and K.
Olukotun, “Transactional Memory Coherence and Consistency,”
Proceedings of the 31st Annual Symposium on Computer
Architecture (ISCA-31), pp. 102–113, June 2004.
[13] T. Harris and K. Fraser, “Language Support for LightweightTransactions,” 18th ACM SIGPLAN Conference on Object-Oriented
Programming, Systems, Languages, and Applications (OOPSLA2003), October 2003.
[14] M. P. Herlihy, V. Luchangco, M. Moir, and W. M. Scherer,“Software Transactional Memory for Dynamic-sized Data
Structures,” Proceedings of the 22nd Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing(PODC), July 2003.
[15] M. Herlihy and J. Moss, “Transactional Memory: Architectural
Support for Lock-Free Data Structures,” Proceedings of the 20th
International Symposium on Computer Architecture (ISCA-20), pp.
289-300, 1993.
[16] IBM Corporation, Encina Transactional-C Programmerʼs Guide
and Reference for AIX, SC23-2465-02, 1994.
[17] Java Grande Forum, Java Grande Benchmark Suite, http://www.
epcc.ed.ac.uk/javagrande/, 2000.
[18] R. Kalla, B. Sinharoy, and J. Tendler, “Simultaneous Multithreading Implementation in POWER5,” Conference Record of
Hot Chips 15 Symposium, Palo Alto, CA, August 2003.
[19] P. Keleher, A. L. Cox, and W. Zwaenepoel, “Lazy Release
Consistency for Software Distributed Shared Memory,”
Proceedings of the Fifth International Symposium on HighPerformance Computer Architecture, pp. 279–283, Orlando, FL,

1999.
[20] T. Knight, “An Architecture for Mostly Functional Languages,”
Proceedings of the 1986 ACM Conference on Lisp and Functional
Programming, August 1986.
[21] L. I. Kontothanassis, M. L. Scott, and R. Bianchini, “LazyRelease Consistency for Hardware-Coherent Multiprocessors,”
Proceedings of Supercomputing ʼ95, San Diego, CA, Dec. 1995.
[22] V. Krishnan and J. Torrellas, “A Chip Multiprocessor Architecturewith Speculative Multithreading,” IEEE Transactions on
Computers, Special Issue on Multithreaded Architecture, Vol. 48
No. 9, pp. 866–880, September 1999.
[23] H. T. Kung and J. T. Robinson, “On Optimistic Methods forConcurrency Control,” ACM Transactions on Database Systems,
Vol. 6 No. 2, June 1981.
[24] C. Lee, M. Potkonjak, and W. Mangione-Smith, “MediaBench:
A tool for evaluating and synthesizing multimedia andcommunication systems,” Proceedings of the 30th Annual
International Symposium on Microarchitecture (MICRO-97),
Research Triangle Park, NC, December 1997.
[25] B. Lewis and D.J. Berg, Multithreaded Programming withPthreads, Prentice Hall, 1998.
[26] J. Martinez and J. Torrellas, “Speculative Synchronization:
Applying Thread-Level Speculation to Parallel Applications,”
Proceedings of the 10th International Conference on Architectural
Support for Programming Languages and Operating Systems(ASPLOS-X), pp. 18–29, October 2002.
[27] K. Olukotun, L. Hammond, and M. Willey, “Improving the
Performance of Speculatively Parallel Applications on the Hydra
CMP,” Proceedings of the 1999 ACM International Conference on
Supercomputing (ICS-99), pp. 21–30, Rhodes, Greece, June 1999.
[28] J. Oplinger and M. S. Lam, “Enhancing Software Reliability
with Speculative Threads,” Proceedings of the 10th International
Conference on Architectural Support for Programming Languages
and Operating Systems (ASPLOS-X), pp. 184–196, October 2002.
[29] M. K. Prabhu and K. Olukotun, “Using Thread-Level Speculation
to Simplify Manual Parallelization,” Proceedings of the Principles
and Practice of Parallel Programming (PPoPP), pp. 1–12, June
2003.
[30] R. Rajwar and J. Goodman, “Transactional Lock-Free Executionof Lock-Based Programs,” Proceedings of the 10th International
Conference on Architectural Support for Programming Languages
and Operating Systems (ASPLOS-X), pp. 5–17, October 2002.
[31] R. Raman, “UltraSparc Gemini: Dual CPU Processor,” Conference
Record of Hot Chips 15 Symposium, Palo Alto, CA, August 2003.
[32] N. Shavit and S. Touitou, “Software Transactional Memory,”
Proceedings of the 14th Annual ACM Symposium on Principles
of Distributed Computing, pp. 204–213, Ottawa, Canada, August
20–23, 1995.
[33] G. Sohi, S. Breach, and T. Vijaykumar, “Multiscalar processors,”
Proceedings of the 22nd Annual International Symposium on
Computer Architecture, pp. 414–425, Santa Margherita Ligure,
Italy, June 1995.
[34] Standard Performance Evaluation Corporation, SPECjbb2000
v1.01, http://www.spec.org/jbb2000/, Warrenton, VA, 2000.
[35] Standard Performance Evaluation Corporation, SPEC*, http://
www.specbench.org/, Warrenton, VA, 1995–2000.
[36] J. Steffan and T. Mowry, “The Potential for Using ThreadLevel Data Speculation to Facilitate Automatic Parallelization,”
Proceedings of the Fourth International Symposium on HighPerformance Computer Architecture, pp. 2–13, Las Vegas,
Nevada, 1998.
[37] T.N. Vijaykumar and G. S. Sohi, “Task Selection for a Multiscalar
Processor,” Proceedings of the 31st International Symposium on
Microarchitecture (MICRO-31), pp. 81–92, December 1998.
[38] T. Wilkinson, Kaffe Virtual Machine, http://kaffe.org, 1997–2002.