On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Systems, Networks & Impact · Grade 9-12

Parallel Computing

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

speedup=T1Tp

Quick Answer

Parallel computing divides work so multiple processors, cores, or computers perform parts of a computation at the same time — useful when one large task can be separated into smaller tasks that run together. You use it when a job is big and splits into pieces that don't need each other's results: coloring millions of pixels, rendering movie frames, searching a huge data set. Speedup T1/Tp measures the gain. A program that takes 100 seconds on one core and 25 seconds on eight has a speedup of 4, not 8, because some steps still run in order and the cores spend time sharing out work and collecting results.

Why This 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.

Intuitive Explanation

Picture 300 quiz papers to grade at one minute each. One teacher needs 300 minutes. Three teachers who each take a pile of 100 finish in 100 minutes, because no paper's grade depends on any other paper. That is the core of parallel computing: when the pieces of a job are independent, separate processors can work on them in the same moment.

The real speedup is usually lower than the number of workers, for two reasons. First, coordination costs time. If splitting the stack and merging three score sheets takes 20 minutes, the job takes 120 minutes, a speedup of 300/120=2.5 rather than 3. Second, some work cannot be split at all. If a tenth of a program must run step by step, no number of processors can make it more than 10 times faster, because that tenth alone still takes a tenth of the original time. This ceiling is called Amdahl's law.

Two things look like parallel computing but are not. A running bank balance, where each day's total needs yesterday's, cannot be divided: day 30 has to wait for day 29, however many cores are free. And a computer with a single core that plays music while you type is switching between the two jobs every few milliseconds. It feels simultaneous, but only one instruction runs at a time, so nothing finishes sooner. The difference is physical: more than one processor must be busy in the same instant, each on its own share of the work.

Think of it like this. 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.

Core idea. Parallelism can reduce running time, but only when the work can actually be split and coordinated well.


When to Use

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.

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

How to Recognize It

Before you plan a parallel solution, look at how the steps of the job depend on one another and what hardware is available.

  1. Are several processors, cores, a GPU or many machines available to run work at the same moment?

    Yes makes parallel computing possible. On one core, splitting a problem is still Decomposition or Divide and Conquer, but the parts run one after another.

  2. Does each step need the result of the step before it, like computing each term of a sequence from the previous term?

    Yes means that part is serial and gains nothing from extra processors. Speeding it up needs a better method, which is a question of Algorithm Efficiency.

  3. Are you asked how much faster the job runs on p processors than on one?

    Yes: compute the speedup T1/Tp and compare it with p. If you are asked how running time grows with input size instead, that is Algorithm Efficiency.

  4. Does handing out the work and gathering the results take a noticeable share of the total time?

    Yes means overhead may cancel the gain, so fewer and larger pieces can be faster. If nothing is shared between processors, the program is ordinary sequential code.

Parallel Computing vs Divide and Conquer vs Decomposition vs Algorithm Efficiency

All four involve splitting work or saving time, so students treat them as one idea. The deciding question is whether separate processors actually run pieces at the same moment.

Parallel Computing

Meaning
Parallel computing runs independent pieces of a job at the same time on several processors, cores or machines.
Key test
Pieces really run simultaneously on different hardware.
Formula
S=T1Tp
Example
A render farm draws 2,000 movie frames on 100 computers, about 20 frames each.

Divide and Conquer

Meaning
Divide and conquer splits a problem into smaller problems of the same kind, solves them, and combines the answers.
Key test
It is a way to design an algorithm and can run entirely on one core.
Formula
T(n)=2T(n/2)+O(n)
Example
Merge sort splits a list in half, sorts each half, then merges the two sorted halves.

Decomposition

Meaning
Decomposition breaks a big problem into smaller parts that are easier to understand and solve.
Key test
It is a planning step; the parts may still be done one by one.
Example
Planning a school fair as tickets, food, games and cleanup before anyone starts work.

Algorithm Efficiency

Meaning
Algorithm efficiency describes how an algorithm's running time or memory grows as the input gets larger.
Key test
It cuts the total work instead of spreading it over processors.
Formula
O(log⁡n)
Example
Binary search checks about 20 items in a sorted list of a million instead of up to a million.

