published or not. The documents may come

An MDE Approach for Domain based Architectural

Components Modelling.

Any correspondance concerning this service should be sent to the repository administrator: staff-oatao@listes-diff.inp-toulouse.fr


H Wendt

K Kiyono
email: kiyono@bpe.es.osaka-u.ac.jp

P Abry

J Hayano
email: hayano@med.nagoya-cu.ac.jp

E Watanabe

Y Yamamoto
email: yamamoto@p.u-tokyo.ac.jp

MultiScale Wavelet p-Leader based Heart Rate Variability Analysis for Survival Probability Assessment in CHF Patients

A priori discrimination of high mortality risk amongst congestive heart failure patients constitutes an important clinical stake in cardiology and involves challenging analyses of the temporal dynamics of heart rate variability (HRV). The present contribution investigates the potential of a new multifractal formalism, constructed on wavelet p-leader coefficients, to help discrimination between survivor and non survivor patients. The formalism, applied to a high quality database of 108 patients collected in a Japanese hospital, enables to assess the existence of multifractal properties amongst congestive heart failure patients and to reveal significant differences in the multiscale properties of HRV between survivor and non survivor patients, for scales ranging from approximately 60 to 250 beats.

I. INTRODUCTION

Congestion Heart Failure: Discriminating Survivors from Non-Survivors. Human Heart Rate Variability (HRV) is known to fluctuate in a highly irregular and complex manner that reflects the health status of patients. The analysis of HRV fluctuations can notably be used to discriminate healthy subjects from patients suffering from congestive heart failure (CHF). However, despite significant recent advances in therapy, CHF is a difficult condition to manage in clinical practice and mortality remains unacceptably high. Medical studies have consistently reported a significant decrease in mortality for patients equipped with implantable cardioverterdefibrillators or undergoing resynchronization therapy. Risk stratification for deciding a priori which patients should benefit from such treatments therefore constitutes a stake of major clinical importance. Identification of high-risk patients with CHF remains a difficult and challenging task with current available methods. It has thus recently received growing academic interest and research efforts (cf., e.g., [START_REF] Nolan | Prospective study of heart rate variability and mortality in chronic heart failure : Results of the united kingdom heart failure evaluation and assessment of risk trial[END_REF]- [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF]). Related works. After the seminal contribution [START_REF] Akselrod | Power spectrum analysis of heart rate fluctuation: a quantitative probe of beat-to-beat cardiovascular control[END_REF] that stimulated the massive use of spectral analysis for HRV characterization, the benefits of using alternative tools dedicated to non linear, non Gaussian and non stationary analyses were investigated (cf., e.g., [START_REF] Bansal | A review of measurement and analysis of heart rate variability[END_REF], [START_REF] Rajendra | Heart rate variability: a review[END_REF] and reference therein). In the last two decades, evidence was gathered that the temporal dynamics of HRV fluctuations are well described by fractal, or scaling, properties, characterized notably by 1/f power spectra [START_REF] Kobayashi | 1/f Fluctuation of heartbeat period[END_REF]- [START_REF] Peng | Quantification of scaling exponents and crossover phenomena in nonstationary heartbeat time series[END_REF], multifractality [START_REF] Ivanov | Multifractality in human heart rate dynamics[END_REF], [START_REF]Behavioral-independent features of complex heartbeat dynamics[END_REF], or non Gaussian distributions with fat tails [START_REF] Kiyono | Critical scale-invariance in healthy human heart rate[END_REF], [START_REF] Kiyono | Multiscale probability density function analysis: Non-Gaussian and scale-invariant fluctuations of healthy human heart rate[END_REF]. It has been shown that the alterations of such properties can be associated with certain diseases and can thus be used as diagnostic tools [START_REF] Ivanov | Multifractality in human heart rate dynamics[END_REF], [START_REF] Hayano | Increased non-Gaussianity of heart rate variability predicts cardiac mortality after an acute myocardial infarction[END_REF]. For instance, an increased departure from Gaussianity (in HRV increments computed on a 25s scale) is associated with an increased cardiac mortality risk in a cohort of acute myocardial infarction (AMI), with a predictive power independent of other HRV indices [START_REF] Hayano | Increased non-Gaussianity of heart rate variability predicts cardiac mortality after an acute myocardial infarction[END_REF]. Furthermore, departures from Gaussianity have been shown to be relevant in the evaluation of increased mortality risk in CHF patients [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF] and compared against fractal exponent and variance in beat interarrival times reported in [START_REF] Makikallio | Fractal analysis and time-and frequency-domain measures of heart rate variability as predictors of mortality in patients with heart failure[END_REF]. Goals, contributions and outline.

In this context, the present contribution aims at investigating to which extent multiscale and multifractal analysis enables to help discriminating between survivor and non-survivor CHF subjects. It relies on the use of a new tool, the wavelet p-leader multifractal formalism, very recently proposed in [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF]- [START_REF] Jaffard | Wavelet analysis of fractal boundaries[END_REF] and briefly defined in Section III. This statistical analysis tool is expected to yield better estimation performance and to show significant robustness in quantifying the scaling properties of real world data [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF]. It is applied to a high quality database, described in Section II, consisting of 24h HRV data for 108 CHF patients collected at Fujita Health University Hospital, Japan. Results are presented and discussed in Section IV, in terms of compared multiscale behaviors, powers of statistical tests and Kaplan-Meier Survival Curves. Conclusions are drawn in Section V, also discussing of future works.

II. DATABASE

Database. A cohort of 108 CHF patients was enrolled at Fujita Health University Hospital, Japan, during years 2000-2001. The cohort was constituted of 61 male and 47 female subjects, with age ranging from 21 to 92 (average 66.1 ± 14.8) years. Of these patients, 39 (36.1 %) died within the follow-up period of 33 ± 17 months (range 1-59 months). Medication status before hospital discharge did not significantly differ between survivor (SV) and non-survivor (NS) patients. Clinical details for these CHF patients were previously reported in [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF]. Data. For each patient, a 24-hour Holter ECG recording was collected prior to Hospital discharge. R peaks were extracted and thoroughly reviewed for outlier removal and detection error correction. When atrial or ventricular premature complexes occurred, they were handled by median interpolation using two successive beats. It has also been checked that no sustained tachyarrhythmias were present in HRV recordings. The corresponding RR inter-arrival time values, denoted as X ≡ {x n , n = 1, . . . , N }, are analyzed as a time series, without resampling on a regular time grid. III. WAVELET P-LEADER FORMALISM Multifractal analysis. Multifractal analysis aims at characterizing the fluctuations along time n of the local regularity of a signal X, classically measured by the Hölder exponent h, by means of the so-called multifractal spectrum D(h) (cf. [START_REF] Jaffard | Wavelet techniques in multifractal analysis[END_REF] for a theoretical introduction). D(h) can be further described using multifractal parameters (e.g., the multifractal exponents described below.) It has already been massively used to analyze HRV both in adults [START_REF] Ivanov | Multifractality in human heart rate dynamics[END_REF], [START_REF] Lopes | Fractal and multifractal analysis: A review[END_REF] and fetuses [START_REF] Doret | Multifractal analysis of fetal heart rate variability in fetuses with and without severe acidosis during labor[END_REF], [START_REF] Jaffard | Irregularities and Scaling in Signal and Image Processing: Multifractal Analysis[END_REF]. Numerous declinations of multifractal formalisms (the practical counterpart of multifractal theory that actually enables to compute the multifractal parameters) were proposed and compared (cf. [START_REF] Lopes | Fractal and multifractal analysis: A review[END_REF] for a review). Notably, declinations of the (discrete) wavelet transform have proven to yield some of the most relevant multifractal formalisms (cf. e.g. [START_REF] Jaffard | Irregularities and Scaling in Signal and Image Processing: Multifractal Analysis[END_REF]- [START_REF] Wendt | Bootstrap for empirical multifractal analysis[END_REF]). The present contribution relies on a new tool, referred to as the wavelet p-leader formalism, that has been theoretically introduced in [START_REF] Jaffard | Wavelet analysis of fractal boundaries[END_REF] and recently studied in [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF], [START_REF] Leonarduzzi | p-exponent and p-leaders[END_REF]. Wavelet coefficients. Let ψ denote the mother wavelet, characterized by a strictly positive integer N ψ defined as ∀n = 0, . . . , N ψ -1, R t k ψ(t)dt ≡ 0 and R t N ψ ψ(t)dt = 0 and referred to as the number of vanishing moments.

