Task Model And Scheduling Algorithms

Task Model and Scheduling Algorithms: Real-time analysis offers several methods for describing the workload of a real-time system. This paper analyzes
mixed task sets of CPU-only and GPU-using tasks with the synchronous implicit-deadline periodic task model as it adequately describes common workloads and has wellunderstood analytical properties.

A synchronous implicit-deadline periodic task set, T, consists of as a set of recurrent tasks, Ti, some of which may access a GPU. We let G(T) denote the set of GPUusing tasks in T. Each task is described by three parameters: its period, pi, which measures the separation between task recurrences (known as jobs); its worst-case CPU execution time, ei, which bounds the amount of CPU processing time a job must receive before completing; and

its worst-case GPU execution time, si, which bounds the amount of GPU processing time required by one of its jobs. This last parameter captures the interval of time between a kernel invocation and the signaling of its completion to the driver. Like worst-case CPU execution, this parameter is unique to each task and is dominated by the GPU kernel execution time plus lesser communication latencies. Preliminary work  has been done to upper-bound GPU kernel execution time, though empirical tests are sufficient for many soft real-time systems. For tasks that do not use the GPU, si = 0. The utilization of task Ti is given by ui = ei=pi and the system utilization is given by

As stated, our goal is to maximize system utilization while supporting soft real-time constraints. Unfortunately, due to a GPU’s I/O-based interface, techniques for heterogeneous systems [11, 17, 12] do not immediately apply. However, as noted earlier, previous work [16] has shown that G-EDF can ensure bounded tardiness in ordinary multiprocessor systems (without a GPU) without system utilization constraints (provided the system is not overutilized). Thus, it is the primary scheduling algorithm considered in this paper. G-EDF is a global scheduler, meaning that jobs share a single ready queue and can migrate between processors. G-EDF prioritizes work by job deadline, scheduling jobs with the earliest deadlines first.