Formula & Notation

speedup=T1Tp
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 — Render-farm speedup

Easy

An animation has 1,000 frames. One computer renders a frame in 6 minutes, and no frame depends on another. A studio splits the frames evenly across 50 computers, after first spending 10 minutes copying the scene files to every machine. Find the time on one computer, the time on 50, and the speedup.
Show the steps and the answer
  1. One computer: T1=1000×6=6000 minutes, which is 100 hours.

    Without parallelism the frames are rendered one after another.

  2. Split the frames: 1000÷50=20 frames per machine, taking 20×6=120 minutes.

    The frames are independent, so all 50 machines can render at the same time without waiting for each other.

  3. Add the setup: T50=10+120=130 minutes.

    Every machine needs the scene files before it can start. Copying them is coordination overhead that the single computer never had.

  4. Speedup: T1/T50=6000/130≈46.

    Close to 50 because the work splits perfectly; the 10 minutes of setup is what keeps it below 50.

Answer: T1=6000 min (100 h), T50=130 min, speedup ≈46

Takeaway: Independent pieces give a speedup close to the number of machines; overhead is what keeps it below that number.

Example 2 — The part that won't split

Standard

A photo filter takes 100 s on one core: 20 s to load and save the file, which must happen in order, and 80 s to process the pixels, which divides evenly across cores. Find the time and speedup on 4 cores and on 16 cores, and the largest speedup possible.
Show the steps and the answer
  1. 4 cores: T4=20+80/4=40 s, so speedup =100/40=2.5.

    Only the 80 s of pixel work divides; the 20 s of loading and saving runs on one core however many are available.

  2. 16 cores: T16=20+80/16=25 s, so speedup =100/25=4.

    Four times as many cores save only 15 more seconds, because the serial 20 s is now most of the run.

  3. Unlimited cores: the pixel part shrinks toward 0 s, so T→20 s and speedup →100/20=5.

    The serial fraction is 20/100=0.2, and Amdahl's law caps the speedup at 1/0.2=5.

Answer: 4 cores: 40 s, speedup 2.5. 16 cores: 25 s, speedup 4. No number of cores gives a speedup above 5.

Takeaway: Measure the part that must run in order before buying processors: it sets a ceiling that no amount of hardware can break.

Example 3 — Find the mistake: splitting a loop whose steps depend on each other

Application

A savings balance starts at $1000 and grows 5% a year, so each year's balance is the previous year's times 1.05. To finish 50 years faster, Ravi gives years 1-25 to core A and years 26-50 to core B, and both cores start from $1000 at the same moment. Core B reports a year-50 balance of $3386.35. Find the mistake and correct it.
Show the steps and the answer
  1. Look at what year 26 needs: the balance at the end of year 25.

    Each step uses the previous step's result, so core B has no correct starting value until core A has finished.

  2. Work out what core B actually computed: 1000×1.0525≈3386.35.

    Starting from $1000, B's 25 multiplications gave the balance after 25 years, not 50.

  3. Compute the true value in order: 1000×1.0550≈11467.40.

    Fifty multiplications in a row take well under a microsecond on one core, far less than the cost of coordinating two cores.

  4. Or remove the dependency: give core B the starting value 1000×1.0525 from the formula.

    Parallel work needs independent pieces. A formula for each starting value means the two halves no longer wait on each other.

Answer: The year-50 balance is about $11,467.40. The years depend on each other, so the loop must run in order unless each core is given its correct starting balance.

Takeaway: Before splitting a loop, check whether each step uses the last step's result; if it does, the pieces can't run at the same time as written.

Where You'll See It

  • A group project split among teammates

    Instead of one person doing every slide, four people each build different slides at the same time — parallel work finishes faster, but only because the slides don't depend on each other.

  • Your phone playing a game while downloading an update

    Modern phones have multiple cores, so different cores handle the game and the download simultaneously instead of forcing you to wait for one to finish.

  • Rendering a movie's special effects on a render farm

    Studios split a movie into thousands of frames and send them to many computers at once, so a job that would take one machine years finishes in days.

