Martino Trassinelli
email: martino.trassinelli@insp.jussieu.fr

V E Gafton

Victor H Etgens

S Hidki

Emmanuelle Lacaze

Emily Lamour

X Luo

Massimiliano Marangolo

M Eddrief

J Mérot

C Prigent

R Reuschl

J.-P Rozet

S Steydli

D Vernhet

Magnetic properties

Keywords: Ion irradiation effect, Magnetic thin films, MnAs

come

Introduction

Thin films of ferromagnetic transition metals have been extensively studied in the last decades for their important applications. Many investigations on the modification of their magnetic properties have been performed using different techniques. In particular, ion bombardment demonstrated to be an efficient tool for this task [START_REF] Chappert | Planar patterned magnetic media obtained by ion irradiation[END_REF]. So far, experiments were performed on transition ferromagnetic metals and on some of their corresponding alloys. They demonstrated that ion bombardment does not affect the chemical composition of the films, but changes significantly structure and magnetic properties.

These modifications are related to local changes of the film structure during the irradiation and to the implantation of ions. More precisely, dependencies on the ion specie, its penetration depth and irradiation dose, giving rises to changes on the coercivity, saturation magnetization and crystal lattice, have been observed [START_REF] Kaminsky | Patterning ferromagnetism in Ni 80 Fe 20 films via Ga + ion irradiation[END_REF][START_REF] Zhang | Xenon-ion-induced phase transition in thin Co films[END_REF][START_REF] Zhang | Magnetic texturing of xenon-ion irradiated nickel films[END_REF][START_REF] Müller | Ion-beam induced changes in magnetic and microstructural properties of thin iron films[END_REF][START_REF] Fassbender | Structural and magnetic modifications of Cr-implanted Permalloy[END_REF][START_REF] Cook | Focused ion beam patterned Fe thin films: A study by selective area Stokes polarimetry and soft x-ray microscopy[END_REF].

In the this work, we present recent studies on more peculiar magnetic material, namely the manganese arsenide, submitted to ion bombardment.

MnAs is a metallic compound that is ferromagnetic below T C = 313 K where the first-order phase transition from hexagonal (α phase) to orthorhombic (β phase, MnP type) is accompanied by a ferromagnetic-paramagnetic transition. The possibility of epitaxial growth of MnAs thin films on standard semiconductors such as GaAs has renewed interest for spintronic research [START_REF] Däweritz | Interplay of stress and magnetic properties in epitaxial MnAs films[END_REF]. The epitaxial strain disturbs the phase transition that leads to the αβ phase coexistence over a large range of temperatures (10-45 • C [START_REF] Kaganer | Strain-mediated phase coexistence in MnAs heteroepitaxial films on GaAs: An x-ray diffraction study[END_REF]). In this range, an alternating structure of ridges (α phase) and grooves (β phase) organized in stripe-shaped domains is created to minimize the elastic energy due to the epitaxy.

Very recently, our group has started to study the change of these peculiar characteristics induced by the implantation of Ne 9+ highly charged ions in the MnAs epilayer. Such changes may open new perspectives in the attractive possibility to maintain ferromagnetism in MnAs to higher temperature than the bulk T C . A better knowledge of these damages will also provide important information about the robustness of this material in hostile radiation environment.

Production of the samples, irradiation and characterization have been entirely performed at the NanoScience Institute of Paris (INSP) where a molecular beam epitaxy (MBE) system and an ion source equipped with a dedicated beam line (SIMPA, French acronym for highly charged ion source of PAris) are available. After the irradiation, the sample is characterized by several techniques: MOKE for magneto-optical Kerr effect, XRD for X-ray diffractometer and MFM for magnetic force microscope. In this paper, we detail the production of MnAs/GaAs films and the set-up for ion irradiation.

First results and discussions of the bombarded films are presented.

Experimental details

MnAs film production

MnAs epilayers are grown by MBE on GaAs(001) substrate. The MnAs growth is performed at 240 • C on a prepared GaAs substrate under As-rich conditions. A growth rate of about 100nm/h leads to a finally thickness of 150 nm. The deposed MnAs is oriented with the αMnAs [0001] and βMnAs

[001] axis parallel to GaAs [ 110]. At the end of the growing processes the samples are capped in situ with an amorphous As layer in order to prevent the MnAs oxidation. More details on the growing process can be found in [START_REF] Breitwieser | Phase transition and surface morphology of MnAs/GaAs(001) studied with in situ variable-temperature scanning tunneling microscopy[END_REF].

Samples of same MnAs/GaAs growth with a surface of 4 × 5 mm 2 are obtained from the original wafer. Once placed on a Omicron sample holder, the films are moved toward the SIMPA facility in atmosphere pressure.

Ion irradiation

The ion irradiation are performed at the SIMPA facility that include an electron-cyclotron resonance ion source coupled to a dedicated beam line.

The ion source can produce intense beams of highly charged ions such as Ne 9+ , Ar 16+ , Xe 26+ . . . After the extraction, the ion beam is selected in charge and mass by a auto-focusing magnetic dipole. With a series of magnetic and electric lenses, the ion beam is transported to the collision chamber where the different samples are placed. In our particular case, we use a beam Ne 9+ with a kinetic energy of the ions of 90 keV (4.5 keV/u) and a maximum intensity of 1 eµA in the chamber. More details of the SIMPA installation can be found in ref. [START_REF] Gumberidze | Electronic temperatures, densities, and plasma 14 x-ray emission of a 14.5 GHz electron-cyclotron resonance ion source[END_REF].

