domain: chim spi

text:
Jonathan Raynaud

Vincent Pateloup

Mégane Bernard

Delphine Gourdonnaud

Damien Passerieux

Dominique Cros

Valérie Madrangeas

Thierry Chartier

Hybridization of additive manufacturing processes to build ceramic/metal parts: Example of LTCC

Stereolithography is an additive manufacturing process, which makes it possible to fabricate useful complex 3D ceramic parts with a high dimensional resolution and a good surface finish.

By coupling the latter process with a second, to deposit another material, it will be possible to obtain multi-material parts using a hybrid machine. This machine is therefore composed of two additive manufacturing processes: stereolithography and robocasting. During this work, we decided to study ceramic -metal assemblies and more particularly the LTCC materials. These materials have low sintering temperatures, generally less than 1000 °C. The mechanical and electrical properties will be studied of the development of parts with complex and innovative geometries to improve the characteristics of current circuits. Finally, our substrate have an excellent permittivity (εr=5.05) and dielectric loss (tan δ=1.8.10 -3 ).

Introduction

The "Temperature Cofired Ceramic" multilayer technologies appeared around the beginning of the 90s. These processes consist in stacking ceramic dielectric sheets elaborated by tape casting, on which conductive patterns, resistances or capacities, were printed by screen-printing (Figure 1). The different printed tapes are assembled and laminated to obtain multilayers circuits. Then metallized holes through the layers, called vias, allow connections between different conductive patterns in different dielectric layers. After lamination, the green stack is submitted to a heat treatment in a controlled atmosphere to eliminate organic and densify components. Co-sintering can be carried out at high temperature (T > 1000 °C) for High Temperature Cofired Ceramics (HTCC) or at low temperature (T ≤ 1000 °C) for Low Temperature Cofired Ceramics (LTCC). The choice of sintering temperature depends on the temperature of use of the component. HTCC parts are used in the power assembly for aerospace [START_REF] Robert | Fiabilité des assemblages de puissance[END_REF]. The LTCC technology is widely used in the manufacture of high frequency devices such as Bluetooth antenna modules, transmitters, power amplifiers, filters and other applications [START_REF] Robert | Fiabilité des assemblages de puissance[END_REF][START_REF] Bakalski | 5-6.5 GHz LTCC power amplifier module with 0.3 W at 2.4 V in Sibipolar[END_REF][START_REF] Scrantom | LTCC technology: where we are and where we're going. II[END_REF]. The dielectric and conductive materials are different for LTCC (alumina/glass and silver, copper or gold) and HTCC (alumina and tungsten or molybdenum), components depending on the temperature of sintering.

The classical route to manufacture HTCC and LTCC parts, i.e. tape casting process for the ceramic substrate and screen-printing for the metallic tracks and vias [START_REF] Smith | HTCC/LTCC use of multiple ceramic tapes in high rate production[END_REF] limits some characteristics of the components:

1) The thickness of a ceramic layer must be larger than 150 microns in order to properly manipulate the tape cast green sheet,

2) The shape of the metallic conductive pattern is limited to 2D patterns linked by vertical vias between dielectric layers which limit the complexity of the metallic network and then the electrical functions than can be integrated inside the LTCC component [START_REF] Robert | Fiabilité des assemblages de puissance[END_REF],

3) There is no possibility of developing lateral shielding, 4) It is impossible to get slanted vias.

In the context of manufacturing of LTCC or HTCC components, additive manufacturing makes it possible to automate production, to build more complex 3D metal circuits than the classical route, to build more complex ceramic packaging shapes and to decrease the thickness of each layer in comparison to classical route. Indeed, additive manufacturing processes gives access to specific architectures to improve properties or to introduce new functions with the deposition of the desired material at each voxel of the part during its construction. In addition, additive manufacturing allows the reduction of production costs because it does not require tooling and limits the loss of raw material.

The present work proposes the development of a new process based on the hybridization of two additive manufacturing processes, i.e. stereolithography and robocasting, to deposit 3D structures of ceramic and metallic materials. In order to evaluate the proposed hybrid process, the feasibility of multimaterial components by hybridization of the stereolithography and robocasting processes is focused on the elaboration of LTCC parts in the article. There is a growing interest to use additive manufacturing processes for LTCC material in many fields of applications (aeronautic, automotive, energy) [START_REF] Induja | Low κ, low loss aluminaglass composite with low CTE for LTCC microelectronic applications[END_REF]. For example, the works of R. Faddoul and al. have shown that it is possible to obtain silver tracks using flexography and inkjet printing [START_REF] Faddoul | Optimisation des procédés d'impression dédiés à la production de masse de composants microélectroniques[END_REF][START_REF] Faddoul | Inkjet printing of silver nanosuspensions on ceramic substrates -sintering temperature effect on electrical properties[END_REF][START_REF] Faddoul | Formulation and screen printing of water based conductive flake silver pastes onto green ceramic tapes for electronic applications[END_REF] in order to reduce the sintering temperature and increase their conductivity with the use of nanoparticles because of their great reactivity. This new hybrid process will be able to decrease the thickness of a ceramic layer down to 50 microns according to the metallic track thickness and to deposit metallic tracks with a thickness of 30-40 microns. The tracks will be connected by metallic vias with the same metal.

It will also be possible to make all-metal layers. In order to show the possibilities offered by this new hydrid process associating stereolithography and robocasting, a hybrid machine has been designed. Several test parts have been realized and characterized in terms of mechanical and electrical behavior to validate this one.

A demonstrative part composed of dielectric ceramic and conductive metal pattern is considered in order to evaluate the possibilities of the developed process (Figure 2). This part is composed of a dielectric substrate (light blue), horizontal tracks (dark blue), oblique and vertical vias (red) and armored vias (black). However, for some preliminary tests, this complex geometry is decomposed in several stages with different difficulties.

Materials and methods

Presentation of the hybrid machine

The two selected processes to manufacture glass/alumina and silver LTCC components are stereolithography and micro-extrusion. Before presenting the hybrid machine, a quick description of the two processes is carried out.

The stereolithography process is based on the selective polymerization, by a computer controlled UV light, of a curable suspension [START_REF] Dupas | Elaboration par stéréolithographie de métamatériaux tout diélectrique pour le domaine du térahertz[END_REF][START_REF] Jacobs | Rapid Prototyping & Manufacturing: Fundamentals of Stereolithography[END_REF][START_REF] Chartier | Additive manufacturing to produce complex 3D ceramic parts[END_REF]. Starting from the CAD file of the part to be realized, the green part is built layer upon layer with the polymerization of cross sectional patterns in each layer (Figure 3a). After completion of the part, the last stages correspond to the cleaning (removal of sticky non polymerized suspension), debinding and sintering. The stereolithography machine used has a laser UV source light, with a wavelength of 355 nm.

Robocasting consists in the extrusion of filaments through a nozzle having a diameter between 100 microns and few millimeters mounted on an X-Y-Z system. The first numerical stages (i.e. CAD, Stl.,…) are identical to those using in stereolithography. A robocasting head has been specifically designed at laboratory to print the conductive metal patterns. This head allows the use of Techcon nozzles with a diameter between 0.1 and 1.5 mm. The schematics of the two processes employed are presented in Figure 3. The metallic network is defined as lines and vias in each layer. Lines and vias in which the metallic paste has to be deposited are not polymerized, then cleaned to remove the nonpolymerized ceramic paste. After, the robot equipped with the extrusion head deposit a filament of metallic paste in the cleaned lines and vias. The strategy chosen to manufacture the complex part presented in Figure 2 is to decompose the manufacturing of this part in different steps of graduated complexity of the printed shapes (Figure 5). The final target is to build in one-step the part given in Figure 2. A final geometry will allow the characterization of our materials in hyper-frequency (Figure 6). This part has been designed by XLim laboratory (Limoges; France) in order to produce optimal performances; these ones having been qualified by retro-simulation in high frequencies with the theoretical perfect geometry. This geometry consists of a surface ground plane (in black) with, on both sides, coplanar access for measurement by microwave probes. The line, embedded in the dielectric substrate, is a half-wave resonator coupled to the coplanar access by evanescent modes. The analysis of the resonances (frequencies and quality factors) will make it possible to characterize the structure. This geometry can be obtained using the hybrid process and then characterized in the microwave range. Our goal is to obtain parts whose dimensions are as close as possible to those designed by the simulation. The choice of materials to reach the expected properties in the microwave is essential.