Common Mistakes

  1. The slip: Doubling the number of processors always halves the running time.

    Why it's tempting: More workers seems like it should mean proportionally faster work, like a perfect assembly line.

    Instead: Speedup is limited by the parts that can't be parallelized and by coordination overhead; adding processors gives diminishing returns (Amdahl's idea).

  2. The slip: Any task can be made faster by running it in parallel.

    Why it's tempting: Splitting work feels universally helpful, so it seems to apply to everything.

    Instead: Only tasks that can be divided into independent pieces benefit; steps that depend on each other's results must run in order.

  3. The slip: Parallel computing has no extra cost — it's pure speed.

    Why it's tempting: We focus on the time saved and forget the work of dividing and recombining.

    Instead: Coordinating and communicating between processors adds overhead, which can outweigh the gains for small or tightly-dependent tasks.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. A task takes 120 seconds on 1 core and 40 seconds on 4 cores. What is the speedup T1Tp, and what would the ideal speedup be?

    Hint: Divide the one-core time by the four-core time.

  2. A program takes 100 s on one core. 20 s of it must run in order; the other 80 s can be split evenly across cores. How long does it take on 4 cores, and what is the speedup?

    Hint: Only the splittable part gets faster when you add cores.

  3. Which loop can run in parallel? Loop A: for i from 1 to 1000, b[i] = a[i] * 2. Loop B: for i from 2 to 1000, a[i] = a[i-1] + 1.

    Hint: Check whether any step needs the result of an earlier step.

  4. Splitting a job across p cores, the work takes 60p seconds, plus 2 seconds of coordination for each core. Find the total time for p=2, 4 and 10. Which of these is fastest?

    Hint: Add the work time and the coordination time for each value of p.

  5. Task 1: design the exact steps to find the largest number in a list. Task 2: split a list of 1,000,000 numbers into 4 chunks, let each core find its chunk's largest, then compare the 4 results. Which task is about parallel computing?

    Hint: Which task has parts running at the same time on different processors?

  6. A program has a 20 s part that must run in order and an 80 s part that can be split. A student says: "It took 40 s on 4 cores, so on 100 cores it will take 1.6 s." What is wrong?

    Hint: Which part of the time can never get shorter, however many cores you add?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

What does Amdahl's law say in numbers?

If a fraction ss of a program must run serially, the speedup on pp processors is at most 1s+(1−s)/p\frac{1}{s + (1-s)/p}. With s=0.1s = 0.1, eight cores give at most 1/(0.1+0.9/8)≈4.71/(0.1 + 0.9/8) \approx 4.7, and even unlimited cores cannot beat 1/s=101/s = 10. That ceiling is why engineers work to shrink the serial part before buying more hardware.

Why are graphics cards so good at parallel work?

A CPU has a handful of powerful cores built to handle varied, branching tasks quickly. A GPU has thousands of simpler cores designed to do the same operation on many pieces of data at once, such as shading every pixel of a frame. That design suits images, physics simulations and training neural networks, which mostly come down to huge grids of numbers multiplied in the same way.

Is running a game and a download at the same time parallel computing?

Only partly. Running several separate jobs at once is usually called multitasking or concurrency, while parallel computing usually means splitting one job so its pieces finish sooner. On a single core, the operating system can still juggle both jobs by switching quickly between them, which looks simultaneous but is not parallel at all. The test is whether two pieces of work truly run at the same instant.

Why can a parallel program give different answers on different runs?

When two processors update the same value at nearly the same moment, the result can depend on which one happens to go first. This is called a race condition. For example, two cores each read a counter of 5, add 1 and write 6, so one increase is lost. Programmers prevent it with locks, or by giving each core its own counter and adding them up at the end.

Learning Path

Parallel Computing

You are here

You need Algorithm (a job as a sequence of steps) and Computing System (processors, memory and how they connect) first. Parallel computing adds the question of which steps can run at the same time on different processors, and a way to measure the gain, speedup T1/Tp, along with its limits. It leads to Artificial Intelligence, where training a model means billions of independent multiplications run side by side on GPUs.

See Also