Section 2.9

Sequential, Parallel & Distributed Computing

Learning Goals

CSN-2.A: For sequential, parallel, and distributed computing:
- - a. Students will compare problem solutions
  - b. Students will determine the efficiency of solutions
CSN-2.B: Students will describe benefits and challenges of parallel and distributed computing.
IOC-1.E: Students will explain how people participate in problem-solving processes at scale.
Students will define sequential computing, parallel computing, and distributed computing.
Students will compare the efficiency of sequential, parallel and distributed solutions.
Students will calculate the speedup of a parallel solution.
CSN-2.A.1: Sequential computing is a computational model in which operations are performed in order one at a time.
CSN-2.A.2: Parallel computing is a computational model where the program is broken into multiple smaller sequential computing operations, some of which are performed simultaneously.
CSN-2.A.3: Distributed computing is a computational model in which multiple devices are used to run a program.
CSN-2.A.4: Comparing the efficiency of solutions can be done by comparing the time it takes them to perform the same task.
CSN-2.A.5: A sequential solution takes as long as the sum of all of its steps.
CSN-2.A.6: A parallel computing solution takes as long as its sequential tasks plus the longest of its parallel tasks.
CSN-2.A.7: 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.
CSN-2.B.1: Parallel computing consists of a parallel portion and a sequential portion.
CSN-2.B.2: Solutions that use parallel computing can scale more effectively than solutions that use sequential computing.
CSN-2.B.3: Distributed computing allows problems to be solved that could not be solved on a single computer because of either the processing time or storage needs involved.
CSN-2.B.4: Distributed computing allows much larger problems to be solved quicker than they could be solved using a single computer.
CSN-2.B.5: When increasing the use of parallel computing in a solution, the efficiency of the solution is still limited by the sequential portion. This means that at some point, adding parallel portions will no longer meaningfully increase efficiency.
CSN-2.B.4: Distributed computing allows much larger problems to be solved quicker than they could be solved using a single computer.
CSN-2.B.5: When increasing the use of parallel computing in a solution, the efficiency of the solution is still limited by the sequential portion. This means that at some point, adding parallel portions will no longer meaningfully increase efficiency.

Objectives and General Description

Parallel and distributed computing leverage multiple computers to more quickly solve complex problems or process large data sets. (CSN -2)

In this lesson, students will participate in a small group activity to illustrate the efficiency of solving problems with large sets of data. This activity will be used to illustrate the differences between sequential, parallel and distributed computing. Then the students will learn how to calculate the speed up of a parallel solution. Finally, students will be asked to develop scenarios in which the types of computing would be most efficient.

Key vocabulary: Sequential computing, Parallel Computing, Distributed Computing, speed up, Fault tolerant, redundant, scalable, Citizen Science

Activities

Activity 2.9.1 Introduction to Parallel Computing (Budget 30-45 minutes)

Write a list of tasks on the board or display for students. Examples: Clean cafeteria tables, sweep the halls, take down old posters in the school, pick up trash in the bleachers, etc. Ask students to give you an estimate of how much time it would take an individual student to complete all tasks. Then ask how the process could be sped up. Students will generally quickly say that they need more people to help. Divide students into groups. Give each group a designated number of "workers" and they must quickly decided to how to manage their workers to most efficiently get the tasks completed. Assign a variety of worker amounts (50, 100, 1000, 10000, etc.). Make sure that one of your groups has an extremely large number.

Discussion questions:

Ask each group to summarize how they would use their workers and manage the tasks.
Does more workers always translate into faster progress?

Explain that we have choices about how to best allocate our computers' processing power. Introduce the vocabulary terms:

Sequential Computing: A computational model in which operations are performed in order one at a time.
Parallel Computing: A computational model where the program is broken into multiple smaller sequential computing operations, some of which are performed simultaneously.
Distributed Computing: A computational model in which multiple devices are used to run a program.

Have students compare the different approaches. Which computing model would be the best solution for their task and group of workers? Which approach would be most efficient? How do we determine what is efficient? Is it based on the time it takes to complete the task? Or something else?

Ask students to give you examples of each of the three types of processing in their task allocation example.

Emphasize that much like the examples that you just discussed, more is not always better. There are advantages and challenges to the different approaches.

Activity 2.9.2 Video reflection (Budget 10 minutes)

Show this video on Sequential and Parallel Computing from CodeHS on YouTube and give students the guided notes to complete.
Have students read this short article on Parallel vs. Distributed Computing: An Overview by Purely Educational.
This can be completed in class or as a homework assignment. Once completed, discuss the benefits and challenges of each of the solutions. This can be completed as a whole group discussion, a Padlet response or warm up / ticket out the door.

Activity 2.9.3 Sorting Activity (Budget 45 minutes)

Complete the sorting activities in this Code.org lesson. Summarize and reflect on the process. Use the time from the first activity and the second activity to calculate the "speedup" of the parallel solution. Speedup of a parallel solution = time of sequential solution / time of parallel solution.

A sequential solution takes as long as the sum of all of its steps.
A parallel solution takes as long as its sequential tasks plus the longest of its parallel tasks.

Activity 2.9.4 Impacts of Distributed Computing (Budget 10 minutes)

The World Community Grid is a distributed computing network created in 2004 by philanthropic initiative of IBM.

World Community Grid enables anyone with a computer, smartphone or tablet to donate their unused computing power to advance cutting-edge scientific research on topics related to health, poverty and sustainability. Through the contributions of volunteers all over the globe, World Community Grid has supported 31 research projects to date, including searches for more effective treatments for cancer, HIV/AIDS and neglected tropical diseases. Other projects are looking for low-cost water filtration systems and new materials for capturing solar energy efficiently.

Show this video on how the World Community Grid has helped provide better access to clean water around the world. Introduce the concept of Citizen Science.

Citizen Science: Scientific research conducted in whole or part by distributed individuals, many of whom may not be scientists, who contribute relevant data to research by using their own computing devices.
Have students research the World Community Grid to see if there are any ongoing projects that relate to their topic/problem/innovation. Do NOT ask students to sign up and donate their computer processing power. That needs to be a decision the family makes.
Quick discussion: What are the beneficial effects, harmful effects and potential impact of the World community grid? What are security, privacy & legal concerns that arise?

Here is the associated webpage for teacher's to reference as background information.

Section 2.9

Sequential, Parallel & Distributed Computing

Learning Goals

Objectives and General Description

Activities

Resources