CodeBlanks Logo Icon CodeBlanks
Login Register

Parallel algorithms

PRAM parallel model.

Parallel algorithms

Parallel algorithms solve a problem on multiple processors simultaneously. The PRAM (Parallel Random Access Machine) is a theoretical model used to describe parallel algorithms.

In PRAM, multiple processors access a shared memory concurrently. With p processors and problem size n, the parallel time T_p is typically close to T_1 / p.

Speedup is T_1 / T_p, and efficiency is T_1 / (p · T_p).

Amdahl's law

Amdahl's law sets the upper bound on speedup based on the non-parallel portion. If a fraction p of the problem is parallel, the maximum speedup is 1 / ((1 - p) + p / n), where n is the processor count.

For example, a 95% parallel problem can be at most 20 times faster with infinite processors. This law shows the limits of parallelization.

Efficient parallel design minimizes the non-parallel portion.

Practice parallel_sum function

Write parallel_sum(arr). Return the sum via parallel reduction: at each step sum adjacent pairs. Print 36 with print(parallel_sum([1, 2, 3, 4, 5, 6, 7, 8])).

Starter code

solution.py
def parallel_sum(arr):
    # Parallel reduction simulation

Sample solution

solution.py
def parallel_sum(arr):
    # Parallel reduction simulation
    while len(arr) > 1:
        new_arr = []
        for i in range(0, len(arr), 2):
            if i + 1 < len(arr):
                new_arr.append(arr[i] + arr[i + 1])
            else:
                new_arr.append(arr[i])
        arr = new_arr
    return arr[0]
print(parallel_sum([1, 2, 3, 4, 5, 6, 7, 8]))

Expected output

36

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 How is speedup defined?

solution.py
speedup = T_1 / T_p
  • T_p · T_1
  • T_1 / T_p Correct answer
  • p · T_p
  • T_1 + T_p

Explanation: Speedup is T_1 / T_p.

2 parallel reduction

Question 
for i in range(0, len(arr), ____):
    new_arr.append(arr[i] + arr[i + 1])
Answer 
for i in range(0, len(arr), 2):
    new_arr.append(arr[i] + arr[i + 1])

Explanation: Stride-2 scan simulates parallel reduction.

3 Parallel concepts

Term Meaning
PRAM Theoretical model
speedup T_1 / T_p
Amdahl Serial limit
reduction Adjacent pair

All lessons in Expert

1 Amortized analysis

  1. What is amortized?
  2. Aggregate method
  3. Dynamic array example
  4. Summary - Amortized

2 NP-completeness

  1. P and NP
  2. NP-complete
  3. Reduction
  4. Summary - NP-completeness

3 Approximation and randomized

  1. Approximation algorithms
  2. Randomized algorithms
  3. Las Vegas and Monte Carlo
  4. Summary - Approximation and randomized

4 String matching

  1. KMP algorithm
  2. Rabin-Karp
  3. Boyer-Moore
  4. Z-algorithm
  5. Suffix array
  6. Summary - String matching

5 Computational geometry

  1. Vector cross product
  2. Convex hull
  3. Line intersection
  4. Closest pair
  5. Point in polygon
  6. Summary - Geometry

6 Network flow

  1. Flow network
  2. Ford-Fulkerson
  3. Edmonds-Karp
  4. Max-flow min-cut
  5. Bipartite matching
  6. Summary - Network flow

7 Game theory and parallel

  1. Minimax
  2. Alpha-beta pruning
  3. Nash equilibrium
  4. Parallel algorithms
  5. MapReduce
  6. Summary - Game theory and parallel

8 Expert final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4
  5. Challenge 5