Parallel & Distributed Computing
- Distinguish sequential, parallel, and distributed computing
- Compute the speedup of a parallel solution over a sequential one
- Explain why speedup is limited by the portion that must run sequentially
Sequential, parallel, distributed
A sequential computing model runs one operation at a time, start to finish. A parallel computing model breaks a program into parts that run at the same time on multiple processors, then combines the results. A distributed computing model uses multiple separate computers (often networked across locations) to work on a single problem — essential for problems too big for any one machine. Parallel and distributed computing exist to finish large jobs faster than a single processor working sequentially ever could.
Measuring speedup
The benefit of a parallel solution is measured as speedup: the time the sequential solution takes divided by the time the parallel solution takes. If a task takes 60 seconds sequentially and 20 seconds in parallel, the speedup is 60 / 20 = 3 times. A speedup of 3 means the parallel version finished in one-third the time. Speedup tells you how much you gained by running work simultaneously — and it is the standard way the exam quantifies the advantage of parallelism.
The limits of parallelism
Parallelism does not scale without limit. Most programs have a portion that must run sequentially — steps that depend on earlier results and cannot be split — plus a portion that can be parallelized. Only the parallel portion speeds up with more processors; the sequential portion sets a floor on the total time. So doubling the processors does not simply halve the time, and adding processors yields ever-smaller gains once the parallel part is already fast. Coordination between processors also adds overhead.
A task takes 90 seconds run sequentially. Split across processors, the parallel version finishes in 30 seconds. What is the speedup, and what does it mean?
- 1.Speedup = sequential time / parallel time.
- 2.Substitute the values: 90 / 30 = 3.
- 3.A speedup of 3 means the parallel solution ran three times faster — it took one-third of the sequential time.
A program runs in 120 seconds on a single processor. A parallel version completes the same work in 40 seconds. What is the speedup?
Speedup is always sequential ÷ parallel — the bigger number on top. A speedup greater than 1 means faster; if you ever compute a value below 1, you divided the wrong way.
Why does doubling the number of processors usually fail to cut a program’s running time exactly in half?
The exam’s key insight about parallelism: only the parallelizable portion speeds up, so the sequential part limits the total speedup. More processors give diminishing returns — never assume time falls in direct proportion to processor count.
Answer the 2 checkpoints as you read.
Sign in to save your progress