Ling Li

Julien Bect

Emmanuel Vazquez

Bayesian Subset Simulation: a kriging-based subset simulation algorithm for the estimation of small probabilities of failure

Keywords: Computer experiments, Sequential design, Subset Simulation, Probability of failure

The estimation of small probabilities of failure from computer simulations is a classical problem in engineering, and the Subset Simulation algorithm proposed by Au & Beck (Prob. Eng. Mech., 2001) has become one of the most popular method to solve it. Subset simulation has been shown to provide significant savings in the number of simulations to achieve a given accuracy of estimation, with respect to many other Monte Carlo approaches. The number of simulations remains still quite high however, and this method can be impractical for applications where an expensive-to-evaluate computer model is involved.

We propose a new algorithm, called Bayesian Subset Simulation, that takes the best from the Subset Simulation algorithm and from sequential Bayesian methods based on kriging (also known as Gaussian process modeling). The performance of this new algorithm is illustrated using a test case from the literature. We are able to report promising results. In addition, we provide a numerical study of the statistical properties of the estimator.

INTRODUCTION

In this paper, we propose an algorithm called Bayesian Subset Simulation (BSS), that combines the Bayesian decision-theoretic framework from our previous studies [START_REF] Vazquez | A sequential Bayesian algorithm to estimate a probability of failure[END_REF][START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF] with the Subset Simulation algorithm [START_REF] Au | Estimation of small failure probabilities in high dimensions by subset simulation[END_REF].

Let Γ = {x ∈ X : f (x) > u} denote the excursion set of a function f : X → R above a threshold u ∈ R. We are interested in estimating the probability α(u) := P X (Γ), which corresponds to the probability of failure of a system for which f is a function of performance (see, e.g., [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF]). If the probability α(u) is small, estimating it using the Monte Carlo estimator α MC m = 1/m m i=1 1 f (X i )>u , X i i.i.d

∼ P X , requires a large number of evaluations of f . If the performance function f is expensive to evaluate, this leads to use a large amount of computational resources, and in some cases, it may be even impossible to proceed in reasonable time. Estimating small probabilities of failure with moderate computational resources is a challenging topic.

When α(u) is small, the main problem with the estimator α MC m is that the sample size m must be large in order to get a reasonably high probability of observing at least a few samples in Γ. In the literature, importance sampling methods have been considered to generate more samples in the failure region Γ. However, the success of this kind of methods relies greatly on prior knowledge about the failure region Γ and on a relevant choice for the proposal sampling distribution.

The idea of Subset Simulation is to decompose the difficult problem of generating samples in the failure region into a series of easier problems, by introducing intermediate failure events. Let u 0 = -∞ < u 1 < u 2 < . . . < u T = u be a sequence of increasing thresholds and define a corresponding sequence of decreasing excursion sets

Γ 0 := X ⊇ Γ 1 ⊇ • • • ⊇ Γ T := Γ, where Γ t := {x ∈ X : f (x) > u t }, t = 1, . . . , T . Notice that Γ t = t i=1 Γ i .
Then, using the properties

α(u 0 ) = 1 , α(u t+1 ) = α(u t ) P X (Γ t+1 |Γ t ) , t ≥ 0 , (1)
α(u) can be rewritten as a product of conditional probabilities:

α(u) = P X Γ T = T -1 t=0 P X (Γ t+1 |Γ t ) . (2)
Thus, the idea of Subset Simulation is to replace the problem of estimating the small probability α(u) by that of estimating the higher conditional probabilities P X (Γ t+1 |Γ t ), 0 ≤ t < T .

In [START_REF] Au | Estimation of small failure probabilities in high dimensions by subset simulation[END_REF], a standard Monte Carlo simulation method is used to estimate P X (Γ 1 ) = P X (Γ 1 |Γ 0 ). For the other conditional probabilities, a Markov Chain Monte Carlo method is used to simulate samples in Γ t , and then

P X (Γ t+1 |Γ t )
is estimated using a Monte Carlo method. Due to the direct use of Monte Carlo method, the number of evaluations needed remains still quite high. For many practical applications where the performance function corresponds to an expensive-to-evaluate computer model, it is not applicable. Note that the Subset Simulation algorithm has recently caught the attention of the Sequential Monte Carlo (SMC) community: using standard tools from the SMC literature, [START_REF] Cérou | Sequential monte carlo for rare event estimation[END_REF] derives several theoretical results about some very close versions of the Subset Sampling algorithm.

In this work, we propose an algorithm that takes advantage of a Gaussian process prior about f in order to decrease the number of evaluations needed to estimate the conditional probabilities P X (Γ t+1 |Γ t ). The Gaussian process model makes it possible to assess the uncertainty about the position of the intermediate excursion sets Γ t , given a set of past evaluation results. The idea has its roots in the field of design and analysis of computer experiments (see, e.g., [START_REF] Sacks | Design and analysis of computer experiments[END_REF][START_REF] Currin | Bayesian prediction of deterministic functions, with applications to the design and analysis of computer experiments[END_REF][START_REF] Welch | Screening, predicting and computer experiments[END_REF][START_REF] Oakley | Bayesian inference for the uncertainty distribution of computer model outputs[END_REF][START_REF] Oakley | Probabilistic sensitivity analysis of complex models: a Bayesian approach[END_REF][START_REF] Oakley | Estimating percentiles of uncertain computer code outputs[END_REF][START_REF] Bayarri | A framework for validation of computer models[END_REF]). More specifically, kriging-based sequential strategies for the estimation of a probability of failure are closely related to the field of Bayesian global optimization [START_REF] Mockus | The application of Bayesian methods for seeking the extremum[END_REF][START_REF] Mockus | Bayesian Approach to Global Optimization[END_REF][START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF][START_REF] Villemonteix | Optimisation de fonctions coûteuses[END_REF][START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF][START_REF] Ginsbourger | Métamodèles multiples pour l'approximation et l'optimisation de fonctions numériques multivariables[END_REF].

The paper is organized as follows. In Section 2, we give a detailed presentation of our new Bayesian Subset Simulation algorithm. In Section 3, we apply the algorithm on an example from the literature, and we perform numerical simulations to investigate the performance of the proposed algorithm. A comparison with Subset Simulation and classical Monte Carlo methods is provided. Finally, we conclude in Section 4.

Remark. An algorithm involving kriging-based adaptive sampling and Subset Simulation has been recently proposed by V. Dubourg and co-authors [START_REF] Dubourg | Reliability-based design optimization using kriging surrogates and subset simulation[END_REF][START_REF] Dubourg | Adaptive surrogate models for reliability analysis and reliability-based design optimization[END_REF] to address the problem of Reliability-Based Design Optimization (RBDO). Their approach is different from the one proposed in this paper, which addresses the problem of reliability analysis.

BAYESIAN SUBSET SIMULATION ALGORITHM

Algorithm

Our objective is to build an estimator of α(u T ) from the evaluations results of f at a number of points

X 1 , X 2 , . . . , X N ∈ X.
Let ξ be a random process modeling our prior knowledge about f , and for each n ≥ 0, denote by F n the σ-algebra generated by X 1 , ξ(X 1 ), . . . , X n , ξ(X n ). A natural Bayesian estimator of α(u t ) using n t evaluations is the posterior mean

α t = E nt (α(u t )) = E nt X 1 ξ>ut dP X = X g t dP X , (3)
where g t : x ∈ X → P nt ξ(x) > u t and E n (resp. P n ) denotes the conditional expectation (resp. conditional probability) with respect to F n (see [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF]). Note that, g t (x) can be readily computed for any x using kriging (see, e.g., [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF]).

Assume now that P X has a probability density function p X and consider the sequence of probability density functions q t , 0 ≤ t ≤ T , defined by

q t (x) = 1 α t p X (x) g t (x). (4)
We can write a recurrence relation similar to [START_REF] Vazquez | A sequential Bayesian algorithm to estimate a probability of failure[END_REF] for the sequence of Bayesian estimators α t :

α t = g t (x) p X (x) dx = α t-1 g t (x) g t-1 (x) q t-1 (x) dx. (5)
The idea of our new algorithm, that we call Bayesian Subset Simulation, is to construct recursively a Monte Carlo approximation α T of the Bayesian estimator α t , using ( 5) and sequential Monte Carlo simulation (SMC) (see, e.g., [START_REF] Del Moral | Sequential monte carlo samplers[END_REF]) for the evaluation of the integral with respect to q t-1 on the right-hand side. More precisely, denoting by m the size of the Monte Carlo sample, we will use the recurrence relation

α t = α t-1 × 1 m m i=1 g t (Y i t-1 ) g t-1 (Y i t-1 ) , 1 ≤ t ≤ T, (6)
where variables Y1 t-1 , . . . , Y m t-1 are distributed according to 1 the density q t-1 , which leads to

α T = T -1 t=0 1 m m i=1 g t+1 (Y i t ) g t (Y i t ) . (7)
The connection between the proposed algorithm and the original Subset Simulation algorithm is clear from the similarity between the recurrence relations (1) and ( 5), and the use of SMC simulation in both algorithms to construct recursively a "product-type" estimator of the probability of failure (see also in [START_REF] Del Moral | Sequential monte carlo samplers[END_REF], Section 3.2.1, where this type of estimator is mentioned in a very general SMC framework).

Our choice for the sequence of densities q 1 , . . . , q T also relates to the original Subset Simulation algorithm. Indeed, note that q t (x) ∝ E nt 1 ξ>ut p X , and recall that qt ∝ 1 ξ>ut p X is the distribution used in the Subset Simulation algorithm at stage t. (This choice of instrumental density is also used by [START_REF] Dubourg | Metamodel-based importance sampling for structural reliability analysis[END_REF][START_REF] Dubourg | Metamodel-based importance sampling for the simulation of rare events[END_REF] in the context of a two-stage kriging-based adaptive importance sampling algorithm. This is indeed a quite natural choice, since qT ∝ 1 ξ>u p X is the optimal instrumental density for the estimation of α(u) by importance sampling.)

Implementation

This section gives implementation details for our Bayesian Subset Simulation algorithm, the principle of which has been described in the Section 2.1. The pseudo-code for the algorithm is presented in Table 1.