Ceramic paste for dielectric substrate

LTCC material conventionally used for the dielectric substrate is alumina mixed with a glassy phase [START_REF] Maeder | Assemblage de matériaux céramiques[END_REF]. The glasses generally used are borosilicate. Alumina may be added to improve mechanical properties [START_REF] Induja | Low κ, low loss aluminaglass composite with low CTE for LTCC microelectronic applications[END_REF]. Other glasses are also used and composed of heavier oxides such as Zn, Pb or Bi oxides [START_REF] Zhu | Preparation and properties of low-temperature cofired ceramic of CaO-SiO2-B2O3 system[END_REF]. The conductive tracks can be realized with metallic materials having a high electrical conductivity such as gold, silver, copper or a silver/palladium mixture [START_REF] Khalil | Technologies LTCC et stéréolithographie céramique 3D appliquées à la conception de dispositifs millimétriques et sub-millimétriques[END_REF].

The characteristics of the LTCC substrate material must be adapted to applications at high frequency:

• a low dielectric constant (εr) between 5 and 20 [START_REF] Sebastian | Low-loss dielectric ceramic materials and their properties[END_REF],

• a low dielectric loss (tan δ) between 10 -3 -10 -4 and a dielectric constant temperature coefficient (τε) close to 0 [START_REF] Sebastian | Low-loss dielectric ceramic materials and their properties[END_REF][START_REF] Baker | Integration concepts for the fabrication of LTCC structures[END_REF].

Besides, the light absorption of this material in the UV range has to be low in order to make it possible the polymerization of the ceramic suspension during the stereolithography process [START_REF] Dupas | Elaboration par stéréolithographie de métamatériaux tout diélectrique pour le domaine du térahertz[END_REF]. Finally, it must have a sintering temperature below 1000 ° C [START_REF] Khalil | Technologies LTCC et stéréolithographie céramique 3D appliquées à la conception de dispositifs millimétriques et sub-millimétriques[END_REF], temperature that represents the melting point of the classical materials use at this temperature (silver, gold copper…). A first approach has been to evaluate, in terms of UV light absorption, a commercial LTCC powder (51K65, Heraeus, German) (Figure 7.a). The spectrometer used for this analysis is the model cary 5000 UV-vis-IR, Agilent, USA. In the literature, different proportions of glass mixed with alumina, ranging from 60 to 80% by mass, are proposed [START_REF] Bakalski | 5-6.5 GHz LTCC power amplifier module with 0.3 W at 2.4 V in Sibipolar[END_REF][START_REF] Scrantom | LTCC technology: where we are and where we're going. II[END_REF][START_REF] Khalil | Technologies LTCC et stéréolithographie céramique 3D appliquées à la conception de dispositifs millimétriques et sub-millimétriques[END_REF]. This amount will be selected depending on the desired shrinkage during heat treatment. Now, the selection of the metal composing our tracks and vias can be treated.

Metallic paste for tracks and vias

The metallic tracks allow conduction of the current in the dielectric substrate. The glass was chosen to make it possible a densification of the dielectric alumina/glass mixture at a temperature of 850°C, which is compatible with silver as conductive metal. According to the process, the particle size of the silver powder and the formulation of the paste must allow extrusion through a 100 µm nozzle. The target track width and vias diameter are 100 µm after sintering.

In this respect, a commercial silver paste (ElectroScience, USA -ref. 9912-K) is tested. The paste contains 81.1 wt% silver and 18.9 wt% organic phase. The sintering temperature recommended by the provider is 850 °C for 1 hour. The selected material of substrate should therefore have a similar sintering temperature than the silver metal. The SEM micrograph (JEOL JSM-IT-300-LV) of the silver powder before heat treatment shows a mean silver particle size lower than 1μm (Figure 8 ), that is compatible with an extrusion of the paste through a 100 µm diameter nozzle.

Printed parts

The substrates are printed by stereolithography with a layer thickness of 50 microns.

The tracks are obtained by robocasting with a printed speed of 10 mm.s -1 and a diameter nozzle of 100 µm. An observation of the tracks before thermal treatment are carried out by optical microscopy (Figure 9).

Thermal cycle -Debinding and sintering atmosphere

The first step was to determine the alumina/glass ratio of the substrate material in order to formulate the stereolithography paste. The substrate should have maximum densification after a heat treatment at 850 °C for one hour in air to be in line with the recommendations of the supplier of the metal paste. In this respect, dilatometric analysis (TMA1750, Setaram, France) were performed on pure glass and various glass/alumina mixtures (Figure 10).

The dilatometric curve of the glass (Fig. 10.a) shows two characteristic temperatures. The first one is the glass transition temperature Tg (about 815 °C) and the second one is the softening point (about 870 °C). These values confirm that this glass is adapted for a sintering around 850 °C. Various glass/alumina ratios have been tested ranging from 40 to 70 wt% glass [START_REF] Luo | Microstructure, sintering and properties of CaO-Al2O3-B2O3-SiO2 glass/Al2O3 composites with different CaO contents[END_REF][START_REF] Induja | LTCC tapes based on Al2O3-BBSZ glass with improved thermal conductivity[END_REF]. The higher the glass concentration is, the larger the shrinkage is important (Figure 10b), that is in agreement with the important shrinkage of the pure glass (i.e. 40%) (Figure 10.a). In order to choose the glass/alumina ratio, the relative density of samples of different glass/alumina ratios sintered at 850 °C for one hour, was measured (Table 1). In order to control the dimensional resolution of the LTCC components as well as densification close to 100%, the glass/alumina ratio was fixed at 70 wt% glass -30 wt% alumina which correspond to a classical shrinkage of 18% at the sintering temperature of 850 °C (1 h) recommended by the supplier of the silver paste. This 70/30 wt% glass/alumina ratio is classically found in the literature [START_REF] Induja | Low κ, low loss aluminaglass composite with low CTE for LTCC microelectronic applications[END_REF][START_REF] Wu | Preparation and Characterization of Printed LTCC Substrates for Microwave Devices[END_REF][START_REF] Hsiang | Effects of alumina on the crystallization behavior, densification and dielectric properties of BaO-ZnO-SrO-CaO-Nd2O3-TiO2-B2O3-SiO2 glass-ceramics[END_REF][START_REF] Seo | Phase evolution and microwave dielectric properties of lanthanum borate-based low-temperature co-fired ceramics materials[END_REF][START_REF] Nowak | Cold processing of green state LTCC with a CO2 laser[END_REF] for LTCC dielectric material. Coefficient of Thermal Expansion (CTE) of the 70 wt% glass/30 wt% alumina, measured by dilatometry, is 5.6.10 -6 k -1 and the thermal conductivity measured by the flash laser technic (LFA427, Netzsh, Germany), is of the order of 1.7 W.m -1 . K -1 .

The stereolithography paste containing 71 wt% mixture powder (glass/alumina) powder The elimination of organic components from the stereolithography paste and from the silver paste is complete around 460 and 250 °C, respectively (Figure 10 andb). To be sure that no more organic remains in a component with a thickness of some mm, a temperature of debinding of 600 °C during 3 hours was retained. In order to avoid phenomena of cracking or bubble formation due to the presence of glass, a slow heating rate lower than 1 °C/min was adopted. The resulting thermal cycle is reported in Figure 12. No weight gain was observed on the TGA of the silver up to 850 °C that suggest that no oxidation of the silver occurs. This point will be further verified by the electrical characterization.

Figure 12: Thermal cycle for debinding and sintering of LTCC parts under air Printed multi material parts are sintered according to this cycle (Figure 13).

The uncovered tracks (Figure 13.a) have a width of 130 μm and a thickness of 20 μm.

Vias (Figure 13.b) have a diameter of 250 μm and a depth of 400 μm. A circular silver armor was printed around a via (Figure 13.c), in order to improve the performance of current circuits.

The diameter of the armor is 4.4 mm, a width of 250 μm and a depth of 400 μm. The oblique via (Figure 13.e), makes it possible to avoid several vertical and horizontal transitions to connect two tracks shifted along the x, y and z-axis, has a diameter of 250 μm and a depth of 400 μm.

Mechanical characterizations

The mechanical characteristics of the substrate, after debinding and sintering, according to the thermal cycle given Erreur ! Source du renvoi introuvable., are measured.

The relative density of the LTCC substrate without the silver tracks, measured by the Archimedes' method using ethanol as the inhibiting liquid, is 97%.

