Chapter 31: Why Parallel? Modern Hardware, Amdahl's Law, and the End of the Free Lunch

"If you were plowing a field, which would you rather use: two strong oxen or 1024 chickens?" — attributed to Seymour Cray, pioneer of supercomputing

Overview

For roughly forty years, programmers enjoyed a free lunch. You wrote your code, and every eighteen months or so a new processor arrived that ran it faster — not because you had done anything, but because the clock ticked quicker. A program that took ten seconds this year would take five in a couple of years, for free, while you slept. Then, around 2005, the lunch stopped being free. Clock speeds hit a wall of physics and have barely moved since. The transistors kept coming — Moore's Law did not end in 2005 — but the chip designers stopped spending them on one faster core and started spending them on more cores. A processor today is not a faster version of a 2005 processor; it is a box holding many 2005-ish cores side by side.

That single fact reorganizes everything about how fast code is written, and it is why this entire part of the book exists. If the hardware will no longer make your serial program faster on its own, then the only road left to more performance runs through parallelism: getting many cores, many sockets, many machines, or a graphics processor to work on your computation at the same time. You have spent Part VII making the heat solver fast on one core — measuring it, profiling it, tuning its loops, feeding the compiler the right flags. This chapter is the hinge. Before you write a single line of OpenMP or MPI or coarray code, you need to understand what parallelism can and cannot buy you, because the answer is governed by an unforgiving piece of arithmetic — Amdahl's Law — that has ended more parallel projects in disappointment than any bug ever has.

This is a conceptual chapter. We will compute a great deal, but the computation is about parallel programs, not inside them; the actual parallel Fortran starts in Chapter 32. Here the job is to build the mental model — the physics that forced the change, the laws that bound the payoff, the taxonomy of the tools, and a disciplined way of thinking about a computation before you parallelize it.

In this chapter, you will learn to:

• Explain the end of the "free lunch": why single-thread performance flattened, and why that is a consequence of power physics, not a failure of engineering.
• Use Amdahl's Law to compute the hard ceiling on speedup set by the part of your program that must run serially — and to see why the last few percent of serial code dominate that ceiling.
• Use Gustafson's Law to see why real supercomputing works anyway: because we grow the problem, not just the core count.
• Lay out the taxonomy of parallel hardware and software — shared memory, distributed memory, and GPUs — and place Fortran's tools (coarrays, OpenMP, MPI, OpenACC, CUDA Fortran) on that map.
• Tell data parallelism from task parallelism, and strong scaling from weak scaling, and use those distinctions to write a parallelization plan for the solver.

Learning Paths

How to read this chapter by track. - ⚡ HPC ("I need parallel code") — this is your on-ramp; read every section closely. §31.2 (the two laws) and §31.5 (the plan) are the ones you will use on Monday morning. - 🔬 Scientist ("my simulation is too slow") — read §31.1 and §31.2 carefully; they tell you whether parallelism will help your problem at all before you invest a week in it. Skim §31.3. - 📖 Standard — read straight through; this chapter frames Chapters 32–35 and names every tool they develop. - 🔧 Legacy ("I inherited old parallel code") — §31.3 is your map of what MPI, OpenMP, and coarrays are, so the old code stops looking like noise. §31.2 tells you what its authors were up against.

31.1 The End of the Free Lunch

To understand why you must learn parallel programming, you have to understand a change in the hardware that happened once, around the middle of the last decade, and will not un-happen. It is worth getting right, because the internet is full of muddled versions of it.

Start with the thing that did not change: Moore's Law. In 1965 Gordon Moore observed that the number of transistors that manufacturers could economically fit on a chip was doubling at a steady, predictable cadence — settling, in the form the law is usually quoted, to roughly every two years — and the trend has held, with heroic effort, for decades. Chips today hold billions of transistors. Moore's Law is about transistor count, and transistor count kept climbing right through 2005 and beyond. When someone tells you "Moore's Law ended and that's why we need parallelism," they have the right decade and the wrong law.

The law that ended is Dennard scaling, and it is the one that actually gave you the free lunch.

Definition (Dennard scaling). Named for Robert Dennard, whose team described it in 1974: as a transistor is made smaller, the voltage and current it needs shrink in proportion, so the power per unit area of the chip stays roughly constant even as you pack in more, faster transistors. The practical payoff, for about thirty years, was that each new manufacturing generation let designers raise the clock frequency substantially without melting the chip. Faster clocks made every existing program faster with no code changes. That was the free lunch.

Dennard scaling broke down in the mid-2000s. As transistors shrank below roughly the 90-nanometre and 65-nanometre generations, effects that the clean scaling model ignored — chiefly current that leaks through transistors even when they are nominally off — stopped being negligible. Power density, instead of holding constant, began to rise sharply with frequency. A chip's power budget is fixed by what you can cool: push past a few hundred watts on a small die and it cooks itself. So clock frequency, which had climbed from megahertz in the 1980s to several gigahertz by 2004, hit a thermal ceiling and stuck there. Two decades later, a top mainstream core still runs at a few gigahertz. The number barely moved.

   single-core        the hoped-for trend (Dennard forever)
   clock speed   . . . . . . . . . . . . . . . . . . . . . .
     (GHz)     .
             .
           .
         .  _______________________________  what actually happened:
       .   /                                  a plateau at "a few GHz"
     .    /
   .-----+---------------------------------------->  year
  ~1985  ~2005                              ~2025
        (Dennard scaling ends here; the transistors
         Moore's Law keeps delivering now go into
         MORE CORES, not a faster one)

