AP CSP Big Idea 4 Parallel Computing

AP CSP Parallel vs. Sequential Computing: Complete Guide (2025‑2026)

Sequential computing executes tasks one at a time on a single processor. Parallel computing executes multiple tasks simultaneously on multiple processors. Parallel computing can dramatically reduce the time needed for large computations — but only when tasks can be divided into independent parts. AP CSP tests the speedup calculation, when parallelism is and is not possible, and why some tasks resist parallelization despite having multiple processors available.

Sequential vs. Parallel
Calculating Speedup
Limits of Parallel Computing
Common Exam Pitfalls
Check for Understanding (6 Questions)
Frequently Asked Questions

NMaximum theoretical speedup with N processors if all tasks are independent

1Sequential bottleneck: even 1 dependent step limits the entire parallel speedup

~1.5xTypical real-world speedup when adding a second processor (vs. theoretical 2x)

Sequential vs. Parallel

Parallel computing achieves a 3x speedup here because all three tasks are completely independent — none depends on another’s output. Real-world speedup is usually less than theoretical maximum.

Scenario — When Can You Parallelize?

A program has four tasks: (A) load data from disk, (B) validate the data, (C) analyze the data, (D) save the results. Task B requires A to finish first. Task C requires B to finish first. Task D requires C to finish first.

Can any of these tasks be parallelized? What is the maximum speedup from using 4 processors?

Answer

None of these tasks can be parallelized because each depends on the previous one’s output. This is a sequential dependency chain: A→B→C→D. Adding 4 processors provides zero speedup for this workflow. The tasks must execute in order regardless of how many processors are available. This is a critical AP exam concept: parallelism only helps when tasks are independent of each other.

Calculating Speedup

Calculating Parallel Time

Add up parallel segments

S
e
q
u
e
n
t
i
a
l
t
i
m
e
=
s
u
m
o
f
a
l
l
t
a
s
k
t
i
m
e
s
<
b
r
>
P
a
r
a
l
l
e
l
t
i
m
e
=
l
o
n
g
e
s
t
i
n
d
e
p
e
n
d
e
n
t
t
a
s
k
t
i
m
e
<
b
r
>
E
x
a
m
p
l
e
:
3
t
a
s
k
s
o
f
1
0
s
e
c
e
a
c
h
<
b
r
>
S
e
q
u
e
n
t
i
a
l
:
1
0
+
1
0
+
1
0
=
3
0
s
e
c
<
b
r
>
P
a
r
a
l
l
e
l
(
3
p
r
o
c
e
s
s
o
r
s
)
:
1
0
s
e
c
<
b
r
>
S
p
e
e
d
u
p
=
3
0
/
1
0
=
3
x

Real-World Speedup Formula

Amdahl’s Law (concept only)

N
o
t
a
l
l
t
a
s
k
s
c
a
n
b
e
p
a
r
a
l
l
e
l
i
z
e
d
<
b
r
>
I
f
5
0
%
o
f
w
o
r
k
m
u
s
t
b
e
s
e
q
u
e
n
t
i
a
l
:
<
b
r
>
M
a
x
i
m
u
m
s
p
e
e
d
u
p
=
2
x
(
r
e
g
a
r
d
l
e
s
s
o
f
p
r
o
c
e
s
s
o
r
s
)
<
b
r
>
S
e
q
u
e
n
t
i
a
l
p
o
r
t
i
o
n
c
r
e
a
t
e
s
a
b
o
t
t
l
e
n
e
c
k
<
b
r
>
M
o
r
e
p
r
o
c
e
s
s
o
r
s
c
a
n
n
o
t
h
e
l
p
t
h
e
s
e
q
u
e
n
t
i
a
l
p
a
r
t

Scenario — Calculate the Speedup

A data processing program has 5 independent analysis tasks, each taking 20 minutes. After the analysis, there is one final summary task taking 5 minutes that requires all analysis to be complete. With one processor, what is the total time? With 5 processors, what is the total time?

Work out both cases. What limits the parallel speedup?

Answer

Sequential time: 5 tasks x 20 min + 5 min summary = 105 minutes. Parallel time (5 processors): all 5 analysis tasks run simultaneously = 20 min, then sequential summary = 5 min. Total: 25 minutes. Speedup: 105/25 = 4.2x (not 5x, because the 5-minute sequential summary cannot be parallelized). The summary task is the sequential bottleneck that limits the speedup to less than 5x.

Limits of Parallel Computing

Tasks That Parallelize Well

Independent workloads

Rendering individual frames of a video
Running weather simulations for different regions
Training machine learning models on different data splits
Searching different parts of a large database simultaneously
Processing transactions for different customers

Tasks That Resist Parallelization

Sequential dependencies

Each step of a recursive calculation that depends on the last
Sorting where each comparison informs the next
Transactions requiring a specific processing order
Any task where step N requires step N-1’s output
Reading and writing to the same variable sequentially

Scenario — Diminishing Returns

A researcher’s analysis runs in 100 minutes on 1 processor. 80 minutes of the work can be parallelized; 20 minutes cannot. She adds processors. What is the maximum speedup she can achieve regardless of how many processors she uses?

What is the theoretical maximum speedup? What limits it?

Answer

The 20 minutes of sequential work cannot be parallelized. No matter how many processors are added, those 20 minutes remain. With infinite processors, the parallel 80 minutes approaches 0 minutes. Total time approaches 20 minutes. Maximum speedup = 100/20 = 5x. She could add 1,000 processors and still not exceed 5x speedup, because the sequential 20% of work is the absolute bottleneck.

