Title: Mouldable fork-join task scheduling techniques with inter and intra-task communications

Authors: Hiroki Nishikawa; Kana Shimada; Ittetsu Taniguchi; Hiroyuki Tomiyama

Addresses: Graduate School of Science and Engineering, Ritsumeikan University, Noji-Higashi 1-1-1, Kusatsu, Shiga, 525-8577, Japan; Japan Society for the Promotion of Science, Kojimachi Business Center Building, 5-3-1 Kojimachi, Chiyoda-ku, Tokyo 102-0083, Japan ' Graduate School 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: Multicore task scheduling that determines the execution order of tasks and mapping on multiple cores is one of the most crucial design processes in order to fully exploit the potential of multicore systems. This paper studies a task scheduling problem for mouldable fork-join tasks with inter and intra-task communications. Unlike existing works, our work assumes that a task can be split into multiple threads, and the threads can run independently in a data-parallel fork-join manner. Our proposed techniques decide the number of cores and the execution start time for each task on the assumption of inter and intra-task communications at the same time during scheduling. The proposed techniques are based on integer programming formulation. The goal is to minimise the overall schedule length. We evaluate the performance of our proposed techniques and the effect of the communications on scheduling results.

Keywords: task scheduling; multicore; parallel task; integer programming.

DOI: 10.1504/IJES.2022.122074

International Journal of Embedded Systems, 2022 Vol.15 No.1, pp.69 - 81

Received: 23 Oct 2020
Accepted: 13 Jun 2021

Published online: 08 Apr 2022 *

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