Optimal Real-Time Scheduling on Two-Type Heterogeneous Multicore Platforms

Citations Over TimeTop 10% of 2015 papers

Abstract

Motivated by the cutting-edge two-type heterogeneous multicore chips, such as ARM's big.LITTLE, that offer a practical support for migration, this paper studies the global (or fully-migrative) approach to two-type heterogeneous multicore scheduling. Our goal is to design an optimal fully-migrative scheduling framework. To achieve this goal in an efficient and simple manner, we break the scheduling problem into two subproblems: workload assignment and schedule generation. We propose a per-cluster workload assignment algorithm, called Hetero-Split, that determines the fractions of workload of each task to be assigned to both clusters without losing feasibility with the complexity of O(n log n), where n is the number of tasks. Furthermore, it provides a couple of important properties (e.g., a dual property) that help to generate an optimal schedule efficiently. We also derive scheduling guidelines to design optimal schedulers for two-type heterogeneous multicore platforms, called Hetero-Fair. By tightly coupling the solutions of Hetero-Split and Hetero-Fair, we develop the first optimal two-type heterogeneous multicore scheduling algorithm, called Hetero-Wrap, that has the same complexity (O(n)) as in the identical multicore case. Finally, concerning a practical point of view, we derive the first bounds on the numbers of intra-and inter-cluster migrations under two-type heterogeneous multicore scheduling, respectively.

Related Papers

• → Using OS Observations to Improve Performance in Multicore Systems(2008)226 cited
• → Dynamic Scheduling of Real-Time Tasks in Heterogeneous Multicore Systems(2018)33 cited
• → Qalitative Study of Contention-aware Scheduling Algorithm for Asymmetric Multicore Processors(2020)2 cited
• → A Reconfigurable Computing Scheduler Optimized for Multicore Systems(2010)1 cited
• → Guidelines for data-parallel cycle-stealing in networks of workstations. II. On maximizing guaranteed output(2003)3 cited