Benhacène Raïlane

Cena

CENA Anthony Marion
email: marion@cena.fr

Rousselle Marie-Pierre
email: roussell@cena.fr

AS RAPID AS PAPER STRIPS? EVALUATION OF VERTIDIGI, A NEW CONTROL TOOL FOR TERMINAL SECTORS

Keywords: HMI, ATC, Touch Screens, Terminal Sectors, Arrival Manager

VertiDigi is a vertical view of the flights in a terminal sector. The view, on a touch sensitive screen, tries to provide a similar service to controllers as the current paper Strips do: a tool to input control clearances naturally, intuitively and at a speed sufficient to allow the traffic to be efficiently managed.

In arrival sectors, an Arrival Manager (AMAN) is often used. The AMAN delays in minutes can also be expressed on the vertical view as a moving target (ball indicating the desired position) for each flight. The resulting ball train is a novel way of representing an arrival sequence in a perceptive analog way.

Experiments were conducted with 8 air traffic controllers from Paris ACC to compare VertiDigi vs. Strips input times, to assess the acceptability of the vertical view, and to estimate usability of the ball train

The most evident outcome is that input times are in the same order of magnitude as papers Strips, and promising to be even shorter with minimal training.

Meanwhile, the vertical view did not affect the controllers' mental view of the traffic.

The ball train, in turn, did not yield better usage, performance or acceptance than the current AMAN Human Machine Interface (HMI).

Introduction: Terminal Sectors

Terminal sectors are en-route sectors but mainly dealing with traffic inbound or outbound from a major or several major airports. These sectors are the intermediate buffer between classical en-route sectors and the final approach. Our study is currently focused on arrival sectors.

Traffic in terminal sectors is such that no standard en-route technique is easily transferred. In an arrival sector, flights typically enter the sector at high speed and high altitude. The work of controllers consists in slowing down traffic, initiating and monitoring the descent, but also sequencing them to create a "train" of aircraft with regular spacing and a common speed to avoid catch-ups.

In the Paris region, an arrival manager (AMAN) also often requires that aircraft be slowed down to respect a given time over a metering fix. This is done in order to account for the capacity of the approach sectors and of the runways downstream.

But the most important characteristic of control in such sectors is the need to give aircraft several clearances in the same sentence, especially during peak or "hub" hour. A typical message is of three elements: speed reduction, descent to a certain Flight Level (FL), and direction clearance to the metering fix. The rhythm of clearances' delivery on the radio is such that it was believed that no input system could ever match the pencil writing on paper Strips.

A user centered Design

VertiDigi was essentially made to meet these specific needs, and address them by deliberately taking the operational point of view as guidance to the design of a new working environment for controllers. Thus, having listed the characteristics of air traffic control in Terminal Sectors, it appeared that the most urgent need was to find a very efficient way of making inputs into a system. We decided to design the new working environment around this particular need, not to address it at the end of the design. Human factors people are often involved in the last moments of conception, once the major design choices have been made. It is then too late for them to radically influence the choices. This generally leaves little room for improvement: mostly superficial Human-Machine Interface (HMI) re-vamping. The HMI is therefore not very user-friendly, and often does not allow users to operate like they did in the "natural" environment [START_REF] Durso | Following the paper trail: design clues from paper flight Strips[END_REF]. To compensate for HMI caveats, the solution is generally to recommend an adequate "training" of the operators, and procedures. This places the burden on the operators' memory and responsibility.

Rapid Input as a prime objective

With this in mind, we examined what was then available as ways to enhance the performance of input. The issue of replacing paper Strips is not new [START_REF] Mackay | Is Paper Safer? The Role of Paper Flight Strips in Air Traffic Control[END_REF] and the challenge is high. A review was therefore made to examine what was the best available solution for input, and try to build from there. Voice recognition was put aside because it did not seem sufficiently reliable for a safety oriented task. Conventional mouse and screen selection of clearances seemed insufficient, and from the informal elements we had, it appeared that wherever such a way of making inputs was selected, controllers would accept it but in practice, they would give up entering all clearances into the system, and focus on the most important input (typically the Flight Level). We then considered the work of another team of the CENA, which had designed a very attractive and convincing HMI for the replacement of paper Strips: DigiStrips [START_REF] Mertz | Pushing the limits of ATC user interface design beyond S&M interaction : the DigiStrips experience[END_REF]. It appeared that the use of touch sensitive screens seemed promising and that, combined with simple gesture recognition and proper graphical design, it could yield input times shorter than ever observed with conventional mouse and clicking HMIs.

A Vertical View to enrich an input means

Another design choice emerged shortly after. The conventional way of offering an input display to replace the paper Strips is to reproduce the actual paper strip board. This was the choice of the earlier mentioned [START_REF] Mertz | Pushing the limits of ATC user interface design beyond S&M interaction : the DigiStrips experience[END_REF] DigiStrips, but the idea of a list of flights is also often proposed in most current modernized Controller Working Position (CWP). Another common option is to use the radar image as a means to access to the flights. The aircraft labels are made reactive, on mouse clicking, and different fields open menus to make Flight Level, Heading, Direct or Speed clearances. Considering the resulting clutter of information on the radar display, we looked for another solution: many controllers ask for a clearer radar image because it is the primary means of analyzing a traffic situation (experienced controllers routinely untick the option for speed vectors, for names of fixes, or any other non-essential display).

On the other hand, we had in mind the importance of the representation of the Vertical profile of aircraft. We were concerned that this element would still be missing on a conventional input display. We felt that an efficient representation of the vertical dimension would be very helpful on terminal sectors. It could be new decision aid tool: one that would provide a simple representation of the traffic situation to be manipulated directly [START_REF] Rekimoto | Pick and Drop : a direct manipulation technique for multiple computer environments[END_REF] rather than an elaborate processing thereof. The advantage of this choice will be expanded in the discussion section. Eventually, we elected to try the use of a vertical view of the traffic as a primary display to access to the flights and make input on them. We thought we could thus integrate both benefits in one single tool: VertiDigi. The first idea was that the radar image (as a Head-up display) would be left intact, as a solid grounds for well established working habits. We then suggested that a new display would be provided in the current place of the paper Strips board (head-down display). And we offered that this display would represent the same traffic situation as the radar image, but in the vertical plane. Each aircraft will, in our case, be represented in distance to a metering fix (on the x-axis) and in current flight level (on the y-axis). Last, the screen is touch sensitive, and each aircraft has a label which is used to open dedicated menus for clearances, using very simple and robust gesture recognition.

Figure 1. Principle of the Vertical View

A Ball Train to improve the AMAN HMI

Current AMANs generally provide the controller with a time-line suggesting delays corresponding to each aircraft. The ATCO is supposed to slow down aircraft, before they reach the metering fix, to absorb suggested delays. We elected to provide a more analog [START_REF] Desenti | Transition Airspace Controller Tool (TACT) Visualization Aids for Radar Controllers[END_REF][10] image of where the aircraft should be, still on this new vertical image. For each aircraft, a target ball was added, on the vertical view, on a horizontal line corresponding to the transfer flight level. A line is then drawn between the actual aircraft and its target. The position of the target is calculated so that it behaves like a real aircraft at the same Flight Level, descending to towards the metering fix, and at a standard delivery speed, but such that it has no AMAN delay. As a result, achieving the AMAN objective can now be made by delivering an aircraft together with its target ball at the metering fix. Doing so uses natural, intuitive perceptive skills to evaluate the situation (visually evaluating distance between an aircraft and its target).

Figure 2. Ball Train (blue lines)

If the line linking the aircraft to its ball is vertical, the delay is bound to be absorbed, provided the aircraft has the proper delivery speed. If the ball is lagging behind the aircraft, and the link is inclined frontward, this intuitively indicates that the aircraft should be slowed down to be caught up by its ball, and thus pass the metering fix on time.

Experiment on the VertiDigi HMI

Objective

