Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Parallel Computing.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
Concept Recap
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.
Instead of one person doing every part of a job in order, several people work on different pieces at the same time.
Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.
What to Focus On
Core idea:Parallelism can reduce running time, but only when the work can actually be split and coordinated well.
Common stuck point:Not every problem parallelizes well. Some steps still have to happen in sequence.
Sense of Study hint:When checking whether a task can run in parallel, look for parts that do not depend on each other. Then compare the extra coordination cost against the time saved.
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.
Answer
4×
First step
1
With infinite processors, parallel part takes near 0 time.
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
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.
Example 4
hard
A pipeline has 5 stages of 2 ms each. Without pipelining, processing 100 items takes how long? With pipelining?
Practice Problems
Try these problems on your own first, then open the solution to compare your method.
Example 1
easy
A task takes 60 seconds on 1 processor. If it splits perfectly across 3 processors, how long does it take?60 ÷ 3 = 20 s — perfect split across 3 processors
Example 2
easy
Speedup is defined as T1/Tp. If T1=100s and Tp=25s, what is the speedup?
Example 3
easy
Two tasks: (a) summing independent parts of a list, (b) computing a running total where each step needs the previous. Which parallelizes well?Independent parts (a): fan out and run simultaneously
Example 4
easy
True or false: doubling the number of processors always exactly halves the running time.
Example 5
easy
What is the main cost that grows when you add many processors that must coordinate?
Example 6
easy
A job has a part that must run alone (serial) and a part that can split. Which part limits the maximum speedup?
Example 7
easy
Four workers paint four identical, independent fences. One fence takes one worker 2 hours. With one worker per fence, how long for all four?4 independent fences, 1 worker each — all done in 2 hours
Example 8
easy
In the speedup formula T1/Tp, what does Tp represent?
Example 9
medium
A program is 80% parallelizable and 20% strictly serial. With unlimited processors, the parallel part takes ~0 time. What is the maximum possible speedup?
Example 10
medium
A task takes 100s. Half is parallelizable. On 2 processors, the parallel half takes 25s and the serial half still 50s. What is the total time and the speedup?
Example 11
medium
With 4 processors a task achieves 3.2x speedup. What is the parallel efficiency (speedup per processor)?Speedup on 4 processors = 3.2×; efficiency = 3.2/4 = 0.80
Example 12
medium
Adding processors past a point makes a parallel program SLOWER. What most likely causes this?
Example 13
medium
Two processors both update a shared counter at the same time and one update is lost. What parallel-computing problem is this, and one fix?Both threads read 100, add 50, write back — one update is lost (race condition)
Example 14
medium
A pipeline has 3 stages, each taking 1 unit, processing many items. After the pipeline fills, how many items complete per unit of time?3-stage pipeline: 1 unit per stage; throughput = 1 item/unit once full
Example 15
medium
Why can a task that is 100% sequential get NO benefit from parallel computing?
Example 16
medium
A job takes 90s on 1 processor. The whole job is parallelizable and splits perfectly across 6 processors. What is the running time and the speedup?
Example 17
medium
Two parallel threads each read a shared balance of 100, add 50, and write back, but interleave so the result is 150 instead of 200. Name the bug and the standard fix.
Example 18
challenge
A program is 90% parallelizable. Compare the speedup on 10 processors versus the theoretical maximum with infinite processors.Amdahl (90% parallel): at p=10 speedup ≈ 5.26×; ceiling = 1/0.10 = 10×
Example 19
challenge
You can split a 1,000,000-element sum across processors, but combining partial sums costs log2(p) merge steps. With p=8, the parallel work is ~1000000/8 and merging adds 3 steps. Why does merging cost grow only logarithmically?8 → 4 → 2 → 1: log₂(8) = 3 merge levels
Example 20
challenge
Adding a 5th processor to a 4-processor system raises speedup from 3.5x to only 3.6x. Using efficiency, explain whether adding more processors is worthwhile here.
Example 21
easy
A 40-second task splits perfectly across 4 processors. How long does each processor take?
Example 22
easy
Speedup formula is T1/Tp. If T1=120s and Tp=30s, find the speedup.
Example 23
easy
True or false: every task can be parallelized.
Example 24
easy
A serial task takes 90s. On 9 processors with perfect splitting, what is Tp?
Example 25
easy
Twelve identical loaves of bread are baked in 12 separate ovens. Each takes 30 minutes. How long for all 12?
Example 26
easy
In T1/Tp, what does the subscript 1 mean?
Example 27
medium
A 200s task: 40s serial, 160s parallelizable. On 8 processors, parallel part takes 20s. Find total time and speedup.
Example 28
medium
With 8 processors a task reaches 6x speedup. What is the parallel efficiency?
Example 29
medium
Two threads each read a counter at 10, both add 1, both write 11. The correct result was 12. What is this bug called?
Example 30
medium
A 4-stage pipeline takes 1 unit per stage. To process 10 items, how many time units from start to last item out?
Example 31
medium
Two processes each hold a lock the other needs and wait forever. What is this called?
Example 32
medium
A 120s job is fully parallelizable across 5 processors with perfect splitting. Time and speedup?
Example 33
medium
A merge of 64 partial results in a parallel reduction takes log264 steps. How many steps?
Example 34
medium
A 32-core machine runs a 90% parallelizable workload. Using Amdahl's law S=1/(s+(1−s)/p), find speedup.
Example 35
hard
A program is 95% parallelizable. Find speedup with 20 processors using S=1/(s+(1−s)/p).
Example 36
hard
A task has communication cost c(p)=2p ms and parallel work W(p)=1000/p ms. Find total time at p=10 and p=50.
Example 37
hard
A parallel sort on 8 cores achieves 6x speedup. A team adds 8 more cores and sees only 7x. Compute efficiencies and decide if adding more cores is worth it.
Example 38
hard
Why does false sharing in shared-memory parallel code slow programs down?
Example 39
hard
A map step takes 20s and a reduce step takes 5s, plus 3s of communication. Across 5 workers, what is total time and throughput per second of items if there are 1,000,000 items?
Example 40
challenge
A team applies Gustafson's law: with p=16 processors and parallel fraction 0.9, scaled speedup is S=p−s(p−1) where s=0.1. Compute S.
Example 41
challenge
A reduction over n=220 elements uses a tree reduction. With p=n/2 processors per level, what is total parallel time in tree levels?
Example 42
medium
A 256-task workload runs on 16 cores. If tasks take equal time and load is balanced, how many tasks per core?