Frédéric Camillo

Eddy Caron

Ronan Guivarch

Aurélie Hurault

Cristian Klein

Christian Pérez

Diet-ethic: Fair Scheduling of Optional Computations in GridRPC Middleware

Keywords: HPC, GridRPC, malleable applications, Grid'5000 HPC, GridRPC, applications malleables, Grid'5000

Most HPC platforms require users to submit a pre-determined number of computation requests (also called jobs). Unfortunately, this is cumbersome when some of the computations are optional, i.e., they are not critical, but their completion would improve results. For example, given a deadline, the number of requests to submit for a Monte Carlo experiment is difficult to choose. The more requests are completed, the better the results are, however, submitting too many might overload the platform. Conversely, submitting too few requests may leave resources unused and misses an opportunity to improve the results. This paper introduces and solves the problem of scheduling optional computations. An architecture which auto-tunes the number of requests is proposed, then implemented in the DIET GridRPC middleware. Real-life experiments show that several metrics are improved, such as user satisfaction, fairness and the number of completed requests. Moreover, the solution is shown to be scalable.

Introduction

High-Performance Computing (HPC) resources, such as super-computers and clusters, are managed by resource management systems, such as batch schedulers [START_REF] Feitelson | Parallel job schedulinga status report[END_REF]. In order for a user to do computations on such resources, she has to submit a predetermined number of requests (also called jobs). For example, in order to execute a Parameter-Sweep Application (PSA), users generally submit one request for each of the parameters that are to be explored. Otherwise, they can coalesce multiple parameters in a single request, as done using the pilot job abstraction [START_REF] Caron | Definition, modelling and simulation of a grid computing scheduling system for high throughput computing[END_REF]. After all requests have completed, the user gathers the results and analyses them.

Unfortunately, choosing the requests to submit is cumbersome to do in advance for applications which have optional computations, i.e., computations that are not critical to the user, but their completion would improve results. For example, a widely used method to test the numerical stability of complex simulations is sampling-based uncertainty analysis [START_REF] Helton | Survey of sampling-based methods for uncertainty and sensitivity analysis[END_REF], such as Monte Carlo experiments. Applications range from aerospace engineering to validating nuclear power plant design. At its core, the method consists in varying input parameters and studying the changes in the output parameters. The larger the number of tested input parameters, the better the quality of the results are. Hence, a typical user would like to test as many parameters as possible before a given deadline.

To run such computation on an HPC platform, the user would have to choose a number of requests to submit. If too many requests are submitted, then the resources are over-utilized, preventing other scientists from completing their simulations in due time. If too few requests are submitted, resources might be left idle, thus, the user lost an opportunity to improve her results. Hence, the user faces the difficulty of choosing the number of requests to submit.

Given the current platforms, finding a solution to this problem is difficult. An attempt at solving it has been done in the context of Cloud computing. Amazon proposes spot instances [START_REF]Amazon ec2 spot instances[END_REF], which are virtual machine instances that can be terminated whenever the Cloud manager chooses to. Spot instances can be used to contain optional computa-tions, as opposed to HPC instances [START_REF]High performance computing (HPC) on Amazon web services[END_REF] which contain mandatory computations. But even such an approach does not guarantee fairness. Intuitively, there is no guarantee that the system balances resources among the optional computations of each user.

This paper introduces and solves a new scheduling problem: fair scheduling of optional computations. Our contribution is three-fold: first, we present a motivating example and formulate the problem statement of this novel scheduling problem; second, we present a platform architecture which efficiently solves this problem; third, we evaluate our approach and show through real experiments its feasibility using a production-level GridRPC [START_REF] Seymour | Overview of GridRPC: A remote procedure call API for grid computing[END_REF] middleware called Diet [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF]. Results show that user unhappiness can be reduced to 0 and that unfairness can be decreased by up to 150 times.

The remaining of the paper is organized as follows: Section 2 presents a motivating use-case, which is then formalized into a problem statement in Section 3. Section 4 describes an architecture which solves the stated problem, and which is evaluated in Section 5. Section 6 compares our approach with related work. Section 7 concludes the paper.

A Motivating Use-case

This section briefly presents the Grid-TLSE project and a motivating use-case called multiple threshold pivoting.

The main goal of the Grid-TLSE project [START_REF] Amestoy | Grid-TLSE: A web site for experimenting with sparse direct solvers on a computational grid[END_REF] is to design an expert site that provides easy access to many direct solvers for sparse linear systems, allowing their comparative analysis. The site assists users in choosing the right solver for their problems, appropriate values for the control parameters of the selected solver and the best computer architecture. Grid-TLSE also serves as a testbed for experts in sparse linear algebra. A computational Grid is used to execute all the runs arising from user requests, which is accessed using GridRPC. The Grid-TLSE project has started in 2002 years and is currently being used by 157 users.

Let us detail how direct solvers work. Solving a linear system of the form Ax = b usually consists of three steps: analyse, factorisation and solve. During the factorisation step of an asymmetric matrix, the matrices L and U are computed such that LU = A. In order to preserve the numerical stability (e.g., avoiding the division by a small number) pivoting can take place. One way to select the pivot is to choose a diagonal entry according to a given threshold. The selection of the threshold is important and for some values, the result of the solution of the linear system can be very bad (see Figure 1).

An often requested feature is to allow a user to run as many factorizations as possible, with different thresholds, until a given deadline is reached. If the deadline is too tight or resources are highly loaded, the system should test at least 3 thresholds, for example. In other words, the user needs to submit a few mandatory requests, which need to be solved whether the deadline is due or not, and a large number of optional requests, which the user would like to have computed, but are not as useful as to wait for their completion past the deadline.

Using GridRPC, it is difficult to choose the number of optional requests to submit to the platform. Obviously, if too few requests are submitted, the number of tested thresholds is suboptimal. If too many are submitted, the optional requests of other users might not have a chance at getting executing, which would be unfair. Even worse, the platform might be so overloaded that the other users might need to wait past their deadlines for the completion of the mandatory requests, which makes them unhappy.

Problem Statement

This section formalizes the problem. First, the resource and user models are described. Second, the metrics that the system has to optimize are defined.

Resource Model

Let the platform be composed of n R resources, which are homogeneous (a computation request has the same execution time on any resource), static (resources are neither added nor removed during execution) and reliable (resources do not fail).

This model is somewhat simple but still applicable in many cases. For example, it fairly well approximates production-level multi-cluster systems such as the Decrypthon grid [START_REF] Bard | Décrypthon grid -grid resources dedicated to neuromuscular disorders[END_REF]. Nevertheless, these assumptions will be relaxed in future work.

User/Application Model

Let the platform be used by n U users. A user i enters the system at time t (i) 0 (which is not known in advance) and needs to solve at least n (i) min (also called mandatory requests) and at most n (i) max requests (including mandatory and optional requests).

The user sets a "tentative" deadline d (i) which acts as follows. If at time d (i) all mandatory requests are completed, the remaining optional requests are cancelled and the user exits the system. Otherwise, the user waits until all mandatory requests are completed, even if this means waiting past the deadline. In the latter case, optional computations can still be executed until the last mandatory request finishes. In other words, the hard deadline is equal to the maximum between the user-provided deadline and the last completion time of the mandatory requests.

To completely characterize the workload, the execution times need to be modeled. We consider that the requests of user i are homogeneous, having the same execution time T (i) . This is a reasonable approximation for the targeted use-cases (Figure 1), as well as many parameter-sweep applications [START_REF] Sonmez | Scheduling strategies for cycle scavenging in multicluster grid systems[END_REF]. However, execution times are not known in advance.

Inria

Metrics

To evaluate how well a system deals with a workload, the following metrics are of interest: the number of unhappy users, unfairness and the number of completed requests.

