Michel Saideh

Student Member, IEEE Marion Berbineau

Member, IEEE Iyad Dayoub

On the Performance of Sliding Window TD-LMMSE Channel Estimation for 5G Waveforms in High Mobility Scenario

Keywords: 5G, FBMC, LMMSE, Channel Estimation

The upcoming 5G era is considered as a critical answer to future railway communication needs. In this work, we analyze the performance of sliding window time domain LMMSE channel estimation technique where a generalized development is proposed and analyzed for 5G FBMC-(O)QAM waveform candidates. In order to enhance performance, the analytical model is extended to exploit multipaths and multiantennas correlation wherever they do exist e.g., tunnels. TD-LMMSE performance for 5G waveforms and achieved enhancements are verified by Monte Carlo simulations.

I. INTRODUCTION

For the future railway communications related to control and command, the upcoming 5G system where low latency, high mobility, efficient spectrum reuse and asynchronous communications should be supported, is considered as a possible answer for the replacement of the GSM-R system. However, choosing a suitable 5G waveform isn't a straightforward task which has led to the proposal of many 5G waveform candidates [START_REF] Nissel | Filter bank multicarrier modulation schemes for future mobile communications[END_REF]- [START_REF] Berardinelli | Generalized dft-spread-ofdm as 5g waveform[END_REF]. The filtering operation has been widely adopted to avoid the bad frequency localization of the 4G Orthogonal Frequency Division Multiplexing (OFDM) waveform. Hence, a group of candidates have adopted the idea of filtering each subcarrier on its own e.g. Filter Bank Multi Carrier (FBMC) [START_REF] Nissel | Filter bank multicarrier modulation schemes for future mobile communications[END_REF], [START_REF] Nam | A new filter-bank multicarrier system with two prototype filters for qam symbols transmission and reception[END_REF], thus offering outstanding spectral containment enhancements. While others have proposed to apply filtering on each group of subcarriers, e.g. Universal Filtered (UF)-OFDM [START_REF] Vakilian | Universal-filtered multi-carrier technique for wireless systems beyond lte[END_REF], hence offering tradeoffs between time and frequency localizations. Direct modifications have been also applied upon 4G DFTspread-OFDM waveforms, thus guarding a high backward compatibility e.g. Generalized DFT-spread-OFDM [START_REF] Berardinelli | Generalized dft-spread-ofdm as 5g waveform[END_REF].

The highly contained spectrum of FBMC has made it highly suited for efficient spectrum reuse and asynchronous communications. However, the FBMC-QAM version has a loss in its spectral efficency while guards complex orthogonality between its subcarriers. On the other hand, the FBMC spectrally efficient version, the FBMC-Offset QAM (OQAM), suffers from a loss of orthogonality in the complex domain which introduces a new kind of interference, the so called intrinsic interference, that requires special treatment to deal with it. Hence, many interference cancellation schemes at pilot positions have been proposed such as using auxilary pilots [START_REF] Javaudin | Pilot-aided channel estimation for ofdm/oqam[END_REF] or some precoding techniques [START_REF] Nissel | On pilot-symbol aided channel estimation in fbmcoqam[END_REF].

In high speed scenarios, channel estimation becomes more challenging due to the Doppler induced Inter Carrier Interference (ICI). While preamble based channel estimation [START_REF] Kofidis | Preamble-based channel estimation in ofdm/oqam systems: A review[END_REF] is not suited for high speed scenarios, some scattered pilot patterns have been adopted recently for FBMC in Pilot Aided Channel Estimation (PACE) context. [START_REF] Nissel | On the influence of doublyselectivity in pilot-aided channel estimation for fbmc-oqam[END_REF] applied a least square estimation at pilot positions while Minimum Mean Square Error (MMSE) interpolation was used to estimate the channel at data positions. A channel adaptive modulation technique was adopted in [START_REF] Fuhrwerk | Scattered pilot-based channel estimation for channel adaptive fbmc-oqam systems[END_REF] with linear interpolation.

In a previous work [START_REF]Time-domain lmmse channel estimator based on sliding window for ofdm systems in high-mobility situations[END_REF], we have proposed a Time Domain-LMMSE (TD-LMMSE) channel estimation technique for OFDM that adopts a comb pilot pattern and estimates the channel impulse response at the middle of a sliding window. This combination has been able to exploit channel correlation of adjacent time samples within a window for the benefits of the sample in the middle, thus having expelling performance in high speed scenarios. In this paper, we generalize the sliding window TD-LMMSE technique and analyze it for 5G FBMC-(O)QAM waveforms. Analytical development is also proposed to exploit the multipaths and multiantennas correlation, whenever they do exist e.g. tunnels [START_REF] Cocheril | On the importance of the mimo channel correlation in underground railway tunnels[END_REF], High Speed Railways (HSR) [START_REF] Zhang | Empirical correlation property of multi-path for highspeed railways in composite propagation scenario[END_REF] and Vehicule to Vehicule (V2V) [START_REF] Paier | Non-wssus vehicular channel characterization in highway and urban scenarios at 5.2 ghz using the local scattering function[END_REF] environments, thus enhancing performance. Monte Carlo simulations are conducted to verify the analytical development.

This paper is organized as follows. Section II describes the FBMC technique while section III proposes the analytical analysis of TD-LMMSE. Section IV includes the simulation part. The work is concluded in section V.

A. Notations

In the following, bold lowercase variables c represent vectors, bold uppercase variables C represent matrices. C H is the Hermitian conjugate of C. We use Matlab notations where for example C(1, :) means the first row of C. The function diag(x) creates a diagonal matrix with the vector x as its diagonal. is the element-wise product.

II. FILTERBANK MULTICARRIER WAVEFORM

The time domain transmitted signal of a multicarrier system could be written as:

x(t) = K-1 k=0 Z-1 z=0 g z,k (t)s z,k (1)
where s z,k is the symbol transmitted at the z subcarrier and the k time position.

g z,k (t) = f (t -kT )e j2πzF (t-kT ) (2)
T and F are the time and frequency spacings. g z,k (t) is the prototype filter f (t) shifted by kT in time and by zF in frequency.

In discrete time domain, a matrix form of equation ( 1) could be written as:

x = Gs (3)
Where

G = [g 1,1 g 2,1 ...g Z,1 g 1,2 ...g Z,K ] (4)
s = [s 1,1 s 2,1 ...s Z,1 s 1,2 ...s Z,K ] T (5)
g z,k is the N × 1 vector formulated by sampling g z,k (t) in equation ( 2) and gathering the samples within the vector g z,k .

N is the number of samples of the whole transmission block. The fact that OFDM sacrifies the Time Frequency Localization (TFL) property of the Balian Low Theorem (BLT) [START_REF] Sahin | A survey on multicarrier communications: Prototype filters, lattice structures, and implementation aspects[END_REF] theorem to achieve the complex orthogonality G H G = I and the full spectral efficiency T F T 0 F 0 = 1 conditions, where T 0 = 1/F 0 represents the maximal case, has caused major problems in asychronous communications and efficient spectrum reuse applications. Filter bank based waveforms on the other hand are concerned with achieving the TFL advantage by sacrificing other properties. Spectral density of T F = 1 could be sacrificed for example hence permitting us of adopting a well TFL prototype filter within the MC technique. While different FBMC-QAM versions have been proposed [START_REF] Nissel | Filter bank multicarrier modulation schemes for future mobile communications[END_REF], [START_REF] Nam | A new filter-bank multicarrier system with two prototype filters for qam symbols transmission and reception[END_REF], the one that sacrifices the spectral density by increasing the spacing between adjacent subcarriers "F = 2/T " [START_REF] Nissel | Filter bank multicarrier modulation schemes for future mobile communications[END_REF] is adopted in our study since it guards the high frequency localization property and exhibits less ICI which is important in high mobility scenarios and in the study of the time domain LMMSE technique. Different TFL prototype filters could be used in that regard e.g. Hermite, PHYDYAS [START_REF] Bellanger | Fbmc physical layer: a primer[END_REF], Root Raised Cosine (RRC) where each of which has different time frequency localization properties.

