ArrayAddition

PD_ParallelFundamentals PD_ParallelDecomposition PD_CommunicationAndCoordination PD_ParallelAlgorithms TCPP_Programming K_12 CS2 DSA Systems ProgLang visual movement

Originally described by Robert Chesebrough and Ivan Turner; the authors cite the 2nd chapter of James Reinders’ book (see citations) as inspiration for this example.

No link to indepdendent description available. Please see Details section for more information.


Details

Students sitting at desks represent “threads” on individual cores. Each student has a piece of paper on their desk representing local memory. Prior to the activity, the instructor writes an array on the board, filled with random values (limit 1 through 10 for ease of addition), with indices written underneath. The goal is to, as a class, add up all the elements in the array and update a global sum value written on a index card held by the instructor.

Naive Case

Defining Critical Regions

Using Reduction


CS2013 Knowledge Unit Coverage

PD/Parallel Fundamentals

2. Distinguish multiple sufficient programming constructs for synchronization that may be inter-implementable but have complementary advantages.

PD/Parallel Decomposition

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]

PD/Communication and Coordination

1. Use mutual exclusion to avoid a given race condition. [Usage]

2. Give an example of an ordering of accesses among concurrent activities (e.g., program with a data race) that is not sequentially consistent. [Familiarity]

5. Write a program that correctly terminates when all of a set of concurrent tasks have completed. [Usage]

8. Write a test program that can reveal a concurrent programming error; for example, missing an update when two activities both try to increment a variable. [Usage]

PD/Parallel Algorithms, Analysis and Programming

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


TCPP Topics Coverage

Programming Topics



Accessibility

This activity is highly visual and involves some movement. The critical section demonstration may be difficult for students who are mobility challenged. In addition, this activity may be difficult for blind students.


Assessment

(Chesebrough2010) used unplugged activities as part of a larger three-day workshop for 16 high schoool students at Brookyn Tech in summer 2009. Chesebrough and Turner report that “the best part” of the camp was the role playing, and that the exercises helped drive concepts home. However, some of the more advanced students felt that the activities were “childish”. However younger and/or less-experienced students enjoyed the role playing exercises.

If all students can see the global index card, it is possible for them to implictly avoid race conditions and fail to produce one, and determine that a core should just “know” what the value is. A short script may be helpful to ensure that students understand what they need to do and what can be assumed (and not assumed).


Citations