Tomasz Kloda
email: tomasz.kloda@tum.de

Antoine Bertout
email: antoine.bertout@univ-poitiers.fr

Yves Sorel
email: yves.sorel@inria.fr

Latency upper bound for data chains of real-time periodic tasks

Keywords: Real-Time Systems, End-to-End Latency, Periodic Tasks, Read-Execute-Write

The inter-task communication in embedded real-time systems can be achieved using various patterns and be subject to different timing constraints. One of the most basic communication patterns encountered in today's automotive and aerospace software is the data chain. Each task of the chain reads data from the previous task and delivers the results of its computation to the next task. The data passing does not affect the execution of the tasks that are activated periodically at their own rates. As there is no task synchronization, a task does not wait for its predecessor data; it may execute with old data and get new data at its later release. From the design stage of embedded real-time systems, evaluating if data chains meet their timing requirements, such as the latency constraint, is of the highest importance. The trade-off between accuracy and complexity of the timing analysis is a critical element in the optimization process. In this paper, we consider data chains of real-time periodic tasks executed by a fixed-priority preemptive scheduler upon a single processor. We present a method for the worst-case latency calculation of periodic tasks' data chains. As the method has an exponential time complexity, we derive a polynomial-time upper bound. Evaluations carried out on an automotive benchmark demonstrate that the average bound overestimation is less than 10 percent of the actual value.

Introduction

The cyber-physical systems are engineered solutions that bridge together the cyber and physical world. At the boundaries of these two worlds, a connection is established through two peripheral subsystems. A sensory subsystem detects the events appearing in the environment and an actuation subsystem delivers the appropriate actions to control the physical process. Low-latency inputoutput processing is a desirable property for enabling time-sensitive control. The software architecture for such systems usually consists of multiple cooperating and communicating tasks that process the data from sensors to actuators. The resulting task chain end-to-end latency necessarily depends on the execution requirements of individual tasks and the inter-task communication delays.

The compound architectures of the real-time embedded systems in which the flow of data requires several processing stages before the actuation signals are produced can be encountered in many mission-and safety-critical applications. Such applications can be found in fields like aeronautics, healthcare, or automotive.

A Flight Management System (FMS) can be viewed as an example of the cyber-physical system with multiplestage data processing where the output of one task or task group is the input of the next one. The FMS is an on-board avionics computing system used in newgeneration aircraft that helps a pilot in operating a wide range of in-flight tasks [START_REF] Walter | Digital Avionics Handbook, Second Edition -2 Volume Set[END_REF]. It keeps track of the current aircraft position, assists the crew in flight planning and trajectory prediction, monitors and helps to optimize the flight parameters and performances (e.g., fuel consumption, flight time). Figure 1 software architecture1 (sensors as triangles, actuators as ellipses, and functions as boxes). As can be seen, many FMS functions are divided into subsequent groups that process the data from the other avionics systems and interfaces. Consider, for instance, the chain marked with the red dotted line in Figure 1. First, the readings from the autonomous sensors, like accelerometers and gyroscopes, together with the information coming from the navigation receivers, like the Distance Measuring Equipment, the VHF Omni Directional Radio Range or the Global Positioning System, are fused in by the tasks of the Sensor Group. Then, the tasks of the Localization Group, based on the information from the navigation database and the fused sensor readings, compute an accurate estimate of the current aircraft position. Afterward, the current position is processed by a chain of tasks from the Trajectory Group and the Guidance Group to deliver the steering signals to the actuators. End-to-end latency constraints. Due to the mission-critical nature of many operations mentioned in the previous FMS example, their results must be produced within a precise time. Wyss et al. [START_REF] Wyss | Propriétés de latence, fraîcheur et réactivité dans un programme synchrone multi-périodique[END_REF] summarize different timing requirements as follows. Reactivity (or data reaction [START_REF] Saad Mubeen | Support for End-to-End Response-Time and Delay Analysis in the Industrial Tool Suite: Issues, Experiences and a Case Study[END_REF]) is a time interval during which data must be present at the sensor input to be detected. Latency is a time interval between the arrival of data at the sensor input and actuator's update with a value corresponding to that particular data (i.e., the time needed for data to be propagated from sensor to actuator). Freshness (or data age [START_REF] Feiertag | A Compositional Framework for End-to-End Path Delay Calculation of Automotive Systems under Different Path Semantics[END_REF]) is a time interval during which the actuator's value corresponding to the same sensor reading is used.

Task chains. From sensor readings to actuation signals, the FMS tasks process the data through several stages. A task chain is a sequence of communicating tasks in which every task receives the data from its predecessors [START_REF] Saad Mubeen | Support for End-to-End Response-Time and Delay Analysis in the Industrial Tool Suite: Issues, Experiences and a Case Study[END_REF]. There are two models of task chains: trigger chains and data chains. They differ in task activation rules. In trigger chains, the tasks are released by the events issued from the preceding tasks. In data chains, the tasks are independent, and every task is activated periodically at its individual rate.

Trigger chains are characterized by a more flexible timing behavior. Their tasks execute only if necessary: a task is released only if it receives the request from its predecessor. The processor resources are used efficiently, and the inter-task data passing is immediate. Conversely, tasks of the data chains are released at every period, even if there is no new data to process. Processor resources can be wasted in the case of redundant task execution. Moreover, certain delay of time can elapse between the instant when the results are produced by the current task and the instant when the next task is released and can retrieve the results.

However, especially in an industrial context, data chains may outweigh the above-mentioned advantages of trigger chains. In fact, imposing the precedence relation between the subsequent tasks of a trigger chain requires synchronization mechanisms (e.g., semaphores). The use of the synchronization primitives can lead to priorityinversion problems and deadlock formations [START_REF] Schlatow | Response-Time Analysis for Task Chains in Communicating Threads[END_REF][START_REF] Sha | Priority Inheritance Protocols: An Approach to Real-Time Synchronization[END_REF]. An additional effort is therefore needed for the integration of these primitives with adequate control structures. As safety-critical software is subject to stringent standards, adding these features to the system makes the certification process ultimately more complicated [START_REF] Forget | Scheduling Dependent Periodic Tasks without Synchronization Mechanisms[END_REF]. For those reasons, the unrestrained execution model of data chains can permit to reduce cost and time overheads related to the correct implementation and validation of synchronization mechanisms required by trigger chains.

Motivation. The respect of timing constraints is crucial for critical real-time embedded systems and must be taken into account at the earliest stages of the design process. End-to-end timing constraints are introduced in many automotive software architectures and modeling languages [START_REF] Saad Mubeen | Supporting timing analysis of vehicular embedded systems through the refinement of timing constraints[END_REF] (e.g., timing model of the AUTOSAR standard [START_REF][END_REF], timing extensions to EAST-ADL [START_REF][END_REF], TADL2 language [START_REF]Timing Augmented Description Language (TADL2) syntax, semantics, metamodel[END_REF]). Computing a single value of data chain latency is not computationally challenging. It is especially true for the short chains and the chains with equal periods. However, already at the design level, the computational complexity becomes a serious limitation when multiple possible design choices must be evaluated. With the rapid increase of software size and complexity in today's embedded systems [START_REF] Bello | Recent Advances and Trends in On-Board Embedded and Networked Automotive Systems[END_REF][START_REF] Ebert | Automotive software[END_REF], the problem can only be exacerbated. Lowering the computational complexity of the latency analysis can help in solving the optimization problems like offsets, periods, and priorities assignment [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF][START_REF] Deng | An Efficient Control-Driven Period Optimization Algorithm for Distributed Real-Time Systems[END_REF][START_REF] Klaus | Data Propagation Delay Constraints in Multi-Rate Systems: Deadlines vs. Job-Level Dependencies[END_REF][START_REF] Krawczyk | Model-Based Timing Analysis and Deployment Optimization for Heterogeneous Multi-core Systems using Eclipse APP4MC[END_REF].

