Fran De Aquino

The Gravitational Invisibility

Keywords: Invisibility, Gravitational Invisibility, Real and Imaginary Universes

The possible obtention of invisibility by means of a gravitational method is shown in this work. This method is based on a gravity control process patented on 2008 (BR Patent Number: PI0805046-5). It goes far beyond the known methods of invisibility and camouflage, which use the principles of light refraction to allow light to pass right through an object (metamaterials).

Introduction

An object that cannot be seen by the human eyes is in called state of invisibility. At this state, the object neither reflects, nor absorbs light, i.e., the light passes freely through it. Under this condition, we can say that the object is 100% transparent. In the Nature, there is no material 100% transparent.

The concept of invisibility includes others ranges of the electromagnetic spectrum, such as radio, infrared, ultraviolet, etc., since the object can be detected by instruments operating in the ranges of radio, infrared, ultraviolet, etc. Thus, the invisibility depends on the eyes of the observer and/or the instruments used to detect the object.

At the state of total invisibility, an object cannot be detected by any real observer or instrument, even making use of detectors, which operate in real ranges of radio, infrared, ultraviolet, etc.

Here we will show a method to make a real body totally invisibly. This method is based on a gravity control process patented on 2008 (BR Patent Number: PI0805046-5, July 31, 2008 [START_REF] De Aquino | Process and Device for Controlling the Locally the Gravitational Mass and the Gravity Acceleration[END_REF]). It goes far beyond the known methods of invisibility and camouflage, which use the principles of light refraction to allow light to pass right through an object (metamaterials) [2,3]. ( )

Theory

1 1 1 2 1 2 0 0 ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Δ + - = = c m p m m i i g χ
where is the rest inertial mass of the particle and 0 i m p Δ is the variation in the particle's kinetic momentum; is the speed of light.

c

In general, the momentum variation p Δ is expressed by

t F p Δ Δ =
where is the applied force during a time interval

F t Δ .
Note that there is no restriction concerning the nature of the force , i.e., it can be mechanical, electromagnetic, etc.

F

For example, we can look on the momentum variation p Δ as due to absorption or emission of electromagnetic energy. In this case, it was shown previously that the expression of χ can be expressed by means of the following expression [START_REF] De Aquino | Ultrafast Conversion of Graphite to Diamond in Gravitational Pressure Apparatus[END_REF]:

( ) 2 1 1 2 1 1 1 2 1 1 1 2 1 2 2 2 2 0 2 0 0 ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - = = ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - = = ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Δ + - = =

c

In the particular case of heterogeneous mixture of matter * , (powder, dust, clouds, air, smoke, heterogeneous plasmas † , etc), subjected to incident radiation or stationary electromagnetic fields, the expression of χ can be expressed by means of the following expression, which is derived from the above equation [START_REF] De Aquino | Ultrafast Conversion of Graphite to Diamond in Gravitational Pressure Apparatus[END_REF]: ; E is the instantaneous electric field applied on the body; 0 μ is the magnetic permeability of the free space;

( ) ( ) 3 1 4 1 2 1 1 1 2 1 2 1 2 6 2 2 0 4 4 4 2 6 4 2 2 2 0 2 2 2 3 0 ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - + - = = ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ - ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - = = f c E S S n n f n c f c E S S
is the oscillating frequency of the electric field and is the number of atoms per unit of volume in the body, which is given by f n ( ) . Consequently we can * From the macroscopic viewpoint, a heterogeneous mixture is a mixture that can be separated easily (sand, powder, dust, smoke, etc.). The opposite of a heterogeneous mixture is a homogeneous mixture (ferrite, concrete, rock, etc). † Heterogeneous plasma is a mixture of different ions, while Homogeneous plasma is composed of a single ion specie.

5 1 4 1 2 1 2 6 2 2 0 4 4 4 2 6 4 0 ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - + - = = f c E S S n n m m rms m m r i g ρ μ φ χ α
Also, it was shown that our Real Universe is contained in an Imaginary Universe; in such way that the real spacetime of the Real Universe is contained in the imaginary spacetime of the Imaginary Universe ‡ [START_REF] De Aquino | of the Relativistic Theory of Quantum Gravity[END_REF]. Thus, each action in the real spacetime corresponds to an equivalent action in the imaginary spacetime. This, means for example, that any momentum, r p r , generated in the real spacetime produces simultaneously an equivalent momentum, , in the imaginary spacetime and vice-versa. . Consequently, the photon generated in the imaginary spacetime will have equal frequency, and the same direction of the real photon (due to r im p p r r = ). Consequently, when an object is illuminated with real photons, it is also being illuminated with imaginary photons. Since there is imaginary mass associated to the real mass [4] § , then, the imaginary photons interact with the imaginary mass associated to real mass of the object, and can be reflected, absorbed or transmitted, such as occurs with the real photons when they incide on the real matter. Real photons in turn do not interact with imaginary ‡ The terms imaginary and real are borrowed from Mathematics (real and imaginary numbers) [START_REF] De Aquino | Beyond the Material Universe[END_REF]. § These new concepts are widely detailed and explained in the ref [START_REF] De Aquino | of the Relativistic Theory of Quantum Gravity[END_REF]. It is essential to study the contents of this reference to get a complete understanding of the matter here developed. matter. Consequently, they pass freely through the imaginary mass (See Fig. 1 (a)). Note that the photons can be of any range of the electromagnetic spectrum, i.e., radio, infrared, light, ultraviolet, etc.

The real light photons are detected by the retina of our eyes, and thus we see the object. If the gravitational mass, m g , of our body is reduced to a value between -0.159m i0 and + 0.159 m i0 , (m i0 is the rest inertial mass of the body), it becomes an imaginary body and realizes a transition to the Imaginary Universe [START_REF] De Aquino | of the Relativistic Theory of Quantum Gravity[END_REF], from where it still will can see objects, because its imaginary retina can to detect the imaginary light photons reflected from the imaginary mass associated to the real object (See Fig. 1 (b)).

Imagine then an observer inside a spacecraft, seeing for an object out of the spacecraft, through a glass window of the spacecraft. If the spacecraft and the observer are turned into imaginary bodies, then, despite the real photons (reflected from the object) no more interact with the retina of the observer, he will still continue seeing the object out of the spacecraft by means of the imaginary photons (associated to the real photons) that are reflected from the object (See Fig. 1 (b)). A second imaginary observer inside the spacecraft, seeing for the internal wall of the spacecraft does not see the real object out of the spacecraft, because the imaginary photons reflected from the body do not surpass the wall of the spacecraft (such as occurs in a real spacecraft with an real internal observer, i.e., the observer cannot see out of the spacecraft). On the other hand, a real observer out of the spacecraft does not see the spacecraft (See Fig. 1 (b)); because the real photons pass through the spacecraft without interact with it, and the imaginary photons reflected from the surface of the spacecraft are not detected by the retina of the real observer (these photons pass freely through it). However, a third imaginary observer positioned out of the spacecraft will see the spacecraft, because the imaginary photons will sensitize its imaginary retina. with the imaginary mass associated to the real mass, and can be reflected, absorbed or transmitted, such as occurs when real photons incide on the real matter. Real photons in turn do not interact with imaginary matter. Consequently, they pass freely through the imaginary mass. (b) The imaginary light photons reflected from the ball sensitize the retina of the observer 1, and then he can see the ball through the window. The observer 2 cannot see the ball because the real light photons do not interact with his retina, and the imaginary photons reflected from the ball do not reach it. The real observer (out of the spacecraft) cannot see the spacecraft because the imaginary light photons reflected from the spacecraft do not sensitize its retina, i.e., they pass freely through the eyes of the real observer, but they will sensitize the retina of the observer 3 (imaginary observer), and consequently he can see the spacecraft. In addition, when a human body becomes imaginary, he becomes invisible to any real observer, but he can see real objects because its eyes can detect the imaginary light photons reflected from real objects.

Real Observer

Imaginary Observers Real Photon Imaginary Photon

Real Body Imaginary Body

There are two ways to transform a real body into an imaginary body. Reducing directly its gravitational mass, m g , to a value between -0.159m i0 and + 0.159 m i0 or reducing the gravitational mass of a part of the body until it becomes negative, and the total gravitational mass of the body be reduced to a value inside the range above mentioned (See Fig. 2). It was shown in a previous paper that the decreasing of the gravitational mass can become relevant in the particular case of spinning ferromagnetic disks subjected to electromagnetic fields with extremely low frequencies (ELF) [7]. This means that a ferromagnetic disk, subjected to appropriated ELF radiation, and spinning with sufficient angular velocity inside the spacecraft can make strongly negative its gravitational mass, , in such way that the total gravitational mass of the spacecraft can be reduced to a value between -0.159m

