Valérie-Anne Nicolas

Bertrand Gilles

Laurent Nana

Validation of a Mixed-Signal Board ATPG Method : The TCB case study Technical report -LISYC

. First results confirm the method fitting well with maintenance test, board modeling stage adequacy and test data generation reliability. The essential need for user-defined dedicated test strategies is highlighted in order to ensure meaningful test process and full blackbox test.

Introduction

During maintenance stage, board test is still in need of semi-automatic, robust and complete tools. This is quite different from the design or production stages for which a large panel of methods and tools exists [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF]. This state of things is mainly due to the maintenance context itself, for at least two reasons. First of all, the late location of maintenance stage in product life-cycle. In many cases, this implies reduced knowledge about the board for maintenance people: no designer direct knowledge, partial documentation, confidentiality restrictions. Moreover, in the case of long life systems, even if some test information is available, it may be unusable on aged components whose caracteristics have evolved. The presence of mixed-signal components reinforce the overall complexity of this kind of test. Secondly, decreasing cost of electronic components induce a consumerist inclination: why test, diagnose and repair when replacing is cheaper and quicker? Although replacing faulty boards or entire systems is sensible and interesting for large distribution products, it is less suited for large long-life systems.

Nowadays, due to the wide variety of board maintenance situations encountered, test, diagnosis and repair at maintenance stage are often realized in an empirical way. Clearly, dedicated methods and specialized tools are needed to guide or automate at least a part of the work involved in the maintenance stage.

Our work is in keeping with this maintenance context and focuses more particularly on mixed-signal board test. We have proposed a method to help maintenance testing, providing a functional ATPG for mixed-signal boards [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF][START_REF] Gilles | Timed functional modeling for mixed-signal boards in maintenance testing[END_REF].

The aim of this paper is to sketch a validation protocol for this method and to discuss first results concerning board modeling choices suitability, signal representation pertinency, test strategies quality.

The second section briefly recalls our method and ATPG. The third section introduces the validation protocol. The application of the validation protocol on an example is detailed in the next section. Trends for future work conclude the paper.

The mixed-signal board ATPG method

As mentioned in the previous section, maintenance test lacks of specific methods and tools. We have proposed a method dedicated to maintenance test of mixed-signal boards [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF][START_REF] Gilles | Timed functional modeling for mixed-signal boards in maintenance testing[END_REF]. Its aim is to check a board behavior and to help determine faulty components in case of defective functionality. This method provides some guidelines for modeling and testing mixed-signal boards. It has been implemented in a semi-automatic prototype tool called "Copernicia". This tool also includes an automatic test pattern generator (ATPG). The non-automatic part of the method is the modeling of the board and its components (a library is provided by Copernicia with the most common components). The test of the board and its components is fully automated using some standard test strategies and test models for the different components. One may add some more specific or detailled test strategies from its own. Whereas the definition and use of such strategies are not automated (they have to be carried on by the test engineer), the test data generation process remains automatic.

Our method is intrinsically based on functional modeling and testing. Since they only make use of the external behavior of the components, functional-based models may address a wide spectrum of situations concerning board maintenance test: they may be adapted to the amount of information available (component specification levels), to the nature of the components (digital, mixed-signal, or analog) and to the goal of the test (go-nogo, fine-grain diagnosis oriented testing). Functional testing of component is not used during design or production stages because test software development is costly. It is mainly achieved at the system level in order to test the interactions between components and to check if the global system meets its specification requirements. Thus, there is no predefined functional tests available at the board level.

The method uses an only generic uniform formalism for modeling and testing: finite state machines (FSM). FSM has been chosen because it allows intuitive modeling of component behaviors (it is especially true for digital components), it is well suited to express test strategies and well known to test practitioners [START_REF] Cheng | Automatic Functional Test Generation Using the Extended Finite State Machine Model[END_REF][START_REF] Lee | Principles and Methods of Testing Finite State Machines-A Survey[END_REF]. ATPG is implemented using constraint logic programming (CLP [START_REF] Paoli | Use of Constraint Solving in Order to Generate Test Vectors for Behavioral Validation[END_REF]) with the Eclipse tool [START_REF] Cheadle | Eclipse: An Introduction[END_REF].

One may refer to [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF] to have a look at the way a simple case study is modeled in Copernicia and [START_REF] Gilles | Timed functional modeling for mixed-signal boards in maintenance testing[END_REF][START_REF] Gilles | Timed functional modeling for mixed-signal boards in maintenance testing: A case study[END_REF] to have an idea of the testing process.

The validation protocol

We have proposed a method to help board test in maintenance. Now, we have to determine how this method fits maintenance testing requirements, process and objectives. For this purpose, we outline a protocol to validate the method, helped by a simulation tool.

On the one hand, in applying our method, we model a given board and then generate some test data for it. On the other hand, using a simulation tool, we model the board and next, simulate its behavior on the obtained test data. This process has to be iterated on a selected set of representative examples.

The main objectives are:

• evaluation of the adequacy of our modeling,

• verification that outputs obtained by simulation are consistent with the outputs predicted by the method (reliability of test data generation), • evaluation of our test package (global test method, test levels, test models, test strategies, standard or userdefined facilities...) with respect to maintenance test requirements, process and objectives.

Several tools are available for modeling, simulating and analyzing dynamic systems. Among them, some are well adapted for systems such as boards, including mixed signal ones, and provide graphical editors which can be used to build complex models by interconnecting blocks which are either predefined basic functions (signal generators, filters...) or user defined functions. Without being exhaustive, we can highlight well known commercial tools such as Simulink which is part of the MATLAB Toolset [START_REF]Using Simulink -Model-Based and System-Based Design[END_REF], Sys-temBuild which is part of the MATRIXx Toolset [2], Labview toolkits for simulation [1] and a public domain tool such as Scicos which is part of the Scilab Toolset [START_REF] Nikoukhah | SCICOS A Dynamic System Builder and Simulator[END_REF]. Scicos functionalities are similar to Simulink's. Actually, the Scilab Toolset developed by INRIA in France is known as the public domain version of the MATLAB Toolset. Most of the functionalities offered by Simulink are also available in SystemBuild.

In order to validate our test data generation approach, we have chosen Simulink for the modeling and simulation of boards. This choice is made because we already use it for teaching and already have some experience of it.

The detailed validation protocol is:

• defining a set of representative examples of boards to be tested ; • chosing adapted test strategies for each board ;

• applying the method on each board: i.e. board modeling, test strategies definition, test data (and predicted results) generation ; • board modeling with Simulink ;

• then for each test data: simulating board behavior with the test data as input, and next verifying the consistency of the output obtained with respect to the output predicted by the method and the test objective.

We present in the next section the experiment on the Test Case Board (TCB) introduced in the Section 4 of [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF].

Protocol application on the TCB

The modeling of the Test Case Board (TCB) with our method is studied in the Section 4 of [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF] and recalled in Figure 1. First of all, we present the TCB modeling using Simulink. Next, we expose the chosen test strategies and the test data generated by our ATPG algorithms. Then, we present the simulation with these test data and the results we obtained. A discussion on this experiment concludes the section.

TCB Simulink modeling

The hierachical Simulink modeling of the board is shown in Figures 2 and3. Figure 2 Figure 3 shows the second level of modeling. At this level, the modeling of the TCB as a set of interconnected block diagrams looks like the board level modeling we proposed in [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF] which is shown in Figure 1 (the TCB is delimited by the dashed rectangle). Each block at the board level matches with a Simulink diagram block:

• the filter (F) is modeled by the built-in transfer function block that implements the transfer function of the analog high-pass filter expressed by

H(s) = s s + 1000 . 2π
where 1000 (Hz) is the value of the cutoff frequency of the filter, • the comparator (C) is modeled by a customized block using the S-Functions API [START_REF]Writing S-Functions -Model-Based and System-Based Design[END_REF],

• the digital controller (D) is modeled by the built-in zero-order hold block with a sampling rate of 500 Hz, • the memory (Mem) is modeled by the general expression block expressed by u(1), meaning that the block output is the same as its input (identity function).

The threshold of the the Simulink comparator is an input of the block whereas the threshold of the block C is a parameter of the block description [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF]. In order to make it possible to refine the Simulink model of the comparator, we have added an input for setting the threshold's value rather than using a hard-wired value in the S-function code. So, we do not need to recompile the S-function code of the block each time the value of the threshold changes.

Figure 3. TCB Simulink modeling: Level 2

Comparing this Simulink modeling with the one obtained by our method, we note that both approaches rely on two hierarchical levels of specification. For Simulink modeling, first level is used to model the board inputs and outputs. Second level is the specification of the components of the board and of their in-between links.

In our method, first level defines the board inputs and outputs, but also the way components are linked. Second level is dedicated to the specification of component behavior.

Both approaches are thus quite similar. The only real difference is the internal representation of components: Simulink's ordinary differential equations (with MATLAB ode45 solver) vs our method FSM. This test data set follows directly from the application of test models and strategies described in Section 4.4 of [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF]. This test data set is the same as the one presented in Section 4.5 of [START_REF] Gilles | Modeling and Generation of Test Patterns for Mixed-Signal Boards: Dealing with Basic Signals[END_REF] without the two first test data, which had unfortunately been added.

Testing process

A test data (TD) is made of an input couple and an output singleton. The input couple has the form (S, Clk) and the output singleton has the form (M P ) where S is the analog source, Clk the clock signal and M P the digital measurement point (memory state).

For memory, here are the formal test data:

T D 1 = (In = (sig(sine, V IN , 10 f c , 0), top(z)), Out = ([v, z]))
with z = T e and V IN -δ 1 ≥ S (S f ilter1 test strategy) where δ 1 is a filter tolerance characteristic and S is the threshold of the comparator. The value v is the value of the signal sig(rw, ∆T 1 , T 0 , t 0 ) at time z. Our ATPG algorithms solve and propagate all the induced sets of constraints with the following parameters:

• the comparator threshold is set to 5 V,

• the filter cutoff frequency is set to 1000 Hz,

• the sampling period T e is set to 0.002 s, and compute the effective test data:

T D 1 = (In = (sig(sine, 5.15, 10000, 0), top(0.002)), Out = ([v, 0.002]))

The value v = 0 is the value at time 0.002 of a rectangular wave signal which frequency is the same as the one of the input sine signal.

T D 2 = (In = (sig(sine, 7.21, 1000, 0), top(0.002)), Out = ([v, 0.002]))

The value v = 0 is the value at time 0.002 of a rectangular wave signal which frequency is the same as the one of the input sine signal. The value v = 0 is the value at time 0.002 of the signal sig(rw, 0.001, 0, 0).

T D 5 = (In = (sig(sine, 11.18, 500, 5.82), top(0.002)), Out = ([1, 0.002]))

(1)

Figure 4. Primary input test signal