Contribution. In our previous work [START_REF] Kloda | Latency analysis for data chains of real-time periodic tasks[END_REF], we proposed a method for the computation of the data chain worst-case latency of periodic independent tasks with implicit deadlines scheduled by a fixed-priority preemptive algorithm given a priority assignment of these tasks and their worst-case response times. As the method has exponential time complexity, in this work we:

• derive a polynomial-time upper bound on the data chain worst-case latency,

• identify the sources of bound pessimism and provide a condition for bound tightness,

• evaluate the impact of different worst-case response time estimations on the precision of the latency analysis for different chain lengths.

Paper structure. The paper is organized as follows. The data chain model is introduced in Section 2. We present a method for the calculation of the worst-case latency of the data chains in Section 3. As the method has an exponential time complexity, we propose in Section 4 a polynomial-time upper bound on the worst-case latency of the data chains. In Section 5, we evaluate the bound precision and efficiency using the generic task sets based on a real-world automotive system. We review the related work in Section 6 and conclude the paper in Section 7.

System model

We introduce a data chain as a sequence of independent periodic tasks with implicit deadlines scheduled by a fixed-priority preemptive policy upon a single processor.

Periodic task model

A system consists of a finite set of periodic tasks. Each task τ i is characterized by its worst-case execution time C i and its period T i (both positive integers). An instance (job) of task τ i is released every period T i and must meet its execution requirement upper bounded by C i before the arrival of its next instance (implicit deadline D i = T i ). The first instance of τ i is released at the time instant 0. The infinite set of all the release time instants of task τ i is referred to as A(τ i ) = {0, T i , 2T i , . . .}. The j -th instance of the task τ i released at r i,j ∈ A(τ i ) is denoted by J i (r i,j ). In the rest of the paper, to facilitate the reading, an arrival r i,j of a task τ i will be sometimes simply denoted by r i when there is no possible ambiguity with different arrivals of τ i . The hyperperiod H is the least common multiple of all task periods, and T max denotes the largest period.

Tasks are scheduled upon a single processor by a fixedpriority preemptive scheduler. Each task τ i is assumed to have a unique priority π(τ i ). We consider that τ i has a higher priority than τ k if π(τ i ) > π(τ k ). Additionally, we denote a set of tasks with priorities higher than π(τ i ) as: hp(τ i ) = {τ k : π(τ k ) > π(τ i )} and with priorities higher than or equal to π(τ i ) as: hep(τ i ) = hp(τ i ) ∪ {τ i }. The tasks are assumed to be independent, and their executions cannot be blocked by another task other than due to contention for the processor. Once a task starts to execute, it will not voluntarily suspend its execution. Tasks can begin processing, complete, or be preempted at any time with respect to their parameters.

Task response time

The worst-case job response time R i (r i,j ) of task τ i released at r i,j ∈ A(τ i ) is given by the longest time from r i,j until it completes its execution. The time instant when it completes its execution is denoted by

f i (r i,j ) = r i,j + R i (r i,j ).
The worst-case task response time of τ i , denoted as R i , is given by the maximum worst-case job response time among all its jobs: R i = max ri,j ∈A(τi) R i (r i,j ). A system is deemed schedulable when ∀τ i : R i ≤ T i .

Data chain model

A data chain F n is a sequence of n ≥ 1 tasks (τ 1 , . . . , τ n ) describing a flow of communication between the tasks realized via shared registers. Let head(F n ) = τ 1 be its first task, last(F n ) = τ n its last task and tail(F n ) = (τ 2 , . . . , τ n ) the chain obtained by removing τ 1 from F n . If n = 1, then τ 1 after its start reads the data from its sensor, computes its outputs and writes the outputs to the appropriate actuator. Otherwise, if n ≥ 2, the data chain F n processes the data as follows: when τ 1 starts, it reads the data from a sensor, computes the results and, at the end of its execution, writes these results into the register of τ 2 ; when τ i (for i : 1 < i < n) starts, it reads the data from the register of τ i-1 , computes the results and writes these results, at the end of τ i , into the register of τ i+1 ; when τ n starts, it reads the data from τ n-1 , computes the outputs and, at the end of its execution, writes these outputs to the corresponding actuator.

The start of the tasks does not depend on the communication, and the tasks are scheduled according to the assigned priorities only. Figure 2 illustrates a data chain F 3 of three tasks (τ 1 , τ 2 , and τ 3 ) and their registers. The communication described above assumes the readexecute-write task semantics (implicit communication [START_REF] Becker | End-to-End Timing Analysis of Cause-Effect Chains in Automotive Embedded Systems[END_REF][START_REF] Hamann | Communication Centric Design in Complex Automotive Embedded Systems[END_REF] in AUTOSAR): the input data can only be read at the beginning of the task execution, and the results can only be written at the end of its execution. The same mechanism is implemented in Cyclical Asynchronous Buffers [START_REF] Clark | HIC: an operating system for hierarchies of servo loops[END_REF]. The operations on the registers (read and write) are atomic and are assumed to take a negligible amount of time. The computation process can be preempted at any time and resumed later from the same context. Each task has its individual register which stores only the most recent data. A data remains present in a register until being overwritten, and the access to the registers is asynchronous (i.e., can be accessed anytime).

Data propagation path

Based on the concept of timed path [START_REF] Feiertag | A Compositional Framework for End-to-End Path Delay Calculation of Automotive Systems under Different Path Semantics[END_REF][START_REF] Becker | Synthesizing Job-Level Dependencies for Automotive Multi-rate Effect Chains[END_REF], we define, for a data chain F n released at time instant r 1 ∈ A(τ 1 ) such that τ 1 ∈ head(F n ), a set of data propagation paths Ω(F n , r 1 ). A data propagation path p ∈ Ω(F n , r 1 ) is an n-tuple (r 1 , . . . , r n ) where r i ∈ p is the release time of the instance of task τ i that propagates the data. A task τ i propagates a data when it writes this data for the first time into a task register of the next task τ i+1 . It is supposed that from the time instant r 1 the data is continuously present at the chain's input, and the registers of the other tasks are empty at r 1 .

Figure 3 shows two different execution scenarios of a data chain F 3 . The chain is composed of three tasks: τ 1 , τ 2 , and τ 3 such that π(τ 2 ) > π(τ 3 ) > π(τ 1 ). Two data propagation paths can be distinguished for Ω(F 3 , r 1,1 ). The first one, shown in Figure 3 a), occurs when τ 1 terminates at f 1,1 : (r 1,1 , r 2,3 , r 3,3 ). The second one, shown in Figure 3 b), occurs when τ 1 terminates earlier at f 1,1 :

