Laurent Capocchi
email: capocchi@univ-corse.fr

Fabrice Bernardi
email: bernardi@univ-corse.fr

Dominique Federici
email: federici@univ-corse.fr

Paul-Antoine Bisgambiglia

BFS-DEVS: A General DEVS-Based Formalism For Behavioral Fault Simulation

Keywords: Discrete Event Simulation, Concurrent and Comparative Simulation, Fault Simulation, DEVS, VHDL

Discrete event modeling allows designing an easy-to-handle and reusable representation of a system but, in its classical form, only permits one simulation at a time for a system. Concurrent and Comparative Simulation (CCS) with Multi-List Propagation (MLP) appears to be an adapted solution, by providing a way to perform several simulations in a single execution run. Concurrent Fault Simulation (CFS) has been one of the first applications of the CCS. The main obstacles to a wide use of this technique are the high complexity of the concurrent simulation algorithms, along with the difficulty to integrate them in a simulation kernel. We focus in this paper on the CFS with MLP of systems described in the new BFS-DEVS formalism, which is an evolution of the original DEVS simulator that integrates the CCS algorithm. The application is performed in the behavioral digital domain of systems described in the VHDL language.

Introduction

Over the last 40 years discrete event simulation has begun to replace physical experimentation, as modeling and simulation offer efficient alternatives to expensive and complex physical experiments. Discrete event modeling allows designing an easy-to-handle and reusable representation of a system. However classical discrete event simulation only permits one simulation at a time for a system. This solution can appear to be very time consuming when many successive simulations are required for the complete experiment, especially in terms of result analysis and observability. In order to escape from these limitations the Concurrent and Comparative Simulation (CCS) with Multi-List Propagation (MLP) appears to be an adapted solution, by providing a way to perform several simulations or other tasks in a single execution run.

Concurrent Fault Simulation (CFS) to simulate faults (mainly inside digital systems) has been one of the first applications of the CCS. The main obstacles to a wide use of this technique are the high complexity of the concurrent simulation algorithms, along with the difficulty to integrate them in a simulation kernel. Essentially for these reasons, fault simulation is not widely used in the domain of discrete event systems, whereas analysis of faulty behavior of discrete event systems could take profit from the established knowledge of digital domain.

We focus in this paper on the CFS with MLP of systems described in the BFS-DEVS formalism (Behavioral Fault Simulation for Discrete EVent system Specification) based on the DEVS formalism introduced by Zeigler in the late 70's in [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF]. DEVS provides a modular and modeling approach, and automatically defines a simulator directly from a model using formal elements and algorithms. It also allows the integration of concurrent simulation algorithms in a simple, evolutive and transparent fashion for the system modeler.

Discrete event simulation has been used in hundreds of different domains (graph analysis, economical studies, symbolic simulation,...) and CCS can be virtually used in each of them. However even if CFS is approximately 20 years old, it is the only real existing application of CCS, and is not or not much used in the discrete event domain. Indeed, for many years, fault simulation has been an essential basic tool of CAD (Computer Aided Design) systems for digital circuits (see [START_REF] Larsson | Behavioral and structural model based approaches to discrete diagnosis[END_REF], [START_REF] Giambiasi | Test pattern generation for behavioral descriptions in VHDL[END_REF] and [START_REF] Santucci | Behavioral testing of digital circuits[END_REF]), but has never been used in the discrete event domain where it could help to analyze faulty behaviors. [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF] proposed a first approach for fault simulation of systems described using DEVS but did not formally integrate the concurrent algorithms. We present in this paper the BFS-DEVS formalism integrating the CFS with MLP algorithms in its kernel, and allowing the modeler to specify the faulty behavior of a system using a new faulty transition function.

Many fault models (see [START_REF] Corno | An RT-level fault model with high gate level correlation[END_REF], [START_REF] Buonanno | How an "evolving" fault model improves the behavioral test generation[END_REF] and [START_REF] Thaker | Register-transfer level fault modeling and test evaluation techniques for VLSI circuits[END_REF]) and concurrent fault simulators for digital circuits (see [START_REF] Gai | The performance of the concurrent fault simulation algorithms in MOZART[END_REF], [START_REF] Machlin | Switch level concurrent fault simulation based on a general purpose list trasversal mechanism[END_REF] and [START_REF] Montessoro | Creator: General and efficient multilevel concurrent fault simulation[END_REF]), essentially occurring at the gate level, have been implemented in past years. The increasing complexity of integrated circuits has led to the development of test tools occurring at higher abstraction levels than the gate level (see [START_REF] Fin | A VHDL error simulator for functional test generation[END_REF], [START_REF] Fulvio Corno | RT-level fault simulation techniques based on simulation command scripts[END_REF] and [START_REF] Thaker | Register-transfer level fault modeling and test evaluation techniques for VLSI circuits[END_REF]). In order to sooner operate in the integrated circuits conception phase, commercial behavioral fault simulators such as HYPERFAULT or TURBOFAULT have been developed, allowing tests to be performed on circuits described in Hardware Description Languages (HDL). However these simulators use heterogeneous simulation en-This article is organized as follows. In a first section we present a state of the art of the CCS domain. A second section is devoted to the presentation of the original DEVS and the new BFS-DEVS formalisms. We show in this section how DEVS is modified in order to integrate the concurrent simulation algorithm. We present in a third section the fault simulation environment along with the essential concepts of BFS-DEVS that are the component library and the fault model. The next two section show how BFS-DEVS is applied in the behavioral digital domain of systems described in the VHDL (VHSIC High level Description Language, described for instance in [START_REF] Ashenden | The designer guide to VHDL[END_REF]) language with some experiments and results. Finally the last section concludes this paper and provides some perspectives of work.

Related Work

Concurrent and Comparative Simulation

As claimed by [START_REF] Ulrich | Concurrent and Comparative Discrete Event Simulation[END_REF], "based on the discrete event simulation, the serial simulation of single experiments is a widely used alternative for physical experimentation. For example, building a model and serial simulation of a model is often superior to building, analyzing and testing physical prototypes of engineering designs. However, usually many similar experiments must be simulated, and each experiment requires manual work." Since the early 70's, many digital systems fault simulation methods have been simultaneously developed to become superior to the serial simulation: this include parallel, deductive and concurrent simulation approaches (respectively proposed by [START_REF] Seshu | On a improved diagnosis program[END_REF], [START_REF] Armstrong | A deductive method for simulating faults in logic circuits[END_REF] and [START_REF] Abramovici | Concurrent fault simulation and functional level modeling[END_REF]). Many fault simulators have been implemented like DECSIM, MOZART, CREATOR, COSMOS or MOTIS, and these methods allow gains in generality, speed, observability and methodological power. Moreover they can be used beyond digital circuits and fault simulation.

CCS is an algorithmic method that applies, and is limited, to systems simulated using discrete events. Its speed increases with the experiments number and similarity: results of a CCS execution are proportional to the number of simulated experiments. This method is parallel/concurrent and minimizes the manual work since it is more systematic, exhaustive and statistical than the serial approach. Moreover its scope is greater because it permits the comparative experimentation of thousands of experiments.

Serial simulation involves a lot of manual work. Therefore initial experiments receive the maximum amount of user's attention, and later are often neglected and not simulated. Results arise in an arbitrary order in which experiments are simulated. For CCS no arbitrariness exists, all experiments are simulated, results appear in a race-like style, in time order and in parallel, and simultaneous results appear simultaneously. Thus all results can be analyzed in a comparative/statistical fashion at any time.

CCS is similar to a multi-processor simulation with one processor by experiment. However there is no need in a parallel computer and costly communication between processors are avoided. CCS obtains a similar efficiency to a parallel computer using only one processor and an equivalent number of virtual processors. In contrast with typical hardware, it is a precise time synchronous method. Being a software solution method, it is more general and flexible than hardware.

Other major properties of CCS are:

(1) CCS is a general and precise method as it permits the simulation of complex sub-systems such as memories. This is essentially due to the MLP technique which allows propagating several object lists into the system in a same time. (2) CCS is fast in several ways. It minimizes the development time because it aggregates experiments into one simulation run, avoiding interruptions and manual work between successive serial experiments. It also minimizes the CPU time because it is based on similarity and on the unique initialization of the simulations. (3) Observation, relative to the observation of the serial simulation, is easy to perform because experiments are performed in parallel. Based on experiment signatures handling and on an artificial experiment average, observation is largely automatic. Signatures may contain deterministic and statistical information about an experiment, its size (relative to a reference experiment) and a statistical distance (a similarity measure) starting from average experiments. Signatures can determine similarities between experiments allowing the elimination of non informative ones. (4) Modeling and simulation are tightly related and modeling requires the testing of sub-models. An optimal testing method is a systematic submodels simulation, which is naturally and easily done with CCS. (5) Many applications using CCS are available, and one particularly interesting is the Concurrent Software Simulation (CSS, used in [START_REF] Demba | Experiences with concurrent fault simulation of diagnostic programs[END_REF]). CSS simulates variant executions of a computer program, and is useful for testing/debugging most kinds of computer programs, finding bugs more quickly and exhaustively than with non-simulating tools. (6) Based on automatic observation, a CCS can be automatically controlled.

Deletion or addition of experiments and run terminations can be performed automatically. While serial experiment requires much manual work, CCS is a more automatic, systematic, error-free method. (7) Many scientific fields require similar physical experiments in parallel like biology, chemistry, meteorology..., but they are too costly due to the needed parallel resources. However when discrete event simulation is a substitute for physical experimentation, then CCS is usually an alternative to serial simulation.

Concurrent Fault Simulation

Fault simulation for digital networks has been the first application of concurrent simulation and is widely used nowadays. Gate level simulation has been the first (and is today the most) implemented application in commercial tools (Mentor or Synopsys), while networks represented at other levels are less easily managed. For instance the DECSIM simulator described in [START_REF] Kearney | DECSIM: A multi-level simulation system for digital design[END_REF] can simulate faults at four logic levels (switch, gate, register, and behavioral), but requires five distinct sub-systems to do this: the four logic levels plus an additional level to manage the information flow between them. The CREATOR simulator described in [START_REF] Gai | Advance in concurrent multilevel simulation[END_REF] reduces in a significant way the number of needed CCS sub-systems using MLP and other generalizations.

Originally concurrent fault simulation has not be defined to speed up the serial fault simulation. However it appeared to be very powerful and the real experience speedups are typically above 1,000:1. Fault simulation is characterized by the need to simulate thousands of faulty experiments. This is usually still impossible due to storage and CPU time limitations, but CSS runs with 10,000 to 50,000 are very efficient. However simulating so many experiments is normally neither necessary nor desirable. For most preliminary experiments, it is sufficient to simulate approximately 1,000 faulty experiments.

The most important works in the fault simulation domain are based on the MLP technique. Interesting approaches such as hierarchical concurrent fault simulations are presented by [START_REF] Lo | Algorithms for an advanced fault simulation system in[END_REF], but the most difficult for fault simulation appears to be fault detection and diagnosis, in conjunction with the execution of diagnostic programs as described by [START_REF] Breuer | Digital system simulation: Current status and futur trends[END_REF].

3 Modeling Specifications

DEVS Formalism

Introduced by Zeigler in the early 70's and completed in [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF], DEVS is a settheoretic formalism that provides a mean of modeling discrete event systems in a hierarchical and modular fashion. Using this formalism, modeling can be easily performed by decomposing a large system into smaller component models with coupling specifications between them. DEVS defines two kinds of models: atomic and coupled models.

An atomic model is a basic model with specifications for the dynamics of the model. It describes the behavior of a component, which is indivisible, in a timed state transition level. Coupled models tell how to couple several component models together to form a new model. This kind of model can be employed as a component in a larger coupled model, thus leading to the construction of complex models in a hierarchical fashion.

DEVS Modeling

Figure 1 shows a hierarchical structure of a coupled model CM 0 containing two atomic models AM 0 , AM 1 and one coupled model CM 1 . The closer under coupling property allows the inclusion of CM 1 inside CM 0 .

Fig. 1. DEVS Model Couplings Example

As in General System Theory (see [START_REF] Zeigler | An introduction to set theory[END_REF]), a DEVS atomic model contains a set of states and transition functions triggered by the simulator. It is represented by the following structure:

AM =< X, Y, S, δ int , δ ext , λ, t a > where:

-X : {(p, v)|(p ∈ inputports, v ∈ X p )} is the input ports set and values for the reception of external events. -Y : {(p, v)|(p ∈ outputports, v ∈ Y p )} is the output ports set and values for the emission of events. -S: is the internal sequential states set.

δ int : S → S is the internal transition function that will bring the system to the next state after the time returned by the time advance function. -δ ext : Q × X → S is the external transition function that will schedule state changes in reaction to an input event.

λ : S → Y is the output function that will generate external events just before the internal transition takes place.

-ta : S → R +
∞ is the time advance function, that will give the life time of the current state (returns the time to the next internal transition).

We can sketch a dynamic interpretation of these definitions: -X is the input ports set for the reception of external events.