A more known FBMC version is the FBMC-OQAM one [START_REF] Nissel | Filter bank multicarrier modulation schemes for future mobile communications[END_REF], which guards the full spectral density feature T F = 1 and the TFL property by sacrificing the orthogonality condition. FBMC-OQAM could be considered as a modified version of the FBMC-QAM where it has the same prototype filter that is designed to be orthogonal for T = T 0 and F = 2/T 0 . However, the following modifications are made:

• Only real symbols are transmitted "PAM" • Time frequency spacing is reduced to T = T 0 /2 and F = 1/T 0 .

• A new phase shift component "e jθ z,k " is added to equation (2) where θ z,k = π 2 (z + k). This is used to shift the interference components, that are added due to the loss of orthogonality, into the imaginary domain. Hence, a new orthogonality condition which stands in the real domain is introduced: {G H G} = I where R{x} is the real part of x.

III. GENERALIZED SLIDING WINDOW TD-LMMSE

The sliding window time domain LMMSE channel estimator is based upon estimating the channel impulse response at the receiver by gathering a window of N w successive received samples in the time domain and estimating the channel impulse response at the middle of this window by using the LMMSE technique. That allows to exploit the correlation between received samples, at both sides of the desired sample, to get a better channel estimate, as it is explained in details in [START_REF]Time-domain lmmse channel estimator based on sliding window for ofdm systems in high-mobility situations[END_REF]. Then, we slide the window one sample, generate the new LMMSE filter, estimate the mid sample, and so on.

In high mobility scenarios, adopting the comb type pilot pattern has shown in our previous work to be preferred than the block type [START_REF]Time-domain lmmse channel estimator based on sliding window for ofdm systems in high-mobility situations[END_REF], hence it is adopted in our study also.

By writing the data and pilot symbols independently, equation (1) could be rewritten in a discrete form as:

x(n) = K-1 k=0 Z-1 z=0 g z,k (n)(p z,k + d z,k ) (6)
Where d z,k and p z,k are the data and pilot symbols, respectively, transmitted at the z subcarrier and the k time position. d z,k (p z,k ) is equal to zero when {z, k} refers to a slot used for pilot (data) symbols. Eq. ( 6) could be rewritten as:

x(n) = x p (n) + x d (n) (7)
where

x p (n) = K-1 k=0 Z-1 z=0 g z,k (n)p z,k (8)
x d (n) = K-1 k=0 Z-1 z=0 g z,k (n)d z,k (9)
x p (n) is the nth sample of the time domain pilot signal which is used to estimate the channel. x d (n) is the nth sample of the time domain data signal that acts as an interference in the estimation process.

Passing through a time variant multipath channel, the nth sample of the received signal could be written as:

y(n) = L-1 l=0 h(n, l)x(n -l) + w(n) (10)
Where h(n, l) is the nth time domain channel sample of the lth path. L is the total number of paths which is assumed to be the same over the time domain. w(n) is the additive white Gaussian noise.

In order to estimate the channel sample h(k, l), we have first to collect the N w surrounding samples of the kth received sample i.e. y k = [y(k -N w /2)...y(k + N w /2 -1)] T . In what follows we omit the subscript k for simplicity. Using [START_REF] Fuhrwerk | Scattered pilot-based channel estimation for channel adaptive fbmc-oqam systems[END_REF] we can write y as:

y = A L-1 l=0 (X p l + X d l )h l + w (11)
A is a mapping matrix used in the CP-OFDM waveform to remove the cyclic prefix. X p l = diag(x p l ) where x p l = [x p (k-N w /2-l)...x p (k+N w /2-1-l)] T . The same definition is used for X d l and

x d l . h l = [h(k-N w /2, l)...h(k+N w /2- 1, l)] T , w = [w(k -N w /2)...w(k + N w /2 -1)] T . x d l = G l d (12)
x

p l = G l p (13)
Where

d = [d 1,1 d 2,1 ...d Z,1 d 1,2 ...d Z,K ] T , p = [p 1,1 p 2,1 ...p Z,1 p 1,2 ...p Z,K ] T , and G l = G(k -N w /2 -l : k + N w /2 -1 -l, :).
Using [START_REF]Time-domain lmmse channel estimator based on sliding window for ofdm systems in high-mobility situations[END_REF] the TD-LMMSE estimates the channel sample h(k, l) using the following equation:

ĥ(k, l) = C -1 yy C yh(k,l) LMMSE filter H y (14)
Where C yy = E yy H is the covariance matrix of the received window y. C yh(k,l) = E yh(k, l) is the correlation matrix between the received window y and the channel sample h(k, l).

Assuming a Wide Sense Stationary Uncorrelated Scattering (WSSUS) channel we can write:

C yy = A L-1 l=0 Rp l,l + Rd l,l R h l h l + R w A H (15) C yh(k,l) = AX p l R h l h l (:, k) (16)
Where eq. ( 15) has been written by noting that

diag(a)Bdiag(a H ) = aa H B ( 17
)
Rp l1,l2 = x p l 1 x H p l 2 , R w = E[ww H
] which is a diagonal matrix with noise variance in its diagonal vector. The N w ×N w channel covariance matrix R h l h l = E h l h H l is a Toepltiz matrix with its first row elements given from Jakes' model for different time samples (n 1 , n 2 ):

R h l h l (1, |n 2 -n 1 |) = α l J 0 (2π(|n 2 -n 1 |)T s f m ) (18)
Where α l depends upon the channel power delay profile. J 0 () is the Bessel function of the first kind with zero order, T s is the sampling period and f m is the maximum Doppler spread.

Rd l1,l2 = E x d l 1 x H d l 2 = G l1 DG H l2 , where D = E[dd H
] is a diagonal matrix with its diagonal elements being equal to the variance of the data symbols at data positions while zeros at pilot positions.

A. Multipaths correlation

The assumption of uncorrelated multipaths is not suitable for all scenarios. Recent studies have shown a good amount of correlation among multipaths in mobile scenarios such as the HSR [START_REF] Zhang | Empirical correlation property of multi-path for highspeed railways in composite propagation scenario[END_REF] and the (V2V) [START_REF] Paier | Non-wssus vehicular channel characterization in highway and urban scenarios at 5.2 ghz using the local scattering function[END_REF] environments. Hence, TD-LMMSE performance could be enhanced by exploiting the channel correlated samples within different multipaths.

By adopting a correlated multipaths scenario, equations ( 15) and ( 16) could be reformulated as follows:

C yy = A L-1 l1=0 L-1 l2=0 Rp l1,l2 +Rd l1,l2 R h l 1 h l 2 +R w A H (19) C yh(k,l1) = A L-1 l2=0 X pj R h l 1 h l 2 (:, k) (20)
For simplicity, we guard Jake's formula of eq. ( 18) while adding multipaths correlation as follows:

R h l 1 h l 2 (1, |n 2 -n 1 |) = ρ l1,l2 α l1 α l2 J 0 (2π(|n 2 -n 1 |)T s f m )
(21) where ρ l1,l2 is the multipaths correlation coefficient between the paths l 1 and l 2 . The channel estimate ĥ(k, l) is given by eq. ( 14).

B. Multi Antenna Correlation

In a similar way, by assuming a SIMO (Single Input Multiple Output) system with M antennas at the receiver, the correlation between the received signals of different antennas, which exists in different scenarios such as in tunnels [START_REF] Cocheril | On the importance of the mimo channel correlation in underground railway tunnels[END_REF], could be exploited thus enhancing the TD-LMMSE performance. The overall received window could be written as:

ỹ = Ã L-1 l=0 ( Xp l + Xd l ) hl + w ( 22
)
where ỹ = [y T 1 y T 2 ...y T M ] T and y m is the received window y from the mth antenna.

Xx l = diag( xx l ) where xx l = [ T x x l 1 T x x l 2 ... T x x l M ] T . hl = [h T l,1 h T l,2 ...h T l,M ]
T where h l,m is the channel vector h l of the mth antenna. Hence, the covariance matrices of the overall received window in (22) could be written as:

C ỹ ỹ = Ã L-1 l1=0 L-1 l2=0 Rp l1,l2 +R dl1,l2 R hl 1 hl 2 +R w ÃH (23) C ỹh(k,l2,m) = Ã L-1 l1=0 Xp l 1 R hl 1 hl 2 (:, km) (24)
Where h(k, l, m) is the kth channel sample of the lth path and the mth antenna. Rp l1,l2 = xp l 1 xH

