Scheduling hard real-time tasks in heterogeneous multiprocessor platforms subject to energy and temperature constraints

Abstract

The power wall is a barrier to improvement in the processor design process due to the power consumption of components. The production of energy optimum systems demands knowledge of different disciplines. The usage of heterogeneous multicore platforms is appealing for recent applications, e.g., hard real-time systems. The motivation is the potential reduced energy consumption offered by such platforms. Hard real-time systems are present in life critical environments. Reducing the energy consumption on such systems is an onerous process. Scheduling becomes particularly challenging to improve system utilization and minimize system energy consumption and peak temperature on such platforms, specially subject to hard real-time constraints. Therefore, we propose a study to effectively answer the pertinent research question: “How to offer users timing correctness and guarantees of hard real-time systems executed on heterogeneous multicore systems with energy and temperature constraints?”. Finding optimal solutions for such question has still several open research questions. The main aim of this thesis is to propose an energy optimization method for hard realtime system on heterogeneous multicore platform demonstrating that it is possible to timely compute timing correctness and guarantees using a sufficient and necessary condition; accounting for energy, temperature, preemption, precedence, shared resources constraints, and architectural interference. The proposal is a two fold approach. First, we investigate the process of finding the optimal task to core and frequency to task processes by means of applying exact schedulability tests for heterogeneous multicore platforms. Second, the outcome of the optimization analysis shall be used as reference to the on-line scheduler. We believe that we have achieved the main objective of this research by combining: (a) schedulability analysis from hard real-time systems, (b) representative mathematical formulations, based on integer linear programming, covering modern processors technological characteristics and using a classical combinatorial mathematical formulation (Multilevel Generalized Assignment Problem), and (c) robust exact implicit enumeration algorithmic strategies from combinatorial optimization, such as branch-and-cut and branch-and-price. The systematic literature review in the research subject reveals that the field has open questions to be answered. For instance, to the knowledge of the author only five works in the state-of-the-art literature deal with the problem by providing optimal solutions. Typically, the existing approaches focus on either heuristics or approximation algorithms. Also, only one work has a proposal to evaluate the schedulability in this scenario with an exact test. The typical formulation in the specialized literature is a 0/1 integer linear programming model which considers a continuous processor frequency domain and determines a single operating frequency per processor. One of the hypotheses tested in this research is: stronger feasibility analysis offers tighter bounds for the problem. We believe that this can be observed, for example, in the results produced by solvers for fixed priority schedulers, by means of an analysis based on a comparative study. By applying less accurate schedulability tests, such as utilization based, the solvers take longer to converge to optimal solutions, when compared to solvers that apply exact schedulability tests based on response time analysis. Another hypothesis tested in this research is: practical instances of the problem are timely solvable to optimal. We have experimented, by means of a comparative study, on finding feasible solutions for workload for fixed priority schedulers with up to 50 tasks distributed on four processors with seven different available frequencies. On independent hard real-time tasks scheduled using EDF policy, we found optimal distribution of up to 90 tasks on four processors with seven different available frequencies. In both cases, the solutions were found within 30 min of execution time. Similarly, on dependent tasks workload, we have optimally distributed 22 tasks, from an automotive control hard real-time application, on four processors with seven different available frequencies, with two shared resources and 23 precedence constraints within 1.5 h. We consider a few hours in the design phase a price worth paying in this context.