The samples are introduced in the collision chamber via an interlock equipped with a radiative oven (see figure 1). In the interlock, once a pressure of few 10 -8 mbar is reached, each sample is slowly warmed up to 270 • C and kept to this temperature for several hours in order to remove the As cap. Once cooled back to room temperature, the sample is transferred to the sample-manipulator located at the center of the collision chamber. Typical pressure of the chamber is 5 × 10 -9 mbar. The manipulator allows for xyz translation and a rotation long the axis perpendicular to the ion beam to Under these experimental condition, we determine from SRIM (version 2008.04 [START_REF] Ziegler | Stopping and Range of Ions in Matter[END_REF]) that the ion implanted distribution covers the full MnAs film thickness enhancing hence the dose effect [START_REF] Zhang | Magnetic texturing of xenon-ion irradiated nickel films[END_REF]. The simulations in figure 3 show that only a very small fraction of ions is deposited in the GaAs substrate excluding the possibility of MnAs-GaAs beam mixing.

Different ion beam bombardment durations, from 5 to several thousands of seconds, corresponding to doses between 1.6×10 12 and 1.6×10 15 ions/cm 2 , are applied on different samples coming from the same growth. Due to the difficulty to have a well defined beam shape on the sample, the dose is estimated with a poor accuracy evaluated to about 50%.

Analysis of the irradiated samples and discussions

After the irradiation, the samples are removed from the interaction chamber to be analyzed. Preliminary studies with MOKE techniques that measure the macroscopic magnetic response at the surface. This first results indicate that already with 1.6 × 10 12 ions/cm 2 no ferromagnetic behavior is observed.

More systematic analysis are performed using XRD and MFM methods and they are presented in the following paragraphs.

XRD measurements

The acquisition of XRD data is performed using a PANalytical XPertPRO MRD diffractometer with a copper anode, generating CuKα The thickness of the samples is found to remain constant whatever the ion dose (within the range used here) with a value around 150 nm demonstrating that sputtering effects are marginal. In opposite, the Bragg reflection spectra exhibits significant modifications as a function of the received dose, as seen in figure 4. For the non irradiated sample, the αMnAs( 3300) and βMnAs(060) reflection peaks are clearly identified (the β peaks are much less intense at 20 • C). The double peak structure is due to the CuKα 1,2 doublet used in the present spectrometer. For low doses, the βMnAs(060) peak is still visible but seems to disappears for doses > 5 × 10 12 ions/cm 2 . For doses around 2 × 10 12 ions/cm 2 , the α and β peaks are strongly distorted ending to a unique doublet at higher doses (≥ 1.5 × 10 14 ions/cm 2 ). This Bragg reflection could correspond to a new phase of MnAs with Ne implantation or to a modification of the α or β phases in analogy of the measurement on Co films bombarded with Xe ions reported in [START_REF] Zhang | Xenon-ion-induced phase transition in thin Co films[END_REF]. In this previous work, local warming during the ion impact induces a phase transition between the hexagonal close packing (hcp) phase, stable in bulk Co below 425 • C, and the face-centered cubic (fcc) phase, stable at higher temperature. An analog phe- nomenon could appear in our case between the two MnAs phases. To probe this aspect, additional measurements on magnetic properties are required to detect the presence or not of the ferromagnetic αMnAs phase. As mentioned before, MOKE measurements suggest that MnAs after Ne bombardment has no macroscopic magnetic properties. For a closer investigation on the lo- cal magnetic properties on the surface, we used an MFM. The results are presented in the following section.

MFM measurements

The magnetic images of the sample surface are taken with a VEECO dimension 3100 MFM equipped with a magnetic tip coated with Co/Cr (model MESP) and working at a temperature around 20 • C. Before each scan, the samples are magnetized long the surface in parallel to the easy axis of the MnAs [ 1100].

MFM images of the decapped samples before irradiation show (see figure 5 left as an example) the well defined and characteristic stripes of MnAs on GaAs due to the succession of αMnAs and βMnAs regions. We observed that, after irradiation, the shape of the stripes is more and more distorted and at 1.5 × 10 13 ions/cm 2 the stripes are completely vanished. Instead, chaotic pattern with elongated regions parallels to the original stripes (parallel to GaAs[ 110]) appears, as it can be observed in figure 5 (right). At higher irradiation doses, the phase contrast continues to decreases toward an almost complete disappearance.

Discussions

Due to the presence of the phase contrast of the MFM images, we can deduce that a local magnetic response is still present at relative at irradiation doses ≤ 3.2 × 10 13 ions/cm 2 but in a meantime, the α and β phases are not anymore distinguishable. In contrast, MOKE data, sensitive to the macroscopic magnetic response of the surface, show that no signal of ferromagnetic behavior is detected with samples irradiated with a dose equal or lower than 1.2 × 10 12 ions/cm 2 . This could indicate of a freezing of the magnetic domain alignment on the surface, even when an external field is applied (as with MOKE). Considering also the XRD data, we can emphasize that these new properties could be intrinsically connected to the presence of a new phase. To confirm or disprove this assertion, more investigation will be performed in the future.

