Calculate the time for a sequential solution as the sum of all its steps
Calculate the time for a parallel solution as sequential tasks plus the longest parallel task
Calculate speedup as sequential time divided by parallel time
Explain why the sequential portion of a program limits parallel efficiency (Amdahl's Law concept)
Distinguish parallel computing from distributed computing and describe the benefits of each
📈 Exam Weight: 11-15% (BI4 combined)
📝 CED Standards: CSN-2.A, CSN-2.B
✅ 5 MCQs • 5 FAQs
💡
Exam Impact: Topic 4.3 has the highest calculation density in BI4. Speedup calculation and the sequential-bottleneck concept appear on nearly every AP exam. Students who can't do the math lose 2-3 points.
Why This Matters
Rendering a 2-hour 3D movie frame by frame would take one computer thousands of years. Pixar uses tens of thousands of computers working simultaneously -- each rendering a different frame. The same problem, split across many processors. This is parallel computing, and understanding how to calculate exactly how much faster it makes things is what Topic 4.3 tests.
Three Computing Models
The AP exam tests three models of computation:
Model
Definition
Key Property
Sequential
Operations performed in order, one at a time
Total time = sum of all step times
Parallel
Program broken into simultaneous smaller sequential operations on one device/machine
Total time = sequential tasks + LONGEST parallel task
Distributed
Multiple separate computing devices run parts of the program
Enables problems too large for one computer; scales across geography
Parallel vs Distributed: Parallel computing splits tasks across multiple processors or cores within one system. Distributed computing splits tasks across multiple separate computers (which may be geographically separated). They are not the same -- and the AP exam tests this distinction.
Sequential Time: Add Everything Up
In a sequential model, every task must complete before the next begins. Total time is simply the sum of all task times.
Tasks: A = 10s, B = 6s, C = 8s, D = 4s (all sequential)
Sequential time: 10 + 6 + 8 + 4 = 28 seconds
This is the baseline. Any parallel or distributed approach is evaluated by how much it improves on this number.
In a parallel model, some tasks can run simultaneously. The CED formula:
Parallel Time = Time for Sequential Tasks + Time for Longest Parallel Task
The key insight: parallel tasks don't all add together -- they overlap. The bottleneck is whichever parallel task takes the longest, because all other parallel tasks finish while that one is still running.
Example: Task A must run first (10s). Then B(6s), C(8s), D(4s) can run in parallel.
Sequential portion: A = 10s
Parallel tasks: B=6s, C=8s, D=4s -- longest is C at 8s
Parallel total: 10 + 8 = 18 secondsTime saved: 28 - 18 = 10 seconds
Most common exam mistake: Students add all parallel task times instead of taking only the longest. If B, C, and D run in parallel, the time is NOT 6+8+4=18 more seconds. It is only 8 seconds (the longest). B and D finish first and their time is “free” -- they ran while C was still working.
Speedup: The Efficiency Ratio
Speedup measures how much faster the parallel solution is compared to the sequential one:
A speedup of 1.56 means the parallel solution finishes in 1/1.56 of the time -- about 64% of the original duration. A speedup of 2.0 would mean exactly twice as fast (half the time). A speedup of 1.0 means no improvement at all.
The Sequential Bottleneck (Amdahl's Law Concept)
No matter how many parallel processors you add, the sequential portion of the program cannot be parallelized. It always runs start-to-finish in order. This creates a hard limit on how fast the parallel solution can be.
The CED states: “When increasing the use of parallel computing in a solution, the efficiency of the solution is still limited by the sequential portion. This means that at some point, adding parallel portions will no longer meaningfully increase efficiency.”
Worked example to show the limit:
Sequential portion: Task A = 10s (CANNOT be parallelized)
Parallel portion: B+C+D can be split across any number of processors
With 3 processors: parallel time = 10 + 8 = 18s
With 100 processors: still = 10 + 8 = 18s (longest parallel task is still 8s)
With infinite processors: still = 10 + 8 = 18s
Floor time = 10s (sequential) + time of longest individual taskAdding more processors beyond 3 gives ZERO benefit here.
This is the essence of Amdahl’s Law: if 50% of a program is sequential, the maximum possible speedup is 2x -- no matter how many processors you use.
Distributed Computing: Beyond One Machine
Distributed computing differs from parallel computing in that it uses multiple separate computing devices, often across a network. Benefits:
Enables problems too large for one computer: Storage or processing requirements exceed any single machine’s capacity
Faster for very large problems: More total computing power than any single system
Geographic distribution: Devices can be anywhere -- useful for global services
Scalability: Add more machines as demand grows
Real examples: SETI@home distributed telescope data analysis across millions of volunteer computers. Weather forecasting runs on distributed supercomputer clusters. Google’s search index is distributed across thousands of servers. Bitcoin mining is distributed across millions of devices worldwide.
Distributed computing also introduces challenges: network latency between machines, synchronization overhead, and the complexity of managing failures across many devices.
Practice MCQs
Predict your answer before clicking. These questions match AP exam difficulty and phrasing.
🔎 MCQ 1 of 5
Tasks A(5s), B(3s), C(7s), D(2s), E(4s). A must run first. B, C, D, E can run in parallel after A. What is the total parallel execution time?
Predict your answer before clicking.
🔎 MCQ 2 of 5
A program runs sequentially in 40 seconds. In parallel, it runs in 25 seconds. What is the speedup?
Predict your answer before clicking.
🔎 MCQ 3 of 5
A programmer adds 10 more processors to a parallel solution but sees no improvement in total runtime. What MOST LIKELY explains this?
Predict your answer before clicking.
🔎 MCQ 4 of 5
Which statement about distributed computing is CORRECT? I. Distributed computing allows problems to be solved that are too large for a single computer II. Distributed computing requires all devices to be in the same physical location III. Distributed computing can solve problems faster than a single computer for large datasets
Predict your answer before clicking.
🔎 MCQ 5 of 5
A sequential program takes 60 seconds. In parallel, the 40-second sequential portion cannot be parallelized, but the remaining 20 seconds can be distributed across unlimited processors. What is the MINIMUM possible parallel runtime?
Predict your answer before clicking.
Frequently Asked Questions
Parallel Time = Time for Sequential Tasks + Time for the LONGEST Parallel Task. The sequential tasks must run in order. The parallel tasks all run simultaneously, so only the longest one matters for total time.
Speedup = Sequential Time / Parallel Time. A speedup of 2.0 means the parallel solution is twice as fast (takes half the time). A speedup of 1.0 means no improvement.
The sequential portion cannot be split across processors -- each step depends on the previous one. No matter how many processors run the parallel portion, the sequential portion always adds its full time to the total. This is the Amdahl's Law concept the AP exam tests.
Parallel computing splits tasks across multiple processors or cores within a single computing system. Distributed computing splits tasks across multiple separate computers that communicate over a network. The AP exam specifically tests this distinction -- they are not the same.
When a problem requires more storage or processing power than a single computer can provide, when problems can be divided into independent sub-problems, when geographic distribution adds value (like serving users worldwide), and when fault tolerance is important (distributed systems can continue if one node fails).
Whether you're a student, parent, or teacher — I'd love to hear from you.
Just want free AP CS resources?
Enter your email below and check the subscribe box — no message needed.
Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
Typically responds within 24 hours
✓
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.