(part g m
Note that this method is very efficient because there is no necessity of to alter directly the gravitational masses of the others parts of the spacecraft. Thus, the advantages of this method are evident. It also can be used in order to transform real human bodies into imaginary human bodies. For example, consider a person wearing a type of clothes similar to ninja clothes (See Fig. 3). The tissue of these clothes is similar to Metallic bubble wrap (See Fig. 4). It has 3 layers. Both the inner layer as the outer layer are metallic; between them there is a dielectric layer (bubble wrap). Inside the bubbles there is ionized air, which can be obtained by using an air ionizer ** . The ionization of the air is necessary in order to increase its electrical conductivity up to m S / 10 1 6 -× ≅ σ † † , which is an ideal value, as we shall see in the following.

From Electrodynamics we know that when an electromagnetic wave with frequency and velocity c incides on a material with relative permittivity

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ < < ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ air i i air air i i M M M M χ
The total volume of the ionized air inside the bubbles can be obtained by multiplying the total external surface area, , of the clothes for invisibility by the thickness of the bubbles, (Fig. 5). Thus, the total inertial mass of the ionized air, , is given by . It is important to note that the bubble with ionized air, such as described in this paper, it can also work as a Gravity Control Cell (GCC). A device widely mentioned in some of my previous works [START_REF] De Aquino | Gravity Control by means of Electromagnetic Field through Gas at Ultra-Low Pressure[END_REF][START_REF] De Aquino | Quantum Gravitational Shielding[END_REF][START_REF] Aquino | Improvements in the Design of the Gravitational Motor[END_REF][START_REF] De Aquino | Method for Obtaining Quantum Vacuum[END_REF][START_REF] De Aquino | A System to convert Gravitational Energy directly into Electrical Energy[END_REF].

  In a previous paper, I showed that gravitational mass, , and rest inertial mass, , are correlated by means of the following expression [

  the electromagnetic energy absorbed or emitted by the particle; is the index of refraction of the particle; W is speed of light.

  In the case of a photon, the momentum p is related to its energy E by means of the following expression:pc E =, where is the speed of light at the free space. Thus, when a photon is generated in the Real Universe with an energy

Fig. 1 -

 1 Fig.1 -The real-imaginary pairs of photons interacting with real and imaginary matter, respectively. (a) The imaginary photons interact

Fig. 2 -

 2 Fig.2 -Transforming a real spacecraft into an imaginary spacecraft. It is possible to transform a real spacecraft into an imaginary spacecraft by reducing the gravitational mass of a part of the spacecraft, m g(part) , until it becomes negative, and the total gravitational mass of the spacecraft be reduced to a value between -0.159m i0 and + 0.159 m i0 .

Fig. 3 -

 3 Fig.3 -Clothes for Gravitational Invisibility.

Fig. 4 -

 4 Fig.4 -Aluminum bubble warp.

)

  i0 and + 0.159 m i0 , transforming then the spacecraft into a imaginary spacecraft.

(

  Let us now apply this equation to the ionized air inside the bubbles in the metallic bubble wrap. Since the electrical conductivity of the ionized air is m of the free space). In this case, Eq. (6) reduces to For atmospheric air, at 1atm, 25°C, we can assume . The number of atoms of air (Nitrogen) per unit of volume, example, making the air passes through the plates of a capacitor subjected to a high voltage.† † The electrical conductivity of atmospheric air at 1 atm, 25°C is the cross-section area of one bubble of the metallic bubble wrap, whose diameter is α See Fig.5); is the oscillating electric field, with frequency , through the ionized air inside the bubbles of the metallic bubble wrap. total inertial mass of the ionized air and is the total inertial mass of the human body with the ninja clothes for invisibility.

α

  Fig.5 -Dimensions of the bubbles


Vladimir-Alexandru Paun
email: paun@ensta-paristech.fr

Bruno Monsuez
email: monsuez@ensta-paristech.fr

Adaptable and Precise Worst Case Execution Time Estimation Tool

Keywords: Hard Real-Time Systems, precision, safety, adaptability WCET, Abstract State Machine, Symbolic Execution

Real-time systems are everyware. When they are integrated into safety-critical systems, the verification of their properties becomes a crucial part. Besides the growth in complexity of the embedded systems, platforms are getting more and more heterogeneous. Being able to validate their nonfunctional properties is a complex and resource consuming task. One of the main reasons is that currently available solutions focus on delivering precise estimation through tools that are highly dependent on the underlying platform as in order to provide precise and safe results, the architecture of the system must be take into account. In this project we address these issues by developing a prototype that maintains a good level of precision while being adaptable to a variety of platforms by separating as much as possible the worst case execution time estimation stage from the hardware modeling aspects.

Introduction

With regard to the respect of the timing constraints, real-time systems are classified in two categories: hard real-time systems (the non respect of a deadline can lead to catastrophic consequences) and soft real-time systems (missing a deadline can cause performance degradation and material loss). We analyze hard real-time systems that need precise and safe determination of the worst case execution time (WCET) bounds that are crucial in the certification process. Tradi-[Copyright notice will appear here once 'preprint' option is removed.] tionally two approaches are used, namely dynamic and static methods [START_REF] Wilhelm | The Worst-Case Execution Time Problem Overview of Methods and Survey of Tools[END_REF], we only consider the latest as dynamic methods, in the traditional sens, fail to deliver safe estimations for modern platforms that contain, for example, pipelines or cache memories and tend to greatly underestimate the WCET.

In order to give a safe estimation of the WCET, all the interactions and reachable states of the system must be analyzed or over approximated, hence the need of an analysis that takes into account the exact underlying architecture. We choose to separate as much as possible the modeling part from the analysis part in order to achieve the flexibility needed to adapt to new hardware.

In our approach we start from the system's model and the binary that will be executed on the final platform. An extension of the Symbolic Execution (SE) [START_REF] Lundqvist | An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution[END_REF], the conjoint SE, will generate all the reachable states of the processor, under the supervision of a prediction module that will fusion identical and similar states in order to contain the state space explosion and give details regarding the global precision loss of the WCET estimation.

In the following we first take a look into the state of the art concerning timing analysis and we continue with the description of the high level architecture of our tool. Subsequently we take a closer look into the formal model used to simulate the hardware that gives us the edge in the adaptability of our tool followed by a presentation of the WCET estimation steps and the transformations needed to contain the combinatorial explosion.

Related works

Many of the available time analysis tools show a list of compatible hardware and present each new platform taken into account as a new feature. One of existing methods, OTAWA, introduced by Cass and Sainrat [START_REF] Cass | A framework for experimenting WCET computations[END_REF], differentiates itself by making a first step towards adaptability as it uses a parametrized model of a generic platform that can address a variety of architectures but nevertheless, the process is fairly difficult and the model lacks precision while it fails to capture the precise behavior of the platform. AbsInt, one of the leading WCET analyzers is also taking a step towards adaptability by apparently looking to use a SystemC description in order to generate an abstract model. The main issue is that the SystemC language has only recently come to be a standard therefore descriptions of older hardware (mainly used in hard real-time systems) are not common. To our knowledge non of the other WCET tools have embraced the adaptability paradigm.

The global architecture of the WCET estimation tool

The two main entries of the tool are the processor model and the program binary, as depicted in Figure 1. The processor is regarded as the union of it's components µP

