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.

DOI: 10.1504/IJES.2020.105286

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article