W Cayzac

) M Pomorski

B Canaud

D Deslandes

J Fariaut

D Gontier

E Lescoute

J G Marmouget

F Occelli

G Oudot

C Reverdin

J E Sauvestre

A Sollier

G Soullié

C Varignon

B Villette

A Blažević

CVD diamond detector with interdigitated electrode pattern for time-of-flight energy-loss measurements of low-energy ion bunches

CVD diamond detector with interdigitated electrode pattern for time-of-flight energy-loss measurements of low-energy ion bunches

Ion stopping experiments in plasma for beam energies of few hundred keV per nucleon are of great interest to benchmark the stopping-power models in the context of inertial confinement fusion and high-energy-density physics research. For this purpose, a specific ion detector on chemical-vapor-deposition diamond basis has been developed for precise time-of-flight measurements of the ion energy loss. The electrode structure is interdigitated for maximizing its sensitivity to low-energy ions and it has a finger width of 100 µm and a spacing of 500 µm. A short single α-particle response is obtained, with signals as narrow as 700 ps at FWHM. The detector has been tested with α-particle bunches at a 500 keV per nucleon energy, showing an excellent time-of-flight resolution down to 20 ps. In this way, beam energy resolutions from 0.4 keV to a few keV have been obtained in an experimental configuration using a 100 µg/cm 2 thick carbon foil as energy-loss target and a 2 m time-of-flight distance. This allows a highly precise beam energy measurement of δE/E ≈ 0.04-0.2 % and a resolution on the energy loss of 0.6-2.5 % for a fine testing of stopping-power models.

The stopping power (dE/dx) of ions in ionized matter 1,2 is a central issue in high-energy density physics (HEDP) 3 and, foremost, in inertial confinement fusion (ICF) [4][5][6][7][8] . However, a systematic experimental database is still missing and precise measurements of the energy loss of ions in plasma are required in order to benchmark the theoretical stopping-power models. The largest differences between the stopping predictions of various models are reported near the stopping-power peak, for projectile velocities comparable to the velocity of the thermal electrons in plasma 1 . This maximum is of special importance as it gives rise to the Bragg peak of energy deposition in a given target, yet measurements in this parameter range are very scarce 9,10 .

Experiments aimed at measuring the ion energy loss close to the stopping-power peak in plasma are considered at CEA-DIF on the 4MV Van-De-Graaff accelerator facility in combination with the GCLT (Générateur de Chocs Laser Transportable) laser system. In these experiments, a 100 µg/cm 2 thick carbon foil is heated by two laser beams to a hot and highly ionized plasma state. For the achievable plasma temperatures of few tens to few hundred eV relevant for ICF and HEDP, the stopping power for interacting projectile ions peaks at beam energies of few hundred keV per nucleon. Hence, the plasma is probed by a bunched beam of α-particles in this low energy range. The ion energy loss in plasma is measured using the time-of-flight (TOF) method. This requires a detector with excellent timing properties for precise TOF measurements, a sufficient radiation hardness to withstand an important ion flux, a sufficiently large detection area, and an optimized sensitivity to low-energy ions. Here, these conditions are fulfilled by a detector on chemical-vapor-deposition (CVD)-diamond basis.

CVD-produced diamond features remarkable properties in terms of radiation hardness, sensitivity, high time resolution and fast time response. These characteristics, associated with suited low-noise broadband electronics, make CVD-diamond an ideal material for both high-rate single particle counting and ion TOF applications 11,12 . This is why, during the past 20 years, CVD-diamond has been increasingly used for ion detection in particle accelerator facilities, in atomic, nuclear and HEDP experiments [13][14][15][16][17] as well as for beam monitoring and heavy ion dosimetry 18,19 . TOF resolutions in the order of 20-40 ps have been reported 13,14,16,17 .

CVD-diamond detectors used in previous experiments on the energy loss of ions in plasma 10,20,21 are described or are similar to the ones presented in Ref. 22 . As in these latter works, the diamond film is here chosen to be polycrystalline. In contrast to single-crystal CVD diamond, polycrystalline CVD diamond is indeed available in larger areas and is more cost-effective. Nevertheless, it features a lower charge-collection efficiency (CCE) notably due to charge trapping at the grain boundaries 23,24 .

The detectors used in previous experiments are based on a plane capacitor electrode (or "sandwich") geometry, with metalization on both sides of the diamond film. This configuration results in a uniform electric field accross the sample and in a charge transport normal to the electrodes. It is therefore most suited to the detection of ions that have a range in diamond larger or similar to the film thickness. In this way, the ion energy deposition as well as the ionization density are uniform in the diamond volume, which leads to an optimized charge collection and time resolution. For example, in the energy-loss experiments of Ref. 20,21 , the projectile ions have an energy of 4 MeV per nucleon and a range in diamond around 22 µm, and the diamond films are 20 µm thick 22 . In contrast, in Ref. 10 , where the energy loss at the stoppingpower peak is measured, the detected ions have a lower energy of 500-600 keV per nucleon. Then, the ion range in diamond is only about 3 µm, while the diamond thickness is 13 µm. In this case, polarization effects due to a non-uniform energy deposition in the sample are likely to generate a significant space charge that degrades the charge collection and, thus, the signal amplitude [25][26][27][28] . Therefore, even if the recorded bunch signals did permit a sufficiently precise energy-loss analysis, the time resolution of the measurements was not optimal for these low-energy ions using this detector geometry.

In order to ensure highly precise TOF measurements at projectile energies of a few hundred keV per nucleon for the energy-loss experiments at CEA-DIF, we have developed a different CVD-diamond detector based on a coplanar electrode geometry. In this alternative configuration, the electrodes are interdigitated and are both patterned on the same surface of the diamond film, while the other surface is not metallized. Then, the electric field remains close and nearly parallel to the diamond surface, which causes a charge transport parallel to the surface. Hence, the detection efficiency is optimized near the detector surface, which is well-suited to low-energy ions whose range is comparable to the field depth. A coplanar electrode geometry is all the more relevant for polycrystalline diamond when patterned on the growth surface as it restricts charge transport to the diamond region where the grains are largest in size.

The interdigitated electrode geometry has shown promising timing performances in the detection of αparticles [29][30][31][32][33] and it has also been successfully applied in the detection of UV and X-ray radiation as well as in charged-particle TOF spectroscopy [34][35][36][37] . In contrast to the sandwich configuration, the CCE and, thus, the pulse height response, is non-uniform accross the active diamond surface due to the non-uniform electric field profile. To a lesser extent, pulse amplitudes are also influenced by charge-trapping effects due to the polycrystalline nature of the diamond. However, in our experiments we consider bunch signals averaged over at least several hundred single-ion pulses.

The detector has been assembled and characterized at CEA-LIST. Its layout and electrical circuit are presented in Fig. 1. The diamond is a free-standing optical-grade polycrystalline film supplied by Diamond Materials 38 . It has a total area of 23×23 mm 2 and a thickness of 300 µm. The electrode fingers are made of a 200 nm thick aluminium layer. They were patterned using a standard photolithography technique on the diamond growth surface, where the grain size is estimated to be around 60 µm. The electrodes have a finger width of 100 µm and a spacing of 500 µm. The active detector area is 20×20 mm 2 , which was chosen according to beam transport simulations using the Monte-Carlo toolkit GEANT4 39,40 . Such area indeed guarantees the detection of at least few hundred ions per bunch for the experimental beam and target parameters described below (see Fig. 5). In order to minimize the capacitance value and thus the signal width, the electrode pattern is split in four equal segments of 10×10 mm 2 . According to the model by Olthuis et al. 41 , each segment features a capacitance value of 6.2 pF. Combined with the 50 Ω impedance of the signal transmission line, this leads to a detector decay time of 315 ps. This short time response, combined with the expected experimental bunch width of 1-2 ns at full width at half maximum (FWHM), provides access to narrow signals and therefore a high TOF resolution. The metallized diamond substrate was fixed on its printed circuit board (PCB) using araldite glue. The contacts of the electrode segments and of the ground were bonded to the PCB tracks with silver loaded resin. Finally, the device was mounted within an aluminium housing.