The mechanical characteristics are measured using 4-point bending test. The Young's modulus E and the flexural strength σ f are determined using the classical theory of beams:

𝐸 𝐹 𝐿 8𝑏ℎ ∆𝑦 σ 3 L l F 2bh
where ∆𝑦 is the displacement of the machine, L the distance between bottom supports (40 mm) and l (20 mm) the distance between upper supports, b and h the width and the thickness of the beam respectively, and F the maximal load at rupture. The flexural strength and the Young modulus values given Table 2 are in agreement with the characteristics usually found in the literature for a LTCC dielectric substrate [START_REF] Khalil | Technologies LTCC et stéréolithographie céramique 3D appliquées à la conception de dispositifs millimétriques et sub-millimétriques[END_REF][START_REF] Golonka | Technology and applications of low temperature co-fired ceramic (LTCC) based sensors and microsystems[END_REF][START_REF] Jantunen | Design aspects of microwave components with LTCC technique[END_REF].

Electrical characterization

The electrical resistance of the tracks was measured by the 4-points method on the first geometry (Figure 5.a). For more precision of the measurement, a platinum wire was bond with a platinum paste to the places where the measures have to be carried out. The resistivity,

𝜌

, of the tracks is calculated using:

𝜌 𝑅 𝑆 𝑙

where l and S are the length and the section of the track respectively, and R the measured resistance.

In both cases of uncovered tracks and embedded tracks with vias (Figure 5.c), similar resistivity values of 2.8.10 -8 Ω.m for a line length of 20 mm was measured. The localization of the track inside the dielectric part (embedded) does not induce a decrease in conductivity that suggests that the embedded track is not damaged and the vias are well aligned with the tracks. The Table 3 compares our work with results of the literature obtained with silver tracks but not necessarily using the same substrates or the same processes.

Eq. 3

Eq. 1

Eq. 2 The obtained values of resistivity are similar to those reported in the literature, though our hybrid process is very different to the classical ones with the advantage to be able to build more complex geometries and continuous armors.

Hyper frequency characterizations

The glass/alumina dielectric material has been characterized in the microwave frequencies range. In this respect, the permittivity and the dielectric losses of the substrate have been measured at 12 GHz by the coupled resonator method [START_REF] Garreau | Étude de filtres hyperfréquence SIW et hybride-planaire SIW en technologie LTCC[END_REF][START_REF] Bianco | Launcher and microstrip characterization[END_REF][START_REF] Sheen | Amendment of cavity perturbation technique for loss tangent measurement at microwave frequencies[END_REF]. At this frequency, the permittivity of the substrate is ε r = 5.05 and the loss tangent tgδ = 1.8 .10 -3 at 20°C.

Moreover, the temperature coefficient τε, measured between 20 and 80 °C, is 48.10 -6 K -1 . The permittivity, the loss tangent and the temperature coefficient of this dielectric substrate corresponds to values found in the literature for LTCC substrates and the losses show that the glass/alumina mixture can be considered as a good material for application in the high frequencies [START_REF] Jantunen | Design aspects of microwave components with LTCC technique[END_REF][START_REF] Bittner | High-frequency characterization of porous low temperature cofired ceramics substrates[END_REF].

High frequencies characterizations were also performed on micro strip line geometry.

A geometry very close to those presented in Figure 6 has been fabricated. The Figure 12 confirms the feasibility of such a geometry using the developed hybrid machine. A line with a width of 600 microns and a space between the line and the ground plane of 300 microns is obtained. These dimensions are very similar to those simulated. In addition, metal walls are obtained from both sides of the line, which is really an advance for this type of circuit. These are connected to a ground plane embedded in the dielectric substrate. The next step is to characterize these components in microwave frequencies. Subsequently, it will be necessary to improve the filling of the ground plane and the position of the studied strip.

Conclusion

A new hybrid machine has been designed to obtain monolithic multi-material parts, consisting in the association of a stereolithography machine and a robotic arm able to control a robocasting head. This hybrid machine makes it possible to build parts consisting in a dielectric substrate, realized using a stereolithography process and metal tracks deposited by robocasting. LTCC components fabricated using this hybrid machine are sintered under air at 850 °C for 1 h. The dense final parts have mechanical properties close to those obtained by conventional methods with a Young modulus E=83 ± 24 GPa and a flexural strength σf=84 ± 24 MPa. The metal tracks have a minimum width of 110 microns and a maximum thickness of 20 microns after sintering. Their resistivity is near 2.8.10 -8 Ω.m, which is close to the best results found in the literature. The presented printed parts have more or less complex geometries, ranging from an uncoated track to micro strip line.

These results demonstrate the feasibility, by a flexible additive manufacturing process, of complex 3D metallic networks in a dielectric material, which is attractive for LTCC, HTCC or other electronic components. For instance, metallic armors and oblique vias can be elaborated using this hybrid process, which is not possible using conventional routes (i.e. tape casting and screen-printing). To extend the applications, HTCC components also used in microelectronics will be built.

Figure 1 :Figure 2 :

 12 Figure 1: (a) Production cycle of an LTCC circuit board [4,9,10] and (b) Process of screen printing

Figure 3 :Figure 4 :

 34 Figure 3: Principle of the processes of (a) stereolithography [14] and (b) robocastingThe hybridization of the two processes consists in a robotic arm controlling the micro extrusion head positioning coupled to a stereolithography device, as shown in Figure4.

Figure 5 :

 5 Figure 5: Presentation of different geometries studied: (a) Uncovered tracks, (b) Embedded tracks connected to the surface by vias, (c) Armored vias and (d) oblique vias. The metal is represented in dark blue, the substrate in light grey, vias in red and armor in black.

Figure 6 :

 6 Figure 6 : Original geometries for hyper frequency characterization: embedded microstrip resonator with the dimensions given in micrometer range.

Figure 7 :

 7 Figure 7: Spectrometry curve obtained by diffuse reflection on a) commercial Heraeus LTCC powder and b) borosilicate glass powder and c) alumina powder The high absorption of this LTCC material at the wavelength of 355nm used by the stereolithography machine (%R = 38% and %Abs = 62 %) makes this material incompatible with the stereolithography process since more than 60% of the beam exposure density is absorbed at 355nm (Figure 7.a). An X-ray fluorescence analysis has confirmed the presence of many heavy elements that would absorb the light in the UV wavelength.Then a formulation of LTCC material was developed, consisting in a mixture of alumina and a commercial glass, compatible with our stereolithography process. A fine reactive αalumina powder was used (P152SB Alteo, France, d 50 =1.4µm, Specific Surface Area BET = 2.60 m²/g, purity = 99.80%). A commercial borosilicate glass (d 50 =1.6µm, Specific Surface Area BET = 8.75 m²/g) containing only light elements was added in order to avoid UV absorption by the glass. The absorption of alumina and glass at 355 nm (%R = 90% and %Abs = 10%) is very low (Figure7.b and c) and adapted to the stereolithography process. The softening point of this glass is 920 °C. The co-sintering temperature will then be lower than 920°C.

Figure 8 :

 8 Figure 8: SEM Micrograph of the silver powder

Figure 9 :

 9 Figure 9: Micrograph of green parts (a) uncovered tracks, (b) Embedded tracks with vias and (c) Armored vias The green tracks have a width of 150 microns (Figure 9.a) and vias with a diameter of 300 microns (Figure 9.b). Square armors have sides of 5 mm and a width of 300 microns (Figure 9.c). It then is necessary to determine the ideal thermal cycle for debinding and cosintering of printed parts.

Figure 10 :

 10 Figure 10: Thermal analysis of the materials used: (a) Dilatometry of glass and (b) dilatometry of alumina/glass system

30 Relative

 30 and 29 wt% of organics (photoinitiator, monomer/oligomer, binder,…) was formulated by 3DCeram-sinto, Limoges (France). The paste has a shear thinning rheological behavior, necessary for the spreading of thin layers with a viscosity of 26.1 Pa.s at 20 s -1 .A critical step of the process of LTCC components by additive technologies is the debinding and the co-sintering of ceramic/metal parts. The thermal cycle requires to eliminate the organic components without cracking and to obtain a dense part. Both the glass/alumina stereolithography and the silver extrusion pastes were characterized by TGA/DSC Ratio glass/alumina (m%) 40/60 50/50 60/40 70//Differential Scanning Calorimetry -Labsys-evo-1600, Setaram, France) in order to define the debinding thermal cycle (Figure11).

