DAG Scheduling Algorithm for a Cluster-Based Many-Core Architecture
Yuto Kitagawa, Tasuku Ishigooka, Takuya Azumi · 2018
This paper proposes a directed acyclic graph (DAG) scheduling algorithm for cluster-based many-core architecture. Most of DAG scheduling methods that consider multiple processors and communication delays use a heuristic approach because it is difficult to shorten a schedule length (i.e.,makespan). Unfortunately, existing heuristic algorithms do not consider tasks that require a large number of computational resources. Such tasks typically need to be offloaded to a large-scale computational resource such as a many-core system or graphics processing unit (GPU). Therefore, we propose a DAG scheduling algorithm that uses a cluster-based many-core architecture to offload such computation; here, we use Kalray MPPA-256 as the many-core architecture. Our algorithm divides many-core computational resources for such tasks. Comparing our results with existing algorithms, we succeeded in shortening makespan with many types of DAGs while also considering Amdahl's law. We also compared the deadline miss ratio and execution time of our algorithm to existing algorithms, and show that the proposed algorithm is superior to the existing algorithms for any evaluation metrics.