The number of unhappy users is the number of users who did not complete their mandatory requests before their deadline d (i) . These users had to wait additionally, after the tentative, user-provided deadline. Ideally, the number of unhappy users should be 0, provided the workload permits such a solution.

Before defining fairness, let us introduce some helper notations. For each user i, the amount of deserved resources r (i) deserved (i.e., the amount the system should allocate the user) is computed as follows. The time is divided into time-slots, such that, during each time-slot j of start-time S (j) and endtime E (j) , the set of users inside the system U (j) is constant:

U (j) = { i : ( t (i) 0 ≤ S (j) ) ∧ ( E (j) ≤ d (i)
)}

The resource area (number of resources times duration) available during that time-slot is divided equally among the among users in U (j) :

r (i) deserved = ∑ j:i∈U (j) n R • ( E (j) -S (j) ) #U (j)
Next, for each user i, the satisfaction s (i) is defined as the amount of resources the system allocated her r

(i)
allocated over the amount of resource she deserved r (i) deserved . A satisfaction 0 ≤ s (i) < 1 means that the user i was allocated fewer resources than deserved, while s (i) > 1 means that the user i was allocated more resources than deserved. Ideally, the satisfaction of all users should be 1, i.e., they are allocated as many resources as deserved.

Having all prerequisites, let unfairness be defined as the difference between the maximum and the minimum among the user satisfactions:

unfairness = max i s (i) -min i s (i)
We refrained from defining unfairness as an average, for the same reasons as stated in [START_REF] Yuan | PV-EASY: a strict fairness guaranteed and prediction enabled scheduler in parallel job scheduling[END_REF]: users tend to be more sensitive to fairness than to performance, thus, the former should be more like a law Figure 2: Diet-ethic architecture or a guarantee that the system is heavily penalized for breaking. Ideally, unfairness should equal 0.

Finally, the number of completed requests is a performance-oriented metric, computed as the sum of all the requests (mandatory and optional) belonging to any user that have completed.

To sum up, we aim at finding a system, which minimizes the number of unhappy users, minimizes unfairness and maximizes the number of completed requests, in this order. Note that, the three presented metrics can only be computed a posteriori, after all users exited the system.

Diet-ethic

In this section, the Diet-ethic platform for fair scheduling of optional computations is presented. First, the architecture is described in an abstract, implementation-independent manner. Second, our implementation of Diet-ethic in the productionlevel Diet GridRPC middleware is detailed.

Diet-ethic Extension

Diet-ethic is an extension over a client-server architecture. The clients (representing the users of the system) are resource consumers that generate computational requests, while the servers are resource providers, doing computations on behalf of the clients. Clients and servers are connected through a middleware, that implements a discovery mechanism.

Before describing Diet-ethic, let us highlight some design choices. First, we chose to keep the server-side scheduling algorithm simple and make servers unaware of the deadlines of the users. This choice has been taken so that clients, which are under the control of the user, be able to evolve their scheduling algorithms separately from the function-ality offered by the server. For example, a future version of Diet-ethic might schedule workflows containing optional computations, without having to change the servers.

Second, the number of requests stored in the platform have to be minimized. This is important, since, for the targeted use-cases, any user could alone fill the whole platform with her optional requests. Therefore, having a system in which all users submit all their requests to the system would clearly not scale.

Let us now describe the Diet-ethic architecture consisting of a server-side queuing module and a client-side request dispatcher (Figure 2), that are described in the next sections.

Server-side Queuing Module

When a request arrives at a server, it is not immediately solved, but is added to a local queue. The queue is regularly checked to determine which requests should be started, cancelled (erased from the queue) or killed (prematurely terminated after it has been started). The queued requests are ordered as follows:

1. mandatory requests have priority over optional requests; this ensures that the number of unhappy users is minimized; 2. started requests have priority; otherwise resources might be wasted as requests are killed and computations completed so-far are lost.

In the end, this improves the number of completed requests, paying a small price on fairness; 3. mandatory requests are order by submit time, i.e., the First-Come-First-Serve (FCFS) scheduling strategy is used; this allows users who arrived first in the system to get a better chance at completing their mandatory requests before the deadline, thus decreasing the number of unhappy users; 4. requests of users who had the fewest allocated resources so far have priority: this ensures server-local fairness; 5. for users having the same amount of allocated resources (such is the case when users enter the system as the same time) a request is randomly chosen. This ensures global fairness, as each server most likely choses to execute the request of a different client.

If a request gets to the front of the queue it is started. Otherwise, if sorting moves a request from the front of the queue, it is killed. For example, if a user submits a mandatory request to a server which is currently executing an optional request, the latter is killed. Requests can be cancelled on the client's demand.

Client-side Request Dispatcher

On the client-side, a custom request dispatcher is required. It works in three phases: setup, monitoring and cleanup.

The setup phase starts with a resource discovery, asking the middleware to return at most n (i) max servers. Next, mandatory requests are dispatched to discovered servers-currently in round-robin. Finally, one optional request is submitted to each discovered server.

In the monitoring phase, the client enters an event-loop. It stays in this phase until all mandatory requests are completed and the deadline has not expired. When an optional request is completed, the client submits a new optional request to the server which executed the former request. As a result, as long as the user is in the system, provided n (i) max is large enough, each server has at least one optional request in the queue, ready to be executed.

Finally, in the cleanup phase, the client cancels all requests that have been submitted but not yet completed. Note that, this phase is entered when all mandatory requests have been completed, thus, only optional requests need not be cancelled.

Having describe the architecture, let us pass on to implementing it in an existing GridRPC middleware.

Diet Middleware Architecture

Let us first describe the Diet GridRPC middleware architecture, which we have extended for optional computation support.

To simplify access to HPC resources, various programming models have been proposed. One of them is the GridRPC API [START_REF] Seymour | Overview of GridRPC: A remote procedure call API for grid computing[END_REF], which has been standardized inside the Open Grid Forum (OGF) [START_REF]Open grid forum[END_REF]. At its core, it extends the familiar Remote Procedure Call (RPC) paradigm to Grid environments. Hence, the end-users' client-server applications can GridRPC offers mechanisms to make synchronous and asynchronous calls to a service. For the asynchronous case, clients can wait in a blocking or nonblocking mode for the completion of a given call to complete. Being based on a client-server model, testing Diet-ethic in this context seemed a natural choice.

Let us present how GridRPC is implemented in Diet [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF]. The Diet component architecture is hierarchically structured for improved scalability as illustrated in Figure 3. The Diet toolkit is implemented in CORBA [START_REF]Common object request broker architecture (CORBA/IIOP)version 3.2[END_REF] and thus benefits from the many standardized, stable services provided by freely-available and high performance CORBA implementations.

The Diet framework has several elements. A Client is an application that uses the Diet infrastructure to solve problems using a GridRPC approach. A SeD (Server Daemon) acts as the service provider, exporting functionality through a standardized computational service interface; a single SeD can offer any number of computational services.

The third element of the Diet architecture, agents, facilitate the service location and invocation interactions of clients and SeDs. Collectively, a hierarchy of agents provides higher-level services such as scheduling and data management. These services are made scalable by distributing them across a hierarchy of agents composed of a Master Agent (MA) and several Local Agents (LA).

A typical Diet interaction goes as follows: (1) First, the client enters the system and sends a discovery message with some information regard-ing the request to be computed to the master agent.