Our primary objective was to determine input times with paper Strips, and compare them to those observed with the VertiDigi HMI. To the best of our knowledge, no reference or experiment actually conducted accurate measurements of the time it actually takes controllers to make markings on paper Strips. Even so, as is often the case with air traffic control, local habits, the type of flights and situations, traffic complexity, the training of controllers, all these factors are such that no control center has similar ways and practices. Therefore, we thought that it would be difficult to conclude from results in input time observed in a different context. We thought that carrying out reference measurements, no matter how costly it would be, would grant us greater confidence in our comparisons. We will later show that this choice eventually permitted to highlight an unexpected result concerning the type of clearances made.

Experimental layout

Our focus was on control in Paris ACC, and we selected real traffic samples from that area. We conducted the experiments with ATCO from that center, on arrival sectors they were familiar with. The controllers were selected with different levels of experience: from trainee to over 5 years of qualification on the sectors. The choice of real traffic samples granted us a great confidence in the realistic aspect of the experiments. Traffic load had been assessed with an experienced controller. Aircraft call signs were actual ones, which enabled them to realistically take advantage of some very well established habits and routine procedures ("ah, there comes Air France XYZ, transverse flight coming from Strasbourg, I know he will be requesting descent sometime in the middle of my sector -let me check if there's a flight in his way").

Conducting the Experiment

Each controller underwent a two day experiment, alone. We chose not to reproduce the team work (a pair of controllers) in order to keep the experiment setup as simple as possible. The controllers had an initial presentation of the interface, followed by a brief training period (45 minutes). They then underwent 6 simulations, of 45 minutes' duration.

The following conditions were applied (in that order):

• Paper Strips-standard AMAN-high traffic • VertiDigi-standard AMAN-normal traffic • VertiDigi-standard AMAN-high traffic • VertiDigi-ball train-normal traffic • VertiDigi-ball train-high traffic • Paper Strips-standard AMAN-normal traffic
In order to prevent any sample specificity effect, the set of simulations was shifted around for each controller, so that each sample was played alternatively in any of the Paper vs. VertiDigi or Standard AMAN vs. Ball train conditions. Furthermore, in both traffic condition (normal or high traffic), the samples were derived from the same real traffic sample, but the aircraft call signs were shifted, and times of arrivals of groups of conflicting aircraft were modified. We believed that this should grant greater similarity between samples, although we feared that the controllers would be able to "recognize" the samples. In practice, they took no notice of this and made no comment as to the similarities between samples.

All simulations were filmed with two cameras, one capturing the overall experimental setup, and one digital recorder focused on the VertiDigi interface or the paper Strips' board. This latter condition was later replayed and timed to measure paper Strips input times. We chose to trigger the timer whenever the pencil touched the paper, and stopped it as soon as it left the paper strip. Each input was also tagged to give its nature (Flight Level, Speed, Direct, rearranging the Strips). In the case of VertiDigi HMI, such recordings were automated and logged in a text file. A computer script enabled us to analyze that data offline, very rapidly.

Results

The analysis of the results led us to consider two aspects: first, as we had given the possibility for labels on the VertiDigi HMI to be moved around, we found out that this functionality had, in practice, been used fairly often, and that it matched the corresponding re-arranging of the paper Strips' board. In terms of time consumed, it turned out that moving labels, even if it addresses more or less the same need to manipulate the traffic, is less time consuming.

Input Times

Considering clearances on VertiDigi, it should be mentioned that the input times recorded corresponded to the interval between the designation or selection of an aircraft label and the subsequent finishing of a clearance input. In practice, some controllers spontaneously took the habit of selecting an aircraft first, then speaking on the frequency to the pseudo-pilot and issuing a clearance, and then, at last, actually making the input into the system. Although this habit tended to disappear with time and as they gained familiarity with the interface, we thought that such a time would not be representative of an actual input time, but more of a working habit. For this reason, we chose not to include in the average times any input values that were above 10 seconds (roughly less then 3% of input were discarded). The corresponding results are given hereunder. The input times are very close (total average time being 0.37 seconds higher in VertiDigi than in Paper Strips condition). The breakdown into different types of input will provide us with more elements. Again, we here chose to segregate between what is considered as standard clearances, summarized in the "Total Clearances" bar, and what can be regarded as manipulation of the interface rather, summarized in the "Total Manip" bar. In this latter category, we included the "shoot", controllers jargon for the transfer of a flight to the next sector. One striking element is the case of absolute heading clearances. In this case, input times where noticeably higher. This can be explained easily by the poor initial design of the interface: whenever such a clearance was made, the controllers had to scroll several times to find the proper value for an absolute heading ("fly heading 270"), given that the menus were made with increments of one degree of angle. Further discussion with the controllers led us to choose 5 degrees increments, which greatly improved the situation.

Average Input Times

Average Times

Adversely, it can be seen that the manipulation of an actual paper Strips' board is time consuming. In the electronic environment, moving labels to prevent overlap and possibly to organize traffic is done more rapidly. We cannot tell, however, if this manipulation can meet the needs of an ATCO and if it permits the building and updating of a mental image as operative as what is done with paper Strips. Some tests we did post simulation show no impact on memory of the traffic, and also that the most important aircraft (those involved in conflicts) were as well recalled in paper as in electronic environment.

Overall, the general feeling is that input times are in the same order of magnitude, and slightly higher for the VertiDigi environment. This result was further confirmed by answers to a questionnaire the ATCO filled in at the end of the experiment. They largely considered the interface as satisfactory in terms of input times, and felt that the HMI easy to use and intuitive.

We then compared the shortest measured input times for each type of clearance. We thought that this could give an indication of what can be expected "at best". We were fortunate to notice that, in most cases, the shortest observed input times were those made in the electronic environment (VertiDigi), as can be seen in the table below.

Minimum Input Time

VertiDigi

It is hard to draw any firm conclusion from this table. The impression, however, is that shorter input times are achievable with the VertiDigi interface. Given that this was performed with only a very limited training time and experience on this interface, we believe that it is likely that, with sufficient training, the ATCOs would be able to make input at a speed at most equivalent to the speed they achieve with paper Strips, and possibly even be quicker.

The learning effect, even though on a short time period, is worth mentioning. The chart here after shows that, with the exception of one controller, input times have decreased (on the average) between the first and the last simulation. In other words, the measured input times are still not stabilized and may evolve further with due training and added familiarity with the interface.

Evolution of Input Times during the Experiment

0,00 0,50

Analysis of the types of Clearances

The first thing to mention is that, adding up all controllers' simulations, the overall number of clearances is roughly equivalent in the VertiDigi (1112) and in the paper Strips condition (1006). We did not consider a 10% increase in the total number of clearances significant, given natural variations in the way controllers manage a traffic sample. Note: the total number of clearances in VertiDigi environment was divided by two to account for a 4-2 ratio of simulations in VertiDigi vs. Strips condition. This means that the ATCOs have not been reluctant to making input into the system, and we can believe that they actually input into the system all clearances they had verbalized on the frequency. This is good news, knowing that when an HMI is too slow or inadequate, controllers can control without marking all the clearances they issue, but eventually reject the HMI as not efficient.

We then looked at the breakdown of this total figure into different categories of clearances. A very surprising and interesting effect appears, for Flight Levels and speed clearances. The number of Flight Level clearances significantly decreases (from 414 to 267), while the number of Speed clearances is almost doubled (from 208 to 368). This difference seems significant, and we think it reveals a change in the way controllers handle the traffic. It should be noted that this result went unnoticed during simulations and appeared during the data-analysis which followed the experiments. We think that this may be the result of the vertical representation of the traffic. Confronted with the vertical view, most controllers declare that they have little use of it, as they are capable of building a mental vertical representation of the, just from reading the flight level figures on the labels of the radar image. It is likely, though, that actually seeing the aircraft represented in the vertical plane supports or facilitates the building of this image, and gives them the chance to make more rapid decisions. In arrival sectors, if no "transverse" flight is in the descent profile of an aircraft, it is easier for a controller to immediately give him a clearance to the final Flight Level (the Transfer Flight Level to the approach controllers). In short, we believe that the vertical view helped them visualize the vertical profiles of aircraft and that they thus gained time in analyzing the situation. The chances are, on the other hand, that the speed clearances increased due to the ball train. Truly, the addition of this new representation of the AMAN sequence certainly acted as an incentive to try and match the time for passage over the metering fix. And the most natural way to do this is by issuing speed clearances (speed reductions namely) to try and absorb the AMAN delay. This is the only plausible explanation we found for the increase in speed clearances.