Conclusions

First investigation on the effect of Ne 9+ highly charged ion bombardment on MnAs/GaAs thin film is presented. The structural and magnetic properties of the MnAs film before and after irradiation are investigated using different techniques, namely, X-ray diffraction, magneto-optic Kerr effect and magnetic force microscope. Preliminary results indicated that ferromagnetic properties of irradiated samples are visible locally using MFM but strongly distorted when compared to non irradiated samples. XRD measurements indicate that this behavior could be linked on a presence of a strongly modified α phase of MnAs or even a new phase. More studies are in any case required.

Figure 1 :

 1 Figure 1: Scheme of the collision chamber. The interlock and the different diagnostic tools are shown. In the inset, a picture of the sample manipulator, thermally regulated, is presented.

Figure 2 :

 2 Figure 2: Left: image of the sample, illuminated by external light on a Omicron sample holder mounted on the manipulator in the center of the collision chamber. Right: the same sample under ion bombardment. The shape and position of the beam hitting the sample is well visible.

Figure 3 :

 3 Figure 3: SRIM predictions [12] on the ion penetration and collision events with the present experimental conditions: Ne 9+ at 90 keV on MnAs/GaAs (150 nm) with an incidence angle of 60 • . Left: distribution of the ion penetration. Right: distribution of atom displacement in the sample. As we can observe, only a very small fraction of ions is deposited in the GaAs substrate.

1 , 2

 12 radiation and operating at 40 kV and 30 mA. The diffractometer is equipped with 4 circular cradles to move the sample with respect different angles for positioning and scanning. XRD patterns are recorded in the 2θ range 20 -100 • , with a step of 0.05 • , and a 17 s time per step. With XRD measurements at grazing incidence angle, the thickness of the sample is determined before and after irradiation. All measurements are obtained at a temperature of 20 ± 1 • C, where α and β phases are normally present in non irradiated MnAs/GaAs films. Data from irradiated films are compared with a reference decapped MnAs/GaAs sample issued from the same growth.

9 91Figure 4 :

 94 Figure 4: XRD Bragg peaks of αMnAs( 3300) and βMnAs(060) plans as a function of the received doses (in ions per cm 2 ).

Figure 5 :

 5 Figure 5: MFM images of 150 nm MnAs on GaAs before (left) and after (right) ion bombardment with a dose of about 1.5 × 10 13 ions/cm 2 . The orientation axis of the GaAs substrates are indicated on each image.

Acknowledgments

The authors would like to thank Mariana Barturen for her help on the MOKE measurements. This experiment has been partially supported by a grant from 'Agence Nationale pour la Recherche (ANR)' number ANR-06-


Challenge ROADEF-EURO 2012 : Machine Reassignment Équipe J19

Michaël Gabay * , Sofia Zaourar †

juin 2012

Nous présentons ici les méthodes que nous avons implémentées pour proposer des solutions au problème du challenge ROADEF-EURO 2012 : la réaffectation de processus sur des machines. Pour les qualifications, nous avions exploré de nombreuses pistes pour résoudre ce problème. Pour la phase finale, nous avons exploré d'autres piste mais les instances étant significativement plus grandes, nous avons finalement mis l'accent sur la recherche locale. Nous présentons ici les approches implémentées dans la seconde phase.

Mots clés Recherche locale, Méta-heuristiques, Machine reassignment, challenge ROADEF-EURO

Le problème

Le problème est le suivant : étant donné un ensemble de machines, hébergeant chacune différents processus, on cherche à réaffecter les processus pour minimiser le coût. Les processus sont regroupés en services et les machines sont regroupées par emplacements (locations) et voisinages. Afin d'être exécuté, chaque processus à besoin d'une certaine quantité de ressources.

Les contraintes sont les suivantes :

1. Chaque machine dispose d'une capacité maximale pour chaque ressource (capacity constraints) et pour certaines ressources, lorsqu'un processus est déplacé, l'espace n'est pas immédiatement libéré sur la machine initiale (transient usage constraints).

2. Deux processus d'un même service ne peuvent pas être hébergés sur une même machine (conflict constraints)

3. Chaque service doit être réparti sur un nombre minimum d'emplacements (spread constraints).

4. Certains service sont dépendants entre eux. C'est à dire que si le service s 1 dépend du service s 2 , chacun des processus de s 1 doit avoir dans le voisinage de sa machine, une machine hébergeant un processus de s 2 .

À nos yeux, les contraintes de dépendance 4 sont les plus difficiles pour ce problème. Celles-ci lient a priori toutes les affectations et empêchent les traitement séquentiels ou la décomposition directe du problème. Nous avons identifié deux approches permettant de s'affranchir de ces contraintes de dépendances. La première approche est d'optimiser l'affectation des processus en se restreignant au voisinage de leurs machines initiales (ou plus généralement d'une solution réalisable). On peut alors utiliser des méthodes à base de programmation linéaire en nombres entiers (PLNE). La seconde technique est d'optimiser au niveau des processus en appliquant des mouvements locaux de type déplacement ou échange. Il devient alors facile de vérifier les contraintes de dépendance. Nous avons testé ces deux approches, la première en décomposant le problème selon les voisinages puis en résolvant un PLNE sur chacun ; la seconde en appliquant une recherche locale [START_REF] Aarts | Local search in combinatorial optimization[END_REF] guidée.