(2) Next, the message is propagated from the master agent to the SeD through local agents. The message eventually reaches all SeDs, (3) which reply with an estimation vector: a set of values describing how fit they are for solving this particular request. Depending on the implementation of a service, an estimation vector might contain information such as CPU power, amount of RAM, estimated completion time of the request, number of queued requests, etc. ( 4) At each level of the agent hierarchy the estimation vectors are aggregated, so that the master agent only has to deal with a small amount of them. ( 5) Finally, one or more estimation vectors are returned to the client, which chooses a suitable SeD. [START_REF] Seymour | Overview of GridRPC: A remote procedure call API for grid computing[END_REF] The request with all the data necessary to solve the problem is sent directly from the client to the SeD.

Let us highlight where scheduling decisions are taken. First, SeDs decide what values to put in an estimation vector. This way, a SeD can make itself more or less preferred for solving a problem. Second, agents throughout the hierarchy aggregate and filter SeDs based on these estimation vectors. For example, only the top 10 least loaded SeDs are returned to the parent agent, thus leaving out overloaded SeDs. Third, clients receive estimation vectors from several SeDs, out of which they may choose a SeD.

To sum up, Diet already implements many prerequisites, such as service calls, scalable scheduling and data management. This allowed us to implement Diet-ethic with minimal effort.

Optional Computation Requests in Diet

Besides the addition of a request dispatcher and a queuing module, the following changes had to be made to implement Diet-ethic on top of Diet.

First, three extensions to the GridRPC API have been needed.

(1) The grpc_discover function allows clients to discover servers in the system.

The function accepts two parameters: the name of the service and the maximum number of servers to return.

(2) The grpc_function_handle_set_optional function allows clients to declare a request as optional. (3) The grpc_wait_any_until function has been implemented, which is an extension to grpc_wait_any allowing a client to specify a timeout. The function block until either a GridRPC request completes or the timeout expires, similarly to the POSIX™ select or poll system calls.

Second, the client-server communication protocol had to been extended, so that each request is tagged with the user it belongs to. This is necessary information allowing servers to ensure fairness among different users. The current implementation assumes that users are honest and do not attempt to falsify their identity. A future implementation will include authentication, thus making sure that requests can be securely associated with a user.

Thus, we obtained a production-ready implementation which we shall use to evaluate the Diet-ethic architecture in the following section.

Evaluation

This section evaluates the proposed architecture. First, we show the gains that can be made with Diet-ethic by comparing it to a standard system which has not been designed to support optional computations. Second, we show that the architecture is scalable. We would like to highlight that all experiments have been done on a real platform. Finally, we discuss the benefits that can be observed by an end-user.

Gains of Supporting Optional Computations

Let us consider increasingly complex scenarios and make a comparative analysis between Diet-ethic and a system without optional computation support. To this end, we used the Diet middleware as it was before our contribution: the SeDs serve incoming requests using the FCFS policy, without distinguishing mandatory from optional requests. On the client-side, we implemented the following behaviour. When a client i enters the system it has to blindly choose n

(i)
submit , a number between n

(i) submit -n (i)
min optional requests (in this order). Then, it waits for the mandatory requests to finish. If the deadline has not expired, it sleeps until the deadline is reached. Finally, it gathers the results of all completed requests and cancels the remaining optional requests submitted to the system. To simplify the analysis of the results, all clients "guess" the same value n submit . For briefness, this system shall be call the legacy system.

Before detailing the scenarios, let us present the common methodology. The platform consists of 1 MA and n R = 10 SeDs. The SeDs only implement a sleep service, i.e., the service itself consumes no CPU nor network bandwidth. The platform is used by n U = 10 identical clients with their parameters chosen as follows: in order to make experiments as useful as possible, but at the same time reduce the time it takes to complete them, we have chosen to "compress" the time: 8 hours are normalized to 100 s. Therefore, we set the execution time T (i) = 1 s and the deadlines d (i) = 100 s. These values are large enough compared to the time it takes to take scheduling decisions, yet small enough so that the time of experiments be reasonable. Next, we set the number of mandatory requests n (i) min = 3 and the number of total requests n (i) max = 1000. These parameters have been chosen so that the following conditions be met:

• there is a solution which makes all users happy; • each user can generate enough optional computations to fill all resources.

The above conditions are the ones in which our system is the most interesting to be studied. Otherwise, if the number of mandatory computations is too high, the platform has no choice but to schedule them in a FCFS fashion, being forced to make some users unhappy. Also, if the number of optional requests is too low, its fairness properties cannot be highlighted.

The metrics we are interested in are those presented in Section 3.3. All measurements have been done at least 10 times and, since we found deviations to be small, we chose to make graphs more readable by only plotting the median.

The systems are compared in 5 different, increasingly complex scenarios, which are described in detail in the next sections.

Night-time Simultaneous Submissions

Let us start with a simple scenario. Users want to do computations during the night, so that their re- Figure 4 shows that Diet-ethic managed to find a solution with no unhappy users, with good (almost ideal) fairness, while maximizing the number of completed requests. Regarding the legacy system, one observes that, if n submit is small, the resources are not filled with computation requests, thus, the number of completed requests is suboptimal. However, if n submit is high enough, on average, the legacy system behaves fairly well. This is due to an experiment artifact that, since all users enter the system at precisely the same moment of time, their requests favorably interleave, therefore, the FCFS policy is mostly finding the optimal solution: all mandatory requests are started first, followed by the optional requests.

Night-time Consecutive Submissions

However, in production systems, users never enter the platform at exactly the same time. In fact, the time the users enter the system might be quite different: some people leave work earlier, others later. Their deadlines are about the same, since those who leave work earlier, often come earlier the next day. To model this scenario, we insert a very small inter-arrival gap t Figure 5 shows that, unless all users guess the ideal solution (that of each user submitting exactly n ideal = 100 requests), the legacy system either does not manage to optimize the number of completed requests (if n submit < n ideal ) or makes users unhappy (if n submit > n ideal ). The latter happens because the FCFS policy fills resources with optional requests of users who arrived early in the system. Therefore, the mandatory requests of users who arrive later start later and can be delayed past the tentative deadline. A similar observation applies to fairness: the FCFS policy favors users who enter the system early, instead of trying to balance requests equally among them.

In contrast, since Diet-ethic distinguishes mandatory and optional requests, it makes sure that mandatory requests have priority over optional ones. Also, instead of favoring users who arrive early, resources are allocated equally among the optional requests of the users. In the end, Diet-ethic improves fairness up to 150 times and behaves as if all users chose the ideal number of requests to submit, but without requiring the users to guess this value.

Day-time Submissions with Regular Arrivals

Let us pass on to a different scenario: day-time submissions. During the day, the users to not enter the system during a short time interval, but are separated by significant inter-arrival times. To start, we study a simpler scenario, in which the inter-arrival time between consecutive clients is constant.

To model this, we took the previous scenario and Except arrival times, all other experimental parameters are kept the same. When contrasting the two scenarios, the main difference is that, in the previous one all clients have entered the system before the mandatory requests of the first client are completed. In contrast, in the current scenario, mandatory requests of a client are already completed by the time the next client arrives in the system. One could say that the previous scenario resembles an off-line scheduling problem (i.e., all requests are known in advance, decisions can be taken in advance), whereas the current scenario resembles an on-line scheduling problem (i.e., the system needs to adapt to arriving requests).

Figure 6 shows the results for this scenario. One can observe that the legacy system behaves best for n submit = 190. No users are unhappy, unfairness is low and the number of completed requests is the highest, even when compared to Diet-ethic. The latter happens because, when a new client enters the system, Diet-ethic immediately starts its mandatory requests, killing optional request if necessary. The so-far done computations are not completed, thus reducing the number of completed requests. Nevertheless, one observes that Dietethic's solution has a lower (near-ideal) unfairness and the number of completed requests stays competitive to the legacy system (1842 vs. 1890: ≈ -2.5%).

