Parallel application of task scheduling algorithm BCSH to a large fine-grained taskgraph divided by level

摘要

We study an automatic generating of parallel programs with task scheduling algorithms. Our algorithm BCSH generates a bulk synchronous schedule which can be applied message aggregation. However, it is not easy for BCSH to deal with large size taskgraphs, because BCSH requires O(N{sup}4) time where N is the number of nodes in a given taskgraph. In this paper, we propose algorithm PBCSH that divides a given taskgraph and then schedules each subgraph in parallel. Like BCSH, PBCSH generates a bulk synchronous schedule. As a result of our experiments, we find small difference in performance between a schedule that PBCSH generates and one that BCSH generates, though PBCSH schedules much faster than BCSH which also means that PBCSH can schedule larger taskgraphs than BCSH within the same time limit.