Sindhu Preetham Burugupally

David Hoelzle

Experimental investigation of curved electrode actuator dynamics in viscous dielectric media

Keywords: Curved electrode, dynamic response, electrostatic actuator, viscous dielectric media

Micromanipulation of biological cells inside a liquid environment requires an actuator that has a small footprint to reduce viscous drag, and low actuation voltage to prevent electrolysis and Joule heating. Curved electrode actuators hold the promise for underwater micromanipulation because they yield large displacements at low actuation voltages for a small footprint. In this letter, we report on the frequency-domain characteristics of the actuator and demonstrate that the actuator can achieve large displacements (1-10 µm) and generates large forces (1-21 µN) at low actuation voltages (8 V) over 1-1000 Hz frequency range in a viscous dielectric media.

An actuator designed to manipulate or probe biological cells at high speeds must be able to operate in an aqueous environment and achieve the following performance metrics: large displacement (1-10 µm) and force (1-25 µN); and broadband frequency (1-1000 Hz) at low actuation voltages (≤8 V). [START_REF] Preetham | Napa Microsystems Workshop[END_REF] Electrostatic actuators are shown to benefit from high relative permitivitty ( r =80) of aqueous media yielding large forces at low actuation voltages. [START_REF] Shih | [END_REF] However, in an aqueous environment, the viscous drag on the actuator surface decreases the quality (Q) factor by at least four orders of magnitude, ? challenging large displacements at high frequencies. As such, comb drive actuators are not strong enough to achieve these metrics at the requisite voltages without large comb arrays which amplify viscous drag. Parallel plate actuators benefit from an electrostatic spring softening nonlinearity that enables high electrostatic force gains, and thus high speed operation, but this same nonlinearity limits displacement by the pull-in instability. 3,[START_REF] Senturia | Microsystem Design[END_REF] Curved electrode actuators hold promise for large displacement, high bandwidth actuation in an underwater environment because of a mechanical spring hardening nonlinearity that counteracts the electrostatic spring softening nonlinearity, extending the usable displacement range while maintaining large electrostatic force gain from a small electrode gap. [START_REF] Preetham | [END_REF]6 Curved electrode actuators are designed to be operated at voltages, V , exceeding the pull-in voltage, V P I (Fig. 1). At V > V P I , the beam electrode comes in contact with the curved electrode and increasing the voltage causes the contact point, a, to zip along the face of the curved electrode. This zipping action results in a shortening of the sprung beam length, L -a, leading to a spring hardening nonlinearity that counteracts the eleca) Electronic mail: sindhupreetham.burugupally@wichita.edu trostatic spring softening nonlinearity, and thus a stable operation past the pull-in voltage, V P I (Fig. 1b). Additionally, the small contact distanced between the beam and curved electrodes provides high displacement gain, permitting large displacement (10 µm), large force generation (10 µN), and high frequency operation (1000 Hz) with low voltages (8 V) and small actuator footprints. To achieve the aforementioned performance metrics of the actuator, we redesigned a curved electrode actuator [7][8][9] in a clamped-clamped beam configuration. [START_REF] Preetham | [END_REF] In this letter, we investigate the dynamics of this actuator in a high viscous media, where Q-factor

1. Here, we present experimental demonstration of the actuator dynamics in two different viscous media: deionized (DI) water and methanol, and demonstrate that the actuator can achieve the desired performance metrics, making it a suitable candidate for micromanipulation of biological cells suspended in aqueous media.

The actuator operates on the principle of electrostatics and is fabricated from silicon (<100> p-type boron doped to 100 ppm) using micromachining techniques [START_REF] Preetham | [END_REF] with the physical parameters given in Table I. The curved electrostatic actuator comprises of three main components: a beam electrode, a reinforcing beam, and a set of four curved electrodes (Fig. 1). The curved electrodes drive the beam electrode in forward and backward directions that deliver the generated force and displacement strokes to the reinforcing beam which in turn delivers to an external load. Note that the reinforcing beam increases the bandwidth frequency of the actuator. The curved electrodes are immovable rigid members whose contour s(x) is described by a second order polynomial function, s(x) = δ m (x/L) 2 ∀ x ∈ [0, L], where δ m is the maximum throw of the curved electrode, x is the coordinate along the beam electrode, and L is the half-length of the beam electrode (Fig. 1b). The beam electrode and the reinforcing beam together form a compliant clamped- clamped structure. The curved electrodes and the beam electrode are coated with 10 nm thick aluminum oxide film for electrical insulation. The actuator is totally submerged in the viscous dielectric media such as DI water and methanol.

As shown in Fig. 1a, energizing the actuator by supplying two amplitude-modulated voltage signals

V A (t) = 1 2 V (1 + cos 2πf t)Π(t) and V B (t) = 1 2 V (1 -cos 2πf t)Π(t)
will result in the shuttling of the actuator -back and forth in-plane -with a peak-to-peak displacement amplitude 2w(L). Here, V is the voltage amplitude, cos 2πf t and -cos 2πf t are the modulation waveforms, t is the time, [START_REF] Shih | [END_REF] Because the reinforcing beam displacement is small in comparison to the available throw, we approximate damping coefficient b to be a constant. The displacement and the force can be modulated by tuning the actuation voltages V A (t) and V B (t) (Fig. 1). Based on the actuation voltage amplitude V and the actuation frequency f , the actuator operates in one of the two modes: nonzipped and zipped. In the nonzipped mode, the beam electrode does not come in physical contact with the curved electrode, while in the zipped mode, the beam electrode comes in physical contact with the curved electrode (Fig. 1b).

Π(t) = 4 π ∞ j=1 1 2j-1 (-1) j-1 cos 2πf c jt is a high- TABLE I.
The actuator is characterized in terms of actuator peak-to-peak displacement amplitude 2w(L) at different voltage amplitudes V ∈ [4, 8] V in the increments of 1 V and actuation frequencies f ∈ [1, 4096] Hz in the increments of 2 N/2 , where N ∈ [0, 24]. The actuator is taped to the bottom of a petri dish and the petri dish is filled with the viscous media of interest. The test facility is comprised of an inverted microscope (Zeiss Observer A1 microscope, Oberkochen, Germany) and high-speed camera (Miro M110, Vision Research, Wayne, NJ, USA) for cinephotomicrography of the moving actuator in the region of interest ROI (Fig. 1c), LabVIEW/NI PCIe-6343 data acquisition system for triggering the high-speed

camera to initiate cinephotomicrography and generating two modulation waveforms

V a (t) = 1 2 V (1 + cos 2πf t), V b (t) = 1 2 V (1 -cos 2πf t)
, a function generator (Tektronix AFG3022C, Beaverton, OR, USA) to multiply these modulation waveforms by Π(t) and to generate two amplitude-modulated voltage waveforms V A and V B , and three x-y-z test probes (XYZ Micropositioner, Quater Research and Development, Bend, OR, USA) to connect the ground and voltages V A and V B to the actuator contact pads. For given actuation voltages V A and V B , the cinephotomicrography was recorded at frame rates > 10 times the corresponding actuation frequency f ; however, for f =4096 Hz, the frame rate is set to 6.1f due to the light sensitivity limits of our high-speed camera.

The actuator is first characterized in deionized water and later in methanol media. During the change of media, the actuator is first triple rinsed in the later media (methanol) and then three times flushed with media and cyclically driven to full peak-to-peak displacement amplitude for 10 minutes. A custom image processing MATLAB R script is used to segment the cinephotomicrograph into frames, measures the actuator location in each frame, and then creates time traces of this measurement for follow-up analyses of frequency content and peak-to-peak displacement amplitude 2w(L).

The actuator displacement is measured in the region of interest (ROI) using the high-speed camera and inverted microscope (Fig. 1c). Fig. 2 provides a representative displacement signal trace at high-frequency operation in deionized water. Note that at this frequency the dis- f BW =200 Hz placement trace approximates a sinusoidal wave and that the peak displacement lags the actuation signal peak V B .

f BW f BW =80 Hz 4 V 5 V 6 V 8 V 7 V =60 Hz Zipped 8 V 7 V 6 V 5 V 4 V
Actuator performance over the entire operating range is better elucidated in frequency response plots in Fig. 3. The most obvious performance features is that the actuator operates in two basic modes -nonzipped and zipped. Additionally, the actuator behaves as a first-order overdamped system, as characterized by the -20 dB/decade magnitude slope at high frequencies (Fig. 3a inset). Our Q-factor is 1 because of the highly viscous environment; the lower frequency of the two real poles is at approximately 200 Hz and the higher frequency real pole is beyond the frequency range we tested. There are more subtle features of the input voltage amplitude-frequency operating space that will be described in the following.

Beam electrode zipping greatly enhances the actu-