p l 2 , R dl1,l2 = E[ xd l 1 xH d l 2 ], R w = E[ w wH ], R hl 1 hl 2 = E[ hl1 hH l2 ] is the M N w × M N w channel covariance matrix which is a combination of M 2
Toeplitz matrix where the first row elements of each are given for different n 2 , n 1 values by:

R hl 1 hl 2 (m 1 , m 2 |n 2 -n 1 |) = β l1l2m1m2 J 0 (2π(|n 2 -n 1 |)T s f m ) (25) Where β l1l2m1m2 = γ m1,m2 ρ l1,l2 α l1 α l2 (26)
γ m1,m2 is the correlation coefficient between the antennas m 1 and m 2 . The estimated channel sample could be written as:

ĥ(k, l, m) = C -1 ỹ ỹ C ỹh(k,l,m) H ỹ (27)

C. Complexity analysis

From equation ( 27) we can see that the calculation of h(k, l, m) comes with a complexity of (M N w ) 2 + LM N w where (M N w ) 2 corresponds to the calculation of

C -1 ỹ ỹ ỹ while LM N w corresponds to C H ỹh(k,l,m) (C -1 ỹ ỹ ỹ).
In the special cases of a SISO system and/or ρ = 0, complexity could be calculated by substituting with M = 1 and/or L = 1, respectively.

To reduce complexity, which is mainly due to the matrix inversion, we have suggested in [START_REF]Time-domain lmmse channel estimator based on sliding window for ofdm systems in high-mobility situations[END_REF] to fix our window during each MC symbol. That means we calculate C -1 ỹ ỹ once for each symbol while C ỹh(k,l,m) is calculated on a sample basis. In addition, the use of a periodic pilot sequence means that Rp l1,l2 is the same among symbols. Adding this to the fact that in some communication environments we have a fixed trajectory, e.g. trains, means that the channel statistics and SNR values would be similar each time the train passes by the same location. Hence, C -1 ỹ ỹ could be calculated offline for different channel statistics and SNR values and stored in a database.

D. Normalized mean square error

The normalized mean square error could be written as [START_REF] Haykin | Adaptive filter theory[END_REF]

N M SE k,l,m = σ 2 h(k,l,m) -σ 2 ĥ(k,l,m) σ 2 h(k,l,m) (28)
where σ 2 h(k,l,m) is the variance of h(k, l, m) and

σ 2 ĥ(k,l,m) = C H ỹk h(k,l,m) C -1 ỹk ỹk C ỹk h(k,l,m) (29)
The average NMSE over one MC symbol is:

N M SE = 1 N LM k,l,m N M SE k,l,m (30)
IV. SIMULATION

In this section, we demonstrate the simulation part where we report the numerical results. We adopt Jakes's model to demonstrate the time varying nature of the channel with a normalized square power delay profile where L = 7. We adopt a subcarrier spacing of 15 KHz, carrier frequency f c = 2.5 GHz, pilot spacing of S p = 6, a window size of 3 OFDM symbols, a mobile speed of 400 km/h, and a (1 × 4) SIMO system are adopted. Z=256 and K is chosen in a way to include all significant interferers. FBMC prototype filters are designed with an overlapping factor value of 4. A cyclic prefix of six samples length and 3000 repetitions for Montecarlo simulations are used. In fig. 1 we show the theoretical and numerical performance of the TD-LMMSE technique for CP-OFDM and FBMC-(O)QAM where different prototype filters are adopted "PHYDYAS [START_REF] Bellanger | Fbmc physical layer: a primer[END_REF], Hermite, Root Raised Cosine (RRC)" with uncorrelated antennas and multipaths. We note that PHYDYAS prototype filter offers better performance than Hermite and RRC due to the fact that it is more localized in the frequency domain. Hence, we adopt the PHYDYAS filter in what follows. Fig. 2 shows the enhancements in performance by the adoption of the multipaths correlation assumption. We assumed for simplicity that multipaths are correlated with each others by the same correlation coefficient ρ and pictured the performance for different values of ρ = 0.4, 0.7, 0.9. reasonable In fig. 3 we simulate the multi antennas correlation case. For clarity, we depict the performance of the FBMC-QAM only. We assume once again that antennas are correlated with each others with the same value γ and we simulate the performance for different correlation values of (ρ = 0, γ = 0.4, 0.7, 0.9). We note that the enhancement in performance fall within the low SNR region only. To sum up, we consider both the SIMO correlation and multipaths correlation assumptions altogether. For clarity, we adopt a correlation coefficient of 0.7 and simulate the performance of FBMC-OQAM only. Fig. 4 depicts the cases of no correlation at all (γ = 0, ρ = 0), only SIMO's correlation (γ = 0.7, ρ = 0), only multipaths correlation (γ = 0, ρ = 0.7), and the case where both SIMO and multipaths correlations exist (γ = 0.7, ρ = 0.7). In this paper, the TD-LMMSE channel estimation technique, which suits high mobility scenarios, has been analyzed for FBMC-(O)QAM based waveforms. This has been made by first proposing a generalized analytical development of the TD-LMMSE. The fact that a comb type pilot pattern was adopted means that the interference is coming only from adjacent subcarriers in the frequency domain and not from the time domain. Hence, PHYDYAS filter has shown better performance than Hermite and RRC filters since it has better frequency localization. It has been also shown that FBMC-QAM offers better performance in the high speed scenarios due to the fact that the subcarriers spacing is twice that of FBMC-OQAM and OFDM, hence there is less ICI. Exploiting multipaths and multiantennas correlation have enhanced all waveforms performance. This was verified by Monte Carlo simulations. Future works include enhancing the TD-LMMSE performance for FBMC-OQAM by proposing ICI cancellation schemes.

VI. ACKNOWLEDGMENT

Figure 1 .

 1 Figure 1. NMSE vs SNR for CP-OFDM and FBMC-(O)QAM with different prototype filters. WSSUS assumption and uncorrelated SIMO are adopted (ρ = 0, γ = 0)

Figure 2 .

 2 Figure 2. CP-OFDM and FBMC-(O)QAM performance with PHYDYAS and ρ = 0.4, 0.7, 0.9, γ = 0

MonteCarloFigure 3 .

 3 Figure3. FBMC-QAM performance with PHYDYAS prototype filter and ρ = 0, γ = 0.4, 0.7, 0.9

MonteCarloFigure 4 .

 4 Figure 4. FBMC-OQAM performance with PHYDYAS prototype filter while adopting both a correlated multipaths and a correlated antennas assumption

This work has been performed within the SMARTIES project within the ELSAT2020 program supported by FEDER, the French State and the Haut de France Region and also the X2RAIL-1 project from H2020 SHIF2RAIL program.


Rabab Bouziane
email: rabab.bouziane@inria.fr

Erven Rohou
email: erven.rohou@inria.fr

Abdoulaye Gamatié
email: abdoulaye.gamatie@lirmm.fr

Energy-Efficient Memory Mappings based on Partial WCET Analysis and Multi-Retention Time STT-RAM

Energy-efficiency has become one major challenge in both embedded and high-performance computing. Different approaches have been investigated to solve the challenge, e.g., heterogeneous multicore, system runtime and device-level power management. This paper targets emerging non volatile memories (NVMs), through Spin-Transfer Torque RAM (STT-RAM), which inherently have quasi-null leakage. This enables to reduce the static power consumption, which tends to become dominant in modern systems. The usage of NVM in memory hierarchy comes however at the cost of expensive write operations in terms of latency and energy. In order to mitigate this detrimental feature, this paper leverages the notion of delta worst-case execution time (δ -WCET), which consists of partial WCET estimates. From program analysis, δ -WCETs are determined and used to safely allocate data to NVM memory banks with variable data retention times. The δ -WCET analysis computes the WCET between any two locations in a function code, i.e., between basic blocks or instructions. Our approach is validated on the Mälardalen benchmark suite and significant memory dynamic energy reductions (up to 80 %, and 66 % on average) are reported.

INTRODUCTION