However, on a real platform guessing the best number of requests n (i) submit each client i should submit is difficult, as it depends on a number of factors, such as the number of resources, arrivals and requirements of other users. Some of this information is unknown at the time a client enters the system. When looking at the results for n submit = 190, one observes that the legacy system is outperformed by Diet-ethic. As in previous scenarios, if fewer requests are submitted, then the number of completed requests is suboptimal. Deviating in the other direction, if too many requests are submitted then unfairness increases.

Interestingly, as the number of submitted requests increases, the number of completed requests slightly decreases. This happens because, increasing n submit also increases the probability that clients launched earlier still have executing requests in the system by the time their deadline is reached. These requests are killed, thus are not completed.

In contrast, Diet-ethic auto-tunes itself and finds a good solution, without requiring the user to guess a good number of requests to submit.

Other Day-time Scenarios

In order to make sure that the proposed system is well-behaved in more realistic cases, let us present two more scenarios. First, we drop the assumption that the interarrival time between consecutive clients is constant. Instead, the arrivals are assumed to obey the wellknown and widely recognized diurnal cycle [START_REF] Feitelson | Workload Modeling for Computer Systems Performance Evaluation[END_REF]. To model this, we took the polynomial P proposed in [START_REF] Calzarossa | A characterization of the variation in time of workload arrival patterns[END_REF], scaled its input to the [0, 100] seconds interval and used the output value as follows: at each second t, the probability of launching a new client is P (t)/10. The division by 10 was made so as to keep the number of clients in the system of the same order-of-magnitude as in the other scenarios.

Second, we give each client a different execution time, by choosing T (i) uniform randomly in [0.75, 2]. Requests generated by the same client are still homogeneous. The arrivals are considered to obey the diurnal cycles as in the above paragraph.

For both of these scenarios (figures 7 and 8), the same observations can be made as in previous sections. There is a value of n submit in which the legacy system behaves well, however, this value is difficult to compute a priori in a real system. In contrast, Diet-ethic auto-tunes itself and manages to minimize the number of unhappy users, minimize unfairness and maximize the number of completed requests.

Scalability

In order to assess the scalability of our solution and measure the overhead, we have designed the following experiment. We reserved the whole Lyon site on the Grid'5000 experimental platform [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] (Ta- Experiments has been done as follows: first, 1 MA has been deployed on the MA node. Second, SeDs have been deployed on each core of the bi-processor SeD nodes, totalling n R = 2 × 69 = 138 SeDs. Finally, on the client node, n U = 100 client have been launched simultaneously with the parameters: n

(i) min = 3, n (i) max = 10000, d (i) = 100, T (i) = 1.
As a reference, traces from the Grid Workload Archive [START_REF] Iosup | The grid workloads archive[END_REF] contains less that 100 users per day.

Besides the metrics presented in Section 3.3, we measure the CPU utilization on the client node, the MA node and one of the SeD nodes. On the client node, we have been careful to filter out CPU usage due to process creation and destruction. The SeDs implement a simple "sleep" service, which does not do any computations. Therefore, the measured CPU usage represents the overhead our system incurs for managing computational requests.

The metrics can be found in Table 2. They show that there are no unhappy users and that unfairness is low. Also, the number of completed requests is 13605, which, compared to the maximum of 13800 requests that could have been completed by 138 SeDs in the 100 s deadline, represents 98.6%. Hence, we conclude that the system managed to optimize the targeted metrics, even under stress conditions.

Let us now take a deeper look at the behaviour of the system and study the CPU usage overhead during the experiments (Figure 9). First, let us observe that the measured CPU usage before launching the clients and after the clients finished is below 1%, thus indicating a low measurement noise.

Next, one can clearly distinguish the three phases of the clients (Section 4.1.2): setup, monitoring and cleanup.

The setup phase takes about 13 s from t = 0 to t = 13. During this phase the CPU usage on the client node is somewhat high, due to all clients simultaneously discovering SeDs, then submitting requests to all of them. Discovery is handled by the MA, on which one observes a peak in CPU usage. On the SeD node, the CPU usage is negligible, being less than 3%.

During the monitoring phase, which lasts from t = 13 to t = 100, one observes that the CPU usage stays relatively low on all nodes. The most stressed is the client node, as the client applications have to submit 138 requests/s to keep SeDs busy. The MA is idling, since it is not participating in this phase, while the CPU usage on the SeD node is negligible.

Finally, during the cleanup phase, the CPU usage on the client node tops at 100%, as cancellation requests are sent by all clients, simultaneously to all SeDs. Again, the MA is idling, while the CPU usage on the SeD node is still fairly low (< 5%).

Note that the scalability experiment is extreme. The clients arrive simultaneously, which is unlikely in real systems and the execution time is short (1 s). For comparison, the average job inter-arrival time on the LCG grid is 5 s, whereas the average runtime is 2.5 h [START_REF] Iosup | The grid workloads archive[END_REF].

To sum up, the CPU usage on the SeD nodes is negligible when a sleep service is used. This means that our system involves low overhead and that SeDs can perform useful computations. The CPU usage on the client node is high during the setup and cleanup phase, nevertheless it managed to generate enough requests, so as to keep SeDs busy. The MA did not prove to be a bottleneck in these experiments.

End-User Perspective

Now that we evaluated Diet-ethic with a synthetic "sleep" service, we return to the motivating application (Section 2) and discuss the advantages that an average end-user observes. We have implemented a working prototype in order to test an initial version of Diet-ethic against Grid-TLSE.

Let us briefly describe what changes were necessary. Grid-TLSE is composed of an upper layer ALTO, responsible for interpreting high-level user requests and aggregating results, and a lower layer BASSO, responsible for communicating with a GridRPC middleware and performing computations. ALTO had to be extended so as to accept a variable number of results for every request sent to BASSO. Previously, ALTO was coded so as to accept a pre-computed number of results for each request, which is no longer true, since the number of completed requests (and, as a consequence, the number results returned to ALTO) depends on the status of the platform. As to BASSO, the behavior described in Section 4.1.2 has been implemented.

Previously, when a user wanted to solve a linear system, she had to choose the number of thresholds to test. This was done using a combination of trialand-error and guesswork. The user had to know approximately the number of available resources and the time a solve takes. If the user overestimated the number of thresholds, she would manually cancel the computations. Conversely, the user underestimated, she would have to manually relaunch the computations with a new set of thresholds.

In contrast, thanks to our contribution, a working prototype showed that the user only has to specify the minimum and the maximum number of thresholds to test, and a deadline. The system automatically tests as many thresholds as to respect the constraints imposed by the users.

Related Work

This section reviews related work from areas of realtime systems and malleable applications.

Real-time Systems

A system is considered real-time if it needs to guarantee a certain response time, i.e., there are tasks that need to be completed before a given deadline. Based on their constraints, real-time systems can either be hard, i.e., missing a deadline leads to system failure, or soft, some deadlines can be missed. Furthermore, the generation of the tasks can be either sporadic, i.e., the arrival time of tasks is not known in advance, or periodic.

For each case, various algorithms have been proposed. For example, Earliest Deadline First (EDF) is an algorithm for hard real-time systems with sporadic tasks. The next task to be executed is the one Inria that is closest to its deadline. It has been shown [START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF] that under certain conditions, EDF is optimal: if there exists such a solution, EDF always find a schedule so that all of the tasks meet their deadlines. However, EDF is considered to be expensive to compute, so more efficient ways of computing a schedule have been studied. If tasks are periodic, one can pre-compute an efficient schedule by simulating the behavior of EDF for a certain period of time. Moreover, having information about all future tasks allows to find a schedule that is not only valid, but also fair [START_REF] Baruah | Fairness in periodic real-time scheduling[END_REF].