ator displacement, at least doubling the displacement (Fig. 3). In the zipped mode, the beam and curved electrodes of the actuator will come in physical contact, greatly reducing the electrode gap and providing a strong amplification of electrostatic force, hence a higher actuator displacement w(L). A high relative permitivitty of the media also enhances the actuator displacement. For instance, in low actuation frequencies f < 100 Hz where the inertial and viscous fluid effects on the actuator are negligible -it can be seen that the actuator's displacement 2w(L) is enhanced in deionized water (high r ; r =80) by up to 6 µm and 2 µm in zipped and nonzipped modes, respectively, relative to methanol (low r ; r =32) (Fig. 3). The difference in force generated by the actuator, hence displacement, would be even higher in comparison to actuation in air (low r ; r = 1), as has been demonstrated by Legtenberg et al. 2. Zipping enhances a system nonlinearity that causes an increase in bandwidth frequency with increasing V (Fig. 3). For instance, the actuator bandwidth frequencies f BW in deionized water for 5 V and 8 V are approximately 80 and 200 Hz, respectively. Similarly, the bandwidth frequencies f BW in methanol media for 6 V and 8 V are approximately 60 and 200 Hz, respectively. In the zipped operations, the effective stiffness of the actuator k is proportional to 1 (L-a) 3 , where L -a is the sprung length of the electrode. A higher the voltage amplitude V will result in a shorter sprung length and higher actuator stiffness, and thus a higher bandwidth frequency. On the contrary, the media introduces inertial loading and viscous damping, both of which are known to decrease the bandwidth frequency and increase actuator pull-in times.

3. Although the actuator is a nonlinear system 5 , the actuator dynamics are approximately linear in the nonzipped mode: low V and/or high f (Fig. 4). Applying a sinusoidal forcing function with frequency f = 1 Hz on the actuator for the zipped mode (8 V) excites the higher odd harmonics f 2n+1 (∀ n ∈ Z >0 ) in the actuator, as measured by ap-plying the discrete Fourier transform (DFT) to the displacement trace 2w(L). Note that the n th order harmonic frequency f n = nf and the nondimensional DFT amplitude

a n = 2 M | M -1 m=0 2w(L) |m e -j 2πnm M | max 2w(L) |f =1 Hz . (1)
As can be seen in equation 1, a n is scaled with peak-to-peak actuator amplitude, max 2w(L) for f = 1 Hz. Here, j = √ -1 and M is the number of sample points used in displacement measurement 2w(L). The presence of higher odd harmonics in the zipped mode results in a clipped sinusoidal response instead of an approximately sinusoidal response. This bears a resemblance of the characteristics of a quasi-harmonic nonlinear system with an external harmonic force of frequency f 1 . 14 However, for the nonzipped mode (4 V), the higher odd harmonics f 2n+1 (∀ n ∈ N) vanish with the appearance of a very low amplitude (< 0.1a 1 ) second harmonic response f 2 . In this operating mode, the actuator approximates a linear system. In the high V and high f operation, the actuator is again nonzipped, yielding a f 3 harmonic that vanishes in relation to the f 1 harmonic (Fig. 4c). Please note that for a high actuation frequency f =4096 Hz, the frame rate is set to 6.1f due to the limits placed by the camera speed (frames per second); here, the acquisition of the actuator displacement signal 2w(L) containing the third harmonics (f 3 ) satisfies the Nyquist-Shannon Sampling Criterion (≥ 2f 3 ), but the sampling rate is below the commonly accepted rule-of-thumb of 10 times the frequency of interest.

4. The available mechanical power P at the reinforcing beam of the actuator is on the order of a nano-Watt, calculated using the relation P =

1 f 1/f t=0 2l
x=0 F.dw(x, t) (Fig. 5). The reinforcing beam displacement w(x, t) is given by the relation w(x, t) = φ(x)w(L, t), where φ(x) is the approximate first mode shape for a clamped-clamped beam 15 and w(L, t) is the displacement of actuator at x = L (equals displacement of the reinforcing beam at x = l). Note that the work done by the beam sprung force and inertia force over one oscillation are zero. Since there is no external load on the reinforcing beam, the available mechanical power is dissipated as heat due to the viscous effect of the media. The available power peaks at 2048 Hz and 2896 Hz for deionized water and methanol, respectively. The sudden dip at 2048 Hz in methanol is due to the smaller actuator displacement 2w(L) at 2048 Hz (2.0 µm) compared to 2896 Hz (2.4 µm) (Fig. 3). In summary, this letter details an experimental characterization of the dynamics of a curved electrode actuator, which has the favorable properties of a large displacement and high frequency range with a low input voltage, but has not been sufficiently described for dynamic operation in viscous media. Four experimental observations are reported: (1) a higher relative permittivity of the media has enhanced the actuator displacement; (2) the zipping mode of operation has enhanced the operating range of the actuator in terms of displacement and bandwidth frequency; (3) to analytically describe the actuator motion, a minimum of first six odd normal modes are required; and (4) the mechanical power available at the reinforcing beam is on the order of a nano-Watt. The experiment results: provide an indication of how many normal modes will be required to analytically describe motion in future theoretical and computational studies; and demonstrate that the actuator can achieve displacements on the order of a biological cell diameter (1-10 µm) and generates large forces (1-21 µN) at low actuation voltages (8 V) over 1-1000 Hz frequency range in a viscous aqueous media, making the actuator a suitable microsystem for micromanipulation of biological cells suspended in aqueous media.

FIG. 1 .

 1 FIG. 1. Curved electrode actuator. (a) Schematic sketch of the actuator in unenergized state with actuation voltages VA and VB, and actuator displacement w(L) shown. (b) One-half of the actuator in zipped mode with annotated design parameters. (c) Stereomicroscopy of the top view of the actuator with the region of interest (ROI) shown by a black-dashed box. The figure inset shows a scanning electron microscopy (SEM) of the actuator electrode and its gaps (gap height = 30.7 µm; gap width = 3.8 µm) in side view after 65% completion of the DRIE BOSCH process. The silicon is yet to be etched to 45 µm deep before released from glass substrate by HF wet etch (Reproduced with permission from Springer Nature Microsyst Technol (2018) 24: 3479. Copyright 2018 Springer-Verlag GmbH Germany, part of Springer Nature). See Ref. 5 for fabrication details.

  Nominal and measured actuator parameters, and physical parameters. Nominal parameters are given by a single number. The measured parameters are given as mean ± standard deviation for four measurements. Parameter Numerical value Beam electrode half-length, L 1000 µm Beam electrode height, h 45 ± 0.4 µm Beam electrode thickness, t 4.7 ± 0.2 µm Electrode gap, g 3.5 ± 0.1 µm Reinforcing beam half-length, l 670 µm Reinforcing beam stiffness, 2kr 4.4 N/m Dynamic viscosity of DI water 0.89 mPa-s Dynamic viscosity of methanol 0.54 mPa-s Viscous damping coefficient in DI water 6.43 µN-s/m Viscous damping coefficient in methanol 3.90 µN-s/m Young's modulus of Si 10 , E 130 GPa Relative permittivity of Al2O3 9 Relative permittivity ( r ) of DI water 80 Relative permittivity ( r ) of methanol, 32 frequency, zero-mean pulse signal to prevent charge shielding effects 11-13 , and f and f c = 500 kHz are the modulation (also called actuation) and carrier frequencies, respectively. The force F generated by the actuator electrodes is estimated using the Newton's second law of motion equation, F = 2k r w(L) + b ẇ(L) + m e ẅ(L), where 2k r is the stiffness of the reinforcing beam, w(L) is the displacement amplitude of the actuator or reinforcing beam, b models the viscous damping on the reinforcing beam, m e is the effective mass of the reinforcing beam and inertial mass of the viscous media, and single overdot and double overdots are first and second temporal derivatives, respectively. The viscous damping coefficient b is computed using the relation given in Shih et al.

FIG. 2 .

 2 FIG. 2. (a) Time-lapsed images of one period of oscillation in the region of interest (shown in the red-dashed box). (b) Measured displacement trace of the actuator in deionized water for 8 V at 512 Hz in the region of interest (ROI). The displacement 2w(L) is shown in blue solid line, while the actuation voltages VA and VB are shown in black and red solid lines, respectively. When no voltage is applied, the actuator is in the neutral position. The displacement measurement has a quantization error of ± 1/2 pixel = ± 0.15 µm.

InsetFIG. 3 .

 3 FIG. 3. Measured frequency response of the actuator for different actuation voltage amplitudes V ∈ [4, 8] V in (a) deionized water (b) methanol. In figure (a) inset, the displacement amplitude defined in terms of decibels (dB) is scaled with respect to the actuator displacement amplitude w(L) at frequency f = 1 Hz and corresponding actuation voltage amplitude V = 4 or 8 V.

