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
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
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
Worked examples
Example 1
mediumShow solution
Answer
First step
See the full worked solution + why-it-works coaching
SetupKey insightWhy it worksCommon pitfallConnection
Example 2
mediumExample 3
hardCommon 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.