The current-voltage curve of the detector, measured under vacuum, is displayed in Fig. 2 for the four segments and for voltage values between -400 V and +400 V. As is shown, the leakage current has negligible values smaller than 150 pA. The detector was characterized in terms of transient current signals and of CCE distribution using α-particles at 5.486 MeV energy from an uncollimated 4 kBq 241 Am radioactive source, located at a distance of 10 mm from the detector surface. The measurements were carried out in air, as tests in air and in vacuum turned out to deliver very similar results. The data were FIG. 4: a): charge collection efficiency (CCE) spectrum for one detector segment (S1) and bias voltages of -300 V and +300 V, normalized to a reference spectrum obtained with a 100 % CCE single crystal CVD diamond detector. b): normalized charge collection spectrum measured after 50000, 100000 and 150000 events, corresponding to roughly 5, 10 and 15 hours of irradiation with the α-particle source.

the charge collection process over time is illustrated in Fig. 4b, showing the measured charge collection spectrum after irradiation times of approximately 5, 10 and 15 hours which correspond to 50000, 100000 and 150000 detected events respectively. These data demonstrate that there is no degradation of the charge collection over time due to polarization in diamond. Due to the slightly higher efficiency using the positive bias configuration, the detector is always operated with a bias voltage of +300 V in the following.

It can be noted that due to the broad CCE spectrum and the relatively low average CCE value, measurements with the detector require sufficient ion statistics for obtaining exploitable signals as well as for reaching the reported timing properties. This is why the detector is only suited for measurements implying a sufficient statistical sample of events, e.g. using ion bunches with hundreds or thousands of particles. But it is not necessarily appropriate for measurements with single ionizing particles, that may induce strongly varying signal amplitudes and timing characteristics depending on the position where they impinge on the detector. It should also be noted that the 5.486 MeV energy α-particles used for the detector characterization have a range in diamond of around 13 µm, as can be estimated using the SRIM stopping database [START_REF] Ziegler | The Stopping and Range of Ions in Matter[END_REF] . As α-particles for the energies of interest of few hundred keV per nucleon have a range of only a few micrometers in diamond, transient signals as well as CCE spectra are likely to differ for these projectiles.

The detector has been tested at the 4MV accelerator facility of CEA-DIF, where proton and α-particle beams in the 0.5-4 MeV energy range can be generated. We used α-particles at 500 keV per nucleon energy (total energy E = 2 MeV) as projectiles. The beam was bunched with a 5 µs period using a newly implemented field-programmable gate array. The beam current was of few hundred nA, which resulted in an ion fluence on the detector of around 5×10 6 cm -2 s -1 . In a laser-induced plasma, the target conditions vary significantly over a nanosecond time scale. Therefore the bunches, of originally 10-15 ns width, are shortened to 1-2 ns at FWHM with a Mobley compression system [START_REF] Mobley | [END_REF] . The beam energy resolution from the accelerator source is of the order of δE/E ≈ 10 -3 . In the beam-plasma experiments, the ion energy loss in the target is determined by comparing the TOF of the bunches that interact with the solid target or with the plasma and those that propagate in vacuum.

Here, we evaluate the detector TOF resolution by measuring the bunch signals after propagation in vacuum. Then, we present an example of TOF measurement after an approximately 2 m distance following the ion interaction with a carbon foil of 100 ± 1µg/cm 2 thickness and 1.3 g/cm 3 density. According to the GEANT4 simulations, the ion energy loss in this target is ∆E = 143.9 keV, with a straggling in energy at 1σ of 7.0 keV. It can be noted that the energy loss of 2 MeV energy α-particles in the aluminium electrode of 200 nm is estimated to be 54 keV, i.e. 2.7 % of the beam energy, which has a negli- shown in Fig. 3 is also plotted for comparison, its amplitude being normalized to the one of the shown bunch signal in vacuum. The signal amplitude with the target tends to be lower due to the angular straggling but no strict comparison can be done due both to possible fluctuations of the source and to the spatially non-uniform detector pulse height response. The analysis of the bunch signals in vacuum gives an estimation of the optimum detector resolution. On the other hand, bunch signals after the target are convoluted with the straggling functions specific to the considered target, which leads to a degraded measurement resolution. For the considered TOF measurement using ion bunches, the TOF resolution is defined as the fluctuation of the measured bunch period. As the TOF of one bunch is given by its signal center of mass, the TOF resolution δt is evaluated using the 1σ fluctuation of the centers of mass of two consecutive bunch signals t i and t i+1 . The distributions of the measured t i+1 -t i are displayed in Fig. 7 for 200 bunch signals coming from 5 distinct measurement series of 40 bunches each. All the data discussed in the following are averaged over these measured 200 bunches. Fitting the distributions of t i+1 -t i with Gaussian functions, the TOF resolution is determined as

δt = σ(t i+1 -t i )/ √ 2.
The energy resolution δE is deduced knowing the projectile energy E, its velocity v and the TOF distance d, using the relation δE/E = 2 δt v/d. For the bunches propagating in vacuum (Fig. 7a), we obtain a TOF resolution δt vac = 20 ps, which gives an estimate of the intrinsic time resolution of the detector. This value corresponds to an excellent energy resolution δE vac = 0.4 keV of the ions at the target position, which represents 0.02 % of the projectile energy E. This value is better than the energy resolution from the accelerator because only a limited interval of ion energies is detected due to the enhanced beam divergence with the Mobley compression, together with the small detector solid angle. On the other hand, the TOF resolution obtained with the carbon target (Fig. 7b) is approximately δt tar = 40 ps, which corresponds to δE tar = 0.7 keV. Hence, the degradation of the resolution due to the straggling is moderate and we still resolve about 0.04 % of the ion energy. Consequently, we obtain an excellent resolution on the ion energy loss ∆E in the solid target of δ ∆E = δE 2 vac + δE 2 tar ≈ 0.8 keV, or 0.6 % of ∆E. The data are summarized in Table I. In the energy-loss experiments with the plasma, the beam collimation is necessary due to the small diameter of the laser focal spot on the target of 0.5 mm compared to the diameter of the incoming ion beam of around 5 mm at FWHM. Therefore, one pinhole is required before the target position in order to guarantee quasi-monodimensional plasma conditions seen by interacting ions, and another pinhole is required after the target position for restricting the detector solid angle to the ions that have interacted with those uniform conditions. GEANT4 beam transport simulations accounting for the beam emittance allowed to find an optimum configuration with a 0.5 mm diameter pinhole located 30 mm in front of the target and another 0.3 mm diameter pinhole positioned 30 mm behind the target (see Fig. 5).

A similar analysis of the detector signals is performed for the collimated beam and the results are also shown in Table I. The signal amplitude and width at FWHM are reduced due to collimation. The TOF and the energy resolutions obtained in vacuum are comparable to the ones found without collimation due to sufficient ion statistics. However, with the target the signal-to-noise ratio is significantly decreased owing to a 80 % smaller ion collection on the detector due to angular straggling as indicated by the GEANT4 results. Consequently, the TOF resolution is degraded to δt tar = 150 ps, which leads to a resolution of δE tar = 3.5 keV on the ion energy. This still corresponds to a highly precise measurement of 0.17 % of the ion energy and it leads to a resolution of δ ∆E = 3.6 keV or 2.5 % on the ion energy loss ∆E.

