Date Added: May 2010
Many computational solutions can be expressed as Directed Acyclic Graphs (DAGs), in which the nodes represent tasks to be executed and edges represent precedence constraints among the tasks. A fundamental challenge in parallel computing is to schedule such DAGs onto multi-core processors while preserving the precedence constraints. In this paper, the authors propose a lightweight scheduling method for DAG structured computations on multi-core processors. They distribute the scheduling activities across the cores and let the schedulers collaborate with each other to balance the workload. In addition, they develop a lock-free local task list for the scheduler to reduce the scheduling overhead.