Let us focus on test data T D 5 generated for the digital part using the test strategy S digital1 . This test data gives the input test stimulus (shown in figure 4) for which the time stamped value of the memory (Out) is equal to 1 when time z is a multiple of the sampling period T e (Clk period). Thus, this test data checks the analog-digital synchronization. Indeed, with test data T D 5 , the primary output P O is always equal to 1. This allows the detection of stuck-at-zero faults, but not stuck-at-one faults.

Let S digital2 be a new test strategy ensuring that the value on the primary output P O is alternately equal to 0 or 1. The new computed value of T D 5 using the test strategy S digital2 is:

T D 5 = (In = (sig(sine, 20.61, 250, 2.9), top(0.002)), Out = ([v, 0.002]))

With the test data T D 5 , the S digital2 test strategy thus detects both stuck-at-zero faults and stuck-at-one faults. The S digital2 test strategy is therefore better than S digital1 . Note that without any extra test strategy, the value of T D 5 would be:

T D 5 = (In = (sig(DC, 3.0, , ), top(0)), Out = ([0, 0]))
where sig(DC, 3.0, , ) represents a DC signal of magnitude 3 V. With test data T D 5 , the primary output P O is always equal to 0 : the analog-digital synchronization is not ensured and stuck-at-zero faults are not detected.

These comments about T D 5 clearly emphasize the importance of the choice of the test strategy in order to have the most meaningful results. Now, let us look at T DS f ilter . It relies on S f ilter1 and S f ilter2 test strategies. Both test strategies ensure that the signal at the output of the filter is higher than the threshold's value of the comparator, to guarantee that the value observed on the primary output P O is alternately equal to 0 or 1. Without using these strategies, the primary output P O may always be equal to 0, and the distinction between weakened or not weakened signal becomes impossible.

If a measurement point at the output of the filter is available, no extra test strategy is needed to test the filter (we perform a kind of unitary test of the filter from the primary inputs of the board). If no intermediate measurement point is available, using S f ilter1 and S f ilter2 test strategies is necessary to test the filter (we perform a black-box test of the filter from primary inputs and outputs of the board).

We showed the advantage of test strategies to produce meaningful results. On the filter test case, we point another role of the test strategies which is the forward propagation of results. Anyway, they are all context dependent strategies.

One may note that no particular test strategy is needed for the comparator. The reason is that the data propagation from the comparator output to primary output P O is straightforward (assuming the memory component is correct).

Finally, using standard component test models and test strategies S f ilter1 , S f ilter2 and S digital2 , our method generate the test data set

T DS = {T D 1 , T D 2 , T D 3 , T D 4 , T D 5 }.
The test data generation stopping point is reached because T DS (like T DS) covers all the test models and associated test strategies of the board's components (this is implemented by full FSM transition coverage). We thus consider that this test data set is sufficient and adequate to test the board in a black-box way. This matches with simulation results. Some of them are presented in the next section.

Simulation

We have simulated the Simulink model with the different test data presented in the previous section, using the MAT-LAB ode45 (Dormand-Prince) solver, starting from time 0 to stop time 0.01s. The results we obtained agree with the test data predicted outputs.

In this section, for the sake of conciseness, we focus on the simulation with test data T D 5 generated for the digital part using the test strategy S digital1 . This test data checks the analog-digital synchronization.

Figure 5 shows the filter output signal. This signal is weakened and has shifted because the frequency of the input test stimulus (500 Hz) is lower than the cutoff frequency of the filter (1000 Hz). The magnitude of the signal is slightly higher than the threshold's value of the comparator (5 V) for times multiple of the sampling rate.

Figure 5. Filter ouput signal

Figure 6 shows the digital comparator output signal. Because the magnitude of the input signal of the comparator is slightly higher than its threshold's value for times multiple of the sampling rate, the output signal is a rectangular wave whose magnitude is 1. The intervals for which the logical value is 1 are centered on the corresponding periods. 2). This result matches the computed primary output in expression (1).

The results we obtained in doing all the simulations agree with the test data and therefore confirm the adequacy and reliabilty of test data (inputs and outputs) generation.

Discussion

The TCB validation experiment stated in 4.2 and 4.3 has confirmed the signal representation choice (sine, rectangular wave and DC signals are common basic signals), the adequacy and reliability of the functional models for basic components, the test models and standard test strategies pertinence in terms of data and expected results for unitary tests, the accuracy of test data generation algorithms.

It has also pointed out the limits of the test models in case of embedded components (black-box testing) and the necessity for extra test strategies definition to ensure propagation of meaningful results to the outputs. The accuracy In our test approach, the overall black-box testing process is the much complete one. The other test facilites we provide may be viewed as restricted applications of this main testing process. For instance, a component unitary test is easier than the overall board test because its environment is restricted to some input/output points, with no other component interaction.

More generally, this particular experiment has shown the interest of a uniform approach to test mixed-signal boards and the generality of our method caracterized by its ability to mix and deal with different test strategies.

Conclusion and future work

We have presented a protocol to validate a mixed-signal board ATPG method and its application on a board case example. Results obtained have been discussed in Section 4.4.

The first results confirm that the method fits well with maintenance test, board modeling stage adequacy and test data generation reliability. The usefulness of proposed automatic standard test facilities is real but appears restricted to some specific tasks of maintenance test (go-nogo test, unitary test). The essential need for user-defined dedicated test strategies is highlighted in order to ensure meaningful test process and full black-box test.

This paper has presented a validation of the method supported only by the example of the TCB. Obviously, a meaningful validation relies on a selected set of several representative examples. Experiments with others board examples are ongoing, and preliminary results are consistent with those stated here.

Figure 1 .

 1 Figure 1. TCB Copernicia modeling

Figure 2 .

 2 Figure 2. TCB Simulink modeling: Top level

  The black-box board test data set generated with our method is T DS = {T D 1 , T D 2 , T D 3 , T D 4 , T D 5 }, made of: T DS f ilter = {T D 1 , T D 2 } using S f ilter1 and S f ilter2 test strategies which are recalled below, T DS comparator = {T D 3 , T D 4 } and T DS digital = {T D 5 } using a test strategy S digital1 that assumes synchronization between analog input sine signal and digital part.

T D 2

 2 = (In = (sig(sine, V IN , f c , 0), top(z)), Out = ([v, z])) with z = T e and √ 2 2 V INδ 3 ≥ S (S f ilter2 test strategy). The value v is the value of the signal sig(rw, ∆T 1 , T 0 , t 0 ) at time z. T D 3 = (In = (sig(sine, Sδ, F IN , φ IN ), top(z)), Out = ([0, z])) with z = T e . The tolerance δ is the tolerance used in the test model of the comparator. T D 4 = (In = (sig(sine, S + δ, F IN , φ IN ), top(z)), Out = ([v, z])) with z = T e . The value v is the value of the signal sig(rw, ∆T 1 , T 0 , t 0 ) at time z. T D 5 = (In = (sig(sine, V IN , 1 Te , φ IN ), top(z)), Out = ([1, z])) with z = k T e and T e = t 0 + ∆T1 2 (S digital1 test strategy).

T D 3 =

 3 (In = (sig(sine, 5.12, 2672.87, 0), top(0.002)), Out = ([0, 0.002])) T D 4 = (In = (sig(sine, 5.52, 2807.23, 0), top(0.002)), Out = ([v, 0.002]))

Figure 6 .

 6 Figure 6. Comparator ouput signal

Figure 7 .

 7 Figure 7. Primary output signal


Mélanie Pailleux

Jérémie Pourchez

Delphine Boudard

Philippe Grosseau

Michèle Cottier

Study on the toxicity of inhaled alumina nanoparticles: impact of physicochemical properties and adsorption artifacts on the measurement of biological responses

Abstract