Le problème du challenge est un problème d'optimisation ; divers coûts rentrent donc également en jeu. Ces coûts sont de trois types différents :

1. Des coûts de charge des machines : chaque machine a un seuil (safety capacity) pour chaque ressource. Au-dessus de ce seuil, la charge supplémentaire a un coût. 2. Des coûts d'équilibrage des ressources : pour certains couples de ressources, trop consommer d'une seule des deux est coûteux. Ce coût permet d'équilibrer la charge des machines pour les ressources concernées. 3. Des coûts liés au déplacement des processus. Les coûts de déplacement des processus peuvent être facilement pris en compte lors d'un mouvement. Ceux d'équilibrage en revanche sont plus complexes : afin de pouvoir les optimiser, il faut pouvoir considérer le problème à une échelle globale (des groupes de machines et processus). Seule la configuration finale compte, les mouvements intermédiaires n'ont pas vraiment de sens pour ces coûts. Les coûts de charge sont plus facilement maîtrisables localement : un mouvement impacte directement ceux-ci. Enfin, sur les instances fournies, nous avons pu observer que l'essentiel du coût était dû au coût de charge et d'équilibre entre ressources. D'où, le coût de charge étant plus facilement maîtrisable, nous utilisons une stratégie particulière pour tenter de le réduire.

Pour chaque instance du problème, une solution initiale était fournie. Pour les heuristiques, il peut être intéressant d'avoir plusieurs points de départ, nous avons donc également implémenté une méthode permettant d'obtenir d'autres solutions initiales. Cette méthode modélise le problème comme un problème de vector bin-packing multidimensionnel et est détaillée en section 1.

D'autres solutions initiales

Si l'on cherche des solutions réalisables pour les contraintes de capacité (y compris les transientes) seulement, le problème "ressemble" à un problème de Vector Bin Packing (VBP). Dans le VBP, on se donne n objets dont les tailles sont des vecteurs de d dimensions o 1 , . . . , o n et un nombre infini de boîtes de même taille fixée b (vecteur de dimension d). Le but est de placer tous les objets dans un nombre minimal de boîtes, de façon à ce que la somme des tailles des objets affectés à une boîte ne dépasse pas la taille de la boîte (i.e. pour chaque boîte et pour chaque dimension j, o i dans la boîte o j i ≤ b j ). Le problème de VBP est NP-complet, même en dimension d = 1. Les heuristiques qui existent dans la littératures pour d ≥ 1 sont inspirées de celles de la dimension 1. Ce sont des heuristiques gloutonnes. Nous avons appliqué l'heuristique de Bin-Centering [START_REF] Panigrahy | Heuristics for vecor bin packing[END_REF]. Pour cela, on définit une fonction de poids (ou volume) qui associe à chaque objet o i un entier (ou réel) v i . Plusieurs choix sont possibles pour définir le volume d'un objet ; on détaille le notre plus bas. Ensuite, pour chaque machine, on parcours la liste des objets pas encore placés dans l'ordre décroissant de leur volume et on place les processus qui "rentrent". Lorsque plus aucun objet ne rentre dans la boîte, on la "ferme" et on passe à la suivante, etc. Dans notre cas, les boîtes sont la machines, les objets sont les processus, et les dimensions sont les ressources. Les principales différences par rapport au problème de VBP sont que d'une part, on dispose d'un nombre fini de machines et d'autre part les machines ont des capacités différentes. Nous avons définis les volumes suivants, pour toutes machine m, et tout processus p :

v(m) = r∈R C(m, r) C(r) , v(p) = r∈R R(p, r) R(r) , (1)
où C(r) (resp.R(r)) désigne la capacité totale des machines (resp. le besoin total des processus) en la ressource r.

Par ailleurs, vu la forme du coût de charge, l'idéal est de remplir les machines au maximum sans dépasser la safety capacity. Cela nous a donné l'idée d'une autre heuristique, qu'on appelle Bin Balancing où l'on cherche à équilibrer la charge des différentes machines plutôt que d'utiliser le moins de machines possibles. Concrètement, on trie les machines dans l'ordre croissant des volumes, les processus dans l'ordre décroissant. On affecte le premier processus p 1 à la première machine possible m i . Pour le processus suivant, on commence par tester les machines à partir de m i+1 , de manière circulaire.

La contrainte de conflits est gérée simplement : un processus n'est affecté à une machine que si son service n'est pas déjà présent. Pour la contrainte de dépendance, on se restreint à affecter les processus dans le voisinage de leur machine initiale. En plus de satisfaire automatiquement les contraintes de dépendances, cette restriction nous permet de décomposer le problème en problèmes plus petits (un problème par voisinage) et indépendants si on néglige les contrainte de répartition (spread constraints, 3) Avec ces heuristiques, nous avons obtenu des solutions réalisables (sans prendre en compte les contraintes de répartition) pour 6 des 10 instances B, en quelques secondes. Ensuite, la réparation des contraintes de répartition risquait de prendre beaucoup de temps et il n'était pas garantie qu'on réussisse à les satisfaire. Comme la contrainte principale pour cette heuristique qui ne cherche qu'une solution réalisable était la rapidité, nous avons dû l'abandonner, à cause du coût des réparations.

