Tomasz Kloda
email: tomasz.kloda@unimore.it

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

Yves Sorel
email: yves.sorel@inria.fr

Latency analysis for data chains of real-time periodic tasks

A data chain is a sequence of periodic realtime communicating tasks that are processing the data from sensors up to actuators. It determines an order in which the tasks propagate data but not in which they are executed: inter-task communication and scheduling are independent. In this paper, we focus on the latency computation, considered as the time elapsed from getting the data from an input and processing it to an output of a data chain. We propose a method for the worst-case latency calculation of periodic tasks' data chains executed by a partitioned fixed-priority preemptive scheduler upon a multiprocessor platform. As far as we know, there is no such formal approach based on closed-form expression for communicating real-time tasks.

I. Introduction

An embedded real-time system must react to its surroundings by sensing, computational processing and actuating upon external events within strict timing constraints. In large and complex industrial systems, different tasks process in a specific order the data before the final results can be delivered to the actuators. From a sensor to an actuator, a specific chain of tasks is involved in the computational processing.

Task chains. A task chain is a sequence of communicating tasks in which every task receives the data from its predecessors [START_REF] Mubeen | Support for endto-end response-time and delay analysis in the industrial tool suite: Issues, experiences and a case study[END_REF]. According to the activation rule, two models are commonly distinguished: trigger and data chains. Tasks in the trigger chains are activated by the events issued from the preceding tasks. In the data chains, the tasks are independent and are activated recurrently at their individual rates.

Trigger chains are characterized by a more flexible timing behavior. Tasks of the same chain execute only if necessary: a task is scheduled only if it receives the request from its predecessor. It results in a more efficient use of the processor resources and a more reactive inter-task data passing. To impose the precedence between subsequent tasks, trigger chains require task synchronization (e.g., semaphores). The use of the synchronization primitives can lead to priorityinversion problems and possible deadlock formations [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF], [START_REF] Schlatow | Response-time analysis for task chains in communicating threads[END_REF]. An additional effort is needed for the integration of these primitives together with adequate control structures. On top of that, as safety-critical software is subject to stringent safety standards, adding these features to the system makes the certification process more burdensome [START_REF] Forget | Scheduling dependent periodic tasks without synchronization mechanisms[END_REF].

Data chains are not synchronized and follow a strict activation pattern. Tasks are released at every period even if there is no new data to consume. Certain delay of time can elapse from the instant when the precedent task produces the data and the instant when the current task is released and can consume it. However, especially in large industrial applications, data chains may be preferred over trigger chains. Their unrestrained execution model can permit to reduce time and cost overheads related to the implementation and validation of synchronization mechanisms needed for trigger chains.