Energy-efficiency has become one major challenge in several computing domains, including embedded and high-performance computing domains. Examples of approaches for addressing the issue are system runtime management, heterogeneous multicores and device-level power management.

In the particular case of embedded domain, e.g., the Internet of Things (IoT), devices are increasingly considering non-volatile memories (NVMs) for their ability to favor normally-off computing that aggressively powers off devices. Thanks to their inherent non-volatility property, the information stored within the NVM can be safely recovered when the system is powered on later. During the switch-off period of the system, neither leakage nor refresh power are involved to preserve the information. This property of NVMs makes them highly attractive w.r.t. classical memory technologies such as SRAM or DRAM.

In the current study, we consider a specific emerging NVM, named Spin-Torque Transfer random access memory (STT-RAM) [START_REF] Boukhobza | Emerging NVM: A Survey on Architectural Integration and Research Challenges[END_REF]. While such a technology has a quasi-null leakage, one major challenge concerns the mitigation of its high write latency and energy cost. Indeed, depending to the NVM technology, writes are several times more costly compared to SRAM or DRAM.

Non-volatility refers to extremely long retention time. Current non volatile RAMs (NVRAMs) are designed with 10+ years of data retention in order to favor higher memory reliability [START_REF] Smullen | Relaxing Non-volatility for Fast and Energy-efficient STT-RAM Caches[END_REF]. Yet, many other NVM technology designs are possible, which enable to build multi-bank memories with variable retention times [START_REF] Sun | Multi Retention Level STT-RAM Cache Designs with a Dynamic Refresh Scheme[END_REF]. This opens an interesting opportunity because memories with shorter retention times have much cheaper latency and energy costs, and typical variables in programs often have a much shorter lifetime. The next section motivates this opportunity.

Motivational Example

Consider the example of Figure 1. The instructions using the three variables a, b and i result in five different memory writes (store instructions) as shown in the control flow graph. The first three initialize the variables in block 22, the last two update the values of i (i++) and b (b=b+i) in block 23. The lifetime of a value is defined as the duration between its ANNOT_MAXITER is a macro that stores this information in a dedicated ELF section of the binary, retrieved by the Heptane tool [START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF] and attached to the CFG. The lifetimes of its five store instructions are shown in (c). Hence, even with a large value of N, most values written to memory only require a short retention time. This is shown in Figure 1 (c): only one value increases proportionally to N.

As an example, let us assume a flat memory (i.e., no cache), with the read/write energy costs from Khoshavi et al. [START_REF] Khoshavi | Read-Tuned STT-RAM and eDRAM Cache Hierarchies for Throughput and Energy Enhancement[END_REF], also summarized in Table 1. Let α R t (resp. α W t ) be the cost a single read (resp. write) to a memory bank with retention time t, the cost of executing the program with a 10-years retention NVM memory is:

E 0 = N × (4α R 10yr + 2α W 10yr ) + 3α W 10yr
If a 10 ms retention memory bank is available, stores (1), ( 2), (3), and (4) can be assigned to it. For large values of N, store (0) must be assigned to the longer bank (for N ≥ 66655, the lifetime exceed 400,002 cycles, i.e. 10 ms at 40 MHz as in our experimental setup). The energy cost therefore becomes:

E 1 = N × (3α R 10ms + α R 10yr + 2α W 10ms ) + α W 10yr + 2α W 10ms
The energy gain is E 0 -E1 E 0 ≃ 31 %. The above simple example motivates the potential energy gain from the design compromise enabled by NVM technologies with variable retention time. This feature can be leveraged through multi-bank memory systems. Mapping variables to the most appropriate memory bank will result in significant reduction of overall memory energy. However the mapping must guarantee that the lifetimes of data stored in memory will not exceed the retention time of their allocated memory bank, in any circumstances.

Our Contribution

In this paper, we exploit static analysis and worst-case execution time techniques to estimate an upper bound of the lifetime of every store instruction in programs. Given, this information, we map each store to the most appropriate memory bank according to the most suitable NVM retention time available. Our results show that significant energy reduction can be obtained with only a few banks, favoring energy-efficient memory designs.

We summarize our contribution as follows:

• an extension of program WCET analysis with the possibility to compute the partial worst-case execution time (δ -WCET 1 ) of any portion of a program;

• exploitation of the δ -WCET analysis to compute the worst-case lifetime for variables defined in store instructions of a program; • multi-bank NVM memory allocation of variables based on their worst-case lifetime characterizations and memory data retention times; • validation of the proposed approach on the Mälardalen [START_REF] Gustafsson | The Mälardalen WCET benchmarks: Past, present and future[END_REF] benchmark-suite (composed of 18 workloads) to show up to 80 % (and 66 % on average) dynamic energy reduction on memory, while considering design calibration parameters from NVM literature.

The rest of this paper is organized as follows. Section 2 reviews related work. We introduce necessary background on the Heptane tool in Section 3, and develop our methodology in Section 4. Finally, we evaluate our approach in Section 5 and conclude in Section 6.

RELATED WORK

We discuss below existing studies on the energy-efficiency of NVM-based systems and WCET estimation in general.

Energy-Efficiency of NVM Caches

There are a number of studies devoted to energy-efficiency of NVM-based caches. Reducing the impact of their expensive write operations was the main objective.

Zhou et al. in [START_REF] Zhou | Energy reduction for STT-RAM using early write termination[END_REF] proposed a technique called Early Write Termination for reducing write energy with no performance penalty. It is a write process with the capability of early termination in case of a redundant write. It is implemented at the circuit level. Smullen et al. [START_REF] Smullen | Relaxing Non-volatility for Fast and Energy-efficient STT-RAM Caches[END_REF] investigated an approach that focuses on technology level to redesign STT-RAM memory cells. They lower the data retention time in STT-RAM, which induces the reduction of the write current on such a memory. This enables in turn to decrease the high dynamic energy and latency of writes.

Other approaches addressed the energy-efficiency issue by considering hybrid cache memories using hardware mechanisms to migrate data between NVM and SRAM memory blocks. The idea is to keep as many write-intensive data in the SRAM blocks as possible in order to reduce the number of write operations to the NVM blocks. Li et al. [START_REF] Li | MAC: Migration-aware Compilation for STT-RAM Based Hybrid Cache in Embedded Systems[END_REF] proposed a migration-aware compilation for STT-RAM-based hybrid cache, by re-arranging data layout to reduce the overhead of migrations. Hu et al. [START_REF] Hu | Data Allocation Optimization for Hybrid Scratch Pad Memory With SRAM and Nonvolatile Memory[END_REF] presented an approach based on region partitioning in order to generate optimized data allocation. A program is divided into regions and before executing each region, a data allocation is generated, which is suitable for the region. In [START_REF] Bouziane | Compile-Time Silent-Store Elimination for Energy Efficiency: an Analytic Evaluation for Non-Volatile Cache Memory[END_REF], we presented an approach to reduce energy consumption by eliminating so-called silent stores, i.e., store instruction instances that write to NVMs values, which were already present there. Our approach is a compile-time technique that helps to mitigate the penalty of such stores, particularly on NVMs.

WCET Estimation

WCET estimation of programs provides an upper bound of task execution time, used for guaranteeing that real-time requirements of a system are met. Traditionally, WCETs are estimated at the granularity of a function. Many tools of WCET estimation are proposed in the literature. Wilhelm et al. [START_REF] Wilhelm | The Worst-case Execution-time Problem -Overview of Methods and Survey of Tools[END_REF] presented an overview of methods and existing tools. Two classes of methods are distinguished: static methods and measurement-based methods. Static methods do not rely on real hardware executions. They analyze the code itself, combine the control flow graph with a model of the hardware architecture, and produce an upper bound of this combination, which is the WCET. On the other hand, measurement-based methods execute the code on real hardware or a simulator for certain inputs. Then, based on the measured times, the minimal and maximal execution times are derived.

The notion of partial WCET (δ -WCET) considered in the current work is recent to the field. It has been recently addressed by Jacobs et al. [START_REF] Jacobs | WCET Analysis for Multi-core Processors with Shared Buses and Event-driven Bus Arbitration[END_REF], where they focus on interference of concurrent tasks sharing a bus, and they compute for how many cycles concurrent cores may be granted access to the resource in any time interval of a given length. Avila et al.

