PD_ParallelDecomposition PD_ParallelAlgorithms TCPP_Architecture TCPP_Algorithms TCPP_Programming CS1 CS2 DSA Systems touch visual

Originally described by Gregory F. Bachelis, David A. James, Bruce R. Maxim and Quentin F. Stout (Bachelis1994)

No link to independent description publicly available. Please see details section for a synopsis.

Other activities by authors

(Bachelis1994): FindSmallestCard, CardSorting, OddEvenTranspositionSort, SieveOfErastothenes, AddLargeNumbers


From (Bachelis1994): The goal is to add a series of 16 random numbers. Each student is given a piece of paper (representing local memory) that only they have access to. Addition can only be performed between two numbers at any given time, and it assumed that it takes the same amount of time to add any two numbers. Thus, one addition operation takes one time step. The processor therefore employs a series of addition operations to to add the collection of numbers. Each number is written down on a separate card. Note cards are also provided for “message passing”.

Serial case:

Parallel Case

Two Students:

Four Students:

Eight students

The class then should asked to calculate the speedup of the parallel cases over the serial cases. The students should see that speedup is not linear, and that the addition of more processors does incur heavier communication cost. To make the example more concrete, assign a cost to each communication component (0.5 time step). Then ask students to recompute time steps and speedup. This should help students clearly observe the cost of communication overhead.

CS2013 Knowledge Unit Coverage

PD/Parallel Decomposition

Core Tier 1:

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

Core Tier 2:

4. Parallelize an algorithm by applying task-based decomposition. [Usage]

PD/Parallel Algorithms, Analysis & 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]

6. Implement a parallel divide-and-conquer (and/or graph algorithm) and empirically measure its performance relative to its sequential analog.

TCPP Topics Coverage

Architecture Topics

Programming Topics

Algorithms Topics


The visual aspect of this activity may make it less accessible for blind students. However. students communicating a message to a blind partner can read their total aloud. The instructor can facilitate passing the total to the next student as necessary.