Task chain latency. Real-time systems comprised of task chains are subject to different timing requirements. 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 them as follows. Reactivity (or data reaction [START_REF] Mubeen | Support for endto-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 a data must be present at the sensor input in order to be detected. Latency is a time interval elapsed between arrival of data at the sensor input and actuator's update with value corresponding to that particular data (i.e., 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 data instance is in use.

Contribution. In this work, we focus on the computation of the worst-case latency for data chains. Given a data chain of periodic independent tasks with implicit deadlines scheduled by a fixed-priority preemptive partitioned algorithm upon identical multiprocessor platforms, a priority assignment of these tasks and the worst-case response times of their jobs, we propose a method for the computation of the data chain worst-case latency. We sketch simple algorithms for an easy and efficient implementation of the proposed method on top of any response time analysis tool.

Paper structure. The paper is organized as follows. In the next section we review related work. The data chain model is defined and hypotheses are made in Section III. A method for the calculation of the worst-case latency of data chains is presented in Section IV. In Section V we evaluate our method using the generic task sets based on a real-world automotive system and in Section VI we conclude the paper.

II. Related work

Davare et al. [START_REF] Davare | Period optimization for hard realtime distributed automotive systems[END_REF] propose period and priority assignment technique for the periodic tasks running on different nodes without consistent view of time (no clock synchronization).

Gerber et al. [START_REF] Gerber | Guaranteeing end-to-end timing constraints by calibrating intermediate processes[END_REF], [START_REF]Guaranteeing real-time requirements with resource-based calibration of periodic processes[END_REF] consider a task chain with harmonicity constraint and enforce by the offset and priority selection that the producer task executes always before the consumer task. Di Natale et al. [START_REF] Natale | Architecture Exploration for Time-Critical and Cost-Sensitive Distributed Systems[END_REF] and Davare et al. [START_REF] Davare | Period optimization for hard realtime distributed automotive systems[END_REF] specify the general case when the 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.

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] Mubeen | Support for endto-end response-time and delay analysis in the industrial tool suite: Issues, experiences and a case study[END_REF] developed frameworks for the computation of different latencies under the same model as in the present work upon a single processor. The framework presented in [START_REF] Mubeen | Support for endto-end response-time and delay analysis in the industrial tool suite: Issues, experiences and a case study[END_REF] is a part of Rubus-ICE tool suite used for the development of automotive systems and handles also other message passing abstractions typical for this kind of systems (e.g., CAN messages). Both frameworks compute all the reachable paths while in our work we propose a closed-form expression (Lemma 1) that identifies directly the one that gives a maximum latency. 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] use model-checking based techniques to analyze latencies in the distributed systems in which chains are composed of preemptive tasks and non-preemptive messages. Khatib et al. [START_REF] Khatib | Computing latency of a real-time system modeled by synchronous dataflow graph[END_REF] use Synchronous Data-flow Graph to model the communications between multi-periodic tasks that start exactly at their releases.

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 Prelude [START_REF] Forget | A real-time architecture design language for multi-rate embedded control systems[END_REF]. The data propagation in functional chain is expressed by a data dependency word [START_REF] Forget | Verifying end-to-end realtime constraints on multi-periodic models[END_REF].

Becker et al. [START_REF] Becker | Synthesizing job-level dependencies for automotive multi-rate effect chains[END_REF]- [START_REF]End-to-end timing analysis of cause-effect chains in automotive embedded systems[END_REF] analyze the end-to-end latency for periodic tasks in abstraction from a concrete scheduling policy, for the static off-line schedules [START_REF]End-to-end timing analysis of cause-effect chains in automotive embedded systems[END_REF], [START_REF]Analyzing end-to-end delays in automotive systems at various levels of timing information[END_REF] and also using the knowledge of the worst-case response times of the tasks [START_REF]Analyzing end-to-end delays in automotive systems at various levels of timing information[END_REF]. The framework presented in [START_REF]Analyzing end-to-end delays in automotive systems at various levels of timing information[END_REF] is versatile and can be applied for the most timing analysis in automotive and avionic systems on single processor like tasks with offsets and Logical Execution Time model; it also automatically generates the job-level dependencies to meet latency constraints. The method is based on the tree of all possible data propagation paths. For two communicating tasks, their communication time instant leading to maximum latency can be identified once all their previous communication time instants are generated. The approach proposed in our work uses the scheduling information (priority, response time, processor assignment) to identify directly with a closed-form expression (Equation ( 4)) the communication time instant leading to the maximum latency. The focus of our work is on multiprocessor platforms and considers that response time of a particular job is also a function of its release time. We formally validate our method by analyzing different schedules resulting from the nonconstant execution times of the tasks.

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] proposed an upper bound on the end-to-end latency of task chains implementing synchronous and asynchronous communicating threads. The multiframe model [START_REF] Mok | A multiframe model for real-time tasks[END_REF] can be used to express the sequential execution of communicating jobs. It generates cyclically a fixed sequence of different jobs according to a predefined time pattern.

III. System model

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

A. 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 by 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 , . . .}. An 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 instances of task τ i are executed upon the processor P (τ i ) (partitioned scheduling). We suppose that the task-to-processor assignment is already given. All the processors are identical and have the consistent view of time (perfectly synchronized clocks). The hyperperiod H is the least common multiple of all the tasks periods.

