REGAIN

Real-time scheduling on general purpose graphics processor units

	FCOMP-01-0124-FEDER-020447 PTDC/EIA-CCO/118080/2010 40 months (Apr 2012 to Jul 2015)
Summary:	Among all processors sold today, 98% are used in embedded computer systems; therefore catering to this segment is of utmost importance. Moreover, there is a persistent trend in computing that techniques originally developed at the high-end (pipelining, cache-memories, instruction-level parallelism) later propagate to embedded computer systems. Graphics processors are the next technology to do this transition. Graphics processors were originally used only for graphics but have evolved significantly during the recent decade as witnessed by the following. First, the performance of graphics processor units has followed the exponential advances in semiconductor density (Moore´s law) whereas the performance of normal processors (CPUs) has not. Second, graphics processor units are increasingly integrated with a normal processor on a single chip for use both in high and low-end computer systems. Intel Sandybridge, AMD Fusion and NVIDIA Tegra 2 exemplify this. Third, today’s graphics processors can multitask and offer fast context switching (25 microseconds) between different applications. Fourth, graphics processors are today able to perform general-purpose computations, using macros in C-programs; this allows normal software developers to use graphics processors for data-parallel programs. Therefore, this type of processor can be viewed as a multicore processor; it has come to be called General Purpose Graphics Processor Unit (GPGPU) or simply GPU (the phenomenon is called GPU computing). Because of its attractive performance, the GPGPU will become the workhorse in virtually all computer systems. Even so, embedded systems pose specific challenges: Embedded computer systems interact with their physical world. For example, a computer which autonomously drives a car (GPUs are intended for this) must not only compute the correct actuation signals (for example steering) but must also do so at the right time in order to drive safely. The real-time systems research community has created a comprehensive toolkit involving (i) algorithms for run-time scheduling of tasks with deadlines and (ii) proof methods (called schedulability tests) for proving before run-time, using a given scheduling algorithm at run-time and given a model of the workload, that all deadlines of tasks are met at run-time. This toolkit (rate-monotonic and earliest-deadline-first scheduling and analysis) is currently well-established for uniprocessors. Scientific work is currently underway for transferring these results to multiprocessors; multicores in particular. Yet, the scientific community in the area of real-time systems offers no scheduling theory for GPGPUs and creating such a theory is non-trivial. Considering the importance of GPGPUs and their expected importance in embedded systems in the future and considering the current lack of scheduling theory for GPGPUs, there is a strong need to create a scheduling theory for GPGPUs. Therefore, this project will create a real-time scheduling theory for GPGPUs. This theory will offer (i) a model suited for describing real-time scheduling on GPGPUs, (ii) algorithms for run-time scheduling of tasks using GPGPUs and (iii) algorithms for proving, before run-time, that tasks using GPGPUs meet their deadlines. This project will also test the theory on commercially available GPGPUs.
Funding:	Global: 139KEUR, CISTER: 139KEUR
Sponsors:
Partners:
Main Partners:
Main Partners:
Contact Person at CISTER:	Konstantinos Bletsas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conference or Workshop Papers/Talks

The Generalized Multiprocessor Periodic Resource Interface Model for Hierarchical Multiprocessor Scheduling HURRAY-TR-121002
Artem Burmyakov, Enrico Bini, Eduardo Tovar

ABSTRACT