The transistors did not stop coming — Moore's Law saw to that — so the designers had to spend them on something. The something was more cores. A single 2004 processor had one core; by the 2010s, mainstream desktop chips had four, eight, sixteen; server sockets today hold dozens; a single compute node in a cluster may present a hundred or more cores across its sockets, and a supercomputer wires together thousands of such nodes. The transistor budget that used to buy you a faster core now buys you more cores of about the same speed.

📜 From History: "The Free Lunch Is Over." In 2005 the C++ authority Herb Sutter published an essay with that title in Dr. Dobb's Journal, and it became the canonical announcement of the shift to the software world. His argument was blunt: the "free lunch" of ever-rising clock speeds was finished, and concurrency — writing programs that do many things at once — would stop being an exotic specialty and become a mainstream necessity. He was right. Everything in Part VIII is the working-out, in Fortran, of the change he named. The scientific-computing world had felt it a little earlier than the desktop world, because it had been living at the bleeding edge of clock speed and cooling for years — but for everyone, the era of automatic speedups was over.

Here is the consequence stated plainly, and it is the reason the rest of this book has been quietly building toward this part. Performance is not accidental — it never was, but now it is not even automatic. The hardware will not make your serial program faster on its own anymore. If your 2005-era mental model is "wait for a faster chip," that model is dead. The only remaining sources of large speedups are the ones you must reach for deliberately: better serial code (Part VII), and parallel execution across many cores (this part). A modern processor is a parallel machine whether or not you use it as one. A serial program running on a 64-core node is leaving 63 cores idle — you have bought a team of oxen and hitched only one.

💡 Intuition: Picture the change as a factory. For thirty years, the way to build more cars per day was to make the single assembly line run faster, and it did, all by itself. Then the line hit its top safe speed and could not go faster without flying apart. The only way left to build more cars was to build more lines and run them in parallel — which works beautifully for tasks you can split across lines, and not at all for the one bottleneck step that only one line can do. That bottleneck step is the subject of the next section, and it has a name and a formula.

🔄 Check Your Understanding. 1. Which "law" ended around 2005 and gave us the free lunch — Moore's Law or Dennard scaling? What did the other one keep doing? 2. Transistor counts are still rising. Where do those extra transistors go now, if not into a faster core? 3. Why does a serial program "waste" a modern multicore chip even when it runs correctly?

Answers

(1) Dennard scaling ended — the rule that shrinking transistors let you raise the clock at constant power. Moore's Law (transistor count doubling) kept going. (2) Into more cores (and larger caches, wider vector units, more memory channels) rather than one faster core. (3) A serial program uses one core; the other cores on the chip sit idle, so you get a fraction of the hardware's capability — the machine is parallel, but the program is not.

31.2 Two Laws That Bound the Payoff: Amdahl and Gustafson

You now know why you must parallelize. The next question is how much it can possibly help — and the answer, for any given program, is fixed by arithmetic before you write a line of parallel code. Two laws frame it. They look like they contradict each other; they do not. They answer two different questions, and holding both in your head is the mark of someone who thinks clearly about parallelism.

Amdahl's Law: the serial fraction is the tyrant

Almost no real program is entirely parallelizable. There is always some work that must happen in order, one step after another: reading a configuration file, allocating memory, printing a result, or a phase of the algorithm where each step genuinely depends on the previous one. Call the fraction of the total work that can be run in parallel $p$, and the remaining fraction that is stubbornly serial $1 - p$. Gene Amdahl, an IBM computer architect, pointed out in 1967 what this does to your speedup.

