PD_ParallelDecomposition PD_ParallelAlgorithms PD_ParallelArchitecture PD_ParallelPerformance TCPP_Architecture TCPP_Programming TCPP_Algorithms K_12 visual touch

Oklahoma Supercomputing Center for Educaton and Research (OSCER)

“Supercomputing in Plain English” - Overview, Slides 45-52.


It is theoretically possible to “act out” the analogy by using an actual puzzle. However, the puzzle needs to be small enough to enable students to complete the puzzle in a reasonable amount of time. This variation is described in (Neeman2006):

Shared Memory:

The above questions lead to a discussion about overhead issues such as contention for shared resources. While in a no-overhead situation it would take 30 minutes for two people to complete the puzzle, communication overhead will cause the puzzle to take more than 30 minutes to complete. Adding more people increases the communication overhead, and the discussing turns to the notion of diminishing returns.

Distributed Memory:

Everyone except for A and B goes back and returns to their seats. Pull out a different puzzle, this time where the pieces for A and the pieces of B are in different baggies. Ask B to go to another table across the room.

The above questions enable students to see that while there is less resource contention, the communication cost gets more expensive. As more students are added, there is additional communication cost. The discussion then transitions to load balancing. Students learn that if processor speeds are equal, then work should be balanced amongst them. However, if one processor is much faster than the other, then that processor should get additional work (Neeman2006).

CS2013 Knowledge Unit Coverage

Parallel Decomposition (Core Tier 1)

1. Explain why synchronization is necessary in a specific parallel program. [Usage]

2. Identify opportunities to partition a serial program into independent parallel modules. [Familiarity]

Parallel Algorithms, Analysis and Programming (Core Tier 2)

3. Define “speed-up” and explain the notion of an algorithm’s scalability in this regard. [Familiarity]

4. Identify independent tasks in a program that may be parallelized. [Usage]

Parallel Architecture (Core Tier 1, Elective)

1. Core Tier 1: Explain the differences between shared and distributed memory. [Familiarity]

8. Elective: Describe the key performance challenges in different memory and distributed system topologies. [Familiarity]

Parallel Performance (Elective)

1. Detect and correct a load imbalance. [Usage]

2. Calculate the implications of Amdahl’s law for a particular parallel algorithm. [Usage]

3. Describe how data distribution/layout can affect an algorithm’s communication costs. [Familiarity]

5. Explain the impact of scheduling on parallel performance. [Familiarity]

TCPP Topics Coverage

Architecture Topics

Programming Topics

Algorithms Topics


The analogy and exercise are very visual; this exercise may not be appropriate for blind students.


Unknown. (Neeman2006) describes the different analogies. There is no assessment provided in (Neeman2006) or (Neeman2008).