(r 1,1 , r 2,2 , r 3,2 ) with f 1,1 > f 1,1 .

Data chain latency

The latency of a data chain is a time duration between the arrival of its input and the first output corresponding to this arrival [START_REF] Rajeev | Schedulability and End-to-end Latency in Distributed ECU Networks: Formal Modeling and Precise Estimation[END_REF].

Definition 1 (Latency). Let F n be a data chain whose registers are initially empty. Its data latency is a time interval elapsed between:

-the time instant at which the data arrives at the input sensor connected to head(F n ) given that the data is available sufficiently long to be detected, and -the time instant at which the actuator connected to last(F n ) is updated with the data corresponding to the computation performed by all the tasks of F n .

Given that the data arrives at r 1 , the maximum latency L(F n , r 1 ) of a data chain F n corresponds to the data propagation path in which the last task τ n completes at the latest time.

Definition 2 (Maximum data chain latency at r 1 ). Let F n be a data chain of n ≥ 1 tasks and r 1 ∈ A(τ 1 ) the release time of its first task τ 1 = head(F n ) such that the input of τ 1 arrives in its register at r 1 . The maximum latency of data chain F n released at r 1 is:

L(F n , r 1 ) = max p∈Ω(Fn,r1) f n (r n ) -r 1 (1)
where r n ∈ p and

τ n = last(F n ). f1,1 r1,1 r1,2 r3,1 r3,2 r3,3 r2,1 r2,2 r2,3 r2,4 τ3 τ2 τ1 L(F3, r1 ,1)
L(F2, r2,3)

(a) Task τ1 finishes at f1,1.

f 1,1 r1,1 r1,2 r3,1 r3,2 r3,3 r2,1 r2,2 r2,3 r2,4 τ3 τ2 τ1 L(F3, r1,1) L(F2, r2 ,2)
(b) Task τ1 finishes at f 1,1 .

Latency analysis

In this section, we present a method for computing the maximum latency of the data chains of real-time periodic tasks [START_REF] Kloda | Latency analysis for data chains of real-time periodic tasks[END_REF]. First, we characterize the time durations between the releases of a task that writes the data and the next task in the chain that reads this data. Given a data arrival time, we construct a sequence of releases of the tasks propagating the data from the first to the last task in the chain (data propagation path). Then, to obtain the worst-case latency, we examine all possible data arrival time instants over the hyperperiod.

The latest data propagation time

We characterize the longest delay in data passing for a pair of directly communicating tasks. Given a release time of the task propagating data (producer), we find the latest possible release time instant of the task that reads this data for the first time (consumer).

In the example shown in Figure 3, there are two instances of task τ 2 that can propagate the data. Figure 3 a) shows the inter-task data passing when τ 1 finishes at f 1,1 (suppose that f 1 (r 1,1 ) = f 1,1 ) and the data is consumed by τ 2 released at r 2,3 . Figure 3 b) corresponds to the case when τ 1 finishes at f 1,1 (f 1,1 < f 1,1 ) and the data is consumed by τ 2 released at r 2,2 (r 2,2 < r 2,3 ). Task τ 2 instance that consumes the data propagates it further to τ 3 . In this example, the data from τ 1 can be propagated to τ 3 by the instances of τ 2 released at r 2,2 or r 2,3 . The time instant r 2,3 is the latest possible release of τ 2 that can propagate the data.

Let F 2 be a data chain of two communicating tasks: producer τ p and consumer τ c having respectively periods T p and T c . The producer, at the end of its execution, fills the input register of the consumer with the result of its computation. Let r c be the latest release time of the consumer job that has for the first time in its register the data written by the producer released at r p .

First, suppose that the consumer has a higher priority than the producer: π(τ c ) > π(τ p ). Figure 4 illustrates a sample execution of such two tasks. Due to the priority order, consumer τ c can preempt producer τ p . The consumer checks for the data at each release but the data cannot be written into the register before the end of the producer execution. The consumer instance released immediately after the end of the producer reads the data for the first time. At worst, the producer finishes at f p (r p ), and the data is read by the earliest consumer instance released after f p (r p ):

r c = f p (r p ) T c T c (2)
Now, suppose that the producer has a higher priority than the consumer: π(τ p ) > π(τ c ). Suppose also that the task set contains a third task τ h which is not part of the chain. Task τ h has the highest priority, π(τ h ) > π(τ p ) > π(τ c ), and its period is equal to the consumer period, T h = T c . A sample execution of such three tasks is shown in Figure 5. The consumer has a lower priority and cannot preempt the producer. Suppose that the producer and the consumer are:

a) released at the same time (see time instant r p,a in Figure 5): Due to the priority order, the consumer waits until the producer completes its execution.

Then, it gets the data without any delay when starting its execution.

b) not released at the same time (see time instant r p,b in Figure 5): If not blocked by the higher priority jobs (e.g., by the second instance of task τ h having an execution time shorter than its worst-case value, the difference is illustrated by the dashed area), the consumer starts before the current producer instance and reads the data written in its register by the previous producer instance. The data written by the current producer instance will be made available for the next consumer instance.

At worst, the data is read for the first time by the first consumer instance released at or after the release of producer:

r c = r p T c T c (3)
Lemma 1. In a schedulable task set with two communicating tasks τ p and τ c such that τ p writes the results of its computation to the register of τ c , the latest possible release r c of the instance of τ c reading for the first time the data propagated by the instance of τ p released at r p ∈ A(τ p ) is given by:

r c =          f p (r p ) T c T c if π(τ p ) < π(τ c ) r p T c T c if π(τ p ) > π(τ c ) (4)
where T p and T c are periods of τ p and τ c , respectively.

The longest data propagation path

We characterize the data propagation path that gives a maximum latency value. A data propagation path in which the data propagation occurs for each task as late as possible and each task can attain its worst-case job response times, leads to the maximum latency. For example, the data path shown in Figure 3 a) satisfies the conditions mentioned above. The value of its latency is maximal. Propagating the data earlier, as for the data path from Figure 3 b), cannot increase the latency.

If such a path cannot be constructed in the schedule, then its latency value cannot be lower than the actual value of the latency given by some realizable path.

Lemma 2. For any data chain of n ≥ 1 schedulable tasks, the data propagation path p in which each task instance that propagates the data is released as late as possible, and each task instance can terminate at its worst-case finishing time, gives the maximum latency.

The proof of Lemma 2 is reported in Appendix.

Method for latency computation

We compute the maximum latency value for a data chain of n ≥ 1 tasks by finding the latest possible releases of the tasks that consume the data.

Consider a data chain of n tasks released at r 1 . The first task of the data chain is a producer, and the second task is a consumer. We find the latest release time instant of the consumer using Equation (4). Then, the second task becomes the new producer, and the third task the new consumer. The release of the producer is the release of the previous consumer, and the same reasoning as for the first two tasks is applied. The method continues in like manner for every successive pair of the chain tasks and can be implemented in a recursive manner.

Consider again Figure 3 and data chain F 3 with τ 1 released at r 1,1 and completed at f 1,1 . The maximum latency L(F 3 , r 1,1 ) can be expressed as L(F 3 , r 1,1 ) = r 2,3 +L(F 2 , r 2,3 )-r 1,1 where F 2 is a data chain composed of τ 2 and τ 3 .

