4.3 Parallel and Distributed Computing

TLDR

Parallel and distributed computing are ways to make programs faster by splitting work across multiple processors or multiple devices instead of running everything one step at a time. For the AP Computer Science Principles exam, you need to compare sequential, parallel, and distributed solutions, calculate execution time and speedup, and explain why adding more parallel power eventually stops helping.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science Principles Exam

This topic shows up in the multiple-choice section, where you read scenarios and diagrams and decide which solution is faster or more efficient. You should be ready to:

• Compare sequential, parallel, and distributed solutions for the same task.
• Calculate execution time for sequential and parallel solutions.
• Calculate the speedup of a parallel solution.
• Explain the benefits and limits of parallel and distributed computing.

The big skill here is evaluating solution options, so most questions ask you to judge or compare approaches rather than write code.

Key Takeaways

• Sequential computing runs operations one at a time, in order. Its total time is the sum of all steps.
• Parallel computing breaks a program into smaller sequential pieces and runs some of them at the same time on multiple processors.
• A parallel solution takes as long as its sequential tasks plus the longest of its parallel tasks.
• Speedup equals sequential time divided by parallel time.
• Distributed computing uses multiple devices to run one program, which lets you solve problems too big for a single computer.
• Parallel solutions scale better than sequential ones, but the sequential portion sets a limit, so adding more processors eventually stops helping much.

Three Computing Models

Programs were traditionally built with sequential computing in mind, where instructions are processed one at a time, in order. As demand grew for faster computers, sequential processing could not keep up, partly because a single processor can only run so fast before heat becomes a real problem. That pressure led to parallel and distributed computing.

Sequential Computing

Sequential computing is a model where operations are performed in order, one at a time. Nothing overlaps. The total time is simply the sum of every step.

Parallel Computing

Parallel computing breaks a program into smaller sequential operations, and some of those operations run at the same time using multiple processors. Most modern computers use parallel systems, often with several cores running at once.

Why parallel computing helps:

• Running tasks at the same time can save a lot of time.
• Parallel solutions scale better than sequential ones. If the workload grows, a parallel solution handles the increase better than a sequential model would.

One important detail: a parallel solution always has a parallel portion and a sequential portion. Some steps must happen in order, and those sequential steps limit how fast the whole solution can get.

Distributed Computing

Distributed computing uses multiple devices to run a program. Those devices can sit in different locations and communicate by sending messages to each other.

The payoff is power. With more than one computer working on the same problem, you can solve problems that a single computer could not handle because of limited storage or too much processing time. Distributed computing also lets much larger problems get solved faster than one computer could manage alone.

Examples of distributed computing in real life include search engines and applications that store your data separately from your own device. Treat these as applications of the concept, not required AP terms.

Execution Time, Efficiency, and Speedup

The exam mixes conceptual questions with calculation questions. You may be asked to calculate the execution time of a sequential or parallel solution, compare the efficiency of two solutions, or calculate the speedup of a parallel solution. Comparing efficiency usually means comparing how long two solutions take to do the same task.

Sequential Execution Time

A sequential solution takes as long as the sum of all its steps. If a program has three steps that take 40, 50, and 80 seconds, the sequential time is:

</>Code
40 + 50 + 80 = 170 seconds

Parallel Execution Time

A parallel solution takes as long as its sequential tasks plus the longest of its parallel tasks. The number of processors affects how fast the solution can run.

Using the same three steps of 40, 50, and 80 seconds with two processors, the fastest possible time is 90 seconds. Here is the reasoning.

First, assume all steps are independent, meaning no step needs the result of another to begin. The question will tell you whether steps are independent, so check before you calculate. If steps are independent, processors can run them in any order or combination.

To find the minimum time, load the work so the busiest processor finishes as early as possible:

• Processor 2 runs the 80-second step.
• Processor 1 runs the 40-second step, then the 50-second step in order, which totals 90 seconds.

Even though Processor 2 finishes in 80 seconds, the whole solution is not done until Processor 1 finishes at 90 seconds. The solution time is set by whichever processor takes longest.

The deciding factor is not always one long task. If Processor 2 had a single 100-second step, the solution would take 100 seconds, because that one long parallel task would now be the longest path.

Calculating Speedup

The speedup of a parallel solution equals the time it took sequentially divided by the time it took in parallel.

</>Code
speedup = sequential time / parallel time

For the example above:

</>Code
speedup = 170 / 90 = about 1.88

Why More Processors Eventually Stop Helping

A parallel solution can only go as fast as its sequential portions allow. Some steps must run in order, such as a step that needs data from an earlier step before it can start.

Here is a non-programming way to picture it. Imagine a group making a slideshow. One student turns in the final file. That student has to wait until everyone else finishes, so turning it in cannot run in parallel with building the slides. It is not an independent step.

As you add more parallel processors, the speedup gains shrink. Eventually you hit something parallelism cannot speed up: either the sequential steps or extra overhead like communication time between processors. That is why adding parallel power past a certain point no longer meaningfully improves efficiency.

How to Use This on the AP Computer Science Principles Exam

Problem Solving

When you get a timing question, work through it in steps:

1. Identify whether the steps are independent. Do not assume. The question should state this.
2. For sequential time, add every step.
3. For parallel time, assign steps so the most loaded processor finishes as early as possible, then take the longest processor's total.
4. For speedup, divide sequential time by parallel time.

Drawing a quick timeline for each processor helps you avoid mistakes.

Worked Example

Here is a two-processor problem. The processes are 60, 30, and 50 seconds, none depend on each other, and each processor runs one process at a time. What is the minimum time?

Walk through it:

1. You want the minimum, so start the longest jobs first. Processor A starts the 60-second process and Processor B starts the 50-second process.
2. Processor B finishes the 50-second process and starts the 30-second process while Processor A keeps running the 60-second process.
3. Processor A finishes the 60-second process at 60 seconds total. Processor B is 10 seconds into the 30-second process.
4. Processor B finishes 20 seconds later.

Total time: 60 + 20 = 80 seconds.

Another way to see it: one processor has to run both the 50-second and 30-second processes in series, which adds to 80 seconds. The 60-second step runs in parallel during that time, so it does not extend the total.

Common Misconceptions

• Parallel time is not the sum of all steps. Sequential time is the sum. Parallel time is the sequential tasks plus the longest parallel task, set by the busiest processor.
• More processors do not give unlimited speed. The sequential portion and overhead set a ceiling, so gains shrink as you keep adding processors.
• Speedup is sequential divided by parallel, not the other way around. A speedup above 1 means the parallel version is faster.
• Steps are not always independent. If a step needs data from an earlier step, it cannot run in parallel with that step. Always check what the question says.
• Parallel and distributed are not the same thing. Parallel uses multiple processors, often in one machine. Distributed uses multiple separate devices working together.
• Distributed computing is about more than speed. It also lets you solve problems that a single computer cannot handle because of storage or processing limits.

Related AP Computer Science Principles Guides

• 4.1 The Internet
• 4.2 Fault Tolerance
• Big Idea 4 Overview: Computer Systems and Networks