Tasks are scheduled upon every 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 ) that execute on P (τ 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 on 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.

B. 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 over 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 .

C. 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 . If n = 1, then τ 1 after its start reads the data from its sensor, computes its outputs and writes them 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 them, 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, tasks are scheduled according to the assigned priorities only. The same mechanism is also implemented in Cyclical Asynchronous Buffers [START_REF] Clark | Hic: an operating system for hierarchies of servo loops[END_REF]. Figure 1 illustrates a data chain F 3 of three tasks (τ 1 , τ 2 and τ 3 ) together with their registers. The communication described above assumes the readexecute-write task semantics (implicit communication [START_REF]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 be read only at the beginning of the execution and the results can be written only at its end. 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. The registers are asynchronous in the sense that they can be accessed anytime.

D. Data propagation path

Based on the concept of timed path introduced in [6] and in [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 a n-tuple (r 1 , . . . , r n ) where r i ∈ p is the release time of the task τ i instance 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 at time instant r 1 all the task registers are empty and the data is from that moment continuously present at the chain's input.

Figure 2 illustrates two different scenarios of execution of a data chain F 3 . The chain is composed of three tasks: τ 1 , τ 2 and τ 3 such that π(τ 2 ) > π(τ 3 ) > π(τ 1 ). In this figure, two data propagation paths can be distinguished for Ω(F 3 , r 1,1 ). The first one, marked with the dotted line, when τ 1 terminates at f 1,1 : (r 1,1 , r 2,2 , r 3,2 ). The second one, marked with the solid line, when τ 1 terminates later at

f 1,1 : (r 1,1 , r 2,3 , r 3,3 ) with f 1,1 > f 1,1 . f 1,1 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)

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

E. Data chain latency

Latency of a data chain is a delay between the arrival of its input and the first output corresponding to it [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 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 ), and the input of τ 1 arrives in its register at r 1 . The maximum latency of data chain F n released at r 1 is not greater than:

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 ).

IV. Latency Analysis

We propose a method for computing the maximum latency of the data chain if the input from the sensor arrives at the release of its first task and then we generalize this method for the arbitrary input arrival times to obtain the worst-case latency. First, for a task that writes the data and the next task in the chain that subsequently reads this data, we characterize the time distances between their releases. Given a data arrival time, we construct a sequence of releases of the tasks propagating this data from the first to the last task in the chain (data propagation path). Then, to obtain the worst-case latency, we expand the proposed method over all data arrival time instants.

A. The latest data propagation time

We characterize the largest 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 particular data for the first time (consumer).

In the example shown on Figure 2, there are two instances of task τ 2 that can propagate the data. The solid line represents 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 . The dashed line 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 at 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 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 higher priority than producer: π(τ c ) > π(τ p ) and is mapped to the same processor: P (τ c ) = P (τ p ). producer τ p . Consumer checks for the data at each release but the data cannot be written into the register before the end of the producer execution. Therefore, the data is read for the first time by the consumer instance released immediately after the end of the producer. 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 producer has higher priority than consumer: π(τ p ) > π(τ c ) and is still mapped to the same processor: P (τ c ) = P (τ p ). Suppose also that there is a third task τ h mapped to the same processor which is not included in the chain. Task τ h has the highest priority, π(τ h ) > π(τ p ) > π(τ c ), and its period is equal to the period of consumer, T h = T c . A sample run of such three tasks is shown in and cannot preempt producer. Suppose that producer and consumer are: a) released at the same time (see time instant r p,a in Figure 4): Due to the priority order, consumer cannot start until producer completes its execution. When it completes, it writes the data into register. Consumer can read the data at the beginning of its execution. b) not released at the same time (see time instant r p,b in Figure 4): The consumer instance released immediately before the release of producer may be blocked by the higher priority jobs until the release of producer.

In that case, it starts after the end of producer execution and reads the data. Nonetheless, the higher priority jobs may complete earlier than their worstcase execution times (like the second τ h instance in Figure 4 where this scenario is illustrated by the hatched part) or their worst-case execution times may be too short to block consumer until the release of producer. The consumer instance that starts before the release of producer cannot get the data from this particular instance of producer. It is the first consumer instance released after the release of producer that reads the data.

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)
We generalize the results obtained above for a chain of tasks allocated to different processors. We consider that the producer τ p and the consumer τ c execute on two different processors with perfectly synchronized clocks: P (τ c ) = P (τ p ). Since the tasks cannot block each other, we can assume that every consumer instance starts always as soon as possible and its buffer is empty if the producer is still running on the other processor. At worst, the data is read for the first time by the consumer instance released immediately after the end of the producer (see Equation ( 2)).

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 ) or P (τ p ) = P (τ c ) r p T c T c if π(τ p ) > π(τ c ) and P (τ p ) = P (τ c ) (4
) where T p and T c are periods of τ p and τ c respectively.