FIG. 4 .

 4 FIG. 4. Measured actuator response in deionized water. (a) Discrete Fourier transform (DFT) of the measured actuator displacement at f = 1 Hz actuation frequency in zipped and nonzipped operations. Here, the frame rate is 40 times the actuation frequency f and hence prevents aliasing for harmonic frequencies of up to 19 th order, f19. The nondimensional DFT amplitude an is scaled with actuator peak-to-peak amplitude max 2w(L) as shown in equation 1. Figure inset shows actuator displacement trace for nonzipped (4 V) and zipped (8 V) at 1 Hz. The displacement measurement has a quantization error of ± 1/2 pixel = ± 0.15 µm. (b) Ratio of DFT amplitudes a3/a1 over 1-4096 Hz frequency range for different voltages, where a1 and a3 correspond to DFT amplitudes at frequencies f1 and f3, respectively.

7

 7

FIG. 5 .

 5 FIG. 5. Estimated available power at the reinforcing beam of the actuator over 1-4096 Hz frequency range for different actuation voltage amplitudes V ∈ [4, 8] V in (a) deionized water (b) methanol. Inset shows a schematic sketch of the actuator and its equivalent lumped model with stiffness 2kr, damping coefficient b, effective mass me, and generated force F applied on the reinforcing beam.

  This work was supported in part by University of Notre Dame Walther Cancer Foundation IITP Fellowship, American Cancer Society Award IRG 14-195-01, Notre Dame Clare Boothe Luce Fellowship, Notre Dame Advanced Diagnostics & Therapeutics Berry Family Foundation Fellowship, and Wichita State, Notre Dame, and Ohio State capitalization funds. Technical consultation was given by the Notre Dame Nanofabrication Facility.

M. Sathyamoorthy, Nonlinear Analysis of Structures (1997), CRC Press Revivals (CRC Press, 2017).


Arturo Ortiz-Tapia
email: aortiztapia2013@gmail.com

Golden Ratios, Lucas Sequences and the Quadratic Family

Keywords: Quadratic family, golden ratio, generalized Lucas sequence

It is conjectured that there is a converging sequence of some generalized Fibonacci ratios, given the difference between consecutive ratios, such as the golden ratio ϕ 1 and the next golden ratio ϕ 2 . Moreover, the graphic depiction of those ratios shows some overlap with the quadratic family, and some numerical evidence suggests that all those ratios in the finite set obtained, belong to at least one quadratic family.

1 Introduction

The Golden Ratio and Beauty

What is beauty? When can something be called beautiful ? Beauty has been defined in many different ways throughout cultures [START_REF] Eco | History of beauty[END_REF]. An ancient attempt to define beauty systematically, was through the golden ratio. Golden ratio is the number ϕ ≈ 1.6180339887 • • • , and its inverse 1/ϕ ≈ 0.6180339887 • • • which is often associated with it. The number ϕ can be defined in several ways, one of them is through a recurrent process involving the Fibonacci numbers [START_REF] Lucas | Théorie des nombres[END_REF]

ϕ = lim n→∞ F n+1 F n (1)
where

F n = F n-1 + F n-2 (2)
with initial values F 0 = 1, F 1 = 1.

Lucas Numbers

Actually, one can start with other initial values, say F 0 = 1, F 1 = 3 and still converge to the same value of ϕ (or its inverse) when the proportion between predecessor and successor is taken as n → ∞. The sequence of numbers is known as Lucas sequence, and the component numbers, Lucas numbers [START_REF] Niven | An introduction to the theory of numbers[END_REF]. In fact, it shouldn't be hard to prove that all the initial values imposed in (Eq. 2) do is to shift individual members of the Lucas sequence, but again they will converge to ϕ.

2 Other ϕ's

Positive ϕ's

So, how can one obtain a convergence to a value other than ϕ ? It turns out that one has to add more members to the recurrence in (Eq. 2), for example [START_REF] Falcon | On the k-lucas numbers[END_REF][START_REF] Miles | Generalized Fibonacci numbers and associated matrices[END_REF]]

L n = L n-1 + L n-2 + • • • + L n-k , k ∈ +Z (3)
without loss of generality, the initial values to these Lucas sequences can be stated as

L 0 = 1, L 1 = 1, • • • L k-1 = 1 (4)
and let be defined ϕ k be the value to which convergences (Eq.5 )

ϕ k = lim n→∞ L k n+1 L k n (5)
or their inverse

1/ϕ k = lim n→∞ L k n L k n+1 (6)
For convenience, from now on inverses will be used, and for simplicity they will be called ϕ k . For the purposes of this paper, the Lucas numbers were calculated using the Wolfram Mathematica command RecurrenceTable (with n = 100, i.e., 100 terms were taken), and then each ϕ k is calculated as in Eq. 6. Although it is of course possible to define an indefinite amount of fractions like in (Eq. 6), it appears that there are only nine that are real, positive, and forming a totally-ordered set (Table 1). The last statement implies that ϕ k -ϕ k+1 > 0. Exceptions to this rule begin, of course, when k > 10.

Towards Convergence of ϕ's

As interesting as the set listed on Table 1 might be, it is important to revise if further on there are more positive differences or not, and to look either for a forming pattern or convergence. So, calculating more Lucas sequences, it is obtained (Eq. 7) Thus

k ϕ k 1 0.618034 • • • 2 0.543689 • • • 3 0.51879 • • • 4 0.50866 • • • 5 0.504138 • • • 6 0.502017 • • • 7 0.500994 • • • 8 0.500493 • • • 9 0.500245 • • • Table 1: List of ϕ k , k ∈ {1 • • • 9}, k ∈ +Z. Notice that ϕ 1 is the golden ratio.                                                             k ϕ k 1 0.
                                                            (7)       k ϕ k+1 -ϕ k 1 0.
F n = F n-1 + F n-2
(10) F n-1 = F n-1 + 0 and then in matrix notation

F n F n-1 =   1 1 1 0   • F n-1 F n-2 (11)
Now, the eigenvalues of the matrix in Eq. 11 are

λ 1,1 = 1 2 1 + √ 5 = 1/ϕ (12) and λ 1,2 = 1 2 1 - √ 5 (13)
It is possible to construct matrices for all the Lucas sequences until convergence of the ϕ k . The elements of the general matrix A k for obtaining the rest of the eigenvalues for the corresponding ϕ k , k ≥ 2, are defined as follows:

a 1j = 1, 1 ≤ j ≤ k + 1, 2 ≤ k ≤ 19 (14) a 2,1 = 1 a j+2,j+1 = 1, 1 ≤ j ≤ k -1
It is known from linear algebra [START_REF] Anton | Elementary linear algebra[END_REF] that a n × n matrix will have n eigenvalues, so once the eigenvalues λ k,n are obtained, it is possible to obtain ϕ k,n = 1/λ k,n , just as in Eq. 12.

The ϕ k,n and the Quadratic Family

Once it is obtained the entire set of ϕ k,n , it is possible to plot them in the complex plane as it can be seen in Fig. 1 Intuitively, Fig. 1 seems to have some resemblance to the Mandelbrot set, symbolized as M. Here M is the set of all complex numbers c, for which the sequence z n = z 2 n-1 + c does not diverge to infinity when starting with z 0 = 0 [START_REF] Devaney | Chaos, fractals, and dynamics: computer experiments in mathematics[END_REF][START_REF] Devaney | An introduction to chaotic dynamical systems[END_REF]. The resemblance is both in shape and approximate scale, as can be seen in Fig. [START_REF] Devaney | An introduction to chaotic dynamical systems[END_REF] where the ϕ k,n are shown together with the Mandelbrot set.

Using the Wolfram Mathematica command MandelbrotSetMemberQ, it was tested whether ϕ k,n ∈ M. It turns out that 54 out of the 155 ϕ k,n are in M; this suggests that for each of the characteristic polynomials of the A k matrices, there are some functions z n = z k n-1 + c which have overlapping values with some members of the quadratic family. Indeed, if one now turns its attention to the Julia set J , where the set J of a function f (z) is the closure of the set of all repelling fixed points of f (z) [START_REF] Devaney | An introduction to chaotic dynamical systems[END_REF], or phrased in another way, it is the points in the boundary of those points that do not escape to infinity under iteration [START_REF] Devaney | Chaos, fractals, and dynamics: computer experiments in mathematics[END_REF]. The set of ϕ k,n is now plotted with the Julia set for comparison, as in Fig. 3 Using the Wolfram Mathematica command JuliaSetIterationCount[-1, ϕ k,n ] (for the function f (z) = z 2 + c, c = -1), and with the criterion that membership to J is stablished when the number of iterations is 1000 + 1, it is found out that only ϕ 1,1 = 0.618 • • • is in J , for this f (z). A depiction of this overlap is shown in Fig. 4. The procedure was repeated with JuliaSetIterationCount[z 2 -2, ϕ k,n ] (for the function f (z) = z 2 + c, c = -2), exhibiting that more members of the set of eigenvalues of the generalized Fibonacci matrices from the convergent sequence discussed in the subsection 2.2 belong to this Julia set, and this in turn seems to suggest that every member of that set belongs to at least one Julia set f (z, c), for some c, and some polynomial functions defining the Julia set.