This work aims at developping a multidisciplinary approach to highlight the correlation between the toxicity of alumina engineered nanoparticles (NP) and their physicochemical characteristics. Accuracy of measurements depends on cell production after contact with particles, but also depends on the ability of biomolecules to get adsorbed on the NP [

I. Introduction

Aluminum hydroxide is a material used in various applications such as abrasive materials, refractories, substrates for electronic circuits... At each step of the manufacturing process (synthesis, collection and purification of the powders), workers could be exposed to fine dust suspended in the atmosphere. Inhalation of some types of particles may cause effects on the health such as reduced lung function, respiratory symptoms and increased risk of tumors. Therefore, it is important to evaluate intrinsic toxicity of fine and ultrafine particles of aluminum hydroxide particles.

II. Materials and methods

I II I. .1 1. . P Ph hy ys si ic co oc ch he em mi ic ca al l c ch ha ar ra ac ct te er ri iz za at ti io on n We work on an aluminium hydroxide powder. The physicochemical characterizations were done by laser granulometry (Malvern Mastersizer 2000), XRD (D5000, Siemens) and TEM (JEOL 2010). The specific surface area of powders was determined by the BET method using * Corresponding author : pourchez@emse.fr Journal of Physics: Conference Series, 2011, 304, 012041, Nanosafe2010: International Conference on Safe Production and Use of Nanomaterials, doi: 10.1088/1742-6596/304/1/012041 2 a nitrogen sorption apparatus (MicroMetrics) and the Photon Correlation Spectroscopy (Zetasizer Nano S, Malvern) was performed in solutions of different pH (pH3.5, pH7 and pH9.4). I II I. . [START_REF] Bruch | Variation of biological responses to different respirable quartz flours determined by a vector model[END_REF]

. T

To ox xi ic ci it ty y a as ss se es ss sm me en nt t To assess the biological activity of aluminum hydroxide powder, cells from the RAW 264.7 macrophage cell line were incubated with aluminum hydroxyde nanoparticles. Three parameters were examined: ¬ The lactate deshydrogenase (LDH) release: LDH is an enzyme found in the cytoplasm of living cells. In case of alteration of the plasma membrane, LDH is released into the environment. ¬ The Tumor Necrosis Factor alpha (TNF-α) production: TNF-α is a cytokine secreted by macrophages. It reflects the activation of macrophage and acute phase of the inflammatory response. ¬ The Reactive Oxygen Species (ROS) production, reflecting the oxidative stress [START_REF] Bruch | Variation of biological responses to different respirable quartz flours determined by a vector model[END_REF][START_REF] De La Harpe | A semi-automated micro-assay for H 2 O 2 release by human blood monocytes and mouse peritoneal macrophages[END_REF].

The interactions can be established between these cells and nanoparticles in specific experimental conditions. This study will highlight the correlation between the level of toxicity induced by nanoparticles and their physicochemical properties. Moreover, biomolecules-nanoparticles interactions were evaluated on a cellular medium measuring both affinity and amount of adsorbed TNF-α on aluminum hydroxyde nanoparticles, at equilibrium state (ELISA kit, R&D Systems ® ).

III. Results and Conclusion

The different physicochemical characterizations show coherent results, the crystallites size is 10nm. Photon correlation spectroscopy shows that the aggregation of particles in water increases with pH. Biological activity of aluminum hydroxide was less important than that of the positive control of toxicity (quartz) but also, and unexpectedly, less important than that of cells alone. To determine if this phenomenon was linked with a cytokine adsorption process, we added 75 pg of TNF-α to aluminum nanoparticles, and after a 24h incubation we found 65 pg of TNF-α in cell culture medium, suggesting a significant adsorption of TNF-α on aluminum hydroxide nanoparticles (13%). In conclusion, cytokine adsorption on nanoparticles could represent an important artifact to take into account for an accurate evaluation of biological responses, especially in order to reliably compare nanoparticles with different physicochemical characteristics.

1,5) , JÉRÉMIE POURCHEZ , DELPHINE BOUDART , PHILIPPE GROSSEAU , MICHÈLE COTTIER (1,2) * (1,3,4) (5) (1,3,4)

	S S S t t t u u u d d d y y y o o o n n n t t t h h h e e e t t t o o o x x x i i i c c c i i i t t t y y y o o o f f f i i i n n n h h h a a a l l l e e e d d d a a a l l l u u u m m m i i i n n n a a a n n n a a a n n n o o o p p p a a a r r r t t t i i i c c c l l l e e e s s s : : : i i i m m m p p p a a a c c c t t t o o o f f f
	p p p h h h y y y s s s i i i c c c o o o c c c h h h e e e m m m i i i c c c a a a l l l p p p r r r o o o p p p e e e r r r t t t i i i e e e s s s a a a n n n d d d a a a d d d s s s o o or r r p p p t t t i i i o o o n n n a a a r r r t t t i i i f f f a a a c c c t t t s s s o o o n n n t t t h h h e e e
	m m m e e e a a a s s s u u u r r r e e e m m m e e e n n n t t t o o o f f f b b b i i i o o o l l l o o o g g g i i i c c c a a a l l l r r r e e e s s s p p p o o o n n n s s s e e e s s s
	MÉLANIE PAILLEUX ((1) LINA, Laboratoire Interdisciplinaire d'étude des Nanoparticules Aérosolisées
	(2) Ecole Nationale Supérieure des Mines de Saint Etienne, Centre CIS ; 158 Cours
	Fauriel -42023 Saint-Étienne Cedex 2, France
	(3) PRES Lyon -Université Jean Monnet, Faculté de Médecine, IFR Inserm 143 -42023
	Saint Etienne Cedex 2 France
	(4) Laboratoire d'Histologie CHU de Saint-Etienne -42055 Saint-Etienne, France
	1

(5)

Ecole Nationale Supérieure des Mines de Saint Etienne, Centre SPIN ; Département PMMC ; LPMG -UMR CNRS 5148, 158 Cours Fauriel -42023 Saint-Étienne Cedex 2, France


Eimear Byrne
email: ebyrne@ucd.ie

Alison Sneyd
email: alison.sneyd@ucdconnect.ie

On the Parameters of Codes with Two Homogeneous Weights

Delsarte showed that for any projective linear code over a finite field GF (p r ) with two nonzero Hamming weights w1 < w2 there exist positive integers u and s such that w1 = p s u and w2 = p s (u + 1). Moreover, he showed that the additive group of such a code has a strongly regular Cayley graph. Here we show that for any proper, regular, projective linear code C over a finite Frobenius ring with two integral nonzero homogeneous weights w1 < w2 there is a positive integer d, a divisor of |C|, and positive integer u such that w1 = du and w2 = d(u+1).

In doing so, we present a new proof that any such code yields a strongly regular graph.

Introduction

The homogeneous weight, introduced for integer residue rings in [START_REF] Constantinescu | A Metric for Codes over Residue Class Rings of Integers[END_REF] and extended for arbitrary finite rings in [START_REF] Greferath | Finite-Ring Combinatorics and MacWilliams Equivalence Theorem[END_REF], has been studied extensively in the context of ring-linear coding. It can be viewed as a generalization of the Hamming weight; in fact it coincides with the Hamming weight when the underlying ring is a finite field and is the Lee weight when defined over Z 4 .

Many of the classical results for codes over finite fields for the Hamming weight have corresponding homogeneous weight versions for codes over finite rings. In particular, in [START_REF] Byrne | Ring Geometries, Two-Weight Codes and Strongly Regular Graphs[END_REF] it was shown that strongly regular graphs can be constructed from codes over finite Frobenius rings with exactly two nonzero homogeneous weights.

In this paper, we examine properties of the parameters of a regular projective two-weight code over a finite Frobenius ring. We obtain the analogue of a result of Delsarte [8, Corollary 2], namely that such a code C must have nonzero homogenous weights of the form w 1 = du and w 2 = d(u + 1) (after scaling by |R × |), where d is a divisor of |C| and u is a positive integer. This emerges by an analysis of the eigenvalues of the Cayley graph Γ of C, which turns out to have exactly 3 distinct eigenvalues and is therefore strongly regular. The integer u mentioned above has the value -ρ -1, where ρ is the least eigenvalue of Γ .

⋆ Work supported by Science Foundation of Ireland grant 08/RFP/MTH1181 2 Preliminaries

Finite Rings and Homogeneous Weights

We recall some properties of finite rings that meet our purposes, many of which are discussed in [START_REF] Honold | A Characterization of Finite Frobenius Rings[END_REF]. For a finite ring R, we denote by R := Hom Z (R, C × ), the group of additive characters of R. R is an R-R bimodule according to the relations r χ(x) = χ(rx), χ r (x) = χ(xr) for all x, r ∈ R, χ ∈ R. A character χ is called left (resp. right) generating if given any φ ∈ R there is some r ∈ R satisfying φ = r χ (resp. φ = χ r ). The next result gives a characterization of finite Frobenius rings.

Theorem 1. Let R be a finite ring. The following are equivalent.

1. R is a Frobenius ring 2. Soc R R is left principal, 3. R (R/Rad R) ≃ Soc R R, 4. R R ≃ R R
Then R R = R χ for some (left) generating character χ. It can be shown that any left generating character is also a right generating character (c.f. [START_REF] Wood | Duality for Modules over Finite Rings and Applications to Coding Theory[END_REF]).

For an arbitrary finite ring, the homogeneous weight is defined as follows [START_REF] Constantinescu | A Metric for Codes over Residue Class Rings of Integers[END_REF][START_REF] Greferath | Finite-Ring Combinatorics and MacWilliams Equivalence Theorem[END_REF]. Example 1. On every finite field GF(q) the Hamming weight is a homogeneous weight of average value γ = q-1 q . Example 2. On the ring Z pq , p, q prime, a homogeneous weight with average value γ = 1 is given by

Definition 1. Let R be a finite ring. A weight w : R -→ Q is (left) homoge- neous, if w(0) =
w : R -→ R, x →                0 if x = 0, p p -1 if x ∈ pZ pq , q q -1 if x ∈ qZ pq , pq -p -q (p -1)(q -1)
otherwise.

In fact the homogeneous weight is unique up to choice of γ on any finite ring. The definition used in [START_REF] Constantinescu | A Metric for Codes over Residue Class Rings of Integers[END_REF][START_REF] Greferath | Finite-Ring Combinatorics and MacWilliams Equivalence Theorem[END_REF] uses the notion of a Möbius function µ on the set of left principal ideals of R, given the partial order induced by set inclusion. Definition 2. Let µ denote the Möbius function on the partially ordered set of left principal ideals of R. For any r ∈ R the homogeneous weight of r is given by

w(r) = γ 1 - µ(0, Rx) |R × x| ,
where γ is a real constant. We say that w is the normalized homogeneous weight for the case γ = 1.

Clearly, w(r

) ∈ Q whenever γ ∈ Q. In particular, if γ = |R × | then w is an integer-valued function, since |R × | = |R × x||Stab R × (x)| for all x ∈ R.
Example 3. On a local Frobenius ring R with q-element residue field, we have µ(0, Rx) = -1 for Rx = Soc R and µ(0, Rx) = 0 for x ∈ R\ Soc R. The homogeneous weight is given by

w : R -→ R, x →    0 if x = 0, q if x ∈ Soc(R), x = 0, q -1 if otherwise,
where we choose γ = q -1.

A description of the homogeneous weight in terms of sums of generating characters is given by the following [START_REF] Honold | A Characterization of Finite Frobenius Rings[END_REF].

Theorem 2. Let R be a finite Frobenius ring with generating character χ. Then the homogeneous weights on R are precisely the functions

w : R -→ R, x → γ 1 - 1 |R × | u∈R × χ(xu)
where γ is a real number.

Codes Over Rings

For the remainder, we let R denote a finite Frobenius ring endowed with a homogeneous weight w. We extend w to a weight function on R n in the obvious way:

w : R n -→ R : w(c 1 , ..., c n ) → n i=1 w(c i ).
We also let C ≤ R R n denote a left linear code. As usual, I and J will denote the real identity matrix and the real all-ones matrix, respectively.

Definition 3. Let C have k × n generator matrix Y = (y 1 |y 2 | . . . |y n ) over R. C is called 1. proper if w(c) > 0 for any non-zero c ∈ C, 1 2. regular if {x • y i : x ∈ R R k } = R for each i ∈ {1, . . . , n}, 3. projective if y i R = y j R
for any pair of distinct coordinates i, j ∈ {1, . . . , n}.

Strongly Regular Graphs

We recall some elementary facts about strongly regular graphs. There are many texts on the subject. The reader is referred to [START_REF] Godsil | Algebraic Combinatorics[END_REF] for further details. Definition 4. A graph G on N vertices is called strongly regular with parameters (N, k, λ, µ) if 1. G is regular of degree k, 2. every pair of adjacent vertices has exactly λ common neighbours, 3. every pair of non-adjacent vertices has exactly µ common neighbours.

It is well-known that a regular connected graph of degree k is strongly regular if it has exactly three distinct eigenvalues. Conversely, if G is strongly regular then it has exactly three eigenvalues k, ρ 1 , ρ 2 from which λ and µ are completely determined:

Lemma 1. Let G be a strongly regular graph with parameters (N, k, λ, µ). Let G have adjacency matrix with eigenvalues ρ 1 , ρ 2 , k. Then

µ = k + ρ 1 ρ 2 and λ = k + ρ 1 + ρ 2 + ρ 1 ρ 2 (1)
It can be deduced from the fact that A has zero trace that if G is non-trivial, unless the ρ i occur with the same multiplicity, they are integers of opposite sign, say, k > ρ 2 > 0 > ρ 1 and further, that ρ 1 < -1.

In [START_REF] Delsarte | Weights of linear codes and strongly regular normed spaces[END_REF] it was shown that every projective code over a finite field with exactly two non-zero Hamming weights (also called a two-weight code) has a strongly regular Cayley graph. This was extended for regular, projective codes over finite Frobenius rings with two homogenous weights [START_REF] Byrne | Ring Geometries, Two-Weight Codes and Strongly Regular Graphs[END_REF].

Given a two-weight code C, with non-zero weights w 1 < w 2 , we denote by Γ (C) the graph whose vertices are the codewords of C and whose edges are pairs of vertices (c, c ′ ) such that w(c -c ′ ) = w 1 . Γ (C) is the Cayley graph of the set of codewords of weight w 1 in C. If C is a two-weight code, we say that C is imprimitive if Γ (C) is trivial. Otherwise we say that C is primitive.

Main Results

We now determine relations between the eigenvalues of Γ (C) and the weights of a two-weight code C.

(u, v)-th entry is D uv = w(u -v).
The following is an extension of [8, Th 1]. Due to space constraints we omit a proof here, but mentions that our approach relies on the character description of the homogeneous weight given in Theorem 2 in the distance matrix D.

D 2 + |C|γ |R × | D = nγ 2 |C| 1 |R × | + n J.
Corollary 1. Let C be a proper regular projective two-weight code with nonzero weights w 1 < w 2 . Then Γ := Γ (C) is strongly regular and the eigenvalues k, ρ 1 , ρ 2 of the adjacency matrix of Γ satisfy

(1) (w 2 -w 1 )k = w 2 (|C| -1) -γn|C| (2) (w 2 -w 1 )ρ 1 = -w 2 (3) (w 2 -w 1 )ρ 2 = -w 2 + γ|C| |R × | Proof: Since C is proper, the adjacency matrix A of Γ satisfies (w 2 -w 1 )A = w 2 (J -I) -D. (2)
A, D, J are real symmetric commuting matrices and can thus be simultaneously diagonalized by an orthogonal matrix. Applying Theorem 3, (1) we observe that 1 is an eigenvector of A with eigenvalue k satisfying ( 1 Then

w 1 = γ|C|(ρ 1 + 1) (ρ 1 -ρ 2 )|R × | and w 2 = γ|C|ρ 1 (ρ 1 -ρ 2 )|R × | . Proof: From Corollary 1, (w 2 -w 1 )(ρ 2 -ρ 1 ) = γ|C| |R × | . Let d = w 2 -w 1
. Now solve for w 1 and w 2 using the equations dρ 1 = -w 2 and d = w 2 -w 1 .

⊓ ⊔ The following holds, with t = -(ρ 1 + 1).

m 1 = |C| -1 -n|R × | and m 2 = n|R × |.

Feasible Parameter Sets

Corollaries 2 and 4 can be used to analyse tables of feasible parameters of strongly regular graphs to see which might arise from two-weight codes over rings (cf. [START_REF] Brouwer | Tables of Parameters of Strongly Regular Graphs[END_REF]). Given a strongly regular graph G on N vertices with eigenvalues k, ρ 1 , ρ 2 , for γ = |R × |, the numbers w 1 = N (ρ1+1) (ρ1-ρ2) and w 2 = N ρ1 (ρ1-ρ2) must be positive integers if G = Γ (C) for a proper, regular projective code C of order N and nonzero weights w 1 and w 2 . Furthermore, the unit group of the alphabet must have order dividing the multiplicity of ρ 2 . For the remainder of this section, a 'two-weight code' will mean a primitive, proper, regular, projective two-weight code.

Existence of Graphs From Codes Over Rings

There are currently 91 feasible parameter sets for strongly regular graphs on at most 225 vertices for which the actual existence of the corresponding graph is not yet known [START_REF] Brouwer | Tables of Parameters of Strongly Regular Graphs[END_REF] (we have not counted graphs complements in this number). Using the integrality conditions on w 1 and w 2 , we calculate that at most 27 of these could arise as Cayley graphs of two-weight codes over finite rings. The regularity condition on a two-weight code C over R means that |R| ≤ |C|, so we need only consider codes over rings of order at most |C|. Checking for the existence of rings R for which there exists a code C < R R n of order N with |R × | dividing m 1 or m 2 allows us to eliminate a further 11 cases (the classification results of [START_REF] Raghavendran | Finite Associative Rings[END_REF] were useful here). We tabulate the remaining 16 possible parameters sets below. Note that if a strongly regular graph G has restricted eigenvalues ρ 1 , ρ 2 with respective multiplicities m 1 and m 2 , then its complement G has restricted eigenvalues ρ 1 , ρ 2 occurring with multiplicities m 2 and m 1 , respectively. Thus in the above table, for G = Γ (C) to exist we require that C be an R-linear code of length n such that |R × |n is equal to either m 1 or m 2 , as complements have been excluded.

|C| w 1 w 2 ρ 1 ρ 2 m 1 m 2 k

The Existence of Two-Weight Codes of Order 100

We claim that there do not exist any two-weight codes of order 100. We first note that no two-weight code of order 100 whose Cayley graph is strongly regular with parameters (100, 33, 14, 9) or (100, 66, 41, 48) exists over any finite Frobenius ring, as the weights required for such a code to exist are not integral. We now consider the existence of two-weight codes of order 100. Let R be a ring of order at most 100. Let M be the set of all multiplicities of positive eigenvalues of feasible strongly regular graphs on 100 vertices. We remove 24 and 75 from this set as by the above note, the corresponding graphs are not the Cayley graphs of two-weight codes. Then M = {18, 22, 27, 33, 36, 44, 45, 54, 55, 63, 66, 72, 77, 81}. If m |R × | is not an integer for any m in M , then no two-weight code of order 100 over R exists. We classify such rings as Type I. If |R × | does divide an m in M , we call R Type II. For many Type II rings, the existence of two-weight codes of order 100 may be eliminated simply by considering the weight composition of codewords of a given length.

Example 4. We consider the existence of two-weight codes over F 25 ⊕ Z 2 , whose group of units has order 24 and divides only m = 72. Then the only two-weight code of order 100 that can exist over F 25 ⊕ Z 2 is one whose Cayley graph is a (100, 72, 50, 56) strongly regular graph, or its complement. If such a code existed, it would have length 3 and non-zero weights w 1 = 70 and w 2 = 80, which is impossible since the non-zero weights of F 25 ⊕ Z 2 are 23, 25 and 48.

Example 5. We consider the existence of two-weight codes over Z 10 . Now |Z × 10 | = 4, which divides m 2 = 36, 44 and 72. We consider the case m 2 = 36 and we will show that no (100, 36, 14, 12) strongly regular graph is the Cayley graph of a two-weight code over Z 10 . Now any (100, 36, 14, 12) strongly regular graph has restricted eigenvalues ρ 1 = 4, ρ 2 = 6 with corresponding multiplicities m 1 = 63, m 2 = 36. If such a graph could be constructed from a two-weight code C over Z 10 , C would necessarily have length n = 9 and non-zero weights w 1 = 30 and w 2 = 40. We now prove that no such C exists. Suppose otherwise, and let G be its generator matrix. We may assume G has two rows, r 1 and r 2 , with |Z 10 r i | = 10. Over Z 2 10 , there are 18 projective, regular points, namely {(0, 1), (1, r), (2, u), (2, 5), (5, 1), (5, 2) : r ∈ Z 10 , u ∈ Z × 10 }. We determine the possible weight compositions of r 1 and r 2 . In Using similar arguments, it can be shown that no primitive two-weight code of order 100 exists. Our results are summarized in the following table.

|R| R Type 100 Z 100 I 100 Z 25 ⊕ F 4 I 100 Z 25 ⊕ Z 2 ⊕ Z 2 I 100 Z 25 ⊕ Z 2 [x]/ x 2 I 100 F 25 ⊕ Z 4 I 100 F 25 ⊕ F 4 II 100 F 25 ⊕ Z 2 ⊕ Z 2 II 100 F 25 ⊕ Z 2 [x]/ x 2 I 100 Z 5 [x]/ x 2 ⊕ F 4 I 100 Z 5 [x]/ x 2 ⊕ Z 2 ⊕ Z 2 I 100 Z 5 [x]/ x 2 ⊕ Z 2 [x]/ x 2 I 100 Z 5 [x]/ x 2 ⊕ Z 4 I 100 Z 5 ⊕ Z 5 ⊕ Z 4 I 100 Z 5 ⊕ Z 5 ⊕ F 4 I 100 Z 5 ⊕ Z 5 ⊕ Z 2 ⊕ Z 2 I 100 Z 5 ⊕ Z 5 ⊕ Z 2 [x]/ x 2 I 50 Z 50 I 50 F 25 ⊕ Z 2 II 50 Z 5 [x]/ x 2 ⊕ Z 2 I 50 Z 5 ⊕ Z 5 ⊕ Z 2 I 20 Z 20 II 20 Z 5 ⊕ F 4 II 20 Z 5 ⊕ Z 2 ⊕ Z 2 II 20 Z 5 ⊕ Z 2 [x]/ x 2 II 10 Z 10 II

Gray Isometries

An immediate consequence of Corollary 3 is given by the following.

Corollary 5. Let R have prime power order p s for some prime p and positive integer s. Let C be a proper, regular, projective two-weight code over R with nonzero weights w 1 < w 2 , where the weight function is computed for γ = |R × |.

Then there exist integers r and t satisfying w 1 = p r t and w 2 = p r (t + 1).

One question that arises from Corollary 5 is whether or not a two-weight code of prime power order yields a graph isomorphic to one arising from a finite field.

Let C 1 , C 2 be a pair of two-weight codes over finite rings R 1 , R 2 respectively, with respect to a pair of (possibly distinct) weight functions w 1 , w 2 . Let Γ i := Γ (C i ) for i = 1, 2. Then clearly Γ 1 and Γ 2 are isomorphic graphs if and only if there is an isometry ι : (C 1 , w 1 ) -→ (C 2 , w 2 ).

We now consider the possibility that some of the known constructions of linear two-weight codes over a finite field are images of linear codes over a finite chain ring under the Gray isometry. A number of authors have looked into extending the standard Gray isometry between (Z 4 , w Lee ) and (Z 2 2 , w Ham ) for the case of a finite chain ring (c.f. [START_REF] Greferath | Gray Isometries for Finite Chain Rings and a Nonlinear Ternary[END_REF][START_REF] Heise | Weighted Modules and Representations of Codes[END_REF][START_REF] Honold | Linearly Representable Codes Over Chain Rings[END_REF][START_REF] Nechaev | Linearly presentable codes[END_REF]). If R is a finite chain ring of length n and residue field GF(q) there is an isometric embedding of R for the homogeneous weight into GF(q) q n-1 for the Hamming weight, in which case the image of R is the generalized Reed-Muller code GRM(1, n -1).

For example, in [2, Prop 6.2] a construction is given for a two-weight code C over a finite chain ring R of length 2 and having residue field GF(q). C has a 2×s(q +1) generator matrix whose s(q +1) columns comprise s distinct elements from each equivalence class of q points in the projective Hjelmslev plane over R, 1 ≤ s ≤ q -1. Then C has q 4 codewords and non-zero homogeneous weights w 1 = q 2 (qs -1) and w 2 = q 3 s = q 2 (qs), for γ = |R × | = q 2 -q. We easily solve for k, ρ 1 , ρ 2 to find k = s(q 3 -q), ρ 1 = -qs and ρ 2 = q 2 -qs, from which we may conclude, using Lemma 1, that Γ (C) is a strongly regular graph with parameters (q 4 , s(q 3 -q), λ = q 2 (s 2 + 1) -3qs, µ = qs(qs -1)).

For the case s = 1, R = Z 4 , Z 9 and GR(4, 2) the corresponding two-weight codes have lengths 3, 4 and 5, sizes 16, 81 and 256 and yield strongly regular graphs with parameters (16, 4, 2, 2), (81, 24, 9, 6) and (256,60,[START_REF] Nechaev | Linearly presentable codes[END_REF][START_REF] Greferath | On Bounds for Codes over Frobenius Rings under Homogeneous Weights[END_REF], respectively. While each such graph has the same parameters as the Cayley graph of a binary [START_REF] Carlet | Z 2 k -Linear Codes[END_REF][START_REF] Byrne | New Bounds for Codes Over Finite Frobenius Rings Designs[END_REF][START_REF] Byrne | Ring Geometries, Two-Weight Codes and Strongly Regular Graphs[END_REF][START_REF] Byrne | New Bounds for Codes Over Finite Frobenius Rings Designs[END_REF] two-weight code, a ternary [START_REF] Greferath | On Bounds for Codes over Frobenius Rings under Homogeneous Weights[END_REF][START_REF] Byrne | New Bounds for Codes Over Finite Frobenius Rings Designs[END_REF][START_REF] Carlet | Z 2 k -Linear Codes[END_REF][START_REF] Godsil | Algebraic Combinatorics[END_REF] two-weight code, and a GF(4)- [START_REF] Nechaev | Linearly presentable codes[END_REF][START_REF] Byrne | New Bounds for Codes Over Finite Frobenius Rings Designs[END_REF][START_REF] Greferath | On Bounds for Codes over Frobenius Rings under Homogeneous Weights[END_REF][START_REF] Honold | A Characterization of Finite Frobenius Rings[END_REF] two-weight code, respectively, we have verified by computer search that no Gray image of any of the 4, 77 or 1023 distinct Z 4 , Z 9 or GR(4, 2) codes constructed as above is Z 2 , Z 9 or GF (4)-linear.

0 and 1 .

 1 If Rx = Ry then w(x) = w(y) for all x, y ∈ R. 2. There exists a real number γ such that y∈Rx w(y) = γ |Rx| for all x ∈ R \ {0}.

Definition 5 .

 5 The distance matrix of C is the |C| × |C| matrix D with rows and columns indexed by the elements of C and whose

Theorem 3 .

 3 Let C be a regular, projective code. Then (1) DJ = γn|C|J and (2)

Corollary 2 .

 2 ), above. Any eigenvector e of A orthogonal to 1 satisfies (w 2 -w 1 )Ae = (w 2 -w 1 )ρe = w 2 (J -I)e -De = -(w 2 + θ)e where ρ, θ are the associated eigenvalues of A and D, respectively. From Theorem 3, (2), we have (D -nγ|C|I)(D)(D + γ|C| |R × | I) = 0, and hence D has exactly two eigenvalues θ 1 = 0 and θ 2 = -γ|C| |R × | corresponding to eigenvectors orthogonal to 1. The result follows.⊓ ⊔ Let C be a proper, regular, projective two-weight code with nonzero weights w 1 < w 2 . Let the adjacency matrix of Γ (C) have eigenvalues ρ 1 < ρ 2 , orthogonal to 1.

Corollary 3 .

 3 Let C be a proper, regular, projective two-weight code with nonzero weights w 1 < w 2 where the weight function is computed for γ = |R × |. Then there exists a positive integer d, a divisor of |C|, and positive integer t such that w 1 = dt and w 2 = d(t + 1). Corollary 4. Let C be a regular, projective two-weight code with nonzero weights w 1 < w 2 where the weight function is computed for γ = |R × |. Let the adjacency matrix of Γ (C) have simple eigenvalue k and restricted eigenvalues ρ 1 < ρ 2 . Then the corresponding multiplicities of m 1 and m 2 of ρ 1 and ρ 2 are given by

u 1 2u 2 2u 3 2u 4 u 5 u 6 u 7 , u i ∈ Z × 10 .1 2u 2 u 3 u 4 u 5 2u 6 u 7 , u i ∈ Z × 10 .

 710710 Z 10 with γ = 4, u ∈ Z × 10 , w(u) = 3, w(2u) = 5 and w(5) = 8. For a given word, let a be the number of coordinates of weight 3, b the number of weight 5 and c the number of weight 8. We solve 3a + 5b + 8c ∈ {30, 40}, where 0 ≤ a ≤ 10, 0 ≤ b ≤ 5, 0 ≤ c ≤ 2 and a + b + c = 8 and arrive at two possible solutions: a = 3, b = 3, c = 2 and a = 5, b = 3, c = 0. There are three possible forms for G. It can be seen by immediate inspection that both rows of G cannot have weight composition a = 3, b = 3, c = 2. Next, we suppose both rows of G have weight composition a = 5, b = 3, c = 0. Then up to monomial equivalence, Now adding the rows of G gives a codeword of weight 24, 29, 34 or 39. The third possibility is that the first row of G has weight composition a = 3, b = 3, c = 2 and the second row a = 5, b = 3, c = 0. Then up to monomial equivalence, Adding the rows of G gives a codeword of weight 29, 34 or 39.

Note that on some finite Frobenius rings w is not positive definite, for example in the ring F2 × F2 we have w(00) = w(11) = 0.


Jalil Boukhobza
email: boukhobza@univ-brest.fr

Pierre Olivier
email: pierre.olivier@etudiant.univ-brest.fr

Stéphane Rubini
email: rubini@univ-brest.fr

A Cache Management Strategy to Replace Wear Leveling Techniques for Embedded Flash Memory

Keywords: component, NAND Flash memory, cache, FTL, performance, simulation, storage, I/O workload, wear levelling I

Prices of NAND flash memories are falling drastically due to market growth and fabrication process mastering while research efforts from a technological point of view in terms of endurance and density are very active. NAND flash memories are becoming the most important storage media in mobile computing and tend to be less confined to this area. The major constraint of such a technology is the limited number of possible erase operations per block which tend to quickly provoke memory wear out. To cope with this issue, state-of-the-art solutions implement wear leveling policies to level the wear out of the memory and so increase its lifetime. These policies are integrated into the Flash Translation Layer (FTL) and greatly contribute in decreasing the write performance. In this paper, we propose to reduce the flash memory wear out problem and improve its performance by absorbing the erase operations throughout a dual cache system replacing FTL wear leveling and garbage collection services. We justify this idea by proposing a first performance evaluation of an exclusively cache based system for embedded flash memories. Unlike wear leveling schemes, the proposed cache solution reduces the total number of erase operations reported on the media by absorbing them in the cache for workloads expressing a minimal global sequential rate.

INTRODUCTION

NAND flash memories are more and more used as main storage systems. We can find them in music players, smart phones, digital cameras, laptop computers, and a huge set of electronic appliances. NAND flash memory is based on semiconductor chips giving them some extremely interesting characteristics. They are small, lightweight, shock resistant, and very power efficient. One of its main constraints is its poor lifetime which is due to the limited number of erase operations one can perform on a given block (see background section). In addition to this limitation, flash memories present poor write performance because writing can be performed only in one direction (from 1 to 0), so a block must be erased before being modified.

The FTL (Flash Translation Layer) is a hardware/software layer implemented inside the flash-based device. One of its main functionalities is the mapping of logical addresses coming from higher levels (applications/operating system) to lower level physical addresses. Throughout this mapping is achieved the wear leveling, which is the widely adopted technique to cope with the limited number of erase operations. Wear leveling consists in spreading the write operations over the whole flash memory area to increase the block average lifetime preventing it from wearing out too quickly. So, in order to modify a given block, it is rewritten to another free one that suffered less erase cycles. The use of such a technique implies to take into account the validity of written data as many versions can be present in different blocks. Garbage collectors are implemented to recover free space when needed.

Wear leveling in FTL relies on an on-flash SRAM-based memory where the logical-to-physical mapping tables are stored. The use of such an SRAM being very expensive for embedded systems, FTL designers tried to severely minimize the size of such metadata. In fact, one have to find a trade-off between increasing the performance of the flash memory by allowing a page mapping algorithm, which consumes a lot of SRAM but reduces the number of erase operations, and reducing the SRAM usage by reducing the metadata and so increasing the granularity of the mapping which increases the number of erase operations. All state of the art solutions are located between those two extremes.

In addition to minimizing the standard deviation of the erasure distribution over the flash media, a good wear leveler should minimize extra erase operations due its own execution. Despite this, a wear leveler cannot lower the total number of erase operations under a certain limit. That is why researchers designed buffering systems on top of FTLs [START_REF] Jo | FAB: Flash-Aware Buffer Management Policy for Portable Media Players[END_REF][START_REF] Kang | Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices[END_REF][START_REF] Kim | BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage[END_REF][START_REF] Wu | An Adaptive Write Buffer Management Scheme for Flash-Based Solid State Drives[END_REF]. They are mainly used to reorganize non sequential request streams which contributes in minimizing the number of erase operations in addition to buffering the data for future use. The main disadvantages of those systems are: 1) the price: too high for many embedded systems like mp3 players, flash memory cards, etc., 2) the complexity: two levels of complexity are cumulated, FTL and cache, and 3) a higher CPU usage.

