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
1977289603 2044949390 1995073517 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. In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algorithm, and whether it can or cannot be improved has become a major open problem in scheduling theory. We address this problem by establishing a quite surprising relation between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. More specifically, we prove that if the single machine problem is hard to approximate within a factor of @math , then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of @math , where @math tends to 0 as @math tends to 0. Combining this with Bansal and Khot's recent hardness result for the single machine problem gives that it is NP-hard to improve upon the approximation ratio obtained by Graham, assuming a new variant of the unique games conjecture. 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.