-Q = {(s,
-Y is the output ports set for the emission of external events.

-D is the components set (coupled or basic models).

-M d is the DEVS model for each d ∈ D.

-EIC is the input links set, that connects the inputs of the coupled model to one or more of the inputs of the components that it contains. -EOC is the output links set, that connects the outputs of one or more of the contained components to the output of the coupled model.

-IC is the set of internal links, that connects the output ports of the components to the input ports of the components in the coupled models.

In a coupled model, an output port from a model M d ∈ D can be connected to the input of another M d ∈ D but cannot be connected directly to itself.

DEVS Simulation

As described in [START_REF] Chow | Abstract simulator for the parallel DEVS formalism[END_REF], DEVS allows a hierarchical and modular modeling of decomposable discrete event systems thanks to these specifications . One the main advantages of DEVS is that the simulator is directly and automatically extracted from the model. This DEVS simulator uses the modeling hierarchy and associates a simulator component to each atomic model and a coordinator component to each coupled model. This association allows the control of the behavior of each atomic model and the synchronization of the whole set of models. As shown in Figure 2, the DEVS simulator is hierarchical and is composed by a tree composed by simulators and coordinators. As shown in Figure 3, each simulation cycle consists in three steps: first, the coordinator searches among its subordinates (coordinator and/or simulator) the smallest activation time of their next event. Next the coordinator collects outputs from these imminent models (i.e. models presenting an activation time for the next event equal to the minimal time) and sends outputs on the models coupled to the imminent models. Finally the coordinator calls each of the imminent models to execute their transition function.

Communication between elements drawn in Figure 3 is performed using four types of messages. The initialization message (i, t) is used to perform an initial temporal synchronization between all actors of the system (messages 1a and 1b on the figure). The internal transition message ( * , t) implies the execution of an internal event (message 2a), while the output message (y, t) allows the output communication to the parent elements, and results from the reception of a ( * , t) message (message 2b). Finally the external transition message (x, t) allows the execution of an external event (message 3). All these messages are more precisely discussed in the next sections.

For [START_REF] Wainer | Experiences in modeling and simulation of computer architectures in DEVS[END_REF] DEVS brings many advantages. First it uses a hierarchical and modular modeling approach allowing the description of the multiple levels of a system as shown by [START_REF] Zeigler | DEVS formalism and methodology -unity of conception diversity of application[END_REF]. It also supports the definition of models defined in different paradigms, allowing the definition of multi-components, each defined using a different technique (see [START_REF] Zeigler | DEVS theory of quantized systems[END_REF]). DEVS allows any existing model to be easily extended, and formal definitions of coupled or atomic models can be modified. Moreover each model can be associated with an Experimental Framework (a set of DEVS atomic models that can be coupled with other DEVS models, designing an environment for conducting experiments) used as a testing module. This approach improves testing facilities.

BFS-DEVS Formalism

BFS-DEVS Modeling

The BFS-DEVS formalism introduced in this paper allows the specification and the simulation of faulty discrete event models. A BFS-DEVS model is defined by a classical DEVS structure with the following additional features first introduced by [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF]:

-Transition and/or output functions are modified if behavioral faults are present in the DEVS model. -Faulty behavior of DEVS models is specified by a new faulty external transition function δ f ault .

Consider a DEVS atomic model whose healthy behavior can be represented by the following DEVS structure:

AM h =< X h , S h , Y h , δ h int , δ h ext , λ h , ta h >
We define the following structure to take the faulty behavior into account:

AM f =< X, S, Y, F, δ int , δ ext , δ fault , λ, ta >
where,

-X = X h X f is the set of input values, with X f representing a set of new faulty values. -S = S h S f is the set of state values, and S f is the set of new faulty states that the model can present due to the presence of a faulty input event.

-Y = Y h Y f is the set of output values, with Y f representing the set of
new faulty values that the output ports can take when a faulty input event occurs.

-F = {F 1 , F 2 , F 3 }
is the faults set, with {F 1, F 2, F 3} is the fault model described further.

δ int : S × F → S is the internal transition function modified by the presence of faults and presents the restriction δ int (s, ) = δ h int (s). -δ ext : Q × X × F → S is the external transition function modified by the presence of faults and verifies δ ext (s, e, x,

) = δ h ext (s, e, x) if x ∈ X h . -δ f ault : Q × X × F → S
is the faulty external transition function providing the faulty behavior when a faulty event occurs.

-λ : X × F → S is the output function, which verifies λ(s, ) = λ h (s). -ta : S × F → R +
∞ is the time advance function,f with the restriction ta(s, ) = ta h (s).

BFS-DEVS specifications are very similar with the original DEVS ones. The difference is that any time a faulty event x f (x f ∈ X f ) occurs, the new faulty state is calculated by the faulty external transition function δ f ault . If the healthy event x h (x h ∈ X h ) occurs, then the new healthy state is calculated by the healthy external transition function δ h ext .

We note that BFS-DEVS models coupling is not changed. But if the fault model contains a structural fault type, this coupling becomes different from the original DEVS coupling. Moreover, we can prove that the property of closure under coupling allowing the hierarchical composition of model is preserved.

BFS-DEVS Simulation

Communication between components is achieved in the original DEVS formalism using four types of messages. To distinguish a faulty behavior inside a simulation, we introduce a new message type message that activates the model as soon as a fault event x f is present on one of its ports at a given time t. Thus we are able to activate the faulty behavior of a component using such a message representing a faulty external event as shown in Figure 4.

A coordinator, using the X set, is then able to send two types of external messages to its imminent children, a "x-message" for a healthy simulation, and a "f-message" for a faulty simulation. Thanks to this distinction we can concurrently perform the faulty and healthy simulations. Indeed the faulty simulation can only be performed if the healthy simulation has already been achieved, because values of the first are used as references for the second. Consequently the healthy simulation precedes the faulty one.

Thus the simulator associated to a DEVS model receiving an external event x (x = x h ∈ X h ), and supposed to present a faulty behavior, receives in fact two types of messages. In a first step a x-message (x s , t) implying the activation of the external transition for the healthy part of the simulation, followed in a second step by a f-message ( , t) implying the execution of the external fault transition function for the faulty part of the simulation. If the model receives an external faulty event x f (x f ∈ X f ), the associated simulator will only receive a f-message (x f , t) from its parent coordinator. Thus it is the nature of the external events that allows the distinction on simulation paths.

4 The Fault Simulation Environment

General Architecture

Concurrent fault simulation is approximately 20 years old and is one of the only existing applications of the concurrent simulation. However discrete event simulation has been employed in many applications and CCS can virtually be applied to each of them. Figure 5 (a) extracted from [START_REF] Ulrich | Concurrent and Comparative Discrete Event Simulation[END_REF] illustrates the relationships between the CCS simulation kernel and applications. We can see that this kernel implies the use of a mandatory modeling interface for a given application. However CCS allows the simulation of models created independently from their execution (concurrent) simulation environment. Thus CCS permits simplicity in writing simulation models and generality in how they are used.

Fig. 5. BFS-DEVS Positioning

To define the software interface, we propose the BFS-DEVS formalism allowing:

-Concurrently modeling and simulating faults of discrete event systems issued from one application. -Distinguishing between the model of the system and the simulation kernel.

-Implementing the model and the concurrent algorithms inside the simulation kernel using an object-oriented approach. -Plugging fault models on demand.

-An easy updating of models in a hierarchical and modular fashion. shows that an application will be represented by a network of BFS-DEVS components (atomic and/or coupled model) constituting the Library. This network is directly simulable by the simulation kernel. This modeling is the interface between the physical applications and the BFS-DEVS simulation kernel based on the CCS. Thus to simulate a given application the modeler would design a domain specific BFS-DEVS library without thinking about the simulation part.

BFS-DEVS Library and Fault Models

Each application owns a BFS-DEVS components library defined by the user. As shown in Figure 6, this library is composed by models (atomic and/or coupled) used to compose the final model to be simulated. Its construct implies the knowledge of a fault model mandatory for the definition of the faulty behaviors. The behavioral rules associated to the data and structure graphs of the application allow defining the models, their interfaces and behaviors. Determining the control and data structures for a given application is not straightforward, and implies a strong collaboration with a studied domain specialist. This determination follows from the discrete event modeling and its result is translated into a network of models. Recurrent types of these models will constitute the BFS-DEVS library. Building a library for a given domain is not easy, but is the only "delicate" phase of our approach.

Before going further in our development we need to introduce some notions. First a behavioral fault is described by [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF] as a modification of the transition functions, and/or of the output functions of the DEVS models. Thus a fault influences the behavior (or the state) of an affected DEVS model and can lead to a faulty behavior we previously described. Inside the BFS-DEVS formalism, a new transition function δ f ault is introduced that permits to specify a faulty behavior for the model. This faulty behavior is obviously related to the fault type the model is affected by. Each fault type able to affect a BFS-DEVS model will change its state using the δ f ault function.

Second a fault model is the set of type of faults that can modify the behavior of a BFS-DEVS model. It strongly depends on the nature of the modeled and simulated physical system. Indeed behavioral fault types inside the BFS-DEVS network must be the most representative of the behavioral defaults of the physical system. The fault model strongly depends on the control and data structures of the application and is integrated into the behavior and the structure of each BFS-DEVS model.

Another important notion is the fault signature which is the consequence of a fault on the behavior of the affected BFS-DEVS models. Each fault owns a signature in which the faulty behavior of all affected BFS-DEVS models is stored.

We call a detectable fault on a BFS-DEVS model a significant fault on a model, i.e. whose signature presents a faulty behavior distinct from the healthy behavior at the end of the simulation.

Finally a locally observable fault is a fault that modifies the behavior of the model during the simulation. A fault is locally observable as long as the behavior is faulty.

BFS-DEVS Simulation Kernel

A concurrent fault simulation inside a BFS-DEVS network (aka. BFS-DEVS simulation) is a healthy simulation of this network along with the concurrent execution of faulty simulations induced by multiple propagated fault lists. Before going further in our development we need to introduce some very essential notions. A propagated fault list groups all faults presenting same signatures. Indeed different faults belonging to a same fault model can imply the same faulty behavior on a BFS-DEVS network. This is one of the main reasons why we can detect different faults in a single BFS-DEVS simulation run. During the simulation the fault list propagation is performed using messages carried on the models ports.

A healthy simulation (aka. reference simulation) is a BFS-DEVS simulation in which no behavioral fault is present. A fault list is built for each model met on this path.

We use the single fault hypothesis defining that only one fault is present in a model at a time and that the effect of the fault is present during the whole simulation. However we can still simulate many faults inside one BFS-DEVS model using the concurrent simulation based on fault lists propagation.

A faulty simulation (aka. concurrent simulation) is a BFS-DEVS simulation in which at least one model is affected by a unique fault list, which can modify the final result of the healthy simulation. However a BFS-DEVS network can be composed by models presenting many possible faulty behaviors (models presenting many output ports). Consequently faults present inside the propagated list can imply different faulty behaviors, leading to a fault list presenting different signatures. Since faults present in the propagated list must have unique signatures (cf. the propagated fault list definition), the initial list is decomposed in sub-lists with the same signature. As a faulty simulation propagates a unique fault list, previous sub-lists are propagated on new faulty concurrent simulations. Thus a faulty "parent" simulation can give birth to "child" faulty simulations propagating sub-lists of the initial fault list. A BFS-DEVS concurrent fault simulation can be then viewed as several faulty simulations concurrencing the healthy one. This property allows us to simulate many faults inside a BFS-DEVS network while respecting the single fault hypothesis.

A healthy (resp. faulty) message is an object allowing the communication and the activation of BFS-DEVS models for a healthy simulation (resp. faulty simulation). It also allows the propagation of the fault lists, the simulation time and several other information inside the network. A faulty message containing an initial fault list can be divided and can give birth to messages containing sub-lists of the initial list.

A healthy path (aka. reference path) is the sequence of (atomic and/or coupled) BFS-DEVS models activated by a healthy simulation of the network.

A faulty path (aka. concurrent path) is the sequence of (atomic and/or coupled) BFS-DEVS models activated by a faulty simulation. This path is concurrent to and obviously different from a healthy path. A faulty path can be divided in some concurrent faulty paths. In order to illustrate the previous notions, consider Figure 8. Let's assume that the healthy simulation activates the models AM 0 , AM 1 , AM 4 , AM 5 , AM 6 , AM 15 and AM 16 (in grey) thus defining the healthy path (bold lines). Each one of these models builds its own fault list: FL0 for AM 0 , FL1 for AM 1 , etc. In our approach faulty simulations are executed concurrently to the healthy simulation, and activate the other atomic models (in white) to give birth to faulty paths (plain lines). Let's also consider that the dashed models and paths on the figure are not simulated because FL1 1 is not divided.

At the beginning of the simulation FL1 is propagated using a faulty message to build the fault signatures for each activated model (for instance AM 7 and AM 8 ). However this list is cut up and is reoriented all along the main faulty path. Indeed all faults belonging to FL1 and evaluated by AM 2 do not imply the same faulty behavior for this last model. Consequently the main fault list FL1 is divided into two sub-lists FL1 0 and FL1 1. These lists are composed by faults implying the same behavior for AM 2 . This division ensures that it exists only one unique signature inside each propagated fault.

As soon as faulty paths join (AM 14 and AM 15 ) propagated faults are merged and their signatures analyzed to build the detected fault list. Finally the main fault list FL0 will be analyzed at the end of the healthy simulation, i.e. when all faulty behaviors have been simulated.

General Object Oriented Implementation

We propose in this section an object oriented implementation based on the previously described notions, and that follows the original DEVS object architecture. The DEVS package shown in Figure 9 is composed by two main abstract classes called AtomicDEVS and CoupledDEVS inheriting the properties of the other abstract class BaseDEVS. These two classes allow the implementation of the atomic and coupled DEVS models and are associated with a Port class used to represent their ports. The whole structure of the system is then represented by an interconnection of instances of these classes. In the DEVS formalism atomic models represent the behavior of the model and coupled models the structure. Thus, to be generic, we define two new classes DomainBehavior and DomainStructure in an other package called Domain.

Classes belonging to this package are the basis of our architecture. The main class Master is a specialization of a CoupledModel class and shall represent the highest level coupled model of the whole model. Only one instance of this class is allowed which will be statically accessed by the DomainBehavior, DomainStructure and SDB classes. The δ f ault function is defined inside the DomainBehavior. DomainStructure allows describing the structural elements used by the Master class, and presents methods like check rules() allowing the validation of the structure using a domain parser. The SDB (Symbolic DataBase) class is introduced to facilitate access to the studied domain data structure. This class, used by a Master is used to store objects handled by the domain, and can also be instancied only one time.

As shown in Figure 9, the XDomainBehavior, XSDB and XDomainStructure are specific to the studied domain, and for each domain these three classes need to be implemented.

To sum up, it will exist only one Master instance that will contain one instance of XSDB as a static attribute. BFS-DEVS atomic models will be represented by specialization instances of XDomainBehavior, and coupled models by class specialization instances of XDomainStructure. The set composed by these classes will define the BFS-DEVS library for the X domain.

We can note that we use a Singleton Design Pattern defined by [START_REF] Gamma | Design Patterns, elements of reusable object-oriented software[END_REF] to ensure the unicity of the Master and XSDB instances that do not appear on the diagram for simplicity reasons. A VHDL description is composed by two parts. First the description of the circuit interface with its environment called entity and composed by the signals list, their direction, their nature, etc.; Second the description of the circuit called architecture that can contain three types of description, the structural description of the sub-circuits interconnections, the functional description of the used boolean functions, and the behavioral description which is represented by algorithms allowing simulating the behavior of the system.

We only focus in this paper on the behavioral description, which is the most used today. This description is composed by a collection of parallel processes containing sequential statements (assignment, conditions, etc.), functions, procedures, signals and variables only used for calculus. Signals are used to allow processes to communicate, and are stored in their respective sensitive lists. Each signal owns a pilot which is a 3-columns table containing the current and future values and the assignment time of the future value. A signal can be "multi-source", i.e. can be affected in several processes. But in order to avoid assignment conflicts we consider that a signal is "uni-source".

Figure 10 presents a multi-process behavioral description of a 8 bits register containing three processes STROBE, ENABLE and OUTPUT along with their sensitive lists (STRB), (DS1,NDS2) and (REG,ENBLD).

Behavioral Fault Model

In the past years several high level behavioral fault models associated with some fault simulation techniques have been proposed by [START_REF] Thaker | Register-transfer level fault modeling and test evaluation techniques for VLSI circuits[END_REF], [START_REF] Corno | An RT-level fault model with high gate level correlation[END_REF], [START_REF] Corno | Testability analysis and ATPG on behavioral RT-level VHDL[END_REF], [START_REF] Santucci | Behavioral testing of digital circuits[END_REF] and [START_REF] Buonanno | How an "evolving" fault model improves the behavioral test generation[END_REF]. However [START_REF] Goloubeva | Behavioral-level fault models comparison: An experimental approach[END_REF] shows that none of them formally establishes the relationships existing between the high level and gate level fault coverages, but considers that the closest fault model is consituted by the bit and conditional coverages.

As in [START_REF] Fulvio Corno | RT-level fault simulation techniques based on simulation command scripts[END_REF] As in [START_REF] Fulvio Corno | RT-level fault simulation techniques based on simulation command scripts[END_REF] we adopt the single fault hypothesis. We use three behavioral fault types acting on the VHDL instructions present in the description to be simulated:

-F 1 Fault Type: These faults are value stuck-at (signals or variables) faults present in the description. For instance, consider the assignment instruction E : S1 <= (S2 and S3) or S4, where the type of S1, S2, S3 and S4 is T : bit.

Evaluation of E gives a healthy value v h to S1, and all S1 i faults of type F 1 on S1 implying a faulty value v f will be the stuck-at values of its definition domain minus the healthy value:

{S1 i |v f ∈ T -{v h }}. In this example if v h = 1
, stuck-at faults on S1 will be stored in the list L S1 = [S1 0 ]. In the same way faults of type F 1 implying a faulty evaluation of E will be determined following their healthy current values. Some of the fault models used by [START_REF] Corno | An RT-level fault model with high gate level correlation[END_REF] convert VHDL objects such as "integer" into the equivalent bit vector according to synthesis conventions, and each element is considered separately as a bit. We can also perform this kind of translation, but the type F 1 appears sufficient to show the validity of our approach. This type corresponds to the bit coverage described in [START_REF] Goloubeva | Behavioral-level fault models comparison: An experimental approach[END_REF]. -F 2 Fault Type: These faults are branch stuck-at faults (stuck-at-true, stuckat-false) of the conditional instructions. When a conditional instruction is evaluated, a healthy conditional branch is chosen between a finite set of possibilities. The stuck-at of other branches different from the healthy branch constitutes the F 2 type. This type corresponds to the conditional coverage described in [START_REF] Goloubeva | Behavioral-level fault models comparison: An experimental approach[END_REF]. -F 3 Fault Type: These faults prevent an assignment instruction to be evaluated. This fault type allows the deletion of redundant assignment instructions inside a VHDL description (see [START_REF] Bisgambiglia | Fault modeling and simulation at behavioral level[END_REF]).

VHDL to BFS-DEVS Translation

The VHDL to BFS-DEVS translation allows describing the control and data flows of a VHDL description as a BFS-DEVS network. This translation brings several advantages. Indeed it provides an homogeneous and modular integration of the simulation algorithms inside the δ f ault transition functions. It also permits a simplification of the analysis and observability treatments and an easy adaptation of the behavioral (or even structural) fault models.

In VHDL a fault will be considered as a bad evaluation of an instruction.

In BFS-DEVS a fault inside an atomic model representing a VHDL instruction modifies its behavior implying a faulty simulation. The three fault types previously described become in this case:

-The F 1 Fault Type, a faulty state transition of a model.

-The F 2 Fault Type, the selection of a faulty output port of a model.

-The F 3 Fault Type, a non-activation of a model.

We use for this paper behavioral VHDL descriptions using sequential instructions composed by one or several process instructions. Each of them is composed by sequential instructions such as assignment, conditional ("if-then-else, case"), and loop statements. We show in [START_REF] Capocchi | Transformation of VHDL descriptions into DEVS models for fault modeling and simulation[END_REF] that these descriptions can be represented using four BFS-DEVS atomic models:

An Assignment atomic model represents a VHDL assignment statement. This association allows us giving a faulty or healthy behavior to the instruction. When such a model is found in the network a fault list of the F 1 type is built. A Conditional atomic model represents a VHDL conditional statement.

This association allows us developing the functions used to determine the F 1 and F 2 faults. A Junction atomic model is associated with end-code statements such as "endif, endcase". Algorithms for fault local observability are defined inside these components. A Process coupled model is associated with the VHDL "process" statement.

It is a coupled model for the structuring of the previous atomic models.

Two new atomic models are introduced:

A Generator atomic model that generates events for the activation of the components inside the BFS-DEVS network. A model of this type is mandatory for the simulation. A ProcessEngine atomic model that manages the processes synchronization and the fault list propagation. This model participates also in the observability analysis, and in the detected fault list update. The VHDL to BFS-DEVS translation is performed using a parser that uses the library, provides the BFS-DEVS network and the total fault list.

Figure 12 shows the generated BFS-DEVS network starting from the 8 bits register description presented in Figure 10.

VHDL BFS-DEVS Simulation

In order to explain the VHDL BFS-DEVS simulation we need to introduce or complete some notions.

A fault signature corresponds to the trace T F i = {((S|V ) j , P (S|V ) j )|i, j ∈ N} of the F i fault on a healthy or faulty path. It is represented by the set of couples ((S|V ) j∈N , P (S|V ) j ) where: S j (or V i ) is the influenced signal (or the influenced variable) by F i , and

P (S|V ) j = [v cf , v f f , time]
is the pilot of the current v cf and future v f f faulty values of S i (or V i ) by F i at time cycle time. A fault can be associated to several signatures.

The locally observable fault list L O is a list of faults implying a different result from the healthy simulation. This result is locally observable on signals and variables of the description.

The detected fault list L D is a list of the detected faults visible on output signals during the concurrent fault simulation. We have

L O ∩ L D = ∅.
A healthy simulation is the parallel execution of the coupled models with no atomic model presenting a faulty behavior.

A faulty simulation is the parallel execution of the coupled models with one or more atomic models presenting a faulty behavior.

An active process is the activation of a coupled model for a healthy or faulty simulation.

An inactive process is the activation of a coupled model for a faulty simulation. However if no atomic model presents a faulty behavior, the coupled model is not activated to speed the simulation up.

A healthy path is composed by the set of BFS-DEVS models activated during a healthy simulation run. However because of the concurrency a healthy path can obviously be divided in several independent healthy sub-paths.

A faulty path is composed by the set of BFS-DEVS models activated during a faulty simulation run.

A reference database is an object storing the VHDL constants and pilots of all signals, variables belonging to this description. This database is accessed by the four basic atomic models previously seen.

We can now define the BFS-DEVS concurrent fault simulation of VHDL systems represented by N > 0 coupled models, as the parallel execution of x < N coupled models for a healthy simulation, and of 1 ≤ i ≤ Nx coupled models for i faulty simulations induced by L i propagated fault lists inside the network.

To illustrate these definitions consider a BFS-DEVS network of a multi-processes behavioral description. During a simulation run, n > 0 coupled models are active for n healthy simulations, and m > 0 coupled models are active for m faulty simulations. We also consider that each coupled model has several paths, implied by the presence of conditional atomic models. Healthy simulations are executed inside the n coupled models, thus defining the n healthy paths. In order to highlight faults implying the faulty paths, faulty simulations are concurrently executed with the healthy simulation in the n + m coupled models.

We can see on Figure 13 that faulty paths derive directly (resp. indirectly) from the n = 2 healthy paths inside the CM 1,2 coupled models (resp. the CM 3 coupled model).

Figure 13 (a) shows the healthy paths (bold) resulting from a healthy simulation of the two coupled models CM 1 and CM 2 corresponding to two active processes AP 1 and AP 2 . Since IP 1 is inactive CM 3 is not activated. We can note that even if IP 1 is inactive for the VHDL simulation, CM 3 would become active whether a simulation of faults in F L 3 is activated.

VHDL Simulation Cycles

VHDL simulation is managed through events on the communication signals between processes. The simulation cycle called symbolic cycle (or delta cycle) is divided in three distinct phases (grey in Figure 14): the EXECUTION phase corresponding to the parallel execution of the processes, the UPDATE phase corresponding to the update of the signals pilot values attributes, and the ANALYSIS phase establishing the list of the processes to be activated following programmed events on sensitive signals.

As shown in Figure 14 the concurrent fault simulation relies on these three phases and complete them with two new phases relative to the concurrent simulation technique used: the fault OBSERVABILITY phase to build the L D list, and the FAULT COVERAGE CALCULUS.

Thus the simulation scheme can be divided in five phases:

(1) The CONCURRENT FAULT SIMULATION phase that consists in a healthy simulation whose results are stored in a reference database, and in concurrent faulty simulations to construct or update L O . (2) The local OBSERVABILITY phase of the propagated faults occurring as soon as all processes have been simulated. This phase consists in com- If no process has been activated for a healthy simulation, no update is performed. (4) The future process activity ANALYSIS that presents a supplementary procedure to manage the fault influence inside the sensitive signals. Indeed if a sensitive signal is affected by faults, these lasts can give birth to faulty simulations on the processes the signal belongs to. [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF] The FAULT COVERAGE CALCULUS only occurs when the future process activity analysis is negative. A fault belonging to L O will be detectable if it implies, in its signature, a current faulty value different from the current pilot value of an output signal. All detected faults are transfered from L O to L D . The fault coverage is given by: C(%) = number of detected f aults total f ault number * 100

Fault List Propagation

The BFS-DEVS concurrent fault simulation can be composed by several faulty simulations driving fault lists to obtain the signatures. Propagation of this list is achieved using a cutting up and an initial list reorientation. Fault list propagation can be divided in two parts: the intra-process (list propagation inside coupled models) and the inter-process (list propagation between coupled models) propagations. To describe these two propagations, we define:

-A VHDL description presenting N processes: P 0<n≤N .

-The sensitive signals lists for processes activation:

L n = {S k∈N }.
-The propagated fault lists:

F L n = {F i |i, n ∈ N}.
-The locally observable fault list: L O .

-The signatures describing the fault propagation during the concurrent simulation: ∀F i ∈ N, T F i = {((S|V ) j , P (S|V ) j )|j ∈ N}.

Intra-process Propagation

At the beginning of a VHDL simulation cycle (except for the initialization cycle) each process can present an activity depending on the sensitivity of the signal belonging to L n .

If a VHDL process P n is active (cf. Figure 15 (a)) the corresponding coupled model CM is also activated by a Generator atomic model in order to run the healthy simulation along with:

-The simulation of the faults F i implying a non activation of CM , and stored in an initial fault list built by the Generator using L O (F L O in Figure 15). Observability of these faults depends on the result of the healthy simulation. Faults will only be appended to L O at the end of the simulation by a ProcessEngine atomic model. -The simulation of the faults F i able to appear inside the Assignment and Conditional atomic models activated by the healthy simulation (bold in Figure 15 (a)). These faults are stored in lists F L n (F L 1 for AM 1 , F L 4 for AM 4 etc.). In the case where these lists come from an Assignment atomic model (AM 1 ,AM 4 , AM 5 , AM 6 ), they are directly appended to L O , the list of locally observable faults. If they come from a Conditional atomic model (AM 16 ) they will be appended to L O by the corresponding Junction model only when once having been simulated on the faulty paths they imply (plain line on the figure). Indeed these lists F L n can give birth to other sub-lists F L nm (F L 1 = F L 1 0 + F L 1 1 on the figure). L O is acting as a reference. On the one hand because if a fault is highlighted on a Assignment atomic model and is already in the fault list, an update of the trace is performed, otherwise the fault is appended. On the other hand because if a fault is highlighted on a Conditional model and is already in the fault list, it will be copied and inserted in the list F L n that will be propagated on the faulty paths. Observability of the contents of the list will be analyzed at the junction of the faulty paths.

If a VHDL process P n is inactive (cf. Figure 15 (b)), the associated coupled model is activated by a Generator atomic model in order to simulate the faults F i ∈ F L n that would have activate it. These faults are essentially directed towards the signals of L n . But contrary to the previous case, the faults F i can present initial signatures during the list propagation. These signatures are issued from the reference list L O and will be updated during the faulty simulation of P n . All faults initially contained in F L n can not take the same path. In the example shown in Figure 15 (b), the initial fault list F L 1 is cut up in two sub-lists F L 1 0 and F L 1 1 such as F L 1 = F L 1 0 + F L 1 1 , since faults of F L 1 0 do not have the same consequences than faults of F L 1 1 in the AM 2 Conditional model. For the same reasons, F L 0 0 is cut up in two sub-lists F L 0 0 0 and F L 0 0 1 such as F L 0 0 = F L 0 0 0 + F L 0 0 1 .

Analysis of fault signatures is performed in the ProcessEngine model at the end of the faulty simulations. Every observable fault will be appended to L O . If a fault is already present in the list a signature update is achieved. Following this update each fault presenting an empty signature is deleted from L O .

Inter-Process Propagation

The VHDL language defines the internal sensitive signals in order to establish links and parallelization between the processes of a description. Thus faults which can be present on these signals are also linked with the processes. If a fault is locally observable on a sensitive signal it will be simulated inside one or several processes.

In order to establish the building rules for this kind of faults, it is necessary to recall the properties of the sensitive signals defined by VHDL:

(1) No (internal or input) sensitive signal can be affected in the process it activates (auto-activation). This property is illustrated in Figure 16 (a). This configuration can bring to a loop in the process activation. (2) A (internal or input) sensitive signal can be affected in several processes.

However in order to avoid conflicts, a conflict resolution function must be implemented for such a signal. In our method these functions are not taken into account. Thus we consider the configuration shown in Figure 16 (b). (3) A sensitive signal can activate several processes. This property is illustrated in Figure 16 (c) and allows the parallelization of the processes activated by a same signal. These properties allow us defining the following faults characteristics:

(1) A fault can belong to several lists F L n of the n inactive processes P n . This characteristic comes from the property number 3 of the sensitive signals.

(2) A fault can not imply different values for a same signal. This characteristic comes from the property number 2 of the sensitive signals.

We can now introduce the inter-process propagation rules for locally observable faults:

(1) If one fault belonging to L O implies the faulty simulation of n different processes P 0≤n<N , it will be duplicated and inserted in LF n . At the end of the simulation run the fault becomes unique with the fusion of the duplicated faults signatures (from the fault property number 1). ( 2) The analysis of the future processes activity is performed against the signatures of the faults in L O . Every fault present in L O , except those of F 1 type on sensitive signals, can activate the associated processes. We can find two origins for the fault lists F L n . First if a model associated to a process is active for a physical cycle, these fault lists are created by the Generator. This last build these lists with reference to the locally observable fault list L O . If a fault already belongs to L O , it is copied and inserted in F L n . It then will be simulated using the inter-process propagation and analyzed at the end of the simulation run inside the ProcessEngine model. If two faults belonging to different messages arrive at the ProcessEngine model in a same time, their signatures are merged in order to obtain only one signature for the fault.

Second If a coupled model associated with a process is active for a symbolic cycle, the fault lists F L n are generated by the ProcessEngine model. Indeed if coupled model needs to be reactivated by a fault present in L O and implying a variation of a signal of L n , a faulty message is sent to the output port of the ProcessEngine model using the Generator. This last only transmits the message. The VHDLSDB class implements the SDB class and represents the data structure of the VHDL language. It is used to store pilots, attributes and update methods.

Object Oriented Implementation

Experiments and Results

The general CFS with MLP approach presented in this paper has been applied to digital systems described in the VHDL language using a BFS-DEVS simulator prototype and a library of BFS-DEVS VHDL components. This implementation derives from a simulation kernel conform to Zeigler's specifications. The whole prototype is composed by about 8,000 lines of Python code.

In order to show the validity of our approach, we chose a sub-set of the VHDL ITC'99 benchmarks of [START_REF]High time for high-level test generation[END_REF] shown in Table 1. Columns in this table sum up the information at the RTL level in terms of number of VHDL lines of code, number of processes, number of assignment and conditional statements and number of signals and variables.

Figure 19 shows the architecture of the developed prototype. A parser based on GENESI (see [START_REF] Paoli | Simulation-based validation of VHDL descriptions using constraints logic programming[END_REF]) allows obtaining the BFS-DEVS network representation file. This network is simulated to generate the fault list obtained from a test sequence provided by a pseudo-random test pattern generator. This gen-erator provides several pseudo-random test vectors arranged in independent sequences, and each one of these sequences contains the "reset" signal with the value "1".

Calculus of the fault coverage is obtained by the number of detected faults on the total number of faults given by the parser. Results are reported in Table 2 and show the number of detected faults along with the associated fault coverage. Experiments show the validity of the BFS-DEVS formalism and prototype presented in this paper. We can indeed determine the faults effects on the VHDL instructions of the behavioral descriptions. The use of a pseudo-random test pattern generator allows obtaining of significant fault coverages to show the validity of our approach. However the length of the test pattern is sufficiently large to detect the most easily observable faults.

The pseudo-random patterns testability can be anticipated by the analysis of the fault coverages shown in Table 2. We note that the b05 benchmark is random pattern-resistant because it presents low fault coverage. Benchmarks b05, b03 and b10 are difficult to test because their fault coverages are obtained with a high number of test vectors. The fault model used in this test sequence is based on the F 1, F 2 and F 3 fault types. [START_REF] Goloubeva | Behavioral-level fault models comparison: An experimental approach[END_REF] shows that the fault model based only on the F 1 and F 2 types can be used for estimating the gate-level stuck-at fault coverage by reasoning on a behavioral model of the benchmarks. However the majority of undetected faults on the benchmarks are of type F 3. A way to improve the fault coverage would be to remove the F 3 type from our global fault model. Considering the F 3 type is however interesting since it allows removing redundant instructions in the VHDL code. Indeed an assignment model in which a F 3 fault is not detected can be removed from the network. This implies a reduction of the number of lines of the description leading to a simulation speed-up.

Conclusion and Perspectives

We presented in this paper the BFS-DEVS formalism for the simulation of discrete event systems behavioral defaults in a simple and efficient fashion. We saw that this formalism is based on the CCS with MLP algorithms to simulate many input patterns against many faulty scenarios inside the BFS-DEVS network.

The proposed simulation environment is homogeneous and allows simply and generically integrating the domain-specific fault model. The design of a BFS-DEVS component library following the behavioral rules of a system is sufficient for the modeling and concurrent simulation of the defaults that can appear in the network. This simulation is also automatic and transparent for the user.

The object architecture of our prototype is generic and extensible to several domains thanks to the abstract classes DomainBehavior and DomainStructure, respectively used to describe the behavior and the structure of a new domain to be managed.

We validated this approach in the domain of behavioral faults for digital circuits. The fault model we used does not present an important correlation with the fault model at the gate level, but the genericity of our approach permits to specify some other fault models at lower abstraction levels. The fault coverages we obtained on the ITC'99 benchmarks are very satisfying.

In this digital domain the main perspective is to design an ATPG (Automatic Test Pattern Generator) to measure the effectiveness of the test patterns used to perform the fault simulation. We shall based this work on signature analysis and also on genetic algorithms for their proved efficiency.

More generally we have several perspectives concerning this research essentially about analysis and performance aspects. First distributed computing is more and more used in the discrete event simulation domain under the name of PDES (Parallel Discrete Event Simulation). We believe that our approach would take advantage of this technology and we plan to develop a Distributed BFS-DEVS based simulator. For instance when applied to the digital circuits domain, this distribution would allow simulating processes in parallel. Second we think that this work can help testing and debugging classical software programs, and that integrating the CSS (Concurrent Simulation for Software) domain metrics (path coverage, statement coverage, branch coverage,...) would be easy to perform in our architecture.

Finally we are currently applying this work to other domains in order to show its genericity of use. First applications are fire forest propagation and graph analysis.

Fig. 3 .

 3 Fig. 3. DEVS Simulator Message Exchange

Fig. 4 .

 4 Fig. 4. Fault Simulator Architecture

Figure 5 (

 5 Figure 5 (b) shows that an application will be represented by a network of BFS-DEVS components (atomic and/or coupled model) constituting the Library. This network is directly simulable by the simulation kernel. This modeling is the interface between the physical applications and the BFS-DEVS simulation kernel based on the CCS. Thus to simulate a given application the modeler

Fig. 6 .

 6 Fig. 6. Building of a BFS-DEVS Library

Fig. 7 .

 7 Fig. 7. Concurrent Fault Simulation Scheme

Figure 7

 7 Figure7shows how i ∈ N + faulty simulations are generated starting from one unique healthy simulation. These faulty simulations result in faults contained in the F L i propagated lists. Moreover a faulty simulation induced by the fault list F L i can imply j ∈ N + faulty simulations propagating the lists F L ij such as F L ij ⊂ F L i ∀i, j ∈ N + . This propagation of faulty simulations by fault lists cutting up and re-orientation can be performed until one fault list is found, i.e. F L ij ≥ 1.

Fig. 8 .

 8 Fig. 8. Concurrent Fault Simulation of a Sample BFS-DEVS Network

Fig. 9 .

 9 Fig. 9. Diagram of the Main Classes of the Architecture

Fig. 10 .

 10 Fig. 10. VHDL Description of a 8 bits Register

Fig. 11 .

 11 Fig. 11. VHDL to BFS-DEVS Translation

Fig. 12 .

 12 Fig. 12. BFS-DEVS network of 8 bit register

Figure 13 (

 13 Figure 13 (b) shows the faulty paths (dashed) generated by the concurrent faulty simulations. We see that faulty paths inside the coupled models CM 1 and CM 2 are directly concurrent to the healthy paths. On the other side faulty paths inside CM 3 are indirectly concurrent to the healthy paths. Moreover the propagation of the fault list #F L 3 ≥ 4 of the inactive CM 3 by cut up allows the simulation of the faults contained in the lists #F L 30 ≥ 1, #F L 31 ≥ 2, #F L 310 ≥ 1 and #F L 311 ≥ 1.

Fig. 13 .

 13 Fig. 13. Schematic View of a BFS-DEVS Concurrent Fault Simulation

Fig. 14 .

 14 Fig. 14. Concurrent Fault Simulation Scheme

Fig. 15 .

 15 Fig. 15. Intra-Process Propagation

Fig. 16 .

 16 Fig. 16. Process Auto-Activation, Assignment Conflict and Process Multi-Activation

Fig. 17 .

 17 Fig. 17. Inter-Process Propagation

Figure 18 presentsFig. 18 .

 1818 Figure18presents the object-oriented implementation we performed for this application of our formalism. We can see the four classes AtomicJunction, AtomicAssignment, AtomicProcessEngine and CoupledProcess implementing

Fig. 19 .

 19 Fig. 19. General prototype architecture

  e)|s ∈ S, 0 < e < ta(s)} is the total state set.e is the elapsed time since last transition, and s the partial set of states for the duration of ta(s) if no external event occur. -δ int : the model being in a state s at t i , it will go into s , s = δ int (s), if no external events occurs before t i + ta(s). -δ ext : when an external event occurs, the model being in the state s since the elapsed time e goes in s . The next state depends on the elapsed time in the present state. At every state change, e is resetted to 0.

	-λ: the output function is executed before an internal transition, and before
	emitting an output event the model remains in a transient state.
	-A state with an infinite life time is a passive state (steady state), else, it
	is an active state (transient state). If the state s is passive, the model can
	evolve only with an input event occurrence.
	A DEVS coupled model CM is a structure:
	CM =< X, Y, D, {M d ∈ D}, EIC, EOC, IC >
	where:

  the fault model we propose in this paper is based on techniques of test of software. This fault model is mainly based on stuck-at signals and variables present in a VHDL behavioral description. To take into account faults inside the description control graph, we consider also the conditional branch stuck-at faults. Finally we consider the jump of assignment statements fault since it can allow us analyzing the redundant code in a VHDL description. We can note that this fault model is evolutive and has not been conceived to validate a specific metric of the HDL. Moreover it can use several fault models through the use of the fault transition function.

	entity Register is
	Port(DI: in bit vector(1 to 8);
	STRB, DS1, NDS2: in bit;
	DO: out bit vector(1 to 8));
	end Register
	architecture Arch of Register is
	signal REG : bit vector(1 to 8);
	signal ENBLD : bit;
	begin
	STROBE: process(STRB)
	begin
	if (STRB='1') then
	REG<=DI;
	end if;
	end process STROBE;
	ENABLE: process(DS1, NDS2)
	begin
	ENBLD<=DS1 and not NDS2;
	end process ENABLE;
	OUTPUT: process(REG, ENBLD)
	begin
	if (ENBLD='1') then
	DO<=REG;
	else
	DO<=''11111111'';
	end if;
	end process OUTPUT;
	end Arch;

Table 2 VHDL

 2 BFS-DEVS Simulation Results


Anca Molnos

Yves Durand

Nicolas Gonthier

Nicolas Gonthier Trading

Trading sharpness with energy consumption in a lens autofocus application

Trading sharpness with energy consumption in a lens autofocus application Anca Molnos, Yves Durand, Nicolas Gonthier Univ. Grenoble Alpes, Grenoble, France. CEA -LETI, MINATEC Campus, Grenoble, France Email: {anca.molnos, yves.durand, nicolas.gonthier}@cea.fr

Abstract-Approximate computing is an emerging paradigm in which the accuracy of computation results can be traded against, e.g., savings in energy, improvement in performance. In this extented abstract we investigate, by means of an example, the applicability of approximate operators (additions, in our case) on an adaptive feedback control loop. Our research vehicle is a autofocus controller that sets the focal distance of a lens such that a defined region of interest (ROI) in the ouput image is sharp. We study the energy consumption and the ROI sharpness error for various operation approximation degree. The results are encouraging indicating that for a 30% reduction on the energy consumed in the addition operations the degradation in the sharpness of only 2%. A 40% reduction on the energy consumed corresponds to a less than 10% degradation.

I. INTRODUCTION

Low power consumption is a crucial challenge in embedded devices that are battery powered or that need to harvest their energy. The approximate computing paradigm [START_REF] Trading | A survey of techniques for approximate computing[END_REF], [START_REF] Xu | Approximate computing: A survey[END_REF] aims to respond to this challenge by trading accuracy of computation against savings in energy, for algorithms that tolerate a bounded error in operations (e.g., addition, multiplication) or operands (e.g., registers, memory). Typical targets where this paradigm may bring significant benefits are signal processing, machine learning, multimedia, iterative algorithms.

In this work we investigate the trade-off between energy and output quality in an application comprising an adaptive feedback control. The use-case application is an autofocus system in charge of controling the focal distance of a lens such that a defined region of interest (ROI) in the ouput image is sharp. Hence, in our case the quality metric is ROI sharpness. The autofocus system includes a simple, adaptive integral controller and a Haar wavelet and an 1 norm to compute the sharpness. We compare two ways of employing approximate operations in the sharpness computation: (1) in the Haar wavelet and the 1 norm and (2) in the Haar wavelet. The practical experimentation platform is an Rasperry-Pi board and a Microelectromechanical (MEM) based lens.

II. AUTOFOCUS USE-CASE AND RESULTS

A. Target application

The lens autofocus system, as proposed in [START_REF] Zarudniev | Autofocus performance realization using automatic control approach[END_REF], consists of a control loop that aims to maximise a sharpness metric. Figure 1 briefly presents this control loop. At each control step, an image is taken, the region of insterest (ROI) is extracted and a sharpness metric, s, and its gradient are calculated. Based on the sharpness gradient the adaptive controller decides how to update its gain and computes the control signal, c, (a voltage in our case), so that an image with a different focal distance is taken on the next step. The process stops when the sharpness gradient is smaller than a given reference or a predefined number of steps is reached. The control signal belongs to a set of discrete values; for simplicity, in what follows we report it as normalised with respect to a maximum value.

s ← s + |hout|+ |vout| 768 * 2 i { 1 norm} end for return s
To evaluate the impact of approximate additions on the quality of application results, we define the relative sharpness error, rse, for an image as:

rse = s ref -s a s ref , (1)
where s a is the sharpness in the approximate case, and s ref is the reference sharpness. For a given image, Figure 2 presents the sharpness versus control signal plot for a real image example, and illustrates the values involved in the determination of the error metric. In the case that the operations are approximate, the control loop will converge towards a different value of the control signal, c a . As a result, the image sharpness will have a value denoted as s a . To define a maximum sharpness reference s ref , we take an intermediate step, because the output of the image sensor is inherently noisy. A sharpness courbe is interpolated using Bspline from a set of sharpness of images corresponding to all possible focal distances (i.e., values of control signals). The maximum sharpness point s ref is the maximum of this courve.

B. Energy and error model

We utilise a simple error model for the addition operations, as follows: (x + y) a = (x + y) e * (1 + ), where ∈ [-1, 1] represents the relative error of an approximate adder and the a and e indices denote an approximate and and exact operation, respectively. We consider that the energy consumption of a exact addition equals 1 unit, similar with [START_REF] Düben | Opportunities for energy efficient computing: a study of inexact general purpose processors for high-performance and big-data applications[END_REF]. An approximate operation typically consumes a fraction of this unit of energy, denoted with e a , e a < 1. We assume that follows a Laplace distribution, as empirically observed in previous work on modeling approximate adders [START_REF] Venkatesan | Macaco: Modeling and analysis of circuits for approximate computing[END_REF]. For a given e a we utilise the results of Kahng and Kang. [START_REF] Kahng | Accuracy-configurable adder for approximate arithmetic designs[END_REF] to determine the mean and scale of the relative error distribution for a given level of energy, e a . The Laplace distribution is utilised to inject errors in the sharpness computations. For a given number of approximate operations, n a and exact operations, n e , the total normalised energy is given by: E = na * ea+ne * 1 (na+ne)

C. Experimental results

The experimental platform used to acquire all images, embeds an imager, a lens and a Rasperry Pi board that implements the autofocus algorithm, as presented in Figure 3. We consider a ROI with 256x256 pixels, which corresponds to 17K addition operations necessary to compute the sharpness. We investigate two cases: (1) all additions, in the Haar wavelet and the 1 norm, are approximate, (2) additions in the Haar wavelet are approximate and the 1 norm is precise. The baseline is the precise sharpness computation using exact additions. Note that, due to noise in the images, the relative sharpness error of the baseline is not always zero. Figure 4 summarises the results, for several values of the energy level, e a . The results indicate that for a 30% reduction on the energy consumed in the addition operations the degradation in the sharpness is only 2%. A 40% reduction on the energy consumed corresponds to a less than 10% degradation.

III. CONCLUSION AND PERSPECTIVES

This work investigates the applicability of the approximate computing techniques on a lens autofocus system. The study indicates a significant energy gain potential for a small loss in final image sharpness.

It is worth noticing that feedback control algorithms rarely benefit from approximate operations because the errors introduce may render a controller instable. In this sense this work extends on the state-of-the-art by investigating the applicability of approximate operators on an adaptive feedback control loop. The particularity of this loop is that it takes decisions based on the output gradient and not directly on the output. Even if the output is imprecise, its gradient may still be in the correct direction, hence the loop has the potential to tolerate the approximations in the operators. A theorethical framework to reason about stability in the presence of approximate operators is and interesting research direction. Other limitations to be addressed in future work are: (1) the error probability vs. energy model is a compilation from literature, hence it might be unrealistic, and (2) the energy model is oversimplistic as it abstracts from the consumption on parts of a processor, such as, instruction decoding, memory access.

Fig. 1 .

 1 Fig. 1. Autofocus control loop Most of the execution time in the control loop is spent on the sharpness computation, hence our investigation focuses on this part of the application. The sharpness metric includes two main kernels: a Haar wavelet and a 1 norm. Most of the operation involved in the sharpness computation are additions. The algorithm below presents the details of the calculation. Require: imageROI, nRow, nCol, order {2D matrix with the ROI pixel values, number of rows and columns of ROI, Haar wavelet order} Ensure: s {the sharpness} s ← 0 hout ← imageROI vout ← imageROI for i in [1,order+1] do hout ← hout[:, 1 : nCol : 2] -hout[:, 0 : nCol -1 : 2] hout ← hout[1 : nRow : 2, :] + hout[0 : nRow -1 : 2, :] vout ← vout[:, 1 : nCol : 2] + vout[:, 0 : nCol -1 : 2] vout ← vout[1 : nRow : 2, :] -vout[0 : nRow -1 : 2, :]

Fig. 2 .

 2 Fig. 2. Error metric example

Fig. 3 .

 3 Fig. 3. Demonstration platform

Fig. 4 .

 4 Fig. 4. Energy vs sharpness (comparison between the two cases)

ACKNOWLEDGMENT

This work was partially supported by the French Agence Nationale de la Recherche, under Grant Agreement ANR-15-CE25-0015 (project ARTEFACT).