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.
@cite_4 studied the scheduling of multiple typed DAG tasks by decomposing each DAG task into a set of independent tasks with artificial release time and deadlines, and then analyzed these decomposed independent tasks by known methods under non-preemptive G-EDF (global earliest deadline first). The work in @cite_4 is not directly comparable with our work due to the difference in problem models. However, when our method (based on Graham's analysis framework) is extended to the multiple-DAG setting in the future, a comparison between these two families of techniques would be meaningful.
@cite_4
1977289603 2044949390 2117135110 2537957541
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. 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. Chen (1994) develops an attractive variant of the classical problem of preemptively scheduling independent jobs with release dates and due dates. Chen suggests that in practice one can often pay to reduce the processing requirement of a job. This leads to two parametric max flow problems. Serafini (1996) considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel. Minimizing the maximum tardiness again gives a parametric max flow problem. A third problem of this type is deciding how many more games a baseball team can lose part way through a season without being eliminated from finishing first (assuming a best possible distribution of wins and losses by other teams). A fourth such problem is an extended selection problem of (1995a), where we want to discount the costs of "tree-structured" tools as little as possible to be able to process all jobs at a profit. It is tempting to try to solve these problems with the parametric push-relabel max flow methods of (GGT) (1989). However, all these applications appear to violate the conditions necessary to apply GGT. We extend GGT in three ways that allow it to be applied to all four of the above applications. We also consider some other applications where these ideas apply. Our extensions to GGT yield faster algorithms for all these applications. This paper considers for the first time end-to-end response-time analysis for DAG-based real-time task systems implemented on heterogeneous multicore platforms. The specific analysis problem that is considered was motivated by an industrial collaboration involving wireless cellular base stations. The DAG-based systems considered herein allow intra-task parallelism: while each invocation of a task (i.e., DAG node) is sequential, successive invocations of a task may execute in parallel. In the proposed analysis, this characteristic is exploited to reduce response-time bounds. Additionally, there is some leeway in choosing how to set tasks' relative deadlines. It is shown that by resolving such choices holistically via linear programming, response-time bounds can be further reduced. Finally, in the considered use case, DAGs are defined based upon just a few templates and individually often have quite low utilizations. It is shown that, by combining many such DAGs into one of higher utilization, response-time bounds can often be drastically lowered. The effectiveness of these techniques is demonstrated via both case-study and schedulability experiments.