Title

Simulation Of Concurrent Dynamic Task Graph

Overview

Task graphs are used for scheduling tasks on parallel processors when the tasks have dependencies. And the task scheduling must be performed on the fly if the tasks and task dependencies aren't known ahead of time. So an algorithm for a concurrent dynamic-task graph is presented to solve this problem.

Paper

Theodore Johnson, Timothy A. Davis and Steven M. Hadfield. A Concurrent Dynamic Task Graph. Parallel Computing, 22(2): 327-333, 1996.

Additional reading material

M.Herlihy. A methodology for implementing highly concurrent data structures.
Duane A. Bailey. Data Structures in Java for the Principled Programmer.

Implementation details

Implement the algorithm in Java for a concurrent dynamic-task graph. Simulate it with GUI if time allows.