Conclusions

It was shown the existence of a set of golden ratios ϕ k obtained by convergence of Lucas sequences. The Lucas sequences in turn were represented in matrix form to obtain ϕ k,n eigenvalues, where the graphic depiction and numerical evidence seem to suggest that every member of that set belongs to at least one member of the quadratic family, namely, the Julia set.

Figure 1 :

 1 Figure 1: Plot of all ϕ k,n .

Figure 2 :

 2 Figure 2: The complete set of ϕ k,n plotted together with M.

Figure 3 :

 3 Figure 3: The complete set of ϕ k,n plotted together with J .

Figure 4 :

 4 Figure 4: Zoom of J in the region where ϕ 1,1 ∈ J .

Acknowledgement: My deepest gratitude to my personal, inner muse, to whom I owe all the inspiration for this work. My sincere thanks to professors María del Carmen Lozano Arizmendi, Hugo H. Corrales and Oscar Adolfo Sanchez Valenzuela for suggesting extending the search of ϕ k until convergence.


Frederic Mondot
email: frederic.mondot@renault.com

Software Analysis: A point of view of a car manufacturer

Keywords: Static Analysis, software development rules, MISRA

This paper presents a point of view on the way and works that Renault considers as necessary to insure a good level of software quality through the application of solutions concerning static code analysis and intrusive control of the software development by quality requirements and software verification levels to the supplier.

Introduction

1.1 Solving software problems: the context in automotive market Embedded Software is a major actor of the automotive innovation but it is put under the spotlight for its good and its bad sides. Over the last few decades, the growth of automotive services containing software is becoming increasingly important.

Electronic services are increasingly complex, distributed and dependent on other electronic systems. These systems are also highly stressed by their environment (driver, passengers, external environment ...). The software that drives such systems is also constrained, especially in terms of dependability. As explained in a McKinsey report [1], Embeddedsoftware systems control a wide variety of automotive applications and handle a number of fundamentally different challenges […]. Unfortunately, embedded software has, at best, a varied record of quality: newspapers regularly report failures and recalls.

It is difficult for the customer of our vehicle to imagine that embedded electronic systems could fail or endanger him.

The press is full of examples of recall campaigns of vehicles following the discovery of electronic problems. This often leads to a realignment of embedded electronics with a focus on a software correction. Consequences of these software problems and campaigns are numerous:

• Discomfort of the client of a car (Potential failure of the vehicle, non-availability of services, immobilization of the car ...) • Economic aspects (cost of warranty, etc) most often shared between the manufacturer and the OEM.

• "Brand" aspect, in other words bad advertising (much more unfavorable for the car manufacturer than the supplier) For the customer, electronics in the vehicle has to be robust, reliable and free of defects. For this last aspect, how do we get there? How to be sure? Quality and reliability of the system are indirect leverage for customer trust and business improvement.

In this way, it represents a challenge for both car manufacturer and suppliers to address the following issue regarding software development: how deploying software products without defects. To do this, Renault shall be very involved in the development achieved by the supplier. That is why the process described above and implemented by the supplier is controlled, adjusted under a contractual quality plan. In this plan, the supplier agrees to respect among others a number of requirements in order to fulfill the Quality objectives (Requirements adequacy, Reliability, Testability, Traceability, Maintainability ...) The monitoring carried out by Renault throughout the development phase by the quality assurance activities intends to ensure the good organization of the process, the good use of techniques, methods and tools. Among these requirements that the supplier has to respect, we shall quote for example, the respect of the "Guidelines for the use of the C language in critical systems" published by MISRA [2].

2.2 A lever to insure confidence in software Everyone knows the exponential curve of cost of corrections of a bug. It is easy to claim that it is necessary to give the means to detect and to correct bugs as soon as possible but this task shall be accomplished within the constraints of model of development (Quality, Cost and Duration). Software bugs could be design defects (linked to the specification) or production defects (linked to the coding phase).

The classical activity of the V&V phase is test (unit and integration test). Unit test phase, for example, is very often the first activity done by the supplier after the coding phase. Based on the design elements, it is intended to verify that the product obtained at the coding step is consistent with the description given in the software design document. So, it is naturally in this phase where defects could be detected. But considering the flow of development of an automotive electronic application, the final and exhaustive functional content occurs late in the project.

Figure 3: exhaustive representative model come late in the development compared to the SW production and validation

The unit tests are also rather late and are of course costly to implement. They require an execution of the code and a dedicated operating environment. Thus, as the code is often modified to achieve the functional specification, unit test made on a specific software file version have to be redone on the updated software file and that is why suppliers could prefer doing these tests when the code is a little bit more mature.

Is there any activity to perform before unit tests phase? For what purpose?

Developers know that some coding constructions could lead to potential defects if they are misused or not controlled in an adequate way in the software architecture. So, development rules shall allow to impose a kind of watchdog during the production of code.

The check of these rules is not intended to validate the functional requirements of the application, but is intended to verify the proper use of language, the proper structure of the code. This analysis can be done as soon as the code is produced and whatever completeness of its functional content. This so-called static analysis is done without executing the code and does not require a complete operational environment.

Is it a guaranty of absence of defects?

The answer to this question is absolutely not. It is a mean to improve code quality, to detect defects sooner in the process but this remains a complement to other V&V activities established by the supplier and Renault. It is also a way to keep an eye on the evolution of the software development by monitoring for example software quality metrics.

Certification of automotive electronic applications is not yet mandatory in automotive domain but the position of Renault is to develop means to "qualify" the software. By this term "qualification" Renault means to give a level (a quality level or a risk level) for the software project. This level will let Renault for example to ask complementary activities to the suppliers.

That is why Renault wants to be even more intrusive in the coding phase and in the V&V phase.

3.

Detect and correct software defects: the sooner, the merrier

Requirements to suppliers

At the beginning of the project, the supplier receives a documentation of requirements concerning the policy of software quality assurance that Renault wishes to lead. In this documentation are notably included the requirements concerning the objectives and the means linked to the static code analysis as well as those linked to the dynamic code analysis. These requirements specify on the one hand the objectives, that is to say, the details about why Renault want the implementation of these kind of analysis, what are the results that Renault expects ( reports, …) and on the other hand the means and process to realize these analyses.

Objectives:

• Check of development rules For that purpose, Renault bases its thinking on Misra Rules. The compliance of these rules is asked to the supplier. Violation of these rules shall be analyzed and justified or corrected by the supplier. The goal is to avoid systematic coding errors in order to correct them at lower cost. Misra rules also allow structuring the code by avoiding potentially dangerous programming constructions.

• Software metrics Code measurement is needed to monitor the evolution of the coding phase throughout the deliveries. Also, the various collected metrics shall allow to identify some "shaded areas". These areas represent in fact part of code with complex structure, which could be potentially poorly controlled by developers, and then, potentially problematic (coding error, no maintainable code…) for this project or for future project. The identification of these areas shall allow the introduction of additional tests or the introduction of oriented tests at the initiative of the supplier or Renault.

• Detection of runtime errors Most Static Verification tools only provide an analysis of the complexity of the software. They look for constructions, which may be potentially dangerous, but some tools provide deep-level analysis by identifying almost all run-time errors and possible access conflicts on global shared data. These errors are linked to the implementation; it is of interest to check them in a static way. No need to have the whole environment development.

The goal is still here to detect as soon as possible coding errors.

Means:

In the point of view of Renault, it is important to insist on the "automatic" aspect of the analysis. Therefore, a dedicated tool shall perform the analysis.

It is also important to insist on the conditions of performing the analysis for several reasons:

• The configuration options of tools are numerous

• The conformity of the code under analysis in term of execution and structure compared to the mass production code. For example, control flow and data flow shall be the same. • The consideration of the functional information of the data for example through the data dictionary. • The analysis perimeter of the tool. Tools have distinct functionalities and then, shall be used only for their purpose

Renault has developed internal competencies on the use of such static analysis tools. Renault has a good view of how to use them. Global requirements and deep level requirements (for example, best configuration options) have been built concerning the process of analysis and the use of the tools.

Results:

The supplier performs the V&V tests and reports the results in an internal document. It is necessary for Renault to get access to these results and reports. As a consequence, requirements also concern analysis reports. A typical report is required to supply to Renault at each software delivery or each major V&V milestone. Information documented in the report (and then, the requirements supplied by Renault) are various. It concerns configurations option, information about experience of the person in charge of the check, justification and details of warnings or violations identified by tools.

The activity of justification of the non-conformities is important. By justification, Renault wishes not only the supplier position about the potential problem (the answer to the question is there a problem or not) but also elements that let the supplier conclude on the potential problem. Moreover, the fact to ask a written justification and illustration is a good strategy for the soundness of the analysis. Indeed, the level of details asked by Renault for the justification of non-conformity helps the person in charge of the analysis to perform good checks. This justification concerns not only the confirmed problems but also the justification of the warnings not considered as problematic. This shall be done to keep the reasons of these choices (traceability) and capitalize them at each software delivery but also in the case of carry-over on another project (execution conditions may have changed and then effect and root causes of the deviation also).

Tools to support the activities

Tools shall support the achievement of the objectives.

As mentioned in sections above, Renault has developed competencies on tools. It is not the goal in this section to mention name of tools but to give some elements on tool categories.

• Misra Rules Tools in this category shall check the whole set of rules that could automatically be checked.

• Software metrics A lot of metrics are available. We have to take into account on the one hand metrics proposed by tools and on the other hand we have to build specific metrics linked to the objectives. An example of this built metrics could be a metric which measure the evolution of the violation of some Misra rules along the software deliveries or metrics based on the review of the warnings.

• Runtime errors

The number of tools realizing this type of analysis is more limited. Typical errors which could de checked are:

division by zero out of bound array index bad use of pointers non initialized variables shared variables conflict unreachable code -etc… A process shall be defined to correctly use tools and analyze the results. Such a process was built by Renault and suggested to the supplier. The process covers various items:

• the configuration of the tool : best configuration… • the analysis sequence: this covers the analysis by the tool and also the analysis of the results which is mainly manual. Renault proposes good process practices to obtain best defects detection and best results review. • the required report: all information needed by Renault to have a good overview of the performed activity and to have all the elements to evaluate a quality level This process is discussed with the supplier, adapted if necessary, collectively accepted.

Benefits for car manufacturer and supplier

The quality of the analysis by tools is important but the quality of the analysis of the results is also very important.

It is one of the Renault requirements on which it is necessary to insist. Indeed, the justification of the choices which allowed to say or not that it is a defect which can lead to a failure represents the main part of the analysis. It is also capitalized information for future versions or when the code is carried over a new project.

For the supplier, this activity shall demonstrate to the car manufacturer through the use of the mentioned type of tools that the product does not present defects and that it is of a good quality level.

On the other side, the car manufacturer want to be sure that everything has been done to "purify" the application of any anomalies. These opposite points of view associated with this citation of Dijkstra [3] "Program testing can be a very effective way to show the presence of bugs, but is hopelessly inadequate for showing their absence" shows that even for a static analysis, it is difficult to define a stop criterion allowing to give or to reach a quality level at a given moment. Nevertheless, the static analysis activity properly integrated into the software development process and properly supervised by the monitoring of the software development of the supplier shall be able to identify or to guarantee an absence of certain defects types very early in the V&V phase. A single method is not sufficient. It is the combination of the techniques and tools through the three defined objectives that let to reach this criterion. It is of course a complement of other V&V activity (dynamic test…)

For the car manufacturer, the systematic introduction at the supplier of a static analysis activity associated with specific requirements (process of the analysis by the tool, process of the analysis of the results, justification of the non-conformity …) is a mean to reach quickly a good quality level for the project.

The formalization of the results and their provision to the car manufacturer allows to follow the evolution of the code quality over the deliveries and to capitalize on defects found (enrichment of the specification, enrichment of the requirements related to the static analysis activity …) For the supplier, this practice will enable him to capitalize on the problems found by enriching its internal rules of development as well as its development process.

A part of the unit test may be covered by the static analysis of the runtime errors (bound analysis, errororiented test …), so the supplier can orient its test campaign in order to avoid areas already covered by this type of analysis. Also with the detection of the unreachable code, the construction of test cases for dynamic tests is facilitated.

Finally and hopefully of course, the use of these various tools allow before the dynamic test campaign to have a code free from some defects. Some Renault projects are using this process since beginning of 2007. For these projects, there were suppliers who already used this type of tools and also novices suppliers in the use of these tools. For these suppliers, the accompaniment of Renault through the requirements was beneficial.

Results are coming and globally three of them could be pointed out:

• a better relation with supplier concerning V&V activities (objectives, share of experience with process and tools) • a good visibility of the results (raised of defects, justification, action plan, capitalization for future developments) • a fast minimization of defects detected by the mentioned tool types.

Another way of progress has to be considered: a change of mindset. Indeed, the supplier sees this new approach as a sanction and not as a mean of software quality improvement and as a collaboration between OEM and supplier towards the objective of producing software of better quality.

Next steps

An improvement of this process will be conducted based on the first results and on the acquisition of skills at Renault on other tools. A strengthening of requirements is also planned as well as greater transparency and communication with the supplier in order to transform the feeling of sanction into an opportunity of collaboration and success.

Conclusion

As exposed in this paper, confidence in the quality of the software is a great challenge for car manufacturer and supplier. This approach by using static analysis close to the production of the source code and the associated process based on the Renault SQA is interesting to tackle the issue of making better software and in a "win win" approach between the car manufacturer and the supplier. The static analysis is of course not the ultimate answer to the problematic of detection of defects. It remains one of the mean in a global V&V process to reach this objective.

The knowing of the analysis results and the reported evolution over the software deliveries must be able to Renault to identify a quality level or a quality risk of the project.

Deployment of this strategy is still in progress but results are already on the good way and will be strengthened by the coming of new standards in future Renault projects (Autosar, ISO26262…).

[1] McKinsey Wolfgang Huhn and Marcus Schaper, Getting better software into manufactured products, March 2006 [2] MISRA : Guidelines for the Use of the C Language in Critical Systems, October 2004 [3] Dijkstra : Humble Programmer, ACM Turing Lecture, 1972

Glossary

Autosar: Automotive open system architecture ECU:

Electronic Control Unit MISRA:

Motor Industry Software Reliability Association SQA:

Software Quality Assurance V&V:

Verification and Validation

Figure 1 :

 1 Figure 1: A representation of electronics defects and their cost to repair (source McKinsey)

Work share between Renault & suppliers in the software development cycle

	1.2 ECU Development: Renault Business model
	Today Renault model of working on ECU (Electronic
	Control Unit) and embedded software is mainly
	based on sub-contracting. Both are currently
	subcontracted to automotive suppliers.
	The figure below shows a usual V-cycle illustration
	for software product development and present the
	phases of which Renault and sub-contractors are in
	charged of.
	Figure 2: Renault makes totally, partially or sub-contracts
	functional specifications based on customer benefits
	and functionality requirements. Suppliers are in
	charged of the whole software product development
	and testing.
	At the end of this development cycle Renault
	achieves functional and system validation testing on
	the ECU.

This modus operandi between Renault and its suppliers cause many exchanges of information at all levels of development and particularly for the software quality monitoring. In this area, exchanges can take the form of audit, review, test report … 2.

Static Software Analysis: a mean to reach full quality?

	2.1 Software Quality Assurance
	The quality of the software relies heavily on the
	quality of its development. The production of the
	software requires the establishment of methods,
	techniques and tools.
	To control this production, we must implement a
	process model that defines:
	• The development phases: definitions of
	requirements, specifications, planning, design,
	coding, testing activities ...
	• Productions: prototype, documentation ...
	• The criteria for phase change,
	• A framework for project management.
	The Renault development model of an ECU involves
	a software development by one or more suppliers.
	This business model involves a technical fact: from
	Renault's side, software product could appear as a
	black box. That is exactly what Renault wants to
	avoid.


J S Camier

C Aussagues

M Lemerre

V David

A Toolchain For Designing And Implementing Efficient, Flexible And Safety-Critical Applications

Keywords: Safety critical real time systems, toolchain, embedded application design

Safety-critical embedded real-time applications have strong needs for both safety and performance. This paper presents a complete method and associated tools for developing this kind of applications. We have developed a complete safety oriented toolchain which is a correct and determinist implementation of a new concurrent model where applications' behaviour is both predictable and reproducible. The model expresses the behaviour and interactions of time-triggered concurrent tasks. This both simplifies comprehension of the application and is the basis for its determinism. Applications are written using an extension to generic languages, which specifies the real-time behaviour of the tasks. Information such as the task's control graph or buffer sizing is computed automatically; then binary code is outputted using a standard compiler; finally the linking stage creates the memory protection tables. At runtime, safety is ensured by different mechanisms: each task is separated into two memory protection domains: one for its own code, and one for the kernel responsible for communications and temporal controls. A microkernel in another memory protection domain is responsible for scheduling and monitoring the tasks' temporal behaviour. Designing and building a toolchain resulted in a complete, industrial-strength development environment which combines ease of use, safety and high performances.