The (L 1 -normalized) discrete wavelet transform coefficients d X (j, k) of X are defined as d X (j, k) = ψ j,k |X , with {ψ j,k (t) = 2 -j ψ(2 -j t -k)} (j,k)∈N 2 .
For detailed introductions to wavelet transforms, readers are referred to e.g., [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF]. Wavelet p-leaders.

The p-leaders are defined as local L p -norms of the fractional integral of order γ of wavelet coefficient,

2 jγ d X (j, k), L (p,γ) (j, k) = 2 j λ j ′ ,k ′ ⊂3λ j,k |2 j ′ γ d j ′ ,k ′ | p 2 -j ′ 1/p , (1)
with λ j,k = [k2 j , (k+1)2 j ) and 3λ j,k = m{-1,0,1} λ j,k+m . The parameter γ ≥ 0 must be chosen to ensure a minimal regularity constraint (cf. [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF]- [START_REF] Jaffard | Wavelet analysis of fractal boundaries[END_REF] for theoretical developments). Parameter p can be freely chosen in a range p ∈ (0, p 0 ) where p 0 is implicitly defined by

η(p 0 ) + γp 0 = 0, (2)
with 1/n j nj k=1 |d X (j, k)| p ∼ K p 2 jη(p) , 2 j → 0.
The p-leaders enable to measure the fluctuations of the local regularity of X, quantified by its p-exponents h p , and to infer the corresponding multifractal parameters (cf. [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF]- [START_REF] Jaffard | Wavelet analysis of fractal boundaries[END_REF] for details, beyond the scope of this contribution.) Cumulants. The quantities used in this work for characterizing the multiscale and multifractal properties of X are the cumulants C (p,γ) m (j) = Cum m ln L (p,γ) (j, •) of the variables ln L (p,γ) (j, k), commonly used for multifractal analysis [START_REF] Wendt | Bootstrap for empirical multifractal analysis[END_REF], [START_REF] Castaing | Log-similarity for turbulent flows[END_REF]. For X with perfect fractal properties (such as selfsimilar or multifractal processes), it can be shown that [START_REF] Castaing | Log-similarity for turbulent flows[END_REF]:

C (p,γ) m (j) = ν (p,γ) m + c (p,γ) m ln 2 j . (3)
When applied to exactly self-similar processes, c

IV. RESULTS AND DISCUSSIONS

p-leaders multiscale HRV analysis.

To apply the pleader multifractal formalism, parameters γ and p need to be selected. First the wavelet coefficients d X (j, k) are computed from the 24h RR interarrival time series for each subject. Inspection shows that for most subjects Condition (2) can not be satisfied with γ = 0 for any p 0 > 0. This provides us with a first and crucial information regarding HRV and scaling: Multifractal analysis can not in general be applied to HRV data without the a priori recourse to a fractional integration of small yet non zero order to ensure minimal regularity. The value γ = 0.5 is found sufficient to ensure minimal regularity for all subjects. To simplify the characterization of the entire database, this value is used for all subjects.

With this choice for γ, the p-leaders L (p,γ) (j, k), the logcumulant functions C (p,γ) m (j) and the exponents c (p,γ) m can be computed for p ∈ (0, p 0 ), where p 0 varies amongst subjects but p 0 ≥ 4 for all subjects. It is found that p = 1 yields the optimal classification between SV and NS subjects. Interestingly, this low value of p matches the theoretical results reported in [START_REF] Leonarduzzi | Extending multifractal analysis to negative regularity: p-exponents and p-leaders[END_REF], [START_REF] Leonarduzzi | p-exponent and p-leaders[END_REF] showing that estimation performance generically improve with decreasing p. All results reported below are thus computed with parameters (p, γ) = (1, 0.5).

Furthermore, it is chosen here to analyze cumulants up to order m = 3, i.e., C (j) corresponding respectively to the mean, the variance and (essentially) the skewness of ln L (p,γ) (j, •).

Statistical discrimination between NS and SV patients.

To assess the discriminative power of p-leaders for the temporal dynamics of NS versus SV CHF patients, Wilcoxon rank-sum tests are used together with Kaplan Meier Cumulative Survival Curves (KMSC), following the methodology in [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF]. KMSC curves are obtained by choosing a threshold for a chosen attribute (say c

(1,0.5) 1

) and splitting the population into two groups of predicted NS and predicted SV with attributes above and below this threshold, respectively. Over the follow-up period, the population of a group decreases each time one of its members dies such that with an ideal discrimination, the population of the predicted SV class would remain constant while that of the predicted NS class would decay to zero. Differences between the decrease of the curves for the two groups are assessed by the Mantel-Haenszel Logrank test: Let n SV and d SV (resp., n N S and d N S ) denote the total number of subjects and the number of deaths occurring in class SV (resp., NS). Let d = d SV +d N S , n = n SV + n N S . Under the null hypothesis that the survival curves of the two classes are equal, the test statistic

! " # $ %& %! %'# %'" %'! % (%)*+ * ,-./0 % 1 &'&!2 3,./0 % 1 &'&24 ! " # $ %& %! ! % & '() %& *+, -%*., . ! " # $ %& %! & &'% &'! &'( )!*+, + -./01 ! 2 &'&!! 3-/01 ! 2 &'&!! ! " # $ %& %! ! % & '() %& *+, -!*., . ! " # $ %& %! &'&( &'&! &'&% & &'&% &'&! )(*+, + -./01

Log-cumulants C

(1,0.5) m (j) as functions of the log of the scale and discrimination between SV and NS patients. Left column: C

(1,0.5) m (j) for m = 1, 2, 3 from top to bottom. Right column: log 10 (pvalue) for each octave j (a value below the threshold 1.30 (dashed horizontal black line) indicates a p-value smaller than 0.05 and thus a significative difference between SV and NS).

Z = n 2 (n-1)(dSV -nSV d/n) 2 nSV nNS d(n-d) ∼ χ 2
1 follows a chi-squared distribution with 1 degree of freedom.

Furthermore, we assess classification performance in terms of Sensitivity and Specificity. Discriminative power of multifractal properties. Fig. 1 shows log-cumulants C