[1] also used the concept of δ -WCET, associated with the gain time. The difference between the estimated WCET and the actual execution time is known as gain time. Early identification of gain time requires to obtain δ -WCETs of the code instead of considering the code as a whole. The authors placed gain points in the program where they measured the actual execution time. These measurements are used to identify all sources of pessimism in the WCET analysis. Oehlert et al. [START_REF] Oehlert | Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis[END_REF] presented a compiler-based extraction of event arrival curves using CFGs. In order to determine the maximum/minimum number of events in a specific time interval, all possible paths in this CFG have to be considered. Their approach is an extension of the work presented by Jacobs et al. [START_REF] Jacobs | WCET Analysis for Multi-core Processors with Shared Buses and Event-driven Bus Arbitration[END_REF]. Then, they suggested an alternative idea where the objective function is set to maximize the number of events on a sub-path to be chosen in a CFG. Our work differs from this idea in that it rather aims to maximize the WCET in a given sub-path of the CFG.

BACKGROUND: THE HEPTANE TOOL

We consider Heptane [START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF], a static WCET estimation tool. The aim of Heptane is to produce upper bounds of the execution times of applications. It targets applications with hard realtime requirements (automotive, railway, aerospace domains). It computes WCETs using static analysis at the binary code level. It is divided in two parts: HeptaneExtract and Heptane-Analysis. HeptaneExtract generates the control flow graph G from a program compiled from C language. Then, it identifies the different loops, attaches the loop bounds information provided by the programmer and attaches the instruction addresses based on the binary file. Heptane does not include the analysis of maximum number of loops iterations, which are not always statically computable in the general case. Thus, loops must be annotated by the user with their maximum number of iterations (maxiter) 2 . Afterwards, HeptaneAnalysis implements IPET (Implicit Path Enumeration Technique) along with cache analysis techniques for several cache architectures [START_REF] Wilhelm | The Worst-case Execution-time Problem -Overview of Methods and Survey of Tools[END_REF]. Static WCET estimation methods are divided into two steps: high-level analysis and low-level analysis (see Figure 2). The high-level analysis consists of determining the longest execution path. The low-level analysis takes into consideration the micro architecture. For the high-level analysis, Heptane performs an IPET analysis, based on Integer Linear Programming (ILP) formulation of the WCET estimation problem. The program flow is mapped into a set of graph flow constraints. An upper bound of the program's WCET is then obtained by maximizing the following objective function: max i n i × w i where w i is the timing information of the basic block i (constant in the ILP problem) determined by the low-level analysis, and n i is the number of times the basic block i is executed (variable in the ILP problem). A basic block is a set of sequential instructions.

For the low-level analysis, Heptane performs data address analysis, cache analysis and pipeline analysis. The pipeline analysis for all supported architectures currently considers a simple in-order pipeline. Note that Heptane performs context-sensitive analysis, which means that every call path 2 External tools such as oRange [START_REF] De Michiel | Partial Flow Analysis with oRange[END_REF] are able to provide loops upper bounds of C programs in some cases. of a function is analyzed separately, e.g. main →foo→bar, and main→bar, where bar is called directly from main but also from foo. Therefore, the objective function will be like the following: max i n i _c × w i , where w i is the timing information of the basic block i in the context c and n i _c is the number of times the basic block i is executed in the context c. The ILP problem is solved by a solver such as lp_solve or cplex by maximizing the objective function and identifying the paths that lead to the estimated WCET.

The WCET estimation depends on the CFG structure of the program, the number and type of instructions inside blocks, but also on the capability of Heptane to apply address and cache analysis to bound the number of cache misses.

PROPOSED METHODOLOGY

Our methodology is a two-step process, illustrated in Figure 3. First, we identify the def-use chains in the program (step referred to as "Reaching loads"). In other words, for each store instruction, we determine all the loads that can read the value previously written. Second, we compute the worst-case execution time between the store and all subsequent loads (step referred to as "δ -WCET"). For this purpose we have developed a method to compute partial WCET estimates which we present in Section 4.1 (further details can be found in our previous work [START_REF] Bouziane | Partial Worst-Case Execution Time Analysis[END_REF]). We then present how we apply it to the case of worst-case lifetimes in Section 4.2. Both steps are entirely static analyses.

δ -WCET Estimation

A program is given as a binary executable input (both ARM and MIPS instruction sets are supported) and an entry point (function main). Considering two basic blocks A and B, we are interested in estimating the WCET from block A to block B, which is the δ -WCET from A to B (item (2) of Figure 3). The δ -WCET estimation is based on the WCET estimation. Considering a subgraph of the CFG, the objective will be to make Heptane derive the δ -WCET from its analysis for the whole CFG. Thus, we first compute the WCET estimate for the entire program, which consists in computing Modify w i based on whether A and/or B are inside a loop or not ▷ Maxiter analysis for each basic block its WCET estimate, and its worst-case execution frequency. Through this step, we obtain the system constraints of the original ILP that we want to use later for δ -WCET estimations, as well as the contextual analysis. Secondly, given two blocks A and B, we compute the set of blocks and edges that can be traversed in any path from A to B. Consider the example on Figure 1, where we selected block A=22 and B=25. All blocks 22, 23, 24, and 25 must be considered, which means that all the blocks in the different paths leading to B must be considered. We achieve this by iterating a depth-first search (DFS) on the CFG, starting from node A, until we reach B or a block that reaches B. Note that the WCET path from A to B is not necessarily on the overall WCET, i.e, the path from A to B may not be a part of the longest path in the overall program, thus, the WCET from A to B is not a sub-WCET of the program's WCET. Then, we compose a new ILP problem for the subgraph G ′ obtained from the DFS, to compute the WCET from A to B (see Algorithm 1 for the details). Therefore, the objective function will include the nodes in G ′ along with the callee nodes (with the callee context) if there is a function call. Moreover, in order to tighten the WCET (make it less pessimistic), we analyze the maxiter annotations. The potential for improvement comes from the fact that the user annotation applies to the execution of the entire function, while we consider only a subgraph. We take into account the following cases, as illustrated in Figure 1:

(1) The backedge is part of the subgraph, hence the loop may execute its maximum number of iterations on a path from A to B. This is the case of the store instruction with ID 0 in Figure 1(b). We keep the value of maxiter unmodified. (2) The backedge is not part of subgraph, as examplified by the store with ID=1 in Figure 1(b): the lifetime created in block 22 (initialization of variable i) is killed in block 23 by store ID=4 (i++). We set maxiter=0 so that the ILP formulation for the subgraph does not consider pessimistic frequencies due to the loop structure. (3) The backedge is part of subgraph, but it does not contribute to any cycle. Consider for example the lifetime created by store with ID=3 (storing the result of b=b+i). Hence, we set maxiter=1. So, the new ILP problem, presented as: max i n i _c × w i where n i ∈ BetweenBlock (A, B), has a new system constraints, slightly different from the original one to consider the above cases. Note that the maxiter modification is applied to all backedges that are not part of the subgraph. The whole implementation of the δ -WCET algorithm has been done inside Heptane, as shown in Figure 2. Given a start node A and an end node B, the high-level analysis of Heptane performs IPET analysis along with the contextual analysis to estimate WCET and then performs the depth-first search and creates a new ILP problem using the contextual analysis related to the output of the DFS and the maxiter analysis. The contextual analysis here consists of including in the ILP objective function, the callee nodes with their callee context if there is any function call in the DFS output nodes.

Linking δ -WCET to NVM Allocation

Data retention time is another parameter one can consider when designing a "non-volatile" memory. Standard STT-RAM cells usually target several years data retention period, e.g., 10-years [START_REF] Smullen | Relaxing Non-volatility for Fast and Energy-efficient STT-RAM Caches[END_REF] for reliability concern. However, different designs can target shorter retention times, coming with gains in memory access latency and energy as shown in Table 1.

We envision a system with memory banks designed for various energy/retention time trade-offs. Knowing at designtime the amount of time a data is needed would let a compiler allocate data to appropriate memory banks.

