One at a time, or many at once?
Most programs you read are sequential: operations are performed in order, one at a time. A sequential solution takes as long as the sum of all of its steps. If a program has three steps of 10, 20 and 30 seconds, a sequential run takes 60 seconds.
Some problems are made of parts that do not depend on each other. Then the work can be shared. Two models are used:
- Parallel computing: the program is broken into multiple smaller sequential computing operations, some of which are performed simultaneously. A single computer with several processors, or a group of machines, can do this.
- Distributed computing: multiple devices are used to run a program. The devices are linked by a network, which is why this topic sits with Computer Systems and Networks.
Imagine marking 200 exam scripts. One marker does them one after another (sequential). Four markers each take 50 (parallel). If the markers work in different schools and send results over the Internet (distributed), they can even take part from different places. But everyone must wait for the head examiner to write the summary report, which can only be done after all the marking. That job cannot be shared.
Calculating the time
A parallel solution has two kinds of tasks.
- Sequential tasks: they must run one after another (or must run alone).
- Parallel tasks: a group that can run at the same time on different processors.
A parallel solution takes as long as its sequential tasks plus the longest of its parallel tasks. If there are several groups of parallel tasks, add the longest of each group. The reason is that the group is finished only when its slowest member is finished; the shorter tasks run in the “gaps”.
The efficiency of two solutions can be compared by comparing the time they take for the same job. The speedup of a parallel solution is
speedup = time taken sequentially ÷ time taken in parallel.
A speedup of 2 means the parallel solution took half as long; a speedup of 1 means no gain.
Why more processors do not mean unlimited speed
Parallel computing consists of a parallel portion and a sequential portion. Only the parallel portion can be shared out. When you add more processors, the parallel portion gets shorter but the sequential portion stays the same. So the total time can never be less than the sequential portion: the efficiency of the solution is still limited by the sequential portion. At some point, adding more parallel capacity no longer meaningfully increases efficiency. This is why the speedup in real systems is usually less than the number of processors.
Benefits and challenges
Benefits.
- Parallel solutions can scale more effectively than sequential ones: when the amount of work doubles, adding processors can keep the time down.
- Distributed computing allows problems to be solved that could not be solved on a single computer because of the processing time or storage needed, and it lets much larger problems be solved quicker than on a single computer.
Challenges.
- The sequential portion limits the gain.
- Tasks must be split up and the results combined, which needs coordination.
- Distributed systems rely on a network, so communication takes time and devices or connections can fail (Topic 4.2).
Worked example 1: sequential time, parallel time and speedup
Scenario. A fictional photo-processing job has four tasks: task 1 loads the images (30 s) and must run first; tasks 2, 3 and 4 then each process a different batch of photos (40 s, 20 s and 50 s) and can run at the same time on different processors; the job ends when all are done.
Task. Compute the sequential time, the parallel time and the speedup.
Sequential time. Add all: 30 + 40 + 20 + 50 = 140 seconds.
Parallel time. Task 1 is a sequential task (30 s). Tasks 2, 3 and 4 form one parallel group; the group takes as long as its longest member, 50 s. So the time is 30 + 50 = 80 seconds.
Speedup. 140 ÷ 80 = 1.75. The parallel solution took about 57% of the time (80 ÷ 140 = 0.571).
Check. The parallel time cannot be less than the longest single task (50 s), nor less than 30 + 50 = 80, the sequential task plus the longest parallel task. Also note task 3 (20 s) finishes long before the others and its processor sits idle for 30 s: parallel solutions are not perfectly efficient.
Worked example 2: the sequential portion sets a limit
Scenario. A fictional program takes 100 seconds when run sequentially. 20 seconds of it is a sequential portion that cannot be split. The other 80 seconds can be divided evenly among any number of processors.
Task. Find the time and speedup with 1, 2, 4, 8 and 80 processors, and the best speedup possible.
The parallel time with p processors is 20 + 80 ÷ p.
| Processors p | Time = 20 + 80 ÷ p | Speedup = 100 ÷ time |
|---|---|---|
| 1 | 100 s | 1.00 |
| 2 | 20 + 40 = 60 s | 1.67 |
| 4 | 20 + 20 = 40 s | 2.50 |
| 8 | 20 + 10 = 30 s | 3.33 |
| 80 | 20 + 1 = 21 s | 4.76 |
Best possible. Even with unlimited processors the parallel portion shrinks towards 0 but the 20 s remains: the time cannot go below 20 s, so the speedup cannot exceed 100 ÷ 20 = 5.
Interpretation. Going from 1 to 2 processors saves 40 s. Going from 8 to 80 processors (ten times as many) saves only 9 s (30 down to 21). The gain per extra processor shrinks, so adding more parallel portions no longer meaningfully increases efficiency. To do better, the programmers must shrink the sequential portion.
Check. At p = 1 the formula gives 100 s, matching the sequential run, which confirms the model.
Reading parallel timing questions
Questions about parallel computing are mostly careful reading. Begin by sorting the tasks into sequential (must run alone, or one after another) and parallel groups (independent and able to run at the same time). Draw a short timeline if it helps: tasks that run in sequence go end to end, and tasks that run together go in stacked rows. The time for a group is the length of its longest row.
Be careful when a task depends on another. If task C needs the results of tasks A and B, it cannot start until both are done, so it belongs after the parallel group, not inside it. Also check how many processors there are. If there are three tasks in a group but only two processors, the third has to wait for one of the first two, and the simple rule of taking the longest no longer applies; exam questions normally state that each task has its own processor, or give a timeline.
Where distributed computing is used
A web search is answered by many servers, each holding part of the index, working on your query at the same time. A film studio renders the frames of an animated film on a farm of computers, each doing a different set of frames. Volunteer projects let thousands of home computers analyse small pieces of scientific data when they would otherwise be idle. In each case the problem is too big for one computer in time or storage, the work can be split into pieces that do not depend on each other, and a small sequential part (collecting and combining results) remains.
Common misconceptions
- “Parallel means the time is the total divided by the number of processors.” Only the parallel portion can be divided; the sequential tasks still take their full time, and the group takes as long as its longest task.
- “Doubling processors doubles the speed.” The sequential portion limits the gain.
- “Parallel and distributed are the same.” Parallel means parts run at the same time; distributed means multiple devices run a program.
- “Add the times of the parallel tasks.” Add only the longest one in each parallel group.
- “Speedup is parallel time divided by sequential time.” It is sequential time divided by parallel time.
- “Distributed computing is only about speed.” It also solves problems too big for one computer’s storage.
- “A sequential program is bad.” Some problems cannot be split, and sequential programs are simpler and cheaper.
Where this leads
This completes Big Idea 4. Unit 2 mentioned that large data sets may need parallel systems, and Unit 5 looks at how crowdsourcing and citizen science use many people’s devices. Practise with the practice questions, recap with the revision notes, and check your skills on the checklist. Then try the Unit 4 diagnostic.
Quick questions
How do I calculate the time for a parallel solution?
Add the times of the tasks that must run one after another (the sequential tasks), and for each group of tasks that run at the same time add only the longest one in the group.
What is speedup?
The time the task took sequentially divided by the time it took in parallel. A speedup of 2 means the parallel solution took half as long.
Why can't I just add more processors to make it as fast as I like?
The sequential portion cannot be split up. However many parallel parts you add, the program still needs at least the time of its sequential tasks, so at some point extra parallel parts stop meaningfully increasing efficiency.
What is the difference between parallel and distributed computing?
Parallel computing runs parts of a program at the same time. Distributed computing uses multiple devices to run a program. Distributed computing is usually also parallel, and it lets you use many computers linked by a network.