Fig. 11 .

 11 Fig. 11. Thermal analysis under air of (a) LTCC stereolithography glass/alumina system (b) commercial silver paste

Figure 11 :

 11 Figure 11: Optical and electronic microscopy of LTCC multi-materials parts: (a) uncovered tracks, (b) embedded track connected to surface by vias, (c) armored vias, and (d) oblique vias after heat treatment at 850 °C/1 h under air

Figure 12 :

 12 Figure 12 : Micrograph of an embedded micro strip resonator in LTCC materials

Table 1

 1 Relative densities of samples of different glass / alumina ratios sintered at 850 °C for one hour

Table 2 :

 2 Mechanical characteristics of the dielectric substrate after sintering at 850 °C for 1h(10 samples)

		σ f (MPa)	Young modulus (GPa)
	850°C / 1h	84 ± 24	83 ± 24

Table 3 :

 3 Comparison between the resistivity obtained in this study with the literature

	Reference	Substrate	Metal	Process	Sintering temperature (°C)	Time (min)	Resistivity (Ω.m)
	Present work	Glass/alumina	80% Ag	Robocasting	850	60	5.5.10 -8
	Faddoul et al.[8]	LTCC -DP951 (Dupont)	70% Ag -3 µm	Screen printing	875	60	3.10 -8
			Commercial
	Luo et al.[29]	Glass/alumina	paste TC0307 Ag	Screen printing	825	30	4.5.10 -8
			(Heraeus)
			D-901-CT
	Lahti et Lantto [28]	Commercial DP943 (Dupont)	(ESL) and HF602 (Dupont	Gravure-offset printing	850 and 875	/	5.10 -8
			tapes) Ag
	Faddoul et al. [27]	Alumina	70% Ag -3 µm	Flexography	700	15	6.10 -8
	Songping [30]	Ferrite	60 -70% Ag 1-2µm	/	850	15	15.10 -8


Xavier Bouju
email: xavier.bouju@cemes.fr

Youness Benjalal
email: y.benjalal@usms.ma

Jacques Bonvoisin

Unraveling the molecular conformations of a single ruthenium complex adsorbed on the Ag(111) surface by calculations Youness Benjalal, a Jacques Bonvoisin

Introduction

For several decades, a field of research has been focusing on the development of molecules capable of mimicking basic electronic devices, namely molecular electronics. [1][START_REF] Cuevas | Molecular Electronics: An Introduction to Theory and Experiment[END_REF][START_REF] Moth-Poulsen | Handbook of Single-Molecule Electronics[END_REF] Among the different components, one of the most emblematic is the molecular switch. In short, this corresponds to a molecule exhibiting two states that can be switched back and forth due to an external stimulus. These states reveal generally a conformational change that induces a change in the electronic properties of the molecule. Most of the examples already reported in the literature deal with molecules deposited on a surface and involve single molecules or self-assembled molecules in the form of a thin molecular mono-layer. To characterize the properties of single molecules or a localized area of a two-dimensional molecular layer, the most used techniques are local-probe based methods, and more specifically scanning tunneling microscopy (STM). Not only one can obtain images with a sub-ångstro ¨m resolution but also with such a fine positioning of the tip one can generate very local stimuli. These stimuli can be light or local electric fields, which are enhanced beneath the tip, tunneling electrons, or a mechanical action provided by the tip. [29][30][31][32][33] In this work, we describe with numerical methods the adsorption and switching of the tris(dibenzoylmethanato)ruthenium (Ru(dbm) 3 ) molecule on the Ag(111) surface; 34,35 this molecule is of particular interest in the route towards the synthesis of larger entities devoted to charge transfer and logic gates. [36][37][38][START_REF] Hliwa | Architecture and Design of Molecule Logic Gates and Atom Circuits[END_REF] Such a molecule with a Ru core can be considered as a precursor of a mixedvalence complex that is interesting for specific electronic properties through charge transfer generating different oxidation states. [START_REF] Guo | [END_REF]41 Generally, these properties are probed with ensemble measurement techniques but STM allows one to address the single molecule level. Indeed, a bias voltage pulse above such a complex can modify these states with the help of the inelastic contribution of the tunneling current. [42][43][44][45] Before that, one needs to understand the adsorption and the switching properties of an isolated molecule and this is the purpose of the present work. For that, we have performed molecular mechanics and STM image calculations. We have determined the corresponding rotation and diffusion barriers of an isolated molecule on the Ag(111) surface in the framework of the semiempirical mono-electronic Hamiltonian of the ASED+ molecular orbital method. 46,47 On the other hand, theoretical calculations of the STM images have been performed with the extended Hu ¨ckel molecular orbital-elastic scattering quantum chemistry (EHMO-ESQC) code. 48,49 This study reveals that the adsorption of Ru(dbm) 3 on Ag(111) results in two adsorption geometries, three-lobed and bi-lobed objects, each one having itself two distinct types of structure. These overall numerical results are in very good agreement with experimental results. 35

Details

The Ru(dbm) 3 molecule in the gas phase is a three-dimensional object containing 85 atoms, consisting of three dibenzoylmethanato (dbm) groups. These groups are planar and each of them is linked to the ruthenium core atom by two oxygen oduction veral decades, a field of research has been focusing on the pment of molecules capable of mimicking basic electronic s, namely molecular electronics. [1][START_REF] Cuevas | Molecular Electronics: An Introduction to Theory and Experiment[END_REF][START_REF] Moth-Poulsen | Handbook of Single-Molecule Electronics[END_REF] Among the different onents, one of the most emblematic is the molecular . In short, this corresponds to a molecule exhibiting ates that can be switched back and forth due to an external us. These states reveal generally a conformational change that s a change in the electronic properties of the molecule. Most examples already reported in the literature deal with ules deposited on a surface and involve single molecules f-assembled molecules in the form of a thin molecular -layer. To characterize the properties of single molecules ocalized area of a two-dimensional molecular layer, the used techniques are local-probe based methods, and more ically scanning tunneling microscopy (STM). Not only one tain images with a sub-ångstro ¨m resolution but also with a fine positioning of the tip one can generate very local li. These stimuli can be light or local electric fields, which hanced beneath the tip, tunneling electrons, or a mechanical provided by the tip. [29][30][31][32][33] this work, we describe with numerical methods the adsorption itching of the tris(dibenzoylmethanato)ruthenium (Ru(dbm) 3 ) ule on the Ag(111) surface; 34,35 this molecule is of particular st in the route towards the synthesis of larger entities devoted to charge transfer and logic gates. [36][37][38][START_REF] Hliwa | Architecture and Design of Molecule Logic Gates and Atom Circuits[END_REF] Such a molecule with a Ru core can be considered as a precursor of a mixedvalence complex that is interesting for specific electronic properties through charge transfer generating different oxidation states. [START_REF] Guo | [END_REF]41 Generally, these properties are probed with ensemble measurement techniques but STM allows one to address the single molecule level. Indeed, a bias voltage pulse above such a complex can modify these states with the help of the inelastic contribution of the tunneling current. [42][43][44][45] Before that, one needs to understand the adsorption and the switching properties of an isolated molecule and this is the purpose of the present work. For that, we have performed molecular mechanics and STM image calculations. We have determined the corresponding rotation and diffusion barriers of an isolated molecule on the Ag(111) surface in the framework of the semiempirical mono-electronic Hamiltonian of the ASED+ molecular orbital method. 46,47 On the other hand, theoretical calculations of the STM images have been performed with the extended Hu ¨ckel molecular orbital-elastic scattering quantum chemistry (EHMO-ESQC) code. 48,49 This study reveals that the adsorption of Ru(dbm) 3 on Ag(111) results in two adsorption geometries, three-lobed and bi-lobed objects, each one having itself two distinct types of structure. These overall numerical results are in very good agreement with experimental results. 35

Details

The Ru(dbm) 3 molecule in the gas phase is a three-dimensional object containing 85 atoms, consisting of three dibenzoylmethanato (dbm) groups. These groups are planar and each of them is linked to the ruthenium core atom by two oxygen site ´Sultan Moulay Slimane, Faculte ´polydisciplinaire, tement de chimie, Be ´ni Mellal, Morocco. E-mail: y.benjalal@usms.ma S-CNRS, Universite ´de Toulouse, Toulouse, France. : xavier.bouju@cemes.fr

Introduction