This article shares many concepts with the cited works, such as guaranteeing deadlines and improving fairness. However, one of our base assumptions is that there are not enough resources to execute all tasks in the given deadlines. The question is then which tasks to sacrifice, in order to keep users satisfied.

Let us now review the field of soft real-time scheduling. The (m, k)-firm deadlines problem [START_REF] Ramanathan | A dynamic priority assignment technique for streams with (m, k)-firm deadlines[END_REF] consists in finding a schedule in a real-time system with periodic tasks, so that at least m out of k consecutive tasks meet their deadline. Various algorithms have been proposed that basically divide the tasks into mandatory and optional [START_REF] Quan | Enhanced fixed-priority scheduling with (m,k)-firm guarantee[END_REF].

Our problem shares some vocabulary (mandatory and optional), but differs in several ways. First, arriving tasks are not periodic. In fact, both their arrival-time and their execution-time are unknown to the platform. Second, it is the user who decides which tasks are to be considered mandatory and which are to be considered optional. Third, the deadline is considered for a group of tasks (i.e., those belonging to the same user) and not for every task individually. Therefore, the solutions brought by cited works are not directly applicable to our problem statement.

Malleable Applications

An application is said to be malleable if it can change its resource usage as requested by the scheduler [START_REF] Feitelson | Towards convergence in job schedulers for parallel supercomputers[END_REF]. This can be done in order to improve resource utilization or decrease response times [START_REF] Hungershofer | On the combined scheduling of malleable and rigid jobs[END_REF]. How to write malleable applications [START_REF] Maghraoui | Dynamic malleability in iterative MPI applications[END_REF][START_REF] Buisson | A framework for dynamic adaptation of parallel components[END_REF] and how to add scheduler support for them [START_REF] Buisson | Scheduling malleable applications in multicluster systems[END_REF][START_REF] Cera | Supporting malleability in parallel architectures with dynamic CPUSETs mapping and dynamic MPI[END_REF][START_REF] Sudarsan | ReSHAPE: A framework for dynamic resizing and scheduling of homogeneous applications in a parallel environment[END_REF] has been extensively studied.

Our solution can be considered yet another scheduling problem that is addressed using mal-leability. However, all of the cited works aim at using malleability to improve some kind of metric, but, in the end, the computations that are executed are always the same, no matter how resources are allocated to the applications. In contrast, to our knowledge, we are the first to propose for a malleable application to adapt to the state of the resources by also changing the computations it does. If many resources are available, the application produces more accurate results, whereas if few resources are available, the application guarantees at least a minimum accuracy.

Parameter-sweep applications are one of the most common classes of malleable applications [START_REF] Sonmez | Scheduling strategies for cycle scavenging in multicluster grid systems[END_REF]. They consist of many sequential tasks, which are relatively short when compared to the executiontime of the whole application. On one hand, this is an advantage, since the scheduling granularity is relatively small, allowing much freedom. For example, a task can be killed and restarted later, possibly on another resource, without losing significant computations. On the other hand, due to the small granularity, one has to take extra precautions not to overload the system.

To solve the above issue, the DIRAC workload management system [START_REF] Casajus | DIRAC pilot framework and the DIRAC workload management system[END_REF] proposes a solution based on the pilot job abstraction. Pilot jobs are container jobs that, instead of executing an actual task, launch a daemon. Once the job starts and the daemon is running, the latter connects to a centralized agent and requests tasks to execute. In DIRAC, the tasks are put in a central queue and the scheduling event is initiated by resource availability. One can say that computation requests are pulled by the resources from the centralized agent. This is in contrast to traditional usage of HPC platform (e.g., imposed by batch schedulers), in which jobs are pushed to resources. DIRAC's approach leads to a natural load balancing where each resource gets the workload matching its actual capacity. In a push approach this is usually achieved by ranking resources based on their capacity, which requires complex calculations and a reliable information system.

Our contribution borrows some concepts both from push and pull scheduling. Mandatory requests are pushed from clients to resources, whereas optional requests are pulled by resources from clients. The former allows clients to dispatch mandatory requests to the most fitting resources, whereas the latter allows to reduce the strain on the platform and produce a natural load balancing as done by DIRAC.

Two aspects differentiate Diet-ethic from DIRAC. First, a limited number of computation requests is stored on the platform, the rest being generated on-the-fly by the clients. In contrast, DIRAC requires all computational requests to be submitted to a centralized agent. Our design choice is necessary to ensure the scalability of the system, since it is possible that only a small percentage of optional requests are actually executed, thus, storing them all centrally would overload the system. Second, DIRAC takes most scheduling decisions in a centralized agent. In contrast, in Diet-ethic, each client and each server contributes to taking scheduling decisions. This can be considered an advantage, since the two entities can evolve their scheduling algorithms separately. For example, a user wanting to implement a different scheduling algorithm can change the client application, without having to wait for a platform upgrade.

Conclusion

This paper presented Diet-ethic a platform architecture to efficiently support optional computations. It can easily be implemented in any GridRPC middleware, such as GridSolve [START_REF] Yarkhan | Recent developments in GridSolve[END_REF] or Ninf [START_REF] Tanaka | Ninf-g: A reference implementation of rpc-based programming middleware for grid computing[END_REF]. Evaluation has been done using an implementation on top of the production-level Diet middleware. Real-life experiments showed that several metrics can be improved, for example user unhappiness can be reduced to 0 and unfairness can be decreased up to 150 times. Finally, the architecture was shown to be scalable.

As future work we propose improving the scheduling of mandatory requests by reallocating them to better suited servers [START_REF] Caniou | Analysis of Tasks Reallocation in a Dedicated Grid Environment[END_REF], instead of mapping them at submittal as currently done. Scheduling of optional computations could be improved by using preemption [START_REF] Li | Online optimization for scheduling preemptable tasks on IaaS cloud systems[END_REF]. Different window sizes would have to be tested to find the best scheduling.

Figure 1 :

 1 Figure 1: Example of the results output by a direct solver; backward error is defined as ||b -Ax||/||b||

Inria

Figure 3 :

 3 Figure 3: Diet architecture

  max , representing the number of requests to submit. First, it submits n (i) min mandatory and n

Figure 4 :

 4 Figure 4: Results: night-time simultaneous submissions scenario

0

  = i • 0.1 s and keep d (i) = 100 s.

Figure 5 :

 5 Figure 5: Results: night-time consecutive submissions scenario

Figure 6 :

 6 Figure 6: Results: day-time scenario with regular arrivals

Figure 7 :Figure 8 :

 78 Figure 7: Results: day-time scenario with irregular arrivals

Inria

Figure 9 :

 9 Figure 9: System overhead: CPU usage for sleep requests

  Parallel and Distributed Computing, vol. 72, no. 5, pp. 666-677, May 2012.InriaRESEARCH CENTRE GRENOBLE -RHÔNE-ALPESInovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Table 1 :

 1 The set of nodes has been divided into three: 1 client node, 1 MA node and 69 SeD nodes.

	Grid'5000 deployment for scalability ex-
	periment
	Cluster	# nodes Configuration
	capricorne	2	2×AMD Opteron 246 @ 2.0 GHz
	sagittaire	69	2×AMD Opteron 250 @ 2.4 GHz
	Table 2: Results of scalability experiment
	Unhappy users	0 ideally 0
	Unfairness		0.70 ideally 0
	Number of completed requests 13605 out of 13800
	ble 1).

RR n°7959

Acknowledgments