The initial Monte Carlo sample Y 0 = {Y 1 0 , . . . , Y m 0 } is a set of independent random variables drawn from the density q 0 = p X -in other words, we start with a classical Monte Carlo simulation step. At each subsequent stage t ≥ 1, a new sample Y t is produced from the previous one using the basic reweight/resample/move steps of SMC simulation (see [START_REF] Del Moral | Sequential monte carlo samplers[END_REF] and the references therein). In this article, resampling is carried out using a multinomial sampling scheme, and the move step relies on a fixed-scan Metropolis-within-Gibbs algorithm as in [START_REF] Au | Estimation of small failure probabilities in high dimensions by subset simulation[END_REF] with a Gaussian-random-walk proposal distribution for each coordinate (for more information on these techniques, see, e.g., [START_REF] Robert | Monte Carlo statistical methods[END_REF]).

= {(X 1 , f (X 1 )), . . . , (X n 0 , f (X n 0 ))} (maximin)
3. Choose kriging model, estimate parameters k θ b) At each stage t(t = 1 . . . T ):

1. Compute the kriging predictor f t-1 n , and choose threshold ũt-1 2. Select and evaluate N t new points using a SUR sampling criterion for the threshold u t .

Update

for each i ≤ m, Y i t ∽ K Y t-1,i , • c)
The final probability of failure is calculated by

α = T -1 t=0 1 m m i=1 g t+1 (Y i t ) g t (Y i t )
A number N of evaluations of the performance function is done at each stage of the algorithm. This number is meant to be much smaller than the size m of the Monte Carlo sample-which would be the number of evaluations in the classical Subset Sampling algorithm. For the initialization stage (t = 0), we choose a space filling set of points Y 0 as usual in the design of computer experiments [START_REF] Santner | The Design and Analysis of Computer Experiments[END_REF]. At each subsequent stage, we use N t iteration of a SUR sampling strategy [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF] targeting the threshold u t to select the evaluation points. Adaptive techniques to choose the sequence of thresholds and the number of points per stage are presented in the following sections.

Remark 1. The resampling step could most certainly benefit from more elaborate schemes, such as the residual resampling scheme [START_REF] Hol | On resampling algorithms for particle filters[END_REF][START_REF] Douc | Comparison of resampling schemes for particle filtering[END_REF][START_REF] Bolic | New resampling algorithms for particle filters[END_REF]. The comparison of resampling schemes is left for future work.

Adaptive choice of the thresholds u t

It can be proved that, for an idealized 2 Subset Simulation algorithm with fixed thresholds u 0 < u 1 < • • • < u T = u, it is optimal to choose the thresholds to make all conditional probabilities P X Γ t+1 |Γ t equal to some constant value (see [START_REF] Cérou | Sequential monte carlo for rare event estimation[END_REF], Section 2.4). This leads to the idea of choosing the thresholds adaptively in such a way that, in the product estimate

α SubSamp T = T t=1 1 m m i=1 1 Γt Y i t-1 ,
2 assuming that Y 1 t , . . . , Y m t are independent and identically distributed according to qt.

each term but the last is equal to some predefined constant p 0 . In other words, u t is chosen as the (1p 0 )-quantile of Y t-1 . This idea was first suggested by [START_REF] Au | Estimation of small failure probabilities in high dimensions by subset simulation[END_REF] in Section 5.2, on the heuristic ground that the algorithm should perform well when the conditional probabilities are neither too small (otherwise they are hard to estimate) nor too large (otherwise a large number of stages is required). The asymptotic behavior of the resulting algorithm, when m is large, has been analyzed by [START_REF] Cérou | Sequential monte carlo for rare event estimation[END_REF].

In Bayesian Subset Simulation, we propose to choose the thresholds adaptively using a similar approach. More precisely, considering the product form of the estimator [START_REF] Welch | Screening, predicting and computer experiments[END_REF], we suggest to choose u t in such a way that

1 m m i=1 g t+1 (Y i t ) g t (Y i t ) = p 0 .
The equation can be easily solved since the left-hand side is a strictly decreasing function of u t .

Remark 2. Note that [START_REF] Cérou | Sequential monte carlo for rare event estimation[END_REF] proved that choosing adaptive levels in Subset Simulation introduces a positive bias of order 1/m, which is negligible compared to its standard deviation.

Adaptive choice of the number N t of evaluation at each stage

In this section, we propose a technique to choose adaptively the number N t of evaluations of the performance function that must be done at each stage of the algorithm.

Let us assume that t ≥ 1 is the current stage number; at the beginning of the stage, n t-1 evaluations of the performance function are available from previous stages. After several additional evaluations, the number of available observations of f is n ≥ n t-1 . Then, for each i ∈ {1, . . . , m}, the probability of misclassification 3 of x ∈ X with respect to the threshold u t is

τ t,n (x) = min p n (x, u t ), 1 -p n (x, , u t ) ,
where p n (x, u) = E n 1 ξ(x)>u (see [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF]). We shall decide to stop adding new evaluations at stage t when

1 m m i=1 τ t,n Y i t-1 ≤ η,
for some prescribed η > 0.

NUMERICAL RESULTS

In this section, we apply the proposed algorithm on a simple 2D test case from the structural reliability literature.

The problem under consideration is the deviation of a cantilever beam, with a rectangular cross-section, and subjected to a uniform load [START_REF] Gayton | Cq2rs: a new statistical approach to the response surface method for reliability analysis[END_REF][START_REF] Rajashekhar | A new look at the response surface approach for reliability analysis[END_REF]. The performance function is:

f (x 1 , x 2 ) = 18.46154 -7.476923 × 10 10 x 1 x 2 3 . (8)
The uncertain factors are x 1 and x 2 , which are supposed to be independent and normally distributed, as specified in Table 2. We use u = 17.8 as the threshold for the definition of the failure event. The probability of failure, which will be used as reference estimator, obtained using α MC m with m = 10 8 , is approximately 3.85 × 10 -5 (with a coefficient variance of about 1/ √ m α ≈ 1.61%). Figure 1 shows the distribution of the input factors along with a contour plot of f . Notice that the failure region is quite far from the center region of the input distribution. In the Bayesian Subset Simulation algorithm, we set an initial design of size N 0 = 10 which is equal to five times the dimension d of the input space (In the literature, very little is known about the problem of choosing N 0 , however some authors recommend to start with a sample size proportional to the dimension d, see [START_REF] Loeppky | Choosing the sample size of a computer experiment: A practical guide[END_REF]). Concerning the choice of N 0 , we decide to apply a greedy MAXMIN algorithm and sequentially choose the points which will maximize the minimal Euclidean distance between any two points in the initial Monte Carlo sample Y 0 . At each stage, we choose a Monte Carlo sample of size m = 1000. A Gaussian process with constant unknown mean and a Matérn covariance function is used as our prior information about f . The parameters of the Matérn covariance functions are estimated on the initial design by REML (see, e.g., [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF]). In this experiment, we follow the common practice of re-estimating the parameters of the covariance function during the sequential strategy, and update the covariance function after each evaluation. The target conditional probability between successive thesholds is set to p 0 = 0.1. The intermediate threshold u t is chosen by the criterion (2.3). The proposal distribution q t for a Gibbs sampling is a Gaussian distribution N (0, σ 2 ), where σ 2 is specified in Table 2. The stopping criterion for the adaptive SUR strategy is set to η t = 10 -6 (for t = 1, . . . , T -1) and η T = 10 -7 .

Figure 2 shows the Design of Experiment (DoE) selected by the algorithm at stage t = 1, 2, 3 and the last stage for one run. Table 3 lists the number of evaluations (rounded to integer) at each stage averaged over 50 runs. We can see that an average total of evaluations N = T i=0 N t = 104 are needed for our proposed Bayesian Subset Simulation, while for Subset Simulation, the number is 1000 + 900 × 4 = 4600. To evaluate the statistical properties of the estimator, we consider the absolute relative bias

κ = E( α) -α α (9)
and the coefficient of variation

cov = δ( α) α , (10)
where E( α) is the average mean and δ( α) is the standard deviation of the estimator α.

Table 4 shows the results of the comparison of our proposed Bayesian Subset Sampling algorithm with the Subset Simulation algorithm in [START_REF] Au | Estimation of small failure probabilities in high dimensions by subset simulation[END_REF]. Crude Monte Carlo sampling is used as the reference probability of failure.

For the fairness of the comparison, we set the same intermediate probability p 0 = 0.1, and sample size m = 1000 in both methods. Fifty independent runs are performed to evaluate the average of both methods. For Bayesian Subset Simulation method, as N is different for each run, we show the minimal and maximal of N from 50 runs.

CONCLUSION

In this paper, we propose a new algorithm called Bayesian Subset Simulation for estimating small probabilities of failure in a context of very expensive simulations. This algorithm combines the main ideas of the Subset Simulation algorithm and the SUR strategies developed in our recent work [START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF].

Our preliminary results show that the number of evaluations is dramatically decreased compared to the original Subset Simulation algorithm, while keeping a small bias and coefficient of variation.

Our future work will try to improve further the properties of our algorithm regarding the bias and the variance of the estimator. We shall also test and validate the approach on more challenging examples.

Figure 1 :

 1 Figure 1: Input distribution and contour plot of the performance function

Figure 2 :

 2 Figure 2: Evaluations selected by the Bayesian Subset Simulation strategy at stage t = 1, 2, 3 and the final Design of Experiment (DoE).

Table 1 :

 1 Algorithm of Bayesian Subset Simulation a) Initialize (Stage 0): 1. Generate a MC sample Y t = {Y 1 0 , . . . , Y m 0 }, drawn according to the distribution P X 2. Initial DoE I n

  I n , adjust intermediate threshold u t-1 according to f t-1 n 4. Regenerate a new sample Y t : 4.1 reweight: calculate weights: w t i ∝ g t (Y i t-1 )/g t-1 (Y i t-1 ) 4.2 resample: generate a sample Y t-1,i according to weights 4.3 move:

Table 2 :

 2 Random input factors Variable Distribution Mean m Standard deviation σ

	x 1 x 2	N N	0.001 250	0.0002 37.5

