8 CHAPTER 2. INTRODUCTION
multicore in 2001. Intel introduced hyperthreading into
its commodity Pentium line in November 2000, and both
AMD and Intel introduced dual-core CPUs in 2005. Sun
followed with the multicore/multi-threaded Niagara in
late 2005. In fact, by 2008, it was becoming difficult to
find a single-CPU desktop system, with single-core CPUs
being relegated to netbooks and embedded devices. By
2012, even smartphones were starting to sport multiple
CPUs.
Second, the advent of low-cost and readily available
multicore systems means that the once-rare experience
of parallel programming is now available to almost all
researchers and practitioners. In fact, parallel systems
are now well within the budget of students and hobbyists.
We can therefore expect greatly increased levels of inven-
tion and innovation surrounding parallel systems, and that
increased familiarity will over time make the once pro-
hibitively expensive field of parallel programming much
more friendly and commonplace.
Third, in the 20
th
century, large systems of highly par-
allel software were almost always closely guarded propri-
etary secrets. In happy contrast, the 21
st
century has seen
numerous open-source (and thus publicly available) paral-
lel software projects, including the Linux kernel [
Tor03
],
database systems [
Pos08
,
MS08
], and message-passing
systems [The08, UoC08]. This book will draw primarily
from the Linux kernel, but will provide much material
suitable for user-level applications.
Fourth, even though the large-scale parallel-
programming projects of the 1980s and 1990s were
almost all proprietary projects, these projects have
seeded the community with a cadre of developers who
understand the engineering discipline required to develop
production-quality parallel code. A major purpose of this
book is to present this engineering discipline.
Unfortunately, the fifth difficulty, the high cost of com-
munication relative to that of processing, remains largely
in force. Although this difficulty has been receiving in-
creasing attention during the new millennium, according
to Stephen Hawking, the finite speed of light and the
atomic nature of matter is likely to limit progress in this
area [
Gar07
,
Moo03
]. Fortunately, this difficulty has been
in force since the late 1980s, so that the aforementioned
engineering discipline has evolved practical and effective
strategies for handling it. In addition, hardware designers
are increasingly aware of these issues, so perhaps future
hardware will be more friendly to parallel software as
discussed in Section 3.3.
Quick Quiz 2.1:
Come on now!!! Parallel program-
ming has been known to be exceedingly hard for many
decades. You seem to be hinting that it is not so hard.
What sort of game are you playing?
However, even though parallel programming might not
be as hard as is commonly advertised, it is often more
work than is sequential programming.
Quick Quiz 2.2:
How could parallel programming
ever be as easy as sequential programming?
It therefore makes sense to consider alternatives to
parallel programming. However, it is not possible to
reasonably consider parallel-programming alternatives
without understanding parallel-programming goals. This
topic is addressed in the next section.
2.2 Parallel Programming Goals
The three major goals of parallel programming (over and
above those of sequential programming) are as follows:
1. Performance.
2. Productivity.
3. Generality.
Unfortunately, given the current state of the art, it is
possible to achieve at best two of these three goals for
any given parallel program. These three goals therefore
form the iron triangle of parallel programming, a triangle
upon which overly optimistic hopes all too often come to
grief.
1
Quick Quiz 2.3:
Oh, really??? What about correct-
ness, maintainability, robustness, and so on?
Quick Quiz 2.4:
And if correctness, maintainability,
and robustness don’t make the list, why do productivity
and generality?
Quick Quiz 2.5:
Given that parallel programs are
much harder to prove correct than are sequential pro-
grams, again, shouldn’t correctness really be on the list?
Quick Quiz 2.6: What about just having fun?
Each of these goals is elaborated upon in the following
sections.
1
Kudos to Michael Wong for naming the iron triangle.