= n i=0 C i
and modeled as a hierarchical timed abstract state machine, described further in the paper, that has the useful feature of enabling multiple definitions for a same component C i . A supervisor that we call the Oracle decides what abstraction level is best suited for the current context in order to optimize the precision to state explosion ratio. An external value analyzer is used to obtain information regarding the instruction order, their addresses and the control flow graph of the program. Symbolic execution is used to symbolically execute each instruction of the program, meaning that each variable has initially a symbolic value (as we generally do not posses exact information on it's value) that gets refined by accumulating all the informations and decisions taken during execution. One of the advantages of this method is that it manages to simulate the interactions inside the processor in detail, for example capturing by construction the timing anomalies [START_REF] Reineke | A vDefinition and Classification of Timing Anomalies[END_REF].

The SE generates all reachable states of the processor, meaning that we have to manage a rapidly increasing state space.

Our fusion stage consists in merging as much states as possible without affecting to much the precision of the estimation. We achieve this by using the prediction module that will first identify the states that are good candidates for merging and then estimate the impact of the fusion on the global analysis. After browsing and evaluating the processor's states, the time corresponding to the worst path is selected.

Timed Hierarchical Abstract State Machines 4.1 Abstract State Machine Formalism

The sequential ASM Thesis, introduced in [START_REF] Gurevich | Evolving Algebras[END_REF] proves the isomorphic modeling of any algorithm. The sequential ASM algorithm consists of a set of rules applied to states in a sequence of steps assimilated to a run.

Hierarchical Timed ASM

Possessing a precise and versatile model of the processor is very important. Nevertheless having access to an usable HDL code, is rarely the case for platforms used in hard realtime systems, that are fairly outdated, and even if it exists, their is no common, unified description language. Ideally we should use the description of the processor as an input and generate an usable model for the analysis. As the lack of availability and standardization makes the task impossible, the need to create a model for each platform is mandatory. This is one of the bottlenecks in the adaptability of current tools, and we consider that the modeling part should be therefore an separated straightforward engineering task that can be made on the fly and without disposing of precise knowledge with regard to the rest of the tool. Therefore we chose to use the abstract state machine, a method that bridges the gap between human understanding and formulation of real-world problems and the deployment of their algorithmic solutions, in our case, the modeling of the processor, that showed it's efficiency as a specification method in numerous practical applications (e.g. see [START_REF]ASM homepage[END_REF], [START_REF] Borger | Abstract State Machines: A Method for High-Level System Design and Analysis[END_REF]). Using a human readable and machine executable language makes the difference when it comes to speeding up the process of the hardware description. However some important features were not included in the original version of the ASMs [START_REF] Gurevich | Evolving Algebras[END_REF] like the timing aspects hence updates are consid-

Description of the ongoing development of a precise WCET estimation tool

2 2012/4/6 ered immediate. Ouimet et all. [START_REF] Ouimet | The Timed Abstract State Machine Language: Abstract State Machines for Real-Time System Engineering[END_REF] introduced the concept of durative actions by adding delays directly in the syntax; our approach is similar. In [START_REF] Slissenko | Simulation of Timed Abstract State Machines with Predicate Logic Model-Checking[END_REF] a prototype of a simulator for reactive timed ASMs that verifies the respect of requirements specifications. Besides the timing aspects we enrich the original model with hierarchical feature that enables us to give different definitions on several abstraction levels of the same processor component. The goal of hierarchical ASMs is to provide at any time during the analysis, the right level of abstraction in order to prevent the combinatorial explosion. We know that we do not always dispose of precise information during the analysis (e.g. data memory address, availability in the cache, etc.) therefore using the most precise description of the fetching mechanism, for example, would be useless, on the other hand, a less precise, more abstract, definition could help reduce the number of generated states.

The hierarchical definition of components integrates seamlessly into the ASM formalism. Basically, the oracle is an ASM module that imports all the needed function definitions and exports the needed functions or rules. Each hierarchical module is defined as a control state ASM (cf. [START_REF] Borger | Abstract State Machines: A Method for High-Level System Design and Analysis[END_REF]) using in it's condition the result from the oracle that decides which implementation is appropriate for the current context.

Conjoint Symbolic Execution

The use of SE to analyze the intra-processor interactions has been used with good results in [START_REF] Lundqvist | A WCET Analysis Method for Pipelined Microprocessors with Cache Memories[END_REF], however the method suffers from the lack of a precise hardware model and inaccurate merging strategies that lead to important overestimations. The basic SE consists in replacing the variables with symbolic values and extending the operations in order to take this into account. The interpretation of the assignment rule is straightforward. Let p(pc) be Q, p(x i ) be E i and p(α ← β) be the old p where the value of α is changed to β. A special treatment is applied to conditional instructions that use the pc to explore all the possible scenarios. The expressions conjoined in the pc are of form Q > 0 where Q is a polynomial over symbolic values. Let R be this expression we thus have three possible cases: we can determine from the pc that the condition is always true (pc ⊃ R and pc ⊃ ¬R), analogue for always false or we can not determine if the condition is true or false, pc ⊃ R and pc ⊃ ¬R, therefore the execution will continue along both branches, generating two new paths.

The first step of our conjoint SE deals with the program's CFG that is regarded as an input for the processor's model SE.

Smart State Fusion

One of the major drawbacks of the SE comes from its quality of generating every feasible path, that for a real-life industrial program generates a combinatorial explosion that is not obviously containable. What still remains challenging today is to handle this explosion while still remaining precise enough. This translates to finding a way of eliminating some of the states, and we choose the technique of states fusion that will try to generate an abstract state capable of capturing the respective states features, with regards to the goal, but remain as compact as possible. It has been proven in [START_REF] Benhamamouch | Computing worst case execution time (wcet) by symbolically executing a timeaccurate hardware model (extented version)[END_REF] that because of the finite number of states that a processor can have and because of the constrains generated by the execution contexts at a certain point we will have states that regardless of the different history, will generate identical or very similar new states. One major step in having precise fusions is to determine when to make them and what changes to apply. States can be of two types: identical, meaning that they have either all the elements that are the same, in this case we can suppose that an eventual fusion will not impact the precision of the analysis, or similar, some of the components are not the same so we proceed to another analysis to determine to which extent they are different. Therefore similar states can be strongly or weakly similar, meaning that the impact of the fusion will be acceptable or not. For the instant this estimation is done dynamically by our prediction module. Its goal is to evaluate the impact in the future of a fusion by unrolling the tree for several steps (generally equal to the pipeline depth), continuing the execution along the paths before and after fusion and comparing the result. Further details about this technique can be found in [START_REF] Benhamamouch | Computing worst case execution time (wcet) by symbolically executing a timeaccurate hardware model (extented version)[END_REF].

Conclusions

The world of embedded software is no longer integrating simple hardware/software therefore critical systems are becoming more and more difficult to prove and certify. The growth in complexity and variety increases the need of versatile analyze methods and adapted tools, that can easily and as costless as possible deal with a large panel of architectures. To this end we presented a novel approach that is able to respond to the evergrowing demands and to place itself into a real industrial context.

Figure 2 .Figure 3 .

 23 Figure 2. The oracle and the fetcher modules

Figure 4 . 5 .

 45 Figure 4. The Dynamic Fusion -snapshot of the Prediction Module


Vladimir-Alexandru Paun

Bruno Monsuez

Philippe Baufreton

On the Determinism of Multi-core Processors *

Keywords: 1998 ACM Subject Classification C.3 Special-Purpose and Application-Based Systems multi-core, determinism, hard-real time systems Digital Object Identifier 10.4230/OASIcs.FSFMA.2013.32

Hard real time systems are evolving in order to respond to the increasing demand in complex functionalities while taking advantage of newer hardware. Software development for safety critical systems has to comply with strict requirements that will facilitate the certification process. During this process, each part of the system is evaluated, requiring a certain level of assurance in order to provide confidence in the product. In particular there must be a level of confidence that the system behaves deterministically that may be based on functionality, resources and time. The success of system verification depends greatly on the capacity to determine its exact behavior. Nonetheless, hardware evolved in order to maximize the average computation power throughput with little to no regard to the deterministic aspect. Therefore modern architectural features of processors, like pipelines, cache memories and co-processors, make it hard to verify that all the needed properties are respected. The multi-core is furthermore difficult to analyze as the architecture employs mechanisms that compromise strong spatial and temporal partitioning when using shared resources without rigorous access control like shared caches or shared input/outputs. In this paper we identify and analyze the main sources of nondeterminism of the multi-cores with regard to the timing estimation. Precise determination of the worst case execution time is a challenging task even in single-core architectures. The problems are accentuated in the multi-core context mainly due to the resource sharing that can lead to highly complex interactions or to nondeterminism. Most of the units that generate behaviors that are hard to take into account can be deactivated, but it is not always easy to predict the impact on the performance. Nevertheless some of the features cannot be disabled (such as the out of order execution or some nondeterministic crossbar access policies) which leads to the invalidation of the respective platform for applications with high criticality level. We will address the problematic units, propose configuration or architecture guidelines and estimate their impact on the performance and determinism of the system.

Introduction

The use of complex computers in safety-critical systems creates the need to ensure that the embedded systems act in the way they are supposed to and that consequences of a malfunction are completely handled in a safe manner. Different standards apply according to the danger level of the system failure. These standards are presented in a collection of guidelines to follow in order to empower the system with a necessary confidence level. The respect of these recommendations determine the success of the certification process necessary for the software approval.

In this paper we focus on the determinism issues related to the worst-case execution time (WCET) with regards to the avionics standards of software certification that will guide the study of potential difficulties of embedding multi-cores. For the assurance of commercial avionics systems a document called "Software Considerations in Airborne Systems and Equipment Certification" is used. Bearing the name DO-178B [21] in the US and ED-12B in Europe, it describes the objectives of software life-cycle processes, process activities and the evidence of compliance required at different software levels. Safety standards like DO-178B and IEC-61508 [START_REF]Functional safety of electrical/electronic/programmable electronic safety-related systems[END_REF] explicitly call for the identification of functional and non-functional hazards and for software compliance with the relevant safety goals. In these standards three important non-functional software characteristics related to safety are mentioned: absence of run-time errors, execution time and memory consumption. The IEC-61508 has a great impact on the hardware selection as it requires the absence of unpredictable timing-related interferences which might affect real-time functions. This impacts directly the multi-cores as it must be ensured that no inherent timing interferences between cores take place. Nevertheless, this type of interferences are quite common and must be dealt with. Existing multi-core architectures employ mechanisms that compromise strong spatial and temporal partitioning when using shared resources without rigorous access control. Therefore we do not always dispose of precise information regarding the timing of some instructions in all circumstances due to their complex interactions with the memory and other dependencies.

The WCET estimation consists of two main steps, namely the control-flow analysis that determines the feasible paths in a program, and the processor-behavior analysis based on low-level analysis, hence the need to throughly determine the hardware behavior. The choice of a hardware platform is therefore greatly influenced by the visibility on the device internal structure as precise architectural implementation details are proprietary data often undisclosed.

The WCET estimation in multi-cores has different levels of difficulties. The first one is inherited from the single core world. Certain modern features in processors cannot be safely analyzed, nor disabled, making the certification of the processor impossible. Other features generate imprecision that will increase the safe margins needed to take in order to comply with the safety constraints, which impacts the feasibility. The second one is introduced by the multi-core architecture and can lead to the impossibility to determine the WCET. Problems from a core are not only translated, when integrated into the multi-cores, but amplified by the context of resource sharing.

State of the art works deal with this issue either by constraining some platforms, or by handling only a part of the issues and giving some new architectural workarounds that are custom tailored for some applications [START_REF] Yan | WCET analysis for multi-core processors with shared L2 instruction caches[END_REF][START_REF] Chattopadhyay | Modeling shared cache and bus in multicores for timing analysis[END_REF][START_REF] Chattopadhyay | Scalable and precise refinement of cache timing analysis via model checking[END_REF][START_REF] Kelter | Bus-aware multicore WCET analysis through TDMA offset bounds[END_REF][START_REF] Yan | Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches[END_REF][START_REF] Liang | Timing analysis of concurrent programs running on shared cache multi-cores[END_REF][START_REF] Hardy | Estimation of cache related migration delays for multi-core processors with shared instruction caches[END_REF][START_REF] Hardy | WCET analysis of multi-level non-inclusive set-associative instruction caches[END_REF][START_REF] Hardy | Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches[END_REF][START_REF] Yan | Hybrid multi-core architecture for boosting single-threaded performance[END_REF]. Another approach is to gather best practices for future multi-core architectures [START_REF] Christian | Predictability considerations in the design of multi-core embedded systems[END_REF] after acknowledging that analysing current multicore architectures is impossible in general. Nevertheless a unified and detailed approach is yet to be available.

Identifying which parts are impossible to analyze, or at what cost in precision, is key to even considering the choice of a certain multi-core processor. Our work is intended as a guideline in such choices, exposing the inherent problems of multi-cores and straitening the path towards a solution in the matter. The article is structured as follows: First we

F S F M A ' 1 3

explain inherent problems to the use of microprocessors in hard real-time systems. In Sec. 3 we describe the major units of the processor, identify problematic execution scenarios and estimate the impact on the predictability and we conclude in Sec. 4.

2

Inherent problems to the use of microprocessors in hard real-time systems

The hardware platform is a central point when analyzing a system. Therefore it is essential to dispose of a precise model of the processor in order to determine its effective behavior. The available information comes mainly in reference manuals and application notes that present the processor's architecture, how to interface it with the environment and how to configure its different function modes. Nevertheless, information present in the user manual is not intended for testing or verification purposes. Furthermore information relevant to the design method and the verification methodology are only briefly discussed, if not at all in these documents, mainly from the integrator point of view. Another issue is the questionable validity of the information presented in the reference document altogether as contradictory information is sometimes provided in different document.

The behavior of a microprocessor is challenging or even impossible to characterize. This is either due to the uncertainty of the effectively calculated result or the uncertainty on the actual time of the effective calculation. De facto, these two aspects are directly related to the notion of data availability. The main consequence of the difficulty in architectural optimization is an interdependence between the data and the instructions of a same task. In the context of multitask applications, an interdependence between various tasks coming from the commutation of the environments during the passing from one task to another, is introduced. In the case of multi-cores additional difficulties appear in the estimation of the WCET, like the issue of two competing processes if they share common architecture elements, notably, memory access controllers. Futhermore challenges are given by the exchange of data between the two applications being executed in both processors. Let us consider two tasks, one critical task being executed in one core, and a second critical task monitoring the calculations of the first task on the second core, it is necessary to ensure the data handled by the two tasks is coherent. Without adding at the application level advanced synchronization operation, it is impossible for the majority of current multi-core microprocessors to guarantee that both applications handle the same data. In fact, due to induced latencies, nothing prevents one of the two applications from handling data d t-1 present at t -1 instant while the other application handles the data d modified at t instant. In fact, one of the rare means to remove these uncertainties would be to strongly pair the monitoring application with the command application, by implanting communications between the two applications via semaphores.

Hardware considerations

Most of the available processors were not especially designed for the hard real-time systems. The multi-cores are no exception as their goal is to maximize the shared resource average utilization. Data communication and synchronization between the different units are optimized for maximum throughput of executed instructions. Therefore multiple execution paths can be taken depending on the execution history, the current state of units or even local choices based on random decisions. A natural way of analyzing the hardware components that influence the determinism would be to first look at those who give a local impact and proceed to components that have a global impact. One can also start by looking into units already present in single-cores, and proceed with units unique to the multi-cores. However, as shaped by this section, there is a thin frontier between the two as even classical, predictable units have a different impact when integrated in the multi-cores. Therefore the analysis of this components can not be solely based on the analysis of the same component in the single-core context.

Pipeline

Present in all modern processors, the pipeline was introduced in order to increase the average performance by ensuring that, whenever possible, an available hardware resource will be occupied. Nevertheless, different events can introduce pipeline stalls such as structural hazards, data hazards and control hazards.

Out of order execution (OoOE), a feature introduced in order to avoid pipeline stalls by decoupling the issue/dispatch and the execution/completion stages, allows execution not following the instructions program order. A fetched instruction will be executed when the input operands and needed resources are available with no regard to whether it is the next in order instruction. The interaction between the cache memory and instruction scheduling influences the precision of the timing estimation.

Pipeline impact on the predictability

The impact of the pipeline varies from local influence with local monotonic optimizations to global influences with timing anomalies that cancel the monotonicity and compositionality. The size of the pipeline has an influence on the predictability of the WCET. A wrong branch prediction causes n cycles penalty, where n is the pipeline depth. The pipeline depth can further influence the predictability potentially generating more hazards as more instructions are being treated at the same time. Besides intrinsic impacts on the predictability, the pipeline, in conjunction with other units, can lead to precision loss or nondeterminism. For example, in case of a L2 cache miss, the number of pipeline stages influences the memory access time [START_REF] Drach | Direct-mapped versus set-associative pipelined caches[END_REF]. Furthermore, in the shared resources context of multi-core sharing a common bus, the pipeline can lead to nondeterminism.

Branch Prediction Unit (BPU)

Through the BPU, processor attempts an early resolve of a branching instruction, before its time, by applying a strategy in order to anticipate the result. The BPU strategy can be either static or based on complex algorithms, un-deterministic in some cases. Based on this estimation, a speculative execution is initiated that will lead eventually to a significant time gain in the case the result is correct. The influence on the cache memory content is non negligible as a miss-prediction is not generally followed by a cache reorganization, therefore the cache configuration is polluted with information from the untaken path.

BPU impact on the predictability

The BPU can make incorrect branch predictions or incorrect branch target address lookup. It is systematically active and directly impacts the temporality of the instruction change. Furthermore, this unit relies on a set of data protection tables stored in tables. The impact is high because of the general unpredictable success rate of the early branching target resolution. It can be largely avoided in the case of statically resolved loops or branches that are not data

F S F M A ' 1 3

dependent. Tailoring the condition of the jump taking into account the branching strategy in order to help it succeed in the majority of cases is also a solution as long as the WCET analyzer can take it into account. In this case, most techniques of adding watermarks in the code with information that help or enable the prediction can be useful.

Floating Point Unit (FPU)

Floating point computation timing can also be hard to accurately estimate because of their implementation. A micro-pipelined unit takes advantage of consecutive instructions that can be pipelined. Units can have either a part of the FPU instructions pipelined or all of them. Therefore consecutive pipelined and non-pipelined instructions can cause stalls, making the timing difficult to compute especially in the case of the out of order execution.

Floating-point data formats and instruction set generally conform to the IEEE Standard for Binary Floating-point Arithmetic, ANSI/IEEE Standard 754-1985. However, the SPARC V8 architecture, for example, does not require that all aspects of the standard, such as gradual underflow, be implemented in hardware [START_REF]SPARC V8 architecture manual[END_REF]. This can be a problem if precise information about the implementation is not given. One of its implementations, the GR712RC/LEON3 does not provide sufficient information on this matter and precise timings in case of this exception could prove difficult to estimate. Similarly the ARM Cortex A9 architecture manual, does not provide precise timing of all instructions. This is mainly due to the unpredictable timing behavior at the instruction level generated by the unit's structure itself and memory system interactions [32].

FPU impact on the predictability

The impact of the FPU depends on its implementation. Instructions can take either a single cycle to execute or several cycles but they can also be pipelined. A combination of either way in parallel is also possible. In conjunction with the instruction rescheduling and thus with the change of data, cascade effects can occur and lead to pathological effects like it can be seen in some PowerPC architectures.

Level 1 Cache

Memories for instructions and data are implemented in order to make the most common case fast, benefiting from a program's spatial locality and temporal locality. Not taking this fact into account in the WCET estimation gives highly pessimistic timing estimations. Cache memory is usually organized in different levels, some local to the core and others situated outside the core. Different cache replacement strategies must be implemented in order to optimize the performance because a strategy that can fit all the possible cases is impossible to find. Therefore the average case performance is optimized. Commonly used strategies are LRU, pseudo LRU, FIFO or round robin and MRU each having a different impact on the predictability of the system. The analysis of the Level 1 cache must be made in conjunction with the other units and is discussed within the timing anomalies in the following.

Impact on the predictability

Worst-case analysis on cache memories is a challenging problem, mainly because they are conceived in order to maximize the average performance. Achieving good results for data cache analysis, for example, is still an open problem, as they are difficult to statically analyze. An approach that enables time-predictable caching, is to lock cache blocks. Combining cache locking with cache partitioning for multiple tasks in the case of task preemption can improve the predictability in some cases [START_REF] Vera | Data caches in multitasking hard real-time systems[END_REF]. Unknown abstract cache states during the analysis generate loose WCET bounds. For example, unified cache for instruction and data can break down all the information on abstract cache states. After accessing n unknown addresses in an n-way set-associative cache all the cache lines will be unclassified in the analysis. Therefore, separation between the instruction and data cache memories should be chosen whenever possible (the problem still holds for shared caches and is discussed in the Level 2 cache section). For this reason Harvard architectures, with physically separate signal pathways for instructions and data, should be privileged in despite of the von Neumann architecture. Context switch or cache misses it can lead to a relatively high global impact due to timing anomalies or Translation Lookaside Buffer (TLB) strategies. In order to improve the performances of the cache memory, instruction and data locality could be increased using compiler techniques for example (code reposition, loop permutation, tiling [START_REF] Wolf | A data locality optimizing algorithm[END_REF] etc.). When performing the WCET analysis, the most problematic features to analyze are the replacement policies for set-associative caches [START_REF] Heckmann | The influence of processor architecture on the design and the results of WCET tools[END_REF]. Pseudo-round-robin and the 4-way associative cache is also a difficult combination in the Motorola ColdFire 5307 [START_REF] Schoeberl | Time-predictable cache organization[END_REF]. In order to ensure the time-predictability of processors, locally deterministic update strategies for caches should be used. According to [START_REF] Reineke | Timing predictability of cache replacement policies[END_REF] the LRU strategy performs best in terms of predictability, far ahead pseudo-LRU and FIFO.

Scratchpad

Scratchpad memories (SPMs) are used to guarantee a unit can work without main memory contention in a system employing multiple processors. As the memory access latencies are predictable, scratchpad memories have become popular for real-time embedded systems. However, the difficulty of allocating code/data to scratchpad memory lies now with the compiler. Scratchpad memory works like a local store and act like "software caches" therefore the strategy is implemented in software and the interactions in the global hardware must be analysed. Timing anomalies with regard to the replacement strategy should be integrated into the hardware model. The most convenient approach to manage the SPM is using static allocation [18] but dynamic SPM allocation is more efficient (it can use profile-based optimization but multiple strategies exist). Analyzing dynamic strategies is challenging, especially the software implemented ones that give optimal allocation for the average execution time. Some WCET-centric techniques exist but they do not handle all architectures.

Memory Management Unit (MMU) and Translation Lookaside Buffer

The TLB is a cache that MMU use to improve virtual addresses translation speeds. The time needed to determine the physical address depends on the number of performed operations. TLB time access is variable. In order to enforce the predictability, the MMU can be deactivated (however the performance loss is significant) or by reducing the size and thus complexity of the TLB (the TLB main entries can be blocked in order to ensure their persistence). A solution is to increase the TLB size so that we only have hits but we still have the problem of an error in the translation that is detected late and takes an undefined (even if still reasonable) time to be corrected. Typical user manuals [START_REF] Aeroflex | UT699 LEON 3FT/SPARCTM V8 MicroProcessor, Functional Manual[END_REF] give upper bounds in the TLB miss case. Timing anomalies invalidate the monotonicity assumption in the general case [START_REF] Wenzel | Principles of timing anomalies in superscalar processors[END_REF], which means that we cannot directly use the upper-bound information as the worst-case scenario. Therefore, without precise information on the exact behavior all F S F M A ' 1 3

possible cases must analyzed, leading to a potential state space explosion. In order to reduce the potential temporal variability, the MMU should be disabled. Nevertheless due to the consequences on the global performances it is not recommendable. In general, virtual memory raises predictability issues at two levels. First at the level of address translation that provides mapping between virtual to physical pages requires a TLB lookup. If the mapping is absent from the TLB a page table lookup is performed. The duration of address translation is hard-to-predict, because not all mappings can be stored in the limited capacity of the TLB or because the TLB might be shared between concurrent processes. Second at the level of paging activity as knowing whether or not a reference to a virtual page will result in a page fault. This is hard to predict because physical memory is shared between concurrent processes.

Impact on the predictability

The virtual addressing and tasks using the shared cache the MMU has a global impact. In the case of multi-cores it is problematic to ensure the micro-TLB coherency. Choosing to handle the TLBs separately introduces new problems of guaranty.

BUS

As competition for resources grows, the natural solution was to use techniques that enable the access from master to slave, and utilization of shared resources in general. Through the use of switching mechanism, permission is granted to one master or the other, which introduces the need of a bus arbiter. Therefore a controller is usually implemented following different strategies that are more or less straightforward. The first difficulty comes from the implementation of the aforementioned strategies. In the case of multi-cores, the resolve of access conflicts is not always deterministic. Therefore at a given processor execution step, a strongly dataflow dependent transition can be made with no way of determine which of the competing units will have gain access to the shared resources. This behavior, otherwise seen as random, at possibly every program point makes it impossible for the analysis to converge to a useful result.

In the following, we will refer to the AMBA AHB bus protocol, an open standard widely used that give a good case study enabling us to pin-point more general advantages and disadvantages of interconnection protocols. Some of the features it provides, are the following: split transactions, several bus masters, burst transfers, pipelined operations and single-cycle bus master handover. The bus arbiter ensures that only one bus master at a time is allowed to initiate data transfers. The arbiter also receives requests from the slaves that wish to complete SPLIT transfers [START_REF] Arm | AMBA Specification[END_REF].

Preventing starvation

The arbitration algorithm between the channels can ensure that if the current owner requests the interface again it will always acquire it. The starvation problems are avoided in the LEON 3FT implementation of the AMBA AHB since the DMA engines always deassert their requests between accesses [START_REF] Gaisler | GR712RC -Dual-Core LEON3FT SPARC V8 Processor, User's Manual[END_REF].

Preventing deadlocks

The SPLIT and RETRY transfer responses can both produce deadlocks. The deadlock can occur when different masters try to access a slave that issues SPLIT and RETRY responses in a way that the slave is unable to deal with. If a slave issues a RETRY response only one master must access it at a time. More importantly, this constraint is not enforced by the AMBA AHB protocol and should be ensured by the system architecture. According to the GR712RC manual, cache snooping should always be enabled in SMP systems to maintain data cache coherency between the processors [START_REF] Gaisler | GR712RC -Dual-Core LEON3FT SPARC V8 Processor, User's Manual[END_REF].

On master data concurrency

The bus arbiter of the AMBA AHA can manage up to 16 bus masters. It grants bus access according to the master's priority. The signals used are: HBUSREQx, HLOCKx, HGRANTx, HMASTER[3:0], HMASTLOCK and HSPLIT[15:0] as described in [START_REF] Arm | AMBA Specification[END_REF]. When a master is granted access, the HGRANTx signal is generated by the arbiter that indicates the appropriate master is currently the highest priority master requesting the bus. After the current transfer completes, the HREADY signal is HIGH and the arbiter will change the HMASTER[0:3] signal to indicate the bus master number. The ownership of the data bus is delayed from the ownership of the address bus. When the HREADY signal is HIGH, the master that owns the address bus will continue to own the address bus until its transfer will be completed. Several problems can occur from this behavior.

(a) When the master is in burst mode, performing bursts of undefined length, it should continue to assert the request until it has started the last transfer. A problem occurs if the arbiter cannot predict when to change the arbitration at the end of an undefined length burst, leading to the impossibility to accurately determine the timing of the transfer. This is what happens in our case study also. (b) A different behavior can lead to a data inconsistency. Using a central multiplexer, each potential master present on the bus can drive out the address of the transfer immediately without having to wait to be granted the bus.

Let HADDR M1 = addr 1 at clk 1 and HADDR M1 = addr 2 at clk 2 and the first master, M 1 be granted master at clk 1 . If HADDR M2 = addr 1 at clk 2 , the data at addr 1 is still unmodified but it will be as M 1 still owns the data bus which leads to data access consistency conflict at addr 1 . The time needed to resolving such a conflict is hard to estimate. A typical example is the case of sharing un-partitioned memory. In order to avoid this case, a strong coupling is recommended between the monitoring application and the command application, by implementing the communication though semaphores. (c) A case where the timing is difficult to compute is when both M 1 and M 2 drive out the same addr 1 on the same slave, M 1 is granted ownership of the bus and then it is stalled by the arbiter that grants the bus ownership to M 2 . If M 2 needs to access addr 1 we cannot precisely determine the time when M 2 will finish its action. For example, this can occur in shared un-partitioned or partitioned memory.

Impact on the predictability

The bus and its arbitration strategy are at the core of the predictability and determinism issues. Because the main role is to grant access to different participants to the shared resources, certain properties must be ensured (fairness, deadlocks prevention) while still being able to ensure good average performances and timing predictability. Therefore when choosing a particular architecture for the hard real-time systems, certain bus architectures and arbitration algorithms should be privileged. Most of the multi-core architectures implement round-robin-like arbiters which allows considering an upper bound on the latency of the access to the shared resources. In [START_REF] Paolieri | Hardware support for WCET analysis of hard real-time multicore systems[END_REF] a round-robin-like bus arbiter to the shared memory

F S F M A ' 1 3
hierarchy in a multi-core architecture is proposed that facilitates the systems predictability. The round robin arbiter can avoid the bus starvation. Nevertheless, the maximum length of a burst for each peripheral connected to the bus influences the maximum delay induced by bus contention. This may lead to high maximum delay bounds and may not be enough to provide firm real time guarantees for heavily loaded systems. Furthermore, having variable burst lengths, combined with the ability to pause them (split transfers), influences the predictability of the WCET. Bus contention can be avoided by using the TDMA bus arbitration with the cost of wasting bus band when the bus load is low. By manipulating the TDMA time slots, the maximum delay bound on transactions is controllable by the designer.

Direct Memory Access (DMA)

DMA allows access to the system memory independently from the CPU. Therefore the processor can proceed with its computations while waiting for relatively slow input/output data transfer. In the multi-core case, DMA is also used for intra-chip data transfer.

Error handling

The DMA controller does not generally detect deadlocks in its communication channels, so it is up to the system to manually abort the DMA transfer. The DMA unit can be disabled not without a strong impact on the performances of certain class of applications.

Level 2 cache

Level 2 cache memory can be either private to each core or shared among cores. Data hazard is one of the factors that become even more prominent in the case of multi-cores because of memory sharing, even though already present in the non-shared L1 memory. Moreover, timing anomalies render the result hard to predict like in the case when a cache miss from a core can reconfigure the memory in a state that is, timing wise, beneficial to the other. This also applies in other cache related scenarios. The problems that can occur in the analysis of the interactions with the pipeline are detailed in the timing anomalies part.

Level 2 cache impact on the predictability

The impact of the shared cache is high and global and gets amplified in the context switch case.

Modeling the behavior of shared caches between cores is practically impossible because of the possible interactions between concurrent threads running on different cores [START_REF] Schoeberl | Time-predictable cache organization[END_REF]. When using a shared cache with parallel programs running on the multi-core processor, a cache-coherency mechanism must be implemented. The WCET analysis of such systems must calculate the worst-case delay caused by maintaining the cache coherence between different cores. Furthermore, resource contention and inter-thread conflicts among the program threads should be considered. Under the assumption that the bus strategy can be statically analyzed, the second level of cache can be made predictable by partitioning the L2 cache for each core [START_REF] Schoeberl | Data cache organization for accurate timing analysis[END_REF].

Timing Anomalies

Timing anomalies inside a given core influence the WCET estimation of integrating multicores in the case of shard memory because of the tight coupling of its internal units and the shared resources. Therefore we cannot ignore the WCET estimation problems of single cores as they are translated into the multi-core case also.

Example of timing anomalies in multi-cores A timing anomaly occurs when a local worst case contributes to the global favorable case. In the case of multi-core, such an example is a cache miss on one core that generates a series of cache hits on the other and vice versa. An example of each of these timing anomalies is given. The architectural setup is configured of two cores with private L1 cache memory but shared L2 cache memory (instruction and data). a A cache miss on one core can generate an overall improvement of the global WCET.

Let l be the cache line that will replace the obsolete line in the cache according to the implemented strategy. If l contains information that will benefit the second core then it can generate several cache hits that were not predicted. Furthermore, this line will be promoted in the priority hierarchy and could furthermore avoid future misses of the first core. b A cache hit on the first core generates the persistence of a cache line in the disadvantage of another that will be replaced after a future cache miss. If the replaced cache line would have generated several cache hits on the second core, the overall timing performance is affected. A first core's cache hit followed by a cache miss is worse than a first core's cache miss followed by a cache miss. c Timing amplification example as a generalization of b) A series of cache hits on the first core with a higher frequency, then the cache accesses of the second core make that every cache miss of the first core lead to the elimination of the second core's cached lines and a great amount of cache misses.