Décomposition par voisinage et PLNE

Comme expliqué en introduction, lorsqu'on fixe un voisinage et qu'on s'intéresse aux machines et processus de celui-ci dans la solution initiale, toute affectation vérifie les contraintes de dépendances. Nous avons donc décomposé le problème selon les voisinages, puis, pour chacun d'eux, considéré des sous-ensembles de machines (le temps de résolution peut facilement exploser sinon) sur lesquels nous trouvons une affectation optimale des processus. Ces problèmes sont résolus en utilisant CLP (solver pour la programmation linéaire) et CBC (branch and cut), qui font partie du projet open-source COIN-OR 1 .

Sur les plus grosses instances, il est toutefois difficile de résoudre ces problèmes à l'optimal. Nous avions donc essayé dans un premier temps de réduire le nombre de machines considérées mais les résultats n'étaient alors pas à la hauteur de la recherche locale. Puis dans un second temps, d'arrêter le branch and cut après un nombre fini de noeuds mais il était alors fréquent de ne pas obtenir de solutions réalisables. L'ajout d'heuristiques telles que le feasibility pump [START_REF] Fischetti | The feasibility pump[END_REF] permet parfois d'obtenir des solutions réalisables mais rarement autres que la solution initiale.

L'approche par décomposition et PLNE n'a finalement pas porté ses fruits mais plus d'effort sur l'ajout de coupes et le paramétrage du solver aurait probablement pu permettre d'améliorer sensiblement ces résultats.

Recherche locale

Nous disposons de deux types de mouvements : le déplacement (un processus est déplacé sur une autre machine) et l'échange (deux processus sont réassignés, l'un à la machine de l'autre). Nous imposons que ces déplacements ne soient réalisés que lorsque la nouvelle solution est réalisable et de coût inférieur à la précédente. Afin que l'algorithme soit performant, nous calculons seulement les variations du coût d'une solution à l'autre. De plus, pour déterminer si la solution voisine est réalisable, nous exploitons les invariants du mouvement. On navigue ainsi d'une solution réalisable à une autre, pouvant à tout moment interrompre le programme pour récupérer la meilleure.

Lors des qualifications, nous avions utilisé ces mouvements dans le cadre d'une recherche locale de type GRASP [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF]. On faisait alors de très nombreux départs depuis la solution initiale que nous optimisions jusqu'à arriver à un puit pour l'un ou l'autre de nos mouvements avant de recommencer. Les mouvements étaient choisis aléatoirement afin d'effectuer le plus de départs possibles et de varier les solutions obtenues.

Toutefois, cette approche n'était plus la meilleure pour les nouvelles instances. En effet, leurs tailles sont telles que nous ne pouvons effectuer que peu de recherches complètes. Il est donc essentiel de guider la recherche afin que celle-ci nous permette d'obtenir les meilleurs résultats possibles en un seul départ. Comme expliqué en introduction, le coût le plus durablement optimisable pour la recherche locale est le coût de charge. Nous pouvons donc guider la recherche selon ce critère afin de le réduire en priorité.