Table 3 :

 3 Average number of evaluations at each stage.

					N t			1	2	3	4	5
					Sub-Sim	1000 900 900 900 900
				Bayesian Sub-Sim	14	17	17	18	28
	400		N t = 14 (t=1)				400			N t	= 15 (t=2)
	300								300
	x 2								x 2
	200								200
					MC sample at stage t
					Final threshold u
					intermediate u t
					Design of Experiment
	0 100	0.4	0.8	x 1	1.2	1.6	2 -3 x 10		0 100	0.4		0.8	x 1	1.2	1.6	2 -3 x 10
			N t = 18 (t=3)							DoE (t=T)
	400								400
	300								300
	x 2								x 2
	200								200
										ut, t = 1, . . . , T		MC sample at stage t=T Final threshold u
														DoE
														Initial design
														intermediate u t
	0 100	0.4	0.8	x 1	1.2	1.6	2 -3 x 10		0 100	0.4		0.8	x 1	1.2	1.6	2 -3 x 10

Table 4 :

 4 Compare with Monte Carlo approach and Subset Simulation Method m N α (10 -5 ) δ( α) (10 -5 )

	κ	cov

By "distributed according to", it is not meant that Y 1 t-1 , . . . , Y m t-1 are independent and identically distributed. This is never the case in sequential Monte-Carlo techniques. What we mean is that the sample Y 1 t-1 , . . . , Y m t-1 is targetting the density qt-1 in the sense of, e.g.,[START_REF] Douc | Limit theorems for weighted samples with applications to sequential monte carlo methods[END_REF].

See[START_REF] Bect | Sequential design of computer experiments for the estimation of a probability of failure[END_REF] Section 2.4 for more information

ACKNOWLEDGMENTS

The research of Ling Li, Julien Bect and Emmanuel Vazquez was partially funded by the French Fond Unique Interministériel (FUI) in the context of the project CSDL.


Adel Noureddine

Aurelien Bourdon

Romain Rouvoy

Lionel Seinturier

Runtime Monitoring of Software Energy Hotspots

Keywords: D.2.8 [Software Engineering]: Metrics Performance, Measurement, Experimentation Power Model, Power Monitoring, Profiling, Bytecode Instrumentation 1

GreenIT has emerged as a discipline concerned with the optimization of software solutions with regards to their energy consumption. In this domain, most of the state-of-the-art solutions concentrate on coarse-grained approaches to monitor the energy consumption of a device or a process. However, none of the existing solutions addresses in-process energy monitoring to provide in-depth analysis of a process energy consumption. In this paper, we therefore report on a fine-grained runtime energy monitoring framework we developed to help developers to diagnose energy hotspots with a better accuracy than the state-of-the-art.

Concretely, our approach adopts a 2-layer architecture including OS-level and process-level energy monitoring. OSlevel energy monitoring estimates the energy consumption of processes according to different hardware devices (CPU, network card). Process-level energy monitoring focuses on Java-based applications and builds on OS-level energy monitoring to provide an estimation of energy consumption at the granularity of classes and methods. We argue that this per-method analysis of energy consumption provides better insights to the application in order to identify potential energy hotspots. In particular, our preliminary validation demonstrates that we can monitor energy hotspots of Jetty web servers 1 and monitor their variations under stress scenarios.

INTRODUCTION

Energy-aware software solutions are becoming broadly available, as energy concerns is becoming mainstream. The increasing usage of computers and other electronic devices (e.g., smartphones, sensors) is continuously impacting our overall energy consumption. Information and Communications Techonology (ICT) accounted for 2% of global carbon emissions in 2007 [START_REF] Gartner | Green IT: The New Industry Shockwave[END_REF] or 830 M tCO2e 2 , and is expected to grow to 1,430 M tCO2e in 2020 [START_REF] Webb | SMART 2020: enabling the low carbon economy in the information age, a report by The Climate Group on behalf of the Global eSustainability Initiative (GeSI)[END_REF]. ICT also consumed up to 7% of global power consumption (or 168 Gigawatt, GW) in 2008 [START_REF] Vereecken | Overall ict footprint and green communication technologies[END_REF]. This number is predicted to grow and double to 433 GW in 2020 or more than 14.5% of worldwide power consumption [START_REF] Vereecken | Overall ict footprint and green communication technologies[END_REF]. These values illustrate the opportunities for efficient ICT solutions to reduce carbon emissions and energy consumption. Rising energy costs in computers and mobile devices requires the optimization and the adaptation of computer systems. In this domain, research in GreenIT already proposes various approaches aiming at achieving energy savings in computers and software. However, most of the state-of-the-art approaches either focus only the hardware [START_REF] Mcintire | ETOP: sensor network application energy profiling on the LEAP2 platform[END_REF], or only offer coarse-grained energy estimation feedback of software [START_REF] Flinn | PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications[END_REF][START_REF] Do | pTop: A Process-level Power Profiling Tool[END_REF].

In this paper, we therefore propose to gather fine-grained applications' power feedback information at runtime and with similar accuracy as hardware monitoring while using only a software approach. Our approach, called e-Surgeon, consists of a system monitoring library (at the operating system level), called PowerAPI, and a software monitoring agent, called Jalen. e-Surgeon estimates the power consumption of applications' source code methods, in real-time, based on raw information collected from hardware devices (e.g., CPU, network card) through the operating system (for Power-API), and from raw information collected from software (CPU time, bytes transmitted through network) through bytecode instrumentation (for Jalen). We use both stateof-the-art power models and propose new models for estimating the power consumption of software at a finer grain.

As a first implementation, we target Java-based applications and we validate our approach using standard application servers, such as the Jetty Web Server. Our preliminary results demonstrate that we can diagnose power hotspots of Java-based applications at runtime, offering opportunities to reduce their power consumption.

The remainder of this paper is organized as follows. In Section 2, we describe our motivations and the main challenges we tackle. Section 3 describes our approach, the design of our proposed architecture and our power models. Section 4 details the implementation of our prototype. In Section 5, we report on the preliminary results we obtained and we validate them using a stress benchmark for the Jetty Web Server in Section 6. Related work is discussed in Section 7, while we conclude in Section 8.

MOTIVATION AND CHALLENGES 2.1 Motivation

Nowadays, power management of software and hardware is achieved either through runtime coarse-grained monitoring, or through analyzing dump files of the application's resources utilization [START_REF] Mcintire | ETOP: sensor network application energy profiling on the LEAP2 platform[END_REF][START_REF] Seo | An energy consumption framework for distributed java-based systems[END_REF][START_REF] Kansal | Fine-grained energy profiling for power-aware application design[END_REF]. Although these approaches allow power management of software, they do not allow runtime and fine-grained monitoring of the applications. Finegrained monitoring and visualization have many advantages: i) diagnose at a detailed level the power consumption and detect power hotspots at the threads and methods level, ii) provide detailed power information to be used for runtime power-aware software adaptation, and iii) helps in providing insights to developers for producing power-efficient code. The Green Challenge for USI 2010 [START_REF]The Green Challenge for USI[END_REF] has identified that profiling applications to detect CPU hotspots is a winning strategy for limiting the power consumption of applications. Therefore, we argue that a fine-grained approach for proposing power-aware information is a keystone for future poweraware systems and software.

Challenges

Hardware monitoring is usually achieved through additional hardware measurement equipments, such as multimeters or specialized integrated circuits (cf. Section 7). This approach offers a precise and accurate measurement of the power consumption of hardware components but at a cost of an additional investment. However, it can neither monitor the power consumption of software components, nor go into the details of software classes and methods usages. We rather believe that a scalable approach can be better obtained through a software-centric approach. Monitoring the power consumption of software has to yield many challenges in order to build an accurate software-centric approach. We outline some of the main difficulties that software monitoring has to cope with if accurate monitoring is to be offered:

• Accuracy. The biggest problem that software monitoring tools face is providing accurate estimations of power consumption based on various collected information. Unlike hardware measurement, software approaches use power models in order to provide an estimation of the power consumption of software components. However, these estimations tend to have different degrees of accuracy and overhead.

• Overhead. As software approaches monitor the executing software and calculate a power estimation of their consumption, an overhead is therefore always observed. The latter depends both on the degree of accuracy needed and on the size of the monitoring tool and the monitored application. This leads to a tradeoff between the accuracy requirements and the cost of the software monitoring tool.

• Fine-grained. Many of the current approaches (cf. Section 7) stop their power consumption estimation at the process level. Some of these approaches provide limited fine-grained but still raw values (such as execution time of methods or active time of threads). However, providing fine-grained estimation of the power consumption of software components is not as intuitive as mixing raw values and power models. The question arises to know which raw values is needed. How can we collect them? Which power models can we use and in which context?

• Power Models. Models to estimate the power consumption have already been proposed (cf. Section 7). However, most of these models are coarse-grained and hardware related, such as providing general formulae for power consumption of the hardware components (e.g., CPU, Network card). Models therefore need to be optimized for our context of fine-grained power consumption computation.

Laying these challenges, we propose in the next section an approach named e-Surgeon, for monitoring and profiling applications at runtime.

E-SURGEON DESIGN AND APPROACH

In this section, we present our power monitoring approach called e-Surgeon. We first present e-Surgeon general architecture, then we describe the power models we integrated.

Architecture

e-Surgeon architecture is composed from two distinct but complementary parts: a system-level power monitoring environment called PowerAPI; and a software-level application profiling environment called Jalen. These two parts work along each other in order to provide accurate runtime energy information at the application level (threads and methods levels). Figure 1 depicts the overall architecture of our approach.

Figure 1: e-Surgeon Reference Architecture.

PowerAPI

PowerAPI architecture is a modular architecture built for agile software programming. The core of the architecture are power modules. PowerAPI is developed as separate modules that can be started or stopped at runtime upon needs. A set of OS-dependent sensor modules (e.g., SCP U , S N etwork ) collect raw information about hardware resource utilization, either directly from the devices or through the operating system. These information are then exposed to another set of OS-independent formula modules that uses our power models (cf. Section 3.2) to compute the power consumption of each hardware component (e.g., FCP U , F N etwork ). These modules also compute the power consumption of running processes and applications per hardware resource. A local database (DB in Figure 2) is also used to store static information about the hardware resources and used to automatically calibrate PowerAPI depending on the environment. Finally, all these modules are managed through a life cycle module. The latter allows to start, stop, add, remove or modify modules depending on monitoring needs and commands sent by applications.

Jalen