Timing anomalies remarks

As previously stated, several types of timing anomalies exist. Some are inherent to instruction execution order and are generally caused by greedy scheduler that will change the instruction execution order causing inversion or amplification of the execution time difference. Others are caused by parallel decomposition and divide et impera approaches to WCET estimations.

As the first ones cannot be avoided, the others may prove essential for the possibility to construct an efficient processor behaviour analysis that does not need to search the whole state space for the whole program at once. The timing anomalies determine three infeasibility criterions in the following. Criterion a) Let p be the processor architecture model, we say that the estimation of the WCET or more generally the processor behaviour analysis cannot be completed on behalf of the parallel decomposition (P D(p)) if there is no other scalable method that can do the analysis of p without the P D(p). In other words, not applying parallel decomposition can affect the scalability and applicability of the estimation method. We proceed by questioning the safeness and efficiency on dealing with parallel timing anomalies. [START_REF] Kirner | Precise worst-case execution time analysis for processors with timing anomalies[END_REF] formalizes the different types of timing anomalies and presents cases when the parallel timing anomalies can lead to the underestimation of the WCET with parallel composition. Criterion b) The use of parallel decomposition in the processor behaviour analysis leads to the underestimation of the WCET in the case of coupled parallel timing anomalies. This point can be referred to in order to decide the use of parallel decomposition. In [START_REF] Kadlec | Avoiding timing anomalies using code transformations[END_REF] a solution to take into account timing anomalies in general is described. The method uses compilation techniques and modifies the binary by instruction injection in order to avoid timing anomalies. The main idea is to interfere with the prefetch stage and ensure that we start with an empty or flushed prefetch window hence there is never an excess