Number of Clearances

Ball Train

The expectations we had were that this new representation would help controllers make earlier decisions on the traffic [START_REF] Grimaud | Delegating upstream -Mapping where it happens[END_REF] and be able to absorb the AMAN delay more completely. In practice, two main findings can be stated:

• AMAN delays reduction is not significantly affected by the use of the ball train w/r to a standard HMI • Clearances are not made earlier in the sector with the use of the ball train.

Several elements can explain this finding. The first thing to be noted is that an AMAN, in terminal sectors, is deemed as an additional task that should be considered only once the highest priority (ensuring conflict avoidance) is soundly granted. And truly, absorbing the AMAN delays is a 'bonus': an action that will only serve the approach controller, in order to smooth his workload. So it is considered as a lesser task, and does not get all the attention from controllers. Furthermore, the ATCOs consider that the AMAN is sometimes misleading, giving delays that are not coherent with the radar situation, only to update them later, once the trajectory predictions are re-calculated. Last, it takes some time to familiarize with the ball train and learn to predict its behavior. The 30 minutes' training period was probably not sufficient for such a new concept. All graphs will not be given here (Flight Levels are mentioned hereafter for an example), but we did explore the locus of different types of clearances, and the delay absorption, with no tangible result.

Discussion

Why so much trouble for input?

From the results mentioned above, it can be seen that the VertiDigi interface has some potential to address the needs of ATCOs in Terminal Sectors, and that the user-centered design actually led to an HMI that satisfied the operators. The question now comes: does this really enhance the performance of the control system as a whole, or does this only bring elements of comfort for the operators? These are probably two sides of the same coin: if the operator feels comfortable with an interface, performance and safety will be increased accordingly. It is assumed that this is probably the soundest way to increase performance of a system. Currently, one major limitation of the capacity of a sector is established by ATCOs themselves: they decide when to not accept additional aircraft in the sector any longer. And rightly so, as they normally account for safety margins that cover for any unexpected, abnormal situation that can occur. They have had difficulties in envisaging the transition to electronic environments, as they knew that this would be likely to degrade their rapidity and response time, thus threatening safety and increasing their stress.

The purpose of VertiDigi was to eliminate this drawback in order to give the electronic environment a chance to provide advantages that are only blocked by the issue of input for the time being. We can quote numerous examples when the input of ATCOs' decisions could be used to improve the ATC system. Generally, any system requiring a trajectory prediction could greatly be improved with this data. Typically, an AMAN would give more sensible suggestion with an informed trajectory prediction, probably yielding better acceptance by controllers. Similarly, no Medium Term Conflict Detection can be efficient if it ignores what aircraft have been told to do. Even more obvious, Data-Link could not possibly exist without clearances being first introduced into a computerized system, and yet this should not be done at the expense of current working practices. Even Short Term Conflict Avoidance may be fine tuned to avoid some false alarms with ATCOs intention (although this can be argued). However, none of these improvements have been implemented in VertiDigi, so far. Our main objective was that the tool be able to replace the functionalities of the paper Strips [START_REF] Durso | Following the paper trail: design clues from paper flight Strips[END_REF] [6] first and foremost.

VertiDigi is designed as an HMI (even if it may have other advantages). We thus included animations which serve nothing but the legibility of the interface for the user, and may enhance error recovery. We also provided possibility for free text input, to cope with all unexpected or specific needs. In its current version, the input made by the ATCOs serves them only as a feed-back to mark the clearances in the aircraft label (in green manuscript font). This serves as a memory aid for the Radar Controller (like marks on paper Strips) but also as a support for cooperation with the Planning Controller [START_REF] Durso | Following the paper trail: design clues from paper flight Strips[END_REF] or on shift changes. One thing to be mentioned is that the time to make an input is not always as important as it may seem. Conservatively, we have not measured, for example, the time it takes to look for a paper Strip in the board. When a flight calls on the radio, finding its label in the VertiDigi interface is likely to be quicker. But the aim is not so much of making the quickest possible input. The real objective is for the operator to feel comfortable with the HMI. Ideally, an HMI should become transparent, so that it serves the work performed by the operator. For example, the initial feeling of the ATCO using VertiDigi was that they could not speak and input at the same time. Reviewing the videos, however, showed that, after the initial simulations, having acquired some familiarity with the tool, they were, indeed, speaking and making input at one time. And they even hardly looked downwards at the HMI to do so: a quick glance to adjust the gesture was soon sufficient. Their gaze remained on the radar image. More than actual input time, this gives us confidence that the tool could be used in a real traffic context.

A stand alone tool

From a system viewpoint, VertiDigi is usable as a passive, stand alone tool, and need not to interact with all the surrounding ATC computer systems. The tool only requires the subscription to radar data (to be able to draw the aircraft at the proper position in the vertical plane) and the Flight Data Processing System (to know what are the route and the fixes on the route of a given aircraft). It does not, however, send any messages outwards. This ability to not communicate outward may be useful: it allows the tool to be inserted inside an existing ATC network 'as is'. The only purpose is to replace the current necessary functions of the paper Strips. The communication of data acquired with this tool (and risk of corruption of existing systems) can thus be delayed, and examined at a later stage. This can be done once sufficient confidence has been gained, that the input tool is accepted by controllers in real working conditions. This leaves room for the implementation of all the necessary fine tuning that can only be done in real conditions.

The choice of the vertical view

To design philosophy underlying VertiDigi is to favor a tool that offers a good representation of the traffic situation, rather than an elaborate treatment of information (like MTCDs or algorithms generally do). Such a design is generally more robust: a representation seldom fails or is hardly bugged. Similar to what can be found in a cockpit [START_REF] Hutchins | How a cockpit remembers its speeds[END_REF], analogue displays seem simplistic. They have, though, some hidden yet very valuable properties to serve as a support for human cognition. Being more 'reliable' and predictable, they also tend to diminish the stress of an operator, and even their limitations are well accepted. The speed vectors on radar displays are a good example: they help predict the aircraft future position, but only as long as the aircraft speed is constant. This is not an issue for controllers: they know this limitation, and use the speed vector accordingly. This is why we chose to display the aircraft position on VertiDigi in distance to the metering fix, not on a time scale as was often suggested and envisaged. We think that even if a slow aircraft is at the same distance to the fix as a rapid aircraft, the controller can cope with this. Adversely, displaying at the same 'time-distance' two such aircraft, one being in practice more distant than the slow one, was deemed as misleading. This requires some level of interpretation which is not intuitive or straightforward, and we fear this could prove dangerous under degraded or high stress conditions. We tried to keep the interface simple, legible, simplistic, even. And we haven't observed any spatial confusion or any situation where an operator was at loss to understand what was happening in the system. One possible reason for that is that VertiDigi provides a fixed vertical view which is very natural in the context of descending or climbing aircraft (typically terminal sectors). On the air side, many trials have been made [START_REF] Prevot | A Display for Managing the Vertical Flight Path -An Appropriate Task with Inappropriate Feedback[END_REF] to provide such a view to the cockpit. The same has been done for the ATCOs before, but generally with a particular temporary view, which is strongly related to one specific aircraft or group of conflicting aircraft. We selected a fixed, global and permanent vertical view to avoid cognitive workload and spatial confusion. The fact that arrival terminal sectors have a strong structural orientation (most aircraft are bound for the metering fix) helped us in this respect. It is assumed that a fixed, permanent vertical representation is more useable to build strong, repeated, familiar geographical references. This appeared unexpectedly when we considered the rate of descent. A grey area indicated, on VertiDigi, the transition above or below the nominal 5% descent path to the metering fix. Although just a fancy feature, this turned out to be very appreciated and used by ATCOs: it helped them spot at a glance the aircraft they had forgotten to initiate the descent (they would therefore enter the grey area) on the display.

