6.7 Model-Based Design and Verification of Real-Time Systems

Time	Label	Presentation Title Authors
11:00	6.7.1	NEAR-OPTIMAL DEPLOYMENT OF DATAFLOW APPLICATIONS ON MANY-CORE PLATFORMS WITH REAL-TIME GUARANTEES Speaker: Stefanos Skalistis, École Polytechnique Fédérale de Lausanne (EPFL), GR Authors: Stefanos Skalistis and Alena Simalatsar, EPFL, CH Abstract Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of interferences on shared resources, thus introducing a cyclic dependency. Moreover, WCET is still an over-approximation of the Actual Execution Time (AET), thus leaving room for run-time optimisation. In this paper we introduce an offline/online optimisation approach. In the offline phase, we first break the cyclic dependency and acquire safe and near-optimal solutions for tasks partitioning/placement, mapping, scheduling and buffer allocation. Then, we tighten the WCETs and update the scheduling function accordingly. In the online phase we introduce a safe distributed readjustment of the offline schedule, based on the AET. Experiments on a Kalray MPPA-256 platform show a tightening of the guaranteed latency up to 46% in the offline phase, and 41% latency reduction in the online phase. In total, we achieve more than 50% of latency reduction. Download Paper (PDF; Only available from the DATE venue WiFi)
11:30	6.7.2	SIMULATING PREEMPTIVE SCHEDULING WITH TIMING-AWARE BLOCKS IN SIMULINK Speaker and Author: Andreas Naderlinger, University of Salzburg, AT Abstract This paper introduces an extension of the modeling and simulation environment MATLAB/Simulink. It enables control and system engineers to consider software execution times, as well as the effects of scheduling and preemption inside software-in-the-loop (SIL) simulations. To this end, we present the concept of a Simulink block whose execution lasts for a finite amount of simulation time. During this time, the simulation engine continues to update the plant or other blocks with outputs that have already been calculated by the block. Execution time information is assumed to be known (or based on some random distribution). Source-level annotating the control software with target specific timing information enables a fine-grained and even a control-flow dependent simulation of the block. We outline the required synchronization with the simulation engine of Simulink. This timing-aware block consumes simulation time in the same sense as a task consumes CPU time on a target. We describe a mechanism to execute a set of such blocks with (potentially cyclic) data dependencies with a static priority scheduler inside Simulink, including support for preemption. The presented approach permits a development process, where a typical time invariant and platform agnostic model is incrementally transformed into a platform-specific one that makes the simulation more realistic. Download Paper (PDF; Only available from the DATE venue WiFi)
12:00	6.7.3	ONLINE WORKLOAD MONITORING WITH THE FEEDBACK OF ACTUAL EXECUTION TIME FOR REAL-TIME SYSTEMS Speaker: Biao Hu, Tech. Univ. Muenchen TUM, DE Authors: Biao Hu¹, Kai Huang², Gang Chen¹, Long Cheng¹ and Alois Knoll¹ ¹Tech. Univ. Muenchen TUM, DE; ²Sun Yat-Sen University, CN Abstract Guaranteeing the system workload within design bounds is a basic requirement for a real-time system. Design-time bounds are usually based on worst-case activation patterns and worst-case execution time. While using the worst-case assumptions for online monitoring can guarantee the system safety, it also introduces unexplored slacks due to tasks consuming less than their worst-case execution times. In this paper, we introduce a monitoring scheme with the feedback of actual execution time for real-time systems. By using this runtime feedback instead of offline assumptions, this monitoring scheme can accept events that are considered as violations offline, and thereby improve the system utilization. In the experiments of both MATLAB simulation and MicroC/OS-II running in a softcore processor implemented on an FPGA, different probability distributions of actual execution time are used in analyzing how much the benefit can be gained from the feedback scheme. Download Paper (PDF; Only available from the DATE venue WiFi)
12:30	IP3-6, 607	LATENCY ANALYSIS OF HOMOGENEOUS SYNCHRONOUS DATAFLOW GRAPHS USING TIMED AUTOMATA Speaker: Guus Kuiper, University of Twente, NL Authors: Guus Kuiper¹ and Marco Bekooij² ¹University of Twente, NL; ²University of Twente + NXP semiconductors, NL Abstract There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow (HSDF) with Auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected (HSDFa) models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models. Download Paper (PDF; Only available from the DATE venue WiFi)
12:30		End of session Lunch Break in Garden Foyer Keynote Lecture session 7.0 in "Garden Foyer" 1350 - 1420 Lunch Break in the Garden Foyer On all conference days (Tuesday to Thursday), a buffet lunch will be offered in the Garden Foyer, in front of the session rooms. Kindly note that this is restricted to conference delegates possessing a lunch voucher only. When entering the lunch break area, delegates will be asked to present the corresponding lunch voucher of the day. Once the lunch area is being left, re-entrance is not allowed for the respective lunch.