F S F M A ' 1 3

instruction waiting to be executed. It can be seen as a compile time method to disable the instruction prefetch in the case where all the slots of the instruction prefetch queue are filled with NOPs. The reference also provides estimation of the overhead when using this method as ranging between 33% and 300%. This leads us to another infeasibility criterion that is related to the maximum overhead allowed for the target platform. Criterion c) Let Ot(p) be the upper-bound of the overhead on a target platform and Op(p) be the overhead of filling prefetch slots with NOPs. If Op(p) > Ot(p) then the analysis does not pass the feasibility test.

Conclusion

Software verification and quality assurance process of hard real-time systems in general are of great importance. Non-functional properties, such as timing, are highly dependent on the underlying hardware platform. Nevertheless, there is a rising demand to integrate more complex processors, such as the multi-cores, even though many problems are yet to be solved in single-cores. Powerful industrial WCET estimation tools available today can do nothing against the lack of information regarding the exact behavior of the platform or the nondeterministic behavior of certain units. Therefore the choice of the processor is crucial in ensuring the success of the system verification.

We have presented the behavior of several units that pose problems concerning the WCET estimation, found either in multi-cores or single-cores. Each unit description is followed by the problematic behavior and the remarks regarding its impact on the predictability. The results can be used to invalidate certain units or architectures and also as a guideline for further analysis.