In conclusion, our detector permits an excellent TOF resolution down to 20 ps for α-particle bunches at 500 keV per nucleon energy. This is comparable to the resolutions reached with high-energy ions and a plane capacitor electrode geometry. The discrepancies of up to 30 % in the stopping-power predictions around the stoppingpower peak in a laser-induced plasma 1 lead to energy-loss differences of at least several tens of keV for the considered carbon target. The energy-loss resolution of a few keV or less obtained from TOF measurements using our detector clearly enables to distinguish these differences experimentally and, thus, to benchmark the stoppingpower models. Therefore the detector satisfies the requirements for the energy-loss experiments at CEA-DIF.

It can be noted that a few studies report a worse radiation hardness of diamond compared to silicon for low-energy ions 26,45 . However, in our case possible polarization effects due to radiation damage are mitigated by the interdigitated structure. The absence of polarization effects can be noticed from the stability of the charge collection over time shown in Fig. 4b. This is also corroborated and reinforced by the fact that no signal degradation was observed in our experiments with ion bunches after a flux of 10 10 -10 11 ions cm -2 on the detector. In view of the non-uniform electric field profile due to the interdigitated structure and in particular in order to understand the relatively small measured CCE values, a more detailed characterization of the detector response will be performed. For this purpose, measurements using the Ion Beam Induced Charge (IBIC) method 46,47 as well as the Transient Current Technique (TCT) 48 for beam energies around 500 keV per nucleon are planned. In this way, the CCE and the temporal pulse response will be mapped accross the detector active surface for the exact projectile conditions of the experiment. This will enable us, with the help of simulations of the electric field, to optimize the electrode geometry and, thus, the measured bunch signals.

FIG. 1

 1 FIG. 1: a) Picture of the diamond film with its electrode pattern. b) Picture of the assembled detector. c) Scheme of the electrode pattern, made of four distinct segments, and of the circuit for signal transmission.

FIG. 2 :FIG. 3 :

 23 FIG. 2: I-V curve for the four detector segments measured under vacuum.

FIG. 5 :FIG. 6 :

 56 FIG. 5: Setup for the test of the detector on the 4 MV accelerator facility.

FIG. 7 :

 7 FIG.7: Distribution of time differences t i+1 -t i between two consecutive ion bunches for a series of 200 bunches from 5 distinct measurement series. The data are shown for a propagation in vacuum (a)) and for a 2 m propagation after beam slowing down in the carbon target (b)). Each distribution is fitted with a Gaussian function for estimating the corresponding bunch TOF resolution.

TABLE I :

 I Mean signal amplitude, width at FWHM as well as TOF (δt) and energy (δE) resolutions obtained for bunch measurements in vacuum and with a 100 µg/cm 2 thick carbon target and a 2 m TOF distance, as well as resolution on the measured energy loss in the target δ ∆E . The data are presented without and with beam collimation respectively.

	No collimation Amplitude Width δt	δE	δE/E δ∆E δ∆E/∆E
	Vacuum	2.4 V	1.4 ns 20 ps 0.4 keV 0.02 %	-	-
	Target	1.9 V	1.9 ns 40 ps 0.7 keV 0.04 % 0.8 keV 0.6 %
	Collimation Amplitude Width δt	δE	δE/E δ∆E δ∆E/∆E
	Vacuum	0.3 V	0.9 ns 40 ps 0.8 keV 0.04 %	-	-
	Target	0.09 V	1.8 ns 150 ps 3.5 keV 0.17 % 3.6 keV 2.5 %

ACKNOWLEDGMENTS

We thank N. Skukan for the manufacturing of the detector printed circuit board in short time delays. We acknowledge B. Lommel and the staff of the Target Laboratory of GSI for producing the carbon foils used in the measurements. We thank the operating team of the 4MV accelerator as well as the dedicated mechanical workshop for their excellent support in the experiments.


Célia Martinie

Eric Barboni

David Navarre

Philippe Palanque

Racim Fahssi

Erwann Poupart

Eliane Cubero-Castan

Multi-Models-Based Engineering of Collaborative Systems: Application to Collision Avoidance Operations for Spacecraft

Keywords: Task and interactive systems models, CSCW, groupware, space systems

The work presented in this paper is based on a synergistic approach [1] integrating models of operators' tasks (described using the HAMSTERS notation) with models of the interactive system (described using the ICO notation) they are using. This synergistic approach makes it possible to bring together two usually independent (but complementary) representations of the same world. Even though supported by modeling and simulation tools, previous work in this area was rather theoretic focusing on concepts and principles in order to articulate this synergistic use of the models. The current article extends this line of research to address groupware applications. These extensions are performed on HAMSTERS notation in order to describe activities involving multiple users dealing with information flow, knowledge they are required to master and communication protocol (synchronous or asynchronous). Other extensions are performed on PetShop tool (supporting the ICO notation) in order to model and execute local and distant groupware applications. These extensions have been brought together by a more complex synergistic module bringing the two views together. Lastly, these extensions have been used for the modelling, design, and construction of a groupware system dedicated to collision avoidance of spacecraft with space debris. This case study is used to assess the applicability of the contributions and to identify paths for future work.

INTRODUCTION

The evolution of computer use from one computer for several persons to many computers for one person could have been the end of multi-user computing. However, the widespread of internet and the rise of social computing has demonstrated that dealing with single user applications is nowadays part of history. Designing interactive systems thus requires most of the time to need to address the needs of group of users involved in common tasks for which the communication, cooperation and production is mediated by computers. Despite this undeniable situation, most of the research contributions in the area of interactive systems engineering still focus on single user applications. This is easily understandable as multi-users application are far more difficult to build than single user ones. This difficulty comes from different sources:

• The difficulty to gather and understand the requirements as well as the need of the users;

• The difficulties to address the required communication infrastructures in order to allow both synchronous and asynchronous communication between the users;

• The difficulty to ensure usability of these applications that are used jointly by different users (with different characteristics and needs) and under different environmental conditions (time zones, seasons, light, sound, …);

• The difficulty to ensure the reliability of these computing systems involving underlying communication mechanisms, networks… This paper aims at proposing a model-based approach for the design of usable and reliable collaborative applications.

To address the usability issue we propose a notation for describing collaborative task i.e. tasks having group of users trying to achieve common goals. This notation extends current models such as GTA [START_REF] Van Der Veer | GTA: Groupware Task Analysis -modeling complexity[END_REF] or CTT [START_REF] Mori | CTTE: support for developing and analyzing task models for interactive system design[END_REF]. As for CTT, which the most mature notation in that domain, extensions refine further the task types (see section 3), adds explicit representation of information and knowledge required for performing the tasks and does not require the construction of an "artificial" task model describing the collaboration.

To address reliability, we propose the use of the ICO formalism and its related tool PetShop extended in order to edit and execute models of interactive distributed applications. This work takes advantage of previous work done with ICO notation to formally specify distributed applications over Corba middleware [START_REF] Bastide | Formal specification of CORBA services: experience and lessons learned[END_REF]. Following the philosophy presented in [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF] we propose also a synergistic approach integrating models of operators' tasks (described using the extended HAMSTERS notation) with models of the interactive system (described using the ICO notation).

These various elements are successively presented in the paper. This presentation is followed by the description of the application of the approach on a real life case study from the space domain. This case study consisted in designing and modeling a collaborative collision avoidance management application for the CNES (French Space Government Agency) Orbit Computation Center. Current existing and in use applications are not supported by dedicated tools for collaboration. They are distributed over many time zones, involve multi-national teams and aim at forecasting and avoiding collisions between spacecraft and space debris.