Assigning a write with a certain lifetime to the appropriate memory bank will help us reduce the energy consumption by avoiding expensive write energy for writes with low lifetimes. Identifying the subsequent reads for each write is done through a dataflow analysis called reaching definitions which statically determines which definitions may reach a given point in the code (item (2) of Figure 3).

Reaching definitions are used to compute use-def chains and def-use chains:

• use-def chain: consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions; • def-use chain: consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definition. We use the def-use chain where a definition d is a store and the reachable uses u are the loads. A definition d1 reaches point u1 if there is a path from d1 to u1 such that d1 is not killed along that path. In Figure 4, d0 is a definition that is never killed and its use is u2, which explains why its lifetime is the highest one. However, d1 is killed by d4. The uses of d1 are u1 and u3; hence, after d4, d1 is no longer available.

Figure 4: Example of reaching definitions

We implemented the computation of def-use chains in Heptane in order to compute, for every write instruction S, the subsequent load instructions L1, L2..., Ln and to define the subgraphs. Array accesses are handled in a safe (pessimistic) manner. We then create an ILP problem for every combination S, {Li} in order to estimate the δ -WCET p i from S to Li as shown in the Algorithm 1. Then, the lifetime of the store S is the maximum value of p i . We repeat this step to compute the lifetimes of all stores in the given program.

Regarding the concrete implementation of variables mapping to memory banks, both software and hardware approaches could be envisioned, as applied previously for scratchpad memories [START_REF] Idrissi | A Survey of Scratch-Pad Memory Management Techniques for low-power and -energy[END_REF]. For instance, a simple solution consists in extending the instruction set with specialized load and store instructions, one for each memory bank (alternatively, the load/store could be extended with an extra parameter to specify the bank). Given the worst-case lifetimes, it is a fairly simple compiler job -or even post-processor on the assembly -to optimize each instruction. It is important that the code size does not change in order to maintain the validity of the analysis carried out by Heptane. The implementation of the above mapping solution belongs to short-term perspectives.

VALIDATION ON BENCHMARK-SUITE 5.1 Experimental setup

We experimented with the Mälardalen Benchmarks, a typical suite for WCET-related experiments. Benchmarks were compiled for ARM using GCC. We slightly modified the code to increase execution times which are otherwise too small: all lifetimes would be far below our lowest threshold, making gains artificially high. As customary with real-time systems, no optimization is applied (optimization level -O0). The reason for this is the need to keep source-level annotations consistent with the binary representation. Compiler optimizations heavily restructure the program representation, to the point that the CFG representation at binary level cannot be matched with the source level, making annotations invalid 3 . The ILP problems are solved by cplex and the resolution times are realistic. To assess the impact on the energy consumed by the memory, we need the number of reads and writes to all memory locations. Thus, we instrumented the benchmarks using DynamoRIO4 , a runtime code manipulation system that supports code transformations on any part of a program, while it executes, to obtain traces of execution. Through the traces, we count the number of occurrences for each store as well as for its subsequent loads, to estimate the energy. The overall setup is shown in Figure 3.

Architectural Setup for IoT Domain

In Internet of Things (IoT) systems, connected devices are able to sense and collect data from the environment. These devices are typically battery powered. To maintain a long period of autonomy, they must be able to manage their energy as long as possible. Therefore, the energy consumption is a critical constraint in the design of an IoT device. An IoT device is most of the time inactive, switching to low-power mode (sleep mode) and waiting for the next task. Consequently, sleep mode power will consumes an important part of energy and battery life, as the transition to the active mode will required additional energy to exit the sleep mode and become fully operational. Several Microcontrollers (MCUs) targeting low-power applications implement several powerdown modes with different transition times that depend on the current low-power mode from which the MCU decides to return to the active mode. The most popular choice of NVM in an MCU is an embedded-flash memory which can be used for both code-storage and data storage applications. However, as for all types of NVM, characterized by their density and low leakage, write operations are much expensive than read operations. By relaxing its retention time, we can reduce the energy cost of a write operation. Partitioning a flash memory into different blocks where each set of blocks has a retention time can help to save an important amount of the energy consumption. In this work, we target an IoT architecture (see Figure 5), with a frequency of 40 MHz, where the read and write latency is 1 cycle and where the flash memory has a high retention time (up to 10 years). We mainly consider the memory subsystem, as in low-power designs, the core consumption of the core is extremely low. As an example, the Cortus APS25s+ core [START_REF]APS25s+ -Enhanced Performance Embedded Microcontroller With Leading Code Density[END_REF] is rated at 17.9 µW/MHz, i.e. 716 µW at 40 MHz. The memory systems we consider consume 2 nJ (resp. 1 nJ) per write. Assuming a write every 10 instructions at 40 MHz, the power would be (40.10 6 × 2.10 -9 )/10 = 8.10 -3 W , i.e. 8 mW (resp. 4 mW), an order of magnitude larger than the core.

Lifetimes Evaluation on Benchmarks

As a prior step to data allocation in multi-retention memory, we apply the proposed δ -WCET-based analysis to the different workloads of the Mälardalen benchmark-suite. The expected results are the lifetimes distributions according to the benchmarks. Here, by lifetimes distributions we mean the way the computed lifetimes are spread through a program. Due to the diversity of these benchmarks, the corresponding distributions in terms of store instructions vary from one benchmark to another. We can categorize the distributions according to the write-intensiveness of the benchmarks.

In this study, we distinguish a static store from a dynamic store: the former is basically an instruction, while the latter is an execution instance of the former. Figure 6 summarizes the worst-case lifetimes of static store instructions found in the subset of write-intensive workloads, i.e workloads that contain a significant number of write operations, from the Mälardalen benchmark-suite. The X and Y axes respectively denote the write instructions and their corresponding worstcase lifetime in clock cycles, while operating at a frequency of 40 MHz. We note that half of the benchmark-suite falls into this category. In order to build a few clusters of store instructions on the base of their estimated worst-case lifetimes, we consider three duration thresholds featuring three memory retention times: 26.5 µs, 3.24 s and 4.27 years, taken from Sun et al. [START_REF] Sun | Multi Retention Level STT-RAM Cache Designs with a Dynamic Refresh Scheme[END_REF] (see Table 2). It clearly appears that the identified store instructions can be partitioned into different groups w.r.t. the three lifetime thresholds. For instance, in the fft benchmark (top-middle), all store instruction lifetimes fall into two clusters: either below 26.5 µs threshold or below 3.24 s threshold; in the qurt benchmark (center), the identified lifetimes are partitioned in three clusters: either below 26.5 µs threshold or below 3.24 s threshold or above 3.24 s threshold. Therefore, this information can be leveraged to reduce energy consumption by allocating the stored data memory accesses to appropriate NVM banks. Figure 7 shows the subset of benchmarks that contain fewer static store instructions compared to those profiled in Figure 6. While the expected energy gain may a priori sound limited for write-light benchmarks, it is not necessarily true since a small number of static store instructions executed several times, e.g., in a loop, could have a non negligible impact on the overall memory energy consumption.

According to its lifetime, each store instruction will be associated with a dynamic energy cost corresponding to the memory retention threshold targeted for this instruction. From the execution traces of benchmarks, we determine how many times such instructions are executed, and we finally estimate the energy for each benchmark.