B. The longest data propagation path

We characterize the data propagation path that gives a maximum latency value. In such data propagation path: i) the tasks propagating the data are released as late as possible (according to their periodic behaviour), and ii) their instances can attain their worst-case job response times.

For instance, in Figure 2, the data path marked with a solid line satisfies the above mentioned conditions and the value of its latency is maximal. Propagating the data earlier, as for the data path with a dotted line, cannot increase the latency value.

If there exists a data propagation path in which the data propagation occurs for each task as late as possible and its tasks terminate as late as possible, then it leads to the maximum latency. If such path cannot be constructed in the schedule, then the latency value associated with this path cannot be lower than the actual value of the latency given by some realizable path. The following lemma establishes this basic property. Its results are used later in Theorem 1.

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.

Proof. Suppose that p = (r 1 , . . . , r n ) where r 1 , . . . , r n are the release time instants of the consecutive instances of tasks that propagate the data. Let p = (r 1 , . . . , r n ) be another path of the same chain such that r 1 = r 1 . First we prove by induction that r n ≥ r n . 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 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 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 and RHS a finishing time of the same task released at

r n ≤ 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 ).

C. Recursive method for latency computation

The problem of finding the maximum latency value for a data chain of n tasks released at r p can be divided into two sub-problems:

• finding the latest time instant r c of data propagation from the first to the second task of the chain, • finding the maximum latency value of a chain released at r c that is made up of the remaining n -1 tasks. Consider again the data chain from Figure 2 with τ 1 that is released at r 1,1 and completes its execution 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 a data chain F n-1 of n -1 tasks such that F n-1 is 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 whose 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) (worst-case response times are assumed to be 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 ) or P (τ p ) = 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

D. The worst-case latency

We derive the worst-case latency 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.

Since the processor may be idle at any time, a task can start to execute at the earliest at its release time. 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 task instance released at r 1 + T 1 . The delay experienced by the data in the sensor register is at most one task period (a similar remark is made in [START_REF] Davare | Period optimization for hard realtime 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. There are many paths and their trajectories depend on the release time of the first task. To find the worst-case latency value all the paths must be verified. 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 its period.

To compute the worst-case latency, Formula (6) must be evaluated for all chain instances released at 0, T 1 , 2T 1 , . . ..

To make it computationally tractable the set of considered releases must be limited. The schedule repeats cyclically every hyperperiod H (least common multiple) of all the tasks in the task set [START_REF] Leung | A note on preemptive scheduling of periodic, real-time tasks[END_REF]. Moreover, the execution of the task is not impacted by the tasks of the lower priority and the tasks that run on different processors. It is sufficient to examine only the releases of the first chain task within interval [0, H) where H = lcm { T j | τ j ∈ hep(τ i ), τ j ∈ F n }. Depending on system properties this limit can be further reduced. If the worst-case response times of each task instance are equal, ∀k ∈ N, τ i : R i (t) = R i (t + kT i ), then it is sufficient to apply Algorithm 1 on 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 response times equal [START_REF] Xu | Harmonic scheduling and control co-design[END_REF], [START_REF] Mohaqeqi | On the problem of finding optimal harmonic periods[END_REF]. Such hypothesis can also be made when schedulability analysis only provides 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 a O(n • H T1 ) time complexity. As the hyperperiod grows exponentially as function of the largest task period in the set and with the number of tasks, the problem of finding the worst-case latency may be intractable in some cases.

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 )
Function L(F n , r 1 ) (Algorithm 1) when called in Algorithm 2 can be improved by saving the values of its calls in a lookup table. It may avoid recomputing the same values for the paths that merge together. In particular, if r c is the value of Equation (4) for r p , then the equation gives the same value for all r p such that:

r p ∈ [r p , r c ] if π(τ p ) > π(τ c ) and r p + R p (r p ) ∈ [r p , r c ] if π(τ p ) < π(τ c ).
The tasks instances released at r p write the data into the register of the same consumer instance and their data paths join together. All of them can follow from that point the same trajectory. The data path traversing r p is released at the earliest time and only it can lead to the worst-case latency. All other paths going through r p can be omitted.

