Techniques optimizing the number of processors to schedule multi-threaded tasks

Geoffrey Nelissen, Vandy Berten, Joël Goossens, Dragomir Milojevic

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

57 Citations (Scopus)

Abstract

These last years, we have witnessed a dramatic increase in the number of cores available in computational platforms. Concurrently, a new coding paradigm dividing tasks into smaller execution instances called threads, was developed to take advantage of the inherent parallelism of multiprocessor platforms. However, only few methods were proposed to efficiently schedule hard real-time multi-threaded tasks on multiprocessor. In this paper, we propose techniques optimizing the number of processors needed to schedule such sporadic parallel tasks with constrained deadlines. We first define an optimization problem determining, for each thread, an intermediate (artificial) deadline minimizing the number of processors needed to schedule the whole task set. The scheduling algorithm can then schedule threads as if they were independent sequential sporadic tasks. The second contribution is an efficient and nevertheless optimal algorithm that can be executed online to determine the thread's deadlines. Hence, it can be used in dynamic systems were all tasks and their characteristics are not known a priori. We finally prove that our techniques achieve a resource augmentation bound of 2 when the threads are scheduled with algorithms such as U-EDF, PD2, LLREF, DP-Wrap, etc.

Original languageEnglish
Title of host publicationProceedings of the 24th Euromicro Conference on Real-Time Systems, ECRTS 2012
Pages321-330
Number of pages10
DOIs
Publication statusPublished - 25 Sep 2012
Externally publishedYes
Event24th Euromicro Conference on Real-Time Systems, ECRTS 2012 - Pisa, Italy
Duration: 10 Jul 201213 Jul 2012

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070

Conference

Conference24th Euromicro Conference on Real-Time Systems, ECRTS 2012
CountryItaly
CityPisa
Period10/07/1213/07/12

Fingerprint Dive into the research topics of 'Techniques optimizing the number of processors to schedule multi-threaded tasks'. Together they form a unique fingerprint.

Cite this