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 scheduling problems with different workload-processor binding restrictions have been studied in the past, including the inclusive processing set restriction @cite_23 @cite_7 @cite_11 @cite_12 where for any two processor sets assigned to two tasks, one set must be the subset of the other , the interval processing set restriction @cite_19 @cite_15 where any two processing sets may have the same machines as the other but one is not a subset of the other and the tree-hierarchical processing set restrictions @cite_30 @cite_0 where each machine is described as a vertex of a tree and a processing set is a path from root to a leaf . These models are all different from our work. On the other hand, much work has been done on scheduling of tasks on heterogeneous multiprocessor with workload-processor binding restrictions @cite_30 @cite_37 @cite_24 , and @cite_32 @cite_9 provided comprehensive surveys for this line of work.
@cite_30 @cite_37 @cite_7 @cite_9 @cite_32 @cite_0 @cite_19 @cite_24 @cite_23 @cite_15 @cite_12 @cite_11
2265244619 2557854731 2081435731 2113497279
In 2008, we published a survey paper on machine scheduling with processing set restrictions [Leung, J.Y.-T., Li, C.-L., 2008. Scheduling with processing set restrictions: a survey. Int. J. Prod. Econ. 116 (2), 251–262]. Since the appearance of that survey paper, there has been a significant increase in interest in this field. In this paper, we provide an expository update of this line of research. Our survey covers five types of processing set restrictions, namely inclusive processing sets, nested processing sets, interval processing sets, tree-hierarchical processing sets, and arbitrary processing sets, and it covers both offline and online problems. While our main focus is on scheduling models with a makespan objective, other performance criteria are also discussed. We consider the problem of scheduling n jobs on m parallel batching machines with inclusive processing set restrictions and non-identical capacities. The machines differ in their functionality but have the same processing speed. The inclusive processing set restriction has the following property: the machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. Each job is characterized by a processing time that specifies the minimum time needed to process the job, a release date before which it cannot be processed, and a machine index which is the smallest index among the machines that can process it. Each batching machine has a limited capacity and can process a batch of jobs simultaneously as long as its capacity is not violated. The capacities of the machines are non-identical. The processing time of a batch is the maximum of the processing times of the jobs belonging to it. Jobs in the same batch have a common start time and a common completion time. The goal is to find a non-preemptive schedule so as to minimize makespan (the maximum completion time). When all jobs are released at the same time, we present two fast algorithms with approximation ratios 3 and 9 4, respectively. For the general case with unequal release dates, we develop a polynomial time approximation scheme (PTAS), which is also the first PTAS even for the case with equal release dates and without processing set restrictions. We consider multiprocessor scheduling to minimize makespan. Each job has a given processing time and in addition, a subset of machines associated with it, also called its processing set. Each job has to be assigned to one machine in its set, thus contributing to the load of this machine. We study two variants of this problem on identical machines, the case of nested processing sets, and the case of tree-hierarchical processing sets. In addition, we consider uniformly related machines with a special case of inclusive processing sets, which has a clear motivation. We design polynomial time approximation schemes for these three variants. The first case resolves one of the open problems stated in the survey by Leung and Li (2008). We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4 3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5 3, which is better than the best known algorithm whose worst-case bound is 7 4. In both cases, we will give examples achieving the worst-case bounds.