Consider Figure 5. The instances of producer task τ p released at the time instants r 1 , r 2 and r 3 , such that r 1 < r 2 < r 3 , communicate with the same instance of consumer task τ c . The respective latencies are: L(F 2 , r 1 ) > L(F 2 , r 2 ) > L(F 2 , r 3 ). The latency has its greatest value for r 1 and all the subsequent releases, r 2 and r 3 , as they cannot increase this value, can be omitted in the computation of the worst-case latency.

V. Experiments

We evaluate the precision of the proposed method for the worst-case latency computation on a generic automotive benchmark [START_REF] Kramer | Real world automotive benchmark for free[END_REF] upon a single processor.

We compare it against a linear-time upper bound on the worst-case latency proposed by Davare et al. [START_REF] Davare | Period optimization for hard realtime distributed automotive systems[END_REF]. The method proposed by Davare et al. [START_REF] Davare | Period optimization for hard realtime distributed automotive systems[END_REF] applies in principle for the sporadic tasks but its use may be also advantageous for the periodic tasks due to its linear-time complexity. As the tasks are not coordinated, the producer τ p may write the data into the register of 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 ) (7)

A. Chain generation

Data chains lengths vary from 2 to 20 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 an associated probability of appearance (the same as in [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, we successively decrease the length from 20 to a minimum of 2 in such way that the number of different periods remains respected. The worst-case response times are obtained from SimSo simulator [START_REF] Chéramy | Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF].

The algorithms described in this work are available on-line 1 through a Python implementation with which experiments presented below are fully reproducible.

B. Analysis precision

In the experiment, we compare the results of the worstcase latency by each method. The results of the experiment are shown in Figure 6. Each point represents the average 1 https://www.lias-lab.fr/~antoinebertout/software/latency.zip worst-case latency value of the corresponding computation method as a function of the chain length for a given utilization factor of the task set. Both methods were tested on the same set of randomly generated data chains. The results obtained are averaged on a minimum of 10000 executions for a given utilization factor u ∈ {0.25, 0.50, 0.75}. The number of distinct periods in the chains varies from 1 to 5. Contrary to the results given by our method, we observe that the pessimism of the linear-time upper bound increases noticeably with the length of the chain. In this particular case, the worst-case latency calculated with the worst-case job response times is equal to the worstcase latency calculated with the worst-case task response times with a tolerance of 10 -3 . Indeed, as task periods are quasi harmonic, most of the task instances verify R i (r i ) = R i under RM scheduling (see also Section IV-D). Therefore, both cases are not differentiated in the figure. The method described in Algorithm 2 provides much more accurate estimates of the worst-case latency and is less sensitive to the increase of the utilization factor. The improvement is achieved with a higher computational cost. Nonetheless, the time needed to execute our method was between 2 and 6 milliseconds2 (without a noticeable impact of the chain length) which is admissible in the most of the cases.

VI. Conclusion and future works

In this paper we proposed a method for the computation of the worst-case latency of data chains and its open-source implementation. The method is easy to implement and can be integrated independently on top of any tool that provides response time analysis.

By investigating the problem of the latency at the level of scheduling, we identify the relations between the execution and the communication of the real-time task and provide a solid base for the future research. In particular, Lemma 1 can be easily extended towards other models that permit to reduce the worst-case latency (e.g., introducing the bestcase execution time or non-preemptive regions may, in some cases, force the consumer task to execute always after the producer). As the method has exponential time complexity, we are currently working on finding an upper bound with linear time complexity that may be derived from the closed-form expression given in Lemma 1.

3 ActuatorFigure 1 :

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

Figure 3 Figure 3 :

 33 Figure 3: Communicating tasks: consumer τ c has higher priority.

Figure 4 .Figure 4 :

 44 Figure 4: Communicating tasks: producer τ p has higher priority.

Figure 5 :

 5 Figure 5: Non critical data propagation paths in the worstcase latency calculation.

  Latency based on R i (r i ) and R iDavare et al. method

Figure 6 :

 6 Figure 6: Impact of the different worst-case latency computation methods.

Each experiment has been performed on a single Intel Xeon E5-2630 v3 CPU (20M cache, 2.40GHz).

Acknowledgements

This research has been partially funded by the French FUI Waruna project.