RELATED WORK

In the field of Computer Supported Cooperative Work (CSCW) and groupware, many contributions deal with classification and properties of groupware applications [START_REF] Rama | A survey and comparison of CSCW groupware applications[END_REF], but also with guidelines about how to design and evaluate the usability of such applications [START_REF] Cockburn | Four principles for groupware design[END_REF]. Another thread of work addresses user interfaces, interaction techniques and underlying computer-based tools for supporting collaborative activities [START_REF] Sun | Xpointer: an x-ray telepointer for relaxed-spacetime wysiwis and unconstrained collaborative 3d design systems[END_REF].

The engineering of groupware applications is also represented amongst the scientifics contributions. For example, Jakobsen et al. propose a collaborative development environment for software development [START_REF] Jakobsen | Work Item and People Dashboard for Software Development Teams[END_REF] while Bates et al. propose an applicative framework for integrating collaborative functionalities [START_REF] Bates | Integrating real-world and computer-supported collaboration in the presence of mobility[END_REF]. Wu and Graham [START_REF] Wu | Toward Quality-Centered Design of Groupware Architectures[END_REF] propose an architectural design framework for software architectures of collaborative applications based on the concept of workspace while Greenberg et al. [START_REF] Roseman | Building Real-Time Groupware with GroupKit, a Groupware Toolkit[END_REF] propose a toolkit for the construction of real-time groupware.

Model-based approaches for engineering groupware applications can be of several types. Workflow approaches such as YAWL [START_REF] Van Der Aalst | Yet Another Workflow Language[END_REF] target at describing and simulating workflow activities systems and subsystems while some recent approaches such as BPEL4People try to take into account user's activities [START_REF] Holanda | Performance evaluation of web services orchestrated with ws-bpel4people[END_REF]. Task-model based approaches target at describing collaborative activities involving group of users collaborating to achieve a common goal [START_REF] Van Der Veer | GTA: Groupware Task Analysis -modeling complexity[END_REF] [18] [START_REF] Jourde | COMM notation for specifying collaborative and multimodal interactive systems[END_REF]. UML-based and tool supported approaches have also been proposed [START_REF] Giraldo | A Model Based Approach for GUI Development in Groupware Systems[END_REF] to support development of collaborative applications. However, while the firstly mentioned contributions focus on user interface and interaction techniques and the later ones on workflows and activities of group of users, none of them propose a solution to bring those two worlds together and address in one single framework these two threads of work that are required to develop usable groupware. Indeed, while efficiency of interaction can be addressed through user interface design, the effectiveness of communication tools and interaction techniques can only be addressed by exhaustive representation of tasks to be performed by collaborating users.

AN INTEGRATED ENVIRONMENT SUPPORTING THE CO-EXECUTION OF TASKS AND GROUPWARE

We propose a synergistic use of task and system models for ensuring consistency, coherence and conformance between collaborative activities and their associated distributed user interfaces and applications. In order to reach this research goal, several extensions that have been made to an existing framework previously introduced in [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF]. The presented framework and tool suite is composed of:

• A modeling and software development environment for interactive systems (Petshop).

• A modeling and simulation CASE tool for engineering user tasks (HAMSTERS).

• A synergistic module for linking system behavioral models and user task model, which then enables their coexecution (Synergistic module).

Petshop extensions

The very early versions of Petshop tool followed a Corba approach to handle communication between models [START_REF] Bastide | Formal specification of CORBA services: experience and lessons learned[END_REF]. Naming Service and Interface Repository were mandatory parts of Corba to make communication possible. But as Corba implies a time consuming workflow (IDL compilation, IDL registration), the Naming Service and Interface Repository were centralized and then the prototyping activities were complex.

As Petshop is Java based, we naturally studied Java RMI in order to reduce the compilation phase (as it was embedded in Java). However, the centralized registration issues remained. In order to ease deployment and more flexibility, the communication layer was updated to follow a peer to peer approach, where each Petshop instance is serving models they run. The proposed implementation uses the Ivy bus. The Ivy protocol 1 was initially designed for broadcasting text messages using regular expressions (regex) for prototyping Air Traffic Control applications. As the approach is using regex, it makes possible to deploy lightweight clients on separate computers. Those separate computers are not able to detect some specifics messages on the bus, which makes it possible to log workflows without polluting the client computers. One of the main advantages of the Ivy approach is that its adoption didn't require modifying the ICO notation which was originally designed for describing systems as a set of cooperating instances of classes (independent from their location).

HAMSTERS extensions

The HAMSTERS notation and CASE tool has been introduced in 2010 in order to provide support for tasksystem integration at the tool level [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF]. Since then, this tool and notation has been refined several times in order to provide support for:

• Automation design. The notation has been extended to help with the analysis of function allocation between human and system thanks to the refinement of cognitive tasks into analysis and decision subtypes of cognitive tasks according to the Parasuraman model of human information processing [START_REF] Martinie | Task-Model Based Assessment of Automation Levels: Application to Space Ground Segments[END_REF].

• Structuring a large number and complex set of tasks introducing the mechanism of subroutines [START_REF] Martinie | Structuring and Composition Mechanisms to Address Scalability Issues in Task Models[END_REF].

• Precise description of knowledge, information and objects required and manipulated [START_REF] Martinie | Extending Procedural Task Models by Explicit and Systematic Integration of Objects, Knowledge and Information[END_REF] in order to accomplish tasks.

These elements are necessary to describe collaborative activities but they are not sufficient. Hereafter are the extensions we propose in order to deal with groupware.

Adding notation elements to describe collaborative activities

Collaborative work is performed by several persons, each one having a role in the achievement of common goals. The concept of role we are using is the same as the one used in [START_REF] Mori | CTTE: support for developing and analyzing task models for interactive system design[END_REF] and [START_REF] Van Der Veer | GTA: Groupware Task Analysis -modeling complexity[END_REF]. Figure 1 illustrates the structure of a HAMSTERS project with several roles, each of them having associated task models structured according to the mechanism of subroutines introduced in [START_REF] Martinie | Structuring and Composition Mechanisms to Address Scalability Issues in Task Models[END_REF]. In the same way, we also integrate the concept of actor [START_REF] Van Der Veer | GTA: Groupware Task Analysis -modeling complexity[END_REF] in the HAMSTERS notation and tool.

Collaborative work can be described at different abstraction levels: at the group level and at the individual level. A group task is a set of task that a group has to carry out in order to achieve a common goal [START_REF] Mcgrath | Groups: Interaction and Performance[END_REF], whereas a cooperative task is an individual task performed by a person in order to contribute to the achievement of the common goal [START_REF] Roschelle | The construction of shared knowledge in collaborative problem solving[END_REF]. In order to be able to describe group tasks, we introduce several new task types illustrated in Figure 2 (in the last right column). These group tasks provide support for describing high level activities that a group of person have to accomplish:

• An abstract group task is a task that can be decomposed into user, system, interactive and collaborative tasks.

• A group (of users) task is task that can be decomposed in user and collaborative user tasks.

• An interactive group task can be decomposed in interactive and collaborative interactive tasks.

Figure 2. Task types in HAMSTERS

• A system group task can be decomposed in system tasks. The refinement of group tasks into low-level activities needs fine-grain task types to describe individual and cooperative tasks that have to be performed in order to contribute to the group activities. As individual task types were already available within HAMSTERS, we then introduce cooperative tasks, illustrated in Figure 2. A cooperative task is a task related to a role and accomplished in correlation with another cooperative task that relates to a different role. A cooperative task may be of various types within the user and interactive main family types.

Cooperative tasks may be performed within various spacetime constraints (local/distant, synchronous/asynchronous) [START_REF] Ellis | Groupware: some issues and experiences[END_REF]. These constraints can be described with notation elements illustrated in Figure 3. Adding edition and simulation capabilities