Time

Label

Presentation Title
Authors

11:00

6.7.1

NEAR-OPTIMAL DEPLOYMENT OF DATAFLOW APPLICATIONS ON MANY-CORE PLATFORMS WITH REAL-TIME GUARANTEES
Speaker:
Stefanos Skalistis, École Polytechnique Fédérale de Lausanne (EPFL), GR
Authors:
Stefanos Skalistis and Alena Simalatsar, EPFL, CH
Abstract
Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of interferences on shared resources, thus introducing a cyclic dependency. Moreover, WCET is still an over-approximation of the Actual Execution Time (AET), thus leaving room for run-time optimisation. In this paper we introduce an offline/online optimisation approach. In the offline phase, we first break the cyclic dependency and acquire safe and near-optimal solutions for tasks partitioning/placement, mapping, scheduling and buffer allocation. Then, we tighten the WCETs and update the scheduling function accordingly. In the online phase we introduce a safe distributed readjustment of the offline schedule, based on the AET. Experiments on a Kalray MPPA-256 platform show a tightening of the guaranteed latency up to 46% in the offline phase, and 41% latency reduction in the online phase. In total, we achieve more than 50% of latency reduction.
Download Paper (PDF; Only available from the DATE venue WiFi)

11:30

6.7.2

SIMULATING PREEMPTIVE SCHEDULING WITH TIMING-AWARE BLOCKS IN SIMULINK
Speaker and Author:
Andreas Naderlinger, University of Salzburg, AT
Abstract
This paper introduces an extension of the modeling and simulation environment MATLAB/Simulink. It enables control and system engineers to consider software execution times, as well as the effects of scheduling and preemption inside software-in-the-loop (SIL) simulations. To this end, we present the concept of a Simulink block whose execution lasts for a finite amount of simulation time. During this time, the simulation engine continues to update the plant or other blocks with outputs that have already been calculated by the block. Execution time information is assumed to be known (or based on some random distribution). Source-level annotating the control software with target specific timing information enables a fine-grained and even a control-flow dependent simulation of the block. We outline the required synchronization with the simulation engine of Simulink. This timing-aware block consumes simulation time in the same sense as a task consumes CPU time on a target. We describe a mechanism to execute a set of such blocks with (potentially cyclic) data dependencies with a static priority scheduler inside Simulink, including support for preemption. The presented approach permits a development process, where a typical time invariant and platform agnostic model is incrementally transformed into a platform-specific one that makes the simulation more realistic.
Download Paper (PDF; Only available from the DATE venue WiFi)

12:00

6.7.3

ONLINE WORKLOAD MONITORING WITH THE FEEDBACK OF ACTUAL EXECUTION TIME FOR REAL-TIME SYSTEMS
Speaker:
Biao Hu, Tech. Univ. Muenchen TUM, DE
Authors:
Biao Hu¹, Kai Huang², Gang Chen¹, Long Cheng¹ and Alois Knoll¹
¹Tech. Univ. Muenchen TUM, DE; ²Sun Yat-Sen University, CN
Abstract
Guaranteeing the system workload within design bounds is a basic requirement for a real-time system. Design-time bounds are usually based on worst-case activation patterns and worst-case execution time. While using the worst-case assumptions for online monitoring can guarantee the system safety, it also introduces unexplored slacks due to tasks consuming less than their worst-case execution times. In this paper, we introduce a monitoring scheme with the feedback of actual execution time for real-time systems. By using this runtime feedback instead of offline assumptions, this monitoring scheme can accept events that are considered as violations offline, and thereby improve the system utilization. In the experiments of both MATLAB simulation and MicroC/OS-II running in a softcore processor implemented on an FPGA, different probability distributions of actual execution time are used in analyzing how much the benefit can be gained from the feedback scheme.
Download Paper (PDF; Only available from the DATE venue WiFi)

12:30

IP3-6, 607

LATENCY ANALYSIS OF HOMOGENEOUS SYNCHRONOUS DATAFLOW GRAPHS USING TIMED AUTOMATA
Speaker:
Guus Kuiper, University of Twente, NL
Authors:
Guus Kuiper¹ and Marco Bekooij²
¹University of Twente, NL; ²University of Twente + NXP semiconductors, NL
Abstract
There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow (HSDF) with Auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected (HSDFa) models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.
Download Paper (PDF; Only available from the DATE venue WiFi)

12:30

End of session
Lunch Break in Garden Foyer

Keynote Lecture session 7.0 in "Garden Foyer" 1350 - 1420

Lunch Break in the Garden Foyer
On all conference days (Tuesday to Thursday), a buffet lunch will be offered in the Garden Foyer, in front of the session rooms. Kindly note that this is restricted to conference delegates possessing a lunch voucher only. When entering the lunch break area, delegates will be asked to present the corresponding lunch voucher of the day. Once the lunch area is being left, re-entrance is not allowed for the respective lunch.