(1,0.5) m (j) as functions of (log 2 of) the analysis scale a = 2 j , and calls for the following comments.

First, it can be observed that, both for NS and SV, all three log-cumulant functions C

(1,0.5) m (j) (Fig. 1, left column) display satisfactory linear behavior across scales 2 3 ≤ a ≤ 2 7 . This indicates that HRV temporal dynamics display scaling properties across groups of 8 to 128 beats. This partially matches with previous analysis of RR interarrival time series reporting scaling in range of 10 to 1000 beats [START_REF] Peng | Quantification of scaling exponents and crossover phenomena in nonstationary heartbeat time series[END_REF]. Such scaling have often been quantified via the so-called α 2 scaling parameter when measured by Detrended Fluctuation Analysis (DFA) (cf. e.g., [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF] and references therein). Note that the slope c

(1,0.5) 1

of the function C

(1,0.5) 1

(j) can be understood as a robust estimator for α 2 . Thorough theoretical and practical comparisons between DFA and p-leaders will be detailed in a forthcoming study.

Second, the fact that the slopes c

(1,0.5) 1

differ (Fig. 1, top left) indicates a clear difference in the self-similar temporal dynamics between SV and NS subjects. Accordingly, Fig. 2 (top right) shows that KMSC computed from c

(1,0.5) 1 has a moderate discriminative power, slightly below the significance level 0.05.

Third, multifractal exponents c

(1,0.5) 2

and c

(1,0.5) 3

, measured from the linear behaviors across scales of the second and third log-cumulant functions, C

(1,0.5) 2

(j) and C

(1,0.5) 3 :*;#<'=+ +8 ! +*+$%$(

(j)

62>?1 @ABC>)D*&%"$"++7 ?>)D *$%$"# ! " # $%# $%& $%' $%( )*+",-"&.
)*"/,-!0. #/1,23)24546457 +#1,28394:49457 ;*', ,<"-;.,*,$%"

73=>2 ?@AB=)C*0%/"&,,8 >=)C *$%$# ! " # $%# $%& $%' $%( )*+,-."!/ )*0$-.!,/ &+1-23)24546457 0!1-28394:49457 ;*<#='>--9 " -*-$%$#& 73?@2 ABCD?)E*"%!0&--8 @?)E *$%!+ ! " # $%# $%& $%' $%( )*'+,-!'. )*#+,-"". &/0,12)13435346 7#0,18293:39346 ;*', ,<#-;.,*,$%$$( 62=>1 ?@AB=)C*!'%+"+,,8 >=)C *$%$$$$# ! " # $%# $%& $%' $%( )*&$+,"!- )*&.+,!.- &/0+12)13435346 &.0+17283938346 :*;#<'=+ +8 # +*+ $%$$' 62>?1 @ABC>)D*!%#.'++7 ?>)D *$%"/
(Fig. 1, middle and bottom left), are observed to clearly depart from 0, a strong evidence that scaling in RR interarrival HRV time series possess multifractal properties, both for SV and NS patients. The range (or power) of the fluctuations of regularity of RR interarrival HRV time series is identical for NS and SV patients. Yet, no significant change in the multifractal temporal dynamics conveyed by c

(1,0.5) 2 and c

(1,0.5) 3 is evidenced between NS and SV patients. Accordingly, KMSC computed from them (Fig. 2, middle and bottom right, respectively) show no discriminative power. Discriminative power of multiscale properties. Multifractal analysis consists of a demanding model as it relies on the assumption that data follow [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF]. To alleviate such assumptions, log-cumulant functions C

(1,0.5) m (j) can be examined at each scale a = 2 j independently, regardless of whether (3) is satisfied or not. These are referred to as the multiscale properties of data (to distinguish from multifractal properties induced by (3)) and provide a measure for the non Gaussian characteristics of p-leaders at each scale j.

First, it is observed that the function C

(1,0.5) 1

(j) (Fig. 1, top right) clearly discriminates between SV and NS temporal dynamics for scales a = 2 j ranging from 2 6 ≃ 60 to 2 10 ≃ 1000 beats. Interestingly, C

(1,0.5) 1 (j) for NS patients is systematically below that of SV patients, indicating a clear decrease in the overall power (or variance) of the RR inter-arrival times HRV time series. This thus materializes a decrease in the overall variability of heart rate, generally considered a sign of bad health. Accordingly, KMSC computed from C

(1,0.5) 1 (j = 7) (Fig. 2, top left) indicate a high discriminative power between NS and SV patients.

Second, the functions C

(1,0.5) 2

(j) (Fig. 1, middle left) show no significant change between NS and SV at any scale and the KMSC computed from C

(1,0.5) 2 (j = 7) (Fig. 2, middle right) indicates little to no discriminative power.

Third and foremost, the third log-cumulant function (skewness type) C

(1,0.5) 3 (j) (Fig. 1, bottom left) is observed to significantly differ for scales ranging from 2 4 ≃ 20 to 2 10 ≃ 1000 beats. The KMSC computed from C

(1,0.5) 3

(j = 7) (Fig. 2, bottom left) reflect this fact and show highly significative discriminating power between NS and SV patients.

These observations confirm multifractal analysis: There exist clear yet subtle changes in multiscaling properties of RR interarrival HRV time series. Changes in C

(1,0.5) 1 (j = 7) indicate changes in the power (or variance) of the time series themselves, a significant decrease being manifest for NS patients; The absence of change in C

(1,0.5) 2 (j = 7) indicates that the range of the fluctuations of ln L (p,γ) (j, •) at any scale does not differ between NS and SV patients; Conversely, the change in C

(1,0.5) 3

(j = 7) indicates a strong positive asymmetry of the fluctuations of ln L (p,γ) (j, •) for NS patients. In equivalent terms, the fluctuations of the time series of NS patients are characterized by the same variance but stronger power law like heavy tails and stronger departure from log-normal tails as those of SV patients.

V. CONCLUSIONS

Making use of the recently proposed p-leader wavelet coefficients multifractal formalism, the multifractal and multiscale properties of RR interarrival HRV time series temporal dynamics of survivor and non-survivor congestion heart failure patients were compared. For both classes of patients, clear scaling and multifractal properties are evidenced. While a (weakly) significant difference is observed for the selfsimilar scaling exponent c

(1,0.5) 1

, no clear differences are evidenced for the multifractal exponents c , for scale A = 2 7 ≃ 100 beats. Equivalent results are obtained with scales 2 6 or 2 8 corresponding to ≃ 60 or ≃ 250 beats. These results are strongly consistent with (and slightly outperform) those reported in [START_REF] Kiyono | Non-Gaussian heart rate as an independent predictor of mortality in patients with chronic heart failure[END_REF] where a significant departure from Gaussianity for detrended increments of the RR interarrival HRV time series is found around a scale of 40 beats.

It comes as a surprising result that the third log-cumulant function yields significant differences when the second one does not, while they are both related to the non-Gaussianity of the data. The differences of the third log-cumulant indicate a subtle change in the heavy tails of the fluctuations that will be further investigated. This preliminary analysis will be further continued by comparing against age-sex matched healthy subjects. Also, the 24h data enables us to study potential differences between awake and sleep phases.