Several functionalities have been added to HAMSTERS CASE tool2 in order to support the edition and simulation of tasks models describing collaborative activities:

• At the edition level, a mechanism to link cooperative tasks across task models belonging to different roles (by mean of contextual menu appearing after a right click on a cooperative task and proposing the list of available cooperative tasks in the other task models belonging to the other roles, as illustrated in Figure 5).

• At the simulation level, a mechanism to enable the execution of several models belonging to different roles.

HAMSTERS make it possible to structure users' activities belonging to one role in several tasks models edit several task models. The association between cooperative tasks of different roles is not made across an additional task model (as for example the cooperative task model in CTTe [START_REF] Mori | CTTE: support for developing and analyzing task models for interactive system design[END_REF]) but it is achieved via an internal correspondence table in the tool.

Figure 5. Defining correspondence of cooperative tasks of 2 task models representing different roles

Synergistic module extensions

The synergistic module has been improved for both design time editing of correspondences and runtime simulation to support collaborative activity modelling and simulation.

Design time

To support collaborative simulation, the editing of correspondences requires three main improvements w.r.t what have been previously done [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF]:

• Allowing the use of several task models instead of a unique one.

• Allowing the use of several collaborative ICO models instead of models concerning a local instance of the application.

• Taking into account cooperative input and output tasks, additionally to input and output tasks previously used.

Runtime

The two main improvements for the runtime use of models concern the task driven simulation as it mainly requires the use of HAMSTERS:

• We added means to select the HAMSTERS role involved in the simulation.

• An important improvement is about the value selection for task objects: executing an input task may requires to select a particular set of values that may be found within the PetShop data set or that may be provided by the user (for instance feeding in a text box). These values are thus used to control the PetShop execution of a transition.

Architecture of the extended environment

As stated in [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF], the integration of the tools relies on specific API provided by both HAMSTERS and PetShop. In this section we present how the whole tool suite has been improved to handle synergistic execution.

As described in the previous sections, the two main specificities introduced by this new approach are:

• HAMSTERS allows the editing and simulation of several roles described using several task models.

• PetShop allows the editing and execution of several distributed ICO models.

The goal of the tool suite is thus improved in order to allow the specification of a distributed user application and the related user activities. The whole interactive system may be considered as a set of pairs of single users and single user application with communications means supported by both the applications and the users. Making these two parts of a pair correspond requires identifying points of connection for both design time and runtime:

• From each tasks specification we extract the set of interactive tasks and cooperative interactive tasks (for both input and output) representing a set of manipulations that can be performed by the users on the system and outputs from the system to the users.

• From each ICO specification we extract the activation and rendering function that may be seen as the set of inputs and outputs of the system model.

Design time architecture

The principle of editing the correspondences between the models of one pair {role, system} is to put together interactive and cooperative interactive input tasks (from the task models) with system inputs (from the system models) and system outputs (from the system models) with interactive and cooperative interactive output tasks (from the task models). Setting up this correspondence may show inconsistencies between the task and system models such as interactive tasks not supported by the system or rendering information not useful for the task performance. The correspondence editing process is presented on Figure 6 where each tool feeds the correspondence editor with information from the API in order to notify it with modifications are done both in the task model and in the system model.

Correspondence Editor i

Tasks Adapters

HAMSTERS i

Task Model

PetShop -ICO i

System Model API API Correspondence i This process that produces a correspondence is repeated for each pair on the entire system. Each pair is being put into correspondence separately producing a set of independent correspondences. These dependencies totally rely on the connection of task tree leaves (both input and output cooperative tasks). These elementary tasks are performed on the local system (represented by a set of ICO models). The separation of the correspondences relies on the fact that each part of the distributed system is modelled by a set of independent ICOs, connected by communication means (method calls) supported at runtime by the Ivy bus.

As the correspondence editing goal is to put together user activities and interactive features, this correspondence is only possible with the finest grain item of both descriptions.

Runtime architecture

Our framework allows the co-execution of task and system models controlled by both the execution of the system model and the execution of the task model as shown in Figure 7 (where the correspondences are those produced by the process described by Figure 6).

Figure 7 highlights the two ways communication within each pair {task, system} allowed by the services embedded within the two following APIs:

• Between HAMSTERS and the Simulation Controller: On one side HAMSTERS notifies changes in the current scenario to the Simulation. On the other side the Simulation Controller is able to ask to perform the corresponding task (according to the correspondence provided by the Correspondence editor), simulating the user action.

• Between PetShop and the Simulation Controller: on one side the PetShop interpreter notifies the Simulation Controller the evolution of the current execution of the system model (notifications come from both rendering and activation functions). On the other side, the Simulation Controller fires the corresponding activation adapter (according to the correspondence provided by the Correspondence editor) simulating the user action.

Such as in [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF] such architecture allows a two ways simulation controlled by the system execution or controlled by the task simulation. The principle of the simulation is the same as in our previous work:

• When driven by the tasks, building a scenario using HAMSTERS is translated by the Simulation Controller into user actions within PetShop (a sequence of transition firing).

• When driven by the system execution, user actions are directly linked to the corresponding tasks from the task model and the user's action on the user interface of the application change the current state of the task model simulation.

The task driven simulation introduces the data correspondence. This correspondence is built on runtime capabilities of the two tools HAMSTERS and PetShop:

• HAMSTERS provides the description of objects, information and knowledge required and manipulated in order to accomplish tasks.

• PetShop, by describing data structure and data flow of the system, provides the set of data manipulated at any moment by any actions (firing of transitions). It is thus possible for any couple (task, event handler) within the correspondence description to match system data and the required objects for the task performance. An example of such data matching is provided by the case study (see next section). The originality of this work relies on the distribution of the system. The choice made to handle this distribution (as illustrated by Figure 7) is to use the communication means offered by PetShop (thanks to the Ivy software bus). The distribution is thus fully supported by the system side of the specification as it requires concrete data communication that should be out of the scope of task modelling.

HAMSTERS

EXAMPLE FROM A LARGE CASE STUDY

The proposed tool suite has been used to design and develop a prototype of groupware application belonging to the space ground segment category of applications. This study has been led in the context of a Research and Technology project funded by the French Space Government Agency (CNES). MARACCASS stands for Models and Architectures for the Resilience and Adaptability of Collaborative Collision Avoidance System for Spacecraft and aims at studying methods, techniques and tools to design and develop collaborative applications. This project is particularly targeting groupware for the management of collision avoidance between satellites and space objects. In this section, we present illustrative extracts from the case study which are relevant to highlight the key points of the contribution.

Management of collision risks between space objects and satellites

CNES and various other international agencies have to cope with the increasing number of space fragments, which are a threat to on-going satellite missions. Collision avoidance management is a collaborative, cross-team, and international activity. Amongst the national and international organizations, two main types of teams can be distinguished: the space observation teams and the satellite mission teams. The observation teams, thanks to various equipment's and tools are gathering information about space objects and their trajectories (past, present, future). The mission teams focus on one particular space object (usually a satellite) and are monitoring and controlling the space object they are in charge of and its operations. If the observation team detects a collision risk between a satellite and a space object, it contacts and alerts the mission team in charge of the satellite.

Roles and main goals to manage collision risks

In this case study, we take the example of the collaboration between the CNES team in charge of monitoring space objects (called the Orbit Computation Center or OCC) and the SMOS3 satellite mission team. In order to collaboratively manage a collision risk, the teams are assisted with several non-integrated software tools: individual software tools to analyze probability of collision and traditional communication tools (email and telephone) to coordinate and communicate about the risk.

