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

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.