Time Estimate: 45 minutes5.9.1. Introduction and Goals¶Parallel ComputingFor hard problems that take a long time to solve, we can sometimes speed up the algorithm by using multiple processors or computers. We can split the workload and compute the parts of the solution in parallel.
Learning Objectives: I will learn to Show
Language Objectives: I will be able to
5.9.2. Learning Activities¶
Searching POGIL ActivityEach group of four should be given a deck of cards (or use PlayingCards.io) Have one team member time the following tasks:
We can compare the efficiency of sequential vs. parallel solutions 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. In the card activity, in the worst case, you would need to look through 52 cards with the sequential algorithm to find a particular card. A parallel computing solution takes as long as its sequential tasks (for example, splitting up the deck of cards into 4 stacks) plus the longest of its parallel tasks (for example, finding the card in parallel). In the parallel algorithm card activity, the 52 cards were divided into 4 stacks, and the 4 team members each looked through around 13 cards in the worst case to find the card in parallel. The speedup of a parallel solution is measured in the time it took to complete the task sequentially divided by the time it took to complete the task when done in parallel. The speedup for the card activity could be close to four times as fast with the parallel algorithm. Benefits and Challenges in Parallel ComputingSolutions that use parallel computing can scale up which means that they can get faster as we add more processors. However, there is a limit to this speed up. Parallel computing consists of a parallel portion and a sequential portion. The sequential portion is usually before and after the parallel part to divide the workload and combine the results. The time taken is the sum of the time taken in the sequential and parallel parts. This means the efficiency of the solution is limited by the sequential portion, at some point, adding parallel portions will no longer meaningfully increase efficiency.Sorting POGIL ActivityEach group of four should be given a deck of cards. Have one team member time the following tasks.
Distributed ComputingIn Distributed Computing, multiple networked computers are used to solve a problem. Distributed computing allows problems to be solved that could not be solved on a single computer because of the required long processing time or large storage needs. And it allows much larger problems to be solved quicker than they could be solved using a single computer. Watch the following video for distributed computing in practice at Folding@Home where you can donate distributed computer time to solve real world problems. They also have a new initiative to help with COVID-19 research. 5.9.3. Summary¶In this lesson, you learned how to: 5.9.4. Self-Check¶ Here is a table of some of the technical terms discussed in this lesson. Hover over the terms to review the definitions.
Q-2: AP 2021 Sample Question: A certain computer has two identical processors that are able to run in parallel. Each processor can run only one process at a time, and each process must be executed on a single processor. The following table indicates the amount of time it takes to execute each of three processes on a single processor. Assume that none of the processes are dependent on any of the other processes.
Which of the following best approximates the minimum possible time to execute all three processes when the two processors are run in parallel?
Q-3: Consider an algorithm to solve a problem that takes 160 seconds to run on 1 processor. This algorithm can be divided among two processors to solve the same problem in 100 seconds. What is the speedup for this parallel algorithm? 5.9.5. Reflection: For Your Portfolio¶Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File/Make a Copy to make your own editable copy. Which of the following best describes the ability of parallel computing solutions?Which of the following best describes the ability of parallel computing solutions to improve efficiency? The efficiency of a solution that can be broken down into parallel portions is still limited by a sequential portion.
Which of the following best explains the ability to solve problems algorithmically?Which of the following best explains the ability to solve problems algorithmically? Any problem can be solved algorithmically, though some algorithmic solutions may require humans to validate the results.
Which of the following parallel computing solutions would minimize the amount of time it takes to execute all four processes quizlet?Which of the following parallel computing solutions would minimize the amount of time it takes to execute all four processes? why? With two processors running in parallel, execution time is minimized when the processors take on as close to an equal workload as possible.
Which of the following is a true statement about the use of public key encryption in transmitting messages?Which of the following is a true statement about the use of public key encryption in transmitting messages? Public key encryption enables parties to initiate secure communication through an open medium, such as the Internet, in which there might be eavesdroppers.
|