Preliminary work before high-fidelity prototyping phase

The first phase of the project has consisted in analyzing current activity with the production of corresponding task models. Then, we proposed several low-fidelity prototypes for a new groupware application to support collaborative activities of collision risk management. These low-fidelity prototypes take into consideration groupware principles [START_REF] Ellis | Groupware: some issues and experiences[END_REF] but also contributions about design considerations for collaborative visual analytics [START_REF] Heer | Design Considerations for Collaborative Visual Analytics[END_REF]. We then produced task and system models from low-fidelity prototypes that had been validated with operational teams.

In the next paragraphs we present extracts from models and from the high-fidelity groupware prototypes that highlight how the proposed framework has been applied to develop a high-fidelity prototype of the collaborative application for collision risk management. In these extracts, we will focus on the collaborative asynchronous activities related to posting annotations (OCC engineer role) and consulting these annotations (SMOS controller role) in the corresponding remote applications. Figure 8 and Figure 9 presents screenshots of the two remote applications dedicated to collaborative management of collision risks. Figure 8 presents the application dedicated to OCC engineers (with a larger set of functionalities such as deep probabilistic calculus and Conjunction Summary Messages creation and edition). In the presented screenshot, a popup window is opened in order to let the OCC engineer edit an annotation. Figure 9 presents the application dedicated to the mission controllers with a reduced set of functionalities. Its main purpose is to provide situation awareness about the collision risks related to the mission and communication and coordination support. In the presented screenshot, an annotation is displayed (pined to the table) to the attention of the SMOS mission controller. In this section, extracts of the task models illustrate the HAMSTERS extensions and especially how the new cooperative task types have been applied to support the development of the groupware Hi-Fi prototype. Figure 11 presents an extract from the set of activities performed once a collision risk has been detected for the SMOS satellite mission. In particular, it shows the sequence of activities led when the SMOS mission controller was not available for a live communication. The OCC engineer first creates an annotation ("Create annotation" input tasks), then positions the annotation (iterative task "Move annotation") until the position is adequate ("Fix annotation position" input task). The OCC engineer then edits the annotation (input task "Edit annotation"), decides to send the annotation (cognitive decision task "Decide to send annotation") and then send the annotation (cooperative asynchronous task "Send annotation"). The two excerpt of the models presented here describe how the editing of an annotation is performed on the OCC side and how it is sent and acknowledged back on the SMOS side. In both case, a snapshot of the dedicated graphical part is provided. These models behave as follows:

1. When in editing mode (a token is put in place EditedAnnotation at the top of the left part of Figure 13), it is possible to edit the text of the annotation using the edition window (see left part of Figure 13). It results in a state change (by the firing of transition changeText_, changing the marking of place EditedAnnotation with the new text) or it is possible to validate or cancel the editing (where button OK fires the transition validate_ and button CANCEL the transition cancel_).

2. When validated (cancellation producing a return to the initial state) a token is put in place newAnnotation, the created annotation is sent to the peer application (SMOS) by the remote invocation peer.submitAnnotation(…).

3. The communication bus Ivy then sends this method call to the ICO SMOS model (a token is put in the service input port of the corresponding method, the place SIP_SubmitAnnotation on the top of the right part of Figure 13).

4. The firing of the following transition submitAnnotation puts a token in place newAnnotation making the transition ack_ available (which is translated into activating the corresponding menu item within the popup menu show on the right part of Figure 13). • The center part allows the editing and execution control of both the sources and models. The layout of this part is fully reconfigurable as illustrated by the layout difference of the left and right part of the figure.

To illustrate the synergistic exploitation of both the system and task models, we use the models presented in the previous sections, following the same scenario as used for the ICO models presentation (editing of an annotation). As the correspondence editing between system and task models are a simple table editing and was already presented in [START_REF] Barboni | Beyond modeling: an integrated environment supporting coexecution of tasks and systems models[END_REF], we only focus here on the task driven simulation with a special focus on the cooperative activities. Following the eight numbered steps presented on the figure, the behavior of the task driven simulation is the following one:

1. A set of available tasks is provided by the HAMSTERS environment that is selectable within the associated list box.

2. The selected task is connected to a transition by the correspondence editing.

3. As the tasks requires an object (see task Edit Annotation in Figure 11 in Task models section of the case study), a dedicated panel is available (see the left part of Figure 16 for a zoomed snapshot of this part of the tool), providing means to select values built from the data (system side) of the running ICO model, related to the transition connected to the task. It is also possible to manually provide a value using the bottom text field of this panel (see bottom right part of Figure 16).

4. When set, the selected value is sent to the ICO model by sending an event (such as graphical part would have done it).

5. Such as in the step 3 of Figure 13 (the scenario described in the ICO models section), an invocation is performed on the remote application.

6. When a token enters a place within the ICO model, a rendering may occur and this rendering may be related to an output HAMSTERS task, using the output correspondence edition.

7. When an output task is selected, a dedicated panel appears at the bottom of the tool, showing whether a rendering occurs and if it corresponds to an output correspondence (Figure 16 shows a detailed view of this panel). In this panel it is possible to indicate if the rendering was effectively correct and perceive (for log purpose).

8. Finally, such as in step 5 of Figure 13 (the scenario described in the ICO models section), an invocation is performed back on the remote application.

CONCLUSIONS AND FUTURE WORK

This paper has proposed a tool supported approach for bridging the gap between tasks and system views in the design of multi-user interactive systems. To this end we have briefly introduced extensions to the notation called HAMSTERS for the description of multi-users tasks models. These extensions allow the production of very detailed description of collaborative tasks beyond the expressive power of other task notations. This expressive power has allowed us to embed this notation within a synergistic framework where collaborative task models are connected to the interactive parts of a distributed system.

Through the application of the approach on a real life case study (that was carried out over the 3 years lifespan of the project) we have demonstrated the validity of the approach in the context of space critical systems. However, this validation has only demonstrated that the notations are able to describe multi-user activities and interactive systems and that they were able to scale enough to describe a real life application. We have not presented in this paper all the work that has been carried out around the definition of the user interfaces, the interaction techniques and the communication and collaboration functionalities. This work has been performed using a User Centered Design approach based on low-fidelity and high-fidelity prototypes.

The work presented here belongs to a longer term research program targeting at the design of resilient interactive systems using model-based approaches. Future work targets at exploiting this approach, to propose model-based usability evaluation of multi-user interactive systems extending the approach proposed for mono-user ones in [START_REF] Bernhaupt | Model-Based Evaluation: A New Way to Support Usability Evaluation of Multimodal Interactive Applications[END_REF]. We will also build on this model-based work to identify function allocations between operators and interactive systems to design more usable and reliable automation for critical systems.

Figure 1 .

 1 Figure 1. Structure of a HAMSTERS project

Figure 3 .Figure 4 .

 34 Figure 3. Elements of notation related to space-time constraintsCooperative task may be dedicated to one or more of the following type of collaborative activities: production, coordination, communication. It is then possible to associate one or more properties amongst this set. For example, Figure4a) shows that one task is dedicated to coordination whereas Figure4b) shows that the task is dedicated to both coordination and communication.

Figure 6 .

 6 Figure 6. Design time architecture of the tool suite.

Figure 7 .

 7 Figure 7. Runtime architecture of the tool suite

Figure 8 .Figure 9 .

 89 Figure 8. Screenshot of the Hi-Fi prototype for collision risks management dedicated to OCC engineers

Figure 10 .

 10 Figure 10. Extract of the highest level task model for the OCC activities (OCC engineer role) Orbit Computation Center (OCC) engineers

Figure 10 presents

 10 Figure 10 presents an extract from the set of activities that have to be performed by the expert engineer on duty from the Orbit Computation Center to monitor and manage collision risks.

