practice
DoI: 10.1145/1461928.1461943
While still primarily a research project,
transactional memory shows promise
for making parallel programming easier.
1
( 1–P) + P/S
Here P is the fraction of the program
that can be parallelized, and S is the
number of execution units.
BY uLRICh DRePPeR
Parallel
Programming
with
transactional
memory
With the speed of individual cores no longer
increasing at the rate we came to love over the past
decades, programmers have to look for other ways
to increase the speed of our ever-more-complicated
applications. The functionality provided by the CPU
manufacturers is an increased number of execution
units, or CPU cores.
To use these extra cores, programs must be
parallelized. Multiple paths of execution have to work
together to complete the tasks the program has to
perform, and as much of that work as possible has to
happen concurrently. Only then is it possible to speed
up the program (that is, reduce the total runtime).
Amdahl’s Law expresses this as:
synchronization Problems
This is the theory. Making it a reality is
another issue. Simply writing a normal
program by itself is a problem, as can
be seen in the relentless stream of bug
fixes available for programs. Trying to
split a program into multiple pieces
that can be executed in parallel adds a
whole dimension of additional problems:
˲Unless the program consists of
multiple independent pieces from the
onset and should have been written as
separate programs in the first place,
the individual pieces have to collaborate. This usually takes on the form of
sharing data in memory or on secondary storage.
˲ Write access to shared data cannot
happen in an uncontrolled fashion. Allowing a program to see an inconsistent, and hence unexpected, state must
be avoided at all times. This is a problem if the state is represented by the
content of multiple memory locations.
Processors are not able to modify an arbitrary number (in most cases not even
two) of independent memory locations
atomically.
˲ To deal with multiple memory locations, “traditional” parallel programming has had to resort to synchronization. With the help of mutex (mutual
exclusion) directives, a program can
ensure that it is alone in executing an
operation protected by the mutex object. If all read or write accesses to the
protected state are performed while
holding the mutex lock, it is guaranteed
that the program will never see an inconsistent state. Today’s programming
environments (for example, POSIX) allow for an arbitrary number of mutexes
to coexist, and there are special types of
mutexes that allow for multiple readers
to gain access concurrently. The latter
is allowed since read accesses do not
38 CommunICatIons of the aCm | feBRuaRY 2009 | vol. 52 | No. 2