How do parallel and distributed computing speed up work, and what are the limits of the speedup?
Topic 4.3 Parallel and Distributed Computing: parallel computing runs tasks simultaneously on multiple processors and distributed computing spreads work across multiple computers, improving speed but with limits.
A focused answer to AP CSP Topic 4.3, covering sequential versus parallel computing, distributed computing, speedup and its calculation, why some tasks cannot be fully parallelised, the benefits of solving large problems, and worked speedup reasoning.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this topic is asking
The College Board (Topic 4.3) wants you to understand parallel and distributed computing. Sequential computing runs one operation at a time; parallel computing runs multiple operations simultaneously on multiple processors; distributed computing spreads work across multiple computers. You must compute speedup (sequential time divided by parallel time), explain why speedup is limited by the parts of a task that cannot be parallelised, and recognize the benefits for large-scale problems.
Sequential, parallel and distributed
Parallel and distributed computing both do work simultaneously; the difference is parallel uses multiple processors in one machine while distributed spreads across separate machines.
Speedup
Why speedup is limited
Not every part of a task can run in parallel. Some steps are sequential: they depend on the result of an earlier step and must wait. The sequential portion takes the same time no matter how many processors you add. So:
- Adding processors only speeds up the parallelisable portion.
- The sequential portion sets a floor on the total time.
- This produces diminishing returns: each extra processor helps less, and the speedup can never exceed what the sequential part allows.
Benefits
Parallel and distributed computing let us solve problems that are too large or too slow for a single sequential machine: processing huge data sets, running large simulations, and serving millions of users. Distributed systems also spread load and add redundancy.
Try this
Q1. A task takes 80 seconds sequentially and 16 seconds in parallel. What is the speedup? [1 point]
- Cue. Speedup is
80 / 16 = 5.
Q2. Why does adding more processors give diminishing returns? [2 points]
- Cue. Only the parallelisable portion of a task speeds up; the sequential portion takes the same time regardless of processors, so each added processor contributes less and the total time cannot fall below the sequential part.
Exam-style practice questions
Practice questions written in the style of College Board exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AP 2022 (style)1 marksMultiple choice. A task takes 60 seconds to run sequentially. When run on a parallel system it takes 20 seconds. What is the speedup?
(A) 40
(B) 80
(C) 3
(D) 0.33
Show worked answer →
The answer is (C).
Speedup is the sequential time divided by the parallel time: 60 / 20 = 3. The parallel solution is 3 times as fast. (A) 40 is the difference in seconds, not the speedup ratio. (B) 80 is the sum. (D) is the inverse ratio.
Markers reward computing speedup as the ratio of sequential time to parallel time, not the difference.
AP 2021 (style)2 marksFree response (short). Explain why doubling the number of processors does not always halve the time a program takes, referring to the parts of a task that cannot be done in parallel.
Show worked answer →
A 2-point question on the limits of parallel speedup.
Point 1: Many tasks have a portion that must be done sequentially (steps that depend on earlier results and cannot run at the same time). Only the parallelisable portion benefits from extra processors.
Point 2: Because the sequential portion takes the same time no matter how many processors are added, the overall speedup is limited: adding processors gives diminishing returns and can never make the program faster than its sequential part allows. A common error is to assume speedup scales perfectly with processor count.
Related dot points
- Topic 4.1 The Internet: the Internet is a network of networks that moves data in packets using protocols such as IP and TCP, with addressing, routing and standards enabling scalable communication.
A focused answer to AP CSP Topic 4.1, covering the Internet as a network of networks, IP addresses, packets and packet switching, protocols (IP, TCP, HTTP, DNS), bandwidth and latency, redundancy in routing, and why open standards enable scalability.
- Topic 4.2 Fault Tolerance: a system is fault tolerant if it continues to operate when some components fail; redundancy (multiple paths or copies) is the main way networks achieve fault tolerance.
A focused answer to AP CSP Topic 4.2, covering what fault tolerance means, how redundancy of paths and data provides it, why the Internet is fault tolerant, the difference between a fault-tolerant and a non-redundant system, and the costs of redundancy.
- Topic 3.11/3.17/3.18 Binary Search and Efficiency: binary search finds a value in a sorted list far faster than linear search, and algorithms are compared by efficiency, with some problems being unsolvable or only approximable.
A focused answer to AP CSP Topics 3.11, 3.17 and 3.18, covering linear versus binary search, why binary search needs a sorted list, reasonable versus unreasonable running time, polynomial versus exponential growth, heuristics, and undecidable problems.
- Topic 2.4 Using Programs with Data: programs process large data sets through cleaning, filtering, classifying and transforming data, often using lists and iteration to scale to large amounts of data.
A focused answer to AP CSP Topic 2.4, covering why programs are essential for large data sets, cleaning and classifying data, filtering with conditionals, using lists and iteration to process data at scale, and visualizing results, with worked pseudocode.
- Topic 3.15/3.16 Random Values and Simulations: simulations are simplified, abstract models of real phenomena that often use random values to represent variability, trading detail for speed, safety and repeatability.
A focused answer to AP CSP Topics 3.15 and 3.16, covering the RANDOM procedure and generating random values, what a simulation is, why simulations are abstractions, their advantages and limitations, and using randomness to model variability, with worked pseudocode.
Sources & how we know this
- AP Computer Science Principles Course and Exam Description — College Board (2025)