Name
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, PD^2, LLREF, DP-Wrap, etc. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/ECRTS.2012.37 | ECRTS |
Keywords | Field | DocType |
multi-threaded tasks,multiprocessor platform,scheduling algorithm,sporadic parallel task,independent sequential sporadic task,computational platform,hard real-time multi-threaded task,inherent parallelism,optimal algorithm,dramatic increase,dynamic system,schedules,optimization,optimization problem,multi threading,silicon,instruction sets,parallel processing,computational modeling | Multithreading,Multiprocessor scheduling,Instruction set,Computer science,Scheduling (computing),Parallel computing,Thread (computing),Real-time computing,Multiprocessing,Schedule,Optimization problem,Distributed computing | Conference |
ISSN | Citations | PageRank |
1068-3070 | 32 | 1.37 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Geoffrey Nelissen | 1 | 190 | 21.77 |
| Vandy Berten | 2 | 153 | 10.77 |
| Joël Goossens | 3 | 666 | 49.22 |
| Dragomir Milojevic | 4 | 111 | 12.25 |