(p,γ) 1

 1 is tied to the self-similar exponent as c (p,γ) 1 = H + γ. It is thus generically referred to as the self-similarity exponent. Exponents c (p,γ) m , m ≥ 2, do not depend on γ and are directly related to the multifractal properties of data, thus referred to as multifractal exponents. Making use of (3), the exponents c (p,γ) m can be estimated by linear regressions of the sample cumulants C (p) m (j) against ln 2 j , for j ∈ [j 1 , j 2 ].

  Fig. 1.Log-cumulants C

Fig. 2 .

 2 Fig. 2. Kaplan Meier Cumulative Survival Curves for the log-cumulants C (1,0.5) m (j = 7) for m = 1, 2, 3 (left column, top to bottom) and for the self-similar exponent c (1,0.5) 1 and multifractal exponent s c (1,0.5) 2

3 .

 3 Instead, clear differences are reported for the first and third log-cumulant functions, C

Work supported by ANR BLANC 2010


Zhibin Yang
email: zhibin.yang@irit.fr

Jean-Paul Bodeveix
email: bodeveix@irit.fr

Mamoun Filali
email: filali@irit.fr

Multi-core Code Generation from Polychronous Programs with Time-Predictable Properties

Keywords: Synchronous languages, SIGNAL, Guarded actions, Verified compiler, Multi-core, Time predictability, AADL

Synchronous programming models capture concurrency in computation quite naturally, especially in its dataflow multi-clock (polychronous) flavor. With the rising importance of multi-core processors in safety-critical embedded systems or cyber-physical systems (CPS), there is a growing need for model-driven generation of multi-threaded code for multi-core systems. This paper proposes a build method of timepredictable system on multi-core, based on synchronous-model development. At the modeling level, the synchronous abstraction allows deterministic time semantics. Thus synchronous programming is a good choice for time-predictable system design. At the compiler level, the verified compiler from the synchronous language SIGNAL to our intermediate representation (S-CGA, a variant of guarded actions) and to multi-threaded code, preserves the time predictability. At the platform level, we propose a time-predictable multi-core architecture model in AADL (Architecture Analysis and Design Language), and then we map the multi-threaded code to this model. Therefore, our method integrates time predictability across several design layers.

Introduction

Safety-critical embedded systems or cyber-physical systems (CPS) distinguish themselves from general purpose computing systems by several characteristics, such as failure to meet deadlines may cause a catastrophic or at least highly undesirable system failure. Time-predictable system design [START_REF] Axer | Building timing predictable embedded systems[END_REF][START_REF] Wilhelm | The worst-case execution-time problem: Overview of methods and survey of tools[END_REF][START_REF] Thiele | Design for timing predictability[END_REF] is concerned with the challenge of building systems in such a way that timing requirements can be guaranteed from the design. This means we can predict the system timing statically. With the widespread advent of multi-core processors in this category of systems, it further aggravates the complexity of timing analysis.

The synchronous abstraction allows deterministic time semantics. Therefore synchronous programming is a good choice for time-predictable system design. There are several synchronous languages, such as ESTEREL [START_REF] Boussinot | The esterel language[END_REF], LUSTRE [START_REF] Halbwachs | The synchronous data-flow programming language lustre[END_REF] and QUARTZ [START_REF] Schneider | The synchronous programming language quartz[END_REF] based on the perfect synchrony paradigm, and SIGNAL [START_REF] Benveniste | Synchronous programming with events and relations: the signal language and its semantics[END_REF] based on the polychrony paradigm.

An integration infrastructure for different synchronous languages has gained a lot of interests in recent years [START_REF] Brandt | Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions[END_REF][START_REF] Talpin | Constructive polychronous systems[END_REF]. A classical solution is to use an intermediate representation. Guarded commands [START_REF] Dijkstra | Guarded commands, nondeterminacy and formal derivation of programs[END_REF], also called asynchronous guarded actions by J. Brandt et al. [START_REF] Brandt | Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions[END_REF], are a well-established concept for the description of concurrent systems. In the spirit of the guarded commands, J. Brandt et al. propose synchronous guarded actions [START_REF] Brandt | Separate translation of synchronous programs to guarded actions[END_REF] as an intermediate representation for their QUARTZ compiler. As the name suggests, it follows the synchronous model. Hence, the behavior (control flow as well as data flow) is basically described by sets of guarded actions of the form γ ⇒ A . The boolean condition γ is called the guard and A is called the action. To support the integration of synchronous, polychronous and asynchronous models (such as CAOS or SHIM), they propose an extended intermediate representation, that is clocked guarded actions [START_REF] Brandt | Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions[END_REF] where one can declare explicitly a set of clocks. They also show how clocked guarded actions can be used for verification by symbolic model checking (SMV) and simulation by SystemC. [START_REF] Brandt | Embedding polychrony into synchrony[END_REF] presents an embedding of polychronous programs into synchronous ones. The embedding gives us access to the methods and tools that already exist for synchronous specifications. For a safety-critical system, it is required that the compiler must be verified to ensure that the source program semantics is preserved. Our work mainly focuses on the SIGNAL language. We would like to extract a verified SIGNAL compiler from a correctness proof developed within the theorem prover Coq as it has been done in the GENEAUTO project for a part of the SIMULINK compiler. Our intermediate representation is a variant of clocked guarded actions (called S-CGA), and currently the target is multi-core code. In [START_REF] Yang | A verified transformation: From polychronous programs to a variant of clocked guarded actions[END_REF], we have already presented the compilation of sequential code and the proof of semantics preservation of the transformation from the kernel SIGNAL to S-CGA. There exist several semantics for SIGNAL, such as denotational semantics based on traces (called trace semantics) [START_REF] Gamatié | Designing embedded systems with the SIGNAL programming language[END_REF], denotational semantics based on tags which puts forward a partial order view of time (called tagged model semantics) [START_REF] Gamatié | Designing embedded systems with the SIGNAL programming language[END_REF], structural operational semantics defining inductively a set of possible transitions [START_REF] Benveniste | Synchronous programming with events and relations: the signal language and its semantics[END_REF][START_REF] Gamatié | Designing embedded systems with the SIGNAL programming language[END_REF], etc. In [START_REF] Yang | A comparative study of two formal semantics of the SIGNAL language[END_REF], we have studied the equivalence between the trace semantics and the tagged model semantics, to assert a determined and precise semantics of the SIGNAL language. The relation between our work and related work is shown in Fig. 1.

The contribution of this paper is to propose a build method of time-predictable system on multi-core, based on synchronous-model development. At the modeling level, synchronous programming is a good choice for time-predictable system design. At the compiler level, the verified compiler from the synchronous language SIGNAL to our intermediate representation (S-CGA, a variant of guarded actions) and thus to multi-threaded code, preserves the time predictability. At the platform level, we propose a time-predictable multi-core architecture model in AADL (Architecture Analysis and Design Language) [START_REF]AS5506A: Architecture Analysis and Design Language (AADL) Version[END_REF], and then we map the multi-threaded code to this model.

The rest of this paper is structured as follows. Section 2 presents the abstract syntax and the semantics of S-CGA. Section 3 gives the multi-threaded code generation schema from S-CGA. The time-predictable multi-core architecture model and the mapping from multi-threaded code to that model are presented in Section 4. Section 5 gives some concluding remarks.

S-CGA