Figure 11 .

 11 Figure 11. Extract of the task model "Handle collision risk between satellite and fragment" for the OCC engineer roleSMOS command and control room controllers and engineersFigure12presents an extract from the set of activities that have to be performed by the SMOS controller when warned by the OCC engineer.

Figure 12 .

 12 Figure 12. Extract of the highest level task model for the SMOS mission activitiesFigure14presents an extract from the set of activities performed once a collision risk has been detected. In particular, this set of activities is cooperative and bound to the above presented set of activities for the OCC engineer role. Once the OCC engineer has sent an annotation, it is displayed in the SMOS remote application (cooperative output task "Display new annotation"). When the SMOS mission controller will be available for consulting the application, s/he detects and acknowledges reception of the annotation (cooperative input asynchronous task "Acknowledge lecture of annotation"). S/he then analyzes the reported risk and may delete the annotation (cooperative input task "Delete annotation").

Figure 13 .

 13 Figure 13. ICO modelling of the two remote applications COO (left part) and SMOS (right part) ICO modelling of the collaborative application to manage collision risks Figure 13 illustrates an excerpt of the connected models of the two remote applications OCC (left part of the figure) and SMOS (right part of the figure). The two excerpt of the models presented here describe how the editing of an annotation is performed on the OCC side and how it is sent and acknowledged back on the SMOS side. In both case, a snapshot of the dedicated graphical part is provided. These models behave as follows:

5 .

 5 Using the menu item ack results in setting a token in place AnnotationToAck which thus allows the firing of transition ackAnnotation. The firing of this transition results in the remote method peer.ackAnnotation(…) invocation (on the bottom of the left part of the figure) and finally makes the transition delete_ fireable (the corresponding menu item becoming enabled).

Figure 14 .Figure 15 ••Figure 15 .

 141515 Figure 14. Extract of the task model "Handle collision risk" for the SMOS mission controller role Distributed co-execution between tasks and applications Figure 15 illustrates two remotes instances of the tool suite presented in this paper, connected using the Ivy communication bus. The left part (resp. the right part) corresponds to the editing of the OCC (resp. SMOS) models. The left-hand part of the figure shows the project structure of the tool suite (i.e. a set of modules of the NetBeans IDE 4 ). This tool may be divided into four parts: • The top part is a set of classical IDE menu bars and tool bars buttons.• The left part provides means to navigate amongst the project files (java sources, ICO, HAMSTERS and correspondence models).• The right part shows properties of the sources or models (bottom part) and tools to modify the currently selected model (on the top part a specific toolbox appears

Figure 16 .

 16 Figure 16. Detailed view on task-system related data.

http://www.eei.cena.fr/products/ivy/documentation/

http://www.irit.fr/recherches/ICS/softwares/hamsters/

http://smsc.cnes.fr/SMOS/index.htm

https://netbeans.org/features/index.html

ACKNOWLEDGMENTS

This work was partly sponsored by CNES R&T MARACCASS. We would like to thank the OCC team and in particular Jean-Claude Agnèse and François Laporte.


Haluk Ozaktas
email: ozaktas@irit.fr

Christine Rochange
email: rochange@irit.fr

Pascal Sainrat
email: sainrat@irit.fr

Minimizing the Cost of Synchronisations in the WCET of Real-Time Parallel Programs

Keywords: Real-time, WCET, parallel programming, lock

Designing time-predictable architectures to support the requirements of hard real-time systems is the goal of several research projects. In this paper we assume that such platforms exist and we focus on the timing analysis of parallel real-time applications. One of the main challenges is to determine how much the delays induced by software constructs such as synchronisations can impact the worst-case execution times (WCETs) of parallel threads. In this paper, we refine state-of-the-art analysis: first, we derive more accurate estimations of stalls at critical sections; second, we introduce new locking primitives that minimise stall times on the worst-case path. Experimental results show noticeable improvements on the WCETs of benchmarks.

INTRODUCTION

In the next years, real-time embedded systems will be built on multicore platforms which provide better energy efficiency than current single-core architectures. But such multicore platforms challenge timing analysis techniques because the sharing of hardware resources among cores generates conflicts that impair the timing predictability [START_REF] Heckmann | The influence of processor architecture on the design and the results of WCET tools[END_REF][START_REF] Rochange | An overview of approaches towards the timing analysability of parallel architecture[END_REF].

This issue is tackled by several research projects, e.g. PREDATOR [START_REF] Cullmann | Predictability considerations in the design of multi-core embedded systems[END_REF], parMERASA [START_REF] Ungerer | parMERASA -Multi-core execution of parallelised hard real-time applications supporting analysability[END_REF] and T-CREST, that aim at designing time-predictable multicore architectures. Promising solutions have already been proposed, e.g. in [START_REF] Paolieri | A hard real-time capable multi-core SMT processor[END_REF][START_REF] Panić | On-chip ring network designs for hard-real time systems[END_REF]. We assume that such time-predictable platforms are available and we look forward to the next step which will be the parallelisation of applications to improve the tasks response time and not only the task throughput. This will be needed to achieve the high performance requirements that are foreseen to get support for better safety, lower emissions and improved comfort for passengers in aircrafts or cars.

Parallel threads experience delays due to the use of synchronisation primitives, which challenges the timing analysis. For example, a thread reaching a barrier might be stalled until other threads reach the same barrier. Similarly, a thread trying to acquire a lock before a critical section might be stalled until concurrent threads get the lock themselves, execute the critical section and then release the lock.

In [START_REF] Ozaktas | Automatic WCET analysis of real-time parallel applications[END_REF], we proposed an approach to determine the WCET of a parallel application in which threads synchronise through the shared memory, using POSIX-like primitives. This approach first computes the worst-case stall times (denoted by W CST ) generated by synchronisations, then integrates them in the global WCET analysis. In Section 2.1, we will review this algorithm to estimate worst-case delays due to inter-thread conflicts. We will then report, in Section 2.2, some experimental results which show that critical sections, already known to limit the average speedup of parallel software, degrade even more noticeably the worst-case performance. This is partly due to considering pessimistic assumptions (maximum contention) in order to obtain safe upper bounds. We will discuss this pessimism in Section 2.3.

Our contribution in this paper is twofold: a) We propose a refined analysis of the impact of stall times at critical sections on the WCET when considering a sequence of critical sections (either distinct critical sections executed in a row, in Section 3.1, or the same section executed in a loop, in Section 3.2). Such sequences are found in various common parallel programming patterns such as dynamic work assignment, producer-consumer scheme or iteration until convergence. Experimental results (Section 3.3) show that sensibly tighter WCET estimates can be achieved. b) We introduce new locking primitives that enforce a constant order on threads crossing repeatedly the same critical section (Section 4.1). They collectively implement our Constant-Order Lock Granting (CO-LoG) policy. Using this policy drastically reduces the impact of synchronisation stalls on the WCET of parallel programs, as shown in Section 4.2.

Related work on static WCET analysis, time-predictable synchronisations and the timing analysis of parallel real-time programs is surveyed in Section 5. We conclude the paper in Section 6.

MOTIVATION

Background

We have proposed an approach to the timing analysis of real-time shared-memory parallel programs in [START_REF] Ozaktas | Automatic WCET analysis of real-time parallel applications[END_REF]. Considering a time-predictable multicore architecture, our solution aimed at estimating the worst-case stall times (WCSTs) of concurrent threads at synchronisation points, i.e. where threads call a barrier_wait() or a mutex_lock() primitive.