As stated in [START_REF] Mohan | How I learned to stop worrying and love flash endurance[END_REF], the endurance problem of flash memories has been widely overestimated and actual flash memories, thanks to recovery time, can sustain much more erase operations than expected.

Because of all the reasons stated above, we think that FTL solutions are temporary and that one should begin considering exclusively cache based flash memories mainly for embedded systems.

We propose, in this paper, a solution based on a simple flexible dual cache to replace wear levelers and garbage collectors. This exclusively based cache system is compared to state-of-the-art FTLs to show that we can rely upon a cache system to minimize and wear level the erase operations and improve performances. This cache system performs well for most tested workloads except for extremely random workloads with very small request sizes.

The main research contributions of this study are the following: 1) a novel caching technique to replace the existing wear leveling (and garbage collection) solutions. 2) The implementation of a simulator used to achieve performance evaluation based on FlashSim [6][7] that is built by extending DiskSim 3.0 [START_REF] Ganger | The Disksim Simulation Environment Version 3.0 Reference Manual[END_REF], the most popular storage system simulator. We added a cache level support for FlashSim. 3) The validation with a large number of synthetic workloads based on global sequentiality parameter.

The paper is organized as follows: a description of flash memories is given in the background section and some related works are discussed in the third section. In the forth section, the proposed cache system organization and policies are depicted. The following section gives performance evaluation methodology and discusses the simulation results, and finally we conclude and give some perspectives in the last section.

