PD_ParallelDecomposition PD_ParallelAlgorithms TCPP_Programming K_12 CS2 DSA 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, ParallelAddition


From (Bachelis1994): The goal is to introduce students to how large pairs of numbers in parallel.

Suppose the goal is to add two large numbers (in this example, 534,789,213 and 495,378,388). The instructor starts by writing the two numbers on the blackboard like so:

+ 495,378,388

The student “processors” sit facing the blackboard. Each student is assigned a certain set of contiguous digit columns. For example, if there are three students, one student would be assigned the 1s to 100s place, another student would assigned the 1,000 to 100,000 place, and last the 1 million to 100 million place.

Each student is then given an instruction sheet that looks like the following:

1. Add the two _digit numbers from your assigned columns.
2. If the sum requires more than _ digits, tell left neighbor "carry"
3. If your right neighbor says "carry", write "carry" above your total, and add one. 
   If the sum now contains a carry, say "carry" to your left neighbor. 
4. Face right when you are done, and hold up the _ digit answer to the blackboard.

Consider the case of 3 student processors. The two large numbers shown in our earlier example will then be split up as follows amongst the three students (student desk positions are also shown):

 | 534 | 789 | 213 |
 | 495 | 378 | 388 |
 [stu2][stu1][stu0 ]

In this example, each student gets assigned 3 digit columns (thus the _ on their instruction sheet is replaced with the number 3)

The instructor then writes the total on the board: 1,030,167,601. Since student 2 said carry, the instructor knows to put a leading 1 to the total.

The exercise can then be repeated with more students or larger numbers. Note that this exercise can be used to demonstrate overflow (to do so, the instructor just does not place the leading number on the board).

Students should recognize that in the parallel case, the fact that one person is sending a carry is independent of whether or not a carry is received. A more complex algorithm is also presented in (Bachelis1994), but we omit it here.

CS2013 Knowledge Unit Coverage

PD/Parallel Decomposition

Core Tier 2

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

PD/Parallel Algorithms

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

TCPP Topics Coverage

Programming 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.