Jalen is a software-level profiling architecture. It is responsible for profiling running applications and estimating their energy consumption at a finer grain, i.e., at threads or methods level. Several profiling techniques can be used, such as bytecode instrumentation or sampling the application. Each of these methods have benefits and drawbacks. The former does not modify the code of the application, and provides an overview of the application's energy consumption. However, it is less accurate than code instrumentation. The latter injects profiling code into the application's code (or bytecode), therefore allowing the profiler to capture all the necessary events related to energy consumption. On the other hand, instrumentation adds an overhead for running the additional code. Our approach, however, does not specify a single method of profiling. We prefer to keep this as a technical choice during implementation and to use dedicated APIs to communicate with the profiler and the lowlevel monitoring environment are to be respected.

The profiling part introspects the application at runtime, collecting statistics about its resources utilization. Information, such as methods durations, CPU time, or the number of bytes transferred through the network card, are collected and classified at a finer grain, e.g., for each method of the application. Next, a correlation phase takes place to correlate the application-specific statistics with the processlevel power information. Details on our power model for the correlation are presented in Section 3.2. Finally, the per-method or per-thread power consumption information is displayed to the user and can be exposed as a service (to be used, for example, in an application's autonomous adaptation cycle).

Power Models

We propose a comprehensive power model using our proposed formulae as well as formulae taken from the state-ofthe-art. In [START_REF] Seo | An energy consumption framework for distributed java-based systems[END_REF], the energy cost of a software is computed based on the following formula:

E sof tware = Ecomp + Ecom + E inf ra ( 1
)
Where Ecomp is the computational cost (i.e., CPU processing, memory access, I/O operations), Ecom is the cost of exchanging data over the network, and E inf ra is the additional cost incurred by the OS and runtime platform (e.g., Java VM).

We base our model on a similar principle, taking into account the modular aspect of the power calculation (e.g., the sum of the power consumption of different hardware components). Infrastructure power, E inf ra , is included in the computational cost of our power models and in our prototype. Power (in watt) is computed as the energy consumption (in joule) per unit of time (one second). From this, we can abstract our global power formula to the following:

P sof tware = Pcomp + Pcom (2)
At this stage, we defined two models, one for CPU computational costs and one for network communication costs.

Pcomp is therefore equal to the CPU power consumed by software, and Pcom is equal to the power consumed by the network card for transmitting software's data. Next, we detail the CPU and network power models we use in Pow-erAPI, and the CPU and network power models we use in Jalen.

PowerAPI Power Models

CPU Model

The CPU power consumed by a specific application (in our case we use process P IDs) can be represented by the following formula:

P P ID CP U (d) = PCP U (d) × U P ID CP U (d) (3)
Where P P ID CP U (d) is the CPU power consumed by the specific process PID during a given duration d, PCP U (d) is the overall CPU power during d and U P ID CP U (d) represents the process CPU usage during d. Thus, our approach is to estimate the power required by the CPU to execute the process PID. This is achieved by computing the CPU percentage usage of the PID by the overall CPU power during a given duration d. Next, we detail our model in order to compute PCP U (d), the global CPU power, and U P ID CP U (d), the process CPU usage.

Overall CPU power

The overall power consumption for the majority of modern processors (CMOS 3 ) follows the standard equation [START_REF] Pouwelse | Dynamic voltage scaling on a low-power microprocessor[END_REF]:

P f,v CP U = c × f × V 2 (4)
Where f is the frequency, V the voltage and c a constant value depending on the hardware materials (such as the capacitance and the activity factor). Thanks to this relation, we note that power consumption is not always linearly dependent to the percentage of CPU utilization. This is due to DVFS (Dynamic Voltage and Frequency Scaling) and also to the fact that power depends on the voltage (and subsequently the frequency) of the processor. For example, a process at 100% CPU utilization will not necessarily consume more power than a process running at 50% CPU utilization but with a higher voltage. Therefore, a simple CPU utilization profiler is not enough in order to monitor power consumption. Our power model takes into consideration these aspects of the CPU and allows accurate power consumption monitoring.

According to formula (4), computing the overall CPU power for a given time is equal to computing a static part (the constant c) and a dynamic part (the frequency f and its associated voltage V ). For the static part, the c constant is a set of data describing the physical CPU (e.g., capacitance, activity factor). Manufacturers may provide this constant, but in most cases this value is missing. To alleviate this problem, we use the existing relation between the overall power of a processor and its Thermal Design Power (TDP) value. TDP represents the power the cooling system of a computer is required to dissipate the heat produced by the processor. Therefore, the overall CPU power can be associated with the TDP as described in the following formula [START_REF] Rivoire | JouleSort: a balanced energy-efficiency benchmark[END_REF]:

P f T DP ,V T DP CP U 0.7 × T DP (5)
Where fT DP and VT DP represent respectively the frequency and the voltage of the processor within the TDP state. The benefit of using this formula is that TDP is a value provided by most manufacturers. In our architecture, TDP is stored in PowerAPI's local database.

For the dynamic part, the frequency f is associated to a specific voltage V. For a given voltage, one or more frequencies are associated. Thus, lowering the voltage results in changing frequency. The other way around is also valid, although in some cases a single voltage can support more than one frenquency. Frequencies used by a processor are provided by the operating system APIs, while voltages are given by manufacturers.

Process CPU usage

In order to compute the CPU usage for a given process (identified by its PID), we propose to calculate the ratio between the CPU time for this PID and the global CPU time (the time the processor is active for all processes) during a duration d :

U P ID CP U (d) = t P ID CP U tCP U (d) (6)
Our approach is inspired by well-known tools such as the Top linux program 4 . Thus, the CPU power consumption in a duration d and for a given frequency f, P f comp is equal to :

P f comp = 0.7 × T DP fT DP × V 2 T DP × f × V 2 × t P ID CP U tCP U (d) (7)
4 http://linux.die.net/man/1/top Finally, the CPU power consumption for a process Pcomp of formula ( 2) is equal to the average of the CPU power of each frequency balanced by the CPU time of all frequencies:

Pcomp = f ∈f requencies P f comp × t f CP U f ∈f requencies t f CP U (8)

Network Model

The network power of a process is calculated using a formula similar to the CPU power formula. We base our model on available information whether they are collected at runtime or provided by manufacturers' documentations. As a first step, we focus on Ethernet network cards. A similar model using a linear equation can be applied for wireless network cards [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF], but we did not investigate wireless cards yet. We obtain, from manufacturers' documentations the power consumed (in watt) for transmitting bytes for a certain duration (typically one second) according to a given throughput mode of the network card (e.g., 1 MB, 10 MB). Our network power model is therefore defined as:

P ower network process = i∈states ti × Pi × d t total ( 9
)
Where Pstate is the power consumed by the network card in the state i (provided by manufacturers), d is the duration of the monitoring cycle, and t total is the total time spent in transmitting data using the network card.

In the next section, we detail the CPU and network power models in Jalen.

Jalen Power Models

CPU Model

Using the information collected from profiling applications and the monitored system, we are able to calculate a reasonable estimation of the CPU time per method. And we use this information to compute the CPU power consumed per method and thread. As application code is generally executed inside threads (i.e., Java), we first calculate the power consumed per thread. For that, we apply the following formula:

P ower CP U thread = T ime CP U thread × P ower CP U process Duration cycle (10)
Where T ime CP U thread is the CPU time of the thread in the last monitoring cycle (obtained from the environment, such as the OS or the JVM), P ower CP U process is the power consumed by the application process in the last monitoring cycle (obtained from PowerAPI), and Duration cycle is the duration of the monitoring cycle. We then filter the methods to get the list of methods running in the last monitoring cycle (whether they are still running or not). For each thread, we get the methods that it invoked from the list (a thread usually has its own execution stack which is made of frames. A frame represents a method invocation). Furthermore, we estimate with a good accuracy the CPU time for each method using the following formula:

T ime CP U method = Duration method × T ime CP U thread m∈M ethods Durationm (11)
Where Duration method is the execution time of the method in the last monitoring cycle, and Duration methods is the sum of the execution time of all methods in the last monitoring cycle.

Finally, we calculate the power consumed per method using this formula:

P ower CP U method = T ime CP U method × P ower CP U thread Duration cycle (12)

Network Model

We calculate the network power using the number of bytes transmitted by the application. We first calculate the number of bytes read/written in the last monitoring cycle. Then, we collect the network power consumed by the application process from our system library PowerAPI. The network power consumed per method is therefore:

P ower N etwork method =
Bytes method × P ower N etwork process Bytesprocess

Where Bytes method is the number of bytes read and written by the method, P ower N etwork process is the power consumed by the application, and Byteprocess is the number of bytes read and written by all methods of the application.

The network power consumption per thread is therefore the sum of the network power of all methods running in the thread as shown in the following formula:

P ower N etwork thread = P ower N etwork methods (14)
In the next section, we describe the implementation e-Surgeon using our power models.

IMPLEMENTATION

The implementation of e-Surgeon includes a system level modular library, PowerAPI, and a Java tool instrumenting bytecode at runtime, Jalen. CPU and network modules as well as profiling functionalities are provided. The source code of our e-Surgeon prototype is available at github5 .

PowerAPI

PowerAPI is implemented as a system level modular library. We implemented so far the CPU and network modules and power models. Our system-level library aims to provide power information per PID for each system component (CPU, network card, etc.). The library is therefore based on a modular approach where each system component is represented as a power module. Power modules operate independently from each other and are composed by two sub-modules: formula and sensor. These sub-modules communicate using the Service-Oriented Architecture (SOA) paradigm, and are contained in an OSGi6 container. In particular, we use Service Oriented Framework (SOF) 7to implement the various modules of PowerAPI in C++.

The sensor sub-module is responsible for gathering operating system related information for the module. For example, it gathers the number of bytes transmitted by the network card, and the time spent by the CPU at each of the processor frequencies (when DVFS is supported). These data are basically given by the operating system, giving to the sensor sub-module of being OS-dependent. In particular, our implementation, based on a GNU/Linux distribution, exploits system information available in the procfs and sysfs file systems [START_REF] Mouw | Linux kernel procfs guide[END_REF]. The formula sub-module, on the other hand, is hardware independent. Indeed, this sub-module is responsible for estimating the power consumed for each process by using both information gathered by the sensor sub-module and information based on hardware characteristics. For instance, in case of CPU energy consumption, our model has to take into account the frequency and voltage ranges, or Thermal Dissipation Power. We implemented sensor and formula sub-modules for the CPU and NIC on a GNU/Linux operating system. Additionally, our library supports the lifecycle management of its power modules. The latter can be started, stopped and their parameters changed at runtime, using a modules manager. The benefit of this modular approach is to offer flexibility while monitoring the system and to control the overhead of the monitoring library.

We provide a modular library where only part of its components are platform-dependent. Its modularity allows easy porting of the library while retaining most of its power modeling code. Although PowerAPI works as a standalone library, it is used in addition to our application power monitoring component: Jalen.

Jalen

We also developed a runtime application power monitoring component, called Jalen, as part of the e-Surgeon architecture. Jalen uses the per-process power information provided by PowerAPI, and correlates it with information collected from the application monitoring in order to provide per-method power information. Jalen is designed as a twoparts architecture: i) a Java programming language agent that instruments the bytecode of the application in order to inject our monitoring code, and ii) a JMX client computing and correlating the collected data. This client extracts the per-method power consumption values. Figure 3 overviews the architecture of Jalen. We use bytecode instrumentation technics 8 to inject our monitoring code into the methods of legacy applications. In order to reduce the overhead introduced by the instrumentation, we offload all the computations to a remote JMX client. Therefore, our Java agent only collects raw values, such as for the CPU: the start time, end time, running status, executing thread identifier and callee method (using a custom execution stack trace). For the network, we use a delegator class to route calls from the class SocketImpl 9 to a custom implementation. We override the methods getInput-Stream() and getOutputStream() to monitor the number of bytes read and written to sockets. This information is then correlated with the method names invoking the methods getInputStream() or getOutputStream(), in order to get the number of bytes read/written by method.