Table 1

 1 Architectural impact on the determinism.

	Unit	Problems	/	Problem	Solutions	Impact
		Failure mode		fre-		Level
					quency
	TLB	TLB	misses	M/ L	Increase the TLB size	M
		times are hard
		to predict
	TLB	TLB error		L	None => disable	M/H
	MMU	The time to ac-	M	Depends on the availability of the be-	H
		cess the tables		havioural model and corresponding tim-
		can take several		ings. Disabling the MMU will only af-
		cycles				fect performances if we use its features.
						This means, flat address mapping, no
						memory protection in the case a pro-
						cess reads/writes the address space of
						another process and not least, when
						performing a context switch there is no
						longer possible to identify the cached
						lines of a certain process.
	Scratch-	Application con-		Analysing dynamic strategies is not an	M
	pad	trolled -> hard		easy task, especially when being soft-
		to estimate the		ware implemented that give optimal al-
		timings				location for the average execution time.
						Some WCET-centric techniques exist
						but they do not handle all architectures.
	L1 cache	Timing anom-	H	Construct complex, accurate processor	H
		alies				model
	L2 cache	Timing anom-	H	Deactivate	H
		alies

Table 1 -continued from previous page

 1

	Unit	Problems	/	Problem	Solutions	Impact
		Failure mode		fre-		Level
					quency
	L2 cache	Data conflicts		M	Partition (core access separation) Par-	H
						tial solution by considering inter-thread
						instruction conflicts [30] Only solutions
						for instruction caches in some configura-
						tions are presented in [11]. [6] Addresses
						only instruction caches with no code
						sharing, LRU strategy, no data -instruc-
						tion memory interference, without tim-
						ing anomalies, so a very restricted en-
						vironment. [7] Deals with inter-thread
						interferences but in a restricted archi-
						tecture. No details are given concerning
						the shared resources granting policy or
						about the BUS context.
	L2 cache	Unknown beha-	L	Deactivate	H
		viour induced by
		the arbiter
	L3 cache	Timing anom-	H	Partition	M/H
		alies
	L3 cache	Data conflicts		M/L	Deactivate	M/H
	BUS	Arbitration,		H	None for the general case In [6] a very	H
		timing	anom-		restricted "BUS" is analysed with fully
		alies, memory		separated code and data accesses and no
		interference			inter-process communication through
						shared memory and TDMA based static
						scheduling where a fixed length bus slot
						is allocated to each core in a round-
						robin fashion.
	Arbiter	Nondeterministic		None	H
	Arbiter	Starvation			Software supervision, but the risk of	H
						using it is even higher. DMA engines
						should always deassert their requests
						between accesses in order to prevent
						starvation.
	Arbiter	Deadlocks				Prevent by careful hardware integration	H
						of the bus arbiter protocol. Can rarely
						be disregarded by construction.
	Pipeline	Timing anom-	H	Construct complex, accurate processor	H
		alies				model. A solution to take into account
						all the timing anomalies (that might
						prove efficient in the multi-core case) is
						presented in [20].
	FPU	High complexity		Construct complex, accurate processor	M/L
						model
							F S F M A ' 1 3

