Semi-Partitioned Scheduling of Fork-Join Tasks using Work-Stealing

Abstract

This paper explores the behavior of parallel fork-join tasks on multicore platforms by resorting to a semipartitioned scheduling model. This model offers a promising framework to embedded systems which are subject to stringent timing constraints as it provides these systems with very interesting properties. The proposed approach consists of two stages—an offline stage and an online stage. During the offline stage, a multi-frame task model is adopted to perform the fork-join task-to-core mapping so as to improve the schedulability and the performance of the system, and during the online stage, work-stealing is exploited among cores to improve the system responsiveness as well as to balance the execution workload. The objective of this work is twofold: (1) to provide an alternative technique that takes advantage of the semi-partitioned scheduling properties by offering the possibility to accommodate fork-join tasks that cannot be scheduled in any pure partitioned environment, and (2) to reduce the migration overhead which has shown to be a traditional major source of non-determinism in global approaches. The simulation results show an improvement of the proposed approach over the state-of-theart of up to 15% of the average response-time per task set.