Computing Models (College Board AP® Computer Science Principles): Study Guide
Sequential, parallel, and distributed computing
What are the three computing models?
Sequential computing is a computational model in which operations are performed in order one at a time
Parallel computing is a computational model where the program is broken into multiple smaller sequential computing operations, some of which are performed simultaneously
Distributed computing is a computational model in which multiple devices are used to run a program
Model | How it works | Example |
|---|---|---|
Sequential | Operations run one at a time in order | A single processor completing steps A, B, then C |
Parallel | A program is split into smaller operations, some running simultaneously on multiple processors | Two processors each handling half of a dataset at the same time |
Distributed | Multiple devices work together to run a program | Computers across a network each processing a portion of a large task |
Performance metrics
How is the efficiency of computing solutions compared?
Comparing the efficiency of solutions can be done by comparing the time it takes them to perform the same task
A sequential solution takes as long as the sum of all of its steps
A parallel computing solution takes as long as its sequential tasks plus the longest of its parallel tasks
Calculating solution time
A program has four tasks: A (2 seconds), B (4 seconds), C (3 seconds), and D (1 second)
Sequential time:
All tasks run one after another: 2 + 4 + 3 + 1 = 10 seconds
Parallel time (two processors):
Tasks A and B run on processor 1. Tasks C and D run on processor 2
Processor 1 | Processor 2 |
|---|---|
A (2s) + B (4s) = 6s | C (3s) + D (1s) = 4s |
The parallel portion takes as long as the longest processor: 6 seconds
Task completion analysis
What is speedup?
The speedup of a parallel solution is measured as the time it took to complete the task sequentially divided by the time it took to complete the task when done in parallel
Using the example above: speedup = 10 / 6 = 1.67
A speedup of 1.67 means the parallel solution completed the task 1.67 times faster than the sequential solution
A speedup of 1 would mean no improvement over the sequential approach
Examiner Tips and Tricks
The AP exam frequently asks you to calculate solution times and speedup. For sequential time, add all the steps. For parallel time, identify which tasks run on which processor, then take the longest processor time.
A common mistake is forgetting that parallel time equals sequential tasks plus the longest parallel group, not the shortest. When calculating speedup, always divide sequential time by parallel time.
Worked Example
A program consists of three tasks. Task X takes 5 seconds, Task Y takes 3 seconds, and Task Z takes 4 seconds. When run in parallel, Task X runs alone on one processor while Tasks Y and Z run together on a second processor.
What is the speedup of the parallel solution compared to the sequential solution?
(A) 1.5
(B) 1.71
(C) 2.0
(D) 3.0
[1]
Answer:
(B) 1.71 [1 mark]
Sequential time = 5 + 3 + 4 = 12 seconds. Processor 1 takes 5 seconds and Processor 2 takes 3 + 4 = 7 seconds, so the parallel time is 7 seconds and the speedup is 12 / 7 = 1.71.
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