Conclusion

The combination of a touch sensitive screen and a vertical display seems a promising way to address the issue of input for Air Traffic Control. The experiments conducted have demonstrated that input times were sufficiently low for the HMI to become 'transparent', leaving the operators to focus on traffic analysis. The choice of the vertical representation seems to offer opportunities for useful operational representations (AMAN, possibly ASAS [START_REF] Benhacène | A Vertical Image as a means to improve air traffic control in E-TMA, Irvine-California[END_REF]). Many improvements are also needed to further match this interface to the operators' needs. The path, however, seems credible and may deserve further experimenting to address other necessary milestones such as grouping/degrouping sectors, a similar tool for the Planning Controller, incorporating future concepts (Data Link, etc.). The ball train, in turn, seems a less mature concept, and deserves either modification, or a lengthier training to be accepted and used by the controllers.


Samy Skander Bahoura
email: samybahoura@yahoo.fr

Samy Skander Bahoura

ON THE MASS OF THE EXTERIOR BLOW-UP POINTS

research documents, whether they are published or not. The documents may come

On the mass of the exterior blow-up points.

INTRODUCTION AND MAIN RESULTS

We set ∆ = ∂ 11 + ∂ 22 on open set Ω of R 2 with a smooth boundary.

We consider the following problem on Ω ⊂ R 2 :

(P ) -∆u i = V i e ui in Ω ⊂ R 2 , u i = 0 in ∂Ω.
We assume that, Ω e ui dy ≤ C, and,

0 ≤ V i ≤ b < +∞
The previous equation is called, the Prescribed Scalar Curvature equation, in relation with conformal change of metrics. The function V i is the prescribed curvature.

Here, we try to find some a priori estimates for sequences of the previous problem. Equations of this type were studied by many authors, see [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF][START_REF] Chen | A priori Estimates for solutions to Nonlinear Elliptic Equations[END_REF][START_REF] Chen | A sharp sup+inf inequality for a nonlinear elliptic equation in R 2[END_REF][START_REF] Cheng | On the asymptotic behavior of solutions of the conformal Gaussian curvature equations in R 2[END_REF][START_REF] Yy | Harnack Type Inequality: the Method of Moving Planes[END_REF][START_REF] Yy | Blow-up Analysis for Solutions of -∆u = V e u in Dimension Two[END_REF][START_REF] Ma | Convergence for a Liouville equation[END_REF][START_REF] Shafrir | A sup+inf inequality for the equation -∆u = V e u[END_REF][START_REF] Zhang | Blowup solutions of some nonlinear elliptic equations involving exponential nonlinearities[END_REF][START_REF] Wolansky | Note on blow-up limits for solutions of ∆u + Ke u = 0 in two dimensions[END_REF]. We can see in [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF], different results for the solutions of those type of equations with or without boundaries conditions and, with minimal conditions on V , for example we suppose V i ≥ 0 and V i ∈ L p (Ω) or V i e ui ∈ L p (Ω) with p ∈ [1, +∞].

Among other results, we can see in [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF], the following important Theorem, Theorem A (Brezis-Merle [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF]).If (u i ) i and (V i ) i are two sequences of functions relatively to the previous problem (P ) with, 0 < a ≤ V i ≤ b < +∞, then, for all compact set K of Ω, sup

K u i ≤ c = c(a, b, m, K, Ω) if inf Ω u i ≥ m.
A simple consequence of this theorem is that, if we assume u i = 0 on ∂Ω then, the sequence (u i ) i is locally uniformly bounded. We can find in [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF] an interior estimate if we assume a = 0, but we need an assumption on the integral of e ui , precisely, we have in [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF]:

Theorem B (Brezis-Merle [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF]).If (u i ) i and (V i ) i are two sequences of functions relatively to the previous problem (P ) with, 0 ≤ V i ≤ b < +∞, and, Ω e ui dy ≤ C, then, for all compact set K of Ω, sup

K u i ≤ c = c(b, C, K, Ω).
If, we assume V with more regularity, we can have another type of estimates, sup + inf. It was proved, by Shafrir, see [START_REF] Shafrir | A sup+inf inequality for the equation -∆u = V e u[END_REF], that, if (u i ) i , (V i ) i are two sequences of functions solutions of the previous equation without assumption on the boundary and, 0 < a ≤ V i ≤ b < +∞, then we have the following interior estimate:

C a b sup K u i + inf Ω u i ≤ c = c(a, b, K, Ω).
We can see in [START_REF] Chen | A sharp sup+inf inequality for a nonlinear elliptic equation in R 2[END_REF], an explicit value of C a b = a b . In his proof, Shafrir has used the Stokes formula and an isoperimetric inequality, see [START_REF] Bandle | Isoperimetric inequalities and Applications[END_REF]. For Chen-Lin, they have used the blow-up analysis combined with some geometric type inequality for the integral curvature.

Now, if we suppose (V i ) i uniformly Lipschitzian with A the Lipschitz constant, then, C(a/b) = 1 and c = c(a, b, A, K, Ω), see Brézis-Li-Shafrir [START_REF] Brezis | A sup+inf inequality for some nonlinear elliptic equations involving exponential nonlinearities[END_REF]. This result was extended for Hölderian sequences (V i ) i by Chen-Lin, see [START_REF] Chen | A sharp sup+inf inequality for a nonlinear elliptic equation in R 2[END_REF]. Also, we can see in [START_REF] Yy | Harnack Type Inequality: the Method of Moving Planes[END_REF], an extension of the Brezis-Li-Shafrir to compact Riemann surface without boundary. We can see in [START_REF] Yy | Blow-up Analysis for Solutions of -∆u = V e u in Dimension Two[END_REF] explicit form, (8πm, m ∈ N * exactly), for the numbers in front of the Dirac masses, when the solutions blowup. Here, the notion of isolated blow-up point is used. Also, we can see in [START_REF] Zhang | Blowup solutions of some nonlinear elliptic equations involving exponential nonlinearities[END_REF] refined estimates near the isolated blow-up points and the bubbling behavior of the blow-up sequences.

We have in [START_REF] Wolansky | Note on blow-up limits for solutions of ∆u + Ke u = 0 in two dimensions[END_REF]:

Theorem C (Wolansky.G. [START_REF] Wolansky | Note on blow-up limits for solutions of ∆u + Ke u = 0 in two dimensions[END_REF]). If (u i ) and (V i ) are two sequences of functions solutions of the problem (P ) without the boundary condition, with,

0 ≤ V i ≤ b < +∞, ||∇V i || L ∞ (Ω) ≤ C 1 , Ω e ui dy ≤ C 2 ,

and,

sup ∂Ω u i -inf ∂Ω u i ≤ C 3 ,
the last condition replace the boundary condition. We assume that (iii) holds in the theorem 3 of [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF], then, in the sense of the distributions:

V i e ui → m j=0 8πδ xj .
in other words, we have:

α j = 8π, j = 0 . . . m,
in (iii) of the theorem 3 of [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF].

To understand the notations, it is interessant to take a look to a previous prints on arXiv, see [START_REF] Bahoura | About Brezis-Merle problem with holderian condition: the case of 1 or 2 blow-up points[END_REF] and [START_REF] Bahoura | About Brezis-Merle problem with holderian condition: the case of 3 blow-up points[END_REF].

Our main results are: Theorem 1. Assume that, V i is uniformly s-holderian with 1/2 < s ≤ 1, and that :

max Ω u i → +∞.

Then, each exterior blow-up point is simple.

