Heterogeneous multiprocessors can offer high performance at low energy expenditures. However, to be able to use them in hard real-time systems, timing guarantees need to be provided, and the main challenge is to determine the worst-case schedule length (also known as makespan) of an application. Previous works that estimate the makespan focus mainly on the independent-task application model or the related multiprocessor model that limits the applicability of the makespan. On the other hand, the directed acyclic graph (DAG) application model and the unrelated multiprocessor model are general and can cover most of today's platforms and applications. In this work, we propose a simple work-conserving scheduling method of the tasks in a DAG and two new approaches to finding the makespan. A set of representative OpenMP task-based parallel applications from the BOTS benchmark suite and synthetic DAGs are used to evaluate the proposed method. Based on the empirical results, the proposed approach calculates the makespan close to the exhaustive method and with low pessimism compared to a lower bound of the actual makespan calculation.

Guaranteeing timing constraints for parallel real-time applications deployed on multicore platforms is challenging, especially for applications containing non-preemptive execution blocks, that suffer from priority inversions. In this article, we propose to model such applications using a sporadic directed acyclic graph (DAG) model where preemption may take place only between the nodes of a DAG task. We present a new method for response-time analysis of such tasks scheduled with the global fixed-priority scheduling policy. We show that our method outperforms the state-of-the-art techniques significantly in terms of resource utilization in experimental evaluations using both benchmark and randomly generated task sets. We also present a method to deal with global EDF scheduling, which is a new technique proposed for response time analysis of sporadic DAG tasks with non-preemptive nodes.

This paper presents a federated scheduling algorithm for implicit-deadline sporadic DAGs that execute on an unrelated heterogeneous multiprocessor platform. We consider a global work-conserving scheduler to execute a single DAG exclusively on a subset of the unrelated processors. Formal schedulability analysis to find the makespan of a DAG on its dedicated subset of the processors is proposed. The problem of determining each subset of dedicated unrelated processors for each DAG such that the DAG meets its deadline (i.e., designing the federated scheduling algorithm) is tackled by proposing a novel processors-to-task assignment heuristic using a new concept called processor value . Empirical evaluation is presented to show the effectiveness of our approach.

We consider the scheduling of a real-time application that is modeled as a collection of parallel and recurrent tasks on a multicore platform. Each task is a directed-acyclic graph (DAG) having a set of subtasks (i.e., nodes) with precedence constraints (i.e., directed edges) and must complete the execution of all its subtasks by some specified deadline. Each task generates potentially infinite number of instances where the releases of consecutive instances are separated by some minimum inter-arrival time. Each DAG task and each subtask of that DAG task is assigned a fixed priority. A two-level preemptive global fixed-priority scheduling (GFP) policy is proposed: a task-level scheduler first determines the highest-priority ready task and a subtask-level schedulerthen selects its highest-priority subtask for execution. To our knowledge, no earlier work considers a two-level GFP scheduler to schedule recurrent DAG tasks on a multicore platform. We derive a schedulability test for our proposed two-level GFP scheduler. If this test is satisfied, then it is guaranteed that all the tasks will meet their deadlines under GFP. We show that our proposed test is not only theoretically better but also empirically performs much better than the state-of-the-art test in scheduling randomly generated parallel DAG task sets.

Multicore architectures can provide high predictable performance through parallel processing. Unfortunately, computing the makespan of parallel applications is overly pessimistic either due to load imbalance issues plaguing static scheduling methods or due to timing anomalies plaguing dynamic scheduling methods. This paper contributes with an anomaly-free dynamic scheduling method, called Lazy, which is non-preemptive and non-greedy in the sense that some ready tasks may not be dispatched for execution even if some processors are idle. Assuming parallel applications using contemporary taskbased parallel programming models, such as OpenMP, the general idea of Lazy is to avoid timing anomalies by assigning fixed priorities to the tasks and then dispatch selective highestpriority ready tasks for execution at each scheduling point. We formally prove that Lazy is timing-anomaly free. Unlike all the commonly-used dynamic schedulers like breadth-first and depth-first schedulers (e.g., CilkPlus) that rely on analytical approaches to determine an upper bound on the makespan of parallel application, a safe makespan of a parallel application is computed by simulating Lazy. Our experimental results show that the makespan computed by simulating Lazy is much tighter and scales better as demonstrated by four parallel benchmarks from a task-parallel benchmark suite in comparison to the state-of-the-art.

The problem of estimating the makespan for parallel applications is overly pessimistic bounds either due to load imbalance issues plaguing static scheduling methods or due to timing anomalies plaguing dynamic scheduling methods for multicore architectures. While dynamic scheduling (where tasks are not pre-assigned) offers better utilization of the processors, it suffers from timing anomalies. This paper contributes with a new timing-anomaly-free dynamic scheduling algorithm, called the Out-of-(priority)-order Lazy (O-Lazy) that offers safe and tighter estimation of the makespan of parallel applications.