In papers such as [START_REF] Brandt | Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions[END_REF], clocked guarded actions has been defined as a common representation for synchronous (via synchronous guarded actions), polychronous and asynchronous (via asynchronous guarded actions) models. It has a multiclocked feature. However, in contrast to the SIGNAL language, clocked guarded actions can evaluate a variable even if its clock does not hold [START_REF] Brandt | Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions[END_REF] for supporting the asynchronous view. Since we focus on the polychronous view, we introduce S-CGA, which is a variant of clocked guarded actions. S-CGA constrains variable accesses as done by SIGNAL. In this section, we first present the syntax of S-CGA, and then we give the denotational semantics of S-CGA based on the trace model.

S-CGA has the same structure as clocked guarded actions, but they have different semantics.

Definition 1 (S-CGA).

A S-CGA system is represented by a set of guarded actions of the form γ ⇒ A defined over a set of variables X. The Boolean condition γ is called the guard and A is called the action. Guarded actions can be of the following forms:

(1) γ ⇒ x = τ (immediate) (2) γ ⇒ next(x) = τ (delayed) (3) γ ⇒ assume(σ) (assumption)
where the guard γ is a Boolean condition over the variables of X, their respective clocks (for a variable x ∈ X, we denote its clock x), and their respective initial clocks (denoted init(x)),

τ is an expression over X, -σ is a Boolean expression over the variables of X and their clocks.

An immediate assignment x = τ writes the value of τ immediately to the variable x. The form (1) implicitly imposes that if γ is defined1 and its value is true, then x is present and τ is defined. Moreover, init(x) exactly holds the first instant when x is present.

A delayed assignment next(x) = τ evaluates τ in the given instant but changes the value of the variable x at next time clock x ticks.

The form (3) defines a constraint. It determines a Boolean condition which has to hold when γ is defined and true. All the execution traces must satisfy this constraint. Otherwise, they are ignored.

Guarded actions are composed by using the parallel operator . An S-CGA example 2 (Example 1) is shown as follows.

true ⇒ assume( ŷ1 = x) ẑ ∧ z ⇒ s1 = f (y1) init( ŷ1) ⇒ y1 = 1 ŝ2 ⇒ s2 = s1 + 1 ŷ1 ⇒ next(y1) = x ŝ1 ⇒ assume( ŝ2) true ⇒ assume( ŷ2 = x) ŝ3 ⇒ assume(ẑ ∧ (not z)) init( ŷ2) ⇒ y2 = 2 ẑ ∧ (not z) ⇒ s3 = f (y2) ŷ2 ⇒ next(y2) = x ŝ4 ⇒ s4 = s3 + 2 true ⇒ assume(x = ẑ) ŝ3 ⇒ assume( ŝ4) ŝ1 ⇒ assume(ẑ ∧ z)
Definition 2 (Trace semantics of S-CGA). The trace semantics of a S-CGA system is defined as a set of traces, that is SCGA = {S | ∀scga ∈ SCGA, scga S = true}. We have the following semantics rules,

(1) γ ⇒ x = τ S = ∀i ∈ N, γ S,i ∧ γ S,i → ( x S,i ∧ τ S,i ∧ x S,i = τ S,i) (2) γ ⇒ next(x) = τ S = ∀i1 < i2 ∈ N, ((∀i ′ ∈ N, i1 < i ′ < i2 → ¬ x S,i ′ ) ∧ γ S,i 1 ∧ γ S,i 1 ) → ( x S,i 1 ∧ τ S,i 1 ∧ ( x S,i 2 → x S,i 2 = τ S,i 1 )) (3) γ ⇒ assume(σ) S = ∀i ∈ N, γ S,i ∧ γ S,i → σ S,i ∧ σ S,i
-Rule (1): when γ is present, and the value of γ is true, x and τ are both present, and the value of x is that of τ . -Rule (2): when γ is present and the value of γ is true at instant i 1 , x and τ are present at i 1 , and if i 2 is the next instant where x is present, then the value of x at i 2 is that of τ at instant i 1 .

-Rule (3): when γ is present, and the value of γ is true, σ is present and true.

The semantics of S-CGA composition is defined as scga 1 scga 2 S = scga 1 S ∧ scga 2 S .

In [START_REF] Yang | A verified transformation: From polychronous programs to a variant of clocked guarded actions[END_REF], we have already presented the translation rules from the kernel SIG-NAL to S-CGA, and give the proof of the semantics preservation in Coq.

3 From S-CGA to Multi-threaded Code

The SIGNAL compilation process contains one major analysis called clock calculus from which code generation directly follows. Moreover, the clock calculus contains several steps, such as the synchronization of each process, i.e., an equation system over clocks; the resolution of the system of clock equations; the construction of a clock hierarchy on which the automatic code generation strongly relies. Our goal here is to adapt the clock calculus to S-CGA.

Based on the semantics of S-CGA, we can get the equation system over clocks. The general rules are given as follows.

S-CGA Clock Equations

γ ⇒ x = τ γ ∧ γ → x ∧ τ γ ⇒ next(x) = τ γ ∧ γ → x ∧ τ γ ⇒ assume(σ) γ ∧ γ → σ ∧ σ init(x) → x (∀x ∈ X)
As a first step, we just consider the endochrony property3 , namely we can construct a clock hierarchy based on the resolution of the system of clock equations. The clock hierarchy of Example 1 (with three clock equivalence classes C0, C1, and C2) is shown in Fig. 2. In the figure, for instance clk x denotes x.

Fig. 2. Clock hierarchy

Moreover, we construct the data-dependency graph (DDG, as shown in Fig. 3) based on the variables reading and writing.

Finally, the multi-threaded code generation is based on both the clock hierarchy and the data dependency graph. First, we map the guarded actions to threads (i.e. partitions, as shown in Fig. 3). As presented in Fig. 4, we would like to treat the partition methods generally, this means different partition methods (such as the vertical way [START_REF] Baudisch | Multithreaded code from synchronous programs: Extracting independent threads for OpenMP[END_REF] for a concurrent execution, the horizontal way [START_REF] Baudisch | Multithreaded code from synchronous programs: Generating software pipelines for OpenMP[END_REF] Fig. 3. Data dependency graph Fig. 4. The proof idea for a pipelined execution, etc) don't affect the proof (here we don't consider performance). Second, in each thread, we organize the guarded actions based on the clock hierarchy. For example, the two guards in Thread2 belong to the same clock equivalence class, so they are merged inside the same control condition in the generated code. Third, we add wait/notify synchronization among the threads. A code fragment of Thread2 is given as follows.

/ * T hread 2 * / void step() { wait(T hread1); if (C1){ s1 = f (y1); s2 = s1 + 1; } notif y(T hread4); }

Mapping Multi-threaded Code to Multi-core

To allow for static prediction of the system timing, we need time-predictable processor architectures, thus we know all the architecture details such as the pipeline and the memory hierarchy to analyze the execution time of programs.

Furthermore, the mapping from multi-threaded code to multi-core architectures should be also static and deterministic.

A time-predictable multi-core architecture model

With the advent of multi-core architectures, interference between threads on shared resources further complicates analysis. There are some recommendations from R. Wilhelm et al. [START_REF] Wilhelm | The worst-case execution-time problem: Overview of methods and survey of tools[END_REF][START_REF] Thiele | Design for timing predictability[END_REF], i.e., the better way is to reduce the time interference: (1) pipeline with static branch prediction and with in-order execution;

