Welcome to Parallel and Distributed Computing!
In this chapter, we are going to look at how computers work together to solve big problems faster. Usually, we think of a computer doing one thing at a time, but in the real world, we often need to process massive amounts of data—like predicting the weather or rendering a 3D movie. To do this, we use Parallel and Distributed computing. Don't worry if these terms sound a bit "techy" at first; we will break them down using simple analogies!
1. Three Ways to Solve a Problem
In AP Computer Science Principles, you need to know the difference between three specific computing models: Sequential, Parallel, and Distributed.
Sequential Computing
Sequential computing is the "traditional" way of processing. Tasks are done one at a time, in order. The computer finishes one task before starting the next.
Analogy: Imagine you are at a grocery store with only one checkout lane open. Even if there are 10 people in line, the cashier can only help one person at a time. The total time it takes is the sum of every person's checkout time.
Key Fact: The time it takes for a sequential program to run is the sum of the time it takes for each individual step.
Parallel Computing
Parallel computing is when a program is broken into smaller parts, and some of those parts are performed at the same time. This usually happens on one computer that has multiple processors (or "cores").
Analogy: Now imagine the grocery store opens four checkout lanes. Four customers can be helped at once! The line moves much faster because work is happening simultaneously.
Key Fact: Parallel computing consists of a sequential portion and a parallel portion.
Distributed Computing
Distributed computing is a model where multiple different computers (a "system" of computers) work together on a single task. These computers are connected via a network (like the Internet).
Analogy: Imagine if the grocery store was so busy that they sent some customers to a completely different branch of the store down the street to be checked out there, and then reported the totals back to the main office.
Key Fact: Distributed computing allows you to solve problems that are too big for a single computer to handle by using the power of many machines.
Quick Review:
- Sequential: One after another.
- Parallel: Same time, one computer (multiple processors).
- Distributed: Same time, multiple computers (networked).
2. Measuring Success: Speedup
The whole point of parallel computing is to save time. We measure how much time we saved using a concept called Speedup.
To find the speedup, you use this formula:
\( \text{Speedup} = \frac{\text{Sequential Time}}{\text{Parallel Time}} \)
Example Calculation:
If a program takes \( 60 \) seconds to run sequentially and only \( 20 \) seconds to run in parallel, what is the speedup?
\( \text{Speedup} = \frac{60}{20} = 3 \)
The program is \( 3 \) times faster!
Important Note: If the speedup is \( 1 \), it means the parallel version didn't save any time at all. If the speedup is less than \( 1 \), the parallel version was actually slower (which can happen if it takes too much work to coordinate the tasks!).
3. The Benefits and Limits of Parallelism
It might seem like adding more processors will always make a program faster and faster. However, there are limits to what parallel computing can do.
The Benefits
- Scalability: Distributed systems can scale up to handle massive amounts of data by just adding more computers.
- Time Efficiency: Most problems can be solved much faster than they could be sequentially.
The Limits (Why isn't it perfectly fast?)
Even with \( 1,000 \) processors, a program will never be "instant." This is because:
1. Sequential Dependencies: Some parts of a program simply must be done in order. You can't put on your shoes until you've put on your socks. No matter how many people help you, the "socks first" part is sequential.
2. Communication Overhead: In distributed computing, the computers have to talk to each other over a network. Sending data back and forth takes time. If the "talking" takes longer than the "working," the system becomes inefficient.
Did you know?
The limit to how much faster a program can get is determined by the portion of the program that must remain sequential. If \( 10\% \) of your program is sequential, no matter how many processors you add, you can never make that \( 10\% \) run any faster.
4. Comparing Models: A Quick Summary Table
Sequential
- Method: One task at a time.
- Hardware: One processor.
- Efficiency: Slowest for large tasks.
Parallel
- Method: Multiple tasks at once.
- Hardware: Multiple processors in one computer.
- Efficiency: Faster, but limited by the number of processors and sequential parts.
Distributed
- Method: Multiple tasks on multiple computers.
- Hardware: Multiple computers connected by a network.
- Efficiency: Highly scalable; can handle the largest data sets.
5. Common Mistakes to Avoid
- Mistake: Thinking distributed computing doesn't use parallel computing.
Correction: Actually, distributed computing is a form of parallel computing because multiple things happen at once, but it uses multiple computers instead of just multiple processors in one box.
- Mistake: Thinking Speedup is calculated as \( \text{Parallel} / \text{Sequential} \).
Correction: It is always \( \text{Sequential} / \text{Parallel} \). Think of it this way: the bigger number (slow time) usually goes on top so that the "Speedup" is a number greater than \( 1 \).
Key Takeaway for the Exam:
When you see a question about Parallel Computing, look for the Sequential part. The total time for a parallel solution is the time of the sequential portion plus the time of the longest parallel task. You can't ignore the parts that have to happen one-by-one!