II. BACKGROUND

Flash memories are nonvolatile EEPROMs. They are of mainly two types: 1) NOR flash and 2) NAND flash, they are named after the logic gates used as the basic structure for their fabrication. NOR flash memories support bytes random access and have a lower density and a higher cost as compared to NAND flash memories. NOR memories are more suitable for storing code [START_REF] Forni | Flash Memory Applications, In Nonvolatile Memory Technologies with emphasis on Flash[END_REF]. NAND flash memories are, by contrast, block addressed, but offer a higher bit density and a lower cost and provide good performance for large read/write operations (as compared to NOR memories). Those properties make them more suitable for storing data [START_REF] Forni | Flash Memory Applications, In Nonvolatile Memory Technologies with emphasis on Flash[END_REF]. The study presented in this paper concerns NAND flash memories.

NAND flash memories can be classified into two categories: 1) Single Level Cell (SLC) and 2) Multi Level Cell (MLC). In SLC flash memories, only one bit can be stored in one cell, while in MLC, two bits or more can be stored. The price to pay when acquiring MLC as compared to SLC technology is quite high. SLC can have up to 10 times higher lifetime and lower access latency [START_REF] Chen | Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives[END_REF].

Flash memory is structured as follows: it is composed of one or more chips; each chip is divided into multiple planes. A plane is composed of a fixed number of blocks, each of them encloses a fixed number of pages that is multiple of 32. Actual versions of flash memory have between 128 and 1024 KB blocks (pages of 2-8KB). A page actually consists of user data space and a small metadata area [START_REF] Gupta | DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings[END_REF] [START_REF] Kang | Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices[END_REF].

