Enforcing Deadlines for Skeleton-based Parallel Programming

Paul Metzger, Murray Cole, Christian Fensch, Marco Aldinucci, Enrico Bini

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

High throughput applications with real-time guarantees are increasingly relevant. For these applications, parallelism must be exposed to meet deadlines. Directed Acyclic Graphs (DAGs) are a popular and very general application model that can capture any possible interaction among threads. However, we argue that by constraining the application structure to a set of composable “skeletons”, at the price of losing some generality w.r.t. DAGs, the following advantages are gained: (i) a finer model of the application enables tighter analysis, (ii) specialised scheduling policies are applicable, (iii) programming is simplified, (iv) specialised implementation techniques can be exploited transparently, and (v) the program can be automatically tuned to minimise resource usage while still meeting its hard deadlines.

As a first step towards a set of real-time skeletons we conduct a case study with the job farm skeleton and the hard realtime XMOS xCore-200 microcontroller. We present an analytical framework for job farms that reduces the number of required cores by scheduling jobs in batches, while ensuring that deadlines are still met. Our experimental results demonstrate that batching reduces the minimum sustainable period by up to 22%, leading to a reduced number of required cores. The framework chooses the best parameters in 83% of cases and never selects parameters that cause deadline misses. Finally, we show that the overheads introduced by the skeleton abstraction layer are negligible.
Original languageEnglish
Title of host publication2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)978-1-7281-5499-2
ISBN (Print)978-1-7281-5500-5
Publication statusPublished - 10 Jun 2020
Event26th IEEE Real-Time and Embedded Technology and Applications Symposium - Sydney, Australia
Duration: 21 Apr 202024 Apr 2020
Conference number: 26

Publication series

ISSN (Print)1545-3421
ISSN (Electronic)2642-7346


Seminar26th IEEE Real-Time and Embedded Technology and Applications Symposium
Abbreviated titleRTAS20
Internet address


Dive into the research topics of 'Enforcing Deadlines for Skeleton-based Parallel Programming'. Together they form a unique fingerprint.

Cite this