What the $#@! is Parallelism, Anyhow? - Intel® Software Network
61 captures<br>02 Nov 2009 - 15 Aug 2025
Oct<br>NOV<br>Dec
03
2008<br>2009<br>2010
success
fail
About this capture
COLLECTED BY
Organization: Alexa Crawls
Starting in 1996, Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the Wayback Machine after an embargo period.
Collection: alexa_web_2009
this data is currently not publicly accessible.
TIMESTAMPS
The Wayback Machine - https://web.archive.org/web/20091103162537/http://software.intel.com:80/en-us/articles/what-the-is-parallelism-anyhow-1/
Javascript is disabled on your browser. In order to use this platform effeciently, please enable javascript from your browser settings or contact your system administrator.
Work
Play
Support
About Intel
Change Location
Search
Intel® Software Network
Connect with developers and Intel engineers
CommunitiesAcademic<br>Cluster Ready<br>Manageability<br>Mobility<br>Parallel Programming and Multi-Core<br>Open Source<br>Virtualization<br>Visual Computing<br>More...
Downloads<br>ToolsIntel® Parallel Studio<br>HPC Tools<br>SOA Products<br>Buy or Renew<br>Free Evaluation Software<br>Free Non-Commercial Download<br>Reseller Center<br>Academic Program<br>Platform Administration Products<br>Content Management Products<br>Tools Knowledge Base
Forums/BlogsForums<br>Blogs<br>Blog Categories<br>Meet The Bloggers
ResourcesEvents Calendar<br>Intel Press Technical Books<br>Intel Software Insight Magazine<br>Intel Visual Adrenaline Magazine<br>Intel Software Partner Program<br>Knowledge Base<br>Take Five Videos<br>Training<br>What If Software
Software Support
Home › Articles
What the $#@! is Parallelism, Anyhow?<br>Submit New Article
Last Modified On :<br>October 28, 2009 2:08 PM PDT
Rate
by Charles Leiserson
I'm constantly amazed how many seemingly well-educated computer technologists bandy about the word parallelism without really knowing what they're talking about. I can't tell you how many articles and books I've read on parallel computing that use the term over and over without ever defining it. Many of these “authoritative” sources cite Amdahl's Law (1), originally proffered by Gene Amdahl in 1967, but they seem blissfully unaware of the more general and precise quantification of parallelism provided by theoretical computer science. Since the theory really isn't all that hard, it curious that it isn't better known. Maybe it needs a better name — “Law” sounds so authoritative. In this blog, I'll give a brief introduction to this theory, which incidentally provides a foundation for the efficiency of the Cilk++ runtime system.
Amdahl's Law
First, let's look at Amdahl's Law and see what it says and what it doesn't say. Amdahl made what amounts to the following observation. Suppose that 50% of a computation can be parallelized and 50% can't. Then, even if the 50% that is parallel took no time at all to execute, the total time is cut at most in half, leaving a speedup of less than 2. In general, if a fraction p of a computation can be run in parallel and the rest must run serially, Amdahl's Law upper-bounds the speedup by 1/(1–p).
This argument was used in the 1970's and 1980's to argue that parallel computing, which was in its infancy back then, was a bad idea — the implication being that most applications have long, inherently serial subcomputations that limit speedup. We now know from numerous examples that there are plenty of applications that can be effectively sped up by parallel computers, but Amdahl's Law doesn't really help in understanding how much speedup you can expect from your application. After all, few applications can be decomposed so simply into just a serial part and a parallel part. Theory to the rescue!
A model for multithreaded execution
As with much of theoretical computer science, we need a model of multithreaded execution in order to give a precise definition of parallelism. We can use the dag model for multithreading , which I talked about in my blog, “Are determinacy-race bugs lurking in your multicore application?” (A dag is a directed acyclic graph.) The dag model views the execution of a multithreaded program as a set of instructions (the vertices of the dag) with graph edges indicating dependences between instructions. We say that an instruction x precedes an instruction y, sometimes denoted x ? y, if x must complete before y can begin. In a diagram for the dag, x ? y means that there is a positive-length path from x to y. If neither x ? y nor y ? x, we say the instructions are in parallel , denoted x ? y. The figure below illustrates a multithreaded dag:
In the figure, we have, for example, 1 ? 2, 6 ? 12, and 4 ? 9.
Just by eyeballing, what would you guess is the parallelism of the dag? About 3? About 5? It turns out that two measures of the dag, called work and span, allow us to define parallelism precisely, as well as to provide some key bounds on performance. I'm going to christen these bounds “Laws,” so as to compete with the...