Three key operations are possible on flash memories: read, write and erase. Read and write operations are performed on pages, whilst erase operations are performed on blocks. Pages in a given block must be written sequentially. NAND flash does not support in-place data modification. In order to modify a page, it must be erased and rewritten in the same location or completely copied to another page and its corresponding LBA-PBA translation map entry is updated.

One fundamental constraint on flash memories is the limited number of write/erase cycles (from 10 4 for MLC to 10 5 for SLC) [START_REF] Chen | Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives[END_REF]. After the maximum number of erase cycles is reached, a given memory cell can no more retain data. Some spare storage cells exist on the chip to cope with such a wearing out. Due to data locality (temporal and/or spatial in many workloads), some of those memory blocks would be much more used than the others. They then tend to wear out more quickly. This very central problem pushed the researchers' community to seriously consider wear leveling techniques to even out the write operations over the whole memory blocks even though these techniques reduce dramatically the performance.

As mentioned earlier, writing a data requires having a clean page available (free page from a block erased beforehand). If the system has to modify a previously written page, it looks for a clean page and writes the data while invalidating the previously occupied page (by modifying the metadata). The erase operation is done asynchronously. If there are no clean pages, a garbage collector is ran to recycle invalidated pages.

III. RELATED WORK

A. FTL Based Systems

One can distinguish three main FTL schemes, named after the granularity of the logical to physical mapping. 1) Page mapping provides great flexibility, at the cost of a large mapping table . 2) Block mapping increases the mapping granularity to a block level, reducing drastically the size of the mapping table. When updating data in a previously written page, the system must copy the entire block to a new free location, leading to huge performance drops. 3) Hybrid mapping tries to mix both page and block mapping techniques. Flash space is partitioned into data blocks, mapped by blocks and log blocks, mapped by pages. When the number of free log blocks becomes low, the system must merge them to create data blocks. Merge operations are extremely costly. Current FTL systems are derived from those three main schemes.

Demand-based Flash Translation Layer (DFTL) [START_REF] Gupta | DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings[END_REF] is a page mapping-based FTL. Only a part of the mapping table is present in SRAM, most of it residing on the flash media itself. Based on DFTL, Convertible Flash Translation Layer (CFTL) [START_REF] Park | CFTL: A Convertible Flash Translation Layer with Consideration of Data Access Pattern[END_REF] also places the major part of its page mapping table on the flash memory. CFTL separates data into cold and hot data, respectively mapped by block and by pages.

Regarding hybrid-based schemes, Dynamic dAta Clustering (DAC) [START_REF] Chiang | A New FTL-based Flash Memory Management Scheme with Fast Cleaning Mechanism[END_REF] separates the flash space into multiple regions, from the coldest to the hottest data. This helps to avoid situations with blocks having mixed hot and cold data which lead to costly full merges. Fully Associative Sector Translation (FAST) [START_REF] Lee | A Log Bufferbased Flash Translation Layer Using Fully-associative Sector Translation[END_REF] tries to increase the number of non-costly switch merges by partitioning the log blocks into sequentially and randomly written log blocks, sequentially written blocks being good candidates for switch merge operations. Block mapping-based scheme Mitsubishi [START_REF] Chung | A Survey of Flash Translation Layer[END_REF] [15] and M-Systems FMAX algorithm [START_REF] Chung | A Survey of Flash Translation Layer[END_REF] divide flash space into 1) normally mapped blocks in which physical pages offset is always equal to the corresponding logical page offset, and 2) additional blocks written independently of the offset. In order to retrieve data written in additional blocks, the corresponding logical page number is written in the Out-Of-Band area of each physical page.

Actual FTL algorithms try to bypass the limitations of the main scheme they derivate from, by storing the mapping table on the flash media for page mapping based schemes, reducing the number of costly full merge operations for hybrid-based schemes, and delaying the block copy operations on page update for block mapping-based algorithms.

For the sake of this study, we have chosen to compare our system to two efficient FTL schemes that are DFTL (page mapped) and FAST (hybrid).

B. Buffers above FTL Systems

Even though designed FTL techniques are more and more efficient (and complex), performance of write operations are still very poor. Buffering systems have been designed to cope with this issue by reorganizing non-sequential request streams before sending them to the FTL. Those buffers are placed on top of FTLs.

The idea behind Flash Aware Buffer (FAB) [START_REF] Jo | FAB: Flash-Aware Buffer Management Policy for Portable Media Players[END_REF] is to keep a given amount of pages in the buffer and flush pages that belong to fullest block. The Cold and Largest Cluster policy (CLC) [START_REF] Kang | Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices[END_REF] system implements two clusters of pages in the cache, a sizeindependent and a size-dependant one based on LRU. Block Padding Least Recently Used (BPLRU) is a write buffer [START_REF] Kim | BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage[END_REF] that uses three main techniques: block level LRU, page padding and LRU compensation. Block-Page Adaptive Cache (BPAC) [START_REF] Wu | An Adaptive Write Buffer Management Scheme for Flash-Based Solid State Drives[END_REF] partitions the cache into two parts: an LRU page list used to store data with high temporal locality, and a list of blocks divided itself into two data clusters organized by recency and size.

Most of those buffer techniques have been designed to be implemented on SSD caches which implies two major characteristics: 1) they rely on too big size buffers (8 to 128MB) and so are not adequate for some embedded systems, 2) they are implemented on top of FTLs for which they do not know the details. This is an advantage if one wants to use the buffer on an existing system (which is the purpose of the authors), but can be a limitation if one wants to design a well performing system.

IV. C-LASH ARCHITECTURE FOR EMBEDDED STORAGE

In this section we describe C-lash (Cache for fLASH) system architecture and policies. C-lash is much smaller than previously discussed cache systems (512KB for the evaluations listed in this paper).

A. C-lash Architecture

In C-lash, the cache space is partitioned into two spaces, a page space (p-space) and a block space (b-space). P-space consists of a set of pages that may come from different blocks in the flash while b-space is composed of blocks that can be directly mapped (see Fig. 1). C-lash is also hierarchical, it has two levels of eviction policies: one which evicts pages from p-space to b-space (G in Fig. 1), and another level in which blocks from b-space are evicted into the flash media (I in Fig. 1). With this scheme, we insure that the system always flushes blocks rather than pages to the flash memory. P-space and b-space regions always contain respectively either valid or free pages or blocks.

When a read request arrives, data are searched in both spaces. If we get a cache hit, data are read from the cache (B or E in Fig. 1), otherwise, they are read from the flash memory (A in Fig. 1). A read miss does not generate a copy into the cache.

When a write operation is issued, in case of a cache hit, data are overwritten (respectively C or D in Fig. 1) with no impact on the flash media. If data are not in the cache, they can only be written into the p-space (C in Fig. 1). If enough pages are available, we use them to write the data. If not, we choose some pages to flush from the p-space to the b-space (G in Fig. 1) and copy the new data.

B. Cache Policies Algorithms

Two eviction policies are implemented for each of p-space and b-space (respectively G and I in Fig. 1).

1) P-space Eviction Policy

When a write request is issued and the considered page is neither present in the p-space nor in the b-space, a new page must be allocated in the cache p-space. If a free page is available, the new page is written and data in the corresponding location in the flash invalidated. If no free space is available, the system chooses a set of pages to evict into the b-space (not into the flash media). Pages to evict are those forming the largest set from the same block. Once this set found, we have two possibilities:

1. A free block is available in the b-space and so victim pages are copied in it.

Figure 1. Structure of the C-lash system.

2. No free block is available and then, the set of victim pages is compared to the number of valid pages contained in each block of the b-space area:

a. If there exists a block containing less valid pages than the victim ones, a switch operation is performed (F and G in Fig. 1): pages in the victim block are moved in the pspace while the subset of victim pages is moved in the freed block. This induces no impact on the flash memory.

b. If all blocks in the b-space contain more valid pages than the subset of victim pages: the b-space eviction policy is executed to flush a block into the flash media.

In the upper illustration of Fig. 2, we describe an example of a p-space eviction; the chosen pages are those belonging to block B21 containing the biggest number of pages. One block in the b-space contains two valid pages which is less than the 3 pages to evict. Thus, C-lash switches between the block B4 and the three pages subset. The system, therefore, frees one page without flushing data into the flash.

2) B-space Eviction Policy

An LRU algorithm is used for this eviction to take into consideration, in the b-space, the temporal locality exhibited by many workloads. When a block eviction is performed, the whole corresponding block in the flash memory is erased before being replaced by the one in the cache.