There are m blow-ups points on the boundary (perhaps the same) such that:

B(x j i ,δ j i ǫ ′ ) V i (x j i + δ j i y)e ui → 8π.
and,

Ω V i e ui → Ω V e u + m j=1 8πδ xj .
and, Theorem 2. Assume that, V i is uniformly s-holderian with 1/2 < s ≤ 1, and,

B1 (0)
V i e ui dy ≤ 40π -ǫ, ǫ > 0, then we have:

sup

Ω u i ≤ c = c(b, C, A, s, Ω).
where A is the holderian constant of V i .

PROOF OF THE RESULT:

Proof of the theorem 1:

Let's consider the following function on the ball of center 0 and radius 1/2; And let us consider ǫ > 0

v i (y) = u i (x i + δ i y) + 2 log δ i , y ∈ B(0, 1/2)
This function is solution of the following equation:

-∆v i = V i (x i + δ i y)e vi , y ∈ B(0, 1/2)
The function v i satisfy the following inequality (without loss of generality):

sup ∂B(0,1/4) v i -inf ∂B(0,1/4) v i ≤ C,
Let us consider the following functions:

-∆v i 0 = 0 in B(0, 1/4) v i 0 = u i (x i + δ i y) on ∂B(0, 1/4)
. By the elliptic estimates we have:

v i 0 ∈ C 2 ( B(0, 1/4)). We can write: -∆(v i -v i 0 ) = V i (x i + δ i y)e v i 0 e vi-v i 0 = K 1 K 2 e vi-v i 0 ,
With this notations, we have:

||∇(v i -v i 0 )|| L q (B(0,ǫ)) ≤ C q . v i -v i 0 → G in W 1,
q 0 , And, because, for ǫ > 0 small enough:

||∇G|| L q (B(0,ǫ)) ≤ ǫ ′ << 1,
We have, for ǫ > 0 small enough:

||∇(v i -v i 0 )|| L q (B(0,ǫ)) ≤ 2ǫ ′ << 1. and, ||∇v i || L q (B(0,ǫ)) ≤ 3ǫ ′ << 1. Set, u = v i -v i 0 , z 1 = 0, Then, -∆u = K 1 K 2 e u , in B(0, 1/4),
and,

osc(u) = 0.
We use Woalnsky's theorem, see [START_REF] Wolansky | Note on blow-up limits for solutions of ∆u + Ke u = 0 in two dimensions[END_REF]. In fact K 2 is a C 1 function uniformly bounded and K 1 is s-holderian with 1/2 < s ≤ 1. Because we take the logarithm in K, the part which contain K 2 have similar proof as in this paper we use the Stokes formula. Only the case of K 1 s-holderian is difficult. For this and without loss of generality, we can assume the

K = K 1 = V i (x i + δ i y).
We set:

∆ũ = ∆v i = ρ = -Ke ũ = -K 1 e vi
Let us consider the following term of Wolansky computations:

B ǫ div((z -z 1 )ρ) log K + ∂B ǫ (< (z -z 1 )|ν > ρ) log K,
First, we write:

B ǫ div((z -z 1 )ρ) log K = 2 B ǫ ρ log K + B ǫ < (z -z 1 )|∇ρ) log K
which we can write as:

- B ǫ div((z-z 1 )ρ) log K = 2 B ǫ K log Ke u + B ǫ < (z-z 1 )|∇u > K log Ke u + B ǫ < (z-z 1 )|(∇K) log K > e u ,
We can write:

∇(K(log K) -K) = (∇K)(log K)
Thus, and by integration by part we have:

B ǫ < (z -z 1 )|(∇K) log K > e u = B ǫ < (z -z 1 )|(∇(K log K -K)) > e u = = ∂B ǫ < (z-z 1 )|ν > (K log K-K)e u -2 B ǫ (K log K-K)e u - B ǫ < (z-z 1 )|∇u > (K log K-K)e u Thus, -( B ǫ div((z -z 1 )ρ) log K + ∂B ǫ (< (z -z 1 )|ν > ρ) log K) = = - ∂B ǫ < (z -z 1 )|ν > Ke u + B ǫ < (z -z 1 )|∇u > Ke u + 2 B ǫ Ke u
But, we can write the following,

B ǫ < (z-z 1 )|∇u > Ke u = B ǫ < (z-z 1 )|∇u > (K-K(z 1 ))e u +K(z 1 ) B ǫ < (z-z 1 )|∇u > e u ,
and, after integration by parts:

K(z 1 ) B ǫ < (z -z 1 )|∇u > e u = K(z 1 ) ∂B ǫ < (z -z 1 )|ν > e u -2K(z 1 ) B ǫ e u ,
Finaly, we have, for the Wolansky term:

B ǫ div((z -z 1 )ρ) log K + ∂B ǫ (< (z -z 1 )|ν > ρ) log K = = B ǫ < (z -z 1 )|∇u > (K -K(z 1 ))e u + 2 B ǫ (K -K(z 1 ))e u + + ∂B ǫ < (z -z 1 )|ν > (K(z 1 ) -K)e u
But, we have soon that if K is s-holderian with 1 ≥ s > 1/2, around each exteriror blow-up we have, the following estimate:

B ǫ < (z -z 1 )|∇u > (K -K(z 1 ))e u = = B(0,ǫ) < (y -z 1 )|∇v i > (V i (x i + δ i y) -V i (x i ))e vi dy = = B(xi,δiǫ) < (x -x i )|∇u i > (V i (x) -V i (x i ))e ui dy = o(1)M ǫ = o(1) B(xi,δiǫ) V i e ui = o(1) B ǫ Ke u , Thus, B ǫ div((z -z 1 )ρ) log K + ∂B ǫ (< (z -z 1 )|ν > ρ) log K = o(1)M ǫ = o(1) B ǫ

Ke u

We argue by contradiction and we suppose that we have around the exterior blow-up point 2 or 3 blow-up points, for example. We prove, as in a previous paper, that, the last quantity tends to 0. But according to Wolansky paper, see [START_REF] Wolansky | Note on blow-up limits for solutions of ∆u + Ke u = 0 in two dimensions[END_REF]:

B ǫ V i (x i + δ i y)e vi → 8π.
Around each exterior blow-up points, there is one blow-up point. Consider the following quantity:

B i = B(xi,δiǫ) < (x -x i )|∇u i > (V i (x) -V i (x i ))e ui dy.
Suppose that, we have m > 0 interior blow-up points. Consider the blow-up point t k i and the associed set Ω k defined as the set of the points nearest t k i we use step by step triangles which are nearest x i and we take the mediatrices of those triangles.

Ω k = {x ∈ B(x i , δ i ǫ), |x -t k i | ≤ |x -t j i |, j = k}, we write: B i = m k=1 Ω k < (x -x i )|∇u i > (V i (x) -V i (x i ))e ui dy.
We set,

B k i = Ω k < (x -x i )|∇u i > (V i (x) -V i (x i ))e ui dy,
We divide this integral in 4 integrals:

B k i = Ω k < (x-t k i )|∇u i > (V i (x)-V i (x i ))e ui dy+ Ω k < (t k i -x i )|∇u i > (V i (x)-V i (x i ))e ui dy = = Ω k < (x-t k i )|∇u i > (V i (x)-V i (t k i ))e ui dy+ Ω k < (x-t k i )|∇u i > (V i (t k i )-V i (x i ))e ui dy+ + Ω k < (t k i -x i )|∇u i > (V i (x)-V i (t k i ))e ui dy+ Ω k < (t k i -x i )|∇u i > (V i (t k i )-V i (x i ))e ui dy,
We set:

A 1 = Ω k < (x -t k i )|∇u i > (V i (x) -V i (t k i ))e ui dy, A 2 = Ω k < (x -t k i )|∇u i > (V i (t k i ) -V i (x i
))e ui dy,