(2) separation of caches (instruction and data caches); ( 3) LRU (Least Recently Used) cache replacement policy; and (4) access of main memory via a TDMA (Time Division Multiple Access) scheme. In the EC funded project T-CREST4 , M. Schoeberl et al. [START_REF] Schoeberl | Data cache organization for accurate timing analysis[END_REF][START_REF] Schoeberl | A time predictable instruction cache for a Java processor[END_REF] propose a new form of organization for the instruction cache, named method cache (MC), and split data caches (including stack cache (SC), static data cache (SDC), constants data cache (CDC), and heap allocated data cache (HC)), to increase the time predictability and to tighten the WCET. The method cache stores complete methods and cache misses occur only on method invocation and return. They split the data cache for different data areas, thus data cache analysis can be performed individually for the different areas. In our work, heap is avoided to be used because we don't use dynamic memory allocation in our multi-threaded code.

Based on these existing work, we would like to model a time-predictable multi-core architecture in AADL. AADL is an SAE (Society of Automotive Engineers) architecture description language standard for embedded real-time systems, and supports several kinds of system analysis such as schedulability analysis. Moreover, we have already worked on the semantics of different AADL subsets such as [START_REF] Yang | From AADL to timed abstract state machines: A verified model transformation[END_REF]. So we envision how to validate semantically the mapping from the language level to the architecture level.

Our multi-core architecture model is illustrated in Fig. 5. Inside the core, we consider static branch prediction and in-order execution in the pipeline. A simplified instruction set (get instruction, compute, write data, and read data) is used. As a first step, we just consider a first level cache (i.e. without L2 and L3). Each core is associated with a method cache, a stack cache, a static data cache, and a constants data cache. However, the same principle of cache splitting can be applied to L2 and L3 caches. The extension of the timing analysis for a cache hierarchy is straight forward. Moreover, TDMA-based resource arbitration allocates statically-computed slots to the cores.

As proposed by [START_REF] Delange | Design and analysis of multi-core architecture for cyberphysical systems[END_REF], a core is associated with an AADL processor component and a multi-core processor with an AADL system component containing multiple AADL processor subcomponents, each one representing a separate core. This modeling approach provides flexibility: an AADL system can contain other components to represent cache, and shared bus, etc. For that purpose, we define specific modeling patterns with new properties (such as Multi Core Properties). A part of AADL specification is given in Fig. 6.

The mapping method

To preserve the time predictability, we consider static mapping and scheduling. Take the example shown in the last section. It generates a configuration file (such as num of threads=4 ) in multi-threaded code generation. Moreover, we have a manual configuration file for the time-predictable multi-core architecture model, for example num of cores=4. Thus, we can generate a static mapping and scheduling, for instance:

-Thread1 → Core1, Thread2 → Core2, Thread3 → Core3, and Thread4 → Core4.

-Thread1: notify(Thread2), notify(Thread3); Thread2: wait(Thread1), notify(Thread4); Thread3: wait(Thread1), notify(Thread4); Thread4: wait(Thread2), wait(Thread3).

Based on the simplified instruction set (considered in the architecture model), the multi-core code can be generated. Thanks to the mechanizations such as method cache, split data caches, TDMA and static scheduling, the execution time of the multi-core code can be bounded.

Conclusion and Future Work

With the widespread advent of multi-core processors in safety-critical embedded systems or cyber-physical systems (CPS), it further aggravates the complexity of timing analysis. This paper proposes a build method of time-predictable system on multi-core, based on synchronous-model development. Our method integrates time predictability across several design layers, i.e., synchronous programming, verified compiler, and time-predictable multi-core architecture model. Interaction among cores might also arm software isolation layers, such as the one defined in ARINC653. Thanks to the existing work such as [START_REF] Delange | Design and analysis of multi-core architecture for cyberphysical systems[END_REF] and [START_REF] Hugues | AADLib, a library of reusable AADL models[END_REF] on AADL modeling on multi-core architectures and their association with ARINC653, we would like to associate our work with partitioned architectures in the future.

Fig. 1 .

 1 Fig. 1. A global view of the relation between our work and related work

Fig. 5 .

 5 Fig. 5. A time-predictable multi-core architecture model

Fig. 6 .

 6 Fig. 6. A part of the AADL specification of the time-predictable multi-core architecture

An expression is said to be defined if all the variables it contains are present.

The weak endochrony[START_REF] Potop-Butucaru | Concurrency in synchronous systems[END_REF] property will be considered in the future.

Time-predictable Multi-Core Architecture for Embedded Systems

