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 multicore processors while preserving the precedence constraints. In this paper, we propose a lightweight scheduling method for DAG structured computations on multicore processors. We distribute the scheduling activities across the cores and let the schedulers collaborate with each other to balance the workload. In addition, we develop a lock-free local task list for the scheduler to reduce the scheduling overhead. We experimentally evaluated the proposed method by comparing with various baseline methods on state-of-the-art multicore processors. For a representative set of DAG structured computations from both synthetic and real problems, the proposed scheduler with lock-free local task lists achieved 15.12x average speedup on a platform with four quadcore processors, compared to 8.77x achieved by lock-based baseline methods. The observed overhead of the proposed scheduler was less than 1% of the overall execution time.