All these collected information are then exposed in a MXBean 10 interface. In particular, the agent performs calculations in order to determine the actual duration of the execution of the method during the last monitoring cycle. This calculation takes into account all the calls to the methods executed in a same thread. It also separates the calculations of these methods by thread. For example, method A() is called twice from thread X, and three times from thread Y. The calculations generate two results: one where the duration is the sum of the two calls in thread X, and the second where the duration is for the sum of the three calls in thread Y. We do not merge these numbers because we need to construct the call tree in order not to take into account the delta duration of the callee method when its children are being executed.

Our prototype can handle this on a per-thread basis thanks to this separation.

Then, we build a JMX client that, not only displays the collected information, but also does the computation and correlation in order to determine the CPU and network power consumed per method in each monitoring cycle. The JMX client collects information exposed by the agent's MXBean.

Using power models and metrics correlations (cf. Section 3.2), we estimate the CPU power and the network power consumed per method.

EMPIRICAL VALIDATION

We validate the accuracy and precision of our e-Surgeon prototype on a Dell Precision T3400 workstation with an Intel Core 2 Quad processor (Q6600), running Ubuntu Linux 11.04 and Java 1.6 We first evaluate our PowerAPI library (cf. Section 5.1), and then evaluate our Jalen Java agent (cf. Section 5.2). Based on these results, we conduct an analysis of a stress benchmark on a Jetty Web Server (version 8.0.4.v20111024) in Section 6.

PowerAPI Validation

CPU Power

We first assess the accuracy of the results provided by our system library. We compared the power values provided by PowerAPI with the actual power consumption of the computer using a powermeter. In our tests we use PowerSpy 11 , a bluetooth powermeter. We compare the values of our library and the powermeter in a stress test on Jetty Web Server using Apache JMeter12 (cf. Figure 5), and using the Linux stress command13 (cf. Figure 4). Note that due to synchronization time lag between PowerSpy and our library, values are shifted for a few seconds in the beginning of the monitoring. These values are normalized in order to observe trends in the CPU power consumption. We normalize these values by subtracting for each measured value of the powermeter, the average of the differences between the values measured by the powermeter and provided by our library. The results show minor variations between the values estimated by our library, and the actual power consumption.

The margin of error is estimated to 0.5% of the normalized and averaged values in the core stressing scenario. The error grows to nearly 3% in the Jetty stress test. We use the Linux Top program to compute the CPU utilization of monitoring one process by PowerAPI and estimate it at around 0.1%. Therefore, we can reasonably argue that using a software-centric approach provides values that are accurate enough to be used by power management software.

Network Power

We run a network stress test using Iperf 14 and measured the power consumption of Iperf's CPU server on our host configuration. We send two sets of TCP packets of 100MB each from a distributed client to our host server. We used the default settings of Iperf, where also its CPU server executes following a periodically cycle (every second). Our results show network consumption around 0.017 watt compared to CPU consumption of Iperf process around 0.9 watt. These numbers show that, although CPU power is quite low (average around 0.9 watt) and the network card uses all its capacity, the consumed network power is largely negligible compared to the consumed CPU power on our test server. This observation is in correlation with the literature [START_REF] Rivoire | JouleSort: a balanced energy-efficiency benchmark[END_REF]. Therefore, we mostly outline the results of our CPU experimentation.

Jalen Validation

We calculate the CPU overhead of our Jalen Java agent using the start time and the time per request of Apache Tomcat 7.0.22 application server 15 as a comparison metric. This metric involves many of Tomcat's classes and methods and is provided by default by Tomcat. The average start time of Tomcat on our host configuration (a MacBook Pro, mid 2009, and Java 1.6) is around 821.8 ms. With Jalen Java agent, Tomcat, while having its methods instrumented, took 1178 ms in average. Therefore, our agent introduces an overhead of 43.34%. We also calculate the time per request using ApacheBenh 2.3. On 10,000 requests, the mean time per request is at 20.206 ms with Jalen, in comparison to 12.861 ms without. The time overhead per request is therefore at 57.11%. Even though these numbers may appear to be high, they should compared to the overhead of similar profilers. We therefore compared our results of Tomcat's start time with the Java Interactive Profiler (JIP) 16 . JIP also instruments bytecode but does not offer power related information. With JIP, Tomcat took 1469.6 ms to start, or an overhead of 78.82%. Thus, Jalen have an overhead 45% lower to similar method-level bytecode instrumentation profilers such as JIP. Figure 7 summarizes these numbers. In the next section, we present and discuss the results of our approach on monitoring and detecting energy hotspots of Jetty Web Server.

ENERGY HOTSPOTS OF JETTY

The goal of our approach is to detect energy hotspots in applications. Jetty Web Server is an example of such complex applications, counting 88,513 source lines of code (SLOC) in the version we used for our study (version 8.0.4.v20111024). We run our e-Surgeon prototype (system library and Java agent plus a JMX client) on an instance of Jetty Web Server. We use JMeter to stress Jetty server using a benchmark scenario (stressing the examples provided by default in Jetty). We run the experimentation for an average time of one minute, with 20 threads (users in JMeter) and a loop count of 500. The results we gathered are presented in Figure 8. The graph portrays the top 10 most powerconsuming methods in the X axis (out of 726 instrumented methods). The right Y axis (thus the bars) represents the power consumed during our execution in percentage of the total power consumed. The left Y axis (thus the line) represents the number of invocations of the method. We run this experiment several times, and although we had difference in the watt power values, we notice that the global and proportional percentage is stable. Note also that the provided values are an aggregation of the execution of the methods on all threads. The first observation is that the top 10 methods consumes nearly half of the total power consumed by Jetty during the stress benchmark (50.99%). More interestingly, we observed that the method org/eclipse/jetty/ io/ByteArrayBuffer.get consumes 14.22% of the total power by its own, with a similar number of invocations compared to other methods.

We also analyze the power consumption per method invocation of the top 10 methods. The results are presented in Figure 9. We observe that org/eclipse/jetty/io/ AbstractBuffer.putIndex has a lower power per invocation in the top 10 methods. This method consumed 2.89% of total power during the tests, but was invoked 42293 times. Thus, this method has a power per invocation of 134.057 microwatts. On the other hand, org/eclipse/jetty/io/ ByteArrayBuffer.get has a power per invocation of 535.237 microwatts with 52159 invocations and 14.22% of global power consumed. The results for the most consuming classes (out of 146) are reported in Figure 10. We note that the 2 aforementioned classes (org/eclipse/jetty/io/AbstractBuffer with 39.22% and org/eclipse/jetty/io/ByteArrayBuffer with 23.89%) consume alone more than 60% of the total power (63.11%). io/AbstractBuffer is an averaged sized class in Jetty of 544 SLOC where only 10 of its methods has been invoked 255,472 times, while the latter is even smaller with 304 SLOC where 26 of its methods have been invoked 606,710 times. These numbers show a strong relation between the energy consumption of methods and their number of invocation. These results can be explained by our benchmark stress scenario. The latter stresses Jetty Web Server using HTTP requests on servlets with simple executed JSP code. Therefore, the highest power consumption in our tests is concentrated on classes which manage reads and writes of HTTP requests (e.g., org/eclipse/jetty/io/AbstractBuffer, org/eclipse/jetty/io/ByteArrayBuffer). This strengthen our initial validation of the accuracy of e-Surgeon.

We believe that this information can help the developers to investigate alternative implementations of the class org/ eclipse/jetty/io/ByteArrayBuffer in order to reduce the power footprint of this method. By keeping track of the power footprint of classes and methods, we think that development tools (e.g., coding completion systems, documentation, debuggers, etc.) could be extended to help developers build greener software.

Limitations

Our results show that we can identify energy hotspots in applications, and in Jetty web server in particular. However, and even though we used a benchmark imitating a real-case scenario, we are aware that our results should not be generalized without further consideration.

First, our aim was to observe trends in energy consumption (which is the reason of using percentages when comparing methods and classes). Raw watt values are less relevant as direct measurements vary greatly between hardware (i.e., a given application consumes different amount of energy when running on two different machines, such as a laptop or a server). Therefore, we argue that our approach is useful in profiling applications in order to find the origin of energy leaks. Developers can then provide hotfixes for the application in order to reduce its energy footprint.