A 3 = Ω k < (t k i -x i )|∇u i > (V i (x) -V i (t k i ))e ui dy, A 4 = Ω k < (t k i -x i )|∇u i > (V i (t k i ) -V i (x i ))e ui dy.
For A 1 and A 2 we use the fact that in Ω k we have:

u i (x) + 2 log |x -t k i | ≤ C, to conclude that for 0 < s ≤ 1: A 1 = A 2 = o(1),
we have integrals of the form:

A ′ 1 = Ω k |∇u i |e (1/2-s/2)ui dy = o(1),
and,

A ′ 2 = Ω k |∇u i |e (1/2-s/4
)ui dy = o(1).

For A 3 we use the previous fact and the sup + inf inequality to conclude that for 1/2 < s ≤ 1:

A 3 = o(1)
because we have an integral of the form:

A ′ 3 = Ω k |∇u i |e (3/4-s/2)ui dy = o(1).
For A 4 we use integration by part to have:

A 4 = ∂Ω k < (t k i -x i )|ν > (V i (t k i ) -V i (x i ))e ui dy.
But, the boundary of Ω k is the union of parts of mediatrices of segments linked to t k i . Let's consider a point t j i linked to t k i and denote D i,j,k the mediatrice of the segment (t j i , t k i ), which is in the boundary of Ω k . Note that this mediatrice is in the boundary of Ω j and the same decompostion for Ω j gives us the following term:

A ′ 4 = - D i,j,k < (t j i -x i )|ν > (V i (t j i ) -V i (x i ))e ui dy.
Thus, we have to estimate the sum of the 2 following terms:

A 5 = D i,j,k < (t k i -x i )|ν > (V i (t k i ) -V i (x i ))e ui dy.
and,

A 6 = A ′ 4 = - D i,j,k < (t j i -x i )|ν > (V i (t j i ) -V i (x i ))e ui dy.
We can write them as follows:

A 5 = D i,j,k < (x-x i )|ν > (V i (t k i )-V i (x i ))e ui dy+ D i,j,k < (t k i -x)|ν > (V i (t k i )-V i (x i ))e ui dy.
and,

A 6 = - D i,j,k < (x-x i )|ν > (V i (t j i )-V i (x i
))e ui dy-

D i,j,k < (t j i -x)|ν > (V i (t j i )-V i (x i ))e ui dy.
We can write:

D i,j,k < (x-x i )|ν > (V i (t k i )-V i (x i
))e ui dy-

D i,j,k < (x-x i )|ν > (V i (t j i )-V i (x i ))e ui dy = = D i,j,k < (x -x i )|ν > (V i (t k i ) -V i (x j i ))e ui dy = o(1), for 1/2 < s ≤ 1.
Because, we do integration on the mediatrice of (t j i , t k i ), |x -t j i | = |x -t k i |, and:

|V i (t k i ) -V i (x j i )| ≤ 2A|x -t k i | s u i (x) + 2 log |x -t k i | ≤ C, and, |x -x i | ≤ δ i ǫ,
To estimate the integral of the following term: e (3/4-s/2)ui ≤ Cr (-3/2+s) , which is intgrable and tends to 0, for 1/2 < s ≤ 1, because we are on the ball B(x i , δ i ǫ). In other part, for the term:

D i,j,k < (t k i -x)|ν > (V i (t k i )-V i (x i ))e ui dy - D i,j,k < (t j i -x)|ν > (V i (t j i )-V i (x i ))e ui dy.
We use the fact that, on D i,j,k :

|x -t j i | = |x -t k i |, u i (x) + 2 log |x -t k i | ≤ C, |V i (t k i ) -V i (x i )| ≤ 2A|x i -t k i | s ≤ δ s i , and, |V i (t j i ) -V i (x i )| ≤ 2A|x i -t j i | s ≤ δ s i ,
To estimate the integral of the following term: e (1/2-s/4)ui ≤ Cr (-1+s/2) , which is intgrable and tends to 0, because we are on the ball B(x i , δ i ǫ).

Thus,

B i = o(1), Proof of the theorem 2:
Next, we use the formulation of the case of three blow-up points, see [START_REF] Bahoura | About Brezis-Merle problem with holderian condition: the case of 3 blow-up points[END_REF]. Because the blowups points are simple, we can consider the following function:

v i (θ) = u i (x i + r i θ) -u i (x i ),
where r i is such that:

r i = e -ui(xi)/2 , B ǫ V i (x i + δ i y)e vi → 8π. u i (x i + r i θ) = Ω G(x i + r i θ, y)V i (y)e ui(y) dx = = Ω-B(xi,2δiǫ ′ ) G(x i , y)V i e ui(y) dy + B(xi,2δiǫ ′ ) G(x i + r i θ, y)V i e ui(y) dy = We write, y = x i + r i θ, with | θ| ≤ 2 δ i r i ǫ ′ , u i (x i + r i θ) = B(0,2 δ i r i ǫ ′ ) 1 2π log |1 -(x i + r i θ)(x i + r i θ)| r i |θ -θ| V i e ui(y) r 2 i dy+ + Ω-B(xi,2δiǫ ′ ) G(x i + r i θ, y)V i e ui(y) dy u i (x i ) = Ω-B(xi,2δiǫ ′ ) G(x i , y)V i e ui(y) dy + B(xi,2δiǫ ′ ) G(x i , y)V i e ui(y) dy
Hence,

u i (x i ) = B(0,2 δ i r i ǫ ′ ) 1 2π log |1 -xi (x i + r i θ)| r i | θ| V i e ui(y) r 2 i dy+ + Ω-B(xi,2δiǫ ′ ) G(x i , y)V i e ui(y) dy
We look to the difference,

v i (θ) = u i (x i + r i θ) -u i (x i ) = B(0,2 δ i r i ǫ ′ ) 1 2π log | θ| |θ -θ| V i e ui(y) r 2 i dy + h 1 + h 2 ,
where,

h 1 (θ) = Ω-B(xi,2δiǫ ′ ) G(x i + r i θ, y)V i e ui(y) dy - Ω-B(xi,2δiǫ ′ )
G(x i , y)V i e ui(y) dy, and, y) dy.

