Abstract:
The conceptual frontier that for many years separated the real-time embedded systems domain from the high-performance computing domain has been shattered by recent technological advances and market trends. Nowadays, many contemporary applications have started to cross the boundaries between the two domains: they are subject to stringent timing requirements and have huge computation demands, which cannot be successfully satisfied following the sequential execution paradigm. Intra-task parallelism enables an application to run simultaneously on different cores, thus allowing for increased performance and offering opportunities to make efficient use of the emergent many-core embedded architectures. However, parallelization adds another dimension to the already challenging problem of multiprocessor real-time scheduling.
In this dissertation, we are interested in studying the problem of scheduling a set of hard real-time parallel tasks atop multiprocessor systems, where each parallel task is represented as a Directed Acyclic Graph (DAG). The DAG task model reflects general features of parallelism characteristic of widely used parallel programming models (such as OpenMP). In this model, a task is defined as a set of concurrent subtasks whose execution has to obey to a set of precedence constraints. Subtasks that are independent of each other may execute either in parallel or sequentially, depending on the decisions of the real-time scheduler. We address both the global and partitioned scheduling paradigms, under traditional preemptive scheduling algorithms, while exploiting the internal structure of the DAGs. Furthermore, we also investigate the applicability of the DAG model to the schedulability analysis of parallel applications with conditional control-flow constructs.
First, we address the schedulability of a set of DAG tasks according to a global fixed-priority scheduling algorithm. To this end, we present a response time analysis based on the concept of problem window, a technique that has been extensively used to study the schedulability of sequential task in multiprocessor systems. Such problem window approach usually categorizes interfering jobs in three different groups: carry-in, carry-out and body jobs. By taking into account the precedence constraints between subtasks pertaining to the same DAG, we propose two novel techniques to derive more accurate upper-bounds on the workload produced by the carry-in and carry-out jobs of the interfering tasks. Using this new characterization, we then derive a schedulability analysis to compute an improved upper-bound on the worst-case response time of each parallel task in both the constrained and arbitrary deadline case.
Second, we look at the problem of scheduling a set of partitioned DAG tasks with constrained deadlines from two different perspectives. Here, partitioning means statically assigning each subtask to a specific core, yet allowing multiple subtasks of the same DAG task to run on different cores. In the first approach, we develop a response time analysis for fixed-priority scheduling, which can be used under any given subtask-to-core mapping. To solve the issue that arises from the potential cross-core dependencies, we show that a DAG task can be modeled and analyzed as a set of self-suspending tasks and present an algorithm to break the cyclic computations. In order to increase the effectiveness of this schedulability test, we also propose a response time analysis for sporadic self-suspending tasks running on a uniprocessor system. In the other approach, we propose a schedulability analysis based on a workload duplication technique. Specifically, we present a partitioning algorithm that maps similar paths of a DAG to the same cores, aiming to minimize the number of cores required for task feasibility and to eliminate cross-core dependencies. Thanks to the duplication of key subtasks, all resulting partitions become independent of each other. Thus, the problem of scheduling a set of partitioned DAGs is reduced to the problem of scheduling a set of sequential tasks on multiprocessors in a partitioned manner.
Third, we deal with the problem of modeling and scheduling a set of DAG tasks with conditional execution. Although it is expected that industrial applications feature conditional operations that depend on run-time data, the DAG model assumes that each and every instance of the DAG releases and executes all its subtasks. While conditional statements were not a major concern in the case of sequential tasks, we are the first to show that they are detrimental for the schedulability analysis of parallel tasks and thus should be explicitly modeled. Consequently, we generalize the DAG model by proposing a multi-DAG model where each conditional parallel task is characterized by a set of execution flows, each of which represented as a separate DAG. Due to conditional statements, only one of such execution flows is undertaken at each task activation. Then, we develop a two-step algorithm that constructs a single DAG of servers (servers are the scheduling entities) to handle the execution of a multi-DAG task, and prove that these servers are able to safely and fully execute any of its execution flows. As a result, each multi-DAG task can be modeled by its single DAG of servers, which facilitates in leveraging the existing single-DAG schedulability analysis techniques for analyzing the schedulability of conditional DAG tasks.
Experimental results validate the contributions proposed in this dissertation and show that they may lead to a substantial reduction in the pessimism of the schedulability analyses for DAG tasks comparatively to state-of-the-art methods. Such improvements are essential for exploiting multiprocessors in real-time embedded systems in a more efficient way.

Authors:


PhD Thesis, FEUP.
Porto.

Notes: Presidente do Juri Doutor José Alfredo Ribeiro da Silva Matos, Professor Catedrático da FEUP Vogais Doutor Robert Davis, Senior Research Fellow on the Department of Computer Science, on the University of York, United Kingdom; Doutor Eduardo Quinones Moreno, Senior Research on the Department of Computer Science, on the BSC - Barcelona Supercomputing Center, Spain; Doutor Vincent Nélis, Integrated Researcher, no CISTER – Instituto Superior de Engenharia do Porto /IPP (Orientador); Doutor Luis Miguel Pinho de Almeida, Professor Associado do Departamento de Engenharia Eletrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto; Doutor Pedro Alexandre Guimarães Lobo Ferreira Souto, Professor Auxiliar do Departamento de Engenharia Informática da Faculdade de Engenharia da Universidade do Porto.



Record Date: 11, Jan, 2019