Second, and in comparison with our first point, the overhead of our prototype is not negligible, thus limiting its usage in production (57.11% overhead for Tomcat's individual requests (cf. Section 5.2)). Although it is comparable to similar bytecode profilers, the overhead is penalizing to be used in production systems (e.g., Tomcat, Jetty). We also developed a lightweight version, providing the energy consumption of running threads (but not methods and classes). This version does not use bytecode instrumentation, therefore its overhead is negligible in Jetty and Tomcat and with a 1.95% increase in time. Note also that the computation of the energy consumption of methods and threads is realized in a separate process, and that PowerAPI runs also in a dedicated process, thus limiting the impact on the execution of the monitored application. We believe that the overhead of our power model and architecture is controlled, and can be considered is acceptable with regards to the benefits of the computed energy indicators.

Future Directions

Our study aims at providing a representation of the energy consumption of CPU-and network-intensive software at different levels of granularity (e.g., application, source code).

In the future, we plan to extend ou approach to measure hardware components that contribute to a high percentage in energy consumption of applications [START_REF] Rivoire | JouleSort: a balanced energy-efficiency benchmark[END_REF], which are, in addition to the CPU, the memory and the disk.

We are also planning to develop additional sensors for different hardware configurations and environments because energy consumption depends on the hardware environment (e.g., modules compatible with Windows, Mac OS, and different hardware models). Developing sensors and modules for virtual machines allows our model to reduce its dependency on hardware parameters (e.g., dealing with the diversity of hardware is therefore left to the virtual machine), and consider energy accounting issues in the context of green computing environments.

RELATED WORK

In this section, we outline the relevant related works to energy modeling, energy monitoring and metering, powerrelated tools at the system level, and application profiling tools, in particular for Java applications.

Energy Metering and Modeling

Monitoring energy consumption of hardware components usually requires an hardware investment, like a multimeter or a specialized integrated circuit. For example in [START_REF] Mcintire | ETOP: sensor network application energy profiling on the LEAP2 platform[END_REF], the energy management and preprocessing capabilities is integrated in a dedicated ASIC (Application Specific Integrated Circuit). It continuously monitors the energy levels and performs power scheduling for the platform. However, this method has the main drawback of being difficult to upgrade to newer and more precise monitoring and it requires that the hardware component be built with the dedicated ASIC, thus making any evolution impossible without replacing the whole hardware. On the other hand, an external monitoring device provides the same accuracy as ASIC circuits and does not prohibit energy monitoring evolutions. The previous monitoring approaches retrieve energy measures about hardware components only. However, knowing the energy consumption of software services and components requires an estimation of that consumption. This estimation is based on calculation formulae as in [START_REF] Seo | An energy consumption framework for distributed java-based systems[END_REF] and [START_REF] Kansal | Fine-grained energy profiling for power-aware application design[END_REF].

In [START_REF] Seo | An energy consumption framework for distributed java-based systems[END_REF], the authors propose formulae to compute the energy cost of a software component as the sum of its computational and communication energy costs. For a Java application running in a virtual machine, the authors take into account the cost of the virtual machine and eventually the cost of the called OS routines. Our model is based on a similar principle, although we abstract the cost of the infrastructure in our computational costs. However, the authors calculate the energy cost of components in terms of the cost of its interfaces (i.e., a method in most cases). The latter is calculated as an estimation of the energy cost of executing Java's 256 bytes code types, JVM's native methods, and the cost of threads synchronization. Our computation model is based on runtime power consumption. The CPU power consumed by a method is its percentage share of the power consumed by the application, calculated using the actual CPU time and utilization of the method. On the other hand, our network model is similar to theirs, as both are based on the size of data transmitted (send/receive) during the invocation of the program. Still, we use runtime-monitored values to calculate power consumption, while they use estimations at construction time albeit refined at runtime. In [START_REF] Kansal | Fine-grained energy profiling for power-aware application design[END_REF], the authors take into account the cost of the wait and idle states of the application (e.g., an application consumes energy when waiting for a message on the network). We also take these states into account by only using the actual time spend running on a resource (i.e., CPU, network card). In [START_REF] Flinn | PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications[END_REF], the authors propose a tool, PowerScope, for profiling energy usages of applications. This tool uses a digital multimeter to sample the energy consumption and a separate computer to control the multimeter and to store the collected data.

PowerScope can sample the energy usage by process. This sampling is more accurate than energy estimation, although it still needs a hardware investment.

System Level Tools

pTop [START_REF] Do | pTop: A Process-level Power Profiling Tool[END_REF] is a process-level power profiling tool. Similar to the Linux Top program, the tool provides the power consumption (in Joules) of the running processes. For each process, it gives the power consumption of the CPU, the network interface, the computer memory and the hard disk.

The tool consists in a daemon running in the kernel space and continuously profiling resource utilization of each process. It obtains these information by accessing the /proc directory. For the CPU, it also uses TDP provided by constructors in the energy consumption calculations. It then calculates the amount of energy consumed by each application in a t interval of time. It also consists of a display utility similar to the Linux Top utility.

Our approach is more flexible and fine-grained than pTop.

Not only we offer process-level power information, but we also go deep into the application in order to profile and report thread and method-level power consumptions. Furthermore, the system level part of e-Surgeon offers better flexibility and on-demand scaling of the tool. Monitoring modules can be shutdown or started depending on the context: on limited resources devices, modules, such as the network or hard disk modules, can be shutdown in order to monitor only the CPU. When more resources become available, these modules will be re-started. Other situations are also possible, such as situations where the user is only interested in monitoring the CPU or the network energy consumption. PowerAPI also adapts to its monitored environment thanks to its auto-calibration process, in particular by using calibration data stored in its database. Our flexible and modular approach therefore offers these functionalities, and extends them to not only OS processes, but also inside Java-based applications profiling.

In addition to pTop, several utilities exist on Linux for resource profiling. For example, cpufrequtils 17 , in particular cpufreq-info to get kernel information about the CPU (i.e., frequency), and cpufreq-set to modify CPU settings such as the frequency. iostat 18 that is used to get devices' and partitions' input/output (I/O) performance information, as well as CPU statistics. Other utilities [START_REF] Gite | How do I Find Out Linux CPU Utilization?[END_REF] also exist with similar functionalities, such as sar, mpstat, or the system monitoring applications available in Gnome, KDE or Windows. However, all of these utilities only offer raw data (e.g., CPU frequency, utilized memory) and do not offer power information.

Application Profiling Tools

Several open-source or commercial Java profiling tools already propose some statistics of Java applications. Tools, such as VisualVM19 , Java Interactive Profiler (JIP)20 , or the Oktech Profiler21 , offer coarse-grained information on the application and fine-grained resource utilization statistics. However, they fail in providing power consumption information of the application at the granularity of threads or methods. For example, the profiler of VisualVM only provides self wall time (e.g., time spend between the entry and exit of the method) for its instrumented methods. We rather provide runtime values for the duration of execution of methods in a monitoring cycle, and give a good estimation of the CPU time of these methods. These tools also lack of providing network related information, such as the number of bytes transmitted by methods and thus the power consumed.

CONCLUSION AND FUTURE WORK

In this paper, we report on the e-Surgeon runtime energy monitoring solution. It allows to gather and calculate the power consumption at processes and methods level. Its modular architecture allows runtime context-based adaptations of the monitoring environment itself, leveraging performance and accuracy at the wish of the application or the user. We also propose power models to calculate the power consumption. Our models use and extend the state-of-the-art models and formulae, and port them to a fine-grained context. Our initial results show the potential of our approach for diagnosing, at runtime, power hotspots of Java-based applications.

As for future work, we plan to: i) propose more power models for other hardware resources (in particular, memory and disk); ii) as application servers are more and more running on virtual machines, we plan to implement specific sensors to these environments and experiment our model and approach on them; and iii) use e-Surgeon and power-aware information to adapt applications at runtime based on power concerns.

Figure 2 :

 2 Figure 2: PowerAPI Reference Architecture.

Figure 3 :

 3 Figure 3: The Jalen Architecture.

Figure 4 :

 4 Figure 4: Stressing the processor cores with the stress command.

Figure 5 :

 5 Figure 5: Running stress tests on Jetty using JMeter.

Figure 6 :

 6 Figure 6: CPU and network power consumption in Iperf stress test.

Figure 7 :

 7 Figure 7: Time overhead of Jalen with Tomcat 7 start time.

Figure 8 :

 8 Figure 8: Cumulated power consumption of Jetty methods under JMeter stresses (top 10 most powerconsuming methods).

Figure 9 :

 9 Figure 9: Power in watt per invocation of the top 10 most power-consuming methods (lower is better).

Figure 10 :

 10 Figure 10: Cumulated power consumption of Jetty classes under JMeter stresses.

https://github.com/abourdon/e-Surgeon

formerly Open Service Gateway Initiative

http://sof.tiddlyspot.com

http://asm.ow2.org

http://jmeter.apache.org

http://linux.die.net/man/1/stress

http://kernel.org/pub/linux/utils/kernel/cpufreq/ cpufrequtils.html

http://visualvm.java.net

http://jiprof.sourceforge.net

http://code.google.com/p/oktech-profiler

Acknowledgments

This work is partially funded by the French Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region Campus Intelligence Ambiante (CPER-CIA) 2007-2013.


Jean-Paul Pique
email: pique@liphy.ujf-grenoble.fr

Pulsed Frequency Shifted Feedback Laser for Accurate Long Distance Measurements: Beat Order Determination

Keywords: laser, Frequency-Shifted Feedback laser, long distance, long range, atmospheric measurements, LIDAR. 1

Long-distance measurements (10 m -1000 m) with an accuracy of 10 -7 is a challenge for many applications. We show that it is achievable with Frequency Shifted Feedback (FSF) laser interferometry technique, provided that the determination of the radio frequency beat order be made without ambiguity and on a time scale compatible with atmospheric applications. Using the pulsed-FSF laser that we developed for laser guide star application, we propose and test, up to 240 m, a simple method for measuring the beat order in real time. The moving-comb and Yatsenko models are also discussed. The first of these models fails to interpret our long-distance interferometry results. We show that the accuracy of long-distance measurements depends primarily on the stabilization of the acoustic frequency of the modulator.

Introduction

Measurement of long-range distances (10 m -1000 m) with an accuracy of 10 -7 is a major challenge for the automotive, aerospace, nuclear, geology, atmospheric applications ... Commercial systems are already available that have an accuracy of the order of few ppm. In general, three categories of methods exist: triangulation, time of flight and interferometry [1].