Definition (Amdahl's Law). If a fraction $p$ of a program's run time can be perfectly parallelized and the remaining fraction $1 - p$ must run serially, then running on $N$ processors takes time $$T(N) = (1 - p) + \frac{p}{N}$$ (taking the one-processor time as $1$), and the speedup — the one-processor time divided by the $N$-processor time — is $$S(N) = \frac{1}{(1 - p) + \dfrac{p}{N}}.$$ As $N \to \infty$, the parallel term $p/N$ vanishes and the speedup hits a hard ceiling: $$S_{\max} = \frac{1}{1 - p}.$$

Read that ceiling again, because it is the whole point. The maximum speedup you can ever get, with infinite processors and zero overhead, is set entirely by the serial fraction $1 - p$. Not by how many cores you buy. By how much of your program refuses to parallelize.

Put numbers on it and the tyranny becomes vivid. Suppose your program is 90% parallelizable — which sounds excellent. Then no matter how many processors you throw at it, you can never go faster than $$S_{\max} = \frac{1}{1 - 0.90} = \frac{1}{0.10} = 10\times.$$ Ten times, and not a hair more, even on a million cores. And you approach that ceiling slowly: on 8 processors, $$S(8) = \frac{1}{0.10 + \dfrac{0.90}{8}} = \frac{1}{0.10 + 0.1125} = \frac{1}{0.2125} \approx 4.7\times.$$ Eight processors, and you got less than 5× because a tenth of the work would not move. Now suppose you did the hard engineering to get to 95% parallel. The ceiling doubles to $1/0.05 = 20\times$. Push to 99% parallel and it leaps to $1/0.01 = 100\times$. The lesson is counterintuitive and important: near the top, every fraction of a percent of serial code you eliminate is worth enormous parallel headroom. Going from 90% to 99% parallel is a 10× increase in your ceiling, from a change that sounds like a rounding error.

🚪 Threshold Concept: Amdahl's Law changes what "optimization" means. Before you internalize Amdahl, you think of parallel speedup as something you buy with cores: more cores, more speed. After you internalize it, you see that your speedup is capped by your worst-parallelized code, and that adding cores past a point does almost nothing. The practical reflex this installs is permanent: before you parallelize anything, you ask "what fraction of the run time is the part I cannot parallelize?" — and if that serial fraction is 20%, you know before you start that 5× is your ceiling and 64 cores is a waste of 59 of them. Amdahl turns "how many cores can I get?" into "how small can I make the serial fraction?" That is a different, and much more productive, question. It is why this part of the book comes after Part VII: you make the serial code as small and fast as you can first, precisely because Amdahl says the serial part is what limits you.

Let us make the ceiling concrete across a realistic range of core counts. For a program that is 95% parallel ($p = 0.95$, ceiling $20\times$), the exact speedups are:

program amdahl_law
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  real(dp), parameter :: p = 0.95_dp          ! parallelizable fraction
  integer,  parameter :: cores(7) = [1, 2, 4, 8, 16, 32, 64]
  integer  :: k, n

  print '(a, f4.2)', 'Amdahl speedup, parallel fraction p = ', p
  print '(a)', ' cores      speedup'
  do k = 1, size(cores)
    n = cores(k)
    print '(i6, f13.4)', n, speedup(p, n)
  end do
  print '(a, f8.4)', 'ceiling as N -> infinity: ', 1.0_dp / (1.0_dp - p)

contains

  pure function speedup(pfrac, ncores) result(s)
    real(dp), intent(in) :: pfrac
    integer,  intent(in) :: ncores
    real(dp) :: s
    s = 1.0_dp / ((1.0_dp - pfrac) + pfrac / real(ncores, dp))
  end function speedup
end program amdahl_law

$ gfortran -std=f2018 -Wall -O2 example-01-amdahl.f90 -o amdahl && ./amdahl
Amdahl speedup, parallel fraction p = 0.95
 cores      speedup
     1       1.0000
     2       1.9048
     4       3.4783
     8       5.9259
    16       9.1429
    32      12.5490
    64      15.4217
ceiling as N -> infinity:  20.0000

Study the numbers. At 2 cores you nearly double (1.90×) — the serial 5% barely bites yet. But by 64 cores you have 15.4×, not 64×: you are using $15.4/64 \approx 24\%$ of the hardware you paid for. The curve is bending hard toward its ceiling of 20, and the extra cores are increasingly wasted. This flattening is not a defect of your code or your compiler; it is the shape of the equation. Every strong-scaling curve you ever measure will have this shape, and recognizing it on a plot — the telltale bend toward a horizontal asymptote — lets you read a program's serial fraction straight off its scaling data.

⚠️ Common Pitfall — quoting a speedup without the core count. "We got a 15× speedup!" is close to meaningless on its own. Fifteen times on how many cores? A 15× speedup on 16 cores (94% efficiency) is superb; the same 15× on 512 cores (3% efficiency) is a near-total failure that a competent reviewer will flag instantly. Always report speedup and the processor count together, and — better — report the efficiency $S/N$ alongside it. A number without its core count is a boast, not a measurement.

Gustafson's Law: grow the problem, and the ceiling lifts

If Amdahl's Law were the whole story, supercomputing would be pointless. Why build a machine with a million cores if a 5%-serial program tops out at 20×? Yet the machines exist, they are busy, and they deliver. Something is missing from the Amdahl picture, and in 1988 John Gustafson, working at Sandia National Laboratories on exactly such a machine, named it.

The hidden assumption in Amdahl's Law is that the problem size is fixed. Amdahl asks: take this exact computation and run it on more cores — how much faster? But that is almost never what a scientist actually does with a bigger machine. Given a thousand-fold more computing power, no climate scientist runs yesterday's forecast a thousand times faster. They run a finer forecast — a higher-resolution grid, more physics, a longer simulated time — that would have been impossible before. The problem grows to fill the machine. And when the problem grows, the parallel part of the work grows with it, while the serial part (reading one configuration file, printing one summary) stays about the same size. The serial fraction, as a proportion of the now-larger job, shrinks.

Definition (Gustafson's Law). Suppose that on $N$ processors a program spends a fraction $s$ of its run time in serial work and $1 - s$ in parallel work, and that as you add processors you scale the problem up so that this parallel time stays fixed (each processor keeps doing a full share). Then the scaled speedup — how much longer the same enlarged problem would take on a single processor — is $$S(N) = s + (1 - s)\,N = N - s\,(N - 1).$$ Unlike Amdahl's ceiling, this grows linearly with $N$, essentially without bound. There is no horizontal asymptote; more cores keep buying more scaled speedup.

The contrast is the entire lesson, so let us see the two laws side by side at the same serial fraction of 5%. Amdahl (fixed problem) crawls toward its ceiling of 20. Gustafson (growing problem) climbs a straight line:

program gustafson_law
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  real(dp), parameter :: s = 0.05_dp          ! serial fraction of the parallel run
  integer,  parameter :: cores(6) = [1, 2, 4, 8, 16, 32]
  integer  :: k, n

  print '(a, f4.2)', 'Serial fraction s = ', s
  print '(a)', ' cores    Gustafson       Amdahl'
  do k = 1, size(cores)
    n = cores(k)
    print '(i6, 2f13.4)', n, gustafson(s, n), amdahl(1.0_dp - s, n)
  end do

contains

  pure function gustafson(sfrac, ncores) result(sp)
    real(dp), intent(in) :: sfrac
    integer,  intent(in) :: ncores
    real(dp) :: sp
    sp = sfrac + (1.0_dp - sfrac) * real(ncores, dp)
  end function gustafson

  pure function amdahl(pfrac, ncores) result(sp)
    real(dp), intent(in) :: pfrac
    integer,  intent(in) :: ncores
    real(dp) :: sp
    sp = 1.0_dp / ((1.0_dp - pfrac) + pfrac / real(ncores, dp))
  end function amdahl
end program gustafson_law

$ gfortran -std=f2018 -Wall -O2 example-02-gustafson.f90 -o gustafson && ./gustafson
Serial fraction s = 0.05
 cores    Gustafson       Amdahl
     1       1.0000       1.0000
     2       1.9500       1.9048
     4       3.8500       3.4783
     8       7.6500       5.9259
    16      15.2500       9.1429
    32      30.4500      12.5490

At 32 cores the two laws already disagree by more than a factor of two — 30.4 versus 12.5 — from the same 5% serial fraction. Extend the table and the gap becomes a chasm: at 1024 cores, Gustafson's scaled speedup is $0.05 + 0.95 \times 1024 = 972.85$, while Amdahl's fixed-problem speedup never exceeds its ceiling of 20. This is not a contradiction and neither law is "more correct." They answer different questions:

• Amdahl asks: "I have this exact problem. How much faster does it finish on more cores?" Answer: limited hard by the serial fraction. This is the question you ask when a result must arrive sooner — a weather forecast is useless if it takes 25 hours to predict tomorrow.
• Gustafson asks: "I have this much time and this many cores. How much bigger a problem can I solve?" Answer: nearly linear in cores. This is the question you ask when accuracy or resolution is what you want more of, and you are willing to spend a fixed wall-clock budget to get it.

The two even define the serial fraction against different baselines — Amdahl's $1 - p$ is a slice of the original serial run time, Gustafson's $s$ is a slice of the parallel run time — which is the subtle reason the same "5%" produces such different curves. Do not let that trip you: the takeaway is the pair of questions, not the algebra. Real supercomputing lives mostly in Gustafson's world (weak scaling, growing problems), which is why the machines earn their keep; but Amdahl's world (strong scaling, fixed problems) is where you land whenever a fixed-size result has to finish sooner, and it is the harsher master of the two.

🐍 Python Comparison. These laws are language-agnostic — they are arithmetic about work and processors, and they bind a Python program exactly as tightly as a Fortran one. But there is a Fortran angle worth naming. In Python, the serial fraction is often accidentally enormous, because pure-Python loops are slow and the Global Interpreter Lock keeps threads from running Python bytecode truly in parallel; people reach for multiprocessing or hand the array work to NumPy (which drops into compiled C and Fortran) precisely to escape it. In Fortran, the numerically heavy part — the part you most want parallel — is already fast, native, and array-shaped, so a larger fraction of your run time is genuinely parallelizable to begin with. A high $p$ is easier to reach when the language does not impose a serial tax. That is one more way performance is not accidental: the language you start in sets the serial fraction you have to fight.

🔄 Check Your Understanding. 1. A program is 80% parallelizable. What is the absolute maximum speedup, on any number of cores? 2. Using Amdahl's Law, compute the speedup of that program on 4 cores. (Hint: $0.2 + 0.8/4$.) 3. In one sentence each, state the different question that Amdahl's Law and Gustafson's Law answer.

Answers

(1) $S_{\max} = 1/(1 - 0.8) = 1/0.2 = 5\times$. (2) $S(4) = 1/(0.2 + 0.8/4) = 1/(0.2 + 0.2) = 1/0.4 = 2.5\times$. (3) Amdahl: "for a fixed problem, how much faster on more cores?" (capped by the serial fraction). Gustafson: "in fixed time on more cores, how much bigger a problem?" (grows with the core count).

31.3 The Taxonomy of Parallelism

Knowing that you should parallelize, and how much it can help, the next question is what kind of parallelism, on what kind of hardware, with what tool. The landscape has a small number of clean categories, and every tool in Chapters 32–35 slots into one of them. The primary axis is where the memory lives.

Shared memory

Definition (shared memory). A parallel model in which several processing units — threads — all read and write the same memory, one common address space. When one thread stores a value into a variable, the others can see it directly, with no explicit communication: coordination happens through the shared data. This is the model of the multiple cores inside a single node, which physically share that node's RAM.

Shared memory is the friendly end of parallelism. Because every thread sees the same arrays, parallelizing often means little more than telling the compiler "run the iterations of this loop on different threads." That is exactly what OpenMP does, by directives you sprinkle onto ordinary Fortran (Chapter 33). The trouble shared memory brings is the flip side of its convenience: if two threads write the same location at the same time, or one reads while another writes, you get a data race — a bug whose answer changes from run to run. And shared memory does not scale beyond one machine: you are limited to the cores and the RAM of a single node, typically tens to low hundreds of cores. When you need more, you must cross to the other model.

Distributed memory

Definition (distributed memory). A parallel model in which each process has its own private memory and cannot directly touch another process's data. Processes coordinate by explicitly sending messages to one another — "here is my boundary row; give me yours." This is the model of a cluster: many separate nodes, each with its own RAM, wired together by a fast network. It scales to the largest machines on Earth, but the programmer must partition the data and arrange every exchange.

Distributed memory is how you reach thousands or millions of cores, because you are no longer confined to one box — you spread the computation across a whole cluster. The dominant tool is MPI, the Message Passing Interface (Chapter 34), in which you divide the problem into pieces (one per process), give each process its own piece, and write explicit calls to exchange the data at the seams. It scales magnificently and it is more work: you think constantly about who owns which data and when it must be communicated. The classic pattern — splitting a grid into tiles and exchanging the shared edges — is domain decomposition, and it is exactly how the heat solver will go distributed in Chapter 34.

   SHARED MEMORY (one node)                DISTRIBUTED MEMORY (a cluster)

  +-----------------------------+       +---------+   +---------+   +---------+
  | core  core  core  core      |       | core    |   | core    |   | core    |
  |   \    |     |    /          |       | private |   | private |   | private |
  |    one shared address space |       | memory  |   | memory  |   | memory  |
  +-----------------------------+       +----+----+   +----+----+   +----+----+
     threads share the SAME              |             |             |
     variables; no messages              +======= network =======+
     (OpenMP; coarrays)                    explicit messages between
                                           private memories (MPI; coarrays)

GPUs and accelerators

The third category is a different kind of processor altogether. A graphics processing unit (GPU) is a device with thousands of small, simple cores, built to do the same operation on enormous quantities of data at once. It is not better than a CPU at everything — it is dramatically better at wide, regular, number-crunching work (like sweeping a stencil over a million-cell grid) and dramatically worse at branchy, irregular, one-thing-at-a-time logic. A GPU has its own memory, separate from the CPU's, so using one means shipping data across to the device, computing there, and shipping results back — and that transfer is very often the bottleneck. Fortran reaches GPUs through OpenACC (directive-based, the gentle path) and CUDA Fortran (explicit kernels, NVIDIA-specific, more control), both in Chapter 35.

Where Fortran's tools land, and the one that is uniquely Fortran's

Here is the map, with the chapter that develops each tool:

Notice that coarrays appear in two rows. That is not a mistake — it is Fortran's distinctive advantage, and worth pausing on. Most languages treat "shared-memory threading" and "distributed-memory message passing" as two entirely different worlds with two different libraries bolted on from outside. Fortran has, built into the language standard itself (since Fortran 2008), a single parallel model — coarrays — that presents one notation whether the images run on the shared cores of one node or across the separate nodes of a cluster. The compiler and runtime handle whether an access to remote data is a memory read or a network message. This is a partitioned global address space model, and no mainstream language expresses it as cleanly as Fortran. It is a concrete, current example of two of this book's themes at once: Fortran is not dead (it standardized native parallelism while other languages were still arguing about threads), and modern Fortran is a modern language (parallelism is a first-class part of it, not an afterthought library). We build coarrays first, in Chapter 32, precisely because they are Fortran's own answer to this chapter's question.

🔗 Connection. The heat solver will travel across this entire taxonomy over the next four chapters. Chapter 32 decomposes the plate across coarray images; Chapter 33 turns the update loop loose on shared-memory threads with OpenMP; Chapter 34 distributes it across cluster processes with MPI and halo exchange; and Chapter 35 offloads the stencil to a GPU. Same solver, four models, all assembled into the finished computational science of the Chapter 38 capstone. This chapter is the map you will hold while you make that journey.

🔄 Check Your Understanding. 1. In which memory model do parallel workers coordinate by reading and writing the same variables, and in which do they send explicit messages? 2. Which model scales to a whole cluster, and which is confined to a single node? 3. What makes Fortran's coarrays unusual among mainstream languages?

Answers

(1) Shared memory coordinates through common variables (OpenMP); distributed memory coordinates by explicit messages (MPI). (2) Distributed memory scales across a cluster; shared memory is limited to one node's cores and RAM. (3) Coarrays are a native, standardized parallel model — part of the language since Fortran 2008 — that works across both shared and distributed memory with one notation, where most languages rely on external libraries.

31.4 Data vs Task Parallelism, and Strong vs Weak Scaling

Two more distinctions complete the vocabulary. The first is about what you run in parallel; the second is about how you measure whether the parallelism worked.

Data parallelism vs task parallelism

Data parallelism is doing the same operation to many pieces of data at the same time. Updating every interior cell of the heat plate with the identical five-point stencil is data parallelism in its purest form: one recipe, a million independent servings, all cookable at once. This is the overwhelmingly common kind in scientific computing, and it is exactly the shape that Fortran's whole-array operations from Chapter 5 already express. When you wrote the Laplacian as a single array statement over the whole interior, you were stating data parallelism — one more reason arrays are Fortran's superpower: the array form hands the compiler and the parallel runtime a block of independent work, laid bare.

Task parallelism is doing different operations at the same time — running independent subroutines concurrently, or overlapping distinct stages of a pipeline. Reading the next data file while computing on the current one is task parallelism. It shows up more at the level of a whole workflow than inside a tight numerical kernel, and it is generally harder to scale to large core counts because you only have so many genuinely different tasks. Most of the heavy lifting in an HPC code, and all of the heavy lifting in the heat solver, is data parallelism.

💡 Intuition: Data parallelism is a hundred cooks each making the same dish for a different table; task parallelism is a kitchen brigade where one cook grills, one plates, and one washes up, all at once. The first scales to as many cooks as you have dishes; the second scales only to as many distinct jobs as the kitchen has. Scientific simulation is almost always the first kind — which is good news, because that is the kind that scales.

Strong scaling vs weak scaling

When you finally run a parallel program and measure it, there are two honest experiments you can do, and they correspond precisely to the two laws of §31.2.

Definition (strong scaling). Hold the total problem size fixed and increase the number of processors, measuring how the run time falls (equivalently, how the speedup rises). Strong scaling is governed by Amdahl's Law: the serial fraction caps it, per-processor work shrinks as you add cores, so overhead looms ever larger and efficiency decays. Good strong scaling is hard, and it is what you want when a fixed-size problem must finish faster.

Definition (weak scaling). Hold the problem size per processor fixed and grow the total problem in step with the processor count, measuring whether the run time stays roughly constant. Weak scaling is governed by Gustafson's Law: each processor keeps a full workload, the serial fraction shrinks relative to the growing whole, and near-flat run time out to large core counts is achievable. Weak scaling is easier, and it is what you want when you would rather solve a bigger, finer problem in the same time.

The bridge between speedup and how well you are using the machine is parallel efficiency, the speedup divided by the processor count, $E(N) = S(N)/N$. Perfect (linear) speedup means $E = 1$ — every core fully pulling its weight. Amdahl guarantees that under strong scaling, efficiency must fall as you add cores; you can see exactly how fast for our 95%-parallel program:

$ gfortran -std=f2018 -Wall -O2 example-03-scaling-efficiency.f90 -o eff && ./eff
Strong scaling, Amdahl, p = 0.95
 cores      speedup   efficiency
     1       1.0000       1.0000
     2       1.9048       0.9524
     4       3.4783       0.8696
     8       5.9259       0.7407
    16       9.1429       0.5714
    32      12.5490       0.3922
    64      15.4217       0.2410

By 64 cores, efficiency has collapsed to 24% — three-quarters of the machine is being wasted on a fixed-size, 95%-parallel job. That is the strong-scaling wall. The way through it is usually not to buy more cores for the same problem (Amdahl forbids the payoff) but either to shrink the serial fraction or to switch to the weak-scaling question and grow the problem to match the cores. Knowing which of these two experiments you are running — and reporting which when you claim a scaling result — is a basic professional honesty, the same discipline the whole book insists on for benchmark numbers.

⚡ Performance Note. There is a humbler reason efficiency falls that the clean laws leave out: overhead. Real parallelism is never free. Threads must be launched and synchronized; processes must package and send messages across a network with real latency; a GPU must copy data across the bus. None of that work existed in the serial program, and all of it grows with the core count. So the measured strong scaling of a real code is always worse than the Amdahl curve for its serial fraction — Amdahl is the optimistic ceiling, assuming perfect, overhead-free parallelism you will never quite achieve. When your measured speedup falls short of Amdahl's prediction, the gap is your overhead, and closing it is much of the craft of Chapters 33 and 34. We measure real scaling, against these predictions, when the solver goes parallel.

🔄 Check Your Understanding. 1. You keep a $2000 \times 2000$ grid fixed and run it on 1, then 8, then 64 cores. Strong or weak scaling? 2. Which law predicts the ceiling for the experiment in (1)? 3. A code shows 20× speedup on 32 cores. What is its parallel efficiency, and is that good?

Answers

(1) Strong scaling — fixed total problem, rising core count. (2) Amdahl's Law. (3) $E = 20/32 = 0.625$, i.e. 62.5% — respectable for 32 cores on a fixed problem, though it means the serial fraction and overhead are already costing you more than a third of the machine.

31.5 Thinking About Parallelizing the Solver — Before Any Parallel Code

Everything so far has been preparation for a single discipline: think before you parallelize. The most common way parallel projects fail is not a subtle bug in the message passing — it is charging in without a plan, parallelizing the wrong thing, and discovering after a week that Amdahl's Law had capped the payoff at 1.3× all along. So before the solver runs on a single extra core, we make a plan on paper. Here is the method, applied to the heat equation.

Step 1 — Make the serial code fast first. This is not optional, and Amdahl's Law is why. Your parallel speedup is measured against your serial baseline, and the serial fraction is what caps you. If your serial code is sloppy — bad loop order against the column-major grain, no vectorization, cache-hostile access — then parallelizing it is polishing a slow thing. Worse, a slow serial bottleneck (say, unoptimized I/O) inflates the serial fraction and lowers your ceiling. So you do Part VII first: Chapter 27 taught why the column-major sweep is fast, Chapter 29 tuned the loops and made the serial kernel as lean as it will go, and Chapter 30 built it with the right flags. Make the serial fast, then make the fast parallel — never the other way around.

Step 2 — Profile to find where the time actually goes. You parallelize the hot spot, not the code you happen to find interesting. Chapter 28 gave you the tools — gprof, system_clock timers — and their verdict for the heat solver is unsurprising but essential to have measured rather than assumed: essentially all of the run time is in the time-stepping loop, and within it, the stencil update. The one-time setup (reading the namelist config, allocating the field, imposing the initial and boundary conditions) is a blink. The periodic output (writing a VTK frame every so often) is small but not zero — and, importantly, it is serial. Those two — setup and I/O — are your serial fraction. The stencil sweep is your parallel fraction.

Step 3 — Identify the parallelism, and the dependencies that forbid it. Look hard at the algorithm's structure, because it decides what is parallelizable:

• Within a single time step, every interior cell's new temperature is computed from the old values of its four neighbours. No cell's update depends on any other cell's new value. So all the interior updates of one step are independent — data-parallel, embarrassingly so. This is the part you parallelize, and it is a large majority of the work.
• Across time steps, the situation is the opposite. Step $n+1$ needs the completed field from step $n$; you cannot compute the future before the present. The time loop is inherently sequential and cannot be parallelized — you parallelize the work inside each step, and let the steps proceed in order. Trying to parallelize across time is a classic beginner's trap; the data dependency forbids it.

That the interior update reads only old neighbour values is not an accident — it is the explicit, two-array ("current" and "next") structure of the finite-difference stepping you built in Chapter 24, and it is precisely what makes the solver so amenable to every parallel model in this part. Good serial design paid forward into easy parallelism.

Step 4 — Estimate the ceiling with Amdahl before writing parallel code. This is the chapter's Project Checkpoint, and its point is to spend five minutes with arithmetic instead of a week with a debugger. From the profile in Step 2, estimate the serial fraction, plug it into Amdahl's Law, and read off the best speedup you could possibly get at your target core count. If the number is encouraging, proceed. If it is not — if setup and I/O are 20% of your run and your ceiling is 5× — then the useful work is not to write OpenMP; it is to go back and attack the serial fraction (buffer the I/O, write less often, overlap output with computation). Amdahl tells you where the work is before you do the work.

Step 5 — Choose the model to match the target scale, and decide strong vs weak. The taxonomy of §31.3 now pays off. If your grid fits comfortably in one node's memory and you want to use its cores, reach for OpenMP or coarrays — shared memory, least ceremony. If the grid is too large for one node, or you need thousands of cores, you must go distributed: MPI or coarrays, with the plate decomposed into tiles and halo cells exchanged at the seams. If the stencil is the whole story and you have a GPU, OpenACC offload may win big on the data-parallel update — as long as you are not drowned by host-device transfer. And decide, honestly, which question you are asking: do you need this plate solved faster (strong scaling, Amdahl, harder) or a finer plate solved in the same time (weak scaling, Gustafson, easier)? The answer shapes everything downstream, including which scaling experiment you will run to prove it worked.

Do these five steps on paper, and by the time you write your first !$omp parallel do in Chapter 33 you will know what you are parallelizing, why, what it should buy you, and how you will measure whether it did. That is the difference between engineering and hope.

🧩 Try It Yourself. Before the Project Checkpoint, guess: if the heat solver spends 98% of its time in the stencil sweep and 2% in serial setup and I/O, what is the best speedup you could ever get, on infinite cores? Write your number down. Then read the checkpoint and see whether the hard ceiling of Amdahl's Law matches your instinct. (If you guessed "about 50×," you have already internalized the law.)

Project Checkpoint

The solver is, by now, a serious piece of serial software: modular, validated against the analytical solution, tuned in Part VII, and built with aggressive flags. It is not yet parallel — that begins next chapter. This checkpoint is the plan-on-paper step, Step 4 above, made concrete: estimate the solver's ideal parallel speedup with Amdahl's Law, from its measured serial fraction, before writing a line of parallel code.

From the profiling in Chapter 28, take an illustrative split (round numbers, for the reasoning — your real profile will differ): the stencil sweeps account for 98% of run time, and the serial setup plus periodic VTK output account for the remaining 2%. So $p = 0.98$ and the serial fraction is $1 - p = 0.02$. Amdahl's Law then gives, at each core count, and in the limit:

program solver_speedup
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  ! Illustrative profile from Chapter 28: the stencil sweeps are 98% of run time,
  ! serial setup + periodic VTK output are the other 2%. (Round Tier-3 numbers.)
  real(dp), parameter :: p = 0.98_dp
  integer,  parameter :: cores(7) = [1, 2, 4, 8, 16, 32, 64]
  integer  :: k, n
  real(dp) :: s

  print '(a, f4.2)', 'Heat-solver ideal speedup (Amdahl), parallel fraction = ', p
  print '(a)', ' cores      speedup'
  do k = 1, size(cores)
    n = cores(k)
    s = 1.0_dp / ((1.0_dp - p) + p / real(n, dp))
    print '(i6, f13.4)', n, s
  end do
  print '(a, f8.4)', 'hard ceiling (N -> infinity): ', 1.0_dp / (1.0_dp - p)
end program solver_speedup

Work the ceiling by hand first: $S_{\max} = 1/(1 - 0.98) = 1/0.02 = 50$. And a couple of the rows, to trust the machine: on 8 cores, $S = 1/(0.02 + 0.98/8) = 1/(0.02 + 0.1225) = 1/0.1425 \approx 7.02$; on 64 cores, $S = 1/(0.02 + 0.98/64) = 1/(0.02 + 0.0153125) = 1/0.0353125 \approx 28.32$.

$ gfortran -std=f2018 -Wall -O2 project-checkpoint.f90 -o speedup && ./speedup
Heat-solver ideal speedup (Amdahl), parallel fraction = 0.98
 cores      speedup
     1       1.0000
     2       1.9608
     4       3.7736
     8       7.0175
    16      12.3077
    32      19.7531
    64      28.3186
hard ceiling (N -> infinity): 50.0000

Read the verdict like an engineer. Even at a healthy 98% parallel, 64 cores buys you 28×, not 64× — an efficiency of $28.3/64 \approx 44\%$ — and no number of cores will ever beat 50×, because 2% of the work will not move. That is genuinely useful to know before you invest in the parallel port: 8–16 cores of shared-memory OpenMP will give you an excellent, high-efficiency 7–12×; pushing to 64 is subject to sharply diminishing returns on this fixed problem. To go further you have two honest moves, both of which the next chapters make good on: shrink the serial 2% (overlap or parallelize the I/O — MPI-IO in Chapter 34 is one route), or grow the problem and change the question to weak scaling, where Gustafson, not Amdahl, sets the ceiling. Save this estimate; when the solver actually runs on 8 threads in Chapter 33, you will compare the measured speedup against this ideal and read the gap as your overhead. The complete program is in code/project-checkpoint.f90.

Summary

This chapter explained why the rest of Part VIII exists and gave you the two laws and the vocabulary to reason about parallelism before writing any.

The two things worth memorizing: first, Amdahl's ceiling, $S_{\max} = 1/(1-p)$ — the single most important number in parallel computing, and the reason you attack the serial fraction before you buy cores. Second, that Amdahl and Gustafson are not rivals but a pair of questions — finish this faster versus solve bigger in the same time — and naming which one you are asking is the first step of every parallel project.

Spaced Review

Three questions reaching back into Part VII, whose serial-performance work is the foundation this whole part builds on. Answer before expanding.

1. (Chapter 27.) Why can sweeping a 2D array with the inner loop over the first index be many times faster than sweeping it with the inner loop over the second — even though both produce the identical result? What is the property of Fortran's memory layout that makes this so?
   

   Answer

   Fortran stores arrays in **column-major** order: the first index varies fastest through memory. Putting the first index on the inner loop walks *consecutive* memory addresses, so each cache line brought in is fully used before the next is needed; the other order strides across memory, wasting most of every cache line and stalling on memory. Same answer, very different speed — which is why Step 1 of §31.5 insists you fix the serial code *first*, since a cache-hostile sweep would only be a fast-to-slow thing once parallelized.

2. (Chapter 29.) Name two distinct serial optimizations from Chapter 29 that you would apply to the stencil update before parallelizing it, and say in one line why doing them first matters for your eventual parallel speedup.
   

   Answer

   Any two of: choosing the column-major loop order; enabling **SIMD vectorization** so each core does several cells per instruction; cache **blocking** to reuse data while it is hot; using `do concurrent` or `contiguous` to signal independence and layout. They matter first because parallel speedup is measured against the serial baseline and is *capped* by the serial fraction (Amdahl): a leaner, faster serial kernel means a smaller serial fraction, a higher ceiling, and real rather than illusory gains from the cores you add.

3. (Chapters 27 & 29.) A colleague proposes to skip Part VII entirely — "we'll just parallelize the slow serial code across 64 cores and get our speed that way." Using Amdahl's Law and one idea from the performance chapters, explain what is wrong with this plan.
   

   Answer

   Parallelism does not fix a bad serial algorithm; it multiplies whatever serial performance you start from, and Amdahl caps even that multiplication by the serial fraction. If the code is cache-hostile or unvectorized (Chapters 27, 29), you are spreading a slow computation across 64 cores and still paying the serial-fraction ceiling — often ending far slower, and far less efficient, than tuned serial code on a handful of cores. Make the serial fast first; *then* parallelize the fast thing.

What's Next

You have the map, the laws, and a plan. Now the solver leaves the single core. Chapter 32 begins with Fortran's own answer to everything this chapter described — coarrays, the native parallel model built into the language standard, where you declare an array with an extra set of brackets and suddenly it is distributed across images running in parallel, with no external library at all. We will take the heat plate, split it across images, and teach the pieces to exchange their shared edges. The free lunch is over; time to cook with the whole kitchen.