Collaborative Scheduling of DAG Structured Computations on Multicore Processors
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.