Common Exam Pitfalls

Thinking N processors always produce Nx speedup

Nx speedup is only possible when all tasks are completely independent. Any sequential dependency reduces the maximum achievable speedup. Real-world speedup is always less than theoretical maximum.

Missing that communication overhead reduces parallel efficiency

In real parallel systems, processors must coordinate: sharing data, synchronizing results, managing dependencies. This overhead means actual speedup is usually significantly less than theoretical.

Thinking parallelism always requires specialized hardware

Parallel computing can use multiple cores in a single CPU, multiple CPUs in one machine, or multiple machines in a cluster. Modern smartphones have multi-core processors that run parallel tasks.

Confusing parallel computing with distributed computing

Parallel computing focuses on speed (doing more work simultaneously). Distributed computing focuses on scale and resilience (spreading work across many machines). They overlap but are distinct concepts.

Check for Understanding

1. A program has 4 completely independent tasks each taking 8 seconds. With 4 processors, what is the total execution time?

32 seconds — same as sequential.
16 seconds — 2 processors would cut time in half.
8 seconds — all 4 tasks execute simultaneously.
2 seconds — processors can subdivide each task further.

4 independent tasks, 4 processors: all tasks execute simultaneously. Total time = duration of one task = 8 seconds. This is the ideal case: 4x speedup.

2. Task A takes 10 seconds. Task B requires Task A’s output and takes 15 seconds. Task C requires Task B’s output and takes 5 seconds. With unlimited processors, what is the minimum total execution time?

30 seconds — unlimited processors cannot help sequential dependencies.
10 seconds — only the longest task determines the time.
5 seconds — the shortest task sets the pace.
0 seconds — unlimited processors can parallelize everything.

B depends on A, and C depends on B. This is a sequential chain: A(10s) → B(15s) → C(5s) = 30 seconds regardless of processor count. Sequential dependencies cannot be parallelized.

3. Consider statements about parallel computing:
I. Parallel computing can always achieve a speedup proportional to the number of processors used.
II. Tasks with sequential dependencies cannot benefit from parallelization.
III. The sequential portion of a program limits the maximum speedup achievable through parallelization.

Which are correct?

I only
II and III only
I and II only
I, II, and III

Statement II is correct — sequential dependencies prevent parallelization. Statement III is correct — this is Amdahl’s Law. Statement I is false — N processors yield Nx speedup only when all tasks are fully independent; sequential portions, communication overhead, and synchronization all reduce actual speedup below N.

4. A program spends 60% of its time on a parallelizable section and 40% on sequential code. Adding unlimited processors, what is the maximum speedup?

Unlimited speedup because you can add as many processors as needed.
1.67x speedup because 60% of the work is eliminated and 40% remains.
2.5x speedup because the minimum time is the 40% sequential portion.
5x speedup because 5 processors would each handle 20% of the parallel work.

With unlimited processors, the 60% parallel section approaches 0 time. Total minimum time = 40% of original. Speedup = 100%/40% = 2.5x. This is Amdahl’s Law: the sequential fraction determines the speedup ceiling.

5. Which task is best suited for parallel computing?

Calculating a bank account balance after a series of deposits and withdrawals, each depending on the previous.
Rendering 1,000 individual movie frames where each frame is independent of all others.
Sorting a list using a bubble sort algorithm where each swap depends on the previous comparison.
Running a simulation where each time step depends on the previous time step’s state.

Rendering 1,000 independent frames is an embarrassingly parallel task: each frame can be rendered simultaneously without any dependency on other frames. The other options all involve sequential dependencies that prevent parallelization.

6. A researcher uses 10 processors instead of 1 and measures a 7x speedup (not 10x). The most likely explanation is:

3 of the 10 processors were defective.
Some portion of the program has sequential dependencies that cannot be parallelized, limiting speedup below 10x.
The program’s tasks take longer when run in parallel due to faster execution.
10 processors always produce exactly 10x speedup for any program.

Real speedup is always less than theoretical maximum due to: sequential dependencies (Amdahl’s Law), communication overhead between processors, synchronization delays, and load imbalance. A 7x speedup from 10 processors is actually good in practice.

Frequently Asked Questions

Does the AP CSP exam require knowing Amdahl’s Law by name?

No. You should understand the concept: the sequential portion of a program limits the maximum speedup from parallelization, regardless of how many processors are added. The AP exam presents scenarios and asks you to calculate or compare speedups — knowing the formula helps but is not required by name.

What is the difference between multicore processors and distributed computing?

Multicore processors have multiple independent processing units (cores) in a single chip, sharing memory. Distributed computing spreads work across multiple separate machines connected by a network. Both achieve parallel execution but at different scales and with different coordination overhead.

Why can’t all programs be parallelized?

Sequential dependencies are fundamental to many algorithms. Any calculation where step N requires step N-1’s result cannot be parallelized without changing the underlying algorithm. Some problems are inherently sequential by their mathematical nature.

← Fault Tolerance Encryption →

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Typically responds within 24 hours

✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

Name *

Email *

I am a... (optional)

Which course? (optional)

Phone (optional)

How did you find us? (optional)

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

Message (optional — leave blank if just subscribing)

✉

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]

AP CSP Big Idea 4 Parallel Computing

AP CSP Parallel vs. Sequential Computing: Complete Guide (2025‑2026)

Contents

Sequential vs. Parallel

Calculating Speedup

Limits of Parallel Computing

Common Exam Pitfalls

Check for Understanding

Frequently Asked Questions

Get in Touch

Message Sent!