[image] [image] Ressource protégée - Inria - Institut national de recherche en sciences et technologies du numérique [Accéder directement au contenu](#)

[image] [image]

* [Documentation](#)

* FR
  Français (FR)

* Anglais (EN)
  Se connecter

* [Portail HAL Inria](#)

* Recherche
  Loading...

## Recherche avancée

Information de documents

Titres

○ Titres

○ Sous-titre

○ Titre de l'ouvrage

○ Titre du volume (Série)

○ Champ de recherche par défaut (multicritères) + texte intégral des PDF

○ Résumé

○ Texte intégral indexé des documents PDF

○ Mots-clés

○ Type de document

○ Sous-type de document

○ Tous les identifiants du document

○ Identifiant HAL du dépôt

○ Langue du document (texte)

○ Pays (Texte)

○ Ville

○ À paraître (true ou false)

Ajouter
<figure><img src="image_1.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
## Auteur

### Auteur (multicritères)

○ Auteur (multicritères)

○ Auteur : Nom complet

○ Auteur : Nom de famille

○ Auteur : Prénom

○ Auteur : Complément de nom, deuxième prénom

○ Auteur : Organisme payeur

○ Auteur : IdHal (chaîne de caractères)

○ Auteur : Fonction

○ Auteur : personID (entier)

○ Auteur : Identifiant de l'organisme payeur

○ Auteur : Identifiant de la structure

○ Directeur de thèse

○ Éditeur

○ Éditeur scientifique

○ Éditeur de la série

## Ajouter

### Structure

### Structure (multicritères)

○ Structure (multicritères)

○ Structure : Acronyme

○ Structure : Nom

○ Structure : Code

○ Structure : Pays

○ Structure : Type

○ Structure : État dans le référentiel

○ Structure : Identifiant HAL de la structure

○ Structure/équipe de recherche : Pays

○ Structure/regroupement d'équipes : Pays

○ Structure/laboratoire : Pays

○ Structure/regroupement de laboratoires : Pays

○ Structure/institution : Pays

○ Structure/regroupement d'institutions : Pays

## Ajouter
# Improving Estimations for Latencies of
Cause-Effect Chains

Max J. Friese<fnref n="1" />,<fnref n="2" />, Thorsten Ehlers<fnref n="1" />, and Dirk Nowotka<fnref n="1" />

**Abstract.** The reaction of a cyber-physical system to a stimulus typically requires the processing of several tasks. A task in this context is an aggregation of different working steps, where each step comprises a dedicated piece of software called runnable. The delay between stimulus and reaction depends of the interaction of the software pieces and is subject to timing constraints. Therefore, tight bounds on the delays are needed at any stage of the engineering processes. We present an extension for an approach to estimate such bounds more precisely than previously possible.

**Keywords:** cyber-physical systems, cause-effect chains, analytical models, formal estimations, end-to-end latencies

## 1 Introduction

For many systems, like cars, safety and comfort features rely on the seamless processing of physical values by electronic control units (ECUs). Those values are captured by sensors and the collected data is used to control actuators to the user's needs. Systems where physical data is processed and physical processes are monitored and controlled by networks of ECUs are called cyber-physical systems (CPS) [15]. In many cases the time for such a system to react to an input is subject to constraints. Thus, a performance analysis with respect to different latencies is an important part of system engineering. The complexity of performance analysis increases with the ongoing digitalization of technical systems.

Constraints on the temporal behavior of CPS usually exists between a physical stimulus and a physical reaction. To estimate an end-to-end latency, the processing between stimulus and reaction is divided in different segments. One of these segments is the software running on the ECUs. The temporal behavior of the software can be determined in several ways. It can be measured in the end-product or with testbed hardware, determined with simulation or estimated by analytical approaches as described in [19]. For measurements and simulations no formal abstraction of the system is needed. The temporal behavior is analyzed using existing parts of the system. However, choosing the right measurement

<footnote n="1">¹ Department of Computer Science, Kiel University, Germany,
{mjf,the,dn}@informatik.uni-kiel.de,</footnote>

<footnote n="2">² Mercedes-Benz Car Development, Sindelfingen, Germany
max.jonas.friese@daimler.com</footnote>
Autres

Champ de recherche par défaut (multicritères)

○ <u>Champ de recherche par défaut (multicritères)</u>

○

○ <u>Revues (multicritères)</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Titre abrégé</u>

○ <u>Revue : Titre</u>

○ <u>Revue : Identifiant interne</u>

○ <u>Revue : Date de début de publication</u>

○ <u>Revue : ISSN électronique</u>

○ <u>Revue : ISSN</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Couleur dans SHERPA/RoMEO</u>

○ <u>Revue : État dans le référentiel</u>

○

○ <u>Colloque (multicritères)</u>

○ <u>Colloque : Titre</u>

○ <u>Colloque : Organisateur</u>

○ <u>Colloque : date de début (Année)</u>

○ <u>Colloque : date de fin (Année)</u>

○ <u>Conférence invitée (oui/non)</u>

○

○ <u>Projets ANR (multicritères)</u>

○ <u>Projet ANR : Acronyme</u>

○ <u>Projet ANR : Acronyme du programme</u>

○ <u>Projet ANR : Code décision (référence)</u>

○ <u>Projet ANR : Nom</u>

○ <u>Projet ANR : Identifiant interne</u>

○ <u>Projet ANR : État dans le référentiel</u>

○

○ <u>Projets européens (multicritères)</u>

○ <u>Projet européen : Acronyme</u>

○ <u>Projet européen : Identifiant de l'appel à projet</u>

○ <u>Projet européen : Référence</u>

○ <u>Projet européen : Nom</u>

○ <u>Projet européen : Date de fin</u>

○ <u>Projet européen : Financement</u>

○ <u>Projet européen : Date de début</u>
scenarios or simulation stimuli to definitely observe the worst-case behavior is
known to be a hard problem [8]. Therefore, a disadvantage of measurement-based
analyses is the lack of guarantees for the measured values to be safe bounds.

On the contrary, approaches based on formal analysis give guarantees for
the calculated bounds. These guarantees come with the price of an overesti-
mation due to assumptions and abstractions in the modeling process. However,
overestimations can be reduced by making use of more detailed system models.
More details inevitably lead to more complexity, resulting in greater computa-
tional effort. This results in a trade-off between precision and computing time.
The presented approach provides a new level of detail while breaking the time-
precision trade-off.

1.1 Problem Statement

In this paper we focus on systems in which data propagation through the software
can be described in terms of so-called cause-effect chains. Such a chain is a
sequence of tasks where he successor of a task reads at least signal value produced
by its successor. A task can occur multiple times within such a chain and a system
function might have multiple associated chains.

The temporal constraints on cause-effect chains can be divided in two categories. One is the delay between the arrival of an input and the reaction of the last task, which is called *response time* (or *reaction time*). Another constraint is *data age* which describes the fact that an output may depend on old input values, e.g. when the task writing a signal is activated less frequent than the task reading the signal. The different semantics for latencies are depicted in Figure 1 and are described with more detail in [5]. The first path, starting at the second instance of *Task A* shows the worst case response time for the chain *Task A* → *Task B* → *Task C* → *Task A*. The second path, starting at the 6th instance of *Task A* shows its data age. Both, the data age and response time of a chain, mainly depend on the possible relative offsets between task instances on the chain and their read and write intervals. The latter depends on the communication model of the task and its core execution time. Furthermore, task instances may influence other task instances when competing for computation time, imposing a delay on the response of the single task.

Safe and tight bounds for both types of constraints and various types of chains
are needed at any stage of the development process, e.g. to evaluate the impact of
changes in the system or verify the final system against timing requirements. The
presented approach is the first formal estimation approach yielding safe upper
bounds while allowing an analysis on intra-task level and supporting the range
of activation models, communication models, and further system parameters as
described below.

## 1.2 Our Contribution

In this paper we demonstrate improvements and extensions of the approach
presented in [6].
○ Projet européen : État dans le référentiel

○ Projet européen : Identifiant interne

○

○ Date de production : année

○ Date de mise en ligne : année

○ Date de publication : année

○ Date d'écriture : année

○ Date de modification du dépôt : année

○ Date de dépôt : année

○ Date de publication électronique : année

○

○ Collection HAL (multicritères)

○ Collection HAL : catégorie

○ Collection HAL : Code

○ Collection HAL : Nom

○ Collection HAL : Identifiant interne

○

○ Identifiant interne du contributeur/déposant

○ Nom complet du contributeur/déposant

○

○ Domaines

○ Domaine primaire

○ Domaine racine

○ Sous-domaine niveau 1

○ Sous-domaine niveau 2

○ Sous-domaine niveau 3

○

○ Statut du document

○ Version du document

○ Type de dépôt

○ Type de document

○ ISBN

○ Numéro - référence

○ Identifiant DOI

○

○ Classification

○ Audience

○ Vulgarisation

○ Comité de lecture - texte (oui ou non)

○ Actes de colloque
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Response Time (blue) and Data Age (orange) of the Chain *Task A → Task B → Task C → Task A*</figcaption></figure>

In particular,

- The authors claim that best- and worst-case execution times can easily be integrated in their model. This is true, however, it significantly increases the runtime of the analysis. We show that this increase can be minimized by adding additional constraints. Furthermore, we demonstrate that the model can also be adapted for computing data ages.

- Additionally to incorporating execution times, a further step towards precision can be made by also looking inside the tasks. We integrate software runnables, i.e. chunks of software which are processed when a task is activated, in the analysis. In order to keep runtimes low, we show how to compress the modeling of runnables such that a high precision is preserved exactly where required.

- To show the benefits of the more detailed approach we compare our outcomes with results of other approaches. A comparison between our adaption and a state-of-the-art implementation of a compositional approaches for example shows significantly tighter bounds.

## 1.3 Structure

This paper is organized as follows: related work is presented in the next section. Subsequently, the systems in scope are described and a set of constraints which models their temporal behavior with respect to cause-effect chains is defined. Finally, in Section 5 the performance of our approach when compared with a state-of-the-art implementation of a compositional approach is evaluated. The benchmarks for the experiments are industrial-scale task sets from an automotive supplier and a manufacturer of automobiles.

# 2 Related Work

Calculating a formal bound on a latency of a cause-effect chain in a given system consists of two main steps. Firstly, a formal representation which fits the purpose is defined or chosen. Secondly, a suitable method to analyze the temporal properties of the model is employed to obtain an estimation. Therefore, due to the descriptive nature of the presented approach, related work is found
○ Référence interne

○ Financement

○ Collaborations

Ajouter

Lancer la recherche
Recherche experte (SolR)

Recherche experte (SolR)

Lancer la recherche
Vers la recherche avancée

• Déposer

Portail INRIA.HAL.SCIENCE
Les publications, logiciels... des scientifiques Inria

• Accueil

• Publications Inria

○ Consulter les derniers dépôts

○ Par équipe de recherche

○ Par auteur

○ Rapports de recherche et techniques

○ Livres blancs

○ Rapports d'activité des équipes

○ Statistiques

• Boite à Outils

○ X2Hal : importer par lot

○ Logiciels : créer le Codemeta.json

○ Créer mon IDHal

○ Créer mon CVHal

○ Haltools : créer ma page de publications

○ Haltools : extraire des données (réservé Inria)

○ Les bonnes pratiques

■ Comment bien s'affilier ?
in two disciplines: modeling systems and describing timing behavior, and the estimation of end-to-end latencies.

A formal language to specify the functionality as well as the timing of real-
time applications has been presented in [11]. One abstraction introduced is the
logical execution time (LET). In LET the behavior of the system in terms of
time is abstracted to when input is read and output is written rather than the
actual execution time [12]. The LET paradigm is especially used in the automo-
tive domain to determine end-to-end latencies [9,16]. LET massively simplifies
the problem of estimating end-to-end latencies for cause-effect chains because
data propagation only occurs within well-defined and fixed instances of chains.
However, in the mechatronic part of the system, data rates might vary because
they depend on physical factors, e.g. the engine speed of a car.

In contrast to analytical approaches, like e.g. [9], formal approaches strive
after upper bounds for latencies, i.e. all response times possibly observed in
the real system are lower or equal that bound. Formal approaches to tackle
this complexity can be divided in two categories. On the one hand, there are
holistic approaches, where chains are analyzed in one piece. The holistic approach
of Becker et al. is implemented by analyzing possible data propagation paths
of a chain [1]. Kloda et al. proposed an analysis algorithm with linear time
complexity which makes use of the execution time of tasks [13]. However, these
analyses are restricted to periodic task sets and make use of worst-case response
times of tasks, rather than worst-case execution times. This can lead to load
being considered which can not possibly be observed simultaneously in the real
system. Another holistic approach to estimating response times was presented
in [3,14]. It is based on mixed integer linear programming (MILP). For the
analysis, the system's timing properties are modeled with the help of linear
constraints. However, the scheduling model differs from the one considered in
this work and again the possible inferences of tasks are assumed to be covered in
an earlier analysis step. Another category of formal approaches if formed by the
compositional analysis (CPA) approaches. In CPA, local analyses are combined
to model the global system behavior to cope with the challenges in scalability.
Latest work on CPA broadens the range of systems for which the approach is
applicable [7] and shows how it can be used for the optimization of data ages [20].
CPA approaches also suffer from the problem that contexts of local worst-cases
might not be considered in the end-to-end result.

3 Properties and Encoding of Task Sets

To model the systems temporal behavior, we use a declarative description of
all possible data propagation paths for a chain within a finite interval of time.
The properties of tasks and chains are encoded in a set of constraints. Search-
ing for the worst case end-to-end latency in all satisfying assignments for these
constraints yields bounds on the latencies of the encoded task sequence. These
bounds are safe if the encoded system behavior models a superset of all possi-
ble behaviors of the real system. Here, safe means, that no worse data age or
* Quelle version puis-je déposer ?

* Choisir le bon « type de document »

* Mettre en valeur ses publications

○ Les tutos IES Inria

* Lier les notices dans HAL

* Umbrhal Inria pour l'accessibilité

* Personnaliser son CVHAL

* Créer et Personnaliser sa collection

• Documentation

○ Aide en ligne HAL

○ Aide en ligne Haltools

○ Aide en ligne X2hal

○ Tutoriels video HAL

○ Documentation API HAL

○ Ajouter des vignettes

○ Identifiant auteur IdHAL et CV

○ Compléter son dossier ORCID avec ses dépôts HAL

○ Inria et la Science Ouverte

X

X

X

Loading...

X

Le document que vous demandez est en access restreint
jusqu'au 2026-01-01 !

Revenir a la notice

Retourner à l'accueil

Contact

•

Ressources
response time can be observed in the real system, assuming that no overload occurs.

## 3.1 System Model

We consider multiprocessor systems, where each processing unit has a fixed set of tasks assigned. Tasks communicate via variables which are located in shared memory. We focus on fixed priority preemptive scheduling (FPPS) in this work. Tasks have a deadline relative to their activation. We assume that each tasks instance is guaranteed to be processed before it relative deadline occurs. In the next section we give a more detailed description of our task model.

## 3.2 Task Properties

The three most important properties of tasks with regards to end-to-end timing analysis are activation, response time of its runnables, and the communication mode for signal values. The response time of the runnables depend on their core execution time and the interference with other runnables competing for computing time on the same processing unit. In the following, $\mathcal{T}$ denotes the set of tasks.

**Task activation** Activation patterns describe the temporal nature of how instances of tasks occur. In general, tasks exist which occurrence cannot be modeled by a periodic-with-offset activation pattern without adding too much pes simism. A typical example from the automotive domain are computations which need to be performed synchronously to the engine speed [2]. The nature of these activation patterns is rather a minimum and maximum occurrence per time in- terval, e.g. because the rounds per minute of a combustion engine is specified within a given range. This can be converted to a minimum and maximum tem- poral distance of two consecutive activation events as shown in [21]. For task where a maximum occurrence per time interval cannot possibly be estimated, our approach additionally supports a sporadic activation pattern.

**Runnables** Let $\mathcal{R}$ be the set of runnables. Let $\mathcal{L} = \{(R)_{i=0}^n | n \in \mathbb{N}$ and $R_i \in \mathcal{R}\}$, i.e. the set of ordered lists of runnables. For a list of runnables of length $n$, $(R)_{i=0}^n$ we say $R_i < R_j$ if and only if $i < j$ f.a. $i, j \in \{0, \dots, n\}$. The runnables of a task are preemptable if the task is behaving cooperative, i.e.

$$ \forall i \in \mathcal{T} : \text{cooperative}(i) = \mathbf{t} \rightarrow (\forall r \in \text{rnbls}(i) : \text{preemptable}(r) = \mathbf{f}) \quad (1) $$

where rnbls($i$) denotes the ordered list of runnables assigned to task $i$. Con- straint 1 is an assertion that must hold for the input data.
* Documentation

* FAQ

* API

* OAI-PMH

* AuréHAL

## Informations

* À propos

* Données personnelles

* Mentions légales

* Accessibilité

* Conformité RGAA

## Questions juridiques

* Je publie, quels sont mes droits ?

* Loi pour une République numérique

* Stratégie de non-cession des droits

* SHERPA/RoMEO

## Portails

* Portails institutionnels

* HAL

* HAL SHS

* HAL Thèses

* MédiHAL

## CCSD

* CCSD

* Episciences

* Sciencesconf
**Communication modes** Runnables communicate with the help of *signals*. Different *communication modes* for signal accesses are common. Direct read and write on signals as the data is being processed is called *explicit communication*. On the contrary, tasks obtaining a local copy of the data they process are said to implement *implicit communication*. In this case, results are transferred to shared memory collectively after the last runnable was completely processed. A special case of implicit communication is called *deterministic communication*. Here, all data manipulated is held in a buffer and written back only at well-defined points of time relative to the activation of the task instance, e.g. the start of the next execution period.

## 3.3 Encoding

In [6] the authors gave a list of constraints which need to be satisfied if a task-level data flow with no core execution times (CETs) is considered. We incorporate CETs on runnable level to add an additional level of detail. Consequently, the constraints which must hold to model the systems behavior need to be extended. The following, previously not considered, constraints must additionally be satisfied:

1. If a task is scheduled for processing, an instance of the first runnable of the task is started. Cf. Constraint 3.

2. If the processing of an runnable instance finished and the corresponding task has another runnable, an instance of this runnable is started. Cf. Constraint 3.

3. When a task instance gets activated, it may interrupt a currently processed runnable instance if the latter is preemptable and the former is preferred for execution by the scheduling policy and both are assigned to the same processing unit. The processing time of all runnable instance of the preempting task is added to the paused time of the preempted runnable. Cf. Constraint 6.

4. The time to process a runnable is at least its BCET and at most its WCET. The results of a runnable are produced between its start and end. Cf. Constraint 7.

5. An instance of a task terminates at the moment the instance of the last runnable of the task was processed. The response time is before a given deadline. Cf. Constraint 8 and Constraint 9.

Given a set of tasks and a chain, it can be derived how many task instances need to be considered for a safe estimation. Let $m_i$ hold this number for each task $i \in T$. The determination of $m_i$ is discussed in [6] and does not change for the extended approach. To encode task instances with their runnables, each task instance and runnable instance gets three variables assigned. A task instance has an activation time $\alpha^T$, an actual starting time $\sigma^T$ and a termination time $\varepsilon^T$. The delay of a task instance is described in the difference between $\alpha^T$ and $\sigma^T$. Each runnable of every task instance has a starting time $\sigma^R$, a termination time $\varepsilon^R$ and a total time it was paused from processing $\ell^R$. In Figure 2 the variables in the context of a task instance are depicted.
The constraints on the activation time $\alpha^T$ only depend on the activation model of the task. Thus, the constraints presented in [6] can be reused. After a task instance is activated, it is enqueued for processing. A possible delay of the actual start depends on other tasks running on the same core. At this point, for the new detail-level,

runnables need to be considered. In order to list the constraints on the $\sigma^T$'s, we define two auxiliary sets. Firstly, let $D_{i,j}^{HP}$ contain the termination times of all task instances that might delay instance $j$ of task $i$ due to higher priority. Secondly, let $D_{i,j}^{NP}$ contain the termination time of all runnables which might cause a delay on instance $j$ of task $i$ because they are still running but might not be preempted.

The actual starting time can then be determined by taking the maximum from the aforementioned sets and the activation time of the task, i.e. for all $i \in \mathcal{T}$ and $1 \le j \le m_i$ holds

$$ \sigma_{i,j}^T = \max(D_{i,j}^{HP} \cup D_{i,j}^{NP} \cup \{\alpha_{i,j}^T\}). \quad (2) $$

After a task is scheduled for processing, the first runnable of the task is processed. Each following runnable, is processed after the processing of its predecessors finished. Therefore,

$$ \sigma_{i,j,r}^R = \max(\{\sigma_{i,j}^T\} \cup \{\varepsilon_{i,j,o}^R | o \in \text{rnbls}(i) \wedge o < r\}) \quad (3) $$

must hold f.a. $i \in \mathcal{T}$ and $1 \le j \le m_i$ and $r \in \text{rnbls}(i)$.

A task might be paused due to other task instance being preferred for processing. To calculate the total paused time, $\iota^R$, we introduce two auxiliary variables for each pair of task instance and runnable. The first one, $i^{HP}$, is defined as

$$ i_{i,j,r,\ell,k,o}^{\mathrm{HP}} = \begin{cases} 1 & \text{if } \sigma_{\ell,k,r}^T \ge \sigma_{i,j}^T \wedge \epsilon_{\ell,k}^T \le \epsilon_{i,j}^T \wedge \sigma_{\ell,k,o}^R > \sigma_{i,j,r}^R \wedge \\ & \text{core}(i) = \text{core}(\ell) \wedge \text{prio}(i) < \text{prio}(\ell) \wedge \\ & \text{preemptable}(r) = \mathbf{t} \\ 0 & \text{otherwise} \end{cases} \quad (4) $$

f.a. $i, \ell \in \mathcal{T}$, $j \in \{1, \dots, m_i\}$, $k \in \{1, \dots, m_\ell\}$, $r \in \text{rnbls}(i)$, and $o \in \text{rnbls}(\ell)$. This is, $i_{i,j,r,\ell,k,o}^{HP}$ is 1 if the runnable $o$ of the $k^{th}$ instance of task $\ell$ causes a pause of the runnable $r$ of the $j^{th}$ instance of task $i$. The second one, $\gamma_{i,j,r}^R$ is the CET of $r$, this is

$$ \gamma_{i,j,r}^R = \varepsilon_{i,j,r}^R - \sigma_{i,j,r}^R - \iota_{i,j,r}^R \quad \forall i, \ell \in \mathcal{T}, j \in \{1, \dots, m_i\}, r \in \text{rnbls}(i). \quad (5) $$

The pause time $\iota^R$ then is f.a. $i, \ell \in \mathcal{T}$, $j \in \{1, \dots, m_i\}$, $k \in \{1, \dots, m_\ell\}$, and $r \in \text{rnbls}(i)$ given by

$$ \iota_{i,j,r}^R = \sum_{\ell \in \mathcal{T} \setminus \{i\}} \sum_{k=1}^{m_\ell} \sum_{o \in \text{rnbls}(\ell)} i_{i,j,r,\ell,k,o}^{\mathrm{HP}} \cdot \gamma_{\ell,k,o}^R. \quad (6) $$

<figure><img src="image_3.png" /><figcaption>Fig. 2. Variables of task instances and runnable instances</figcaption></figure>
To model the possible interference by other tasks for tasks scheduled cooperatively, we add an additional preemptable runnable between any two runnables where the task might return control to the scheduler.

Given the CET and the paused time, the possible termination times for the runnables can be determined. This is, f.a. $i, \ell \in \mathcal{T}, j \in \{1, \dots, m_i\}, k \in \{1, \dots, m_\ell\}$, and $r \in \text{rnbs}(i)$

$$ \varepsilon_{i,j,r}^R \ge \sigma_{i,j,r}^R + \iota_{i,j,r}^R + \text{bcet}(r) \wedge \varepsilon_{i,j,r}^R \le \sigma_{i,j,r}^R + \iota_{i,j,r}^R + \text{wcet}(r). \quad (7) $$

The end of processing of the last runnable of a task instance finally determines the time of termination for the task instance $\varepsilon^T$.

$$ \varepsilon_{i,j}^T = \max(\{\varepsilon_{i,j,r}^R \mid r \in \text{rnbs}(i)\}) \quad (8) $$

According to our assumptions, the response time of task instances is bound by its deadline, i.e.

$$ \varepsilon_{i,j}^T \le \alpha_{i,j}^T + \text{deadline}(i) \quad \forall i \in \mathcal{T}, 1 \le j \le m_i. \quad (9) $$

## 3.4 Model optimization

The newly gained precision, comes with the price of larger constraint models. Especially, Constraint 4 and Constraint 6 contribute to an increase because they depend on the amount of runnables per task. However, the impact can be reduced by aggregating individual runnables to a single runnable where it has little to none effect on the estimation. More precisely, multiple runnables of a task which is not part of the analyzed chain can be aggregated to one runnable modeling the same load. For task which participate in the chain, only the first possible read access and the last possible write access are relevant to determine the temporal behavior with respect to the chain. Therefore, the runnables of such a task can be divided in three categories: the ones processed prior to the first read, the ones processed in between, and the ones processed after the last write. Each group of runnables can be aggregated as described above, resulting in three synthetic runnables for a task on the chain.

Aggregating runnables to abstract their temporal behavior collectively gives the flexibility to adjust the time-precision tradeoff by the user's needs. If fast estimations are needed, e.g. because the system model is still vague in early development stages, nearly all runnables can be aggregated. If the system design is fixed in the final product, final analyses can be performed with a greater level of detail.

# 4 Properties and Encoding of Cause-Effect Chains

As described above, the analysis of task sequences suffices for the analysis of end-to-end latencies in the considered systems. Let $(p^T)_{k=1}^\ell$ with $p_k^T \in \mathcal{T}$ f.a. $k \in \{1, \dots, \ell\}$ be such a sequence of tasks and let $(p^R)_{k=1}^\ell$, with $p_k^R$ subsequence
of rnbs($p_k^T$), be the corresponding sequence on runnable level f.a. $k \in \{1, \dots, \ell\}$. The timing properties of the sequence can be characterized by an ordered sequence of points of time with two points of time for each task or runnable involved. The first point of time describes when data is read, the second point of time describes when data is written. As proposed in [6] two additional sets of variables are used. One variable holds the point of time at which values were written at index $k$ f.a. $k \in \{1, \dots, \ell\}$. The other holds the index of the task instance participating in the chain at index $k$. In the constraints on $x$ and $n$ the newly gained precision is reflected. Most evidently in the constraints in the case of explicitly communicating tasks, e.g. the constraints for response time which are

$$n_k = \min(\{j \mid \min(\{\sigma_{i,j,r}^R \mid r \in p_k^R\}) \ge x_{k-1}\}) \quad (10)$$

and

$$\min(\{\sigma_{i,n_k,r}^R \mid r \in p_k^R\}) \le x_k \le \max(\{\epsilon_{i,n_k,r}^R \mid r \in p_k^R\}) \quad (11)$$

f.a. $k \in \{1, \dots, \ell\}$.

Finally, the objective under the constraints on $n$ and $k$ and the constraints listed in Section 3.3 is to maximize the difference in the response time of the last task and the activation of the first task on the chain.

# 5 Evaluation

We evaluated the performance of the improved model in terms of quality of the results, and scalability and performance. For this, we encoded the constraints using the high-level constraint language MiniZinc [18]. For solving, the MiniZinc models are linked with a data file to create a FlatZinc formula [17]. We chose the parallel version of the lazy clause generation solver Chuffed as presented in [4] to solve the FlatZinc-formula. As an environment to run our tests we used OpenMpi<fnref n="3" /> under CygWin<fnref n="4" />. The performance in terms of time consumption and memory usage was measured with the time command<fnref n="5" />. The experiments were carried out on a desktop computer with an Intel(R) Core(TM) i9-7940X CPU @ 3.10GHz and 128 GB DDR4 running Windows 10 Enterprise.

Besides more precise results, the evaluations show the need of sporadic activation patterns for safe and precise estimations. To evaluate precision on runnable-level, we compare our results to the results of [20] for different variants of the task-set published in [10]. Afterwards, we compare the results of the task-level approach with the results of the compositional timing analysis tool pyCPA. For this comparison we used a benchmark based on the task set of a powertrain controller from Daimler. The data is available online<fnref n="6" />. The tasks CXIY X, Y $\in \{0, \dots, 3\}$

<footnote n="3">³ https://www.open-mpi.org/</footnote>

<footnote n="4">⁴ http://cygwin.org/</footnote>

<footnote n="5">⁵ http://man7.org/linux/man-pages/man1/time.1.html</footnote>

<footnote n="6">⁶ https://www.informatik.uni-kiel.de/~mjf/CPCPS/</footnote>
of the benchmark task set have an alternative sporadic activated pattern. These are used to show that approximating the behavior of a sporadically activated tasks with the help of a periodic task does not yield safe bounds.

The results of the comparison with *pyCPA*<sup>7</sup> are listed in Table 1. They show tighter bounds for data age and response time for all chains. The differences originate from an overestimation on relative offset between the tasks on the chain. Summing them up takes situations into consideration which can not possibly occur in the real system.

<table><caption>**Table 1.** Results for Chain 0 – Chain 7</caption><thead><tr><th rowspan="2">Chain</th><th colspan="3">Response time<br>(µs)</th><th colspan="2">Data age (µs)</th></tr><tr><th>py- task-<br>CPA<br>level<sup>1</sup></th><th>task-<br>level<sup>2</sup></th><th>py- task-<br>CPA<br>level<sup>1</sup></th><th>task-<br>level<sup>2</sup></th></tr></thead><tbody><tr><td>Chain 0</td><td>22160</td><td>10650</td><td>10650</td><td>20910</td><td>10650</td></tr><tr><td>Chain 1</td><td>21420</td><td>10740</td><td>10800</td><td>15170</td><td>6740</td></tr><tr><td>Chain 2</td><td>15410</td><td>4750</td><td>4750</td><td>19930</td><td>8660</td></tr><tr><td>Chain 3</td><td>34620</td><td>15250</td><td>15250</td><td>32890</td><td>15160</td></tr><tr><td>Chain 4</td><td>36110</td><td>15240</td><td>15300</td><td>34380</td><td>15240</td></tr><tr><td>Chain 5</td><td>27685</td><td>15780</td><td>15780</td><td>7685</td><td>5780</td></tr><tr><td>Chain 6</td><td>16520</td><td>10015</td><td>11748</td><td>31520</td><td>25015</td></tr><tr><td>Chain 7</td><td>5265</td><td>5015</td><td>6355</td><td>5265</td><td>5015</td></tr></tbody></table>

task-level<sup>1</sup> : Benchmark task-set without sporadic tasks

task-level<sup>2</sup> : Benchmark task-set with sporadic tasks

Furthermore, we compared the results using the periodic activation patterns with the ones using their sporadic alternative. The results are also shown in Table 1. For chains containing task C0I0, the estimation increases, e.g. the response time of Chain 6. An effect on the estimations is also observed for chains only containing periodic tasks, e.g. the data age of Chain 1. The additional delay is caused by a newly possible delays of periodic tasks. This can lead to additional relative offsets between tasks, e.g. because of shifted

write intervals. Depending on task set and chain, the concurrence of both effects can lead to tremendously increased estimations, e.g. for the data age of Chain 5. On the one hand, C0I0 can have a greater temporal distance to C1T0 in terms of activation time. On the other hand, a shift of C2T1 to the left and C3T3 to the right results in an additional period of C2T1 being added to the latency.

Another evaluation is based on originally published in [10]. In [20] Schlatow et al. propose different priority assignments and core mappings in order to optimize data ages. We compared the results with estimations obtained using our approach. Both, a task-level data flow and a runnable-level data flow were considered. The task level-data flow was implemented by aggregating all runnables of a task in terms of their

<table><caption>**Table 2.** Results for the Bosch FMTV Challenge model</caption><thead><tr><th rowspan="2">Experiment</th><th rowspan="2">Chain</th><th colspan="3">Data age (µs)</th></tr><tr><th>results<br>from [20]</th><th>task-<br>level</th><th>runnable-<br>level</th></tr></thead><tbody><tr><td>default</td><td>Chain 2</td><td>-</td><td>148283</td><td>120101</td></tr><tr><td>Eπφ</td><td>Chain 2</td><td>160415</td><td>148283</td><td>120101</td></tr><tr><td>EπφA</td><td>Chain 2</td><td>134207</td><td>128283</td><td>110101</td></tr><tr><td>default</td><td>Chain 3</td><td>-</td><td>4927</td><td>3148</td></tr><tr><td>Eπφ</td><td>Chain 3</td><td>5249</td><td>4200</td><td>3148</td></tr><tr><td>EπφA</td><td>Chain 3</td><td>4683</td><td>4981</td><td>2422</td></tr></tbody></table>

temporal behavior. The result are listed in Table 2. They show that the improvement from variant *Eπφ* to *EπφA* for Chain 2 is confirmed by our estimations. However, in the case of Chain 3 the estimations using a task-level data flow disagree with the results obtained using a runnable-level data flow regarding an

<footnote n="7">⁷ https://bitbucket.org/pycpa/pycpa</footnote>
improvement. This shows the importance of reliable and precise estimations in
the context of optimization. An actual improvement might not be achieved if the
margin of the optimization lies within the imprecision of the estimation method.

6 Conclusion

In this paper we showed how the constraint programming approach to latency estimation can be improved to obtain tighter bounds on end-to-end latencies. The extended approach supports a wide range of task-sets and can be used to estimate data ages as well as response times. The comparison with state-of-the-art estimations shows an improved precision. This comes with the cost of additional computational effort. Nevertheless, we showed that the approach can be optimized to scale for industrial-size task-sets.

References

1. Becker, M., Dasari, D., Mubeen, S., Behnam, M., Nolte, T.: Synthesizing job-level dependencies for automotive multi-rate effect chains. In: 22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016, Daegu, South Korea, August 17-19, 2016. pp. 159–169. IEEE Computer Soc. (2016)

2. Biondi, A., Buttazzo, G.C.: Engine control: task modeling and analysis. In: Nebel, W., Atienza, D. (eds.) Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE 2015, Grenoble, France, March 9-13, 2015. pp. 525–530. ACM (2015), http://dl.acm.org/citation.cfm?id=2755872

3. Boniol, F., Lauer, M., Pagetti, C., Ermont, J.: Freshness and reactivity analysis in globally asynchronous locally time-triggered systems. In: Brat, G., Rungta, N., Venet, A. (eds.) NASA Formal Methods, 5th International Symposium, NFM 2013, Moffett Field, CA, USA, May 14-16, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7871, pp. 93–107. Springer (2013)

4. Ehlers, T., Stuckey, P.J.: Parallelizing constraint programming with learning. In: Quimper, C. (ed.) Integration of AI and OR Techniques in Constraint Programming - 13th International Conference, CPAIOR 2016, Banff, AB, Canada, May 29 - June 1, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9676, pp. 142–158. Springer (2016)

5. Feiertag, N., Richter, K., Nordlander, J., Jonsson, J.: A compositional framework for end-to-end path delay calculation of automotive systems under different path semantics. In: Proceedings of the IEEE Real-Time System Symposium - Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, Barcelona, Spain, November 30, 2008 (2008)

6. Friese, M.J., Ehlers, T., Nowotka, D.: Estimating latencies of task sequences in multi-core automotive ecus. In: 13th IEEE International Symposium on Industrial Embedded Systems, SIES 2018, Graz, Austria, June 6-8, 2018. pp. 1–10 (2018)

7. Gemlau, K.B., Schlatow, J., Möstl, M., Ernst, R.: Compositional analysis for the waters industrial challenge 2017. In: International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS). Dubrovnik, Croatia (jun 2017)
8. Godefroid, P., Sen, K.: Combining Model Checking and Testing, pp. 613–649. Springer International Publishing, Cham (2018)

9. Hamann, A., Dasari, D., Kramer, S., Pressler, M., Wurst, F.: Communication centric design in complex automotive embedded systems. In: Bertogna, M. (ed.) 29th Euromicro Conference on Real-Time Systems, ECRTS 2017, June 27-30, 2017, Dubrovnik, Croatia. LIPIcs, vol. 76, pp. 10:1–10:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)

10. Hamann, A., Ziegenbein, D., Kramer, S., Lukasiewycz, M.: Demonstration of the fmtv 2016 timing verification challenge (April 2016), http://www.ecrts.org/forum/download/file.php?id=35&sid=619cd45cc904f6f8a66fc526919a2ebd

11. Henzinger, T.A., Horowitz, B., Kirsch, C.M.: Giotto: A time-triggered language for embedded programming. In: Embedded Software: First International Workshop, EMSOFT 2001 Tahoe City, CA, USA, October 8–10, 2001 Proceedings. pp. 166–184. Springer (2001)

12. Kirsch, C.M., Sokolova, A.: The logical execution time paradigm. In: Chakraborty, S., Eberspächer, J. (eds.) Advances in Real-Time Systems (to Georg Färber on the occasion of his appointment as Professor Emeritus at TU München after leading the Lehrstuhl für Realzeit-Computersysteme for 34 illustrious years). pp. 103–120. Springer (2012)

13. Kloda, T., Bertout, A., Sorel, Y.: Latency analysis for data chains of real-time periodic tasks. In: 23rd IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2018, Torino, Italy, September 4-7, 2018. pp. 360–367. IEEE (2018)

14. Lauer, M., Boniol, F., Pagetti, C., Ermont, J.: End-to-end latency and temporal consistency analysis in networked real-time systems. IJCCBS 5(3/4), 172–196 (2014)

15. Lee, E.A.: Cyber-physical systems - are computing foundations adequate? Proc. Workshop CyberPhysical Syst. Res. Motiv. Tech. Roadmap (01 2006), http://ptolemy.eecs.berkeley.edu/publications/papers/06/CPSPositionPaper/

16. Martinez, J., Olmedo, I.S., Bertogna, M.: Analytical characterization of end-to-end communication delays with logical execution time. IEEE Trans. on CAD of Integrated Circuits and Systems 37(11), 2244–2254 (2018)

17. Nethercote, N.: Converting minizinc to flatzinc (2014), http://www.minizinc.org/downloads/doc-1.2.2/mzn2fzn.pdf

18. Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: Minizinc: Towards a standard CP modelling language. In: Bessiere, C. (ed.) Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4741, pp. 529–543. Springer (2007)

19. Santos, M.M.D., Ambiel, V., Acras, M., Gliwa, P.: On the timing analysis at automotive real-time embedded systems. SAE Technical Paper (03 2017)

20. Schlatow, J., Möstl, M., Tobuschat, S., Ishigooka, T., Ernst, R.: Data-age analysis and optimisation for cause-effect chains in automotive control systems. In: 13th IEEE International Symposium on Industrial Embedded Systems, SIES 2018, Graz, Austria, June 6-8, 2018. pp. 1–9 (2018)

21. Schliecker, S., Ernst, R.: A recursive approach to end-to-end path latency computation in heterogeneous multiprocessor systems. In: Rosenstiel, W., Wakabayashi, K. (eds.) Proceedings of the 7th International Conference on Hardware/Software Codesign and System Synthesis, CODES+ISSS 2009, Grenoble, France, October 11-16, 2009. pp. 433–442. ACM (2009)