11.7 Extending Scheduling Schemes
Date: Thursday 28 March 2019
Time: 14:00 - 15:30
Location / Room: Room 7
Chair:
Marco Di Natale, Scuola Superiore Sant’Anna of Pisa, IT
Co-Chair:
Mitra Nasri, TU Delft, NL
This session presents papers with generalization of fixed-priority, global EDF, and applications to synchronous data flows
| Time | Label | Presentation Title Authors |
|---|---|---|
| 14:00 | 11.7.1 | ANALYZING 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:30 | 11.7.2 | SIMPLE 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:00 | 11.7.3 | HARD 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:30 | End of session Coffee Break in 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
|
DATE Newsletter
Stay informed on our latest news!
DATE Smartphone App
available at
In the Whova App search for "DATE 2019" in the event list and use the Password: "DATE".
Visit us at DATE 2019
