Parallel and Distributed Computing Chapter Notes | AP Computer Science Principles - Grade 9 PDF Download

Introduction

Parallel and distributed computing are key concepts in AP Computer Science Principles, addressing the need for faster and more efficient computing as traditional sequential methods reach their limits. This chapter explains how parallel computing uses multiple processors simultaneously and how distributed computing leverages multiple devices across locations to solve problems. It covers their advantages, calculations for execution time and speedup, and includes an example problem. Understanding these concepts helps us see how modern systems handle large data sets and complex tasks efficiently.

Parallel and Distributed Computing Definitions

• Sequential computing processes program instructions one at a time, but it’s limited as single processors can’t get faster without overheating.
• Parallel computing:
  • Breaks a program into smaller tasks, some of which run simultaneously on multiple processors (cores).
  • Modern computers use 4 to 24 cores for parallel processing.
  • Advantages:
    • Saves time and money by performing tasks concurrently.
    • Scales better than sequential computing, handling increased workloads effectively.
• Distributed computing:
  • Uses multiple devices, often in different locations, to run a program, communicating via messages.
  • Enables solving complex problems or handling large data sets that a single device couldn’t manage due to storage or processing limits.
  • Examples: Search engines, cloud applications (e.g., Gmail, Google Docs), and cryptocurrency mining.
• Both parallel and distributed computing process large data or complex problems faster than sequential computing, without overheating hardware.

Execution Time, Efficiency, and Speedup

AP CSP tests may include questions on execution time, efficiency comparisons, or speedup calculations for parallel and sequential solutions.

Calculating Execution Time

• Sequential Solutions:
  • Total time is the sum of all step durations.
  • Example: Steps taking 40, 50, and 80 seconds take 170 seconds total.
• Parallel Computing Solutions:
  • Time depends on the number of cores and whether steps are independent (don’t rely on each other’s results).
  • Example:For steps of 40, 50, and 80 seconds with two processors:
    • One processor does the 80-second step; the other does 40 and 50 seconds sequentially (90 seconds).
    • Total time is 90 seconds, as the longer processor’s time determines the total.
    • If the longest parallel task is longer (e.g., 100 seconds), it sets the total time.

Calculating Speedup

• Speedup = (Sequential time) ÷ (Parallel time).
• Example: 170 seconds (sequential) ÷ 90 seconds (parallel) = 1.88 speedup.

Speed Limits

• Parallel computing speed is limited by sequential steps that must wait for prior results.
• Non-programming example: In a group slideshow project, submitting the final slideshow can’t happen until all slides are ready, limiting parallel speedup.
• Adding more processors eventually yields less speedup due to sequential steps or communication overhead.
• Always check if steps are independent before calculating, as the problem will specify this.

Example Problem

Problem: A computer with two identical processors runs three independent processes:

• Process X: 60 seconds
• Process Y: 30 seconds
• Process Z: 50 seconds

Question: What’s the minimum time to execute all processes in parallel?
Options: 
(a) 60 seconds
(b) 70 seconds
(c) 80 seconds
(d) 90 seconds
Ans: (c) 80 seconds.
Solution: Processor A runs the 60-second process (X).
Processor B runs the 50-second process (Z), then the 30-second process (Y), totaling 80 seconds (50 + 30).
Since processes are independent, Processor B’s 80 seconds determines the total time, as Processor A finishes earlier (60 seconds).

Conclusion

Parallel and distributed computing enable faster processing for complex tasks and large data sets compared to sequential computing. These concepts are essential for modern applications and will be explored further in Big Idea 5, focusing on computing’s societal impacts.

Key Terms