The requisite accuracy can be provided by laser interferometry methods. Interferometry with a single laser is very accurate, but applicable only for very short distances, because the fringe size is the laser wavelength. For longer distances, the interference order to be determined becomes extremely high. This difficulty has been overcome by the "Synthetic Wavelength Interferometry" method (SWI) [2], which has demonstrated beautiful results [START_REF] Floch | Proc. SPIE[END_REF][START_REF] Azouiqui | [END_REF]. The method consists in superimposing two beams of frequency ν and ν 1 2 in an interferometer. The synthetic wavelength Λ = c / (ν 2 -ν ) 1 then lies in the millimeter range. For an optical path difference z, the interference

order ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ Λ = z m
is determined by scanning the frequency of one laser. Distances of several tens of meters have been measured in this way with an accuracy of ppm. This method using two lasers, however, remains more difficult to implement for various technical reasons. With a single laser, the easiest technique, called "Modulated Continuous-Wave Frequency" (FMCW) [1] or "Optical Frequency Domain Reflectometry" (OFDR) [5] consists in quickly scanning the wavelength of a high spectral purity laser. The beat frequency detected at the output of the interferometer is proportional to the optical path difference, and generally lies in the kilohertz range. Unfortunately, this is in an area where the intrinsic noise of the laser is still high.

Furthermore, the nonlinearity of the scan remains a strong obstacle. For all the interferometry techniques mentioned above, the maximum measurable distance is limited by the coherence of 2 the laser line. In an experiment of great ingenuity, Nakamura et al. [6,7] have shown that an FSF laser can measure distances up to more than 18.5 km with an accuracy of a few ppm. This new technique is similar to the OFDR method but with a beat in the radio frequency range. Although it is very promising, it nevertheless suffers from the difficulty and the slowness of determining the beat order.

In this paper we show that the pulsed-FSF laser that we developed for laser guide star [8] solves many of the problems outlined above. In the second section we describe the experimental set-up used. In the third section we describe a new technique to determine unambiguously, and in a few ms, the RF-beat order. We show experimentally that the well known moving-comb model fails to interpret the results of long distances measurements. The model of Yatsenko et al. [9] is more relevant. Finally in the fourth section, we discuss the conditions required to achieve an accuracy of 10 -7 .

Pulsed-FSF laser long distance measurement set-up

Fig. 1 The set-up is depicted in Figure 1. The pulsed-FSF laser is detailed in reference [8].

Briefly, the laser cavity consists of two dye amplifier media. The dye-jet (J) is pumped by a cw

New method for fast beat order determination

The and the log of its FFT (PD3 signal). The recurrences n×ν RT (n = 1,2 ...) are clearly observed.

Recurrences for n> 1 are strongly attenuated by the 300 MHz bandwidth of our oscilloscope.

The narrow beat frequency 2ν AO was attributed [10] to a residual amplitude modulation due to imperfections in the AO frequency shifter. The very weak satellites ν ± 2ν we observe (Fig. 2b) prove an amplitude modulation at a frequency of 2ν (see below).

RT AO AO

The existence of this modulation on the beam is an obstacle for experimental demonstration of a hypothetical movingcomb (see below).

Other sidebands (Fig. 2c), close to ν recurrences RT correspond to an already observed amplitude modulation frequency ν am of about 1.25 MHz [8]. Here we interpret these as interruptions of the intra-cavity field due to air-bubbles that flow through the dye cell and pass in the spatial mode of the intra-cavity beam. These interruptions, which occur on average every few tens of microseconds, induce relaxation oscillations just after the build-up. Based on the underlying non-linear dynamics, the frequency modulation can be satisfactorily described by the photon density model of reference [8]. These sidebands are intrinsic to the amplifying medium. Observation of recurrences and doublets gave rise to the moving-comb model [11], which has hitherto satisfactorily described most interferometric results in the literature. It consists of considering that the frequency comb of an equivalent multi-mode laser (without AO) shifts at the rate 2ν AO /τ RT , where τ RT = 1/ν RT . To our knowledge, only two papers report the observation of moving-comb in very different experimental conditions. By injecting the FSF laser beam in a Fabry-Perot interferometer of sufficient resolution and fixed length, the passage of "modes" would produce signal peaks of frequency 2ν AO on a fast photodiode. This experiment is very delicate because the detection bandwidth must be between 2ν A0 and ν .

RT The first demonstration was made in reference [12] using an FSF dye laser having the following characteristics: 2ν AO = 0.2 MHz and ν RT = 188 MHz. As expected in the moving-comb model, the time response of the signal at the output of a high resolution Fabry-Perot interferometer displays temporal peaks spaced in time by 1/2ν AO . A second experimental demonstration was performed in references [13,14]. An FSF Nd: YVO4 diode-pumped laser was used with the following characteristics:

2ν AO = 157 MHz and ν RT = 1492 MHz. These observations seemed to validate the moving-comb model (at least when 2ν AO is smaller than, and even close to, ν RT ). However, we will see below that it fails to interpret our experimental results of long-distance interferometry.

Without using the spectral aspect of the moving-comb model, Yatsenko et al. [9] introduced a more realistic stochastic model by including frequency dependent gain and losses of an FSF laser seeded by spontaneous emission. The authors calculated that the RF spectrum of the output signal of an interferometer injected by an FSF laser exhibits doublets whose spacing is directly proportional to the path difference between the two interferometer arms.

In both models the distance measured by interferometry is determined modulo of a characteristic distance z 0 . As discussed below, z 0 is in metric range that, compared to SWI techniques, makes things easier for measurements over long distances. However, it is also necessary to determine the beat order.

Beat order in the moving-comb model

