ABSTRACT
Many computational solutions can be expressed as directed acyclic graphs (DAGs) with weighted nodes. In parallel computing, scheduling such DAGs onto multi/many-core processors remains a fundamental challenge. In this chapter, we first introduce a modularized scheduling method for DAGstructured computations on multicore processors, where various heuristics can be utilized for each module within the scheduling framework. This modular design enables the scheduler to be adaptive to various underlying architectures. In particular, we develop lock-free data structures for reducing the overhead due to coordination. Second, we extend the scheduling method to many-core
processors. Considering the architectural characteristics of many-core processors, we propose a hierarchical scheduler with dynamic thread grouping. Such a scheduler dynamically adjusts the number of threads used for scheduling and task execution. Therefore, it can adapt to the input task graph to improve performance. We evaluate the proposed method using various data sets. We also use exact inference in junction trees, a real-life problem in machine learning, to evaluate the performance of the proposed schedulers on multi/many-core processors.