For several decades, a field of research has been focusing on the development of molecules capable of mimicking basic electronic devices, namely molecular electronics. [1][START_REF] Cuevas | Molecular Electronics: An Introduction to Theory and Experiment[END_REF][START_REF] Moth-Poulsen | Handbook of Single-Molecule Electronics[END_REF] Among the different components, one of the most emblematic is the molecular switch. In short, this corresponds to a molecule exhibiting two states that can be switched back and forth due to an external stimulus. These states reveal generally a conformational change that induces a change in the electronic properties of the molecule. Most of the examples already reported in the literature deal with molecules deposited on a surface and involve single molecules or self-assembled molecules in the form of a thin molecular mono-layer. To characterize the properties of single molecules or a localized area of a two-dimensional molecular layer, the most used techniques are local-probe based methods, and more specifically scanning tunneling microscopy (STM). Not only one can obtain images with a sub-ångstro ¨m resolution but also with such a fine positioning of the tip one can generate very local stimuli. These stimuli can be light or local electric fields, which are enhanced beneath the tip, tunneling electrons, or a mechanical action provided by the tip. [29][30][31][32][33] In this work, we describe with numerical methods the adsorption and switching of the tris(dibenzoylmethanato)ruthenium (Ru(dbm) 3 ) molecule on the Ag(111) surface; 34,35 this molecule is of particular interest in the route towards the synthesis of larger entities devoted to charge transfer and logic gates. [36][37][38][START_REF] Hliwa | Architecture and Design of Molecule Logic Gates and Atom Circuits[END_REF] Such a molecule with a Ru core can be considered as a precursor of a mixedvalence complex that is interesting for specific electronic properties through charge transfer generating different oxidation states. [START_REF] Guo | [END_REF]41 Generally, these properties are probed with ensemble measurement techniques but STM allows one to address the single molecule level. Indeed, a bias voltage pulse above such a complex can modify these states with the help of the inelastic contribution of the tunneling current. [42][43][44][45] Before that, one needs to understand the adsorption and the switching properties of an isolated molecule and this is the purpose of the present work. For that, we have performed molecular mechanics and STM image calculations. We have determined the corresponding rotation and diffusion barriers of an isolated molecule on the Ag(111) surface in the framework of the semiempirical mono-electronic Hamiltonian of the ASED+ molecular orbital method. 46,47 On the other hand, theoretical calculations of the STM images have been performed with the extended Hu ¨ckel molecular orbital-elastic scattering quantum chemistry (EHMO-ESQC) code. 48,49 This study reveals that the adsorption of Ru(dbm) 3 on Ag(111) results in two adsorption geometries, three-lobed and bi-lobed objects, each one having itself two distinct types of structure. These overall numerical results are in very good agreement with experimental results. 35

Details

The Ru(dbm) 3 molecule in the gas phase is a three-dimensional object containing 85 atoms, consisting of three dibenzoylmethanato (dbm) groups. These groups are planar and each of them is linked to the ruthenium core atom by two oxygen atoms generating an octahedral structure. The size of the molecule is 1.28 nm between two adjacent dbm and 1.21 nm between opposite hydrogen atoms in each dbm group in the gas phase (Fig. 1).

Once deposited on the Ag(111) surface, the geometry of the molecule changes drastically. The adsorbed structure was examined by using an extended semi-empirical atom superposition and electron delocalization (ASED+) approach. 46,47,[50][51][52] This method is based on the extended Hu ¨ckel molecular orbital theory and is a powerful numerical tool to describe the behavior of large molecules. This numerical code has already proven its reliability to calculate the adsorption state using various molecular systems on metallic surfaces, [53][54][55][56] insulating films, 57 and semiconducting surfaces. 58,59 Moreover, ASED+ results have already shown very good agreement with DFT results. 46,47 Standard parameters for carbon, hydrogen, and oxygen were used. 46,47 The (H ii , z) extended Hu ¨ckel parameters for Ru were chosen as Ru 5s (H ii = 8.60 eV, z 1 = 2.078), Ru 5p (H ii = 3.28 eV, z 1 = 2.043) and Ru 4d (H ii = 11.12 eV, z 1 = 5.378, and z 2 = 2.303 with weighting coefficients of 0.534 and 0.6365, respectively), taken from Hoffmann et al. 60 These parameters have been successfully used for the ruthenium tris(b-diketonato) complexes previously studied. 34,55 Calculated STM images were obtained within the electron scattering quantum chemistry (ESQC) method. 48,49 This method describes the electronic scattering between the substrate and the tip by modeling the chemical structure of the tunnel gap (substrate, molecule, tip apex, and tip substrate). The algorithm determines the electronic coupling of atoms in the tunnel junction with a mono-electronic Hamiltonian at the semiempirically extended Hu ¨ckel molecular orbital (EHMO) level. From the scattering matrix of the STM junction, the tunnel current is evaluated by using the Landauer formula. The realistic geometry of all the components composing the STM junction is explicitly considered with a full atomic representation including the tip itself and a set of atomic orbitals is associated with each atomic site. ESQC is reliable to provide accurate STM images not only for small systems but also for large adsorbed molecules. 34,[54][55][56][61][62][63][64]

Results and discussion

The relaxed adsorption position of the Ru(dbm) 3 molecule on the Ag(111) surface is identified with ASED+. This gives two adsorption structures.

Tri-lobed geometry

In the first one called the T geometry (Fig. 2), the molecule lies on the Ag(111) surface with three phenyl groups in contact with the surface keeping an octahedral geometry with the oxygen atoms. The molecular geometry is shown in Fig. 2(b) where all the atoms closest to the surface are at a height of B2.5 Å. The adsorption energy including the van der Waals interaction between the molecule and the metallic surface reaches 0.34 eV. The corresponding STM images of a Ru(dbm) 3 molecule calculated with ESQC with parameters (bias voltage and tunneling current threshold for constant-current imaging mode) similar to those used in experiments 35 show a three-lobe structure (Fig. 3). ASED+ investigations have been performed in order to calculate the rotation barrier when the molecule lies on the different adsorption sites, that is to say when the Ru central atom is above top, bridge and hollow sites. These calculations are presented in Fig. 2(a). The curves describe the adsorption energy variation for the three sites by considering a molecule with all the degrees of freedom free to relax except the x and y coordinates of the central reference atom and of the oxygen atoms, which are kept frozen. The three energy curves give a relatively fair estimation of the rotation barrier along the [111] direction, which is perpendicular to the substrate (Fig. 2(c)), according to the surface site on which the center of the molecule is located. It can be observed that the top site is the most stable and that the differences relative to the hollow and bridge sites are B15 and B20 meV, respectively. Whatever the adsorption site considered, the rotation barrier can be calculated and this yields periodic curves with a periodicity of 601 related to the symmetry of the molecule and the surface. The cross-over points of the three curves are indicative of a barrier which reflects a combination of translation and rotation allowing diffusion on the surface. Moreover, the presented ASED+ calculation does not include the presence of the tip nor the local electrostatic field; these terms probably do not break the apparent symmetry of the energy barriers of rotation due to the large tip-surface distance in the imaging mode and the low bias voltage, so that the molecule stays in the main top site. Furthermore, the structure presented in Fig. 2 suggests the existence of a chiral property. Indeed, the adsorption process generates two enantiomers for the T geometry on the Ag(111) surface (enantiomers T 1 and T 2 ) as indicated in Fig. 3(a andb). In the T 2 geometry, there is an inversion of the position of the phenyl groups with respect to T 1 : the three phenyls in contact with the surface in T 1 will be detached in T 2 with a 3D configuration, and vice versa. These two geometries have the same energetic characteristics (energy and site of adsorption, rotation and diffusion barrier. . .) and the same curves found in Fig. 2(a).

Using these enantiomer conformations, STM images were computed with the ESQC technique under the same tunneling conditions as in experiments (Fig. 3(c andd)). In both cases, the three bright lobes in the triangular arrangement correspond to tunneling through the three phenyl groups at the top, while the triangular sub-protrusions are attributed to the three phenyl groups in contact with the surface, which are connected to the center of the molecule via the oxygen atoms.

These results given in Fig. 3 are qualitatively consistent with the experimental results and quantitatively reflect the main features presented in ref. 35 demonstrating the chirality of the molecule with its enantiomers on the substrate.

Bi-lobed geometry

The second structure is a bi-lobed structure, called the B geometry. Actually, as observed experimentally, 35 80% of the molecules present a bi-lobed shape on the surface after evaporation of Ru(dbm) 3 on Ag(111).