Table 1 -continued from previous page

 1

	Unit	Problems	/	Problem	Solutions	Impact
		Failure mode		fre-	Level
						quency
	FPU	Mixes		multi-		None	M/H
		cycle	instruc-
		tions (for which
		timing	estim-
		ation is not
		always possible)
		and single cycle
		instructions
	FPU	Can	generate		Must analyse the fault tolerant mech-	M/H
		computational			anism. If the behaviour is taken into
		errors. Timing		account at each step, might prove very
		of	exception		costly.
		catching is hard
		to	precisely
		determine
	ALU	Can	generate	L	Construct complex, accurate processor	M/L
		computational			model taking into account the fault tol-
		errors.					erance.
	BPU	In the strategy	M	Construct complex, accurate processor	H
		is fixed and the		model
		prediction	is
		wrong, the time
		penalty is very
		important.
	BPU	If the prediction	L	None	H
		strategy is not
		fixed, it can be
		very difficult to
		model or even
		impossible if ran-
		domness is used.

This work was supported by SAFRAN Sagem.


Vladimir-Alexandru Paun
email: paun@ensta-paristech.fr

Bruno Monsuez
email: monsuez@ensta-paristech.fr

Philippe Baufreton
email: philippe.baufreton@sagem.com

Hierarchical Timed Symbolic Abstract State Machines for precise WCET estimation

Abstract-The Abstract State Machines have been around for a while, earning their place in the embedded system world. Their formal background makes them suited for proofs, their refinement design method eases the system engineering and their apparent simplicity steepens the end user's learning curve. The numerous extensions that followed have adapted the ASMs to most of the real-time system needs. Our aim is to provide a safe, precise and adaptable worst-case execution time (WCET) estimation for processors featuring modern components. The safety property implies that among all the possible processor states, generated by the binary for all possible inputs, the ones that cause the maximal execution time must be considered. However, complex architectural components, designed to speedup the average case, make it impossible to infer local timing decisions to the global systems as the monotony is broken by the timing anomalies. Therefore, a large number of states must be analysed, generating a combinatorial explosion. Our approach starts with a value analysis of the binary code performed by abstract interpretation. The inherent imprecision of its results is taken into account by the initially concrete abstract state machine processor model. Through the use of an internal oracle, it can dynamically adapt to the lack or imprecision of information by choosing a different hierarchy level for all the impacted components. This kind of execution optimises the granularity of the run based on several strategies. State merging is also used, in order to further counter the state space explosion, in the detriment of precision. The merging is based on identified similar states through the use of equivalence classes. This also offers a leverage on the tradeoff between the precision and scalability of the analysis. Time, different abstraction levels of the processor during the same run and symbolic execution are directly added in the ASM model, as opposed to other approaches. This provides us with the needed architectural adaptability and full control over the main target of the analysis: precise WCET estimation. Taking into account a new processor becomes an engineering task as a new model for the processor is given in our extension of the ASM, with little syntactical differences. This in made possible by the seamless integration of the WCET estimation alongside the ASM semantics, which must not be changed whenever a new platform is considered.

