Getting Started
As computational problems become larger and more complex, from simulating global climate change to analyzing massive datasets, a single computer working step-by-step is often too slow. To solve these grand challenges, we need ways to divide the work and process it simultaneously. This chapter explores how we can move beyond one-at-a-time processing to harness the power of many processors working together.
What You Should Be Able to Do
Explain the difference between sequential, parallel, and distributed computing models.
Compare the benefits and drawbacks of using a parallel or distributed approach to solve a problem.
Determine the potential "speedup" of a parallel solution compared to a sequential one.
Describe how distributed computing systems are used to solve large-scale problems.
Key Concepts & Application
The Core Idea
An algorithm is a finite set of instructions that accomplishes a specific task. Traditionally, a computer executes an algorithm's instructions one at a time, in order—a method called sequential computing. Imagine washing a large pile of dishes by yourself: you wash one, dry it, and put it away before starting the next. This is efficient for a small number of dishes, but slow for a banquet.
To speed things up, you could use parallel computing. You might wash the dishes while a friend dries them. You are both working at the same time on the same pile of dishes, using two "processors" (you and your friend) to complete the overall task faster. This works well, but you both need to be in the same kitchen.
For an enormous task, like catering a city-wide festival, you might use distributed computing. You could give a crate of dishes to ten different friends and have them wash them in their own homes. Each person works on their own portion of the task on their own equipment. This approach is highly scalable but requires coordination to collect all the clean dishes afterward.
Computing Models & Performance
These three approaches—sequential, parallel, and distributed—represent different models for executing a program. The choice of model depends on the problem, the available resources, and the desired performance.
| Feature | Sequential Computing | Parallel Computing | Distributed Computing |
|---|---|---|---|
| Execution | One instruction at a time. | Multiple instructions at the same time on one machine. | Program runs across multiple, separate machines. |
| Hardware | A single processor or core. | A multi-core processor or multiple processors in one computer. | Multiple, independent computers connected by a network. |
| Best For | Simple, linear tasks that cannot be broken down. | Complex problems that can be divided into smaller, independent sub-tasks. | Massive-scale problems that require more resources than a single machine can provide. |
| Example | Calculating a running total in a list, one item at a time. | Rendering a single frame of a 3D animation by assigning different pixels to different cores. | Scientific research projects like Folding@home, where millions of home PCs contribute processing power. |
A program is suitable for parallel computing only if it can be broken into parts that can be solved at the same time. If every step depends on the one before it, a parallel approach will not provide a speed advantage.
Tracing & Analysis
The primary benefit of parallel computing is a reduction in processing time. We measure this improvement using a metric called speedup.
Speedup is defined as the time it takes to complete a task sequentially divided by the time it takes to complete the same task in parallel.
Speedup = (Sequential Execution Time) / (Parallel Execution Time)
Scenario Trace:
Imagine an algorithm that processes a large image.
Sequential Time: A single processor takes 120 seconds to process the entire image.
Parallel Time: The image is split into 4 equal parts, and 4 processor cores work on one part each. Due to the need to split the image and combine the results, the total time is 40 seconds.
Calculating Speedup:
Speedup = 120 seconds / 40 seconds
Speedup = 3
In this case, the parallel solution provides a speedup of 3, meaning it is 3 times faster than the sequential solution.
It is important to note that the speedup is not always equal to the number of processors used. This is because a parallel system introduces new work, such as the overhead of coordinating between processors and combining their results. Some parts of an algorithm may also be inherently sequential and cannot be sped up, limiting the overall performance gain.
A distributed computing system offers additional benefits beyond speed, such as improved reliability. Since the system uses many machines, it can be fault-tolerant—if one computer fails, the others can continue working.
Core Concepts & Terminology
Algorithm: A finite set of instructions that accomplishes a specific task. All computing, whether sequential or parallel, is based on algorithms.
Sequential Computing: A computational model in which operations are performed in order, one at a time. This is the traditional, step-by-step method of execution.
Parallel Computing: A computational model where a program is broken into smaller pieces, some of which are run simultaneously on multiple processors in a single computer.
Distributed Computing: A computational model in which multiple devices are used to run a program. These devices are separate computers connected by a network.
Speedup: A measure of how much faster a parallel solution is than a corresponding sequential solution. It is calculated as the sequential time divided by the parallel time.
Sequential Loop (Example Logic): A common structure in sequential computing where a list is processed one item at a time.
numbers <- [10, 20, 30, 40] sum <- 0 FOR EACH num IN numbers { sum <- sum + num // This operation happens one by one } DISPLAY(sum)This pseudocode demonstrates a task that must process each item in order to arrive at the final
sum.
Core Skill Check
Logic Tracing: A sequential algorithm takes 2 hours to run. A parallel version on the same dataset takes 30 minutes. What is the speedup?
Debugging: A programmer splits a task among 8 processors but only achieves a speedup of 2. What is a likely reason for the limited performance gain?
Application: Describe a real-world example of a distributed computing system and explain why that model is appropriate for the task.
Common Misconceptions & Clarifications
"Parallel computing makes every program faster."
- Clarification: A program only benefits from parallel computing if its tasks can be performed independently. If every step depends on the result of the previous one, it cannot be parallelized.
"Using twice the processors will make the program twice as fast."
- Clarification: The speedup is rarely perfect. The overhead required to manage the parallel processes (like splitting the data and combining the results) consumes time and limits the maximum speedup.
"Parallel and distributed computing are the same."
- Clarification: Parallel computing typically involves multiple processors within a single machine. Distributed computing involves multiple, separate machines connected by a network.
"A speedup of 4 means you used 4 processors."
- Clarification: Speedup is a ratio of times, not a count of processors. While using 4 processors might ideally lead to a speedup of 4, it is not a direct equivalence due to overhead.
Summary
As the scale of data and the complexity of problems grow, sequential computing is often insufficient. Parallel computing allows us to solve problems faster by executing multiple operations at the same time on a single machine, with its effectiveness measured by speedup. For even larger tasks, distributed computing harnesses the power of many separate computers working together over a network. This not only provides massive computational power but also increases reliability. Understanding these different computing models is essential for developing solutions to the most challenging problems in science, business, and art.