After relaxation with ASED+, the molecule adopts a conformation with two dbm groups almost parallel to the surface and the third one perpendicular to the surface plane. The geometry is thus formed by a square base with a top molecular part which is along the [1% 10] direction of the surface (Fig. 4(b)). This peculiar geometry is called B 1 . The adsorption energy was found to be 0.60 eV where all the atoms closest to the surface are at a height of B2.5 Å. A second geometry is also observed by STM, called B 2 . In this case, the top bi-lobed structure has rotated by about 301 with respect to the B 1 case and appears to be oriented along the side of the square base instead of along the diagonal. It should be noted that the general shape of these two forms does not change during the STM experiments 35 since the molecules are not destroyed during evaporation nor modified while scanning.

To understand the origin of the B 1 and B 2 structures, in connection with the intramolecular and molecule-substrate interactions, we calculated the equilibrium structure of Ru(dbm) 3 in the bi-lobed structure as a function of the rotational angle of the two phenyls around the C-phenyl bond for the top dbm (Fig. 5). 11 The rotation of the right phenyl is clockwise it is counterclockwise for the left phenyl around the angle j and y, respectively (Fig. 5). 65 We consider the molecule with two dbm groups parallel to the surface plane such that the central octahedral structure is preserved. To study the p-p intramolecular interactions between the two phenyls of the top dbm group and the other part of the molecule, we calculated the energy variation associated with the rotation of the two phenyls in the top dbm, as shown in Fig. 6. These calculations show the strong p-p repulsion when the molecule is found in the B ' position (i.e. j = y = AE901), whereas a minimum energy is observed for j = y = AE301. A small energy barrier exists for j = y = 01 (the B 00 case) due to the weak steric crowding between the hydrogen atoms on the top and the HÁ Á ÁO interactions on the bottom in this configuration. Consequently, the B 1 (j = y = 301) and B 2 (j = y = À301) structures correspond to the two minima. Notice that the angle between the two phenyl groups is thus 601, which is a result in very good agreement with ab initio results for the biphenyl molecule. 65 Experimentally, STM images of the B geometry show two forms, each one with two protrusions. 35 The two lines joining these protrusions form an angle of 301. STM image calculations of forms B 1 and B 2 obtained by ASED+ relaxation [Fig. 7(a andc)] exhibit similar features [Fig. 7(b andd)]. Moreover, the angle between the two orientations is also about 301. The agreement is thus excellent. This indicates that the rotation of about 301 of the bi-lobed forms in the experimental and calculated STM images (Fig. 7(b andd)) can be explained by the rotation of each phenyl in the top dbm group by 601 for B 1 and À601 for B 2 around the C-phenyl bond as indicated in Fig. 6(b).

The calculations of the STM images in both the B 1 and B 2 cases in Fig. 7(b andd) show that the two bright lobes in the linear arrangement correspond to the two phenyl groups in the top dbm group, which is oriented along the direction [1% 10], with an apparent height of about 3.9 Å. The two protrusions are separated by about 8.7 Å; this value is in good agreement with the distance between two opposite phenyl groups in the top dbm group of the bi-lobed structure, which is about 8.1 Å (Fig. 4(b) and 5). It is now well-known that reversible switching between two molecular states can be induced by an STM tip. A change in the potential energy surface with respect to particular degrees of freedom may result in a modification of an energy barrier between two states. This change can be generated by the presence of the tip at a relatively low tip-surface distance, e.g. by creating a van der Waals trap, 61 or by an extra induction energy provided by the electric field in the STM junction. 11,16 Here, a switch between the two states has been observed when the tip is located above one of the molecule lobes, as discussed previously. 35 This B 1 2 B 2 switching effect is compatible with the low energy barrier of 60 meV, as shown in Fig. 6. 12,65 Our theoretical results are thus qualitatively consistent and in good agreement with the experimental results. 34,35 In addition we have demonstrated that the central cage around the Ru atom is not distorted by the interaction of the molecule with the Ag(111) surface for different geometries (T 1 , T 2 , B 1 , and B 2 ). The Ru atom keeps its coordination sphere intact (the distance between Ru and O atoms is 2.09 AE 0.03 Å), meaning that in this case the complex coordination atom is not influenced by the interaction of the molecule with the surface. Finally, it was experimentally observed that the switching from T to B occurs for a bias voltage around +2.5 V. Further calculations, but out of the scope of the present paper, should be performed to determine the energetic barrier to go from T to B with explicit consideration of the electric field beneath the STM tip and the molecule using a self-consistent procedure, 66 and an accurate dipole moment calculation of the distorted octahedral cage due to adsorption and the Jahn-Teller effect.

Conclusion

In this work, we have shown that the tris(dibenzoylmethanato)ruthenium molecule adsorbs in two structures on Ag(111) by fully relaxing the molecular structures: a bi-lobed and a threelobed geometry. For this last one, we have shown that this object presents two orientations related to the geometry of the molecular enantiomers on the surface. These results are in good agreement with experimental results in which the T geometry corresponds to three dbm groups forming an octahedral structure on Ag(111). With the second bi-lobed geometry, we have described and presented the possible reversible switching between two stable states of this complex when adsorbed on Ag(111). The B 1 molecular structure has two dbm groups located almost parallel to the Ag(111) surface forming a square pedestal, while the third dbm group is perpendicular to the substrate plane and is directed along the [1% 10] direction. The other structure B 2 can be deduced from B 1 by a mutual rotation of the top phenyl groups. Molecular mechanics calculations have shown that a small energy barrier exists between these two states, compatible with the switching effect observed experimentally. Additionally, STM image calculations of both structures reveal that each structure shows two protrusions and that their respective orientation with the substrate is in agreement with experimental results. We calculated under the same conditions as the experiment the STM images of these structures, B 1 and B 2 . The results show that the bi-lobed shape has rotated by about 301 due to the flexibility of the two phenyl groups in the top dbm. This demonstrates that it is also possible to obtain a B 2 shape on Ag(111) from a B 1 object with the help of a stimulus provided by the STM tip.

  Unraveling the molecular conformations of a single ruthenium complex adsorbed on the Ag(111) surface by calculations Youness Benjalal, a Jacques Bonvoisin b and Xavier Bouju * b The tris(dibenzoylmethanato)ruthenium (Ru(dbm) 3 ) molecule has recently been characterized by scanning tunneling microscopy (STM) experiments upon adsorption on Ag(111). The adsorbed Ru(dbm) 3 molecule shows two conformations with respect to the [1 % 10] direction of the substrate, one with a three-lobed feature and the other one with a bi-lobed structure. For each of these structures, the molecule can take two geometries (states). Molecular mechanics calculations in a semi-empirical framework and STM calculated images reveal that these states on the substrate originate from the enantiomer of the Ru(dbm) 3 molecule in the case of three-lobed structure and from the rotation of the two phenyls in the top dbm moities for the bi-lobed form.

  conformations of a single ruthenium complex adsorbed on the Ag(111) surface by calculations

Fig. 1

 1 Fig. 1 Optimized chemical structure of a tris(dibenzoylmethanato)ruthenium (Ru(dbm) 3 ) molecule in the gas phase (carbon atoms are in gray, hydrogen in white, oxygen in red and the central brown atom is ruthenium).

Fig. 2

 2 Fig. 2 (a) Variation of the rotation barriers of an adsorbed Ru(dbm) 3 molecule when the central Ru atom is above a top (red), hollow (green), and bridge (blue) site of the Ag(111) surface (tri-lobed structure). The curves show the adsorption energy during the rotation taking into account the relaxation of the molecule at each step. The two minima indicated with black arrows are separated by 601 and correspond to the symmetry of the molecule on the surface. Top view (b) and side view (c) of the calculated model of Ru(dbm) 3 above a top site on Ag(111) deduced from ASED+ optimization. Carbon atoms are in gray, hydrogen in white, oxygen in red, the central brown atom is ruthenium and Ag atoms are in blue. The red arrows indicate the [1 % 10] and [11 % 2] directions of the surface.

