**Real-Time Scheduling on Heterogeneous Multiprocessors**

Ref: CISTER-TR-140306 Publication Date: 17, Mar, 2014

Ref: CISTER-TR-140306 Publication Date: 17, Mar, 2014

# 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.

**Authors:**

PhD Thesis, Faculdade de Engenharia da Universidade do Porto.

Porto, Portugal.

Record Date: 17, Mar, 2014