Computer Science · 10th Grade · Network Architecture and Web Systems · Weeks 19-27

Introduction to Parallel Processing

Students explore the concept of parallel processing, understanding how tasks can be divided and executed simultaneously to improve performance.

• Common Core State Standards
• CSTA: 3A-AP-17
• CSTA: 3A-CS-01

About This Topic

Parallel processing is the strategy of dividing a computational task into independent subtasks that can be executed simultaneously across multiple processors or cores. In US 10th-grade computer science, students connect this concept to both hardware architecture (multi-core CPUs and GPUs) and software design (threads, processes, and task decomposition). This topic aligns with CSTA Standards 3A-AP-17 and 3A-CS-01, addressing program design and hardware-software interaction.

Not all problems benefit equally from parallelism. Tasks with sequential dependencies, where step B cannot begin until step A is complete, cannot be meaningfully parallelized. Identifying which portions of a problem are 'embarrassingly parallel' versus inherently sequential is a core skill. Amdahl's Law provides a framework for estimating the maximum speedup achievable when only part of a task can be parallelized.

Students grasp these ideas most readily through physical simulations where they experience the difference between doing tasks one at a time versus splitting them among peers. The contrast between organizing a single student sorting 100 cards versus 10 students each sorting 10 cards makes theoretical speedup tangible.

Key Questions

1. Explain the basic idea of parallel processing.
2. Analyze simple problems that can benefit from parallel execution.
3. Compare the challenges of sequential versus parallel task execution.

Learning Objectives

• Compare the execution time of sequential versus parallel algorithms for a given task.
• Analyze simple problems to identify tasks that are suitable for parallel execution.
• Explain the relationship between the number of processors and potential performance gains.
• Evaluate the trade-offs between complexity and performance when designing parallel solutions.

Before You Start

Introduction to Algorithms

Why: Students need a foundational understanding of algorithms and how they represent step-by-step instructions for problem-solving.

Basic Programming Concepts (Variables, Loops, Conditionals)

Why: Understanding fundamental programming constructs is necessary to conceptualize how tasks are broken down and executed.

Key Vocabulary

Parallel Processing	A method of computation where multiple processors or cores work simultaneously on different parts of a single task to speed up execution.
Sequential Processing	A method of computation where tasks are executed one after another in a specific order, with each task completing before the next begins.
Task Decomposition	The process of breaking down a large, complex problem into smaller, independent subtasks that can be processed individually.
Amdahl's Law	A formula that calculates the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved.
Embarrassingly Parallel	A type of task that can be easily divided into many independent subtasks with little or no communication needed between them, making it ideal for parallel processing.

Watch Out for These Misconceptions

Common Misconception

Parallel processing is always faster than sequential processing.

What to Teach Instead

Parallel processing introduces overhead for dividing work, communicating between processes, and merging results. For small tasks or tasks with many sequential dependencies, this overhead can make parallel execution slower than sequential. Students discover this directly when their parallel card sort includes merging time in the total.

Common Misconception

Any task can be split into parallel parts if you have enough processors.

What to Teach Instead

Tasks with data dependencies, where each step requires the result of the previous step, cannot be meaningfully parallelized regardless of available processors. Identifying these sequential bottlenecks is as important as identifying parallel opportunities when designing efficient programs.

Common Misconception

More cores always means proportionally faster performance.

What to Teach Instead

Amdahl's Law shows that the sequential portion of any program imposes a hard ceiling on speedup, regardless of how many parallel processors are added. Doubling from 4 to 8 cores rarely doubles performance because the sequential fraction dominates at scale.

Active Learning Ideas

Simulation Game: Sequential vs. Parallel Sort Race

One student sorts a deck of 50 numbered cards in order while a group of five students each sort a subset of 10 cards simultaneously. The class records time for both approaches, discusses the actual speedup ratio, and identifies the overhead costs (dividing the deck, merging results) that reduce the theoretical maximum speedup.

25 min·Whole Class

Think-Pair-Share: Can This Be Parallelized?

Give students a list of six tasks: rendering each frame of a video independently, processing steps of a sequential recipe, searching separate sections of a database, computing a running total where each value depends on the previous, resizing 1,000 images, and building floors of a skyscraper. Students individually classify each as parallel-friendly or sequentially constrained, then compare reasoning with a partner.

20 min·Pairs

Inquiry Circle: Amdahl's Law in Practice

Groups receive a scenario where 60% of a program can be parallelized and must calculate the theoretical maximum speedup for 2, 4, 8, and unlimited processors. They graph the results, identify the diminishing returns, and write a one-paragraph recommendation explaining when adding more processors stops being cost-effective.

30 min·Small Groups

Real-World Connections

• Video game developers use parallel processing to render complex graphics and simulate realistic physics in real-time, allowing for immersive gaming experiences on consoles and PCs.
• Scientific researchers in fields like climate modeling and genomics employ massive parallel computing clusters to analyze vast datasets and run complex simulations, accelerating discoveries.
• Financial institutions utilize parallel processing for high-frequency trading algorithms and risk analysis, enabling them to process millions of transactions and market data points per second.

Assessment Ideas

Exit Ticket

Provide students with a short list of tasks (e.g., sorting a deck of cards, calculating the average of 10 numbers, solving a maze). Ask them to identify which tasks are 'embarrassingly parallel' and explain why, and which are sequential and why.

Quick Check

Present a simple scenario, such as preparing ingredients for a large meal. Ask students to describe how they would divide the tasks among 3 people to complete it faster than if one person did everything. They should identify at least two distinct subtasks.

Discussion Prompt

Facilitate a class discussion using the prompt: 'Imagine you have a task that takes 10 minutes to complete sequentially. If you could perfectly split it across 2 processors, what is the absolute fastest it could possibly finish, according to Amdahl's Law? What real-world factors might prevent you from reaching that ideal speedup?'

Frequently Asked Questions

What is parallel processing and how is it different from sequential processing?

Sequential processing executes tasks one at a time, in order, on a single processor. Parallel processing divides a problem into independent subtasks and runs them simultaneously on multiple processors or cores. The goal is to reduce total execution time. A GPU rendering a 3D scene processes thousands of pixels in parallel, while a CPU running a loop executes one iteration at a time.

What kinds of problems benefit most from parallel processing?

Problems that can be divided into independent subtasks with no shared state are ideal candidates, often called 'embarrassingly parallel.' Examples include image processing (each pixel transformed independently), Monte Carlo simulations (each trial is independent), and search operations across partitioned data. Problems with strong sequential dependencies, like a step-by-step algorithm where each result feeds the next, benefit far less.

What are the main challenges of parallel versus sequential task execution?

Sequential programs are simpler to reason about because execution order is predictable. Parallel programs introduce challenges including race conditions (two processes modifying shared data simultaneously), deadlock (two processes waiting for each other), overhead from task coordination, and difficulty in debugging non-deterministic execution order.

How does active learning help students understand parallel processing concepts?

Physical sorting simulations make abstract speedup ratios concrete. When students time both approaches and calculate their own speedup ratio, they encounter the overhead reality firsthand. Discovering that 5 parallel workers didn't produce 5x speedup prompts genuine questions about coordination cost and Amdahl's Law that a lecture would need to manufacture.