I. INTRODUCTION

In order to safely and precisely estimate the WCET of a processor we need a versatile model that can take into account all the possible component interaction and offer the means to confine and control the inherent state space explosion of exploring all the execution scenarios. Abstract State Machines (ASMs) have been used with success in processor modelling and verification [START_REF] Huggins | Specification and Verification of Pipelining in the ARM2 RISC Microprocessor[END_REF], and proved in our case to ne the best candidate to describe the underlying architecture for worstcase execution time estimation. Despite the formal background which makes it suited for proofs, the ASM model can be seen as a simple language and used accordingly with a minimum time to take in hand.

II. ABSTRACT STATE MACHINES

A. Timed ASM

The addition of time to the ASMs is not new and is present in different shapes. Timed ASM with instantaneous actions were first introduced in [START_REF] Gurevich | The railroad crossing problem: An experiment with instantaneous actions and immediate reactions[END_REF]. Both paradigms are further developed in [START_REF] Beauquier | A First Order Logic for Specification of Timed Algorithms: Basic Properties and a Decidable Class[END_REF] and [START_REF] Ouimet | The Timed Abstract State Machine Language: Abstract State Machines for Real-Time System Engineering[END_REF] with semantics oriented on verification. The approach presented in this work incorporates concepts from previous approaches from the ASM community however it represents the time in the simplest useful manner, close to the basic ASM but on the other hand adapted to generate runs that can reduce the number of processed information. A complete formal definition of the new model is available, therefore the verification capabilities of the ASMs are preserved. One of the first step to counter the state space explosion is to enable a time-accurate model for the processor, by allowing the step of the run to change in order to make a transition directly to a different new state. Timed ASM were also designed in order to conform with the set of axioms defined in [START_REF] Graf | Time in State Machines[END_REF] like global tine, srict time progress along causal chains, absence of Zeno computations, global urgency, etc.

B. Hierarchical ASM

Precise WCET estimation is dependent on the precision of the hardware model. However generating all the exact states of the processor at every step of the run triggers a state-space explosion. We introduce the concept of dynamic choice of the refinement granularity in what we call Hierarchical ASMs. Therefore, the model itself, is able to chose on the fly the appropriate abstraction level for a given rule among several, user-defined, definitions. This can be particularly useful in the case of a processor design as the precision on the values of manipulated data, given by a value analyser for example, is not always on pair with the level of detail of the processor model. The main idea is to adapt the level of abstraction of the processor description to the precision given by the value analysis in order to master or reduce the state-space explosion inherent to the WCET analysis. The definition of the ASMs is modified in order to allow not only a single rule definition for a rule name, but multiple, chosen according to the oracle among a list associated to each rule. A rule name assignment for an ASM state is a function that assigns to each rule name, a rule definition taking into account the choices of the Oracle and the critical locations. Choosing a certain definition for a rule name may imply also the automatic choice for other rules, explained by the notion of critical locations that we introduced for rules that use other rules locations. When conceiving the HTASM execution, we must choose the way we deal with the update sets associated with the execution trace. We need to be able to come back from an abstract state to a more concrete one. This means that the abstract run will potentially cover more concrete executions. In order to be able to resume to a concrete state we must be able to reconstruct the exact definition of the store equivalent to a particular concrete execution. In order to achieve this we can associate update sets to a certain rule name definition and collect them into an update bag that will not modify the general superuniverse but only allow us to recreate the exact state corresponding to the concrete state. In this way, ASMs can naturally deal with multiple parallel executions.

C. The Oracle

Whenever multiple definitions for a rule name are available, the Oracle is in charge with choosing the most adapted, according to different strategies. For example, if a rule definition depends on locations that are unknown, a more abstract version of that component is selected, that either no longer depends on those locations or allies to a whole set of values for those locations. The Oracle can also be trained, based on dynamic predictions for example it will try to minimise the state numbers based on previous success correlated to active locations and their values.

D. Symbolic ASM

Symbolic execution (SE) has already been used successfully in WCET estimation. Our analysis generates all the reachable states of the processor under all the reachable states of the program by doing a conjoint symbolic execution of the processor model and the binary. We integrated the SE directly into the ASMs, modifying the run in order to take into account symbolic values (completely unknown or baring information from the value analysis), from an additional universe, and adding the interpretation of symbolic terms.

E. State Merging

An instruction needs and generates a certain context in order to execute on a processor. The conjunction of this contexts generate similar processor states for different execution histories, [START_REF] Benhamamouch | Computing worst case execution time ( WCET ) by Symbolically Executing a time-accurate Hardware Model[END_REF]. Therefore the processor will find itself in similar states. This allows us to create equivalence classes for the generated states, differentiated by the notion of a distance that takes advantage of the formal definition of the processor model. Therefore, the search for merging state candidates is greatly improved with every new defined class. For example we can have identical states, where all the location values and rule definitions are the same or similar states. The decision to merge identical states is take automatically. On the other hand, similar states must be further analysed in order to decide if they should be merged. At this moment the dynamic prediction module takes over and compares the results of the execution before and after the state merge in order to make the choice. This module has another purpose that is to backtrack on the path that led to identical states in order to identify other potentially similar states.

III. USE CASES

The ability to estimate the impact of state merging on the resulting WCET is important to give an idea about its inherent over-approximation. Our analysis allows the control of the state merging threshold which enables the user to decide whether a precise but long and resource consuming estimation or a less precise but faster one should be performed. Having the choice can be particularly handy, as quick product cycles influence the development process, meaning code modifications take place more often with minor changes. However, in the general case, a safe WCET estimation implies a complete system WCET analysis, which may lead to delays for the new interruptive, agile development process. Therefore a faster and less precise analysis can be useful, especially that in early development stages, the system in conceived in order to have a higher temporal budget reserves in order to allow later evolutions.

IV. CONCLUSIONS

We have presented the structure of our tool that estimates the WCET with a custom precision. Thanks to the conjoint symbolic execution, all the reachable states of the processor, running the binary, are generated. The possibility to make delayed transition is presented as a support for abstracting the processor components in order to achieve a more compact simulation. We have also introduced a model that can dynamically refine the components of the processor, preparing a framework where run-time abstraction can be made in both ways between the concrete and the more abstract definition. In order to further reduce the state space explosion, merging is used through the dynamic prediction model. The tool is currently in the implementation phases, however prototypes of a previous version, using state merging and a classical ASM processor model had give good results regarding the precision of the estimation on benchmarking code examples.


References Results • Using the TWSA model that keeps only valid and relevant states and that gives a

precise and yet compact representation of the global system.

• Apply abstraction techniques to merge states and dynamically fusion states during the conjoint symbolic execution.

 Determining worst case behavior of the system SystemC is a system level design language for hardware/software modelling, it extends C++ by concurrency, time, hardware data types, reactivity… It has a simulation kernel that executes designs in a discrete-event simulation Global approach

A

  WCET estimation workflow based on TWSA model of SystemC designs Nesrine Harrath-Vladimir-Alexandru Paun -Bruno Monsuez ENSTA ParisTech, Paris, France http://uei.ensta-paristech.fr Objectives  Validating functional (correctness of system behavior)or non-functional properties (time constraints ) of hard real time systems. Using the timed SystemC waiting state automata (TWSA) to model the hardware.  Timing properties need to be carefully addressed as they are important in performance and safety verification of real time embedded systems.  Giving an upper bound estimation of the worst case execution time of the code running on the modeled system .

Issues

  Scientifc challenges: verify and validate embedded software  Industrial challenges : verify both functional and non-functional properties of a hard real time systems. RTSS 2011 Programming language: SystemC Problem: Building TWSA & WCET estimation  Conjoint Symbolic Execution of the system model and the program  With every executed instruction all reachable states of the processor are explored  Handling the state space explosion with controlled precision:



  worst case execution time analysis  An abstract model based on the analysis of the wait/notify mechanism of SystemC.  A compositional model used for a bottom/up approach. Modularity and adaptability to ever changing architectural models  Generate the system model directly from the HDL code that served to create the system  Ability to verify the correctness of the system model with regard to the upcoming certification standardsFuture workRefine the SystemC model to capture precise information about the system behaviour. A joint study of system precision and dynamically changing architectures to give a precise estimation of WCET.