This work is supported by the French ANR COOP project, n • ANR-09-COSI-001 (http://coop.gforge. inria.fr). Experiments were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (https://www. grid5000.fr). Special thanks to Gilles Fedak for his insightful comments.


Fernando D Antognini

F Amaro

J M R Biraben

D Cardoso

Is the proton

Keywords: proton radius, muonic hydrogen, Rydberg constant, Planck constant, Avogadro constant

HAL is

Is the proton radius a player in the redefinition of SI based units ?

février 2011

By Charge Radius Experiment with Muonic Atom collaboration : F. Nez(1), A. Antognini(2), F.D. Amaro(3), F. Biraben(1), J.M.R. Cardoso(3), D. Covita(3), A. Dax(4), S. Dhawan(4), L. Fernandes(3), A. Giesen(5), T. Graf (6), T.W. Hänsch (2), P. Indelicato(1), L. Julien (1), C.-Y. Kao (7), P.E. Knowles (8), E. Le Bigot (1), Y.-W. Liu (7), J.A.M. Lopes(3), L. Ludhova (8), C.M.B. Monteiro(3), F. Mulhauser (8), T. Nebel (2) , P. Rabinowitz (9), J.M.F. dos Santos(3), L. Schaller (8), K. Schuhmann (5), C. Schwob(1), D. Taqqu (10), J.F.C.A. Veloso(3), F. Kottmann (11) and R. Pohl (2) (1) Laboratoire Kastler Brossel, ENS, UPMC and CNRS, 4 place Jussieu, 75252 Paris Cedex 05, France,

(2) Max-Planck-Institut für Quantenoptik, 85748 Garching, Germany, (3) Departamento de Física, Universidade de Coimbra, 3000 Coimbra, Portugal, (4) Physics Department, Yale University, New Haven, Connecticut 06520-8121, USA, (5) Dausinger and Giesen GmbH, Rotebülstr. 87 70178 Stuttgart, Germany, (6) Institut für Strahlwerkzeuge, Universität Stuggart, 70569 Stuggart, Germany, (7) Physics Department, National Tsing Hua University, Hsinchu 300, Taiwan, (8) Département de Physique, Université de Fribourg, 1700 Fribourg, Switzerland, (9) Department of Chemistry, Princeton University, Princeton, New Jersey 08544-1009, USA, 1 (10) Paul Scherrer Institut, 5232 Villigen-PSI, Switzerland, (11)Institut für Teilchenphysik, ETH Zürich, 8093 Zürich, Switzerland.

Résumé

It is recognized now that the international system of units will be redefined in terms of fundamental constants [1] [2] [3] [4] even if the occurring date is still under debate. Actually, the best estimate of fundamental constants values is given by a least square adjustment, carried out under the auspice of the Committee on Data for Science and Technology (CODATA) task group on fundamental constants. This adjustment provides a significant measure of the correctness and over-all consistency of the basic theories and experimental methods of physics using the values of the constants obtained from widely differing experiments. The physical theories that underlies this adjustment are assumed to be valid such as quantum electrodynamics (QED). Testing QED, one of the most precise theory is the aim of many accurate experiments. The calculations and the corresponding experiments can be carried out either on a boundless system (for example the electron magnetic moment anomaly) or on a bound system such as atomic hydrogen. The value of fundamental constants can be deduced from the comparison theory-experiment. For example using QED calculations [6], the value of the fine structure constant given by the CODATA mainly infers from the measurement of electron magnetic moment anomaly done in the group of G. Gabrielse [5]. The value of Rydberg constant is known from the two photon spectroscopy of hydrogen combined with accurate theoretical quantities. The Rydberg constant extracted from the theory-experiment comparison of atomic hydrogen is known with a relative uncertainty of 6.6×10 -12 [7]. It is the most accurate fundamental constant up to date. A careful analysis shows that the knowledge of the electrical size of the proton is nowadays a limitation to this comparison. The aim of the muonic hydrogen spectroscopy was to get an accurate value of the proton charge radius. However, the value deduced from this experiment is in contradiction with the other less accurate determinations [8]. The problem is known as the proton radius puzzle. In this paper, we will look at the possible consequences of the proton puzzle to the redefinition of SI based units. After a short introduction of the proton properties, we will describe the muonic hydrogen experiment. An intense theoretical activity derives from our observation. A brief summary of possible theoretical explanations at the present date of the writing of the paper will be

The proton

Even though the proton is one of the most abundant constituent of the visible Universe, some of its properties are not well known. Study of its properties is an important issue of our deep understanding of the matter. Proton is made of three valence quarks (up, up, down) kept together by strong interactions. Ab-initio calculations can be down on this structure using quantum chromodynamics (QCD) theory.

An important step has been the calculation of the mass of the proton using QCD with a relative uncertainty better than 4% [9] [10]. Experimentally the absolute mass of the proton is known with a relative uncertainty of 5×10 -8 [7].

The ab-initio calculation of the spin of the proton (i.e. 1/2) has been also undertaken. The present state of the problematic is known as the "spin crisis" [11]. It refers to the experimental finding that only a small contribution of the spin of the proton seems to be carried by the quarks [12] [13] [14]. Indeed the study of the spin structure of the nucleon is an important task of the particle physics either theoretically [15] or experimentally [16].

Some attempts have been also done to estimate the proton charge radius with QCD. Some values of r p have been published [17] [18]. New and more reliable values of proton radius should be given in the future as the calculation capabilities are increasing with time.

2 Experimental determinations of the proton charge radius

Scattering experiments

In fact the best knowledge of the proton charge radius comes from experiments. First determinations were given by electron-proton elastic scattering experiments. The principle of those experiments is to measure the differential cross section of a scattered electron beam sent onto a thin hydrogen (H 2 ) target. The relevant parameter is the space-like momentum transfer -Q 2 . The proton mean square charge radius is given by the slope of the Sachs form factor (G E ) of the proton at Q 2 =0.

r 2 p = -6 ∂G E (Q 2 ) ∂Q 2 | Q 2 =0 . (1)
The proton radius is defined as

r p = r 2 p . (2)
The main contribution to r p comes from low momentum measurements. Even if conceptually the experiment is simple, practically it is not. The spacelike momentum transfer cannot be made arbitrary small. The electron must cross the target in which a single elastic scatter has to occur. Measurements nearby Q 2 =0 must not be affected by the direct electron beam. Therefore the proton radius can be only obtained from an extrapolation of the differential cross section at Q 2 =0. This extrapolation is strongly model-dependent. A first determination of r p have been obtained in 1955 [19]. In the 80s, an experiment has been specially built in Mainz to get an accurate value of r p from low momentum transfers. The analysis of the data done in Mainz gives r p =0.862 (12) fm [21] in strong disagreement with an accurate previous determination [20]. Up to 2000's, no new scattering experiment have been carried out at low momentum transfers. All the different values of r p which have been published come from a re-analysis of the low momentum scattering data associated or not to high momentum scattering data (for example [22] [23]). The re-analysis considered by the CODATA task group has been obtained by I. Sick [24]. This work takes into account the world data on elastic electron proton scattering, the Coulomb distortion, and uses a parametrization that allows to deal properly with the higher moments. In the 2000's a sophisticated experiment has been carefully designed at Mainz to measure accurately r p [25]. Taking advantage of three high-resolution spectrometers, it was possible to measure the elastic electron-proton scattering cross section with a statistical precision of better than 0.2%. The value of r p published in 2010, deduced from an analysis done in Mainz with their data is 0.879(8) fm [26]. Another value of r p from scattering experiment has been published very recently [27]. This value of the proton radius is deduced from the global analysis done in [28] in which the new measurements done at "high" Q 2 [27] are included.

Hydrogen spectroscopy

At short distance, the Coulombian electrostatic potential is "shielded by the finite size of the proton". Consequently the energy levels of atomic hydrogen are slightly shifted. Therefore a value of r p can be obtained from high resolution spectroscopy of hydrogen. A simplified but powerful analysis of the main hydrogen data has been presented in [29] using only the most accurate experimental data : the frequency of the 1S-2S transition measured in Garching [30], the 2S-8S/8D transitions measured in Paris [31] and the 1/n 3 dependence of QED corrections [32] [33] (where n is the principal quantum number of hydrogen theory). A precise value of the 1S Lamb shift of hydrogen can be extracted from a proper linear combination of those three quantities. Assuming the exactness of QED calculations, an accurate value of r p can be deduced. A complete analysis of all the spectroscopic measurements is also regularly done by the CODATA task group on fundamental constants (see for example [7]). The last resulting spectroscopic value of r p is 0.8760(78) fm.

Muonic hydrogen spectroscopy

The aim of the muonic hydrogen spectroscopy of the 2S-2P splitting was to determine more accurately the proton radius. Muonic hydrogen (µ-p) is an exotic atom in which the muon (µ -) replaces the electron "orbiting around" the proton in normal atomic hydrogen. As electron, muon is a lepton but 207 times heavier and its lifetime is only 2.2 µs. Because of the mass dependence, the Bohr radius of µ-p is around 200 times smaller than the one of electronic hydrogen, the sensitivity to finite size of the proton is then largely enhanced. The contribution due to the finite size of the proton is around 2 % to the 2S-2P splitting of muonic hydrogen whereas it is only 1.4×10 -4 for the 2S 1/2 -2P 1/2 of electronic hydrogen. Another important issue in the comparison between muonic and electronic hydrogen, is the vacuum polarization which is the dominant contribution to the 2S-2P splitting of µ-p. As the Bohr radius is 200 times smaller, the overlap of S state wave-functions with the distribution of virtual electron-positron pairs is more important, consequently the contributions of the vacuum polarization corrections are larger. The wavelength of the 2S-2P transition in µ-p is 6 µm and the oscillator strength 10 -7 of the one of electronic hydrogen. Moreover the population of muonic hydrogen in 2S state is small. Because of those considerations this experiment has been really challenging. 3 Muonic hydrogen experiment

Principle of the experiment

The principle of the experiment has been described in many papers [34]. Let us recall the mains step. Muons (µ -) beam is send into a H 2 gas target. Muonic hydrogen atom is formed at principal quantum number around n=14 : the muon goes from the continuum to a bound state by ejection of an Auger electron. Subsequently the H 2 molecule breaks up and the muonic cascade of the neutral µ-p atom begins. Radiative and collisionally induced deexcitation processes bring it down to 2S or 1S state within a few nanoseconds. This cascade has been carefully studied [35] specially the collisional quenching of the 2S state [36] [37] [38]. 99% of atoms decay to 1S state, producing a large 2 keV fluorescence prompt peak. About 1% of muonic hydrogen are formed in a long-lived 2S state [39]. A laser pulse triggered by muons (see after) is send into H 2 target. Because of the short delay between laser trigger and output of the laser, a time-delayed 2 keV fluorescence peak is observed if the 2S-2P transition has been excited by the 6 µm light.

Apparatus

The challenges of the muonic hydrogen experiment were the production of long-lived muonic hydrogen in 2S state, the realization of the laser at 6 µm randomly trigerrable with a short delay and the analysis of the small signal awaited (few counts/hours).

To reduce collisional quenching of the 2S state, muons are stopped in H 2 gas at pressure of 1 hPa. For that a special low energy muon beam (∼keV) has been designed and built at Paul Scherrer Institut to efficiently stop muons at this ultra-low gas pressure within the small target volume required for efficient laser excitation. At 1hPa, the lifetime of the 2S metastable state is around 1 µs [36] [37]. Many details of this muon line can be found in [START_REF] Antognini | AIP Conf. Proc[END_REF] [35] [41] [START_REF] Ludhova | [END_REF] [43] [START_REF] Nebel | [END_REF]. We just emphasis that a special care has been put on the quality of the signal triggering the laser. The detection of keV-muons without stopping them is a non trivial task. It is done with thin carbon foils stack which simultaneously acts as muon detector and improves the beam quality by frictional cooling [START_REF] Mühlbauer | [END_REF].

The design of the laser is dictated by the need of a tunable light source at 6 µm triggerable within 1 µs after a random trigger by incoming muons. The laser chain used in 2009 run derives from many development of the initial laser chain used in 2003 [START_REF] Antognini | [END_REF]. The fast and powerful triggerable pulsed laser at 515 nm is used to pump an oscillator-amplifier titanium sapphire (TiSa) laser. Three consecutive vibrational Raman scattering in H 2 in a multiplepass cell are used to convert the 708 nm light into 6 µm pulse. The 6 µm light is then send, 20 m away, in a specially design multi-pass non resonant cavity surrounding the H 2 target in which µ-p atoms are formed. The later cavity is used to illuminate all the stopping volume of the muon in the target (5×15×190 mm 3 ). The frequency of the 6 µm light is driven by the one of the TiSa oscillator which is seeded by a cw-TiSa laser. The frequency of the cw-laser is permanently controlled with two wavemeters, a very stable Fabry-Perot cavity and atomic/molecular lines (I 2 , Cs, Rb). The cw laser is permanently locked on a Fabry-Perot fringe. The step of the scanning of the laser frequency is a multiple of the free spectral range of this Fabry-Perot interferometer [8]. Whereas the design of TiSa ensemble remains the same between the first and the last runs [46], the design of the green pump laser has to be changed drastically. A designed thin disk laser has to be built specially for our experiment [47].

The analysis of small signal requires a very good knowledge of the background. Since the early stage of the experiment, the 2 keV detectors (Large Area Avalanche Photodiodes, LAAPDs) have been well studied in order to maximize their time and energy resolutions [START_REF] Ludhova | [END_REF] [43] [48]. During the data analysis, background events are efficiently rejected. The final rate of about 1 background event per hour originates mainly from electrons from muon decay which are wrongly identified as 2 keV Lyman-α x-rays.

Results

At least, many muonic hydrogen lines have been observed during the fourth beam time period. The first line which has been observed and analysed is the most intense one : 2S 1/2 (F=1)-2P 3/2 (F=2) of muonic hydrogen (see figure 2). The signal is clearly above the noise floor. 550 events are measured in the resonance where 155 background events are expected. A Lorentzian profile is adjusted on the data to give the frequency of the line versus Fabry-Perot fringe. The absolute frequency of the line is performed from absolute calibration of the light at 6 µm using the H 2 O well known spectroscopy and the free spectral range of the Fabry-Perot interferometer (see figure 3). A careful and detailed analysis of the uncertainty budget of the centroid position of this line has been done in [8] [START_REF] Nebel | [END_REF].

The quantity determined by our experiment is the absolute frequency of 2S 1/2 (F=1)-2P 3/2 (F=2) resonance of muonic hydrogen : 49 881.88 (76) GHz. The main contribution to the uncertainty is statistical ; it is given by the fit of the Lorentzian shape on the experimental data. The relative uncertainty of the centroid position (1.6×10 -5 ) corresponds to 4% of the line width (∼18 GHz) which exhibit the fact that our experiment is far away from a high resolution spectroscopy one, but which also means a very weak dependance of the centroid of the resonance to the line shape model.

Nevertheless, the present result is good enough to extract the proton radius with the smallest uncertainty up to date. The value of the proton radius is obtained from the comparison of our determination of the frequency .49 µm and 6.04 µm is performed with H 2 O lines with the pulsed laser source while the free spectral range of the Fabry-Perot interferometer is determined in cw regime in the 695 nm-780 nm range with well known atomic/molecular lines. To detect an eventual drift of the Fabry-Perot interferometer, this one has been regularly compared to iodine lines before, during and after the beam time. The integer numbers (N,N') can be determined without any doubt thanks to our two wave-meters.

of 2S 1/2 (F=1)-2P 3/2 (F=2) muonic line with the theoretical prediction. The theoretical prediction derives for a large part from the bound state QED one of electronic hydrogen scaled with the mass of the muon. Those predictions account for radiative, recoil, proton structure fine and hyperfine contributions. A detailed list of the contributions can be found in [49]. The predicted frequency of the 2S 1/2 (F=1)-2P 3/2 (F=2)transition of muonic hydrogen is :

ν(GHz) = 50772.43(1.18) -1263.69 × r 2 p + 8.39 × r 3 p . (3)
The deduced value of r p is : 0.84184(36)( 56) fm where the first and second uncertainty originate respectively from experimental uncertainty and theoretical uncertainty. This result 0.84184(68) fm differs significantly (∼5 σ) with others determinations (see figure 4).

The proton radius puzzle

The confusing situation about r p is known as the proton radius puzzle. It has stimulated an intense activity in the community. It is impossible to make an exhaustive list of all the contributions already available on the ArXiv base, we apologize to authors whose papers are not cited. We can only point out some of the searches at the present date.

Definition of the proton radius

An obvious concern in the comparison is to make sure that the proton radius extracted from various experiments have the same meaning. A first positive answer has been given in [50] : "a conceivable accidental incompatibility of the conventions used in references [...] for the proton radius therefore cannot be the reason for the observed discrepancy". [...]refereing to all the proton radius determinations.

Charge distribution in the proton

The charge radius distribution is related to G E by the Fourier transformation. One attempt has been done to reevaluate the third Zemach moment of the proton r 3 p to solve the proton radius puzzle. However the reevaluation of r 3 p with the charge distribution presented in [53] is in contradiction with electron-proton scattering data [54] [55]. Fig. 4 -Comparison of the various determinations of the proton radius. Defining the proton radius as the slope of the Sachs form factor, experimental results are sort from low momentum transfer (electronic hydrogen) to high momentum transfer (scattering experiments) followings [73]. This presentation emphasis the surprising result of muonic hydrogen which can be view as a "dip in the form factor slope" at the corresponding Q 2 momentum of muonic hydrogen experiment.

QED corrections

The contradiction between the proton radius extracted from electronic hydrogen and from muonic hydrogen is intriguing for QED specialists. Because of the mass scaling law, QED of muonic hydrogen has always been considered to be simpler than the one of the hydrogen atom. Nevertheless, the proton radius puzzle has stimulated either careful checks of present QED corrections or evaluation of new corrections for hydrogen atoms [56] [57] [58]. Up to now, the proton radius puzzle can not be solve with new or wrong QED corrections.

Rydberg constant

The Rydberg constant is the scaling factor of atomic level. Assuming the correctness of QED calculations in electronic hydrogen atom, the problem can be solved by shifting by 5 standard deviations the value of the Rydberg constant, known with an uncertainty of 22 kHz, using the most accurate frequency measured in hydrogen [30]. However, the CODATA Rydberg constant is not only determined with 1S-2S and 2S-8S frequencies transitions but with others frequencies measurements certainly less accurate but all highly consistent together and with theory [7]. Moreover the recent measurement of the 1S-3S transition in hydrogen [59] is in very good agreement with the theoretical estimate [60]. At the present time there is no indications of a disagreement between theory and experiments in electronic hydrogen. But it is clear that the accuracy of the hydrogen experiments other than the 1S-2S one have to be improved to clarify the situation. It can be seen in figure 5 in which all the value of r p deduced from 1S-2S transition frequency, the 1/n 3 law and only one of the 2S-n(S,P,D) transitions frequency which has been measured. Individually, there is not a large discrepancy with the muonic determination of r p . On the other hand, most of the values are pointing in the same direction... Many ongoing experiments are carried out to test bound state QED. Results of the NPL experiment on the 2S-6S/D transitions [68], currently analyzed may bring an important and independent contribution to the hydrogen spectroscopy and so to the proton radius puzzle. Combined with the ongoing experiment at Garching, which aims at measuring the 1S-2S transition in He + [69], the experiment planed at Paul Scherrer Institut in order to measure the muonic helium ion Lamb shift (µHe + ) may illuminate the pro- Fig. 5 -Comparison of various determinations of the proton radius from hydrogen spectroscopy. Each value is obtained from the 1S-2S transition frequency, the 1/n 3 law and one of the other hydrogen experimental data from 2S-n(S,P,D). (a) is from [61], (b) is from [62], (c) is from [63], (d) is from [64], (e) is from [65], (f ) is from [66] combined with [59], (g) is from [31], (h) is from [67] and (i) from [59]. The double red line corresponds to the uncertainty of the proton radius determination obtained from muonic hydrogen spectroscopy.

ton radius conundrum [70]. A determination of the Rydberg constant nearly independent on the nucleus structure has also started at NIST Gaithersburg with the study of circular states of 20 Ne 9+ [71].

New physics

A possible way to solve the proton radius would be to introduce new "particles" which are coupled differently to the muon compared to the electron. However, this new physics search is already constrainted by many low energy data [72] [73] [74]. Indeed for example, recent laboratory-sized experiments are enough accurate to set a limit to the internal structure of the electron or to the existence of new dark matter particles assuming the exactness of QED calculations or testing for the first time the muon and hadrons contributions to the electron anomaly a e [5] [75]. A deviation to the Coulomb's law in muonic hydrogen is also ruled out by measurements in electronic hydrogen [76].

The proton and the redefinition of SI units

As discussed above, the new determination of the proton radius may affect the value of the Rydberg constant R ∞ . This constant is related to many fundamental constants. For example the estimate of the mass of the electron m e in the CODATA adjustment is derived from the relation

m e = 2R ∞ h cα 2 (4)
where α is the fine structure constant, c the velocity of light and h the Planck constant. The Rydberg constant is also linking the two possible ways proposed for the redefinition of the kilogramme, the Avogadro constant N A and the Planck constant h :

N A × h = c 2 A e α 2 M u R ∞ (5)
However, the current relative uncertainty on the experimental determinations of N A [77] or h [78] is in the order of few part of 10 8 . This is three orders of magnitude larger than the "possible" shift of the Rydberg constant may be disclosed by the new value of proton size radius from muonic hydrogen. The proton radius puzzle will not interfere in the redefinition of the Kilogramme.

For many years, hydrogen atom has been advocated as an "ideal" clock (see for example [79]) as in principle it can be calculated in contrary to the others clocks. Should the second being redefined with hydrogen atom in term of fundamental constants ? Today, calculations for hydrogen are about 10000 times less accurate than current experimental caesium clock precision, due to the growing complexity of the calculations of higher order corrections. The best experimental determination is also 10 3 times worse than the best optical clocks, which are front-runners to redefine the second in several years time (see P.Gill article in this issue). Improved theory with higher order corrections to two or three more orders is needed before the calculable clock approach for hydrogen becomes competitive.

Nevertheless, the finding solution of the proton radius puzzle is a step in the long quest to decode hydrogen spectrum : the "Rosetta stone of modern physics" [80].

Fig. 1 -

 1 Fig.1-Principle of the muonic hydrogen experiment. Muons are stopped in 1 hPa H 2 gas. 99% goes under radiative cascade to 1S state, producing a large prompt peak of 2 keV radiation. The 2S-2P transition is detected with the smaller peak due to the laser induced X rays, at the time of the laser arrival (∼0.7 µs) to the muon stop volume.

Fig. 2 - 2 Fig. 3 -

 223 Fig. 2 -2S 1/2 (F=1)-2P 3/2 (F=2) resonance. The discrepancy with the others determinations is clearly visible. The frequency gap is around 75 GHz with the position of the line expected with electronic hydrogen. The inset calibration H 2 O line has been recorded at 30 hPa.