Title: A branch-and-bound approach to scheduling of data-parallel tasks on multi-core architectures
Authors: Yang Liu; Lin Meng; Ittetsu Taniguchi; Hiroyuki Tomiyama
Addresses: Graduate School of Science and Engineering, Ritsumeikan University, Noji-Higashi 1-1-1, Kusatsu, Shiga, 525-8577, Japan ' College of Science and Engineering, Ritsumeikan University, Noji-Higashi 1-1-1, Kusatsu, Shiga, 525-8577, Japan ' Graduate School of Information Science and Technology, Osaka University, Yamadaoka 1-5, Suita, 565-0871, Japan ' College of Science and Engineering, Ritsumeikan University, Noji-Higashi 1-1-1, Kusatsu, Shiga, 525-8577, Japan
Abstract: This paper studies a task scheduling problem which schedules a set of data-parallel tasks on multiple cores. Unlike most of previous literature where each task is assumed to run on a single core, this work allows individual tasks to run on multiple cores in a data-parallel fashion. Since the scheduling problem is NP-hard, a couple of heuristic algorithms which find near-optimal schedules in a short time were proposed so far. In some cases, however, exactly-optimal schedules are desired, for example, in order to evaluate heuristic algorithms. This paper proposes an exact algorithm to find optimal schedules. The proposed algorithm is based on depth-first branch-and-bound search. In our experiments with up to 100 tasks, the proposed algorithm could successfully find optimal schedules for 135 test cases out of 160 within 12 hours. Even in cases where optimal schedules were not found within 12 hours, our algorithm found better schedules than state-of-the-art heuristic algorithms.
Keywords: task scheduling; multi-core; data parallelism; branch-and-bound.
International Journal of Embedded Systems, 2020 Vol.12 No.1, pp.125 - 135
Received: 19 Aug 2017
Accepted: 02 Apr 2018
Published online: 24 Feb 2020 *