h 2 (θ) = B(0,2δiǫ ′ ) 1 2π log |1 -(x i + r i θ)y| |1 -xi y| V i e ui(
Remark that, h 1 and h 2 are two harmonic functions, uniformly bounded.

According to the maximum principle, the harmonic function G(x i +r i θ, .) on Ω-B(x i , 2δ i ǫ ′ ) take its maximum on the boundary of B(x i , 2δ i ǫ ′ ), we can compute this maximum:

G(x i +r i θ, y i ) = 1 2π log |1 -(x i + r i θ)y i | |x i + r i θ -y i | ≃ 1 2π log (|1 + |x i |)δ i -δ i (3ǫ ′ + o(1))| δ i ǫ ′ ≤ C ǫ ′ < +∞ with y i = x i + 2δ i θ i ǫ ′ , |θ i | = 1, and |r i θ| ≤ δ i ǫ ′ .
We can remark, for |θ| ≤ δ i ǫ ′ r i , that v i is such that:

v i = h 1 + h 2 + B(0,2 δ i r i ǫ ′ ) 1 2π log | θ| |θ -θ|
V i e ui(y) r 2 i dy,

v i = h 1 + h 2 + B(0,2 δ i r i ǫ ′ ) 1 2π log | θ| |θ -θ| V i (x i + r i θ)e vi( θ) d θ,
with h 1 and h 2 , the two uniformly bounded harmonic functions.

Remark: In the case of 2 or 3 or 4 blow-up points, and if we consider the half ball, we have supplemntary terms, around the 2 other blow-up terms. Note that the Green function of the half ball is quasi-similar to the one of the unit ball and our computations are the same if we consider the half ball.

By the asymptotic estimates of Cheng-Lin, we can see that, we have the following uniform estimates at infinity. We have, after considering the half ball and its Green function, the following estimates:

∀ ǫ > 0, ǫ ′ > 0 ∃ k ǫ,ǫ ′ ∈ R + , i ǫ,ǫ ′ ∈ N and C ǫ,ǫ ′ > 0, such that, for i ≥ i ǫ,ǫ ′ and k ǫ,ǫ ′ ≤ |θ| ≤ δ i ǫ ′ r i , (-4 -ǫ) log |θ| -C ǫ,ǫ ′ ≤ v i (θ) ≤ (-4 + ǫ) log |θ| + C ǫ,ǫ ′ , and, ∂ j v i ≃ ∂ j u 0 (θ) ± ǫ |θ| + C r i δ i 2 |θ| + m × r i δ i + + m k=2 C 1 r i d(x i , x k i ) ,
In the case, we have:

d(x i , x k i ) δ i → +∞ for k = 2 . . . m,
We have after using the previous term of the Pohozaev identity, for 1/2 < s ≤ 1:

o(1) = J ′ i = m ′ + m k=1 C k o(1), 0 = lim ǫ ′ lim ǫ lim i J ′ i = m ′ , which contradict the fact that m ′ > 0. here, J i = B i = B(xi,δiǫ ′ ) < x i 1 |∇(u i -u) > (V i -V i (x i ))e ui dy.
We use the previous formulation around each blow-up point. If, for x j i , we have:

d(x j i , x k i ) δ j i → +∞ for k = j, k = 1 . . . m,
We use the previous formulation around this blow-up point. We consider the following quantity:

J j i = B j i = B(x j i ,δ j i ǫ ′ ) < x i,j 1 |∇(u i -u) > (V i -V i (x j i ))e ui dy.
with,

x i,j 1 = (δ j i , 0), In this case, we set:

v j i (θ) = u i (x j i + r j i θ) -u i (x j i )
, where r j i is such that:

r j i = e -ui(x j i )/2 , B(x j i ,δ j i ǫ ′ ) V i (x j i + δ j i y)e vi → 8π.
We have, after considering the half ball and its Green function, the following estimates: If, for x j i , we have:

∀ ǫ > 0, ǫ ′ > 0 ∃ k ǫ,ǫ ′ ∈ R + , i ǫ,ǫ ′ ∈ N and C ǫ,ǫ ′ > 0,
d(x j i , x k i ) δ j i ≤ C j,k for some k = k j = j, 1 ≤ k ≤ m,
All the distances d(x j i , x k i ) are comparable with some δ j i . This means that we can use the Pohozaev identity directly. We can do this for example, for 4 blow-ups points.

We have many cases: Case 1: the blow-up points are "equivalents", it seems that we have the same radius for the blow-up points.

Case 2: 3 points are "equivalents" and another blow-up point linked to the 3 blow-up points. We apply the Pohozaev identity directly with central point which link the 3 blow-up to the last.

Case 3: 2 pair of blow-up points separated. Case 3.1: the 2 pair are linked: we apply the Pohozaev identity. Case 3.2: the two pair are separated. It is the case of two separated blow-up points, see [START_REF] Bahoura | About Brezis-Merle problem with holderian condition: the case of 1 or 2 blow-up points[END_REF] ACKNOWLEDGEMENT.

The author is grateful to Professor G. Wolansky who has communicated him the private communcation.

,

  such that, for i ≥ i ǫ,ǫ ′ and k ǫ,ǫ ′ -ǫ) log |θ| -C ǫ,ǫ ′ ≤ v j i (θ) ≤ (-4 + ǫ) log |θ| + C ǫ,ǫ ′ , and, ∂ k v j i ≃ ∂ k u j 0 (θ)We have after using the previous term of the Pohozaev identity, for 1/2 < s ≤ 1:o(1) = J j i = B j i = m ′ + = m ′ ,which contradict the fact that m ′ > 0.


Lilia Zaourar
email: lilia.zaourar@lip6.fr

Alix Munier-Kordon

An approximation algorithm for testing memories of an integrated circuit

Keywords: Memory test, Batch, Bin-Packing, Approximation algorithm

Memory testing of an integrated circuit is a real industrial challenge, and presents several interesting original combinatorial optimization problems. A simple model for testing a set of memories, taking into account their test time and power, is first presented. Feasible solutions consist on grouping memories into lots of a maximum fixed power. The aim is to minimize the overall test time for a unique sequential tester. The problem includes the classical Bin-Packing problem and thus is N P -hard. A simple lower bound of the overall test time is first obtained using a continuous version of the problem. A simple heuristic issued from a Next Fit Decreasing strategy is then presented and its performance ratio is proved to be bounded by 2.

Introduction

Nowadays, any integrated circuit (SOC in short for System On Chip) leaving a supply chain is tested automatically. In order to reduce the time to market of a product this testing step has to be as cheap as possible with the least time consumption.

For that purpose, an external tester sends data to the circuit, and compares its answers to those normally expected. A set of components dedicated to the realization of this test phase is generally added to the circuit. Part of the processing is then carried out directly by the chip, significantly speeding the industrial process. Those compoments are called BIST (Built In Self Test).

Memory cores usually occupy a significant area of the SOC and are often designed with most aggressive rules. Thus, testing all these memories became a real challenge and presented original combinatorial problems. Two costs are usually considered in this phase: the total testing time of the memories of a chip and power consumption due to the test procedure. The idea here is to group the overall memories of a chip into different lots that are evaluated separately; each lot has its own testing time and required an amount of power to be tested.

Various grouping schemes have been proposed in the literature. In this work, we are interested only in the optimization criteria with respect to both power and time. The pioneering work on memory BIST sharing was presented by [START_REF] Zorian | A distributed BIST control scheme for complex VLSI devices[END_REF]. The author proposed a new BIST sharing architecture together with a test scheduling that does not exceed power dissipation limit during test procedure. Several techniques for test scheduling were investigated later. In [START_REF] Cp | Simultaneous module selection and scheduling for power-constrained testing of core based systems[END_REF] the authors adressed the issue of test scheduling under power and area constraints. They gave a greedy algorithm with a time complexity of O(n 3 ) to select grouping memories. Numerical results are given for a SOC with less than 10 memories. In [START_REF] Chakrabarty | Test scheduling for core-based systems using mixed-integer linear programming[END_REF] the test scheduling optimization problem is modeled as an open-shop scheduling problem with m machines, and solved by using a Mixed Integer Linear Programming (MILP ) formulation to obtain the optimal schedule. Based on the same assumption, a power constrained MILP model for the precedence and preemptive test scheduling problems has also been presented in [START_REF] Chakrabarty | Precedence-based, preemptive, and power-constrained test scheduling for system-on-a-chip[END_REF]. In [START_REF] Huang | Resource allocation and test scheduling for concurrent test of core-based SOC design[END_REF] the authors formulated the problem as a two dimensional Bin-Packing problem by fixing bounds for the maximum test power and test time. Then, they solved it heuristically by using a Best Fit heuristic algorithm. A survey of techniques used and numerical results can be found in [START_REF] Xu | Resource-constrained system-on-a-chip test: a survey[END_REF].

The main flaw of all the methods adressed previously is that the complexity of the algorithms developed drastically limits the size of the problem considered. The aim of our work is to present a simple model for a sequential BIST tester and efficient heuristics to solve it.

Our paper is organized as follows. In Section 2, we define the memory grouping problem and formulate it as a generalized version of Bin-Packing. Section 3 is devoted to the determination of an optimal solution for a continuous version of our problem, leading to a nice lower bound of the minimum overall test time.

Next Fit Decreasing heuristics are studied in Section 4. It is proved that, if the memories are allocated to lots following non increasing powers, the performance ratio of the built solution may be not bounded. However, it is also proved that this ratio is bounded by 2 if memories are considered following non increasing test times. Section 5 is our conclusion.

Problem formulation

An instance Π of the problem tackled here is defined by a set L of n memories M i , i ∈ {1, • • • , n}, each of them defined by a couple of positive integers (t i , p i ). t i represents the time needed by the tester to evaluate M i , p i is its associated power. An integer value P max corresponding to the power of the tester is also fixed. Lastly, P max should satisfy P max ≥ P for P = max i∈{1,••• ,n} p i .