Fig. 3 (

 3 Fig. 3 (a and b) Calculated models of a Ru(dbm) 3 molecule adsorbed on Ag(111) (structures T 1 and T 2 ). Full (dashed) yellow lines identify the Ru atom-upward (downward) phenyl directions of the three dbm groups. (c and d) EHMO-ESQC calculated images of a Ru(dbm) 3 molecule adsorbed on Ag(111) as shown in (a and b) respectively, under the same tunneling conditions as in the experimental STM.

Fig. 4

 4 Fig. 4 (a) Calculated rotation energy of a Ru(dbm) 3 molecule above a top (red), hollow (green), and bridge (blue) site of the Ag(111) surface (bi-lobed structure). The curves show the adsorption energy during the rotation taking into account the relaxation of the molecule at each step. The red arrow indicates the [1 % 10] direction of the surface, with the long axis of the dbm top oriented along this direction [1 % 10]. (b) Top view and (c) side view of the calculated adsorption geometry of Ru(dbm) 3 on the Ag(111) substrate with the B geometry.

Fig. 5

 5 Fig. 5 Model of a Ru(dbm) 3 molecule on the Ag(111) substrate obtained by ASED+ calculations (type B) with the rotational angles j and y of the two phenyl groups around the C-phenyl bond of the top dbm.

Fig. 6

 6 Fig. 6 Energy variation of the Ru(dbm) 3 molecule adsorbed on the Ag(111) surface (type B) as a function of the rotational angle of the two phenyl groups around the C-phenyl bonds on the top dbm.

Fig. 7 (

 7 Fig. 7 (a and c) Space-filling model of a Ru(dbm) 3 molecule adsorbed on Ag(111) (structures B 1 and B 2 , respectively). (b and d) EHMO-ESQC calculated images of a Ru(dbm) 3 molecule adsorbed on Ag(111) for the forms B 1 and B 2 , respectively, under the same tunneling conditions as in experiments.

Acknowledgements

We thank R. Coratger (CEMES-CNRS) for discussions. This work was supported by Programme Investissements d'Avenir under Program No. ANR-11-IDEX-0002-02, Reference No. ANR-10-LABX-0037-NEXT.

Conflicts of interest

There are no conflicts to declare.


Paul Iannetta

Laure Gonnord

Lionel Morel
email: lionel.morel@cea.fr

On optimizing scalar self-rebalancing trees

Keywords: arbres équilibrés, parallélisme, modèle polyédrique, calcul haute performance Compas

Balanced trees are pervasive and very often found in databases or other systems which are built around querying non-static data. In this paper, we show that trees implemented as a collection of pointers shows bad data locality, poor cache performance and suffer from a lack of parallelism opportunities. We propose an alternative implementation based on arrays. Both implementations appear to be equivalently efficient time-wise. This new layout exposes new parallelism opportunities which can be then exploited by an optimizing polyhedral compiler.

Introduction

Trees, especially balanced trees, are pervasive and are often found behind data strutures which need to be frequently queried such as sets, maps or dictionaries. Hence, they are often found in traditional databases as T-Trees [START_REF] Lehman | A study of index structures for main memory database management systems[END_REF] (a kind of balanced tree built on AVL trees [START_REF] Adel'son-Vel'skii (g | An algorithm for organization of information[END_REF][START_REF] Gonnet | Handbook of Algorithms and Data Structures in Pascal and C[END_REF]) or B-Trees [START_REF] Gonnet | Handbook of Algorithms and Data Structures in Pascal and C[END_REF]. The growing need of analyzing large amount of data, gathered from the internet and stored in gigantic databases require harnessing the computing power of high performance parallel machines at their fullest. Improving the processing of trees is part of this endeavor and, a first step in this direction has been made by Blelloch et al. [START_REF] Blelloch | Just join for parallel ordered sets[END_REF][START_REF] Sun | Implementing parallel and concurrent tree structures[END_REF][START_REF] Sun | Pam: Parallel augmented maps[END_REF] who investigated the benefits of bulk operations to increase parallelism. In this paper, we claim that there is still room for optimizations addressing better cache locality. Indeed, traditional approaches implement trees as collections of pointers. We show that such implementations demonstrate poor data locality, leading to bad performances. Then we explore an alternative representation of those trees with the goal of providing better memory locality, while enabling fine-grained parallelism. Our approach here is to build a memory layout with good properties with respect to the current state of the art compilers and their optimization schemes. This memory layout uses an array instead of a collection of pointers. This induces deep changes to the underlying mechanisms and their complexity (see Section 3). Our goal is to make that this changes in complexity is amortized by better data locality and compiler support for our programs. In particular, not only we will exhibit better opportunities for vectorization, but also we plan to use polyhedral-model based optimizing compilers as backend. The polyhedral model [START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, I, onedimensional time[END_REF][START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, II, multidimensional time[END_REF][START_REF] Feautrier | Encyclopedia of Parallel Computing[END_REF] is a framework which aims at increasing the code locality of affine loop by rescheduling their instructions using various methods such as tiling and pipelining. As far as we know, the polyhedral model has never been considered to address programs using complex data structures relying on pointers such as trees, apart from the work of Paul Feautrier and Albert Cohen [START_REF] Cohen | Analyse de flot de données pour programmes récursifs à l'aide de langages algébriques[END_REF][START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF][START_REF] Feautrier | A parallelization framework for recursive tree programs[END_REF] which uses algebraic languages to describe the iteration space over trees. However, unlike Feautrier and Cohen, our approach does not extend the polyhedral model to tree like data structures. Rather, we try and make fit trees into arrays and see to what extent the operations like insertion, find or deletion can be written so as to fall within the reach of the polyhedral model. Our work focuses on standard operations and their parallelization opportunities before tackling bulk operations which is left for the future. The rest of the paper is organized as follows. Section 2 recalls some background knowledge on AVL trees and the different ways of storing a tree as an array. Section 3 explains in depth our approach and Section 4 presents the optimizations that can be performed and to what extent our redesigned operations fit the polyhedral model. Finally, Section 5 concludes and discusses plans for future work.

Background

AVL Trees

An AVL tree [START_REF] Adel'son-Vel'skii (g | An algorithm for organization of information[END_REF][START_REF] Gonnet | Handbook of Algorithms and Data Structures in Pascal and C[END_REF] is a binary search tree such that both of its children are AVL trees and that the absolute difference of theirs heights is strictly less that two. Those trees support the same operations as standard binary search trees (insert, delete and find). However, in order to keep those trees balanced when inserting or removing an element, they also provide a mechanism called rotation (see Figure 1 for simple or double rotation examples). An insertion needs at most one rotation to preserve the balance while a deletion may require as much as O(lg n) rotations. Nevertheless, since a rotation is an O(1) operation, and that both insertion and deletion inspect the balance ratio of O(lg n) nodes, the complextity of both operations is O(lg n). It is important to note that this will not be the case anymore when AVL trees will be stored as arrays because rotations will not be constant time operations anymore. The find operation is also O(lg n) due to the balanced nature of AVL trees.

x

T 1 y T 2 z T 3 T 4 (a) A binary tree T y z x T 1 T 2 T 3 T 4 (b) T after L-rotation x y T 4 T 1 z T 2 T 3 (c) A binary tree T y z x T 1 T 2 T 3 T 4 (d) T after LR-rotation

AVL trees as arrays

There are two natural categories of tree traversals: breadth-first and depth-first traversals. Each of them induces a linear order which can be used to index the elements of a tree. This order is not unique and depends on the order in which the children are visited.

Depth-first numbering. The depth-first traversal of a tree starts from its root, then recursively visits its left child before recursively visiting its right child. This traversal induces an order on the elements of the tree which can then be used to arrange the elements as an array. However, there is no cheap way to recompute the structure of the tree from this numbering. This is a huge limitation because, in order to perform insertions, deletions, or searching for an element the structure of the tree is needed. A way to keep the structure of the tree is to store two additional arrays: one with the indexes of each node's father and the another with the indexes of each node's right child. Nevertheless, such book keeping is pretty expensive.

Breadth-first numbering. The breadth-first traversal of a tree starts from its root, then it visits each node at distance 1 of the root, then all nodes at distance 2 of the root, and so on until all nodes have been visited. Again, this traversal induces an order on the elements. This time, however, the structure of the array can be easily conserved if we also keep free holes for unused nodes. This way, the numbering induces layers where the i th layer is 2 i -wide. The main advantage of this layered representation is to provide an easy way to recover the tree structure from array indices.

(a) Depth-first Numbering We propose to evaluate in the rest of the paper how this new breadth-first memory layout can expose optimization opportunities, in particular during the construction of the tree where rotations are the crucial operations.

Rotations on breadth first arrays

Traditionally, a rotation is a cheap operation which: 1. moves around two pointers and 2. updates the information about the heights and the balance ratio of the nodes. However, when trees are internally represented as arrays, rotations become much more expensive because, now, part of the array has to be actually moved from one memory location to another. Hence, the cost of a rotation in the worst case becomes O(n). This section describes each operation (left and right rotation, but also left-right and right-left rotations) as a sequence of low-level operations on breadth-first array, namely shifts and pulls. On the other hand, the next section will explore how those low-level operations can be more efficient.

Low-level operations on breadth-first arrays

As presented in Section 2.2, breadth-first arrays provide a convenient index scheme which allows to view the array as a collection of layers. The next paragraphs will explain the action of rotations on those layers. First, we present a collection of low-level operations (shifts and pulls), then, we describe how those low-level operations can be combined to implement rotations.

It should be noted that those low-level operations can be applied on all kinds of breadth-first arrays, by themselves they do not preserve the balancing property of AVL. The combinations presented in Section 3.2 do preserve the balancing property.

Left and right shifts (Figure 4a). A shift moves a subtree at a certain depth to the left or to the right. The tree is moved such that it is still on the same depth. If we move left the left-most y

T 1 T 2 T 3 T 4 (b) Pull-down Left x T 1 T 2 pull up T 1 T 1 (c) Pull-up
Figure 4: Low-level operations subtree or move right the right-most subtree of a depth then this subtree is removed from the tree. The following picture might suggest that this operation is an involution. Nevertheless, this is not the case. First, the values which are moved overwrite previous values if any. Second, a subtree which is moved out of the tree it is forever lost. Pull up (Figure 4c). A pull up takes a subtree and graft it in place of its father. This is a destructive operation in the sense that the father's node as well as one of his children's tree is overwritten. This operation can't be performed on the root because it does not have a father.

Left and right pulls down (Figure 4b). A pull down takes a subtree and graft it at the place of its right (in the case of a right pull down) or left (in the case of a left pull down) children. Conceptually this operation is not destructive, however, in practice, if the array which is used to represent the tree is of fixed size it is. This can be avoided by padding the tree with an empty layer at the bottom.

Rotations as sequences of low-level operations

Now that the elementary operations have been defined, we can use them to implement rotations as is explained in the following table. Unlike the depth-first representation, this time the rotations are not a single in-memory shift but several independent in-memory shifts which are all performed on the same array. The independence of those shifts will be explored in more details in Section 4.

Compas'2020 : Parallélisme / Architecture/ Système/ Temps Réel MILC -Lyon, France, du 30 juin au 3 juillet 2020

Performance analysis

The goal here is to present and analyze the benchmarks, summarizing the time and the percentage of cache misses during the creation of random trees. The experiments have been done on a machine equipped with an Intel ® Core ™ i5-5300U CPU @ 2.30GHz with 3072KB of cache. As can be seen from the above results neither the tree implementation, nor the array implementation are very good with respect to cache utilization. The number of cache misses is not constant for the tree implementation as may suggest the table. The huge number of cache misses in the array implementation is mostly due to the fact that the addresses are not aligned. The density of breadth first arrays is also a huge concern as the more elements they have, the sparser they become. However, an interesting fact is that both require almost the time to construct an AVL tree from scratch. For this reason, we decided to investigate the opportunities that could be brought by a more efficient array implementation.

Optimizing breadth-first arrays

The previous section showed that the usual operations on AVL trees can be performed as a combination of low-level operations on breadth-first arrays. This section will focus on the internal mechanisms of those low-level operations and explore how they could be made more efficient. Most of what is presented focuses on the shift operations, optimizations relative to pulls are only sketched.

Shifts

A shift is an operation which moves internally a subtree to the left or to the right, erasing any previous data and zeroing the source location. Figure 5b illustrates how data moves when the subtree whose root is 2 (the striped region on the figure) is moved to the right into the subtree whose root is 3 (the checkerboard-like region on the figure). Shifting a subtree only modifies the source and destination region, that is why node 1 on the figure remains untouched. It can also be seen that the source region does not overlap with the destination region, this can be hinted to the compiler by using memcpy which provides an interface with restrict pointers since C99. The code listing in Figure 5a 1 makes use of that property.

Another point that should be noted is that layers can be moved independently from one another. More precisely, each node can be moved independently of the others. This means that it 1 This implementation cannot be used to shift a subtree out of an array. idx is the index of the root of the subtree to be shifted, elems is a breadth-first array, len its length, and dir is the shift direction (0 is left and 1 is right.) is possible to massively parallelize the shift mechanism. Indeed, the for is a parallel for and memcpy and memset can be distributed over multiple threads as well as vectorized. While it is possible to add openmp #pragma manually our end goal is that an optimizing compiler should be able to detect itself the parallelization opportunities, as well as the vectorization opportunities and to harness them. When we want to try to expose the inner parallelism of a code mainly using arrays, we cannot help but think of the polyhedral model [START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, I, onedimensional time[END_REF][START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, II, multidimensional time[END_REF][START_REF] Feautrier | Encyclopedia of Parallel Computing[END_REF]. However, our code does not quite fit the model because the iteration variable of the for loop does not follow a linear pattern. PLUTO [START_REF] Bondhugula | Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model[END_REF][START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF] a polyhedral loop parallelizer is able to detect and parallelize memcpy and memset2 but fails to optimize the parallel for. Another room for improvement comes from the fact the data could be moved in small chunks whose size should depend on the features of the processor such as its cache size and the size of the registers used by its vector unit.

Pulls

Like shifts, pulls also offer parallelism and pipelining opportunities. However, unlike for shifts, data is moving from one layer to another and the order of operations becomes important. This leads to more complex moving patterns that will be studied in detail in the future.

Conclusion

In order to address the parallelism issues of self-rebalancing trees, we proposed to change the memory layout to a collection of pointers to an array. Time-wise, the new memory layout performs almost the same as the traditional implementation based on a collection of pointers. We also pointed out that the cost of rotations is higher with this layout but it is possible to alleviate this cost since those can be massively parallelized. In the future, we plan to improve on this work on several directions : first of all, we are working on breath-first arrays compression to improve cache performance. Second, the very predictable data layout of these arrays should enable us to push the limits of polyhedral-based compiler optimisations so that to automatically perform bulk operations.

Figure 1 :

 1 Figure 1: Left (L) rotation applied on to the unbalanced tree T, and a left-right (LR) rotation applied to the unbalanced tree T'

Compas' 2020 :

 2020 Parallélisme / Architecture/ Système/ Temps Réel MILC -Lyon, France, du 30 juin au 3 juillet 2020

Figure 2 :

 2 Figure 2: Array Numberings

Compas' 2020 : 1 right shift T 1 left shift T 1 (

 2020111 Figure 3: Unbalanced trees

  down T 4 pull down T 1 pull down T 1 pull down T 4 2. shift right T 3 shift left T 2 shift left T 2 shift right T 3 3. pull up z pull up z pull up T 2 pull up T 2 4. relabel x, y, z relabel x, y, z relabel x, y, z relabel x, y, z

Compas' 2020 :

 2020 Parallélisme / Architecture/ Système/ Temps Réel MILC -Lyon, France, du 30 juin au 3 juillet 2020 void _shift (int idx, int * elems, size_t len, int dir) { int start_lvl = _greatest_bit_pos(idx + 1); int end_lvl = _greatest_bit_pos(len -1); / * 0 = left -> -1 ; 1 = right -> 1 * / int dir_coef = 2 * dir -1; for (int i = 0 ; i < end_lvl -start_lvl + 1 ; ++i) { int size = (1 << i) * (sizeof * elems); int src = (1 << i) * (idx + 1) -1; int dest = src + dir_coef * depth; memcpy(elems + dest, elems + src, size); memset(elems + src, 0, size);

Figure 5 :

 5 Figure 5: Shift internals

  Each test has been run 10 times. The following table records the mean of the results across those 10 calls.

			avl-tree		avl-bf
	size density time (s) cache-misses (%) time (s) cache-misses (%)
	64	0.55	0.001812	45	0.001659	41
	512	0.33	0.001955	48	0.001792	43
	1024	0.33	0.001754	48	0.001943	43
	65536	0.13	0.031252	17	0.047713	36
	524288	0.17	0.517095	46	0.648161	60
	1048576	0.13	1.192258	47	1.509468	63
	2097152	0.06	3.027440	47	3.779821	63

We have rewritten these two functions as loops operating on single elements, as PLUTO is unable to deal with function calls.