As far as critical sections (mutexes) are concerned, this approach is conservative: it assumes that a thread trying to acquire the lock is stalled, in the worst case, by any other thread that also requests the lock at some point in the program. To allow the stall time to be upper bounded, we consider time-predictable mutexes, as proposed in [START_REF] Gerdes | Time analysable synchronisation techniques for parallelised hard real-time applications[END_REF], which guarantee that threads are granted the lock on a first-come first-served basis. With this assumption, the WCST at a critical section is estimated as:

W CST ≤ (T -1) • C
where T is the total number of threads using the lock and C is the worst-case execution time spent in the critical section. If threads do not execute all the same code in the critical section, the longest path is considered.

In other words, the cost of any critical section is multiplied by the number of concurrent threads because a pessimistic situation, with full contention, is assumed. The impact on the WCET of the parallel application can be sensible if either the number of threads is large or the critical section is long or the critical section is executed several times in a loop. This is confirmed by experimental results reported in Section 2.2. In Section 2.3, we explain why this estimation of WCETs is pessimistic and can be refined.

Impact of Critical Sections on Worst-Case Execution Times

Critical sections are known to be a performance bottleneck in parallel programs: since a single thread at a time can execute in a critical section, it may happen that other threads be stalled until the critical section is free. Depending on the respective sizes of parallel parts of code and critical sections, such conflicts and sequentialisation might severely degrade performance. In this section, we report experimental results that show how much the worst-case performance is impacted by stall times at critical sections.

Methodology

All the experimental results reported in this paper have been collected considering the following architectural model and benchmark applications.

Multicore Model.

In order to isolate the effects of synchronisation stall times, we assume a 64-core1 architecture built up on very simple cores. Each core benefits from private 32-KB separate instruction and data caches, and executes any instruction that hits in the cache in a single cycle. The latency to the main memory is 649 cycles, which includes the impact of maximum possible contention among cores, assuming a timepredictable interconnection network and memory system, such as the one proposed in [START_REF] Panić | On-chip ring network designs for hard-real time systems[END_REF].

Hardware-based data coherency management is challenging for timing analysis because its behaviour is strongly related to the actual interleaving of accesses to shared data by the different threads. Some solutions towards time-predictable data-coherent caches have been proposed, e.g. the ODC 2 cache in [START_REF] Pyka | Performance evaluation of the time analysable on-demand coherent cache[END_REF], but they introduce extra memory accesses that impact the WCET. To focus on synchronisation costs, we assume that shared data are not cached and reside in the main memory only.

Benchmark Programs. We consider three parallel applications. Each of them is composed of a main thread that creates child threads. All threads (including the main one) execute the same computation code. Critical sections are implemented using timepredictable lock primitives, e.g. ticket locks, that guarantee that threads are served in a first-come first-served basis. This way, a thread competing with T -1 other threads cannot be stalled more than once by each other thread when it requests access to a critical section.

jacobi (see Figure 1) solves a system of linear equations using the iterative Jacobi method on a 2D matrix. Each thread computes part of the points, independently of the other threads (as in the so-called embarrassingly parallel computation model). The process is repeated until convergence is reached, i.e. until the average variation of results from one iteration to the other one is lower than a specified threshold. Each thread computes its local variation (line 9 ) then adds it to the global variation in a critical section (line 12 ). A synchronisation barrier is used to ensure that threads do not start their computation before the global variation is initialised (line 5 ) and do no check the convergence condition before the global variation has been computed (line 14 ). The last barrier in the loop (line 18 ) ensures that decision on convergence is made before global variation is reset to zero. Since the implementation of the barrier_wait primitive includes a critical section, the synchronisation pattern of this application repeats the sequence shown in Figure 2: between two progress synchronisations, threads compete for two critical sections in a row. spinlock unlock(mutex→guard) 27: end function Figure 13: New mutex primitives implementing the CO-LoG policy threads is fixed). In mutex_get_in, a thread first gets a ticket (line 3 ), i.e. a unique integer which is then used to index the arrays. Then the thread is appended to the list (lines 4-7 ). Note that these operations must be performed within a critical section, protected by a spin lock. Naturally, the stall time at this critical section must be accounted for when estimating WCETs but (a) its value is small because the critical section is very short, and (b) the function will generally not be invoked in a loop. To get the lock, a thread executes the mutex_lock routine and waits until its ticket is selected (line 19 ). Once it terminates the execution of a critical section, it invokes mutex_unlock that grants the lock to the thread holding the next ticket in the list (line 25 ). Again, this is protected by a spin lock that must be taken into account when computing WCETs. In mutex_get_out, the ticket of the thread is removed from the list. This way, the thread will not be indefinitely waited for by other threads trying to get the lock. Figure 15 provides an example of how the new primitives can be used in an application code. Note that it is absolutely needed that the thread call mutex_get_out when it exits the loop, otherwise there would be a risk of deadlock.

The CO-LoG policy, which ensures the lock is granted always in the same order, guarantees a synchronized progress of threads in loop iterations. It makes it impossible for thread thx to execute iteration i + 2 while thread th0 is still in iteration i. This removes the cause of possible stalls described in Section 3.2 for E ≥ (T -1)•C and illustrated in Figure 8 between th1 and th0. As a result, using CO-LoG policy, a thread taking the maximum possible time to execute the computation part is only stalled in the first iteration

STW C = (T -1) • C (7)
On the other hand, if E < (T -1) • C, the longest thread is stalled for (T -1) • C -E at each iteration, except for the first one, because the lock is still being held by other threads. By considering maximum contention for the fist iteration, the maximum stall time can be formulated by:

STW C = (T -1) • C + (N -1) • ((T -1) • C -E) (8)

Experimental Results

Results for dta.

As previously said, (T -1) • C < E for dta. Then, when using the CO-LoG primitives, the longest thread only waits in the first iteration of the loop. This yields to a total stall time that is about 0.003% of the stall time found for the pessimistic analysis for 2 threads, and 0.1% for 64 threads.

In other words, the synchronisation is almost for free. Figure 16 plots the speedups obtained with CO-LoG and with the pessimistic analysis respectively. The speedup improvement achieved by CO-LoG is 10.5% for 8 threads and 94.6% for 64 threads. Unsurprisingly, this is significantly more than the increases obtained by the improved analysis since the stall times are much more drastically reduced by the CO-LoG policy. It should also be noted that even though only 9.52% of the total WCET is spent on waiting at critical sections for 8 threads (cf. Table 2), the CO-LoG policy still yields to a significant increase of the speedup.

Results for hist.

In Section 3.3, we stated that (T -1) • C < E when T ≤ 16 for hist. In that case, and when using CO-LoG, the longest thread only waits at the critical section in the first iteration example.

CONCLUSION

To reach their required level of performance, future realtime systems will be implemented on multicore architecture and their software will have to be parallelised. Even on a time-predictable multicore, parallel threads are submitted to delays due to synchronisation operations. These delays must be accounted for when computing the WCET of a parallel critical application. In a recent paper [START_REF] Ozaktas | Automatic WCET analysis of real-time parallel applications[END_REF], we proposed a solution to compute safe upper bounds on these delays. In this paper, we introduce two solutions that contribute to achieving tighter analysis of synchronisation-related delays: (a) a refined analysis of the stall times in sequences of critical sections (either different critical sections executed in a row or a single critical section embedded in a loop); and (b) a new strategy for lock granting, named CO-LoG, that is implemented in a set of primitives and helps to reduce drastically estimated stall times. Experimental results show noticeable decreases of estimated stall times and improvements on WCET estimates.

Figure 15 :

 15 Figure 15: Usage of new mutex primitives

In practise, so many cores in a shared-memory architecture may raise side issues which are out of the scope of this paper.

Acknowledgments

The research leading to these results has received funding from the European Union Seventh Framework Programme under grant agreement no. 287519 (parMERASA).