Acknowledgments: This work was supported by the RTRA STAE Foundation in France (http://www.fondation-stae.net/).


Strategies for the Interconnection of CAN buses through an Ethernet switch

Abdelaziz Ahmed Nacer, Katia Jaffres-Runser, Jean-Luc Scharbarg and Christian Fraboul IRIT -ENSEEIHT, Toulouse University 2, rue Charles Camichel 31000 Toulouse -France {aahmedna, katia.Jaffres-Runser, Jean-Luc.Scharbarg, Christian.Fraboul}@enseeiht.fr Abstract-This paper discusses the use of an Ethernet switch to interconnect remotely located fieldbuses, e.g. CAN. Mastering delays of flows is a key issue in such architectures. The focus of this paper is to propose and analyze bridging strategies for the gateways between CAN and the Ethernet switch. Our previous studies have highlighted the benefits of an optimal design of encapsulation policies at ingress gateways to the switch. In this paper, we show that regulating CAN traffic at the egress gateways is essential as well to provide timely transport of CAN flows.

I. INTRODUCTION

Fieldbuses (e.g. CAN, Profibus) have been developed in the context of real-time applications that have specific communication requirements, in particular in terms of timing constraints. However, the amount of information that is nowadays exchanged in such systems has been increasing steadily and is reaching the limits of traditional fieldbuses, especially in terms of bandwidth. Switching from fieldbuses to Ethernet is a classical trend in real-time systems due to the wide acceptance of the Ethernet standard and its evolution toward a more predictable switched architecture.

The network architecture considered in this paper interconnects a set of CAN buses through an Ethernet switch. The goal is to increase the available bandwidth while keeping the well established CAN technology. We argue that the key point to achieve a timely behavior of the flows in the network is to carefully define the bridging strategies of the gateways interconnecting the fieldbuses with the switch. This paper proposes a set of bridging strategies both for the CAN to Ethernet and the Ethernet to CAN gateway directions. Previous studies have highlighted the benefits of an optimal design of encapsulation policies at ingress gateways to the switch. In this paper, we show that regulating CAN traffic at the egress gateways is essential as well to provide timely transport of CAN flows.

The paper is organized as follows. Section II summarizes the considered network architecture. Section III proposes different bridging strategies and section IV shows their impact on an example configuration. Section V concludes and gives some directions for future work.

II. HYBRID NETWORK ARCHITECTURE

The purpose of this study is to interconnect several CAN buses with a switched Ethernet network. First, CAN and switched Ethernet are presented in Section II-A. Then the targeted network architecture is detailed in Section II-B.

A. Protocol descriptions

A CAN bus (Controller Area Network) [START_REF]ISO International Standard 11898-Road vehicles -Interchange of digital information -Controller area network (CAN) for high-speed communication[END_REF] is a serial communication bus originally suited for in-vehicle communication but also used in other areas such as aerospace, or industrial automation. CAN bus is a message-based protocol. A CAN frame has neither a destination nor a source address. The protocol addressing system is based on messages identifiers. The CAN frames are broadcasted on the bus. When frames are received, station get the frame they are interested in by filtering out the identifiers. The identifier field represents the priority of the frame: the smaller the identifier, the higher the frame priority. CAN MAC is based on a Non-Destructive Bit Wise Arbitration process. • Identifier is an 11-bit field that identifies the data contained in the frame.

• DLC is a 4-bit field giving the length of the data.

• Data field contains the frames payload (up to 8 bytes).

The CAN frame length L is calculated following the work of Davis et al. [START_REF] Davis | Controller area network (can) schedulability analysis: Refuted, revisited and revised[END_REF] which integrates the worst case overhead induced by bit stuffing using L = 47+8×DLC + 34+8×DLC 4 .

A Full Duplex switched Ethernet network [START_REF] Jasperneite | Deterministic realtime communication with switched ethernet[END_REF] is a collisionfree network. Collisions on the physical link are eliminated since each equipment of the network is only connected to a switch by a Full Duplex link.

B. Interconnection architecture

Fig. 2 presents the illustrative network example studied in this paper. The network consists of three CAN buses interconnected via 3 gateways (G1, G2, G3) and one Ethernet switch. Each gateway interconnects a CAN bus to the switch. In this first study, we assume a basic Ethernet network composed of a single switch but we aim at investigating in the future a more complex network where several switches relay distant real-time data.

The switch includes a set of input and output ports. Only output ports have FIFO queues for storing frames before transmitting them to the next network component. When a frame is received by the switch, the output transmission queue is determined and the frame is enqueued waiting for the transmission on the output link. The switching tables are set up statically and no spanning tree process is used since all flows are known in advance in this type of architecture. This is a reasonable assumption in our context. A CAN flow F i , as depicted in Fig. 3, is a succession of CAN frames F r j characterized by the same period P i , the same identifier (i.e. priority), and an offset O i . Two types of flows will be considered in this paper:

• Local CAN flows: frames of these flows are sent and received on the same bus.

• Remote CAN flows: frames of these flows are transferred from one bus to another one.

III. GATEWAY DESIGN

Fig. 4 summarizes the transmission of a remote CAN frame via the Ethernet switch. The frame is transmitted on its source CAN bus and it arrives in its ingress gateway. It is transformed into an Ethernet frame and transmitted to its egress gateway. It is then transformed again into a CAN frame and transmitted to its CAN destination bus. Formally, an ingress gateway captures remote CAN frames and introduces them into the switched Ethernet network. Conversely, an egress gateway captures switched Ethernet frames and introduces them into the destination CAN bus it is connected to. The endto-end delay of a frame highly depends on the transformation processes which are implemented at the gateways both in the ingress and egress directions. In the following sections, we propose different strategies for both the ingress and the egress transformations.

A. Ingress gateway

As previously mentioned, CAN is a message based protocol (no address field). Conversely, Ethernet uses source and destination addresses for the identification of frames. Thus, an efficient and handy strategy consists in encapsulating CAN frames in the data field of Ethernet frames [4][5]. This process is illustrated in Fig. 5. The remaining problem is to determine how many CAN frames are encapsulated in each Ethernet frame. Indeed, a CAN frame includes at most 8 data bytes, while an Ethernet frame contents up to 1500 bytes. Several possibilities have been evaluated in [START_REF] Scharbarg | Interconnecting can busses via an ethernet backbone[END_REF] [START_REF] Scharbarg | Can-ethernet architectures for real-time applications[END_REF] in the context of vintage Ethernet.

1) The one-to-one strategy: The gateway encapsulates each remote CAN frame it receives in a separate Ethernet frame and this frame is immediately forwarded to the switch. Obviously this strategy minimizes the waiting time of remote CAN frames in their ingress gateways. The drawback of this strategy is that it generates a large overhead on Ethernet (Ethernet frames with few data). Thus the Ethernet bandwidth is not used efficiently.

2) The n-to-one strategy: The gateway encapsulates exactly a given number N of remote CAN frames in each Ethernet frame. Clearly, it will reduce the number of Ethernet frames and increase their size. Thus the use of Ethernet bandwidth is improved. The main drawback of this strategy is that it creates a waiting delay at the ingress gateway for most of the remote CAN frames. Indeed, a remote CAN frame has to wait until there are N -1 other pending remote CAN frames going to the same egress gateway. 3) Timed n-to-one strategy: This encapsulation strategy is a trade-off between the two previous ones. The aim is to use efficiently the Ethernet bandwidth while bounding the delay incurred by remote CAN frames in their ingress gateways. This goal is achieved by associating a timer t i to each remote CAN flow i. This timer t i is started as soon as one frame of flow i arrives in the ingress gateway. An Ethernet frame is built with the pending CAN frames and forwarded to the switch as soon as the timer associated to one pending CAN frame elapses or there are N pending CAN frames. It has been shown in [START_REF] Scharbarg | Interconnecting can busses via an ethernet backbone[END_REF] [START_REF] Scharbarg | Can-ethernet architectures for real-time applications[END_REF] that this strategy outperforms the other ones in the context of vintage Ethernet.

B. Egress gateway

Each time a gateway receives an Ethernet frame, it decapsulates the included remote CAN frames in it and transmits them on the CAN bus. Two approaches are proposed in this paper:

• in the first one (immediate forwarding), remote CAN frames are ready for transmission on the CAN bus as soon as they are decapsulated from the Ethernet frame.

• in the second one (traffic shaping), remote CAN frames can be delayed on their egress gateway in order to regulate the traffic on the CAN bus.

The following paragraphs detail these two approaches. They will be compared on a case study in section IV.

1) Immediate forwarding strategy: This approach is illustrated in Fig. 6, assuming one single CAN flow F i from CAN bus 1 to CAN bus 2. The first frame F r 1 from F i is generated at time t 0 . It is delayed by competing frames on CAN bus 1 and its transmission on this bus is achieved at t 1 . Assuming a one to one strategy at the ingress gateway, F r 1 is encapsulated in an Ethernet frame and immediately forwarded to the gateway of CAN bus 2. F r 1 is then decapsulated and immediately ready for transmission on CAN bus 2 (at time t 2 ). It is delayed by competing frames and finishes transmission on CAN bus 2 at time t 3 . The second frame F r 2 from F i is generated at time t 0 +P i . It is immediately transmitted on CAN bus 1 since there are no competing frames at this instant. Then it is encapsulated in an Ethernet frame and forwarded to the gateway of CAN bus 2. It is decapsulated and immediately ready for transmission (at time t 4 ). It is immediately transmitted, since there are no competing frames at this instant. Similarly the third frame F r 3 of F i is generated at t 0 + 2P i , transmitted on CAN bus 1, forwarded to CAN bus 2 where it is finally transmitted.

