ParallelGarbageCollection

PD_CommunicationAndCoordination TCPP_Algorithms CS2 DSA ParProg Graduate movement visual

Originally described by Paulo A.G. Sivilotti and Scott Pike

Paper and poster available online:


Details

See paper for details. In summary, this activity presents a directed graph with a distinguished vertex (labeled the root). Vertices are connected to each other with some number of edges. The end-goal is determine the set of reachable vertices from the root (“food”) and distinguish them from the set of non-reachable vertices (“garbage”). Complicating the process is the presence of a mutator process that can modify (add or delete) edges; the set of vertices stay constant.

A group of 15 to 20 students are chosen for the activity to represent the vertices of the graph. Each student is given a hat and a set of 12 index cards. One student play the part of the root.

This activity is effective at demonstrating an incorrect algorithm. To force an incorrect execution case, the instructor joins the activity as a special node:

Tips from the authors * Ensure that students know each other’s names prior to the activity.


CS2013 Knowledge Unit Coverage

PD/Communication and Coordination

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.


TCPP Topics Coverage

Algorithms Topics


The instructors used this activity in an upper-level undergraduate course on parallel programming. They also recommend the activity for graduate students.


Accessibility

The activity may be difficult for students who are blind and/or have mobility issues.


Assessment

No assessment provided.


Citations