Because 2ν AO < ν RT (75 MHz and 253 MHz, respectively) with a ratio close to that of the experimental work of reference [14] where the moving-comb seems to have been observed experimentally, it is tempting to use this picture. Kasahara et al. [11] proposed a model in which the field is expressed as:

)) 2 sin( 1 ( ) ( ) 2 / ( ) 2 / ( ) ( ) 2 / 2 / ( 2 exp ) ( ) ( )) ( 2 exp( ) ( ) ( 0 2 0 2 0 t B A t E q t q t t q t t E t E t j t E t E am q RT AO AO AO q L AO RT AO q q q q πν τ ν ν ν ν ν ν τ ν π + = Φ + - + - = Φ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ Δ - - = Φ = ∑ (1)
The signals at the photodiodes PD1 and PD3 are:

2 int 2 1 ) ( ) ( ) ( ) ( ) ( τ - + = = t bE t aE t I t E a t I ( 2
)
where q is the index of the modes. Δν L is the spectral width of the laser line, or more precisely the width of the spectral envelope. The time delay between the two arms of the Mach-Zehnder is where m is the beat order and z 0 is the equivalent of the fringes in the SWI technique. With the parameters of the previous section, z 0 is about 4.29 m. For a distance of 100 m, the order m is only 23. The power of the method is obvious: we can measure distances merely by detecting the radio frequency in the range 0-ν RT (in practice the interval 0-ν RT /2 is sufficient), provided that the determination of the beat order m is unambiguous. In our case the highest frequency to be measured is 253 MHz. The 300 MHz bandwidth of a relatively cheap oscilloscope is sufficient.

τ = z/c,
Note that this bandwidth avoids the spurious peaks of the well known aliasing phenomenon.

Beat order in the Yatsenko model

In this realistic model the electric field of the FSF laser increases from broadband spontaneous emission injected into an active laser cavity containing a gain medium, a spectral filter and an optical frequency shifter. From the spontaneous emission, the succession of round trips in the cavity generates spectra of evenly spaced 2ν AO frequencies. The underlying idea is similar to that used to calculate the photon density of an FSF laser from a rate equation model [15,16]. Yatsenko calculates the second and the fourth order correlation function of the electric field G 2 and G 4 to interpret observations on the laser intensity (PD3) and the output intensity of a two beam interferometer (PD1). The authors show that G 4 is the sum of two terms: G , which, in the power spectrum, respectively generate ν RT recurrences and ν RF doublets with a separation that depends on the path difference of the interferometer. In our notation, these terms are:

)) / ( ) / ( ) ( 2 ( 16
1 ) ( ) 4 ( 3 c z t F c z t F t F G t G M M M M + + - + = ∑ ∞ -∞ = (4) ) 4 cos( ) ( ) ( ) 4 ( int ∑ ∞ -∞ = = M AO M c z M t F G t G πν (5) with ) 4 exp( ) 4 ) ( exp( 2 ) ( 2 0 2 2 2 2 2 M M M t t F L RT L M - ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ Δ - - Δ = ν τ π ν (6)
M is the round-trip number in the cavity. M 0 , the number of 2ν AO spectral elements in the laser line, is M 0 ~ Δν L /2ν AO . Note that M 0 τ RT is the effective lifetime of the photon in the active cavity.

The cosine of equation ( 5) is the key term that generates doublets. Figure 5 shows the dependence of the FFT of G 4 on the RF frequency ν and the path difference z. It is quite similar to Figure 4 of the moving-comb model. The RF frequency follows the same law: it is proportional to modulo z of the same characteristic length z 0 . The beat order must therefore be determined independently. This model shows that long-range coherence is not contained in the optical field but in the properties of intra-cavity frequency shifter. A recent experiment [17], using two dye FSF lasers with identical cavities, shows that it is indeed the phase of the AOM driver that maintains coherence.

However, although the model of Yatsenko et al. is applied to an active cavity, it does not show the over intensities corresponding to resonances at frequencies ν RF = k×2ν AO which are observed in the moving comb model (see Figure 4) and which are also observed both in the literature and in our experiments. This point is not essential insofar as we are interested only in distance measurements, but it becomes important when reflectometry measurements are considered.

New method for fast beat order determination

In the framework of the moving-comb model, references [11] and [18] give a method of determining m. Without going into detail, it consists in measuring ν RF as a function of ν AO or for two adequate values of ν AO respectively . These operations, however, do not always determine m unambiguously [11]. Furthermore, the determination is lengthy and, as discussed below, technical problems arise in order to achieve the required accuracy

The basic idea of our work lies in the fact that z 0 is of the order of several meters and that our pulsed-FSF laser is the superposition of a continuous field and a pulsed field. At a repetition rate of 2 kHz the pulse width is 32 ns. A fast photodiode (PD2) simultaneously records the two pulses from the two Mach-Zehnder arms. The pulse rise time is fast enough (<1 ns) to determine the time-delay τ p between pulses and therefore z p = cτ p with a precision δz p much better than z 0 (typically ~ 10 cm). The beat order m is then very quickly determined. This is the integer part of

z p /z 0 : ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ = 0 z z m p (7)
The fractional part of z {z} is measured on the cw overlap of I int (next section) by precise measurement of ν RF in the 0-ν RT band. Given the accuracy of z p , it is sufficient to measure the zero order beat frequency in the interval 0-ν RT /2.

-400 The proposed method seems to fail when z is equal to mz 0 within δz p . In that case the uncertainty in the measurement of m is one. Then, the unambiguous determination of m requires a second measurement. Since z is the path difference between the two arms of the interferometer, a second measurement can be done by increasing (or decreasing) the length of the reference arm by an amount greater than 2δz p . Combining these two measurements allows one to determine m unambiguously. A double-reference arm is easy to implement. This double-reference arm method works as long as δz p is much smaller than z 0 . Otherwise it is possible to use a narrower pulsed pump laser (picosecond rise time have been demonstrated with dye lasers).

-
Finally note that the AO modulator could also be gated, but the build-up of the FSF laser is too slow [8] to give an unambiguous measurement of m.

Long range measurements and coherence

In the moving-comb model, when the low-pass band is limited to ν RT , the RF-beat corresponds to beating between modes separated by Δν = Δm×ν RT , where Δm is the mode number difference. As we show below, Δν may be greater than the width of the optical spectrum Δν L . In this work we studied experimentally the transition where Δν, initially less than Δν L , becomes greater. Our FSF laser can have two line widths: 4.5 GHz with an intra-cavity etalon [8] and 30 GHz without etalon (measured respectively with a high resolution Fabry-Perot and a SOPRA 2000 monochromator). In our experimental set-up, the distance interval of 12-240 m corresponds to the RF-beat between modes separated by Δm = 2-56, that is to say, a frequency difference Δν ranging from 0.25 GHz to 15 GHz. With a width of the optical spectrum of 4.5

GHz and distances increasing from few meters up to 240 m, the transition can easily be crossed.

The path difference corresponding to this transition is:

0 z z RT L t ν ν Δ = (8)
The value of z t is 508 m and 76 m for the width of the optical spectrum of 30 GHz and 4.5 GHz respectively. Figure 7 shows the dependence of the RF-beat width Δν RF on z, for both width of the optical spectrum. It remains constant without anomaly through the transition. Throughout the path difference range, it is in very good agreement with the calculated value [11]:

RT AO L RF ν ν ν π ν 2 1 3 2 4 Δ = Δ (9)
It is interesting to note that the measurement of Δν RF also provides a simple and accurate method for determining the width of the optical spectrum of a FSF laser. 2ν AO , ν RT and Δν RF are measured directly in the FFT of I int (t). Experimentally, we find a line width of 4.2 GHz when the etalon is used. In reference [8] a width of 4 .5 GHz was measured using a Fabry-Perot interferometer of high finesse, which is difficult to align.

In the framework of the moving comb model, this experimental result shows that two modes separated by 15 GHz (z ~ 240m) interfere coherently while the width of the optical spectrum is only 4.5 GHz. It has even been shown in the literature [7] that two modes, separated by Δm = 30 000, still interfered coherently, without degradation of the spectral width. The mechanism of this long range correlation has never been interpreted within the moving-comb model. The Yatsenko model does not need to invoke the beat between widely separated modes:

the presence of the doublets ±ν RF is sufficient to interpret our results.

Precision

It is interesting to compare the OFDR and FSF laser interferometry techniques. OFDR uses a frequency scanned single-mode laser. Today, OFDR is no longer limited by the coherence length of the laser. Commercial lasers with line widths below 1 MHz yield coherence lengths of several hundred meters. The limitation comes from the technically available chirp rate and from the lack of linearity of scanning. Moreover, in OFDR the maximum measurable distance z max and absolute accuracy δz are linked by the relation (assuming a perfectly linear scan) [19]:

γ δ 2 max c z z = ( 10
)
where γ is the chirp rate. For example, a distance of 1000 m measured with an accuracy of 10 Using an FSF laser changes the issue radically. The chirp-rate can be colossal and the chirp perfectly linear (if the optical cavity length and the acoustic frequency are kept constant).

Another remarkable property is the decoupling between precision and maximum distances. It has been demonstrated that the RF-doublets exist for path differences much larger than c/Δν L , which allows the laser line to be broadened to increase the distance accuracy.

Figure 7 depicts the widths of RF-beats Δν RF in good agreement with formula (9). A width of 30 GHz can already give a resolution of about 100 microns. As the beat order is determined unambiguously (dm = 0), the distance accuracy is given by:

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + = RT RT RF RF RT RF AO AO d d z z d z dz ν ν ν ν ν ν ν ν 0 (11)
As our AO modulator driver is not temperature controlled, the stability of the acoustic frequency ν AO is only about 3×10 -5 . It is then measured in real time with a high resolution frequency counter having an accuracy of 2×10 -7 . ν RF and ν RT are measured in the FFT of I int with the oscilloscope (TDS 3034B), which has an accuracy of 2×10 -5 . Figure 8 shows the dependence of the precision of our measurements on the distance z (curve a of Fig. 8). An accuracy of 10 -6 is achieved for long distances z > 50 m. At short distances, the accuracy is dominated by the measurement of ν RT and ν RF . At long distances, it is dominated by ν AO . Techniques named Oven Controlled Crystal Oscillator (OCXO) and Rubidium Crystal Oscillator Controlled (RCBC) can easily stabilize the RF frequency applied to the AO with accuracies ranging from 10 -6 to 10 -10 . With an acoustic frequency accuracy of 2×10 - 8 (commercial), an accuracy of 10 -7 is reached for distances above half a kilometer (curve b of Fig. 8). At shorter distances, the accuracy of ν RT and ν RF must also be improved. It is not enough to increase the precision of the spectrum analyzer (temperature stabilization ...), since the laser line must also be broadened. In our laser configuration, broadening by a factor 3 is possible. The goal of an accuracy of 10 -7 is achievable for distances greater than tens of meters with a laser line-width of about 100 GHz (curve c of Fig. 8). Yatsenko et al. [START_REF] Ogurtsov | [END_REF] have showed by injecting a single-mode laser that higher signal to noise can be obtained. However, for accuracies better than 10 -7 , it becomes necessary to measure independently the index of refraction of the air. Methods using frequency combs from a femtosecond laser are under development [22]. For long distance measurements, the power of FSF laser interferometry lies in the fact that the accuracy is essentially a matter of the electronic limitations of the AO driver, which can be easily solved for a few thousand dollars.

V Conclusion

The output signal of a Mach-Zehner injected by an FSF laser allows measurement of long distances z:

{} z mz z + = 0 ( 12
)
The beat-order m and the fractional part {z} must be determined separately. The interest of our pulsed-FSF laser lies in the superposition of a pulsed and a cw field. The first determines m unambiguously and the second determines the fractional part {z} with precision. z 0 is a metric that depends only on the acoustic frequency ν AO , which may be very accurate. In this work, z 0 is approximately 4.29 m, but, in the configuration of reference [12] , which uses two AOs used in substrative-frequency, z 0 can be much larger. Typically with ν AO = 0.2 MHz, z 0 is about 750 m.

Up to this distance, measurement of the zero order RF-beat is sufficient. However, it requires a precision of the frequency ν AO that is at least two orders of magnitude better than that considered in Figure 8. In that case, to reach an accuracy of 10 -7 the stabilization technique RCBC then becomes necessary.

This work also shows that the moving-comb picture should be abandoned because interferometric long-range measurements lead to a paradox that has no physical explanation: two modes cannot interfere unless they coexist .

  frequency doubled VANADATE laser (VERDI/Coherent) and the dye-cell (C) is pumped by a pulsed frequency doubled YAG laser operating at a repetition rate of 2 kHz with pulse duration of 35 ns (Navigator II/Spectra Physics). Both are quasi-longitudinally pumped. The acoustooptic shifter (AO) operates at an acoustic frequency ν AO of 35 MHz. The cavity is closed on the first diffraction order of the AO. The only selective elements of the cavity are: a three-quartzplate Lyot-filter (L) and an etalon (E) (with a free spectral range of 400 GHz and a 40% reflection coefficient on each side). Then, our FSF laser can have two line widths: 30 GHz and 4.5 GHz respectively. The AO also acts as a broadband filter through the grating that is generated. This arrangement yields a single line and a cavity free spectral range ν RT of 253 MHz.The use of a Michelson interferometer creates additional RF-beats and intra-cavitydisturbances. A Mach-Zehnder configuration avoids feedback of the beam to the output mirror of the FSF laser. A first beam splitter (BS1) reflects two 4% beams. The intensity and power spectrum of the first beam are analyzed using a fast photodiode (PD3). The second beam is injected into the reference arm of the Mach-Zehnder. The optical path of the transmitted beam is elongated in a White cell of focal length 3 m. The output beam of the White cell is superimposed on the reference beam through a 50% beam splitter (BS2). One advantage of the White cell is the mode matching of the two beams. Use of a pinhole (PH) allows perfect superposition whatever the path difference, which is adjusted by horizontal movement of mirror M. The length of the second arm of the Mach-Zehnder can be varied easily from 12 m to 240 m in steps of approximately 12 m. Three fast photodiodes are used (rise time < 1 ns). The photodiode PD1 records the interferometric signal I int . As will be seen later, the photodiode PD2 is used to measure the RF-beat order. The signals from PD1 and PD3 are filtered and amplified (36 dB, frequency bandwidth: 50 kHz to 1.5 GHz). The three signals are analyzed using an oscilloscope with FFT capability (Tektronix TDS 3034B) having a precision time base of 2×10 -5 . The frequency of the AO shifter is measured in real time by a frequency counter with an accuracy of about 2×10 -7 (Racal Dana 1992 including a crystal oven).

Fig. 2

 2 Fig.2

Figure 2a and 2b

  Figure 2a and 2b show respectively an expansion of the laser intensity I(t) (PD3 signal)

Fig. 3 Figure 3

 33 Fig.3

  Fig. 4

Figure 4

 4 Figure 4 depicts the FFT dependence of I int (t) on frequency ν and distance z. We see

  Fig. 5

Fig. 6 Figure 6

 66 Fig. 6

  Fig. 7

  Fig.8

Acknowledgments

We thank the LIPhy laboratory and the CNRS for funding this project. The author is very grateful to E. Geissler for his contribution in reading the paper.