We can see on the example of Fig. 6 that F r 1 and F r 2 create a small burst of traffic on the destination bus. Indeed, the time elapsed between the arrival of F r 1 and F r 2 at CAN bus 2 is smaller than the period of flow F i . In other words, the immediate forwarding of remote CAN frames by their egress gateway can reduce significantly the duration between the instants where two consecutive frames of a given CAN flow get ready on their destination bus. Moreover, such a burst of traffic has an impact as well on the delay of the local flows of CAN bus 2 which can be increased. This is even the case for the worst case delay of these flows since its derivation is a function of the periods (or generalized periods) of all flows transmitted on the destination CAN bus [START_REF] Davis | Controller area network (can) schedulability analysis: Refuted, revisited and revised[END_REF]. 2) Traffic shaping strategy: The aim of this strategy is to guarantee a minimum duration between any two consecutive frames of a remote CAN flow on their destination CAN bus. In order to achieve this goal, the egress gateway computes, for each decapsulated remote CAN frame F r j , the time elapsed since the arrival of the previous frame of the same flow in the gateway. If this time is at least the period of the flow, the frame F r j is immediately ready for transmission. Otherwise F r j is delayed so that the period of the flow is guaranteed at the egress gateway level. Fig. 7 shows the impact of this strategy on the example of Fig. 6. The second and third frames of F i are postponed by the gateway of CAN bus 2 in order to guarantee at least P i between any two consecutive frames of Fig. 7. The traffic shaping strategy F i . Thus no burst on flow F i is created on CAN bus 2 and its local flows may not be delayed by the burst of F i anymore. As a consequence, the worst case delay of the local flows is not increased anymore since the period of remote flows is maintained. The next section illustrates the impact of the egress gateway strategies on the delays of flows.

IV. IMPACT OF THE EGRESS GATEWAY POLICIES

The network architecture depicted in Fig. 2 is considered. 42 flows are transmitted on this architecture as given in Table I. 40 of them are local flows: 15 on CAN bus 1, 15 on CAN bus 3, and 10 on CAN bus 2. One remote flow originates on bus 1 while the other one is generated on bus 3. Both of them have their destination on bus 2. These remote flows have the lowest priority on their source bus and the highest one on their destination bus. In the following paragraphs, we show the impact of traffic shaping on a very specific scenario. Then we measure this impact on a random set of scenarios by simulation. At the ingress gateway, the one-to-one strategy is sufficient since there is at most one remote flow generated by each bus.

A. Traffic shaping on a selected scenario

Let's assume that the offsets of all the flows are null. It means that the first frame of each flow is ready for transmission at time 0. Fig. 8 shows the scheduling of frame transmissions on the three CAN buses for two different cases. The top part of Fig. 8 considers immediate forwarding strategy at G2 while the bottom part considers the traffic shaping strategy. For both cases, the 15 local frames of bus 1 and the remote CAN frame are transmitted in this order between time 0 and time 2.1ms. A similar scheduling occurs on bus 3. Thus remote frames 31 and 32 are ready for transmission on bus 2 at time 2.13ms. On this bus, the 10 local frames ready at time 0 are transmitted between time 0 and 1.135ms. At time 2ms, 10 other frames from the local flows of the bus 2 are ready for transmission. The highest priority one (flow 38) is transmitted at time 2ms, since frames 31 and 32 are not ready yet. At the end of the transmission of frame 38, frames 31 and 32 have arrived and they are transmitted since they are pending frames with the highest priority. These transmissions are completed at time 2.4ms. Meanwhile a second frame from flows 31 and 32 has arrived at G2. Indeed, these frames have been generated at bus 1 and 3 at time 2ms and they have been transmitted after frames 5 and 6 which have been generated at the same time and have a higher priority. At this point, the scheduling on bus 2 depends on the egress gateway strategy. When the immediate forwarding strategy is applied (Fig. 8-top), frames 31 and 32 are ready as soon as they are received by G2 at time 2.315ms. Thus, they are transmitted between time 2.4ms and time 2.67ms, delaying local frames 39 to 47. When the traffic shaping strategy is applied (Fig. 8-bottom), frames 31 and 32 have to wait at G2 until their period (i.e. 2ms) has elapsed since the arrival of the previous frames of the same flows. Thus they are ready for transmission at time 4.13ms. Thanks to this delay, frames from local flows are transmitted earlier than with the immediate forwarding strategy. We can conclude that, on this specific scenario the delay of the the second frames of 39 to 47 is decreased of 0.270ms as traffic shaping is applied.

B. Impact of traffic shaping on random scenarios

The previous paragraph shows that traffic shaping at egress gateways can have a positive impact on the delay of local flows. The next question is: is this impact significant if we consider random scenarios (which is the general case since buses are not synchronized)? A simulation campaign has been conducted in order to answer this question for the configuration considered herein.

We have modeled the network architecture of Fig. 2 using Omnet++ simulator [START_REF] Varga | An overview of the omnet++ simulation environment[END_REF]. As a first step, we have considered gateways that implement the immediate forwarding strategy described in Section III-B. As a second step, we have considered gateways that implement the traffic shaping strategy. Flow offsets O i are randomly generated in the interval [0, P i ].

Table II shows the maximum and average end-to-end transmission delays achieved by simulation for both strategies for flows traveling on CAN bus 2. Simulations show that using the traffic shaping on the egress gateway G2 increases maximum and average end-to-end delay of remote flows. This is due to the introduction of the waiting time at the egress gateway level. As expected, traffic shaping of remote flows ). This corresponds to the conclusion of paragraph IV-A. Conversely, the egress gateway strategy has no impact on the average delay of the local flows. Indeed, the shaping can decrease or increase the delay of a frame from a local flow. For instance, in Fig. 8, the delay of the second frame of flow 39 decreases from 0.81ms to 0.54ms, while the delay of the third frame of flow 39 increases from 0.27ms to 0.535ms.

V. CONCLUSION

This paper studies the interconnection of CAN buses through a switched Ethernet network. The interconnection between CAN and Ethernet is done by gateways. The bridging strategy implemented at these gateways is a key issue in such an architecture. We propose different strategies both for the CAN to Ethernet and the Ethernet to CAN directions. We show on an example configuration the impact of the strategy of the Ethernet to CAN direction on the delay of frames. A more comprehensive study is needed in order to better understand the impact of the strategies on the delays. The goal will be to establish guidelines for the choice of the strategies, based on the kind of flows transmitted on the network. We also intend to evaluate the impact of pure Ethernet flows which could share the switched Ethernet network with CAN flows. This could imply the use of QoS mechanism at the switch level. Finally, many real-time Ethernet solutions exist (e.g. TTEthernet, Profinet,...). The introduction of such technologies in our architecture should be evaluated.

Fig. 1 .

 1 Fig. 1. Standard CAN frame format Fig. 1 depicts a standard CAN frame format. The following fields are important to the rest of the paper :

Fig. 2 .

 2 Fig. 2. Illustrative hybrid network architecture

Fig. 3 .

 3 Fig. 3. CAN flow characterization

Fig. 4 .

 4 Fig. 4. Flows transmission over a hybrid network

Fig. 5 .

 5 Fig. 5. Frame encapsulation

Fig. 6 .

 6 Fig. 6. The immediate forwarding strategy

Fig. 8 .

 8 Fig. 8. Network behavior

TABLE II .

 II MAXIMUM AND AVERAGE END-TO-END DELAYS reduces the maximum observed delay of local CAN flows (e.g. from 1.815 ms to 1.632 ms for flow 47