11.7 Extending Scheduling Schemes

Printer-friendly version PDF version

Date: Thursday, March 28, 2019
Time: 14:00 - 15:30
Location / Room: Room 7

Chair:
Marco Di Natale, Scuola Superiore Sant’Anna of Pisa, IT, Contact Marco Di natale

Co-Chair:
Mitra Nasri, TU Delft, NL, Contact Mitra Nasri

This session presents papers with generalization of fixed-priority, global EDF, and applications to synchronous data flows

TimeLabelPresentation Title
Authors
14:0011.7.1ANALYZING GEDF SCHEDULING FOR PARALLEL REAL-TIME TASKS WITH ARBITRARY DEADLINES
Speaker:
Xu Jiang, The Hong Kong Polytechnic University, HK
Authors:
Xu Jiang1, Nan Guan1, Di Liu2 and Weichen Liu3
1The Hong Kong Polytechnic University, HK; 2Yunnan University, CN; 3Nanyang Technological University, SG
Abstract
Real-time and embedded systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the computation capacity of hardware. Recently much work has been done on the scheduling of parallel real-time tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this paper, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task, which not only outperform the state-of-the-art in general evidenced by empirical evaluation, but also guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5). The proposed analysis techniques are also extended to and evaluated with the case of multiple DAG tasks using the federated scheduling approach.

Download Paper (PDF; Only available from the DATE venue WiFi)
14:3011.7.2SIMPLE AND GENERAL METHODS FOR FIXED-PRIORITY SCHEDULABILITY IN OPTIMIZATION PROBLEMS
Speaker:
Paolo Pazzaglia, Scuola Superiore Sant Anna, Pisa, IT
Authors:
Paolo Pazzaglia, Alessandro Biondi and Marco Di Natale, Scuola Superiore Sant'Anna, IT
Abstract
This paper presents a set of sufficient-only, but accurate schedulability tests for fixed-priority scheduling. The tests apply to the general case of scheduling with constrained deadline where tasks can incur in blocking times, be subject to release jitters, activated with fixed offsets, or involved in transactions with other tasks. The proposed tests come in a linear closed-form with a number of conditions polynomial in the number of tasks. All tests are targeted for use when encoding schedulability constraints within Mixed-Integer Linear Programming for the purpose of optimizing real-time systems (e.g., to address task partitioning in a multicore system). The tests are evaluated with a large-scale experimental study based on synthetic workload, revealing a failure rate (with respect to the state-of-the-art reference tests) of less than 1% in average, and at most of 2% in a very small number of limit-case configurations.

Download Paper (PDF; Only available from the DATE venue WiFi)
15:0011.7.3HARD REAL-TIME SCHEDULING OF STREAMING APPLICATIONS MODELED AS CYCLIC CSDF GRAPHS
Speaker:
Sobhan Niknam, Leiden University, NL
Authors:
Sobhan Niknam, Peng Wang and Todor Stefanov, Leiden University, NL
Abstract
Recently, it has been shown that the classical hard real-time scheduling theory can be applied to streaming applications modeled as acyclic Cyclo-Static Dataflow (CSDF) graphs. However, many streaming applications are modeled as cyclic CSDF graphs, thus they are not supported by such scheduling theory. Therefore, in this paper, we propose an approach which enables to apply the classical hard real-time scheduling theory on streaming applications modeled as cyclic CSDF graphs. The proposed approach converts each task in a cyclic CSDF graph to a constrained-deadline periodic task. This conversion enables the utilization of many hard real-time scheduling algorithms which offer properties such as temporal isolation and fast calculation of the required number of processors for scheduling the tasks. We evaluate the performance of our approach in comparison to existing scheduling approaches. The evaluation, on a set of real-life benchmarks, demonstrates that our approach can schedule the tasks in an application, modeled as a cyclic CSDF graph, with guaranteed throughput equal or comparable to the throughput obtained by existing scheduling approaches while providing hard real-time guarantees for every task in the application thereby enabling temporal isolation among concurrently running tasks/applications on a multi-processor platform.

Download Paper (PDF; Only available from the DATE venue WiFi)
15:30End of session
Coffee Break in Exhibition Area



Coffee Breaks in the Exhibition Area

On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area.

Lunch Breaks (Lunch Area)

On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the Lunch Area to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area.

Tuesday, March 26, 2019

Wednesday, March 27, 2019

Thursday, March 28, 2019