In case the flash memory still contains some valid pages of the block to evict from the cache, a merge operation (J in Fig. 1) is to be performed. This merge operation consists in reading the still valid pages in the flash memory before flushing the whole block from the cache. The merge can be done either during a p-space eviction, we call it early merge, or just before flushing the block on the flash media, we call it late merge. Early merge is more advantageous if the workload is read intensive and shows temporal and/or spatial locality (make benefit from the cached data). If the workload is writeintensive, we would use the late merge. By delaying the merge operation we insure two main optimizations: 1) we read a minimum number of pages since between the moment the pages are evicted into the b-space and the moment they will be evicted into the flash, many pages can be written and so invalidated from the flash. 2) Since it is possible for a block in b-space to be moved to p-space during a p-space pages eviction (a switch), it may not be worth doing the merge operation too early. This can cause extra read operations. We restrict the scope of the presented study to the use of a late merge scheme.

An example of block eviction is shown in Fig. 2. In the lower illustration, we describe a p-space eviction leading to a b-space flush to the flash media. In the p-space eviction phase, two pages of the B21 block are chosen to be evicted. The blocks in the b-space contain more valid pages than the pages amount to be evicted from the p-space. So, the system needs to evict a block into the flash beforehand. After that, the system copies both pages of the B21 into the freed block. In this specific example, no merge operation occurs because the flushed block is full of valid pages.

V. PERFORMANCE EVALUATION

In this part, we compare the C-lash system and three efficient state-of-the-art FTLs: DFTL, FAST and the idealized page mapping algorithm used as a baseline. The purpose of the performance evaluation part is to study if caching techniques can replace actual efficient FTL schemes for embedded storage.

A. Simulation Framework and Methodology

FlashSim is a simulator based on Disksim [START_REF] Ganger | The Disksim Simulation Environment Version 3.0 Reference Manual[END_REF] which is the most popular disk drive storage system simulator in both academia and industry. Disksim is an event driven simulator that has been validated with an exhaustive set of disk models. It simulates the whole storage system going from the device driver until the detailed disk movement, integrating many controller strategies, queues, caches, bus systems, and detailed disk descriptions. Disksim also integrates a very detailed synthetic workload generator which is used in part of our experimentations. Disksim does not natively include flash memory support.

FlashSim integrates some modules that are specific to the flash memory subsystem simulation. In addition to the components modeled by Disksim, it is able to simulate the basic flash device infrastructure to implement specific operations: read, write, erase, etc. Logical to physical address translation mechanisms are also implemented with garbage collection policies. FlashSim implements many FTL schemes: the FAST, DFTL schemes and an idealized page based FTL.

We have modified and increased the functionality of FlashSim to allow the simulation of a dual cache subsystem placed on the top of the flash media. The used cache is configurable as many cache policies can be simulated in the bspace (FIFO, LRU, and LFU). Only the study based on LRU is shown in this paper.

B. Storage System and Performance Metrics

We rely on three main performance metrics: the average request response time, the number of performed erase operations and weighted standard deviation of the erase operations distribution to express the quality of wear leveling. In our study, the response time is captured from the I/O driver point of view, including all intermediate delays: caches, controllers, I/O queues, etc. We tried to minimize the intermediate elements' impact to focus on the flash memory subsystem behavior. The second metric we capture is the number of performed erase operations. It indicates the wear out of the memory.

We simulated a NAND flash memory with a 2KB page size and a 128KB block size. The three operations have the following delays: 130.9µs for a page read: 405.9µs for a page write, and 2ms for a block erase: [START_REF] Micron | Small Block vs. Large Block NAND Flash Devices[END_REF]. The chosen C-lash configuration has 2 blocks (128KB each) in the b-space and 128 pages in the p-space (a total size of 512KB). The mapping table used with C-lash is extremely small (much less than 1KB) as compared to the cache size. All the performed simulations begun with the same initial state, the flash media was supposed to be completely dirty. Each new write in a given block generated an erase operation.

C. Simulated Workloads

The performed tests are those described in Table 1. We mainly vary the global sequentiality of the workload by tuning three parameters: sequentiality (strictly contiguous requests), spatial locality (interleaved contiguous requests [START_REF] Ganger | The Disksim Simulation Environment Version 3.0 Reference Manual[END_REF]) and request size.

We also varied the number of requested data which gives an idea on the size of used address space and so the free area of the flash. This last parameter is important because for some FTL schemes, the more free space is available, the better are the performances. Nevertheless, for embedded systems, it is more realistic to consider that the flash memory space has been optimized and then, there is not much free space available.

D. Results & Discussion

In this section, we describe the results obtained when comparing our cache for flash solution with the following FTLs: FAST, DFTL and an idealized page mapping FTL. As stated in the background section, the pure page mapping FTL is very RAM consuming and is not really usable, but it gives the best FTL performance. As in [START_REF] Gupta | DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings[END_REF], we use it as a baseline in our study.

1) Sequentiality:

As we can see in Fig. 3, C-lash performs better than DFTL, in terms of response time, if the sequentiality rate is above 40 %. It always performs better than FAST.

It achieves less erase operations if the sequentiality rate is above 50% and always outperforms FAST.

Thanks to the dual cache eviction properties of C-lash which help absorbing the erase operations, C-lash always perform a better wear leveling than both FAST and DFTL.

The more the sequentiality rate is high, the more C-lash approaches the ideal page mapping FTL performance for the three performance metrics.

2) Spatial Locality. We can draw the same conclusions concerning the spatial locality as for the sequentiality. In terms of response time, C-lash always acheives better performance than FAST, it performs better than DFTL if spatial locality is above 10%, and performs even better than the page mapping FTL if spatial locality is greater than 85%.

Concerning the number of erasures, C-lash takes advantage of its buffering mechanism to reveal sequentiality and so performs better than DFTL for more than 20% spatial locality, and better than page map FTL for more than 85% spatial locality.

Spatial locality defines requested data that are neighbors but not strictly contiguous. Two requests, R1 and R2, are supposed to be neighbors if the distance between the start address of R1 and the start address of R2 is under a given threshold. We defined, for the sake of these tests, the threshold to be less than two pages (we used a normal distribution). That is the reason why for 100% spatial locality C-lash gives far better performance than other FTLs, it is because C-lash takes benefit of both spatial and temporal locality (through the Disksim spatial locality parameter, we can also simulate temporal locality if the distance is nil).

We can observe that the weighted standard deviation increases for 100% spatial locality. For the three FTLs, this is mainly due to the very high temporal locality making the same data blocks to be very frequently modified. For the case of C-lash, the number of erase operations is too small (write/modify absorbed by the cache) to consider the case of 100% spatial locality. In fact, we have less than 10 erase operations. This case is not representative of real workloads.

3) Request Size: These tests were performed with 0% sequentiality and 20% spatial locality. We see that for requests sizes greater than 6 pages (of 2KB), C-lash mean response time is better than DFTL mean response time. C-lash even performs better than the page mapping FTL for request sizes greater than 16 pages.

We can observe the same behavior for the number of erasures.

We can also notice that the slope of both response times and number of erasures curves for the three FTLs is steeper (logarithmic scale in the figure) than the one of C-lash. In fact, C-lash takes more benefit from the increasing request sizes. The more the request size is important, the less we have to do costly merge operations.

In fact, the request size is just another facet of sequentiality. The bigger the request size is, the more we access to contiguous pages into a given block of the flash memory, and so better is the throughput.

4) Request number:

For this study, we fixed the request size to 6 pages. As we can see in Fig 4 ., we have varied the number of requests in two modes: a random workload and a sequential one.

Generally, we can observe that C-lash performance is independent from the number of issued requests. In fact, this parameter has no impact on its performance in terms of response time/throughput. FTLs take more benefit from the available free space in the flash media to delay erase operations. For DFTL and page mapping FTLs, the more requests we have, the worse is the performance. For random workloads, C-lash outperforms DFTL when more than 60000 requests are issued, which approximately represents 700MB of data (from 1GB space). For sequential accesses, C-lash outperforms DFTL earlier: when there is more than 20000 requests issued, which represents 230MB of data. The same conclusions can be drawn for the number of erasures: the more I/O requests we issue, the better is the performance of C-lash as compared to other FTLs. Wear leveling performed by C-lash is always better than DFTL and FAST for the tested workloads except for extremely small number of requests, which is not realistic.

In fact, the number of requests gives us an idea of the total congestion of the flash memory. Performance of C-lash is independent from this parameter while the performances of the different FTLs highly depend on the available free space on the flash media to perform wear leveling. Most embedded systems do not oversize their secondary storage for cost reasons. That is why we think that one does not have to count on the amount of free space available to better absorb erasures.

VI. LIMITATIONS OF C-LASH

• C-lash system performs poorly for very random workloads with small request sizes but still performance drop is not dramatic and we can notice that many workloads are sequential for an important number of embedded systems (mp3 and mp4 players, cameras, etc).

•

In case of a power failure, data in the cache can be lost. This is a very important problem especially for embedded systems; a possible solution consists in adding a small battery [START_REF] Kim | BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage[END_REF] allowing to flush all the valid pages of the cache in the flash media. In C-lash system, we thought about this problem and we implemented the LRU algorithm on the b-space and rather than on the p-space which would have provoked more flush operations on the media. This ensures a more regular data flush operations, and so less data loss, sometimes at the expense of performance (increase of response time).

•

For some FTLs like DFTL, the more free space is available, the better are performances. C-lash system performance can lag behind even when sequential rate is somewhat high if flash memory is supposed to be nearly free. This case did not seem realistic to us, that is why performed tests does not consider this case even though the request number could have been increased for sequential rate tests.

VII. CONCLUSION

We think that the FTL must be considered as a temporary solution, as flash-based embedded storage systems could migrate in a near future toward exclusively cache-based solution. This migration will unload the flash subsystem from more and more complex wear leveling and garbage collection schemes, and so reducing FTL overhead and improving the overall storage system performance.

In this paper, we presented C-lash, an exclusively cachebased solution that outperforms state-of-the-art FTL schemes performance under workloads showing a minimum global sequentiality. As stated in this paper, sequentiality is characterized by three parameters: the sequentiality rate for strictly contiguous requests, the spatial locality for neighbor /local requests and the request size.

The performance evaluation of this study also showed that C-lash performs a better wear leveling than the tested FTL solutions (DFTL and FAST) by showing a less important weighted standard deviation. Good wear leveling performances is achieved thanks to the LRU scheme implemented at the bspace level which insures the cache to absorb erasures caused by temporal locality exhibited by many workloads.

While C-lash architecture shows good performances with embedded constraints (size, congestion, complexity) with a large set of workloads, it is not completely adequate for large scale storage systems like SSDs. As an extension perspective, we are studying a composite structure including a FTL and a collaborative cache based on C-lash. The FTL, in this case, is only used to deal with random workloads. Indeed, while FTL systems can be replaced by caching mechanisms for embedded systems, we think that they are still useful to manage random workloads in mass storage systems in collaboration of well performing caching mechanism.

