Heterogeneous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.
The most relevant related work is @cite_31 , which developed the baseline WCRT bound as stated in Section . The analysis techniques of are based on the classical work by Graham @cite_21 @cite_36 for DAG (the special case of the model considered in this paper with only one type). The real-time scheduling problem for multiple untyped DAG has been intensively studied, with different scheduling paradigm including federated scheduling @cite_39 @cite_28 @cite_6 and global scheduling @cite_25 @cite_38 @cite_27 @cite_10 @cite_22 , which are also based on the classical work by Graham @cite_21 @cite_36 . Similarly, although we assume a single typed DAG task in this paper, our work would be a necessary step towards the scheduling and analysis of multiple recurring typed DAG tasks.
@cite_38 @cite_22 @cite_36 @cite_28 @cite_21 @cite_6 @cite_39 @cite_27 @cite_31 @cite_10 @cite_25
2620711632 2044949390 262229658 1625622590 1977289603 1917241563 2077163592 1599063719
A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. As the computational demands of real-time tasks increase, tasks may require internal parallelism in order to complete within stringent deadlines. In this paper, we consider the problem of mixed-criticality scheduling of parallel real-time tasks and propose a novel mixed-criticality federated scheduling (MCFS) algorithm for parallel tasks modeled by a directed acyclic graph. MCFS is based on federated intuition for scheduling parallel real-time tasks. It strategically assigns cores and virtual deadlines to tasks to achieve good schedulability. For high-utilization tasks (utilization ( )1), we prove that MCFS provides a capacity augmentation bound of (2+ 2 ) and ((5+ 5 ) 2 ) for dual- and multi-criticality, respectively. We show that MCFS has a capacity augmentation bound of (11m (3m-3) ) for dual-criticality systems with both high- and low-utilization tasks. For high-utilization tasks, we further provide a MCFS-Improve algorithm that has the same bound but can admit many more task sets in practice. Results of numerical experiments show that MCFS-Improve significantly improves over MCFS for many different workload settings. We also present an implementation of a MCFS runtime system in Linux that supports parallel programs written in OpenMP. Our implementation provides graceful degradation and recovery features. We conduct empirical experiments to demonstrate the practicality of our MCFS approach. have recently introduced some novel analytical techniques in order to derive a speed-up bound for the multiprocessor global EDF scheduling of systems of recurrent tasks that are represented using the sporadic DAG task model, and have applied these techniques to obtain a pseudo-polynomial time sufficient schedulability test. In this paper, these techniques are further generalized to yield an improved pseudo-polynomial time sufficient schedulability test for global EDF scheduling of systems of sporadic DAG tasks. It is shown that this new test strictly dominates the one by , in addition, schedulability experiments demonstrate that the improvement can be quite substantial for certain kinds of task systems. Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these task systems, we experience difficulties in applying such results to real application scenarios, where the execution flow of parallel tasks is characterized by multiple (and nested) conditional structures. When a conditional branch drives the number and size of sub-jobs to spawn, it is hard to decide which execution path to select for modeling the worst-case scenario. To circumvent this problem, we integrate control flow information in the task model, considering conditional parallel tasks (cp-tasks) represented by DAGs composed of both precedence and conditional edges. For this task model, we identify meaningful parameters that characterize the schedulability of the system, and derive efficient algorithms to compute them. A response time analysis based on these parameters is then presented for different scheduling policies. A set of simulations shows that the proposed approach allows efficiently checking the schedulability of the addressed systems, and that it significantly tightens the schedulability analysis of non-conditional (e.g., Classic DAG) tasks over existing approaches. Real-time systems increasingly contain processing units with multiple cores. To use this additional computational power in hard deadline environments, one needs schedulability tests for task models that represent the possibilities of parallel execution of jobs of a task. A standard model is to represent a (sporadically) recurrent task by a directed a cyclic graph (DAG). The nodes of the DAG correspond to the jobs of the task. All such jobs are released simultaneously, have to be completed within some common relative deadline, and some pairs of jobs are linked by a precedence constraint, i.e., an arc of the DAG. This poses new challenges for analyzing whether a task system is feasible, in particular for the commonly used online algorithms Earliest Deadline First (EDF) and Deadline Monotonic (DM). While for ordinary sporadic tasks the required algorithmic techniques are well-understood, despite recent research much remains open in this model. In this work, we completely close the gap between the algorithmic understanding of feasibility analysis for the usual sporadic task model and the case where each sporadic task is a DAG. We show for DAG tasks that EDF has a tight speedup bound of 2 - 1 m, where m is the number of processors, while DM has a speedup bound of at most 3 - 1 m. Moreover, we present polynomial and pseudopolynomial time tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF or DM to meet all deadlines on a specified number of processors. We remark that the effectiveness of some of our tests matches the best known algorithms for ordinary sporadic task sets, thus closing the gap. A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of re-current task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time. We study the scheduling of different types of tasks on different types of processors. If there are k types of tasks and @math , identical processors for tasks of type i, the finishing time of any list schedule is at most @math times worse than the optimal schedule. This bound is best possible. If the processors execute at different speeds then the performance of any list schedule (relative to the optimal schedule) is bounded by k plus the maximum ratio between the speeds of any two processors of the same type. Recurrent (periodic and sporadic) task systems have traditionally been scheduled upon multiprocessor platforms using either the partitioned or the global approach. Under the recently-proposed federated approach, each task is either restricted to execute upon a single processor (as in partitioned scheduling), or may execute upon multiple processors but is the only task to execute upon each of these processors. Earlier studies concerning the federated scheduling of task systems represented using the sporadic DAG model were restricted to implicit-deadline and constrained-deadline sporadic task systems, the research reported here extends this study to the consideration of task systems represented using the more general arbitrary-deadline sporadic DAG model.