Introduction

Since 1994, CEA, with EDF and AREVA-NP, have worked out a plan of R&D, which mainly deals with the dependability of complex safety critical real time embedded systems. The agreement between dependability concerns and designing, implementing or executing methods has to be demonstrated, thanks to determinism and predictability of the systems' behaviour. The focus is the use of parallelism techniques in the design and the implementation steps of safety critical systems, while still ensuring strong safety properties, such as deterministic behaviour. The goal is to build safety critical systems where the system behaviour is independent from the asynchrony that is allowed during the execution of an application with several different rhythms. It is a major difficulty to conciliate determinism of a whole safety-critical real-time system and a multitask model in order to remain in conformance with the safety requirements and to allow rigorous and flexible design and development which includes verification and validation. OASIS allows a level of performances and flexibility not reached by synchronous languages where detection and confining mechanisms during execution can not be found, whereas OASIS is structured around this objectives. Our contribution leads to the definition of a method and its toolchain for designing and implementing deterministic, fault-tolerant, safety-critical real-time system architectures on standard hardware. Their behaviour is then unvarying, unique, and independent from the realization on a target computer. Indeed, our aim is to cut down the development, qualification and architecture costs by facilitating the design, implementation, oversizing reduction, testing, validation and qualification of such systems. The OASIS model of multitasking design environment is in fact well suited to implement such deterministic real-time systems on embedded architectures while improving dependability and performance.

Complete safety-oriented design method

New concurrent design model

The use of parallelism techniques in the design and the implementation steps of safety critical systems, while still ensuring strong safety properties, is the main focus of the OASIS approach [START_REF] David | Safety properties ensured by the oasis model for safety critical real time systems[END_REF]. It proposes rules, formal methods and a set of tools for safety critical application engineering, allowing design and parallel programs implementation with fully deterministic and predictable behaviour and thus guaranteeing specified dependability properties. In the OASIS model, an application is viewed as a fixed set of communicating tasks that interact to achieve their goals.

A task is an autonomous entity that can be executed and is composed by a number of elementary activities executed in sequences and that have specified temporal execution windows. Their execution is managed in a time-triggered way. Few assumptions are made about the nature of the tasks: their rhythms can be periodic or not, regular or not. This point is essential: OA-SIS facilitates the design, because it does not induce constraints on the decomposition of an application in tasks. The OASIS framework allows the design of real time multitasking systems which are entirely deterministic through its capability of handling tasks with multiple constraints for their processing. Its implementation is based on a time synchronized parallel running principle. It guarantees responses in specified times using a safety-oriented multitasking execution, and has predictable and reproducible behaviours. The main idea of the OASIS approach is, first of all to develop multitask programs which are sporadic or cyclic, regular or irregular and then to demonstrate that some properties of well functioning that come from the specifications of the system can be proved and are in accordance with the constraints of qualification.

Provable deterministic semantics

Extension to generic languages: As in OSEK [START_REF]Iso-17356 road vehicles -open interface for embedded automotive applications[END_REF], the OASIS approach has its own formal language (Ψ) which allows the developer to express the complete and formal behaviour of an application and where the pure algorithmic parts can still be written in native language. The goal of the Ψ language is to allow a formal description of the OASIS' elements (parallelism, temporal synchronizations, communications) without breaking the algorithm coding rules of the developer. In the Ψ language, there are only declarative specifications of the behaviour of the tasks: the system procedure call principle does not exist. After the code compilation and generation, one function is associated with each real time behavioural element. Their semantic is compiled in the runtime and their sequence is defined in state-transition diagrams that are controlled by the kernel. Problems connected with bad argument values or wrong code sequences of kernel call are avoided by construction. The Ψ compiler makes a complete lexical and grammatical analysis, manages the units by taking care of the source files structures and by controling their coherency. A line numbers management for errors reporting has been implemented, as well as coding recommendations verifications. Time-triggered concurrent tasks: In a time-triggered approach, the system observes its environment and initiates processing operations at recurring, predetermined instants in time [START_REF] Kopetz | The time-triggered approach to realtime system design[END_REF]. In OASIS, these instants can be viewed as points in the globally synchronized time of the time triggered system. As shown in Figure 1, a task is an autonomous execution entity consisting of a varying number of elementary actions (EA).

Figure 1: Each elementary action performed for this task takes place between two temporal synchronization points of the time-triggered system, not necessarily contiguously. Elementary action sequences complies with certain logical conditions.

It is deterministic for both logical and temporal aspects: the real-time system behaviour is always unique and invariant. This property is essential for testability: as soon as a schedulability proof is reached, implementations will have identical results, leading to predictability of the test scenarios and the reproducibility of their results. By construction, OASIS is a complete answer to demonstrate the system timeliness: all timing constraints of all activities are clearly expressed in the design phase. All these constraints are calculated on the same global real-time clock and ensured: no activity can be delayed or omitted, no activity can start before their earliest start date without being detected. A simple time-driven scheduling at run-time perfectly manages the temporal coherence of all these timetriggered activities. Contrary to most of actual systems, there is no asynchrony that could impact these basic and fundamental features of OASIS.

Real-time behaviour specifications: The proof that all activities meet their deadlines is connected with the sizing computer architecture problem which is equivalent to make a scheduling analysis. In the application domain we consider, each activity must have a bounded duration and an upper bound can be exhibited. From a safety point of view, an (non optimal) upper bound is simpler and safer than the better worst case execution time. So we can use the results of the deadline-driven scheduling techniques to schedule and execute these activities on the target computer. These techniques are efficient, rigorous and optimal if the programming model is adequate. An off-line verification of the processor load and the calculation of the maximum load of the dynamic scheduling can be performed for the whole system. The knowledge of the upper bounds is not used to tune the real-time system behaviour but is only used to size the targeted architecture. That's why the behaviour is unvarying regardless of its implementation and why OASIS is a formal approach.