The Disksim simulator including the C-lash support will soon be available online with the bunch of performed tests.

Figure 2 .

 2 Figure 2. Two examples describing different scenarios of the eviction policy for p-space and b-space.

Figure 3 .

 3 Figure 3. Performance evaluation for C-lash according to sequential rate, spatial locality and request size.

Figure 4 .

 4 Figure 4. Performance evaluation for C-lash according to the number of issued I/O requests.

Table 1 .

 1 Tested workloads characteristics on 1GB I/O space (default values are underlined unless otherwise specified).

	Seq. rate	Spatial locality	Mean Req. Size
	0100% (steps	0100% (steps of	1, 2, 4, 8, 16 , 32, 64,
	of 5%)	10%)	128 pages
	Request number	Write rate	Inter arrival times
	60000	80%	exp (0, 200ms)


Valerie-Anne Nicolas

Bertrand Gilles

Laurent Lemarchand

Lionel Marcé

Bruno Castel
email: bruno.castel@isismpp.fr

A Maintenance-Oriented Board Testing Approach

Keywords: Maintenance testing, mixed-signal board testing, modelling, automatic test pattern generation, diagnosis

We present an ongoing work in the domain of mixed-signal board maintenance testing, supported by an industrial case study. We propose a method providing a partial automation and a help for the board maintenance testing and diagnosis stages. It is validated by the implementation of a prototype tool.

MOTIVATION

The overall process of mixed-signal board testing needs to be mastered more efficiently. A large amount of work has already been done concerning testing during conception phases (design for testability) and production. The main part of these works deals with digital boards, some others with analogue boards, and quite a few with mixedsignal boards [START_REF] Michael | Essentials of Electronic Testing for Digital, Memory and Mixed-signal VLSI[END_REF][START_REF] Mark | Roberts "An Introduction to Mixed-Signal IC Test and Measurement[END_REF]. As a result, tools exist for digital boards testing, analogue boards testing, or some specific electronic components testing. One may notice that, surprisingly, not much interest has been thrown into testing during the maintenance stage. Indeed, the maintenance process has its own specificities and testing problematic, different from these of conception or production. Our work is related to this aspect and concerns more particularly the maintenance testing of mixedsignal boards.

First, we explain the specificity of maintenance testing. Then, we sketch the main ideas of our method in this context. Next, some more details on the method and its application via a prototype for mixed-signal boards testing are given. Results on an industrial case study are then presented. A discussion on future work ends the paper.

MAINTENANCE CONTEXT

The maintenance stage is one of the step constituting the life cycle of a manufactured product, which begins after the development/production cycle, and thus does not belong to it. This cut is not artificial and explains why methods conceived for the development stage are not well suited to maintenance. For example, when a failure occurs in a product in use for several years, it is often long and difficult to repair it. Although it is always possible to throw away a faulty component/board and just replace it by a new good one in the case of cheap large series, there are still some more complex, particular technology, valuable components/boards that really need to be repaired. Actually, in most cases, specifications and test data for the product are missing.

It is also rare that the development/production team for this product is still there to help. The one in charge of the diagnosis and repair has then to face a complex problem, often in an empirical way, with no tool available to guide or automate at least a part of his work.

In maintenance, one may distinguish preventive maintenance from corrective maintenance. Corrective maintenance is, as in the above example, to be able to deal with failures when they occur, sometimes very quickly. Preventive maintenance consists in checking periodically the correct behaviour of components, and may seem more time-consuming than corrective maintenance. However, by anticipating incorrect behaviours, it allows to guarantee a higher level of confidence in the product and thus a lower need for corrective maintenance.

As far as testing is concerned, corrective maintenance may be viewed as a local approach whereas preventive maintenance is more global. In the first case, tester is interested in one behaviour (to reproduce the target failure), and in the second case, he has to check the set of all behaviours of the board. Independently of their nature, these two kinds of maintenance are in great need of generic testing methods and tools.

The method we introduce next was first designed for corrective maintenance needs, and offers a well-adapted precision level according to this aim. In adds, it may also constitute a help for preventive maintenance.

MAIN IDEAS

Our final goal is to propose a method, supported by a (semi-)automatic tool, providing a help to the board maintenance testing and diagnosis stages. We thus have to formalise the testing and diagnosis data and processes, taking into account the industrial context and practices. Two main aspects are to be considered. First, mixed-signal boards testing practitioners have some know-how related to their experience and skills in the testing process. We think that this knowledge has to be included in the tool. Second, the tool must match the background of testing practitioners in order to be really useful and used. This implies formalisms which are intuitive or well-known to testing engineers. Because of the lack of tools dealing with mixed-signal components, we pay special attention to the modelling and testing of mixedsignal boards.

METHOD AND PROTOTYPE

We have implemented the ideas illustrated on Figure 1 in a prototype tool. This prototype provides a Graphical User Interface (GUI) allowing high level topological description of a mixed-signal board. In addition, the GUI includes some facilities for the choice of a testing strategy, for the description of the board-ATE connection and for the description of data (signals) flow.

A mixed-signal board is modelled as a set of connected functional blocks (each block identifies a function that can either be digital, analogue or mixed-signal). A functional block expresses a function, and does not need to correspond exactly to one of the physical components of the board. Indeed, most of the time it involves a set of such physical components. The description of the board is thus made at two levels: the board level and the block level as illustrated by Figure 3.

The prototype proposes different ways for defining functional blocks. The first one is dedicated to digital functions, the second to analogue or mixedsignal functions, and the third to black box functions. To define a digital function, the user describes the behaviour of the block using a finite state machine (FSM) formalism. In the second case, the user selects a function in a library of analogue and mixed-signal common components. Due to the specificity of maintenance testing, the prototype also allows black box functions. This kind of definition has to be used when absolutely no information on the board behaviour is available. In practice, it is therefore possible to learn from a known good board a test data set characterising the board. This description is used in a black box definition. Even though using this description reduces the power of the method at the board level, it is some time mandatory to use it. To generate more accurate test data than that obtained just from a board behaviour specification, we use testing strategies in add of the functional description of the board. A testing strategy expresses behaviours or faults that have to be specifically targeted by the generated test data set.

The prototype relies on some basic predefined testing strategies (this usefully benefits from crossfertilisation with testing practitioners), but it also allows to describe and use its own specific testing strategy.

From an internal point of view, the different kinds of blocks (digital, analogue or mixed-signal) are treated homogeneously. Most of the prototype is written in C++, excepted the part concerning testing strategies that is implemented using constraint logic programming, with the ECL i PS e solver [START_REF] Cheadle | Eclipse: An introduction[END_REF].

The prototype has been validated on two first industrial case studies: the "Tachy board" [START_REF] Gilles | Towards a New Modelling of Mixed Signal Boards For Maintenance Testing[END_REF] and the "Filter Command Board", which are mixedsignal boards. We detail the application of the method on the "Filter Command Board" in the next section.

CASE STUDY

We first present the board involved in the case study. Then, we give the test data set obtained applying our method. More details on this case study modelling and testing are presented in [START_REF] Gilles | A Maintenance-Oriented Board Testing Approach[END_REF].

Board description

The "Filter Command Board" (FCB) is a mixedsignal board (depicted in Figure 4) and is part of a telecommunication system. We describe shortly the inputs/outputs and the functionality of this board.

FCB has the following inputs/outputs signals:

• one serial digital input (SDI),

• one clock input (CK),

• one copy command (Copy),

• one transfer command (E/D),

• one serial digital output (SDO)

• eight digital outputs (DO),

• sixteen analogue outputs (AO1 and AO2).

Figure 1 and

 1 Figure 1 and Figure 2 sketch our complete method process flow.

Figure 3 :

 3 Figure 3: The architecture of the prototype

Figure 4 :

 4 Figure 4: The Filter Command board

The board testing process flow

  The test program is the test data set instrumented with ATE primitives and an oracle. The oracle compares the real outputs of the test with the expected ones, and is thus able to decide and list which tests fail.Figure2presents how to obtain a test report by running the test program on the maybe faulty board, using an ATE. The first information in the test report is the verdict: the board passed the tests or not. If not, for each failed test, the test report indicates the real and expected results, and the possibly faulty functional blocks. This ends the testing stage and is the departure point of the diagnosis stage. Depending on the required grain of diagnosis, one can stop there and just replace by good ones the components corresponding to faulty blocks. For more precise diagnosis, the method provides some functions that test more specifically the internal behaviour of a functional block (branch, state and path testing and coverage in an FSM context).

	Test Data Set /
	Test Program
	Automatic Test Pattern Generator (ATPG) Figure 1: Test data set generation process flow Testing Strategies Board Description Test Data Set / Test Program Digital Functions (FSM) Analogue and Mixed-Signal Parametric Functions Black Box Defined Functions Figure 1 shows how to generate a test data set for a board given some testing strategies and a description of the (correct) board. This test data set may then be automatically translated into a test program expressed in an Automatic Test Equipment (ATE) language. Automatic Test Equipment (ATE) Tested Board (DUT) Figure 2:	Test Report

ACKNOWLEDGMENTS

We wish to thank Michel Le Goff from ISIS-MPP for his helpful comments on industrial board maintenance testing practices.

FCB digital part is made of:

• three 8-stage shift registers serially loaded into SDI on the rising edge strobe, • three 8-bit storage registers parallel loaded from shift registers on the rising edge of the Copy signal, • three 3-state buffers enabling /disabling digital output data with E/D signal.

FCB mixed-signal part is made of two commutation amplifiers CA1 and CA2. Each amplifier has height digital inputs and height analogue outputs. The commutation table for each input/output is given in Table 1.

Table 1 : The commutation table

The main function of the FCB is to command weight filters connected to the commutation amplifiers outputs A01 and A02. Digital outputs DO and SDO command other modules in the system.

Board testing

We present here the test data sequences (and associated expected outputs). The final board test data set is: This test data set is made of three sequences, the first two of size 24, the third one of size 1. It covers all the possible values for the 25 outputs, and the particular case of the transfer command set to 0.

CONCLUSION AND FUTURE WORK

We have presented a method for mixed-signal board testing, designed to face the specificities of maintenance testing. Some aspects have been validated such as the functional approach at all levels, the homogeneous modelling formalism (for digital, analogue and mixed-signal functions) and the testing strategies. The prototype is already able to generate expected test data (thus completing the first part of the method, cf. Figure 1) for the boards involved in the case studies.

Further work is needed to validate our complete approach and prototype, and its real impact on diagnosis. In particular, the second part of the method (depicted in Figure 2) is not yet implemented and needs an important effort as it implies the construction of a physical board, dedicated to the application of our method on a specific ATE.

Future work includes more experimentation of the method on other types of boards, but first results are encouraging, reinforcing the idea that at least semi-automatic testing of mixed-signal boards is feasible. This kind of tool would respond to a real need in the industrial community.