Evolution of lifetimes with program duration. As discussed in Section 1.1, not all lifetimes are equal. Some are constant, regardless of the number of iterations (such as lifetimes related to variables b and i of Figure 1(b), others vary (such as variable a). We confirmed that the same applies beyond our motivational example. Figure 8 shows how lifetimes evolve when the number of iterations of the main loop grows in sqrt. Clearly the first ten lifetimes remain unchanged, while the last six increase proportionally, suggesting optimization potentials, even for large run times.

Gain evaluation

To evaluate how NVMs with variable retention times have prominent impact on energy consumption, we consider different memory setups depending on the target memory bank sizes. We already introduced one possible setup in Table 2 featuring a 4 MB STT-RAM memory size. Now, let us consider another memory setup featuring smaller memory banks with a size of 32 KB (based on the same technology [START_REF] Sun | Multi Retention Level STT-RAM Cache Designs with a Dynamic Refresh Scheme[END_REF]). The energy consumption for this new setup according to the same retention times is summarized in Table 3. Note that write energy costs overall are smaller, and read costs are also reduced for shorter retention times. Given the above setups, we evaluate the energy gain, which mainly comes from the assignment of store operations to appropriate banks based on their worst lifetimes, hence reducing the corresponding write energy. Since the leakage of NVMs is almost null, we only focus on their dynamic energy, i.e., induced by read and write operations. We formulate the energy consumed by loads and stores as:

E = N R × α R + N W × α W (1)
where N R and N W are respectively the number of read and write executions and α R and α W are respectively the dynamic energies of a read and a write operation. In a system where we have three different banks, we have three different α R and α W . Therefore, the energy consumed by loads and stores will become as follows:

E = i ∈ {NVM retention times} N R i × α R i + N W i × α W i (2)
where N R i and N W i are respectively the number of read and write executions (obtained from profiling) on the NVM bank i and α R i and α W i are respectively the dynamic energies of a read and a write operation on bank i.

By applying the above formulas, we compute the dynamic energy gain, as illustrated in Figure 9 for the Mälardalen Figure 9 shows that we achieved with the small memory configuration up to 80 % of energy gain compared to the baseline (small memory with 4.27 years retention time) and up to 75 % with the large memory configuration. In fact, dynamic energy of read and write operations on a small size memory are less expensive compared to the large size memory.

Generally speaking, the energy gain depends on how many times a store is executed on a specific bank of memory. For illustration, Figure 10 shows for three benchmarks how many times each static store instruction has been executed (NW) and how many times the stored value has been read (NR), before getting rewritten. The trend observed for these benchmarks is representative of the overall benchmark-suite.

In the ud benchmark, the major part of the store instructions is executed more than 10 4 times. More than half of these instructions have low lifetimes. This is beneficial for energy saving. The statemate benchmark, which shows more lifetimes requiring higher retention times (falling strongly in the memory region with a retention time of 4.27 years), has less energy savings among the three benchmarks. As expected, with both small and large memory configurations, the lowest energy gain is for this benchmark.

In the matmult benchmark, we can notice the possible detrimental impact of high NR values despite an important number of store instructions with short lifetimes. This benchmark shows a gain of 60 % as shown in Figure 9, for the small memory setup. However, this gain grows down to 55 % when considering the large memory setup, in which the cost of read energy is multiplied by more than two and half.

CONCLUSION AND PERSPECTIVES

In this paper, we applied a partial worst-case execution time (δ -WCET) analysis to programs in order to determine the worst-case lifetimes of program variables involved in store instructions. This information is then used to safely allocate these variables in appropriate NVM memory banks, according to their data retention time. We validated our approach on the Mälardalen benchmark-suite, by showing a significant reduction of memory dynamic energy (up to 80%, with an average of 66%). This contributes to answer the energy-efficiency challenge faced in both embedded and high-performance computing domains.

The short-term perspective to this work concerns the implementation of variables mapping to memory banks. While both software and hardware approaches could be considered, we plan to focus on the former approach. More precisely, we will explore a compiler-oriented approach to post-process the assembly for deciding the mappings based on the preevaluated worst-case lifetimes. Further research directions address cache-based architectures. Indeed, the case study presented in this paper, features a cache-less system. More generally, NVMs can be exploited at different levels of the memory hierarchy. As discussed in Section 2, they can be leveraged through hybrid designs where they are combined with traditional memory technologies, e.g., SRAM or DRAM. Data layout guided by worst-case lifetimes could be key to drive each piece of data to the appropriate memory bank.

  # d e f i n e N 10 i n t main ( void ) { i n t a , b , i ; a = N ; b = 0 ; f o r ( i = 0 ; i <a ; i + + ) { ANNOT_MAXITER( motivational example (b) control-flow graph and memory access instructions (c) duration of the lifetimes created by each store instruction, for different numbers of iterations of the loop, and 10 ms threshold

Figure 1 :

 1 Figure 1: A sample program (a), with its associated Control Flow Graph -CFG (b). The loop iterates ten times.ANNOT_MAXITER is a macro that stores this information in a dedicated ELF section of the binary, retrieved by the Heptane tool[START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF] and attached to the CFG. The lifetimes of its five store instructions are shown in (c).

Figure 2 :

 2 Figure 2: Heptane extended with δ -WCET analysis (blue dashed-box components added by current work).

Figure 3 :

 3 Figure 3: Sketch of our framework (input: C code).

Algorithm 1 3 :▷ the list of nodes encountered in possible paths 6 : 8 : 9 :

 13689 General δ -WCET algorithm 1: procedure BetweenBlocks(A,B) 2: L = DFS (A, B) ▷ nodes in DFS stack at completion for all nodes N visited in the DFS and N L do 4: L = L ∪ DFS (N , B) procedure Generation of the ILP problem from A to B 7: L = BetweenBlocks (A, B) max i n i _c × w i where i ∈ L ▷ the rest of the basic blocks are excluded by setting their w i to 0 for all calls in L do 10:add to the objective function the callee nodes with their callee context 11:

Figure 5 :

 5 Figure 5: MCU containing a processor, SRAM, embedded Flash, and programmable I/O peripherals

Figure 6 :

 6 Figure 6: Worst-case lifetimes of static store instructions for write-intensive workloads from the Mälardalen benchmark-suite: the X and Y axes respectively represent the write instructions and their corresponding worstcase lifetime in cycles at 40 MHz. Two duration thresholds are made explicit along the Y axis (26.5µs and 3.24s).

Figure 7 :

 7 Figure 7: Worst-case lifetimes of static store instructions for write-light workloads from the Mälardalen benchmark-suite: the X and Y axes respectively represent the write occurrences and their corresponding worstcase lifetime in cycles at 40 MHz. Two duration thresholds are made explicit along the Y axis (26.5 µs and 3.24 s).

Figure 8 :

 8 Figure 8: Lifetime distribution in sqrt for different values of MAXITER (i.e., N)

Figure 9 :

 9 Figure 9: Energy savings based on Tables 3 and 2 setup w.r.t. a 4.27 yr STT-RAM memory

Figure 10 :

 10 Figure 10: Number of executed static store instruction (NW) and how many times the stored value has been read (NR), before being rewritten. X, Y-left and Y-right axes are respectively store identifiers, lifetimes in cycles and the values of NR and NW.

Table 1 :

 1

	10 years	0.233	0.601
	10 ms	0.233	0.269

Retention time Read energy (nJ): α R Write energy (nJ): α W Two 512 KB NVM retention times

[START_REF] Khoshavi | Read-Tuned STT-RAM and eDRAM Cache Hierarchies for Throughput and Energy Enhancement[END_REF]

definition (i.e., a write) and its last use (i.e., a load) before it is redefined. The lifetimes created by all the stores are very different. Store (0) in block 22 creates a lifetime that spans the entire duration of the program because it is defined at the beginning and read in each iteration of the loop. Conversely, the lifetimes defined by stores (1) and (2) in block 22 only reach the first iteration of block 23 in which they are redefined. The same holds for the data lifetimes defined at stores (3) and (4) in block 23, alive only across one iteration.

Table 2 :

 2

4 MB NVM memory retention times

[START_REF] Sun | Multi Retention Level STT-RAM Cache Designs with a Dynamic Refresh Scheme[END_REF]

Table 3 :

 3 32 KB NVM memory retention times[START_REF] Sun | Multi Retention Level STT-RAM Cache Designs with a Dynamic Refresh Scheme[END_REF]

We previously described further useful applications of δ -WCETs[START_REF] Bouziane | Partial Worst-Case Execution Time Analysis[END_REF]. Please note that the acronym pWCET, used previously[START_REF] Bouziane | Partial Worst-Case Execution Time Analysis[END_REF], has been modified into δ -WCET in the current paper upon a suggestion from anonymous reviewers in order to avoid a confusion with "probabilistic" WCET.

Li et al. [12] traced annotations via compiler optimizations, but this requires heavy compiler machinery and is not in the focus of this work.

http://www.dynamorio.org/

ACKNOWLEDGEMENTS

This work has been funded by the French ANR agency under the grant ANR-15-CE25-0007-01, within the framework of the CONTINUUM project.


A Govin
email: govin@emse.fr

P Grosseau

C Lors

D Damidot
email: denis.damidot@imt-lille-douai.fr

IMPACT OF A THIN COATING LAYER OF CALCIUM ALUMINATE AND SULFOALUMINATE CEMENTS ON ALGAL BIOFOULING

Keywords: biofouling, mortar, algae, calcium aluminate cement

The aim of the study is to evaluate the bioreceptivity to green algae of a thin layer of mortar based on Calcium Aluminate, SulfoAluminate and Portland cements. The results highlight the ability of Calcium Aluminate Cement (CAC) thin coating to inhibit the algal colonization on the duration of the test. SulfoAluminate Cement (SAC) did not affect the biocolonization. Through Avrami's model, it is shown that CAC strongly inhibits the growth of algae, while the SAC slightly inhibits the growth but strongly promotes the attachment of algal cells.

1.

Instructions to authors submitting a final paper

Authors should submit a final paper corresponding to the accepted abstract no later than 15 January 2018. The organisers do not commit themselves to include in the Proceedings any paper received later than the abovementioned deadline. At least one of the authors must register and pay his/her registration fee during the advance period (before 15 April 2018) for their paper to be included in the final programme of the Conference. In case an author has more than one paper, the registration would be valid only for one paper and co-author/s should be registered for publication of multiple papers.

This document provides information and instructions for preparing a paper to be included in the Proceedings of the RILEM 253-MCI Conference. Papers and all related correspondences should be written in English.

In the manuscript, the paper article should be preceded by one page containing the author(s) information (as in this page). The page should contain the paper title, abstract ID number (given by the organisers), keywords, e-mail and postal address of each author. The first name will indicate the principal/corresponding author and those that follow, the co-authors in the order of precedence. INTRODUCTION Building materials are progressively and inevitably subjected to biological colonization [START_REF] Hendry | Masonry walls: materials and construction[END_REF]. More especially, the facades of buildings become more and more bioreceptive due to their exposition to weathering rain, wind, sunlight, and CO 2 , etc. The term "bioreceptivity", as defined by Guillitte, corresponds to "the ability of a material to be colonized by one or more groups of living organisms without necessarily inducing biodeterioration" [START_REF] Guillitte | Bioreceptivity: a new concept for building ecology studies[END_REF]. Regarding facades of buildings, biological stains affect clearly their aesthetics and represent a significant economic loss, due to the costs of cleaning works. The color of the biofilm is mainly green, black or red, depending on the biological species, themselves depending on climatic conditions, geographic location, exposure ([3][4] [START_REF] Rindi | Diversity, Distribution and Ecology of Green Algae and Cyanobacteria in Urban Habitats[END_REF]). Several biological organisms can be involved in the biocolonization of façades, such as bacteria, cyanobacteria, algae, fungi and lichen. Among these microorganisms, cyanobacteria and algae are predominant in the biofilm formed on the substrates, and they are the first colonizers after bacteria [START_REF] Tomaselli | Biodiversity of photosynthetic microorganisms dwelling on stone monuments[END_REF].

The intensity and kinetics of biological colonization of buildings surfaces depends on the environment and the substrate [START_REF] Crispim | Algal and cyanobacterial biofilms on calcareous historic buildings[END_REF] [START_REF] John | Algal growth on buildings: A general review and methods of treatment[END_REF]. Physical (roughness, porosity) and chemical (mineralogical/chemical composition, surface pH) characteristics of the substrate influence biological colonization [START_REF] Ortega-Calvo | Factors affecting the weathering and colonization of monuments by phototrophic microorganisms[END_REF] [START_REF] Deruelle | Rôle du support dans la croissance des microorganismes[END_REF]. It was shown that calcium aluminate cement (CAC) exhibits a greater resistance than ordinary Portland cement (OPC) to inorganic or organic acids produced by microorganisms, such as sulfur-oxidizing bacteria or fungi [START_REF] Herisson | Toward an accelerated biodeterioration test to understand the behavior of Portland and calcium aluminate cementitious materials in sewer networks[END_REF][12] [START_REF] Govin | Development of an accelerated test of fungal biodeterioration: Application to calcium aluminate cements[END_REF]. The growth of green algae, such as Klebsormidium flaccidum, is also slowed down by CAC [START_REF] Grosseau | Effect of the Chemical Composition of Building Materials on Algal Biofouling[END_REF].

The aim of the present study is to combine the potential resistance to the proliferation of green algae by CAC, while reducing costs by decreasing the amount of CAC used. A SulfoAluminate Cement (SAC) was also tested. The objective is to highlight the effect of the chemical composition of the cement used in mortar on the attachment capacity of green algae and on their growth during a laboratory test. The experimental algal colonization was simulated by Avrami's model and the rate constants related to algal attachment and growth were extracted.

EXPERIMENTAL APPROACH AND RESULTS

In order to reduce the cost of the materials, a thin coating of 1 mm thick, of CAC-based mortar and of SAC-based mortar were deposited on the surface of an OPC-based substrate (labeled CEMI). An OPC-based coating, with the same composition, was also tested as reference. The bioreceptivity of the samples were tested using a biofouling laboratory test.

During the experiments, a suspension containing the green alga, Klebsormidium flaccidum, was periodically sprinkled (1.5h each 12h) on the top of the tested samples inclined at 45°. A specific image analysis method, based on image segmentation using a pixel supervised classification, was developed and used to quantify the colonization rate of each sample. An in situ evaluation of the biofouling was also investigated. Samples with the same design were also exposed to natural conditions on a bench located outdoors in Douai (North of France) (device is described in [START_REF] Dalod | Influence de la composition chimique de mortiers sur leur biodétérioration par les algues[END_REF]).

RESULTS

By applying Avrami's model (eq. 1), the colonization rate was then simulated and was described by two processes: attachment of algal cells and their growth. Indeed, the colonization is initiated by the attachment of algae on the surface of the samples. It results in the appearance of very small green spots on the surface, corresponding to algae, which can be assimilated to nuclei in the Avrami's model. These algal spots are detected after a specific time called latency time (tl). The extension of the colonization results from the growth of the first algal spots and from the adhesion of new ones, as in the Avrami's model. These two processes are characterized by two rate constants, Kg (Spot.day -1 .µm -2 ) and Kc (µm.day -1 ), corresponding to the attachment and the algal growth, respectively.

n l K(t t ) X(t) 1 e   (1)
with

2 gc K AK K  (2) 2 A (q 1)(q 2)(q 3)     (3)
n q 3  (4)
The rate constant correlated to algal attachment (Kg), as well as, (q) were determined from image analysis data by quantifying the number of new algal spots appearing between two images, using eq. 5.

q gl dγ K (t t ) dt    (5)
Where  is the number of algal spots at time t per unit area (Spot/mm 2 ) (q) was found to be equal to one for each formulation. Finally, the rate constant related to algal growth (Kc) was calculated from K, Kc and q previously determined.

The results show that Avrami's model is suitable to simulate the algal colonization of cementitious materials. The results from laboratory test highlight that the CAC coating inhibits the algal colonization of the samples. Conversely, the SAC did not seem to affect the colonization rate. However, despite the same colonization rate, the SAC promoted the attachment of algae (higher Kg) but partially inhibited their growth (lower Kc), compared to the OPC. The inhibition of the algal growth was strongly increased by the CAC, since Kc was around ten times lower than for CEM I. Moreover, the latency time seemed to be affected by the chemical composition of the coating. Indeed, CAC exhibited higher latency time than the two other cements.

CONCLUSIONS

 The results confirmed the ability of CAC to exhibit an algaecide effect, even if the deposit was only a 1 mm thick coating, conversely to SAC.  Avrami's model is suitable to simulate the colonization rate of cement-based mortars.  The attachment rate constant (Kg) was weakly affected by CAC but strongly by SAC.  The growth rate constant (Kc) and, to a lesser extent, the latency time (tl) are affected by the chemical composition of the mortar. The growth rate constant was around ten times lower for CAC-based mortar than for the reference. The CAC strongly inhibits the algal growth.

Figure 1 :

 1 Figure 1: a) Evolution of the experimental and simulated Colonization rate for each tested mortar, b) attachment rate constant, c) latency time, d) growth rate constant