Communication: Communication is strictly managed to keep the determinism communication and therefore independent from the implementation. There are two way for a task to declare and specify its communication means in the OASIS model. On one hand, there is an implicit communication mechanism: temporal variables. Each temporal variable is a real-time data flow: values are stored and updated by the unique writer, the owner task, at a predeterminated rhythm (see Figure 2). Other tasks can view only the past values of these variables. Figure 2: Real-time data flow: assuming that a task has a temporal variable X, regardless of the values between dates t start and t end , if another task observes the value of X at date t 0 , the X value "observed" is always its past value X(t 0 = X(t start ).

On the other hand, there is an explicit message passing mechanism (see Figure 3). In addition to common message attributes, the sender indicates the message type and its visibility instant. It specifies the date, beyond which the message can be consumed by the recipient task. Each task has message storage queues. Messages are checked during compilation and their visibility date is specified by the sender. A recipient task has queues for receiving purposes which can only accommodate messages of the same type and has an associated time limit. To achieve determinism, the sequence of messages sorted by visibility date is made to be total. Figure 3: Real-time messages: if message M is sent by the second task with a visibility date t 1 , then it cannot be consumed before the t end date, since t 1 > t start

The temporal consistency of exchanged data between tasks is ensured by the fact that it takes place at the transition of two consecutive processing of the consumer side. This strict observation principle is mastered: data on which a processing takes place are not sensitive between the beginning date t start and the ending date t end .

Execution control graphs: From the abstract syntactical tree obtained during the first Ψ compilation stage, control graphs of each task are automatically generated. They are built with different types of primary nodes that meet real-time features. Their oriented edges reveal the congruency between themselves and code lines that can be executed. It is important to notice that edges could never be walked over because of the conditional branching logic, but an edge can however include several logical branches. All of the possible temporal paths of a task are in fact embedded in its execution control graph which represents an autonomous and independent element that is animated within a true execution in simulated time without the target machine or used to control the system execution on the target machine. The temporal behaviour analysis of one task can be refined when limited loops including temporal constraints are met or when synchronizations on a specific real-time clock have been declared. A construction based on temporal states congruency with loop analysis can be computed from the control graph that are unfolded on the real time basis: all temporal synchronization points are then obtained. These results are used to validate specified temporal features at design stage and to automatically size the communication buffers.

Determinism: Determinism is one of the basic properties of OASIS. Determinism means that the behaviour is single and unvarying. Each task has a behaviour independent of the target architecture. Due to unvarying behaviour, adding or deleting a task which has no direct interaction with other tasks, does not affect the application behaviour.

Offline development tools

Statically computed runtimes information: To perform a successful appliance of our method and approach in the industry, all necessary support tools have been defined and realized. They deal with the following aspects: design, compilation, code generation, execution, simulation, analyses and safe sizing of the communication buffers. From the Ψ design, the code production chain is entirely automatic, operational and includes the:

• compilation of the tasks and of their associated state-transition diagrams, • the interface of the tasks with the system kernel,

• the calculation of each buffer worst case sizes, • the link edition for each task, between the tasks and with the system layer, • the generation of static memory protection tables to enable the protection of the whole application,

The temporal dependencies are calculated on temporal graphs and the buffer sizing is automatically performed too. OASIS also focused on the tool quality (size of the considered case studies, compilation modularity, documentation and trace generation, error code report in the original source code) and on the portability and perennial principles of the developments.

Distributed model: The OASIS environment is geared by an extension to provide distributed safetycritical real-time systems with the same properties.

The objective is to increase performances and modularity while satisfying compliance to the safety requirements. In order to design a distributed safetycritical system with the OASIS chain of development, the model for single processor has been extended to distributed ones with the two following constraints:

• The distributed system remains in conformance with the OASIS model, in particular with the determinism property, • The underlying hardware architecture (e.g. network topology) must be as transparent as possible for application designer.

For distributed architecture, OASIS focuses on the reuse of pre-developed networking solutions. For example, the time-triggered basement of OASIS at runtime makes easier the management of integrated solutions like time-triggered networks, that are nowadays available. Another solution that proposes OASIS is to reuse the Ethernet hardware layer and to pilot it with a time division multiple access strategy. In this case, OA-SIS sets the global time basis of the system. Hence, all communications are deterministic [START_REF] Chabrol | Deterministic distributed safetycritical real-time systems within the oasis approach[END_REF]. Connected to this work, additional works for automatic and safe mapping of real-time tasks and communications among a distributed architecture have been performed.

Correct implementation

Embedded real-time execution model

Graph-execution control: The OASIS kernel architecture is composed of:

• a generic runtime wrapping that interfaces the tasks and the micro kernel, • a real-time determinism and dependability-oriented micro kernel which implements data exchanges for the communications and a graph-execution control of each task code sequences.

The kernel has been realized to satisfy all the previously stated properties: real time, determinism, genericity and dependability. It implements data exchanges for communications and a graph-execution control of each task code sequencing. The kernel is not a classic real time monitor. It manages real time and processor sharing, verifies online all execution times with a time watchdog and it also controls deadlines. The kernel does not require any internal synchronisation (e.g. no semaphores), nor any atomic section, except the processor single instruction atomicity. Time management is also based on a defensive programming in order to detect incoherencies on the speed of the hardware time flow.

Memory protection:

The kernel which ensures an early fault detection and confinement and the runtime are segmented and put in place according to a patented process [START_REF] David | [END_REF]. The implemented mechanisms ensure that any applicative error, regardless of location, will have a deterministic impact on the system. In opposition to most current systems, the asynchronisms of the execution do not have any impact on the determinism.

The memory is split in segments with necessary and sufficient access rights depending of the execution context. This allows detection and confining of operational anomalies (e.g. referencing fault) between the tasks, between a task and the kernel, inside the kernel and its microkernel. As far as we are aware of works in the safety-critical real time domain, no solution has incorporated such a precise partitioning of memory access rights. With these principles and with a specific organization of the memory segments, we are able to guarantee unvarying execution contexts for elementary activities, even in the presence of undetected anomalies (undetected because they could occur inside the right segment memory). The MMU is statically initialized with constant tables generated at the end of the linking edition. The use of cache memory is managed by these tools.

Optimal online scheduling and sizing

Efficiency of real-time systems can be measured by the size of the hardware needed to perform a task. Namely, if the same functionnality can be accomplished by two different systems on two different hardware, the more performant system is the one that can run on the slower hardware. OASIS has many advantages with regard to performance. Thanks to its simple task model (no mutex or lock, no synchronous communication), all tasks are really independent, their behaviour is deterministic, and studying their behaviour is tractable. Thus at compile-time, all the possible deadline, start times and execution paths of the tasks are extracted from source code, forming possible execution graphs. From these graphs, different kinds of information can be computed.

Computation of all buffers' size: We should point out that in OASIS, all messages are sent asynchronously, meaning that they have to be buffered for the duration between the sending of the message and its reception.

Computing the size of these buffers is a difficult problem in most real-time systems.

In the best cases, a size large enough can be proven, but it is rarely also the necessary size, which leads to buffer oversizing. This is because computing the buffer size is intractable in classical fixed-priority systems and sufficient approximations have to be used instead. If there are many communications in the system, a large amount of memory can be wasted, increasing the cost of the system.

In OASIS, the unfolded graphs, carrying all the temporal informations of the processings in the tasks, can be used to extract such informations in more complex cases. The result is a perfectly sized buffer, whose size is sufficient for holding all messages in every configuration, and for which there is at least one configuration in which the buffer is perfectly full. This allows the system designer to minimize the amount of memory needed.

Computation of the needed processor's speed: The load of the architecture and the processor's speed can also be automatically computed. From the execution graphs of the tasks, we can compute a "synchronous product" that represents in a single graph all possible executions interleaves between the tasks; every path represent the parallel execution of several tasks. When coupled to the quotas of all elementary actions, the synchronous product allows to find out whether the application is schedulable or not. The technique cuts all jobs to be done among several intervals and computes for each possible execution interleave the existing constraints under the form of a set of equalities and inequalities. These constraints are then solved using a numeric linear programming solver such as lpsolve, and give a possible schedule of the system for each possible execution path [START_REF] Aussagu | A method and a technique to model and ensure timeliness in safety critical real-time systems[END_REF]. We then simply schedule the system using a deadline driven algorithm: since this algorithm is optimal [7], i.e. can correctly schedule every schedulable job set, and we proved that the job set is schedulable, all deadlines are guaranteed to be met.Still, we perform online monitoring that all the jobs finish before their deadlines for safety reasons. So as to find out the cause of a deadline miss, we also monitor the fact that each job does not exceed its quota. A slight change of the technique allows not only to perform feasibility analysis, but also the required processor's speed. The idea is to divide all the given quotas by a formal factor k, and find the minimal k such that the system remains schedulable. The found k is the maximum load of the system, a measurement of the required processing power. It is helpful to give an idea of the safety margin, but can also help choosing the processor's speed. The processor is perfectly sized when the load of the system is of 1. Assuming that the quotas are reached, the sizing of the processor is again optimal.

Computation of an optimal multiprocessor schedule:

The previously presented technique of feasibility analysis can be adapted for multiprocessor systems using the scheduling theory developed in [START_REF] Lemerre | Equivalence between schedule representations: theory and applications[END_REF]. But even if this allows to know that the system is schedulable, it does not allow to schedule it directly because the deadline driven algorithm is no longer optimal on multiple processor systems. It is worth noting that few optimal multiprocessor real-time scheduling algorithms are known (the only known are the Pfair algorithms [START_REF] Baruah | Proportionate progress: a notion of fairness in resource allocation[END_REF], and they are limited only to periodic tasks).

In order to get an optimal multiprocessor schedule, the results of the feasibility analysis have to be used directly. This is one focus of our current research. Many problems have to be solved, such has the practical storage of the synchronous product (which consumes a lot of memory) in an embedded system, or ways to find weights such that the fewest possible migrations occur. The theoretical gain of using an optimal scheduling algorithm over a deadline driven or a partitionned solution is of two, meaning that we can use processors that are two times less powerful to schedule the system using the optimal scheduling algorithm.

Efficient implementation

As seen in the previous paragraph, the simple task model of OASIS (no mutex, no locks) allows to perform exact feasibility analysis and to schedule tasks optimally, improving the processor use a lot compared to fixed-priority and lock-based solutions. We can also note that the time-triggered nature of OASIS also occur much fewer preemptions than interrupt-based systems; and these preemptions occur only at known time. This also helps in tightening the computation of quotas [START_REF] Louise | A new paradigm for cache related wcet computation[END_REF].

Scalability: The lock-free solution of OASIS also makes it perfect for symmetric multiprocessing systems. Indeed, we can examine the effect of using locks in a computer system:

• On a uniprocessor system, if a thread tries to acquire a lock when it is already hold, an extra preemption occurs so that the thread holding the lock finishes its computation. • On a multiprocessor system, the lock can be already hold by a thread that is running on another processor. Two solutions arise: either the holding thread is migrated, either the waiting thread must wait for the other processor to run the holding thread and release the lock. Both are real efficiency bottlenecks.

Moreover, locks also are unsecure, since a buggy thread may hold a lock indefinitely, thus blocking all the system. On the contrary, the wait-free nature of OASIS makes it extremely scalable and is very performant on symmetric multiprocessing and distributed systems.

Distributed communication: In order to use temporal variable or message mechanisms, it is necessary to indicate respectively the updating period date or the visibility date. The updating date and the visibility date indicate the instant when the data should be available for consumers. It also represents the last instant for receiving the data. By this way, in the OASIS approach, the communication latencies are never considered as insignificant. These temporal parameters provide a way of integrating temporal constraints and communication latencies due to the network at the design level.

No change of the design model is required. The underlying target hardware architecture is transparent for the application designers. Since TDMA brings a static network scheduling, its behaviour is therefore reproducible in temporal and logical domain. To ensure the timeliness, the network scheduling must be computed in order to set each time slot before the deadline where transmitted data must be available for distant consumers. Network fault tolerance begins from the ability to detect errors coming from the network. The error detection is simple and efficient. Since the network scheduling is static, each unit has a perfect knowledge of the network behaviour. The error detection is therefore based on a qualitative approach where missing or swapping of packets are critical errors. Moreover, network is supervised in order to detect disregarded execution and sizing hypothesis such as the absence of collision or the bounded clock synchronization accuracy.

Clock synchronisation: One of the biggest problems in a multiprocessor system is to maintain clock synchronization between the different processors. As OA-SIS rely on time for all its synchronizations, if different tasks use non-synchronized clocks then a message could not be received by another task on time, thus not respecting the execution model. One way to deal with this problem is to have a maximum synchronization drift δ and to force all deadlines to be reached before the actual deadline minus δ. This is what is done on distributed systems, where drifts cannot be avoided; but this has some impact on performances.

We have thus organized the system so that δ = 0. The solution is conceptually simple: instead of using one clock per processor, only one processor has an interrupt routine that updates a clock, puts its value in shared memory, and awakes the other processors at certain dates. The cache coherency mechanisms impose a unique view of the system's memory, thereby ensuring that δ = 0. Compared to a multiple timer solution (for instance [START_REF] Calandrino | Quantum support for multiprocessor pfair scheduling in linux[END_REF]), our approach is architectureindependent, fault-tolerant, and more efficient.

An application: dependable IA32-based display system

4.1 Overview of the system architecture Requirements: The application taken as a case study aims at displaying user-data on a touch-screen, in a flexible and safe way, using the OASIS framework. The execution architecture is a off the shelf Intel IA-32 based hardware (PC-AT/Pentium M computer). This displaying system must be able:

• To retrieve data transmitted by one or several external I/O units through Ethernet links, • To process these input data,

• To display the elaborated information to users through a graphical interface defined by some external HMI-designers, • And to process user inputs such as set points or other parameters.

The main requirement is to achieve HMI functionalities with high dependability. Real time performances deal with the data storage capacities and rhythms, the response times of the display and the validity of displayed information. Hence, up to few thousands analog or binary values can be recorded each second during 30 minutes or 24 hours. The time between the acquisition of data and its subsequent display on the screen shall not exceed one second and an HMI event must be taken into account in less than 200 milliseconds. All information on a screen must also be time consistent.

Hardware/Software organization: The hardware aris a standard, widespread and portable one. The target is a Pentium M architecture, with DDRAM that could implement hardware error-checkand-correction mechanisms, with static memory, with a graphic processing unit, Ethernet-based communication devices. OASIS generic layer and kernel ensures all system functions, including hardware configuration control. The software is organized in two main layers: an applicative one and a generic one. The OASIS method ensures some important features for the safety: the modularity of the developed software, the temporal and logical determinism of the application execution. The software applicative layer consists of user tasks that manage the application displaying policy (e.g. the data management, some graphical item representations, actions triggered by user inputs). It is related to functional treatments that have to be done to the acquired data before displaying them. It is also compounded of external static tables that describe both the HMI screens and the acquired data disposition inside. The generic software layer implements the hardware management of the display. This layer consists of tasks that manage the main physical devices and the communication interfaces with the applicative layer. As presented in the Figure 4, the software is compounded of the following nine tasks:

• agApl: the applicative task that implements the functional treatments on the acquired data. • agScreen: screen display management, in order to display the current image and its components on the screen, by first preparing the image to be displayed and then transmitting it to the screen. • agTouch: RS232 interface and associated touchscreen pointing device management. • agKbdPs2: PS/2 interface and associated keyboard and backup pointing device management. • agNet: low-level network management and protocol implementation for data exchanges. • agMgt: high-level network management, building the I/O functional dataflow for the application layer. • agMem: static memory management.

• agStatus: maintenance management, including the Ethernet one. On maintenance requests, it transmits a monitoring and error buffer. • agSelfTests: hardware self-tests performing and collecting.

Displaying principles: The GPU is configured in a linear frame buffer mode: the video memory is mapped as a raw set of bytes at a dedicated memory location and displayed as this. The display is managed by only one task, agScreen which builds and sends the whole memory bitmap to the video memory at one time. This guarantees the consistency of the graphic elements that are displayed on screen in one image. HMI definition is based on high-level graphic objects that have static features and dynamic ones. agScreen gets the graphic items description in two locations: one in file(s) that define static parts and the other in the communication interfaces (temporal variables) between agScreen and an applicative task that updates cyclically the values of the dynamic parts. For the preparation of the screen memory bitmap, high-level functions are provided in a dedicated library. These functions take the static and dynamic parts of a high-level item and update in accordance the screen memory bitmap.

Hardware management

The goal is to check that the developed software will run on its actual target hardware and that the so-far achieved configuration of the hardware is in conformity with the specified hardware nominal configuration and settings. In order to reach this objective, the kernel probes the entire PCI buses and compares all the relevant registers of all other devices. This order of hardware checking is strictly followed and any failure is considered and processed as an error. After the start-up phase and the low-level hardware initialization phase, tasks managing specific hardware perform a high-level initialization and checking phase. Moreover, self-tests of any hardware component are performed by the task that manages it. They are performed in order to detect any main hardware failure when the system is operational. They are collected by the agSelfTests task that provides an overall synthesis of the self-test results.

The only component that is tested but for which the results are not taken into account is the Ethernet chipset dedicated to the maintenance. The monitored hardware components are the Ethernet chipset dedicated to the I/O network, the touchscreen pointing device, the keyboard, the backup pointing device, the IDE/ATA static memory device and the ALU&FPU. The ECC-RAM provides a hardware-based permanent detection and correction. An overall status is elaborated from all self-test results and attached with each data going outside the displaying system. Self-test results are displayed in a dedicated self-test page and may be sent on the maintenance network. Any hardware fault detected by the kernel (e.g. execution control graph non conformity) leads to an error management procedure that can be taken into account since design phase.

Efficiency and dependability level

Within the OASIS framework, nine parallel tasks are executed in a PC-AT/Intel IA32 single-processor computer with time scales ranging from the millisecond to few seconds, allowing the full control of a configurable graphical HMI with up to 50 pages, 100 24h-curves, 100 30min-curves and 150 items per graphic object type, data storage on 24h and calculations for millions of measure points, network communication management (around 40000 data per second), application downloading and monitoring. It has been easily demonstrated that in all cases during execution:

• The displaying rate is of 20 images per second (an image is compounded of 1024x768 pixels of 16bpp and entirely built by the generic layer). • Data received through an I/O network are displayed in a consistent way in less than 1 second. • Any input (pressed keys, pressed buttons, pointing device movement) entered by the user is detected and taken into account in less than 200ms. • Any action triggered by the user is processed in less than 1 second.

As the execution of the application is monitored by the OASIS kernel, any violation of the hypotheses that contribute to the demonstration of these temporal properties are detected. The temporal and logical determinism of the safe-by-construction OASIS approach guarantees that the whole application behaviour is reproducible and that it totally fulfills its specifications. Thanks to OASIS, even in case of a failure, the application behaviour is also deterministic, i.e. reproducible.

Conclusion

The OASIS model and tools ensure most important safety properties as the data coherence, an unvarying and deterministic real time behaviour, and in depth fault-detecting and fault-confining hardened mechanisms. The absolute determinism is necessary to the pertinence of the tests, and OASIS meets this goal to make easier test and analysis works to qualify a safetycritical system. This formal approach of real-time design avoids many difficulties and traps encountered with standard multitasking ideas. Hence, it will significantly reduce the cost of safety-critical system. OASIS provides a major technological break that improves both dependability and performances of safety-critical real-time embedded systems. It allows implementing efficient advanced real-time functionalities without any safety loss, compared to traditional programming techniques. It also greatly increases their perenniality. A real-time system designed with OASIS is a system without any unreproducible defects. Moreover, R&D works are in progress to provide additional extensions towards heterogeneous hardware and software architectures and to carry on facilitating the system level design.

Figure 4 :

 4 Figure 4: Software architecture of the dependable IA32-based display system