When you run a program like a web browser, email client, or video game, that program normally runs on a single computer. The CPU in one computer is more than enough to handle the needs of these applications. However, some advanced programs may require more than one computer or more than one processor to run efficiently.
We can use the concepts of parallel computing and distributed computing to handle more advanced, CPU-intensive tasks. Parallel computing uses a single computer with multiple processors to process different tasks at the same time. Distributed computing uses the resources from multiple computers to process small parts of a larger task.
Parallel Computing
To understand how parallel computing works, we first need to define sequential computing. Sequential computing is a model where the different operations in a program are performed one at a time, in a specific order. Picture yourself getting ready for school in the morning. You get out of bed, get dressed, get breakfast and go off to school. Each of these tasks are performed one at a time, in a specific order. After all, you wouldn't get dressed before you get out of bed!
Now let's say that the "get breakfast" task actually includes three smaller tasks: feeding yourself, feeding your cat, and feeding your dog. Each of these tasks is separate and can be completed in any order or even at the same time. However, to do more than one task at a time, you need help! Perhaps you can get your brothers and sisters to feed the cat and the dog while you eat your own breakfast. Each task is separate, but they can all be successfully performed at the same time. This is an example of parallel processing.
Computer programs often have tasks that can be similarly completed in any order or at any time. Since each task runs on a CPU, you just need multiple CPUs to do more than one thing simultaneously. To take advantage of parallel processing on a computer, you must be able to break a larger task down into smaller jobs that can be assigned to different CPUs. If your computer has multiple CPUs, then these tasks can be executed at the same time, and the overall amount of time it takes to complete the program is reduced.
Weather Map broken into a gridFor example, the task of generating weather forecasts is very complex. Computational models use a high volume of data from many locations and need to generate predictions for many areas. An overall weather map can be created by dividing an area into a grid and then handling the calculations for each grid with a different CPU. The calculations for each grid, which are done in parallel, can be quickly combined to form a final weather map.
Executing a task with a small number of sequential steps may not take very much time. However, the advantages to parallel processing become obvious as you scale up the size of the problem. What happens if the number of sequential steps increases by a factor of 10, 100, or 1000? If you process each step in sequence, your overall runtime will increase by that same factor of 10, 100, or 1000. That may be far to long to reasonably wait for an answer!
However, if you can execute many of those tasks in parallel, the overall runtime will not increase nearly as much. Parallel processing can give you an answer in a reasonable time, even for very large problems. Naturally, the cost of providing the extra CPUs needed to run tasks in parallel may limit your ability to scale up to larger problems.
Distributed Computing
Parallel computing is a powerful concept, but sometimes a computer program needs more processing time or data storage than one computer can provide. How many processors can one computer have? A typical computer has anywhere from 1 to 12 (or more) processors. However, there is a point at which you simply cannot fit any more processors on the computer's hardware. Some computing tasks may need hundreds or thousands of CPUs to produce an answer in a reasonable time-frame.
In this case, distributed computing may be a better choice. Distributed computing uses the power of many computers to run the pieces of a single program. Each distributed computer will send results back to a central location. Distributed computing allows complex programs to run faster than they could on a single computer, even if that computer has multiple CPUs.
Distributed computing is more common than you may believe. Consider a video game that runs on a low-power smartphone or in your web browser. 3D graphical scenes can require intensive calculations to render, but fortunately, it is usually possible to render different parts of the scene independently. That means you can distribute the graphical responsibilities for small sections of the screen to many other computers. When those computers are all finished, the final scene is rendered by combining the smaller sections.
Distributed rendering of an image
You can find many other examples of distributed computing projects, where a complex task can be usefully broken down into many pieces. Here are a few topics where distributing computing has been applied.
Find new prime numbers and other special mathematical values
Attempt to crack encryption keys
Scan radio frequencies for intelligent signals
Run simulations of physical models of the universe
Analyze biological models, proteins, and new drugs
...and much more!
Parallel and Distributed Efficiency
How much time can you save with parallel or distributed computing? A purely sequential solution will take as long as the sum of all of its steps, executed in order, one at a time. In our morning routine example, let's say each task takes the following amount of time:
5 minutes to get out of bed
10 minutes to get dressed
10 minutes to get breakfast for yourself
5 minutes to feed your cat
5 minutes to feed your dog
10 minutes to get to school
That's a total sequential time of 45 minutes.
Now, how long will it take if we can accomplish the 3 feeding tasks in parallel?
5 minutes to get out of bed
10 minutes to get dressed
10 minutes to get breakfast for yourself, feed your cat, and feed your dog
10 minutes to get to school
Our total time is now 35 minutes, so we have saved 10 minutes! Notice that the three tasks done in parallel normally take 10, 5, and 5 minutes each. The overall time it takes to finish all 3 tasks is equal to the longest parallel task (10 minutes to feed yourself). The other two tasks are shorter and will be completed while you are eating breakfast.
The efficiency of a parallel solution is called the "speedup" value. This value is equal to the time it took to complete the program sequentially divided by the time it took to complete the program when done in parallel. Our morning routine speedup value is 45 / 35 or about 1.29.
You will get a higher speedup value if your program can accomplish more tasks in parallel. For example, if a computer rendering program would normally take 1 millisecond to render a complete image sequence, but takes only .02 milliseconds to render the image by distributing the task to many CPUs, the speedup value is 50. This means your parallel or distributed solution is 50 times faster than a sequential program on one CPU!
Most programs will have a mix of tasks that must be completed in sequence and that can be completed in parallel. Your speedup or increased efficiency will be limited by the tasks that need to happen in sequence. Even if you theoretically distributed all tasks that can be run in parallel, the sequential tasks must still be done in order on one CPU, and that sequential time will help form a lower limit on the overall processing time.
1. How are tasks normally executed in sequential computing?
2. What kind of tasks can be executed in parallel?
3. What kind of hardware do you need on a computer to run tasks in parallel?
4. How can distributed computing remove some limitations of parallel processing on one computer?
5. What are some examples of applications that can use distributed computing?
6. If you put several tasks in parallel, how would you determine the total time it takes to finish all tasks?
7. What is a speedup value and how is it calculated?
8. How can you get a higher speedup value?
9. How do sequential tasks limit the speedup you can realize by parallel processing?
1. Tasks in sequential computing are executed one at a time, in a specific order.
2. Tasks that can be executed in parallel are those that can be completed in any order or even at the same time, without any dependencies.
3. To run tasks in parallel, you need a computer with multiple processors or CPUs.
4. Distributed computing allows for the use of multiple computers, which can provide more processing power and data storage than a single computer.
5. Examples of applications that can use distributed computing include finding prime numbers, cracking encryption keys, analyzing biological models, and running simulations of physical models.
6. The total time it takes to finish all tasks in parallel would be equal to the time it takes to complete the longest parallel task.
7. A speedup value is the efficiency of a parallel solution and is calculated by dividing the time it took to complete the program sequentially by the time it took to complete the program in parallel.
8. A higher speedup value can be achieved by having more tasks that can be executed in parallel.
9. Sequential tasks limit the speedup that can be realized by parallel processing because they must still be done in order on one CPU, and the sequential time forms a lower limit on the overall processing time.
1. Tasks are executed one at a time in sequential computing. Each operation is performed in a specific order, with the next operation starting only after the previous one has completed.
2. Tasks that are independent of each other and do not rely on the completion of another task can be executed in parallel. These tasks can be performed simultaneously by multiple processors or cores, reducing the overall execution time.
3. To run tasks in parallel, you need a computer with multiple processors or cores. Each processor or core can handle a separate task simultaneously. The number of processors or cores in a computer determines the degree of parallelism that can be achieved.
4. Distributed computing can remove some limitations of parallel processing on one computer by utilizing the power of multiple computers. Instead of relying on a single computer with limited processors or cores, distributed computing distributes the workload across multiple computers. This allows for greater scalability and the ability to handle more complex tasks that require a larger number of processors or cores.
5. Some examples of applications that can use distributed computing include:
- Finding new prime numbers and other mathematical values
- Attempting to crack encryption keys
- Scanning radio frequencies for intelligent signals
- Running simulations of physical models of the universe
- Analyzing biological models, proteins, and new drugs
6. To determine the total time it takes to finish all tasks executed in parallel, you would typically consider the time taken by the longest task. This is because the other tasks can overlap or be completed while waiting for the longest task to finish. The overall time would be equal to or slightly longer than the time taken by the longest task.
7. The speedup value is a measure of efficiency in parallel computing. It represents the ratio of the time it takes to complete a program sequentially to the time it takes to complete the same program in parallel. It is calculated by dividing the sequential time by the parallel time.
8. A higher speedup value can be achieved by increasing the degree of parallelism, which means executing more tasks in parallel. This can be accomplished by increasing the number of processors or cores, using more powerful hardware, or optimizing the program to enable more parallel execution.
9. Sequential tasks can limit the speedup that can be achieved through parallel processing. Even if many tasks can be executed in parallel, if there are sequential tasks that need to be performed in order, the overall processing time will be limited by the sequential tasks. This means that the speedup may not be proportional to the number of tasks executed in parallel, as the sequential tasks will still need to be completed one after another.
1. In sequential computing, tasks are executed one at a time, in a specific order. Each task is performed after the previous task is completed.
2. Tasks that can be executed in parallel are those that are separate and independent of each other. These tasks can be completed simultaneously or in any order.
3. To run tasks in parallel, you need a computer with multiple processors or CPUs. Each CPU can handle a separate task simultaneously.
4. Distributed computing can remove the limitations of parallel processing on one computer by using the power of multiple computers. In distributed computing, different parts of a single program are run on different computers, and the results are sent back to a central location. This allows complex programs to run faster than they could on a single computer.
5. Some examples of applications that can use distributed computing are finding new prime numbers, cracking encryption keys, scanning radio frequencies for intelligent signals, running simulations of physical models, and analyzing biological models, proteins, and new drugs.
6. To determine the total time it takes to finish all tasks in parallel, you need to consider the time taken by the longest parallel task. This is because the other tasks can be completed while the longest task is being executed.
7. The speedup value is a measure of efficiency in parallel processing. It is calculated by dividing the time it took to complete the program sequentially by the time it took to complete the program when done in parallel. A higher speedup value indicates a more efficient parallel solution.
8. You can get a higher speedup value by parallelizing more tasks. The more tasks that can be executed in parallel, the higher the potential speedup value.
9. Sequential tasks limit the speedup that can be realized by parallel processing because these tasks must still be done in order and on one CPU. The time taken by sequential tasks forms a lower limit on the overall processing time. If there are many sequential tasks or if the sequential tasks take a significant amount of time, the speedup value will be limited.