Parallel Computing Formula

Parallel computing is the practice of dividing work so multiple processors, cores, or computers can perform parts of the computation at the same time.

The Formula

speedup=T1Tp

Ask yourself: Can the job be split into pieces that do not need each other's results, so several processors work on them at once?

Quick example

A graphics card can process many pixels in parallel when rendering an image, and a data center can split a large computation across many machines.

What this formula means

Parallel computing is the practice of dividing work so multiple processors, cores, or computers can perform parts of the computation at the same time. It is useful when one large task can be separated into smaller tasks that can run together.

A kitchen with four cooks chops four piles of vegetables four times as fast, but it can't bake one cake four times faster: the batter must be mixed before it goes in the oven. Someone also has to hand out the piles and collect the bowls, and with too many cooks that handing-out takes longer than the chopping.

Formal view

Parallel computing distributes work across multiple processing units. Performance is often described by speedup T1/Tp, comparing one processor to p processors.

Worked examples

Example 1

medium
By Amdahl's law, with serial fraction s=0.25 and infinite processors, maximum speedup is 1/s. Compute it.
Show solution

Answer

4×

First step

1.
With infinite processors, parallel part takes near 0 time.

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
A task is 60% parallelizable. With unlimited processors the parallel part takes 0. What is the max speedup?

Example 3

hard
On 4 processors a 100s task takes 30s. Compute speedup, efficiency, and serial fraction by Amdahl.

Common mistakes

  • Assuming more processors always produce proportional speedup
  • Ignoring the overhead of coordination and communication
  • Trying to parallelize steps that depend heavily on each other

Why this formula matters

Around 2005, processor clock speeds stopped climbing because faster chips ran too hot, so most speed gains since then have come from more cores: a phone has six to eight, a graphics card has thousands. Knowing which parts of a job can split lets you predict how much faster it can get. Without that, you buy a 16-core machine for a program whose slow part runs in order and see almost no change.

Frequently asked questions

What is the Parallel Computing formula?

Parallel computing is the practice of dividing work so multiple processors, cores, or computers can perform parts of the computation at the same time. It is useful when one large task can be separated into smaller tasks that can run together.

How do you use the Parallel Computing formula?

Reach for parallel computing when a job is large and made of many independent pieces: each pixel, frame, file or data row can be handled without waiting for the others. Signals include cores, GPUs, clusters, render farms and speedup. If each step needs the previous step's result, the pieces can't run together; analyze it as a step-by-step Algorithm instead. If the question is what parts a single machine has and what each one does, that is Computing System.

Why is the Parallel Computing formula important in CS Thinking?

Around 2005, processor clock speeds stopped climbing because faster chips ran too hot, so most speed gains since then have come from more cores: a phone has six to eight, a graphics card has thousands. Knowing which parts of a job can split lets you predict how much faster it can get. Without that, you buy a 16-core machine for a program whose slow part runs in order and see almost no change.

What do students get wrong about Parallel Computing?

Not every problem parallelizes well. Some steps still have to happen in sequence.

What should I learn before the Parallel Computing formula?

Before studying the Parallel Computing formula, you should understand: computing system, algorithm.