Theorem 1. Let F n be a data chain of n ≥ 2 tasks and F n-1 be a data chain of n -1 tasks obtained from F n by removing its first task τ p : F n-1 = tail(F n ). The maximum latency L(F n , r p ) of F n when its first task τ p is released at the time instant r p ∈ A(τ p ) is:

L(F n , r p ) ≥ (r c -r p ) + L(F n-1 , r c ) ( 5
)
where L(F n-1 , r c ) is the maximum latency of F n-1 whose first task τ c is released at the time instant r c given by Formula (4).

Proof. Let (r 1 , . . . , r n ) be a data propagation path obtained by the iterative application of Theorem 1. For 1 < i ≤ n, Equation (4) gives r i that is the latest possible release of τ i instance that propagates the data. By Lemma 2, a latency value of a data propagation path with the latest possible release time instants cannot be smaller than a latency value of any other data propagation path.

Algorithm 1 uses the results of Theorem 1 to compute the maximum latency of a data chain F n whose first task is released at the time instant r p . The algorithm has a linear time complexity O(n) (we suppose that the worst-case response times are known).

Algorithm 1 Data chain maximum latency at r p .

Require:

F n is a data chain, n ≥ 1, r p ∈ A(head(F n )) 1: function L(F n , r p ) 2: τ p ← head(F n ) 3: if n = 1 then 4: return R p (r p ) 5:
end if 6:

F n-1 ← tail(F n ), τ c ← head(F n-1 ), Q ← 0 7: if π(τ p ) < π(τ c ) then 8: Q ← R p (r p ) 9:
end if 10:

r c ← r p + Q T c T c 11:
return r c -r p + L(F n-1 , r c ) 12: end function

The worst-case latency

The worst-case latency can be calculated by applying the above-presented analysis for all the release time instants of the first task in the chain and by taking into account the delay of the first task sensor data detection. At the earliest, a task can start to execute at its release time (if the higher priority jobs are completed). Suppose that τ 1 , the first task in the chain, starts at r 1 ∈ A(τ 1 ), and the data arrives at the sensor immediately after its start. In that case, the data is handled by the next τ 1 instance released at r 1 + T 1 . The delay experienced by the data in the sensor register is not greater than one task period (similar reasoning is used in [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF][START_REF] Hamann | Communication Centric Design in Complex Automotive Embedded Systems[END_REF]). Then, the data travels along the data propagation path, as explained above. As there are many paths and their trajectories depend on the release time of the first task, to find the worst-case latency value all these paths must be analyzed. Given a data chain F n of n ≥ 1 tasks, the value of its worst-case latency is:

L(F n ) < T 1 + max r1∈A(τ1) L(F n , r 1 ) (6)
where τ 1 ∈ head(F n ) and T 1 is the period of τ 1 .

To compute the worst-case latency, Formula (6) must be evaluated for all releases of the first chain task (0, T 1 , 2T 1 , . . .). Using the fact that the schedule repeats cyclically every hyperperiod H [START_REF] Leung | A Note on Preemptive Scheduling of Periodic, Real-Time Tasks[END_REF], it is sufficient to check the releases of the first chain task within the interval [0, H). Moreover, since the execution of the task is not interfered by the lower priority tasks, it is sufficient to examine only the releases of the first chain task within the interval [0, H) where H = lcm { T j | τ j ∈ hep(τ i ), τ i ∈ F n }. Depending on system properties, this limit can be further reduced. If the worst-case response times of all task instances are equal, ∀k ∈ N, τ i : R i (t) = R i (t + kT i ), then it is sufficient to apply Algorithm 1 on the hyperperiod of all the tasks in the data chain

H = lcm { T i | τ i ∈ F n }.
For instance, in the analysis of task sets with harmonic periods scheduled under Rate Monotonic (RM ) all the jobs of the same task have their worst-case job response times equal [START_REF] Mohaqeqi | On the Problem of Finding Optimal Harmonic Periods[END_REF][START_REF] Xu | Harmonic Scheduling and Control Co-design[END_REF]. Such a hypothesis can also be made when the schedulability analysis provides only a single upper bound for all task jobs.

Algorithm 2 finds a maximum latency by calling the function L(F n , r 1 ), defined in Algorithm 1, for all the possible releases r 1 of the first task in the chain F n within the hyperperiod H. Then, finding the worst-case latency has an O(n • H T1 ) time complexity. The input size of the problem is bounded by O(n • log(T max )). Since the hyperperiod grows exponentially as a function of the largest task period in the task set and with the Algorithm 2 Data chain worst-case latency.

Require: F n is a data chain of n tasks, n ≥ 1

1: H ← hyperperiod of all tasks in the set,

τ 1 ← head(F n ) 2: for all r 1 ∈ {0, T 1 , 2T 1 , . . . , H -T 1 } do 3: compute L(F n , r 1 ) using Algorithm 1 4: end for 5: L(F n ) ← T 1 + max r1 L(F n , r 1 )
number of tasks [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF], finding the worst-case latency has an exponential time complexity and may be intractable. Nonetheless, in the presence of harmonic periods, the hyperperiod H is equal to the largest task period T max . Thus, finding the worst-case runs in polynomial time with respect to the numeric value of the input and has a pseudo-polynomial time complexity.

Example

Figure 6 illustrates the worst-case latency computation for a sample execution of a data chain F 3 composed of three tasks: τ 1 , τ 2 and τ 3 . The task instances that do not propagate new data are shadowed.

For the instances of task τ 1 released at time instants 0, 20 and 40, the maximum latency values are respectively L(F 3 , 0) = 16, L(F 3 , 20) = 20 and L(F 3 , 40) = 12. By adding the delay of the first task sensor data detection equal to its period (T 1 = 20) to the greatest maximum latency value (L(F 3 , 20) = 20) we obtain the worst-case latency L(F 3 ) = 40.

In this example, we always consider the worst-case job response times. If the worst-case task response times were used instead, the worst-case latency would be associated with the data path released at time instant 40 and would be equal to 44 overestimating the actual value by 10% (since R(τ 1 ) = 10, it would be considered that J 1 [START_REF] Leung | A Note on Preemptive Scheduling of Periodic, Real-Time Tasks[END_REF] propagates the data to J 2 (54)). In Section 5, we empirically evaluate the impact of the precision in the response-time analysis on the latency over-approximation.

In the data path leading to the worst-case latency, the delay in the data passing between τ 1 and τ 2 is lower than in the data path released at 0. In this schedule, there is no data path in which every pair of communicating tasks always incurs the delay that is greater than in all other data paths. Nonetheless, in the next section, we will suppose that every pair of communicating tasks can always cause the greatest possible delay to obtain a latency upper bound that can be computed in polynomial time in the input size.

Latency bound

We derive an upper bound on the worst-case latency of the data chain. This bound can be computed in polynomial-time in the input size by finding the largest time intervals between the releases of any two directly communicating tasks.

Bound derivation