Memories are grouped into bins (or lots) to be tested. A bin B ⊆ L has a test time T B = max Mi∈B t i and a power P B = Mi∈B p i . Our problem consists in partitioning the set of memories L into a set of bins B such that:

the power of each bin is bounded by P max , i.e. ∀B ∈ B, P B ≤ P max ; -the overall test time

T B = B∈B T B is minimum. Mi M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 M13 ti 6 6 6 4 4 4 4 4 3 3 2 2 2 pi 2 1 1 3 2 2 2 1 3 1 3 1 3
Table 1. Test times and powers of an instance of Π. We also suppose that Pmax = 6.

As example, let consider the instance of Π reported by Table 1. A feasible solution is presented by A feasible solution for the instance of Π given by Table 1.

The sub-problem of Π for which memories are of equal test time (t

1 = t 2 = • • • = t n ) is clearly a Bin-Packing problem.
We conclude that Π is NPhard [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF], and thus the determination of approximation algorithms is of interest. To our best knowledge, Π has never been adressed before. However, several approximation algorithms that have been proposed to solve the classical Bin-Packing problem [START_REF] Coffman | Approximation Algorithms for Bin Packing: A Survey[END_REF] constituted a starting point for our study.

Π can also be formulated as a batch scheduling problem [START_REF] Potts | Scheduling with batching: a review[END_REF] without setup time on a single machine. Tasks correspond to memories. Each task i ∈ {1, • • • , n} has a duration equal to the test time t i . Batches are carried out sequentially. P max is the limit size of a batch.

An optimal solution for the continuous problem

Let consider in this section a continuous version Π cont of the initial problem Π where a memory can be placed in several bins. The power of a memory M i belonging to bins

B cont 1 , • • • , B cont α is split into α positive values p 1 j , • • • , p α j with α i=1 p i j = p j .
This extension of the problem has clearly no application in our industrial context. However, we build easily an optimal solution B cont of Π cont , providing a nice lower bound for the overall test time of Π.

Let us consider a feasible solution B cont for the continuous version Π cont built as follows where each memory is split into at most two bins. Let suppose that memories are numbered as t 1 ≥ t 2 ≥ • • • ≥ t n . For any value i ∈ {1, • • • , n + 1}, the sequence u i is defined as u i = i-1 j=1 p j and we set k = ⌈ un+1 Pmax ⌉ the number of bins B cont α , α ∈ {1, • • • , k} built as:

B cont α = {i ∈ {1, • • • , n}, (α -1)P max -p i < u i < αP max }.
The corresponding values of the memory power are set as follows:

∀i ∈ B cont α , p α i =    p i if (α -1)P max ≤ u i ≤ αP max -p i u i+1 -(α -1)P max if u i < (α -1)P max αP max -u i otherwise.
For the example presented in Table 1, memories are numbered following non increasing test times. A representation of B cont is pictured by 1.

Theorem 1. B cont is an optimal solution for Π cont .

Proof. The proof is by recurrence on the number of bins k. B cont is clearly optimum for k = 1 since all the memories are placed in a same bin.

Let consider now an optimal solution B opt for a minimum number of bin k > 1. Corresponding bins are noted

B opt 1 , • • • , B opt k ⋆ with k ⋆ ≥ k. Let suppose that B opt 1 has a maximum test time, i.e. T B opt 1 = max i∈{1,••• ,n} t i .
Starting from B opt and using simple exchange arguments, it is possible to build another optimal solution B ′opt such that, the bin with the maximum test time

B ′opt 1 = B cont 1 .
Remaining memories define another instance I of Π cont with a minimum number of bins equal to k -1. By recurrence, bins B cont . We obtained lastly that

T B opt = T B ′opt = T B ′opt 1 + k ⋆ j=2 T B ′opt j = T B cont 1 + k j=2 T B cont j = T B ,
which concludes the recurrence proof.

Performance ratio of Next Fit Decreasing strategies

We observe that classical simple strategies for approximatively solving the Bin-Packing problem may have a non-bounded performance ratio. These algorithms only take into account the size of the objects, corresponding in our case to the power of the memories. In the worst case, each new bin will contain a memory with a maximal test time.

Let consider first Next Fit Decreasing strategy for which memories are numbered and treated following non increasing powers, i.e.,

p 1 ≥ p 2 ≥ • • • ≥ p n . Each
opt = ∆ 1 + (P max -1)∆ 2 = 2∆ 1 .
The ratio is then equal to T T opt = P max 2 , which is not bounded.

We study in the following the performance of the Next Fit Decreasing strategy where memories from L are considered following their non increasing test times. It is supposed thus that they are numbered such that t

1 ≥ t 2 ≥ • • • ≥ t n .
Figure 1 presents the feasible solution obtained by a Next Fit Decreasing strategy applied to our example presented by Table 1.

Theorem 3. Let the integer K = ⌊ Pmax P -1 ⌋ -1.
The performance ratio of the Next Fit Decreasing strategy where memories are considered following their non increasing test times equals 1 + 1 K .

This last bound is asymptotically tight. Indeed, consider an instance of our problem given by n 1 memories of power P , and n 1 × (P max -P ) memories of unit power. Test times of memories are all equal to ∆.

An optimal solution can be found by constructing n 1 bins, each of them containing one memory of power P . Remainings slots are all filled with memories with unit power. The overall test time is here equal to T opt = n 1 × ∆. Now, a Next Fit Decreasing strategy may lead to a solution where the first n 1 bins are filled with one memory of power P and P max -2P + 1 unit memories. It remains n 1 × (P -1) memories of unit power that are placed into n 1 × P -1 Pmax bins. The overall test time is then equal to T = n 1 × ∆ × (1 + P -1 Pmax ). Setting α = Pmax P -1 , we observe that for important values of α that

1 α(1-1 α ) ≈ 1 α (1 + 1 α ) = 1 α + o( 1 α
). Thus, the ratio T T opt = 1 + 1 α ≈ 1 + 1 α(1-1 α ) , and the performance ratio is tight when α = Pmax P -1 → +∞.

Conclusion and future works

Theoretical perspectives rely in the study of other approximation algorithms to improve the performance ratio. These algorithms may be implemented and compared experimentally with other more complex algorithms (as example genetic algorithms [START_REF] Zaourar | A Complete methodology for determining memory BIST optimization under sharing constraints[END_REF]) to solve real-life instances.

Figure 1 .

 1 Fig.1. A feasible solution for the instance of Π given by Table1.

Figure 2 . 4 = 2 1 . 1 = 6 , T B cont 2 = 4 , T B cont 3 = 4 , T B cont 4 = 2 and T B cont 5 = 2 . 5 13Fig. 2 .

 2421162434425252 Fig.2. An optimal solution B opt for the continuous version Π cont of the instance of Π expressed by Table1.

2 ,

 2 • • • , B cont k correspond to an optimal solution for I, and thus k j=2 T B cont j = k ⋆ j=2 T B ′opt j

  new memory M i is placed in the current bin B. If there is no enough place, B is closed and a new current bin is opened to receive M i . Theorem 2. The performance ratio of the Next Fit Decreasing strategy where memories are considered following their non increasing power is not bounded. Proof. Let consider an instance composed by n 1 = P max > 1 memories of test time ∆ 1 and n 2 = n 1 ×(P max -1) memories of test time ∆ 2 = ∆ 1 P max -1 . Powers are supposed to be unit. A solution of Next Fit Decreasing algorithm may be obtained such as each bin contains one memory of test time ∆ 1 and (P max -1) of test time ∆ 2 . The overall test time equals T = P max ∆ 1 . Now, if every bin contains only memories of same test time, the overall test time equals T


Claude Boutin

Pierre Roussillon

Assessment of the Urbanization Effect on Seismic Response

come   L'archive ouverte pluridisciplinaire