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.
Abstract [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints . Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.] studied the U2Chain problem in which two processors are given and all jobs have unit processing time; every job can be executed on only one machine; there are chain-type precedence constraints among the jobs and the objective is to minimize the makespan. This problem arises from the job-system where different jobs require different resources, thus a job may be processed only on some special machine. Since the problem is strongly NP-hard, they gave an approximation algorithm with performance ratio of 5 3. The purpose of our paper is to improve their result by giving a new approximation algorithm with a worst-case guarantee 3 2 for this problem. In this paper a new approximation algorithm with worst case performance ratio 3 2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints . Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: “Does there exist a polynomial time heuristic with worst-case guarantee better than 5 3 for the problem U2Chain?”. The new approximation algorithm is also applied to the problem J 2| pmtn | C max . In a heterogeneous system, the efficient exploitation of parallelism requires scheduling strategies that account for heterogeneity among processors to achieve an effective mapping of computations to processors. The paper presents a scheduling heuristic specialized for heterogeneous multiprocessor systems which make use of several different types of processors. The new algorithm is based on the greedy strategy: no processor remains idle if there is some task available that it could process. A graph called the classified typed task graph is used to describe the current status of tasks of different types at each scheduling step. With the graph, the algorithm dynamically evaluates the priorities of tasks only when there are multiply executable candidates, and then schedules an appropriate one onto the currently available processors of the corresponding type. A preliminary evaluation shows that this algorithm has promising performance. >  In this paper we have analysed a scheduling problem where each task has a type and where only a bounded number of processors of each type is available. We show that the typed scheduling problem remains NP-complete for a disjoint set of chains, two types and one processor of each type. If the deadline is a constant number, this problem, given k processors, remains NP-complete for out-trees, in-trees and a disjoint union of chains. In contrast we give a polynomial algorithm if we have an interval order.