HomePublicationsPhD Thesis

Real-Time Scheduling on Heterogeneous Multiprocessors
Ref: CISTER-TR-140306       Publication Date: 17, Mar, 2014

Abstract:
Embedded computing is one of the most important areas in computer science today, witnessed by the fact that 98% of all computers are embedded. Given that many embedded systems have to interact “promptly” with their physical environment, the scientific community has invested signifi- cant efforts in developing algorithms for scheduling the workload, which is generally implemented as a set of tasks, at the right time and in proving before run-time that all the timing requirements will be satisfied at run-time. This field of study is referred to as the real-time scheduling theory. The scheduling theory for a unicore processor is well-developed; the scientific results are taught at all major universities world-wide and the results are widely-used in industry. Scheduling theory for multicores is emerging but the focus so far has been for multicores with identical processing units. This is unfortunate because the computer industry is moving towards heterogeneous multicores with a constant number of distinct processor types — AMD Fusion, Intel Atom and NVIDIA Tegra are some of the examples of such multicores.
This work deals with the problem of scheduling a set of tasks to meet their deadlines on heterogeneous multiprocessors with a constant number of distinct processor types. On heterogeneous multiprocessors, not all the processors are of the same type and further, the execution time of a task depends on the type of processor on which it executes. For such platforms, designing scheduling algorithms assuming that, tasks during their execution, can migrate between processors of different types is hard to achieve (if not impossible) for many practical systems since processors of different types typically vary in instructions sets, register formats, etc. Hence, designing algorithms in which either tasks cannot migrate between any two processors (referred to as non-migrative) or tasks can migrate between processors of same type (referred to as intra-migrative) is of greater practical significance.
For the non-migrative scenario, the scheduling problem can be solved in two steps: (i) assigning tasks to individual processors before run-time and (ii) once the assignment is done, scheduling the tasks on each processor using a uniprocessor scheduling algorithm at run-time. Scheduling tasks that are assigned to an individual processor is a well-studied problem and optimal scheduling algorithms exist for this problem, in the sense that, if there exists a schedule that meets all deadlines of the tasks then the optimal algorithms succeed in finding such a schedule as well. Hence, assuming that the tasks are scheduled during run-time on each processor using such optimal scheduling algorithms, this work focuses on designing algorithms for assigning tasks to individual processors on heterogeneous multiprocessors with a constant number of distinct processor types such that there exists a schedule that meets all deadlines for the assignment obtained by the algorithm.
Similarly, for intra-migrative scenario, the scheduling problem can be solved in two phases: first, assigning tasks to processor types (rather than to individual processors) before run-time and then scheduling the tasks on each processor type using a multiprocessor scheduling algorithm at run-time. Scheduling tasks that are assigned to a processor type is also a well-researched topic as this problem is equivalent to identical multiprocessor scheduling problem and optimal scheduling algorithms exist for this problem. Hence, the focus of this work is to design algorithms for assigning tasks to processor types on heterogeneous multiprocessors with a constant number of distinct processor types assuming that the tasks are later scheduled using the optimal scheduling algorithms. Therefore, assuming that the tasks are scheduled during run-time on each processor type using such optimal scheduling algorithms, this work focuses on designing algorithms for assigning tasks to processor types such that there exists a schedule that meets all deadlines for the assignment output by the algorithm. For the non-migrative scenario as well as the intra-migrative scenario, this work considers both the two-type heterogeneous multiprocessors in which the number of distinct processor types is two and the generic t-type heterogeneous multiprocessors in which the number of distinct processor types is t ≥ 2.
For the task assignment problems under consideration, it is not possible to design an optimal algorithm with polynomial time-complexity unless P = NP. Hence, non-optimal algorithms with polynomial time-complexity are designed and a metric referred to as the speed competitive ratio is used to quantify the the performance of these algorithms. The speed competitive ratio of an algorithm A is the smallest number S, such that any task set that can be assigned by an optimal algorithm upon a particular platform before run-time to meet all deadlines when scheduled at runtime, can also be assigned by A to meet all deadlines if given a platform in which each processor is S times as fast.
For the problem of assigning tasks to processor types, polynomial time-complexity algorithms with finite speed competitive ratios are proposed for two-type and t-type heterogeneous multiprocessors. Similarly, several polynomial time-complexity algorithms with different speed competitive ratios are also proposed for the problem of assigning tasks to individual processors on two-type and t-type heterogeneous multiprocessors.
This work also studies the problem of scheduling tasks that share resources such as data structures and sensors on heterogeneous multiprocessors — referred to as the shared resource scheduling problem. Tasks must operate on such resources in a mutually exclusive manner while accessing the resource, that is, at all times, when a task holds a resource, no other task can hold that resource. For this problem, polynomial time-complexity algorithms with finite speed competitive ratios are proposed for two-type and t-type heterogeneous multiprocessors.
Overall, the proposed algorithms have the following advantages. The proposed algorithms for shared resource scheduling problem are first of their kind since no previous algorithm exists for this problem. The other algorithms proposed in this work either have a better speed competitive ratio and/or a better time-complexity and/or a better average-case performance compared to the existing algorithms in the literature.

Gurulingesh Raravi

Document:

View
PDF Download
PDF