We characterize a relation between the releases of two communicating real-time periodic tasks. Let τ i and τ j be two periodic tasks such that τ i writes into τ j register. If T i is the period of τ i and T j is the period of τ j , then their releases are given by r i = k i T i and r j = k j T j for any k i , k j ∈ N 0 . Based on the Bézout's identity and its implications, r j -r i = k j T j -k i T i must be multiple of gcd(T i , T j ) and every multiple of gcd(T i , T j ) can correspond to some distance between the releases of these tasks (the same reasoning is used in [START_REF] Pazzaglia | Simple and General Methods for Fixed-Priority Schedulability in Optimization Problems[END_REF][START_REF] Pellizzoni | A New Sufficient Feasibility Test for Asynchronous Real-Time Periodic Task Sets[END_REF][START_REF] Pellizzoni | Feasibility Analysis of Real-Time Periodic Tasks with Offsets[END_REF]). Consequently, in a schedule of periodic tasks without offsets, for any two tasks τ i and τ j , the following condition must be verified:

∀ (r i , r j ) ∈ A(τ i ) × A(τ j ) : gcd(T i , T j ) | r j -r i (7)
Consider first the case when the producer has a higher priority than the consumer: π(τ p ) > π(τ c ). Lemma 1 states that the data, at worst, must be processed by the first job of consumer released at or after the current producer release. As the consumer is released every T c , one of its jobs is always released within the interval [r p , r p + T c ).

if π(τ p ) > π(τ c ) : r c -r p < T c (8)
Now we consider the case when the consumer has a higher priority than the producer: π(τ c ) > π(τ p ). Lemma 1 shows that the data must be processed by the first consumer job released immediately after the end of the producer. The producer cannot take more time than R p to produce the data. Additionally, like in the previous case, the consumer needs less than T c units to get the data once it is written in its register.

if π(τ c ) > π(τ p ) : r c -r p < R p + T c ( 9
)
The length of the time interval between r p and r c can be bounded by Formulas [START_REF] Becker | Synthesizing Job-Level Dependencies for Automotive Multi-rate Effect Chains[END_REF] and [START_REF] Becker | Timing Analysis Driven Design-Space Exploration of Cause-Effect Chains in Automotive Systems[END_REF]. By the condition given in Formula ( 7), the length of this interval must be multiple of gcd(T p , T c ). Based on these properties, we can obtain an upper bound on the time interval between r p and r c . Lemma 3. Let τ p and τ c be two communicating realtime periodic tasks such that τ p writes the results of its computation to the register of τ c . The maximal distance between the release time r p of the task τ p and the release time r c of the task τ c that reads the data produced by τ p at r p for the first time is not greater than:

r c -r p ≤ q(τ p , τ c ) • R p gcd(T p , T c ) -1 gcd(T p , T c )+T c (10)
where

q(τ p , τ c ) = 1 if π(τ c ) > π(τ p ) , 0 if π(τ c ) < π(τ p ).
Proof. In order to ease the subsequent presentation, we introduce the variable X = q(τ p , τ c ) • R p (r p ). Equation (4) can be rewritten as:

r c = r p + X T c T c
The following relation must be satisfied:

r p + X T c T c < r p + X + T c T c T c ≤ r p + X + T c
The value of r c -r p can be therefore bounded by:

r c -r p = r p + X T c T c -r p < X + T c (11)
Time instant r p is a multiple of T p , and time instant r c is a multiple of T c . Their greatest common divisor gcd(T p , T c ) divides both instants, and thus there must exist k, k ∈ N 0 such that r p = k gcd(T p , T c ) and

r c = k gcd(T p , T c ). Consequently, r c -r p = (k -k) gcd(T p , T c
) is also a multiple of gcd(T p , T c ). The greatest multiple of gcd(T p , T c ) satisfying the right-hand side of Expression [START_REF] Bini | Biasing effects in schedulability measures[END_REF] can be used as a bound for r c -r p .

r c -r p ≤ X + T c gcd(T p , T c ) -1 gcd(T p , T c )
T c is divisible by gcd(T p , T c ).

r c -r p ≤ X gcd(T p , T c ) -1 gcd(T p , T c ) + T c
Finally, if π(τ p ) < π(τ c ) then X = q(τ p , τ c ) • R p (r p ) = 0 and we get Formula [START_REF] Bello | Recent Advances and Trends in On-Board Embedded and Networked Automotive Systems[END_REF]. Otherwise, if π(τ p ) > π(τ c ) then X = q(τ p , τ c ) • R p (r p ) ≤ q(τ p , τ c ) • R p and we get Formula (10) as well.

Bound computation and its time complexity

Algorithm 3 computes the upper bound on the worst-case latency of a data chain. Its running time is linear in the number of tasks in the chain. The greatest common divisor is calculated with the Euclidean algorithm. According to Lamé's Theorem, the number of steps in the Euclidean algorithm never exceeds five times the number of digits in the smaller number [START_REF] Honsberger | Mathematical Gems II[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF]. If T max is the maximal period among all periods T 1 , . . . , T n , then the worst-case complexity of the Euclidean algorithm applied to any pair of these periods is not greater than 5 • log 10 (T max + 1) . Thus, the overall running time of Algorithm 3 is bounded by O(n•5• log 10 (T max + 1) ) which is polynomially bounded Algorithm 3 Data chain worst-case latency upper bound. Require:

F n is a data chain, n ≥ 1 Ensure: L ≥ L(F n ) 1: L ← T 1 2: for i ← 1, n -1 do 3: τ p ← τ i , τ c ← τ i+1 4: L ← L + T c -gcd(T p , T c ) 5: if π(τ c ) > π(τ p ) then 6: L ← L + R p gcd(T p , T c ) gcd(T p , T c ) 7:
end if 8: end for 9: L ← L + R n in the input length. Note that the algorithm complexity is independent of the response time analysis as it assumes that the worst-case response times are known. Indeed, the algorithm can be combined with the response time analyses characterized with different complexities and with different precisions. The experiments performed in the following section try to find a trade-off between complexity and accuracy of the response time analysis.

Bound tightness

The bound can overestimate the value of the worst-case latency given by the method described in the previous section. In the following, we review several causes of this pessimism.

First, the bound considers that every task instance can reach the worst-case task response time: ∀τ i ∀t ≥ 0 : R i (t) = R i . Second, the bound may consider schedules than cannot exist: Formula (10) seeks the maximum distance between the releases of two consecutive tasks within the chain, but it does not check if this distance is in accordance with other releases of the tasks in this chain. More precisely, given any two tasks in the chain τ i and τ j , the condition given by Formula (7) is verified only for i and j = i + 1 but in the valid schedule it must be verified for all other j : 1 ≤ j ≤ n (e.g., when computing the bound and n ≥ 3, then the relation is never checked between the releases of τ 1 and τ n ).

The bound from Lemma 3 gives a time interval between the releases of two consecutive tasks of a data chain. Let ∆ k,k+1 ≥ 0 be such a time interval between the releases of tasks τ k and τ k+1 for k ≥ 1. Therefore, the time interval between the releases of any two tasks τ i and τ j of this chain, such that j > i ≥ 1, is given by ∆ i,j = j-1 k=i ∆ k,k+1 . All the values calculated in this way, for all i, j ≤ n, must satisfy Condition [START_REF] Becker | MECHAniSer-A Timing Analysis and Synthesis Tool for Multi-Rate Effect Chains with Job-Level Dependencies[END_REF] if the results of applying bound from Lemma 3 correspond to a schedule that can be actually observed. Otherwise, the results are overestimated by considering a schedule that cannot exist. Lemma 3, for tasks τ k and τ k+1 within a data chain, gives a time interval that is a multiple of gcd(T k , T k+1 ) (see Equation [START_REF] Bello | Recent Advances and Trends in On-Board Embedded and Networked Automotive Systems[END_REF]). The time interval between the releases of τ i and τ j , calculated as it is explained above, can be expressed as divisor, it can be shown that ∆ i,j = x i gcd(T i , T i+1 ) + . . . + x j-1 gcd(T j-1 , T j ) is a multiple of gcd(T i , . . . , T j ). Now, suppose that the following relation holds for all the tasks:

∆ i,j = j-1 k=i x k gcd(T k , T k+1 ) where x k ∈ N 0 .
τ 3 τ 2 τ 1 L(F 3 ) = 14
∀ i, j ≤ n : gcd(T i , T j ) = gcd(T i , . . . , T j ) (12)
then the Condition ( 7) is satisfied, and it can be concluded that Lemma 3 yields the time intervals from which a valid schedule can always be constructed. The condition given in Formula ( 12) is not always satisfied by harmonic periods. Indeed, consider the worstcase latency of the data chain shown in Figure 7. The chain is composed of three tasks τ 1 , τ 2 , and τ 3 with harmonic periods and priorities assigned according to RM scheduling policy. The task set parameters are described in Table 1. The Condition ( 12) is not satisfied in that case as gcd(T 1 , T 3 ) = gcd(T 1 , T 2 , T 3 ) (i.e. 4 = 2).

Table 1: Task parameters for the example from Figure 7.

Task T i C i π(τ i ) τ1 8 1 1 τ2 2 1 3 τ3 4 1 2
We assume that the input data arrives right after the time instant 0 (this part of the schedule is skipped in Figure 7). The actual value of the worst-case latency is 14. The value of the worst-case latency calculated with Algorithm 3 is equal to 16. The algorithm overestimates the actual value of latency when considering the data passing between the tasks τ 2 and τ 3 . It assumes the worst-case delay is equal to 2 while, in reality, this delay is always 0.

Under certain assumptions, the bound can be less pessimistic or can even give the same value of the worstcase latency as the method described in Section 3. If the chain is composed of two tasks only, τ 1 and τ 2 , then the distance between the task releases given by Formula (10) corresponds always to a valid schedule: the distance is multiple of gcd(T 1 , T 2 ) and this is the only condition required by Formula [START_REF] Becker | MECHAniSer-A Timing Analysis and Synthesis Tool for Multi-Rate Effect Chains with Job-Level Dependencies[END_REF]. The same follows if all the task periods in the chain are equal: ∀i, j ≤ n : T i = T j . Another source of pessimism comes from considering for each task instance its worst-case task response time as its worst-case job response time. However, as mentioned in the previous section, under certain conditions, like in the harmonic schedules under RM, this is actually the case.

Experiments

In this section, we evaluate the performance of the worstcase latency analysis [START_REF] Kloda | Latency analysis for data chains of real-time periodic tasks[END_REF] summarized in Section 3 and of the polynomial-time upper bound on the latency presented in Section 4 in terms of precision and practical complexity on a generic automotive benchmark [START_REF] Kramer | Real World Automotive Benchmark For Free[END_REF] upon a single processor.

We compare these two methods against a linear-time upper bound on the worst-case latency proposed by Davare et al. [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF]. In principle, the latter method applies for sporadic tasks, but its use may also be advantageous for the periodic tasks due to its linear time-complexity. As the tasks are uncoordinated, the producer τ p may write the data into the register of the consumer task τ c immediately after its start. It induces a maximum delay of T c + R c for each pair of producer/consumer. The worst-case latency for a chain of n tasks F n is expressed as:

L(F n ) = n i=1 (T i + R i ).
The algorithms described in this work are available on-line 2 through a Python implementation with which experiments presented below are fully reproducible.

Chain generation

Data chains are made of tasks picked from a set of 50 tasks. Task parameters are generated based on the automotive benchmark [START_REF] Kramer | Real World Automotive Benchmark For Free[END_REF]. Periods are randomly chosen from the set {1, 2, 5, 10, 20, 50, 100, 200, 1000} with a probability of appearance taken from [START_REF] Kramer | Real World Automotive Benchmark For Free[END_REF]. The utilization of task τ i is generated using the UUnifast [START_REF] Bini | Biasing effects in schedulability measures[END_REF] algorithm and then multiplied by the chosen period T i giving C i . We consider RM scheduling policy and discard unschedulable task sets. To focus on chain length only for Figures 8a, 8b and 8c, we successively decrease the chain length in such a way that the number of distinct periods remains respected.

Analysis and bounds precision

We evaluate the precision of the analysis and bound respectively described in Section 3 and 4 as well as the bound of Davare et al. [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF]. They require worst-case response time (WCRT) information. In Figure 8, we compare the results varying the precision of the method used to obtain WCRT. We study the impacts of the chain length and of the number of distinct periods in the chain on the latency. For each task instance of τ i released at r i,j ∈ A(τ i ), we use the following methods to safely estimate its job WCRT R i (r i,j ):

• SimSo simulator [START_REF] Chéramy | SimSo: A Simulation Tool to Evaluate Real-Time Multiprocessor Scheduling Algorithms[END_REF] for its exact value;

• exact schedulability test [START_REF] Joseph | Finding Response Times in a Real-Time System[END_REF] for R i and then R i (r i,j ) = R i (R i , circles);

• sufficient schedulability test [START_REF] Neil C Audsley | Real-time scheduling: the deadline-monotonic approach[END_REF] for an upper bound on R i and thus it is considered that R i (r i,j ) is equal to this bound (sufficient R i , squares);

2 www.lias-lab.fr/~antoinebertout/software/latency.zip

• no response time information, R i (r i,j ) is bounded by T i (R i = T i , triangles).

In Figures 8a, 8b and 8c, results are averaged for a given task set utilization factor u and a chain length. Utilization factors are selected from the set {0.25, 0.5, 0.75} and the number of distinct periods from 1 to 5. In Figure 8d, results are averaged for a given number of distinct periods p, and u is set to 0.75. Each experiment was repeated 10000 times. In all the plots of Figure 8, the latency computed using Algorithm 1 corresponds to a precision ratio of 100% on the y-axis. A precision ratio is equal to:

L with estimated WCRT L with Algorithm 2 • 100% (13)
In our experiments, the worst-case latency calculated with the worst-case job response times R i (r i,j ) is equal to the worst-case latency calculated with the worst-case task response times R i with a tolerance of 10 -3 (and thus not represented in Figure 8a). Indeed, as task periods are quasi-harmonic, most of the task instances verify R i (r i,j ) = R i under RM scheduling (see also Section 3.4).

We record the following observations:

• the proposed polynomial-time upper bound on latency, represented in Figure 8b (based on worstcase task response time R i ), has a maximum overestimation of 10% of the worst-case latency computed with the exponential method presented in Section 3; considering the gap on the theoretical complexity, the pessimism introduced is very limited;