Dans un premier temps, on trie les machines par ordre décroissants des valeurs de leurs coûts de charge signés (négatif si le seuil de charge n'est pas atteint). Puis à chaque itération, on essaye de déplacer un des processus des machines dont le coût de charge est élevé vers des machines dont le coût est négatif (ou au moins plus petit). Afin de ne pas trop augmenter les autres coûts, on impose tout de même qu'un mouvement ne soit effectué que s'il fait diminuer le coût total de la solution. Cette première étape permet de réduire significativement les coûts en moins de 30s. Cependant, comme on empêche les déplacements d'une machine de moindre coût vers une machine de coût plus élevé, la solution est encore optimisable par déplacements et échanges aléatoires. Ce que l'on effectue dans le second temps.

http ://www.coin-or.org/

Le programmeLe programme final est open source et n'utilise que des composants open-source. Il sera prochainement publié, probablement sur GitHub 2 . Les bibliothèques utilisées pour le rendu final sont Boost 3 et la STL. Le programme rendu n'utilise que des mouvements de recherche locale bien que les autres mouvements soient implémentés et fonctionnels.Le programme fourni répond aux spécifications requises. Il peut être compilé sous linux à l'aide de la commande make et l'exécutable se trouve dans le répertoire bin.

PerspectivesLes heuristiques implémentées sont sous-optimales mais présentent l'avantage de passer à l'échelle. Nous avions beaucoup d'espoir pour la décomposition en sous-problème et l'utilisation de la PLNE. Notre approche pourrait être améliorée par l'ajout de coupes au solver et un affinage des paramètres en fonction de la taille de l'instance considérée. La programmation par contrainte pourrait peut être également remplacer avantageusement la PLNE et permettre d'obtenir plus facilement des solutions réalisables sur les instances des sous problèmes.On pourrait également implémenter d'autres mouvements pour la recherche locale ou permettre de dégrader la solution lorsqu'on est proche d'être bloqués.

https ://github.com/

http ://www.boost.org/


Sidharta Andalam

Partha S Roop
email: p.roop@aucklanduni.ac.nz

Alain Girault
email: alain.girault@inria.fr

Deterministic, predictable and light-weight multithreading using PRET-C

We present a new language called Precision Timed C, for predictable and lightweight multithreading in C. PRET-C supports synchronous concurrency, preemption, and a high-level construct for logical time. In contrast to existing synchronous languages, PRET-C offers C-based shared memory communications between concurrent threads, which is guaranteed to be thread safe via the proposed semantics. Mapping of logical time to physical time is achieved by a Worst Case Reaction Time (WCRT) analyser. To improve throughput while maintaining predictability, a hardware accelerator specifically designed for PRET-C is added to a soft-core processor. We then demonstrate through extensive benchmarking that the proposed approach not only achieves complete predictable execution, but also improves overall throughput when compared to the software execution of PRET-C. The PRET-C software approach is also significantly more efficient in comparison to two other light-weight concurrent C variants called SC and Protothreads, as well as the well-known synchronous language Esterel.

I. Introduction

Embedded applications are reactive and concurrent, and also have strict timing requirements. The conventional approach to the design of such systems has been the use of a realtime operating system (RTOS) that executes on a speculative processor to manage both the concurrency and timing needs of the application. The problem of concurrency managed through operating system threads has been highlighted by Lee [START_REF] Lee | The problem with threads[END_REF]: "They discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism". Understandability is lost since the programmer is burdened with ensuring correctness through complex synchronisation mechanisms provided by the RTOS. Predictability is sacrificed since concurrency is emulated through RTOS scheduling that is inherently non deterministic. More importantly, as these threads are "heavy-weight", there is a significant performance penalty to be paid. This is because each thread has to maintain complete context such as the process control block.

A move away from this direction is the concept of light weight multithreading in C-a language of choice for embedded systems. Two prominent examples in this category are the recent SC [START_REF] Hanxleden | SyncCharts in C -A Proposal for Light-Weight Deterministic Concurrency[END_REF] proposal and an earlier C-library called Protothreads [START_REF] Dunkels | Protothreads: Simplifying event-driven programming of memory-constrained embedded systems[END_REF]. SC is designed mainly for encoding Sync-Charts [START_REF] André | Semantics of SyncCharts[END_REF] in C directly. This is achieved by having a single tick function that manages the state transition between threads using computed goto statements. The main focus of SC has been to achieve reduced code size in comparison to Esterel [START_REF] Berry | The Esterel synchronous programming language: design, semantics and implementation[END_REF] based implementations of SyncCharts. Protothreads [START_REF] Dunkels | Protothreads: Simplifying event-driven programming of memory-constrained embedded systems[END_REF] is a light-weight C library for the programming of concurrent statemachines. The main objective is to produce minimal memory foot-print for embedded applications. Both languages rely on C macros to generate C code. Similar to PRET-C, there are a few synchronous extensions to C [START_REF] Boussinot | Reactive C: An extension of C to program reactive systems[END_REF], [START_REF] Lavagno | ECL: A specification environment for system-level design[END_REF]. ReactiveC [START_REF] Boussinot | Reactive C: An extension of C to program reactive systems[END_REF] is the closest to PRET-C. However, none of these languages are designed for predictable execution and thread-safe shared memory communication, unlike PRET-C.

Our contributions are the following: (1) We present a new light-weight, concurrent language called PRET-C, for the predictable programming of PRET architectures. PRET-C offers a very simple mechanism for achieving thread-safe shared memory communication between light-weight C-threads through its synchronus semantics, not available in earlier light-weight threading libraries for C. [START_REF] Andalam | PRET-C: A new language for programming precision timed architectures[END_REF] We offer a hardware accelerator, called ARPRET, for PRET-C execution over soft-core processors, so that predictable execution can be achieved without sacrificing throughput. (3) We demonstrate, through extensive benchmarking, that ARPRET excels in comparison to the pure software implementation of PRET-C. Software implementation of PRET-C significantly outperforms SC, Protothreads, and Esterel [START_REF] Berry | The Esterel synchronous programming language: design, semantics and implementation[END_REF] in the average and worst case execution time, while generating consistently more compact code.

The organisation of this paper is as follows. In Section II, we present the PRET-C language through a producer-consumer example along with its semantics and the intermediate format.

In Section III we present the ARPRET architecture and how PRET-C programs are executed. The experimental results are presented in Section IV, and our conclusions are presented in Section V.

II. PRET-C overview

PRET-C extends C using the five constructs shown in Table I. In order to guarantee a predictable execution, we impose some restrictions to C, such as the lack of dynamic memory allocation and recursion. Also, all loops must have at least one EOT. Our five C extensions are implemented as C-macros, all contained in a header file, named pretc.h .

A PRET-C program runs periodically in a sequence of ticks triggered by an external clock. The inputs coming from the environment are sampled at the beginning of each tick. They are declared with the ReactiveInput statement. The outputs emitted to the environment are declared with the ReactiveOutput statement.

The PAR(T1,...,Tn) statement spawns n threads that are executed in lock step. Threads in PRET-C are always scheduled based on a fixed static order. This is determined based on the order in which threads are spawned using the PAR construct. For example, a PAR(T1,T2) statement assigns to T1 a higher priority than to T2. Threads communicate through shared variables and reactive outputs. Mutual exclusion is achieved by ensuring that, in every instant, all threads are executed in a fixed order by the scheduler.

The EOT statement marks the end of a tick. When used within several parallel threads, it implements a synchronisation barrier between those threads. Indeed, each EOT marks the end of the local tick of its thread. A global tick elapses only when all participating threads of a PAR( ) reach their respective EOT.

The abort P when pre C construct preempts its body P immediately when the condition C is true. In case of a strong abort, the preemption happens at the beginning of an instant, while the weak abort (indicated by the weak keyword) allows its body to execute and then the preemption triggers at the end of the instant. All preemptions are triggered by the previous value of the Boolean condition C (hence the pre keyword), to ensure that computations are deterministic. This is needed since the values of variables can change during an instant. The use of pre ensures that preemptions are always performed based on the steady state values of variables from the previous tick.

A. Producer Consumer example

We present in Figure 1 a producer-consumer example adapted from [START_REF] Vahid | Embedded System Design[END_REF] to motivate PRET-C. The main function consists of a single main thread that spawns two threads (line 36): a sampler thread that reads some data from the sensor reactive input and deposits this data on a global circular buffer, and a display thread that reads the deposited data from buffer and displays it on the screen, thanks to the user defined function WriteLCD (line 29). The sampler and display threads communicate using the shared variables cnt and buffer. Also, the programmer has assigned to the sampler thread a higher priority than to the display thread. All the threads are declared as regular C functions.

During its first local tick, the sampler thread does nothing. During its second local tick, it checks if its data buffer is full (line 11): as long as buffer is full, it keeps on waiting until the display thread has read some data so that there is empty space in buffer. When it exits this while loop, it then writes the current instant's value of the sensor input to the next available location of the buffer (line 12) and ends its local tick (line 13). During its last local tick, the index i of buffer and the total number of data cnt in buffer incremented (lines 14 and 15), since this is a circular buffer. Then, the sampler loop is restarted.

During its first local tick, the display thread does nothing. During its second local tick, it checks if there is any data available to read from buffer (line 23). If there is no data available, then it ends its local tick and keeps on waiting until some data is sent by the producer. When this happens, it reads the next data from buffer (line 24) and ends its local tick (line 25). During its next local tick, the i index of the buffer is incremented (line 26) and the total number of data cnt in buffer is decremented (line 27). During its last local tick, it sends the data read from buffer to a display device (line 29).

The main thread (main function) has an enclosing abort over the PAR construct. This preemption is taken whenever an external reset button has been pressed in the previous instant (line 37). When a strong preemption happens, the two threads are aborted and the cnt variable is reset (line 38). The main thread pauses for an instant before flushing the buffer and restarting the two threads again.

When cnt=cnt+1 and cnt=cnt-1 are executed in the same tick, due to the higher priority of the sampler thread over the display thread, cnt will be first incremented by 1, and once sampler reaches its EOT, the scheduler will select the display thread which will then decrement cnt by 1. Thus, the value of cnt will be consistent without the need for enforcing mutual exclusion between the sampler and display threads. Emulating this concurrency on RTOS would lead to race conditions, and it would be the programmer's responsibility to enforce mutual exclusion. Static timing analysis of a synchronous program is equivalent to determining the worst case tick length of this program, termed as the worst case reaction time (WCRT) [START_REF] Mendler | WCRT algebra and interfaces for Esterel-style synchronous processing[END_REF]. For timing analysis of PRET-C, we first generate an intermediate format, called Timed Concurrent Control Flow Graph (TC-CFG). It encodes the explicit control-flow of the threads as well as the forking and joining information of the threads. The TCCFG corresponding to our example of Figure 1 is shown in Figure 2.

B. Mapping logical time to physical time

A PRET-C program is first converted into ARPRET assembly code, and then the TCCFG is extracted from analysing the assembly code. All threads in TCCFG are modelled as concurrent processes in a model checker that supports operations on bounded integers [1]. Then, by evaluating a CTL query, the value of the tight tick length can be determined. More details are presented in [START_REF] Roop | Tight WCRT analysis for synchronous C programs[END_REF].

III. ARPRET architecture

This section presents a hardware accelerator to Microblaze [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF] in order to achieve better throughput for the worst case execution. The hardware accelerator performs PRET-C specific thread scheduling and preemption. ARPRET platform consists of a Microblaze soft-core processor that is connected to a hardware extension, called the Predictable Functional Unit (PFU), using the fast simplex link (FSL) [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF]. More details of this architecture are provided in [START_REF] Andalam | PRET-C: A new language for programming precision timed architectures[END_REF].

Microblaze acts as the master by initiating thread creation, termination, and suspension. The PFU stores the context of each thread in the thread table and monitors the progress of threads as they execute on Microblaze. When a given thread completes an EOT macro, it sends appropriate control information to the Thread Control Block through the FSL. In response to this, the PFU sets the local tick bit for this thread to 1, and then invokes the scheduler. The scheduler then selects the next highest priority thread for execution by retrieving its program counter from the thread table and sending it to Microblaze.

IV. Benchmarks and results

In this section, we first compare the execution of PRET-C on ARPRET with the pure software execution on MicroBlaze to assess the efficacy of the proposed hardware acceleration. We then compare the software execution of PRET-C with Protothreads, SC, and Esterel. Comparison is done over both execution time and memory usage of a set of benchmark programs with a high degree of concurrency and preemption. Some of the benchmarks are adaptations of programs from the Estbench [START_REF] Edwards | Estbench Esterel benchmark suite[END_REF] suite.

To preserve behavioural equivalence between Protothreads and PRET-C, we made Protothreads synchronous by using the yield construct that is similar to EOTs, and also by forcing tick synchronisation to facilitate a synchronous execution like PRET-C and Esterel. Preemptions in Protothreads were emulated using a software-like approach based on the placement of checkaborts. For Esterel, all non-immediate aborts were replaced by their immediate counterparts.

A. Benchmarking

The benchmarking process was carried out as follows. Firstly, we generated code for ARPRET. Then, for the same benchmarks, we generated C code for execution on Microblaze. To enable a fair comparison with the hardware scheduler, thread scheduling was done very efficiently in software using a CEClike [START_REF] Edwards | Code generation in the Columbia Esterel Compiler[END_REF] linked-list based scheduler. We call this approach the software compilation approach for PRET-C. We present the results of the hardware versus software execution of PRET-C in Table II.

For execution time comparison, we used random test vectors and measured the execution time over one million reactions. The worst case (W) is the maximum of the measured values, while the average case (A) is obtained by averaging all samples. Our estimated WCRT value (U) is obtained through the static analysis approach based on model checking presented in Section II-B. Table II shows that the hardware approach is 28% more efficient for the average case, and 26% for the worst case execution when compared to the software approach.

The comparison results of PRET-C software execution with SC, Protothreads, and Esterel is presented in Table III. Code was generated on Microblaze for SC, Protothreads, Esterel, and the PRET-C software approach. We used the CEC Esterel compiler since it consistently generated the most efficient code compared to all other Esterel compilers. PRET-C yields significantly more efficient code compared to all others in both the average (A) and worst (W) cases. Finally, the memory usage (M in bytes) of PRET-C is better compared to Protothreads and Esterel, while being slightly worse than SC, by only 4%.

V. Conclusions and future work

We have presented the language PRET-C, targeting real-time embedded systems, by simple synchronous extensions to the C language. PRET-C has constructs for logical time, synchronous concurrency, and preemption. It also offers deterministic access to shared memory, such that all PRET-C programs are causal [START_REF] Benveniste | The synchronous languages 12 years later[END_REF] and thread-safe [START_REF] Lee | The problem with threads[END_REF] by construction. We have also designed a hardware accelerator to improve the worst case behaviour of PRET-C programs so that overall real-time implementation is achieved without sacrificing throughput [START_REF] Lickly | Predictable programming on a precision timed architecture[END_REF].

We benchmarked the proposed approach by comparing an efficient software implementation of PRET-C with the hardware approach. We also compared the software approach with two other light-weight C libraries. In all cases, the proposed approach excels both in terms of worst case execution time and code size. When compared with Esterel, PRET-C achieves consistently better results. Interestingly, since the average case performance of PRET-C (software approach) is also significantly better than the average case execution of SC, Protothreads, and Esterel, it implies that PRET-C can be used not only for real-time systems but also for any systems where throughput is important. In the near future, we will investigate multicore execution of PRET-C and memory hierarchy issues.

Fig. 2 .

 2 Fig. 2. TCCFG of the Producer-Consumer

  10480 261 493 9506 53 138 10544 78 109 12340 86.21 32.07 62.82 80.93 31.88 13.76 Channel Protocol 91 122 11832 684 757 11528 139 162 11680 232 313 17628 86.07 34.53 75.43 83.88 24.69 61.02 Reactor Control 98 114 10652 444 520 10094 93 106 10668 112 144 12716 77.93 -5.37 42.86 78.08 -7.54 20.83 Producer Consumer 43 62 14520 355 422 13818 74 86 17336 408 417 17060 87.89 41.89 89.71 85.31 27.90 85.13 Smokers 328 412 10720 589 671 11054 268 520 10648 552 1063 12716 44.31 -22.38 59.43 38.60 20.76 61.24 Robot Sonar 130 175 8198 720 770 8054 194 236 8154 408 417 22388 81.94 32.99 82.11 77.27 25.85 58.03 Average 77.50 18.95 68.72 74.01 20.59 50.00

	PRET-C (SW)		SC		Protothreads		Esterel			AC Gain%	WC Gain%
	Example A	W	M	A	W	M	A	W	M	A	W	M	SC	PT	Esterel SC	PT Esterel
	ABRO 36 94
															TABLE II
										QUANTITATIVE COMPARISON OF HARDWARE VERSUS SOFTWARE
													EXECUTION OF PRET-C

TABLE III QUANTITATIVE

 III COMPARISON OF THE PRET-C SOFTWARE APPROACH WITH SC, PROTOTHREADS AND ESTEREL