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: | |
| Contact Person at CISTER: | Konstantinos Bletsas |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Journal Papers
Task partitioning and priority assignment for distributed hard real-time systems CISTER-TR-151001
Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, Luis Miguel PinhoJournal of Computer and System Sciences (JCSS), Elsevier. Dec 2015, Volume 81, Issue 8, pp 1542-1555.
Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, Luis Miguel PinhoJournal of Computer and System Sciences (JCSS), Elsevier. Dec 2015, Volume 81, Issue 8, pp 1542-1555.
Conference or Workshop Papers/Talks
Semi-Partitioned Scheduling of Fork-Join Tasks using Work-Stealing CISTER-TR-151007
Cláudio Maia, Patrick Meumeu Yomsi, Luis Miguel Nogueira, Luis Miguel Pinho13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC 2015). 21 to 23, Oct, 2015, Session W1-A: Multiprocessing and Multicore Architectures. Porto, Portugal.
Cláudio Maia, Patrick Meumeu Yomsi, Luis Miguel Nogueira, Luis Miguel Pinho13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC 2015). 21 to 23, Oct, 2015, Session W1-A: Multiprocessing and Multicore Architectures. Porto, Portugal.
PDFOverhead-aware schedulability evaluation of semi-partitioned real-time schedulers CISTER-TR-150402
Pedro Souto, Paulo Baltarejo Sousa, Robert Davis, Konstantinos Bletsas, Eduardo TovarIEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015). 19 to 21, Aug, 2015. Hong Kong, China.
Pedro Souto, Paulo Baltarejo Sousa, Robert Davis, Konstantinos Bletsas, Eduardo TovarIEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015). 19 to 21, Aug, 2015. Hong Kong, China.
Hard real-time multiprocessor scheduling resilient to core failures CISTER-TR-151105
Borislav Nikolic, Konstantinos Bletsas, Stefan M. Petters21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015). 19 to 21, Aug, 2015, pp 122-131. Hong Kong, China.
Borislav Nikolic, Konstantinos Bletsas, Stefan M. Petters21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015). 19 to 21, Aug, 2015, pp 122-131. Hong Kong, China.
Online Admission of Parallel Real-Time Tasks CISTER-TR-150701
Cláudio Maia, Luis Miguel Nogueira, Luis Miguel Pinho6th Real-Time Scheduling Open Problems Seminar (RTSOPS 2015). 7, Jul, 2015. Lund, Sweden.
Cláudio Maia, Luis Miguel Nogueira, Luis Miguel Pinho6th Real-Time Scheduling Open Problems Seminar (RTSOPS 2015). 7, Jul, 2015. Lund, Sweden.
An Execution Model for Fine-Grained Parallelism in Ada CISTER-TR-150403
Luis Miguel Pinho, Brad Moore, Stephen Michell, S. Tucker Taft20th International Conference on Reliable Software Technologies - Ada-Europe 2015 (Ada-Europe 2015). 25 to 29, Jun, 2015. Madrid, Spain.Best Paper Award.
Luis Miguel Pinho, Brad Moore, Stephen Michell, S. Tucker Taft20th International Conference on Reliable Software Technologies - Ada-Europe 2015 (Ada-Europe 2015). 25 to 29, Jun, 2015. Madrid, Spain.Best Paper Award.
Holistic Analysis for Fork-Join Distributed Tasks supported by the FTT-SE Protocol CISTER-TR-150507
Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, Paulo Pedreiras, Luis Miguel Pinho11th IEEE World Conference on Factory Communication Systems (WFCS 2015). 27 to 29, May, 2015, TII-SS-2: Scheduling and Performance Analysis. Palma de Mallorca, Spain.
Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, Paulo Pedreiras, Luis Miguel Pinho11th IEEE World Conference on Factory Communication Systems (WFCS 2015). 27 to 29, May, 2015, TII-SS-2: Scheduling and Performance Analysis. Palma de Mallorca, Spain.
Real-Time Fine-Grained Parallelism in Ada CISTER-TR-150404
Luis Miguel Pinho, Brad Moore, Stephen Michell, S. Tucker TaftInternational Real-Time Ada Workshop (IRTAW 2015). 20 to 22, Apr, 2015. Pownal, U.S.A..
Luis Miguel Pinho, Brad Moore, Stephen Michell, S. Tucker TaftInternational Real-Time Ada Workshop (IRTAW 2015). 20 to 22, Apr, 2015. Pownal, U.S.A..
Towards Certifiable Multicore-based Platforms for Avionics CISTER-TR-150702
Muhammad Ali Awan, Patrick Meumeu Yomsi, Konstantinos Bletsas, Vincent Nélis, Eduardo Tovar, Pedro SoutoWork in Progress Session, 21st IEEE Real-Time and Embedded Techonology and Applications Symposium (RTAS 2015). 13 to 16, Apr, 2015, pp 27-28. Seattle, U.S.A..
Muhammad Ali Awan, Patrick Meumeu Yomsi, Konstantinos Bletsas, Vincent Nélis, Eduardo Tovar, Pedro SoutoWork in Progress Session, 21st IEEE Real-Time and Embedded Techonology and Applications Symposium (RTAS 2015). 13 to 16, Apr, 2015, pp 27-28. Seattle, U.S.A..
A Multi-DAG Model for Real-Time Parallel Applications with Conditional Execution CISTER-TR-141207
José Fonseca, Vincent Nélis, Gurulingesh Raravi, Luis Miguel PinhoThe 30th ACM/SIGAPP Symposium On Applied Computing (SAC 2015). 13 to 17, Apr, 2015, Embedded Systems. Salamanca, Spain.
José Fonseca, Vincent Nélis, Gurulingesh Raravi, Luis Miguel PinhoThe 30th ACM/SIGAPP Symposium On Applied Computing (SAC 2015). 13 to 17, Apr, 2015, Embedded Systems. Salamanca, Spain.
Conference or Workshop Posters/Demos
A module for the FTT-SE protocol in ns-3 CISTER-TR-150407
Fábio Oliveira, Ricardo Garibay-Martínez, Tiago Cerqueira, Michele Albano, Luis Lino FerreiraDemo in Workshop on ns-3 (WNS3 2015). 13 to 14, May, 2015. Castelldefels, Spain.
Fábio Oliveira, Ricardo Garibay-Martínez, Tiago Cerqueira, Michele Albano, Luis Lino FerreiraDemo in Workshop on ns-3 (WNS3 2015). 13 to 14, May, 2015. Castelldefels, Spain.
Towards the Combination of Work-Stealing and Semi-Partitioned Scheduling for Parallel Tasks CISTER-TR-151103
Cláudio Maia, Luis Miguel Nogueira, Patrick Meumeu Yomsi, Luis Miguel PinhoPoster presented in Work in Progress Session, 28th GI/ITG International Conference on Architecture of Computing Systems (ARCS 2015). 24 to 26, Mar, 2015. Porto, Portugal.
Cláudio Maia, Luis Miguel Nogueira, Patrick Meumeu Yomsi, Luis Miguel PinhoPoster presented in Work in Progress Session, 28th GI/ITG International Conference on Architecture of Computing Systems (ARCS 2015). 24 to 26, Mar, 2015. Porto, Portugal.