• to obtain the polynomial-time complexity of both, the response time and the latency analysis, the proposed polynomial-time upper bound can be combined with the utilization based schedulability tests [START_REF] Bini | A Hyperbolic Bound for the Rate Monotonic Algorithm[END_REF][START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment[END_REF]; the over-estimation of the worst-case latency is then about 80% of the worst-case latency computed with the exponential method (R i = T i ).

• for a similar theoretical complexity, the upper bound we propose (based on R i ) is more accurate than the method of Davare et al. of Figure 8c;

• the chain length has the effect of decreasing the pessimism of the worst-case job response time approximation (Figure 8a) while it remains quite stable for the bound (Figure 8b) and slightly increases for the method of Davare et al. (Figure 8c);

• the precision of the upper bound on latency decreases when the number of distinct periods increases (Figure 8d) because the bound is sensitive to the gcd of the tasks periods; as pointed out in Section 4, the upper bound on R i is exact with equal periods in the chain;

• globally, the more precise the worst-case job response time approximation, the better precision of the bound.

Figure 9: number of paths explored by the different latency computation methods.

Computational complexity

As explained in Section 3.4, the exact method evaluates one data propagation path per each release of the first task in the chain in H and has an O(n• H T1 ) time complexity. We also proposed in Section 3.4 to use as a limit the hyperperiod of the chain tasks H(F n ) if the worst-case task response times only are available.

Figure 9 shows the average number of data propagation paths traversed by each method as a function of the number of distinct periods in the chain. For each number of the distinct periods, the chains with every possible period combination (with replacement) were considered. As expected, we observe that our upper bound and the method of Davare (lines are overlaid) are the most efficient. The worst-case latency computation with the method described in Algorithm 2 must process, respectively, more than 300 and more than 600 data propagation paths with the worst-case task response times and with the worst-case job response times.

Related work

We survey related work on the latency computation for the periodic real-time task and similar models.

Harmonic periods. Gerber et al. [START_REF] Gerber | Guaranteeing end-to-end timing constraints by calibrating intermediate processes[END_REF][START_REF] Gerber | Guaranteeing Real-Time Requirements With Resource-Based Calibration of Periodic Processes[END_REF] consider a task chain with harmonicity constraint (i.e., periods that pairwise divide each other [START_REF] Han | A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms[END_REF]) and enforce by the offset and priority assignment that the producer always executes before the consumer. Di Natale et al. [START_REF] Di | Architecture Exploration for Time-Critical and Cost-Sensitive Distributed Systems[END_REF] and Davare et al. [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF] specify the general case when producer and consumer have harmonic periods without being necessarily monotonic in their lengths over the entire chain. They assume additionally that the relative offsets are selected to enforce the execution of the producer before the consumer. In the present work, there are no particular constraints neither on the task periods nor on the relative offsets.

Uncoordinated tasks. Davare et al. [START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF] also consider periodic tasks. The proposed method for the worst-case latency computation has a linear-time complexity. However, as the tasks are running on different nodes without a consistent view of time (no clock synchronization), the assumed worst-case behavior is more pessimistic than in the case of periodic tasks running on a single processor as supposed in this paper.

Periodic task model. Feiertag et al. [START_REF] Feiertag | A Compositional Framework for End-to-End Path Delay Calculation of Automotive Systems under Different Path Semantics[END_REF] and Mubeen et al. [START_REF] Saad Mubeen | Support for End-to-End Response-Time and Delay Analysis in the Industrial Tool Suite: Issues, Experiences and a Case Study[END_REF] develop frameworks for the computation of different types of latencies under the same model as in the present work. In [START_REF] Becker | Analyzing End-to-End Delays in Automotive Systems at Various Levels of Timing Information[END_REF] Becker et al. propose a method for the worst-case latency computation using the information about the worst-case response times of the tasks. The authors develop an effective pruning technique to reduce the number of analyzed points in an inter-task communication tree. Following on from these works, we use the scheduling information (priority, response time) to identify directly with a closed-form expression the communication time instant leading to the maximum latency. None of these algorithms runs faster than exponential time. In this paper, we tackle their computational complexity by proposing an upper bound that can be computed in a polynomial-time. Rajeev et al. [START_REF] Rajeev | Schedulability and End-to-end Latency in Distributed ECU Networks: Formal Modeling and Precise Estimation[END_REF] and Anwikar and Badhuri [START_REF] Anwikar | Timing analysis of real-time embedded systems using model checking[END_REF] consider distributed systems in which chains are composed of preemptive tasks and non-preemptive messages. The systems are represented by a set of automata, and then the latencies are obtained using a model-checking based technique. Khatib et al. [START_REF] Khatib | Computing Latency of a Realtime System Modeled by Synchronous Dataflow Graph[END_REF] use Synchronous Data-flow Graphs to model the communications between multi-periodic tasks. It is assumed that each task instance starts exactly at its release. A method for the latency computation, as well as a lower and an upper bound on its value, are proposed. Our model is based on the real-time periodic task whose start does not necessarily coincide with its release.

Abstract models. Wyss et al. [START_REF] Wyss | Propriétés de latence, fraîcheur et réactivité dans un programme synchrone multi-périodique[END_REF][START_REF] Wyss | End-to-end Latency Computation in a Multi-periodic Design[END_REF] present an analysis of the end-to-end latencies for a formal language with synchronous semantics named Prelude [START_REF] Forget | A Real-time Architecture Design Language for Multi-rate Embedded Control Systems[END_REF][START_REF] Pagetti | Multi-task Implementation of Multi-periodic Synchronous Programs[END_REF]. The data propagation in a functional chain is expressed by "a data dependency word" [START_REF] Forget | Verifying end-to-end real-time constraints on multi-periodic models[END_REF][START_REF] Pagetti | Multi-task Implementation of Multi-periodic Synchronous Programs[END_REF]. Biondi et al. [START_REF] Biondi | Achieving Predictable Multicore Execution of Automotive Applications Using the LET Paradigm[END_REF] and Martinez et al. [START_REF] Martinez | End-to-end latency characterization of implicit and LET communication models[END_REF] address the problem of end-to-end latency for the tasks based on the Logical Execution Time model on multicores. Martinez et al. [START_REF] Martinez | End-to-end latency characterization of implicit and LET communication models[END_REF] introduce also the formulas for the latency computation of sporadic tasks with the implicit communication model. In this work, we also consider the implicit communication, but the tasks activation pattern is periodic. Becker et al. [START_REF] Becker | End-to-End Timing Analysis of Cause-Effect Chains in Automotive Embedded Systems[END_REF][START_REF] Becker | MECHAniSer-A Timing Analysis and Synthesis Tool for Multi-Rate Effect Chains with Job-Level Dependencies[END_REF][START_REF] Becker | Synthesizing Job-Level Dependencies for Automotive Multi-rate Effect Chains[END_REF] analyze different types of the end-to-end latencies for periodic tasks in abstraction from a concrete scheduling policy as well as for the static off-line schedules [START_REF] Becker | Analyzing End-to-End Delays in Automotive Systems at Various Levels of Timing Information[END_REF][START_REF] Becker | End-to-End Timing Analysis of Cause-Effect Chains in Automotive Embedded Systems[END_REF]. The authors propose an algorithm for an automatic generation of the job-level dependencies guaranteeing that imposed latency constraints are met. The task model in the present paper assumes that the schedule is not static as the tasks' execution times may vary from one task instance to another.

Trigger chains. While this paper studies the data chains, there is also a large body of literature on the trigger chains that are subject to various end-to-end constraints. The holistic analysis [START_REF] Tindell | Holistic Schedulability Analysis for Distributed Hard Real-time Systems[END_REF] applies to the tasks whose execution can be triggered by the arrival of a message or by the completion of a preceding task. Schlatow and Ernst [START_REF] Schlatow | Response-Time Analysis for Task Chains in Communicating Threads[END_REF] propose an upper bound on the end-to-end latency of task chains with synchronous and asynchronous communicating threads.

Multiframe. The multiframe model [START_REF] Baruah | Generalized Multiframe Tasks[END_REF][START_REF] Mok | A multiframe model for real-time tasks[END_REF] or transaction tasks [START_REF] Pellizzoni | Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling[END_REF][START_REF] Rahni | Feasibility Analysis of Real-time Transactions[END_REF][START_REF] Traore | Characterization and Analysis of Tasks with Offsets: Monotonic Transactions[END_REF] generate cyclically a fixed sequence of different jobs according to a predefined time pattern. They can also be used to express the sequential execution of communicating jobs. However, they do not consider that a job could transfer the data to two or more jobs (linear model [START_REF] Gutiérrez | Schedulability analysis of distributed hard real-time systems with multiple-event synchronization[END_REF][START_REF] José | On the schedulability analysis for distributed hard real-time systems[END_REF]) and the delay between the releases of two directly communicating jobs must be constant or upper-bounded by a constant value. In the data chains, this delay can vary from one task instance to another, and the same task can be involved in multiple data flows.

CAN messages. Di Natale et al. [START_REF] Di | Understanding and Using the Controller Area Network Communication Protocol: Theory and Practice[END_REF] propose a method for the evaluation of the worst-case latency for mixed chains of real-time tasks and Controller Area Network (CAN) messages. Zeng et al. [START_REF] Zeng | Probabilistic Timing Analysis of Distributed Real-time Automotive Systems[END_REF][START_REF] Zeng | Stochastic Analysis of CAN-Based Real-Time Automotive Systems[END_REF][START_REF] Zeng | Statistical analysis of Controller Area Network message response times[END_REF] describe the use of statistical analysis to compute the probability distribution of end-to-end latencies for CAN message chains. In this work, we consider that a task can be preempted at any point during its execution and we analyze the effects of the preemption on the latency.

Conclusion

In this paper, we proposed a polynomial-time upper bound on the worst-case latency of data chains. We showed with benchmark based on the automotive application that the use of the proposed bound can disentangle the complexity of the worst-case latency estimation with little loss in terms of precision. The bound lays the groundwork for solving several problems in software engineering of real-time systems like, for instance, task periods and priorities assignment optimization under latency constraints [START_REF] Becker | Timing Analysis Driven Design-Space Exploration of Cause-Effect Chains in Automotive Systems[END_REF][START_REF] Davare | Period Optimization for Hard Real-time Distributed Automotive Systems[END_REF][START_REF] Deng | An Efficient Control-Driven Period Optimization Algorithm for Distributed Real-Time Systems[END_REF][START_REF] Klaus | Data Propagation Delay Constraints in Multi-Rate Systems: Deadlines vs. Job-Level Dependencies[END_REF][START_REF] Krawczyk | Model-Based Timing Analysis and Deployment Optimization for Heterogeneous Multi-core Systems using Eclipse APP4MC[END_REF][START_REF] Zhao | A Unified Framework for Period and Priority Optimization in Distributed Hard Real-Time Systems[END_REF]. chain such that r 1 = r 1 . First, we prove by induction that ∀i 1 ≤ i ≤ n : r i ≤ r i . Base case (i = 1). By definition r 1 ≤ r 1 . Induction step (1 < i ≤ n). By the induction hypothesis: r i ≤ r i . Since the chain's tasks are schedulable and have their deadlines equal to their periods, every task instance must finish before the release of its next instance. If τ i is released before r i at r i < r i , then it executes within the interval [r i , r i + T i ] and must finish before r i . It fills the input register of τ i+1 with the results of its computation before r i . The instance of task τ i released at r i executes within the interval [r i , r i + T i ] and fills the register of τ i+1 with the results of its computation after r i . Consequently, no instance of τ i released at r i ≤ r i can write into the register of τ i+1 at a later time than τ i released at r i does. Hence, if task τ i+1 released at r i+1 has already data from τ i released at r i , then the earlier or the same instance of τ i+1 must have the data from τ i released at r i : r i+1 ≤ r i+1 .

From the definition of maximum latency given by Equation (1), the lemma statement holds iff:

f n (r n ) ≤ f n (r n ).
The LHS of the previous expression gives a finishing time of task τ n released at r n ≤ r n and RHS a finishing time of the same task released at r n . If r n = r n , then f n (r n ) = f n (r n ) and the statement is clearly true. Otherwise, if r n < r n , then by the same reasoning as in the induction part, every task instance must finish before the release of its next instance, and it follows that f n (r n ) < f n (r n ).

Figure 1 :

 1 Figure 1: Flight Management System software architecture.

Sensor

3 ActuatorFigure 2 :

 32 Figure 2: Register-based communication in a data chain of three tasks τ 1 , τ 2 , and τ 3 .

Figure 3 :

 3 Figure 3: Two possible execution scenarios of a data chain of three tasks: τ 1 , τ 2 , and τ 3 .

Figure 4 :

 4 Figure 4: Communicating tasks: consumer τ c has a higher priority than producer τ p .

Figure 5 :

 5 Figure 5: Communicating tasks: producer τ p has a higher priority than consumer τ c .

Figure 6 :

 6 Figure 6: Maximum latency computation for the data chain F 3 of three tasks τ 1 , τ 2 and τ 3 with the following parameters: (C 1 = 5, T 1 = 20, π(τ 1 ) = 1), (C 2 = 1, T 2 = 6, π(τ 2 ) = 3) and (C 3 = 3, T 3 = 12, π(τ 3 ) = 2).

Figure 7 :

 7 Figure 7: Latency bound overestimation for a data chain of three tasks with harmonic periods under RM.

  From the properties of the greatest common

	8	9	10	11	12	13	14	15	16
	8	9	10	11	12	13	14	15	16
	8	9	10	11	12	13	14	15	16

See[START_REF] Durrieu | Predictable Flight Management System Implementation on a Multicore Processor[END_REF][START_REF] Pagetti | Programming mutli/many-core COTS for critical embedded systems[END_REF] for a more detailed description. The interesting examples of the automotive systems with similar data processing structure can be found in Chapter 4 of[START_REF] Di | Understanding and Using the Controller Area Network Communication Protocol: Theory and Practice[END_REF] and in[START_REF] Becker | Synthesizing Job-Level Dependencies for Automotive Multi-rate Effect Chains[END_REF].

Acknowledgments

Tomasz Kloda was supported by the Chair for Cyber-Physical Systems in Production Engineering at TUM and the Alexander von Humboldt Foundation.

Appendix

Proof of Lemma 2. Let p = (r 1 , . . . , r n ) and let r 1 , . . . , r n be the release time instants of the consecutive instances of tasks that propagate the data such that each instance is released as late as possible and can terminate at its worst-case finishing time. Now suppose that p = (r 1 , . . . , r n ) is an arbitrary path of the same