J Philippe
email: jphilipp@laas.fr

M V De Paolis

C Arenas-Buendia

D Henry

A Coustou

A Rumeau

H Aubert

P Pons

Passive and Chipless Packaged Transducer for Wireless Pressure Measurement

Keywords: Passive sensor, chipless sensor, pressure sensor

A new microwave fully passive, chipless and packaged sensor for wireless pressure monitoring in harsh environments (such as, extreme temperature, radioactive and/or toxic environments) is proposed in this paper. The sensor consists of a planar microstrip resonator, which is electromagnetically coupled with a high resistivity and thin silicon membrane. Prototypes have been designed and fabricated using a photoresist intermediate layer for the silicon membrane bonding. The electromagnetic simulation of the system is also performed in order to predict the transducer performances. Measurement results using the packaged sensor are provided to experimentally validate the simulation results and the manufacturing process.

Introduction

Wireless, batteryless (no power supply) and chipless (no electronic circuit) sensors are a promising solution for remote measurements of physical quantities in high radiation or extreme temperature environments, or/and when the battery replacement is difficult or induces high costs. Such remote measurements require two main units: (1) the sensing unit, which is sensitive to any variation of the (physical or chemical) quantity of interest, and (2) the reader, which allows wireless interrogation of the sensing unit. Electromagnetic (EM) sensors operating in the microwave frequency range (see, e.g., [START_REF] Pons | Electromagnetic transduction for wireless passive sensors, Eurosensors[END_REF][START_REF] Thai | A Novel Passive Wireless Ultrasensitive Temperature RF Transducer for Remote Sensing[END_REF][START_REF] Hallil | Novel Microwave Gas Sensor Using Dielectric Resonator with SnO2 Sensitive Layer[END_REF]) are advantageously used here in the sensing unit while a Frequency-Modulated Continuous-Wave (FMCW) radar will serve in our future work as the reader (see, e.g., [START_REF] Bouaziz | Novel Micro-fluidic Structures for Wireless Passive Temperature Telemetry Medical Systems Using Radar Interrogation Techniques in Ka-band[END_REF]). A reading range up to 58 meters of passive humidity EM sensors using such a radar was recently reported in [START_REF] Henry | Long Range Wireless Interrogation of Passive Humidity Sensors using Van-Atta Cross-Polarization Effect and Different Beam Scanning Technique[END_REF].

Literature reports many developments performed on passive pressure sensors with different technologies and devices, such as, e.g., microwave circuits [START_REF] Jatlaoui | Working Principle Description of the Wireless Passive EM Transduction Pressure Sensor[END_REF] [START_REF] Ibrahim | Passive single chip wireless microwave pressure sensor[END_REF], microwave cavity resonators [START_REF] Senior | Wireless passive sensing application using a cavity loaded evanescent mode half mode substrate integrated waveguide resonator[END_REF], evanescent mode resonator [START_REF] Cheng | Evanescent-mode-resonator-based and antenna-integrated wireless passive pressure sensors for harsh-environment applications[END_REF], slot antenna integrated resonator [START_REF] Su | Slot Antenna Integrated Re-Entrant Resonator Based Wireless Pressure Sensor for High-Temperature Applications[END_REF], capacitive sensors [START_REF] Rogers | A Passive Wireless Microelectromechanical Pressure Sensor for Harsh Environments[END_REF], or dielectric resonators [START_REF] Schumacher | Passive chipless wireless pressure sensor for Harsh and reflective environments[END_REF]. Table I reports some of their characteristics in terms of pressure measurement range, operating frequency fres, full-scale frequency range, and the measurement sensitivity.

Table I. Wireless, passive, and chipless pressure sensors reported in the Literature.

Reference

Pressure range fres (GHz) full-scale frequency range (absolute // relative) Measurement Sensitivity [START_REF] Su | Slot Antenna Integrated Re-Entrant Resonator Based Wireless Pressure Sensor for High-Temperature Applications[END_REF] 0.4 -1.2 bar 2.107 6 MHz // 0.28% 7.31 MHz / bar [START_REF] Senior | Wireless passive sensing application using a cavity loaded evanescent mode half mode substrate integrated waveguide resonator[END_REF] 0 -736 Pa 5.16 50 MHz // 0.97% 16 MHz / Pa [START_REF] Ibrahim | Passive single chip wireless microwave pressure sensor[END_REF] 1 -1.8 bar 9.61 25 MHz // 0.26% 0.16 MHz / bar [START_REF] Cheng | Evanescent-mode-resonator-based and antenna-integrated wireless passive pressure sensors for harsh-environment applications[END_REF] 0 -5.3 bar 11.75 200 MHz // 1.7% 35 MHz / bar [START_REF] Rogers | A Passive Wireless Microelectromechanical Pressure Sensor for Harsh Environments[END_REF] 0 -900 Pa 15 16 MHz // 0.11% 0.22 MHz / Pa [START_REF] Schumacher | Passive chipless wireless pressure sensor for Harsh and reflective environments[END_REF] 0 -4 bar 20.53 2.2 GHz // 11% 455 MHz / bar [START_REF] Jatlaoui | Working Principle Description of the Wireless Passive EM Transduction Pressure Sensor[END_REF] 0 -3 bar 39 1.1 GHz // 2.8% 370 MHz / bar

In view of this state of the art as it will be shown in this paper, our packaged pressure sensor offers a larger absolute full-scale frequency range and higher measurement sensitivity.

This paper deals with the manufacturing of passive and wireless microwave sensors for pressure monitoring. These sensors are based on two transductions: (1) the mechanical transduction, which converts the pressure variation into the deflection of a thin membrane, and (2) the electromagnetic transduction, which converts this deflection into the variation of the scattering parameters of the microwave resonator. As an application, pressure monitoring in nuclear plant buildings is targeted. The first part of the paper reports the design and the technological manufacturing process of the proposed pressure sensor. Next, mechanical and full-wave electromagnetic simulation results are discussed and last but not least, the predicted sensor performances in terms of full-scale range and sensitivity are experimentally validated.

Working principle and design of the EM pressure sensor

The passive pressure sensor is a planar microwave resonator, which is electromagnetically coupled with a high resistivity thin silicon (Si) membrane. In the previous design and first concept reported in [START_REF] Jatlaoui | Working Principle Description of the Wireless Passive EM Transduction Pressure Sensor[END_REF], the coplanar (CPW) technology was applied for fabricating the microwave resonator (Fig. 1). However, the packaging of this solution required input and output CPW-to-microstrip discontinuities (see Fig. 2) which may excite multiple undesirable spurious modes in addition to the resonant frequency of the resonator.

As shown in Fig. 3, the use of the microstrip technology instead of a CPW technology allows us the removal of eventual spurious resonances. A high-resistivity Si membrane is placed above the resonator located inside a cavity (Fig. 4). All the dimensions of the structure are reported in Figs. 4 and5.

Manufacturing process

The manufacturing process is described in Fig. 6. It uses a 500 µm thick borosilicate glass (B33) substrate. After piranha and plasma cleaning, a 0.55 µm thick chromium-aluminum (Cr-Al) layer allows manufacturing of the planar microwave resonator by using PVD deposition and lift-off patterning. The ground plane is fabricated by PVD deposition of a 1.55 µm thick Cr-Al layer. A high resistivity Si (100) membrane of thickness 100 µm ± 10 µm is then bonded over the resonator using a low-loss photoresist (thickness of 16 µm). This bonding solution provides a quite simple process to guarantee the sensor is sufficiently hermetic.

Manufacturing analysis

Thicknesses measurement

Resonator metallization and cavity thicknesses were measured before and after the bonding in order to (1) predict the sensor performances and (2) check the reliability of the manufacturing process.

Measured thicknesses before the bonding

In Fig. 7, the locations of the thickness measurement are indicated with the letters C (center), E (east), N (north), S (south) and W (west). Table II gives the thicknesses measured from a mechanical profilometer with an accuracy of ±0.1 µm for the photoresist and of ±0.01 µm for the metallization of the resonator. It is found that the resonator metallization and photoresist layer are deposited at an average acceptable thickness of respectively 0.57 µm and 15.7 µm with an average deviation of ±0.02 µm (3.5 %) and ±0.5 µm (3.2 %). Si membranes thicknesses were also measured using a dial test indicator with an accuracy of ±1 µm. For a given membrane, measurements indicate that the thickness ranges between 102 µm and 105 µm. After the bonding step, the separation distance between the bottom of the Si membrane and the planar resonator was measured by using X-ray microtomography at different points on the circular cavity. The measurement resolution is of 2.5 -3 µm and the measurement accuracy is of ±0.1 µm. The variation from the center point of the cavity thickness is between -1.7 % and 5.1 % (see Fig. 8). The separation distance between the planar resonator and the bottom of the membrane is then quasiuniform inside the circular cavity. The cavity thickness of the sensor (placed at point T in Fig. 7) was also measured using interferometric profilometry technique with a measurement accuracy of ± 0.5 µm. This distance is evaluated at 15.2 µm ± 0.5 µm. In the next section, both airtightness and resilience to pressure hysteresis of the sensors will be evaluated in order to validate the technological process and materials choice.

Airtightness measurement

To check the structure is hermetic, the sensors were placed inside a chamber where the vacuum was maintained for some days. The resonant frequency of the planar resonator was measured with a Vectorial Network Analyzer (VNA), as it will be detailed in Section 6. The results are displayed in Fig. 9. From the frequency measured when vacuum is established (1.2x10 -5 mbar), it is observed that the circular cavity is not fully hermetic: an undesirable decrease of 7.54 MHz per hour (or equivalently of 0.035 % per hour) of the resonant frequency occurs. However, as a pressure monitoring will be performed in less than one hour in our application, it can be concluded that the sensors' airtightness sufficient to demonstrate the proof-of-concept.

Resilience to pressure hysteresis of the fabricated sensors

The samples were placed inside a hermetic chamber. The resilience to pressure hysteresis was measured by applying pressure cycles {atmosphere pressure -vacuum} and by measuring the resulting resonant frequency shift after the air filling of the chamber. The measurement results are reported in Table III. In the worst case, the resonant frequency changes from the initial value fref of ± 0.90 % (± 205 MHz for fref = 22.8 GHz). The resilience to pressure hysteresis of the sensors is therefore acceptable for the proof-of-concept phase.

Full-wave electromagnetic simulation of the pressure sensor

The performances in terms of full-scale range and sensitivity of the microwave pressure sensor were evaluated by using rigorous (full-wave) electromagnetic simulations. These simulations were performed by using ANSYS HFSS commercial software [13].

Simulated sensor performances without overpressure

Considering the transducer described in Figs. 4 and5, the effect of the cavity thickness on the electromagnetic descriptors is first studied. The cavity and membrane thicknesses of the transducer (placed at point T in Fig. 7) are respectively of 15.2 µm ± 0.5 µm and between 102 µm and 105 µm. From electromagnetic simulations, the resulting resonant frequency of the planar resonator is expected between 22.6 GHz and 22.8 GHz for a Si membrane thickness of 105 µm (see Table IV). The very small non-uniformity (5µm) of the membrane thickness is expected to generate a acceptable frequency shift of 80 MHz (~0.35 %) of the resonant frequency (see Table V). The amplitude of the microwave electric field (E-field) on the microwave resonator surface was also computed. As observed from Fig. 10 (a) and (c), the maximum E-field amplitude is located at the two edges of the halfwavelength microstrip resonator (coordinates XA = 1.535 mm and XB = -1.535 mm in Fig. 10). The E-field amplitude decreases abruptly by moving away from the edges (see Fig. 10 (c)).

Simulated sensor performances with overpressure

In order to analyze the performances of the sensor when the overpressure occurs on the Si membrane, it is necessary to compute the membrane deflection when a pressure is applied. An accurate model for membrane deformation prediction is now described.

Mechanical modelling

The deflection of the membrane when the pressure is applied (that is, when a gradient is created between pressures inside and outside of the cavity) can be simulated from a close-form expression and from rigorous simulation techniques.

When the pressure is applied on the Si membrane surface, the resulting membrane deflection can be derived from a fourth-order differential equation. The solutions of this equation depend on the geometry (square, circular, rectangular, etc.), dimensions, and mechanical properties of the membrane [START_REF] Boukabache | Microcapteurs de pression, Technique de l'ingénieur[END_REF]. As the cavity is circular in our case, only membranes with circular geometry were considered here. The deflection 𝑊𝑊(𝑟𝑟) of the membrane when an overpressure is applied on its surface can be approximated by the following close-form expression (see Fig. 11) [START_REF] Mingli | Multiphysic Simulations Approach for an EM Transduction Based Pressure Sensor, Micromechanics and Microsystems Europe Workshop[END_REF]:

𝑊𝑊(𝑟𝑟) = 𝑊𝑊 0 𝑊𝑊 𝑁𝑁 (𝑟𝑟) (1)
where W0 denotes the maximum deflection at the membrane center, and WN(r) designates the distance from the center. For the circular membrane, W0 and WN(r) can be approximated as follows [START_REF] Mingli | Multiphysic Simulations Approach for an EM Transduction Based Pressure Sensor, Micromechanics and Microsystems Europe Workshop[END_REF]:

𝑊𝑊 0 = 12𝑅𝑅 4 (1-𝜈𝜈 2 ) 64𝐸𝐸𝑒𝑒 3 𝑃𝑃 (2) 𝑊𝑊 𝑁𝑁 (𝑟𝑟) = (1 - 𝑟𝑟 2 𝑅𝑅 2 ) 2 (3)
where R and e denote respectively the radius and the (uniform) thickness of the membrane while E, ν, and P are respectively the Young's modulus, the Poisson's ratio, and the applied overpressure.

From Eq. ( 1), it can be observed that the deflection depends only on dimensions ( R and e) and mechanical properties (E and ν) of the circular membrane. mechanical properties (E and ν) of the circular membrane. For a membrane radius R of 2750 µm and a thickness e of 105 µm, and assuming that the direction of the Si membrane deflection occurs along the crystallographic direction <001>, we will set E to 130 GPa and ν to 0.28. Moreover, in our application, the applied overpressure P will vary between 0 to 2.5 bars. The membrane deflection when the pressure is applied was also analyzed from rigorous mechanical simulations by using COMSOL Multiphysics commercial software [16]. These simulations allow taking into account the geometry and mechanical properties of the constitutive materials (Si, photoresist, and B33 materials) of the sensor. Assuming that the Si membrane deflection occurs in the crystallographic direction <001>, a so-called pressure boundary load was assigned along the z-axis to the top faces B33, Si, and photoresist materials (see Fig. 12 (a)), while the fixed constraint (perfect clamping) was assumed on the bottom side of the B33 material, as illustrated in Fig. 12 (b). Fig. 13 shows the simulated total deformation of the membrane obtained from COMSOL Multiphysics software by assuming an applied overpressure of 1 bar, and Fig. 14 displays the maximal membrane deflection as a function of the applied overpressure. As expected, a linear relationship is obtained both from the close-form expression of Eq.( 1) and from the rigorous mechanical simulations. Moreover, the difference between the results given by these two simulation approaches does not exceed 9%. From these results, the pressure beyond which the membrane is in contact with the planar resonator can be predicted. From the close-form expression, this pressure is of 2.44 bars (see point P1 in Fig. 14(a)) while the rigorous membrane simulation gives 2.23 bars (see point P2 in Fig. 14(a)).

Electromagnetic simulation of the microwave pressure sensor

In order to analyze the impact of the membrane deflection on the performance of the microwave pressure sensor, rigorous (full-wave) electromagnetic simulations were performed by using of ANSYS HFSS commercial software [13] and by applying a flat membrane model (the clamping condition of the membrane is then taken into account in these simulations). The electromagnetic simulations were performed for the displacements d extracted from the following simulation conditions:

• Case A: where the electrical field E-field is maximum, i.e. in x = XA for the corresponding displacement calculated through the close-form expression; • Case B: where the electrical field E-field is maximum, i.e. in x = XA for the corresponding displacement simulated through COMSOL simulations; • Case C: where the membrane deflection is maximum, i.e. at the center of the membrane (x = 0) for the corresponding displacement calculated through the close-form expression; • Case D: where the membrane deflection is maximum, i.e. at the center of the membrane (x = 0) for the corresponding displacement simulated through COMSOL simulations. The variation of the resonant frequency and the input reflection coefficient Sii at fc = 23.8 GHz (radar reader central operating frequency respect to the band (22.8 -24.8 GHz) when an overpressure is applied on the sensor membrane are displayed in Figs. 15 and16. Both the resonance frequency shift and Sii in correspondence with the maximum deflection of the membrane (Cases C and D) are of 62 to 66 % greater than the one obtained for deflections extracted where the E-field is maximum (Cases A and B). Moreover, for the same position on the sensor surface (Cases A and B, and Cases C and D), the difference between the results obtained from the close-form expression and from COMSOL simulations is of 21 -25 % for the resonant frequency shift and of 11 -13 % for the input reflection coefficient.

Experimental results

The packaged sensor is shown in Fig. 17. A dedicated setup is used to apply pressure inside this packaging as depicted on Fig. 18. The pressure is applied with a precision of ± 50 mbar between 0 and 2.7 bars on the top face of the sensor (and thus on the Si membrane) as described in Section 5.2.1. The scattering parameters (reflection and transmission coefficients) of the microwave sensor are measured using a calibrated VNA allows an accuracy of ± 0.05 dB and ± 16 MHz. The reproducibility of the measurement results was first investigated by using one sensor which has been four times mounted, connected and removed from its metallic package. As shown in Table VI, the resonance frequency fres fluctuated slightly during the measurements (0.35 % from its original value) leading to a precision of ± 80 MHz (for a resonant frequency of 22.85GHz). The precision of the measured resonant frequency is then of ± 96 MHz.

Table VI. Measurement results reproducibility of the sensor's resonant frequency

#1 #2 #3 #4 fres (GHz) fres fres. (1+0.013%) fres. (1-0.310%) fres. (1-0.349%)
Measurement results at atmospheric pressure (Patm) give a resonant frequency close to 22.95 GHz (see Fig. 19). Simulation results with a 16µm-thick cavity and a 105µm-thick Si membrane are in agreement with the experimental data with a shift of around 150 MHz (0.7 % of fres). In addition, it can be noticed that the cavity thicknesses of 15 µm and 14 µm provide a frequency shift of 200 MHz (0.9 %) and of 350 MHz (1.5 %), respectively (see Table IV andTable V). The linear behavior of the input reflection coefficient of the microwave sensor between 1 bar and 2 bars depicted in Fig. 20 allows deriving the contact overpressure PC. The extrapolation of linear behavior at 2.54 dB (that is, when the membrane is in contact with the resonator) gives an overpressure PC at 2.26 bars, which corresponds to the value obtained from COMSOL simulation (2.23 bars). It is also relevant to compare in Figs. [START_REF] Mingli | Multiphysic Simulations Approach for an EM Transduction Based Pressure Sensor, Micromechanics and Microsystems Europe Workshop[END_REF] and 16 the experimental data with the simulated results obtained from the four cases defined in Section 5 (see cases A, B, C and D): the results obtained for the deflection in cases A and B (flat membrane model approximation) are in excellent agreement with the measurement data. Moreover, the sensitivity and full-scale range of the sensor between 0 and 2 bars are respectively of 2 % / bar (or equivalently, 460MHz / bar) and 4 % (930 MHz) for the resonant frequency (see Fig. 21).

The best performances are obtained between 1 and 2 bars with a sensitivity of 2.7 % / bar (or equivalently, 620 MHz / bar) and a full-scale range of and 2.7 % (620 MHz). Moreover, when measuring Sii parameter at the operating frequency fc (see Fig. 20), the sensitivity is of 1.86 dB/bar while the fullscale range is of 3.2 dB. Again, the best performances are obtained between 1 and 2 bars with the sensitivity of 2.29 dB/bar and a full-scale range of 2.29 dB. To the best knowledge of the authors, these results show the device is the most sensitive in comparison with the state-of-the-art (see Table I).

Conclusion

This paper described the design, manufacturing and characterization of a transducer dedicated to wireless measurement of pressure. The proposed EM passive and wireless pressure sensor brings a significant performance improvement compared the very first pressure sensor reported in 2007 [START_REF] Jatlaoui | Working Principle Description of the Wireless Passive EM Transduction Pressure Sensor[END_REF]. A monolithic configuration using microstrip technology was proposed and allowed the manufacturing of packaged pressure sensors without spurious resonances. The analysis of the cavity thickness before and after the silicon membrane bonding, as well as the airtightness and the resilience to pressure hysteresis of the transducer, was reported and validated the technological process. Mechanical and electromagnetic simulation results were discussed and were found in very good agreement with experimental data. The future work will consist of remotely interrogating the fabricated pressure sensors by using the FMCW radar beam scanning technique reported in [START_REF] Henry | Long Range Wireless Interrogation of Passive Humidity Sensors using Van-Atta Cross-Polarization Effect and Different Beam Scanning Technique[END_REF] and [START_REF] Philippe | Wireless remote monitoring of packaged passive sensor for in-situ pressure measerement in highly reflective environments[END_REF].

Fig. 1 .

 1 Fig. 1. Top (top) and bottom (bottom) views of the CPW microwave resonator with its thin membrane [6].

Fig. 2 .

 2 Fig. 2. View of the microstripto-CPW transition inside the packaging (bottom) and with the packaging cover (top).

Fig. 3 .

 3 Fig. 3. Measured transmission coefficient (S12) versus frequency of a packaged microstrip line (in blue) and of a packaged CPW line with its input and output microstrip-to-CPW discontinuities (in orange).

Fig. 4 .

 4 Fig. 4. Cross-sectional view of the different sensor layers.The resistivity (ρ), the relative permittivity (εr), and the loss tangent (tan δ) of each material are also given.

Fig. 5 .

 5 Fig. 5. Dimensions of the microstrip resonator. Φ denotes here the diameter of the circular cavity.

Fig. 6 .

 6 Fig. 6. Description of the manufacturing process of the microwave sensor.

Fig. 7 .

 7 Fig. 7. Map of the different cells on the substrate. Green patterns represent the different cavities. C, E, N, S, T, W denote Center, East, North, South, Transducer, and West, respectively.

Fig. 8 .

 8 Fig. 8. Upper (top) and cross-sectional (bottom) micrograph for X-ray microtomography thickness measurement.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Resonant frequency variation vs. time (in hours) for the airtightness analysis.

Fig. 11 .

 11 Fig. 11. Membrane geometry (left) and deflection 𝑊𝑊(𝑟𝑟) when an overpressure P is applied on its surface (right).

Fig. 12 .Fig. 13 .

 1213 Fig. 12. The two structural mechanical boundary conditions: a) a pressure boundary load was assigned along the z-axis and on the top side of the B33, Si and photoresist materials (in purple); b) a fixed constraint (perfect clamping) was assumed on the bottom side of the B33 material (hatched region). It was assumed to model a sensor with a 16 µm thick cavity and a 105 µm thick silicon membrane.

Fig. 14 .

 14 Fig. 14. Membrane deflection as a function of the applied overpressure P obtained from the close-form expression of Eq.(1) and from COMSOL Multiphysics simulations [16]: a) displacement [µm] versus the applied overpressure [bar] at the center of the circular membrane ; b) displacement [µm] along the x-axis of the Si membrane for an applied overpressure of 1 bar. It was assumed to model a sensor having with a 16 µm thick cavity and a 105 µm thick silicon membrane.

Fig. 15 .

 15 Fig. 15.Resonant frequency shift for various applied overpressures. Experimental data (dashed black line) and results obtained in correspondence of the following four cases: Case A (blue line) where the electrical field E-field is maximum in x = XA for the corresponding displacement calculated through the close-form expression; Case B (red line) where the electrical field E-field is maximum in x = XA for the corresponding displacement simulated through COMSOL simulations; Case C (green line) where the membrane deflection is maximum in the centre of the membrane (x = 0) for the corresponding displacement calculated through the close-form expression, and Case D (purple line) where the membrane deformation is maximum at the center of the membrane (x = 0) for the corresponding displacement simulated through COMSOL. Sensitivities are given for each case and are calculated between 0 and 2bars.

Fig. 16 .

 16 Fig. 16. Input reflection coefficient Sii at fc = 23.8 GHz (radar operating frequency) as a function of overpressure: comparison between the experimental data (dashed black line), the close-form expression results, and the COMSOL results (See Fig. 15 for the definition of Cases A, B, C and D). The parameters S and FSR denote respectively the sensitivity and the full-scale range of the sensor between 0 and 2 bars.

Fig. 17 .

 17 Fig. 17. Views of the packaged pressure sensor.

Fig. 18 .

 18 Fig. 18. Experimental setup for measuring the scattering parameters of the microwave sensor when a pressure is applied.

Fig. 19 .

 19 Fig. 19. Measured input reflection coefficient Sii versus frequency for various applied overpressures.

Fig. 20 .

 20 Fig. 20. Measured input reflection coefficient Sii at 23.8 GHz (radar operating frequency) as a function of the applied overpressure.

Fig. 21 .

 21 Fig. 21. Measured resonant frequency shift for various applied overpressures.

Table II .

 II Measured thicknesses of the resonator metallization and photoresist layer (in µm).

	4
		Center C	North N East E South S	West W Average	Average deviation
	Photoresist	16.5	15.9	15.6	15.9	14.8	15.7	0.45
	Resonator Metallization	0.598	0.586	0.573	0.545	0.559	0.57	0.02

.1.2. Measured thicknesses after the bonding

Table III .

 III Resonant frequency variation after pressure cycles.

	Cycle number	Cycle 0	Cycle 1	Cycle 2

Resonant frequency (%) -cell 1 fref

fref .(1 -0.43%) fref .(1 -0.90%) Resonant frequency (%) -cell 2 fref fref .(1 + 0.17%) fref .(1 -0.35%)

Table IV .

 IV Simulation of the cavity thickness impact on the resonant frequency for a Si membrane thickness of 105µm.

	Cavity thickness (µm)	14	15	16
	Resonant frequency (GHz)	22.60	22.75	22.80

Table V .

 V Simulation of the silicon thickness impact on the resonant frequency for a cavity thickness of 16µm.

	Cavity thickness (µm)	100	102	105
	Resonant frequency (GHz)	22.88	22.83	22.80

Acknowledgments

The authors wish to thank Occitanie Region (CARANUC Project) and EDF (Electricité de France) for financial support. This work was partly supported by LAAS-CNRS micro and nanotechnologies platform members of the French RENATECH network. We would like to thank Liliane Duperon for her proofreading of the paper.

Conflicts of Interest

The authors declare no conflict of interest. The founding sponsors had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, and in the decision to publish results.


Nicolas Auger

Mathilde Bouvel

Cyril Nicaud

Carine Pivoteau

Analysis of Algorithms for Permutations Biased by Their Number of Records

Keywords: permutation, Ewens distribution, random generation, analysis of algorithms

The topic of the article is the parametric study of the complexity of algorithms on arrays of pairwise distinct integers. We introduce a model that takes into account the non-uniformness of data, which we call the Ewens-like distribution of parameter θ for records on permutations: the weight θ r of a permutation depends on its number r of records. We show that this model is meaningful for the notion of presortedness, while still being mathematically tractable. Our results describe the expected value of several classical permutation statistics in this model, and give the expected running time of three algorithms: the Insertion Sort, and two variants of the Min-Max search.

Introduction

A classical framework for analyzing the average running time of algorithms is to consider uniformly distributed inputs. Studying the complexity of an algorithm under this uniform model usually gives a quite good understanding of the algorithm. However, it is not always easy to argue that the uniform model is relevant, when the algorithm is used on a specific data set. Observe that, in some situations, the uniform distribution arises by construction, from the randomization of a deterministic algorithm. This is the case with Quick Sort for instance, when the pivot is chosen uniformly at random. In other situations, the uniformity assumption may not fit the data very well, but still is a reasonable first step in modeling it, which makes the analysis mathematically tractable.

In practical applications where the data is a sequence of values, it is not unusual that the input is already partially sorted, depending on its origin. Consequently, assuming that the input is uniformly distributed, or shuffling the input as in the case of Quick Sort, may not be a good idea. Indeed, in the last decade, standard libraries of well-established languages have switched to sorting algorithms that take advantage of the "almost-sortedness" of the input. A noticeable example is Tim Sort Algorithm, used in Python (since 2002) and Java (since Java 7): it is particularly efficient to process data consisting of long increasing (or decreasing) subsequences.

In the case of sorting algorithms, the idea of taking advantage of some bias in the data towards sorted sequences dates back to Knuth [9,p. 336]. It has been embodied by the notion of presortedness, which left. This equivalent definition of records naturally extends to sequences of distinct integers, and for any sequence s of distinct integers, the positions of the records in s and in norm(s) are the same. A position that is not a record is called a non-record.

A cycle of size k in a permutation σ ∈ S n is a subset {i 1 , . . . , i k } of [n] such that i 1 σ → i 2 . . .

σ → i k σ → i 1 .
It is written (i 1 , i 2 , . . . , i k ). Any permutation can be decomposed as the set of its cycles. For instance, the cycle decomposition of τ represented by the word 6321745 is (32)(641)(75).

These two ways of looking at permutations (as words or as set of cycles) are rather orthogonal, but there is still a link between them, provided by the so-called fundamental bijection or transition lemma. The fundamental bijection, denoted F , is the following transformation:

1. Given σ a permutation of size n, consider the cycle decomposition of σ. 2. Write every cycle starting with its maximal element, and write the cycles in increasing order of their maximal (i.e., first) element. 3. Erasing the parenthesis gives F (σ).

Continuing our previous example gives F τ = 3264175. This transformation is a bijection, and transforms a permutation as set of cycles into a permutation as word. Moreover, it maps the number of cycles to the number of records. For references and details about this bijection, see for example [3, p. 109-110].

The number of non-records as a measure of presortedness

The concept of presortedness, formalized by Mannila [START_REF] Mannila | Measures of presortedness and optimal sorting algorithms[END_REF], naturally arises when studying sorting algorithms which efficiently sort sequences already almost sorted. Let E be a totally ordered set. We denote by E the set of all nonempty sequences of distinct elements of E, and by • the concatenation on E . A mapping m from E to N is a measure of presortedness if it satisfies:

1. if X ∈ E is sorted then m(X) = 0; 2. if X = (x 1 , • • • , x ) and Y = (y 1 , • • • , y
) are two elements of E having same length, and such that for every i, j ∈ [ ],

x i < x j ⇔ y i < y j then m(X) = m(Y ); 3. if X is a subsequence of Y then m(X) ≤ m(Y ); 4. if every element of X is smaller than every element of Y then m(X • Y ) ≤ m(X) + m(Y ); 5. for every symbol a ∈ E that does not occur in X, m(a • X) ≤ |X| + m(X).
Classical measures of presortedness [START_REF] Mannila | Measures of presortedness and optimal sorting algorithms[END_REF] are the number of inversions, the number of swaps, . . . One can easily see, checking conditions 1 to 5, that m rec (s) = number of non-records in s = |s|number of records in s defines a measure of presortedness on sequences of distinct integers. Note that because of condition 2, studying a measure of presortedness on S n is not a restriction with respect to studying it on sequences of distinct integers.

Given a measure of presortedness m, we are interested in optimal sorting algorithms with respect to m. Let below m (n, k) = {σ : σ ∈ S n , m(σ) ≤ k}. A sorting algorithm is m-optimal (see [START_REF] Mannila | Measures of presortedness and optimal sorting algorithms[END_REF] and [START_REF] Petersson | A framework for adaptive sorting[END_REF] for more details) if it performs in the worst case O(n + log | below m (n, k)|) comparisons when applied to σ ∈ S n such that m(σ) = k, uniformly in k. There is a straightforward algorithm that is m recoptimal. First scan σ from left to right and put the records in one (sorted) list L R and the non-records in another list L N . Sort L N using a O(|L N | log |L N |) algorithm, then merge it with L R . The worst case running time of this algorithm is O(n + k log k) for permutations σ of S n such that m rec (σ) = k. Moreover, | below mrec (n, k)| ≥ k! for any k ≥ n, since it contains the k! permutations of the form Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, Carine Pivoteau

(k + 1)(k + 2) . . . n • τ for τ ∈ S k . Consequently, O(n + k log k) = O(n + log | below mrec (n, k)|)),
proving m rec -optimality.

Ewens and Ewens-like distribution

The Ewens distribution on permutations (see for instance [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF]Ch. 4 & 5]) is a generalization of the uniform distribution on S n : the probability of a permutation depends on its number of cycles. Denoting cycle(σ) the number of cycles of any permutation σ, the Ewens distribution of parameter θ (where θ is any fixed positive real number) gives to any σ the probability

θ cycle(σ)
ρ∈Sn θ cycle(ρ) . As seen in [1, Ch. 5], the normalization constant ρ∈Sn θ cycle(ρ) is θ (n) , where the notation x (n) (for any real x) denotes the rising factorial defined by x (n) = x(x + 1) • • • (x + n -1) (with the convention that x (0) = 1).

Mimicking the Ewens distribution, it is natural (and has appeared on several occasions in the literature, see for instance [START_REF] Borodin | On adding a list of numbers (and other one-dependent determinantal processes)[END_REF]Example 12]) to define other non-uniform distributions on S n , where we introduce a bias according to some statistics χ. The Ewens-like distribution of parameter θ (again θ is any fixed positive real number) for statistics χ is then the one that gives to any σ ∈ S n the probability

θ χ(σ) ρ∈Sn θ χ(ρ) .
The classical Ewens distribution corresponds to χ = number of cycles. Ewens-like distributions can be considered for many permutations statistics, like the number of inversions, of fixed points, of runs, . . . In this article, we focus on the distribution associated with χ = number of records. We refer to it as the Ewens-like distribution for records (with parameter θ). For any σ, we let record(σ) denote the number of records of σ, and define the weight of σ as w(σ) = θ record(σ) . The Ewens-like distribution for records on S n gives probability w(σ) Wn to any σ ∈ S n , where W n = ρ∈Sn w(ρ). Note that the normalization constant is W n = θ (n) , like in the classical Ewens distribution: indeed, the fundamental bijection reviewed above shows that there are as many permutations with c cycles as permutations with c records. Fig. 1 shows random permutations under the Ewens-like distribution for records, for various values of θ.

Fig. 1: Random permutations under the Ewens-like distribution on S100 with, from left to right, θ = 1 (corresponding to the uniform distribution), 50, 100, and 500. For each diagram, the darkness of a point (i, j) is proportional to the number of generated permutations σ such that σ(i) = j, for a sampling of 10000 random permutations.

Linear random samplers

Efficient random samplers have several uses for the analysis of algorithms in general. They allow to estimate quantities of interest (even when their computation with a theoretical approach is not feasible), and can be used to double-check theoretical results. They are also a precious tool to visualize the objects under study (the diagrams in Fig. 4 were obtained in this way), allowing to define new problems on these objects (for example: can we describe the limit shape of the diagrams shown in Fig. 4?).

As mentioned in [6, §2.1], one can easily obtain a linear time and space algorithm to generate a random permutation according to the Ewens distribution (for cycles), using a variant of the Chinese restaurant process reviewed in what follows. To generate a permutation of size n, we start with an empty array (i) σ of length n that is used to store the values of the σ(i)'s. For i from 1 to n, we choose to either create a new cycle containing only i with probability θ θ+i-1 or to insert i in one of the existing cycles with probability i-1 θ+i-1 . To create a new cycle, we set σ[i] = i. To insert i in an existing cycle, we choose uniformly at random an element j in [i -1] to be the element following i in its cycle, and we set σ[i] = j and σ[σ -1 [j]] = i. To avoid searching for σ -1 [j] in the array σ, we only need to keep σ -1 in a second array while adding the elements in σ.

Starting from this algorithm, we can easily design a linear random sampler for permutations according to the Ewens-like distribution for records, using the fundamental bijection. The first step is to generate a permutation σ in S n with the above algorithm. Then, we write the cycles of σ in reverse order of their maximum, as sequences, starting from the last element and up to exhaustion of the cycle:

n, σ[n], σ[σ[n]], . . . , σ -1 [n]
. Each time we write an element i, we set σ[i] = 0 and each time a cycle is finished, we search the next value of i such that σ[i] = 0 to start the next cycle. This new cycle will be written before the one that has just been written. Note that all these operations can be performed in time complexity O(1) using doubly linked lists for the resulting permutation. In the end, the cycles will be written as sequences starting by their maximum, sorted in increasing order of their maximum, which is the fundamental bijection.

Note that there exists another branching process, known as the Feller coupling, to generate permutations according to the Ewens distribution (see for instance [1, p.16]). Although it is less natural than with the Chinese restaurant process, it is also possible to infer linear random samplers from it. Details will be provided in an extended version of this work.

Average value of statistics in biased random permutations

Let θ be any fixed positive real number. In this section, we study the behavior of several statistics on permutations, when they follow the Ewens-like distribution for records with parameter θ. Our purpose is mostly to illustrate methods to obtain precise descriptions of the behavior of such statistics. Such results allow a fine analysis of algorithms whose complexity depends on the studied statistics.

Recall that, for any σ ∈ S n , w(σ) = θ record(σ) and the probability of σ is w(σ) Wn , with W n = θ (n) . Recall also that the records of any sequence of distinct integers are well-defined. For any such sequence s we subsequently set record(s) to be the number of records of s and w(s) = θ record(s) . Note that for any such sequence s, w(s) = w(norm(s)), because the positions (and hence the number) of records do not change when normalizing.

Technical lemmas

Seeing a permutation of S n as a word, it can be split (in many ways) into two words as σ = π • τ for the usual concatenation on words. Note that here π and τ are not normalized permutations: τ belongs to the set S k in n of all sequences of k distinct integers in [n] where k = |τ |, and π belongs to S n-k in n . The weight function w behaves well with respect to this decomposition, as shown in the following lemmas.

Lemma 1 Let n be an integer, and τ be a sequence of k ≤ n distinct integers in [n]. Denote by m the number of records in τ whose value is larger than the largest element of [n] which does not appear in τ , and define w n (τ ) as θ m . For all σ ∈ S n , if σ = π • τ , then w(σ) = w(π) • w n (τ ).

For instance, the definition of w n (τ ) gives w 9 (6489) = θ 2 (8 and 9 are records of τ larger than 7) and w 10 (6489) = 1 (there are no records in τ larger than 10).

We extend the weight function w to subsets X of S n as w(X) = σ∈X w(σ). For any sequence τ of k ≤ n distinct integers in [n], the right-quotient of X with τ is X/τ = {π : π • τ ∈ X}. Since w(π) = w(norm(π)) for all sequences π of distinct integers, we have w(X/τ ) = w(norm(X/τ )) for all X and τ as above (As expected, norm(Y ) means {norm(π) : π ∈ Y }).

For k ∈ [n], we say that X ⊆ S n is quotient-stable for k if w(X/τ ) is constant when τ runs over S k in n . When X is quotient-stable for k, we denote w q k (X) the common value of w(X/τ ) for τ as above. For instance, X = (4321, 3421, 4132, 3142, 4123, 2143, 3124, 1324) is quotient-stable for k = 1. Indeed,

w q 1 (X) = w(X/1) = w({432, 342}) = w(X/2) = w({413, 314}) = w(X/3) = w({412, 214}) = w(X/4) = w({312, 132}) = θ + θ 2 .
Note that S n is quotient-stable for all k ∈ [n]: indeed, for any τ of size k, norm(S n /τ ) = S n-k so that w(S n /τ ) = w(S n-k ) for all τ of size k. It follows that w

q k (S n ) = w(S n-k ) = θ (n-k) . Lemma 2 Let X ⊆ S n be quotient-stable for k ∈ [n]. Then w(X) = θ (n) θ (n-k) w q k (X).
A typical example of use of Lemma 2 is given in the proof of Theorem 3. Remark: Lemma 2 is a combinatorial version of a simple probabilistic property: Let E τ be the set of elements of S n that end with τ . If A is an event on S n and if the probability of A given E τ is the same for every τ ∈ S k in n , then it is equal to the probability of A, by the law of total probabilities.

Summary of asymptotic results

The rest of this section is devoted to studying the expected behavior of some permutation statistics, under the Ewens-like distribution on S n for records with parameter θ. We are especially interested in the asymptotics in n when θ is constant or is a function of n. The studied statistics are: number of records, number of descents, first value, and number of inversions. A summary of our results is presented in Table 3.2. The asymptotics reported in Table 3.2 follow from Corollaries 4, 6, 9, 11 either immediately or using the so-called digamma function. The digamma (ii) function is defined by Ψ(x) = Γ (x)/Γ(x). It satisfies the identity

n-1 i=0 1 x+i = Ψ(x + n) -Ψ(x)
, and its asymptotic behavior as

x → ∞ is Ψ(x) = log(x) -1 2x -1 12x 2 + o 1 x 2 . We also define ∆(x, y) = Ψ(x + y) -Ψ(x), so that ∆(x, n) = n-1 i=0 1 x+i
for any positive integer n. In Table 3.2 and in the sequel, we use the notations P n (E) (resp. E n [χ]) to denote the probability of an event E (resp. the expected value of a statistics χ) under the Ewens-like distribution on S n for records. Remark: To some extent, our results may also be interpreted on the classical Ewens distribution, via the fundamental bijection. Indeed the number of records (resp. the number of descents, resp. the first value) of σ corresponds to the number of cycles (resp. the number of anti-excedances (iii) , resp. the minimum over (ii) For details, see https://en.wikipedia.org/wiki/Digamma_function (accessed on April 27, 2016). (iii) An anti-excedance of σ ∈ Sn is i ∈ [n] such that σ(i) < i. The proof that descents of σ are equinumerous with anti-excedances of F -1 (σ) is a simple adaptation of the proof of Theorem 1.36 in [START_REF] Bóna | Combinatorics of permutations[END_REF], p. 110-111.

θ = 1 fixed θ > 0 θ := n , θ := λn, θ := n δ , See (uniform) 0 < < 1 λ > 0 δ > 1
Cor.

E n [record] log n θ • log n (1 -) • n log n λ log(1 + 1/λ) • n n 4 E n [desc] n/2 n/2 n/2 n/2(λ + 1) n 2-δ /2 6 E n [σ(1)] n/2 n/(θ + 1) n 1- (λ + 1)/λ 1 9 E n [inv] n 2 /4 n 2 /4 n 2 /4 n 2 /4 • f (λ) n 3-δ /6 11
Tab. 1: Asymptotic behavior of some permutation statistics under the Ewens-like distribution on Sn for records. We use the shorthand f (λ) = 1 -2λ + 2λ 2 log (1 + 1/λ). All the results in this table are asymptotic equivalents.

all cycles of the maximum value in a cycle) of F -1 (σ). Consequently, Corollary 4 is just a consequence of the well-known expectation of the number of cycles under the Ewens distribution (see for instance [1, §5.2]). Similarly, the expected number of anti-excedances (Corollary 6) can be derived easily from the results of [START_REF] Féray | Asymptotics of some statistics in Ewens random permutations[END_REF]. Those results on the Ewens distribution do not however give access to results as precise as those stated in Theorems 3 and 5, which are needed to prove our results of Section 4. Finally, to the best of our knowledge, the behavior of the third statistics (minimum over all cycles of the maximum value in a cycle) has not been previously studied, and we are not aware of any natural interpretation of the number of inversions of σ in F -1 (σ).

Expected values of some permutation statistics

We start our study by computing how the value of parameter θ influences the expected number of records.

Theorem 3 Under the Ewens-like distribution on S n for records with parameter θ, for any i ∈ [n], the probability that there is a record at position i is:

P n (record at i) = θ θ+i-1 .
Proof: We prove this theorem by splitting permutations seen as words after their i-th element, as shown in Fig. 2. Let R n,i denote the set of permutations of S n having a record at position i. We claim that the set R n,i is quotient-stable for ni, and that w(R

n,i ) = θ (n) θ (i) • θ (i-1) • θ. It will immediately follow that P n (record at i) = w(Rn,i) θ (n) = θ (i-1) •θ θ (i)
= θ θ+i-1 . We now prove the claim. Let τ be any sequence in S n-i in n . Observe that norm(R n,i /τ ) = R i,i . Since the number of records is stable by normalization, it follows that w(R n,i /τ ) = w(R i,i ). By definition, π ∈ S i is in R i,i if and only if π(i) = i. Thus R i,i = S i-1 • i in the word representation of permutations. Hence, w(R i,i ) = θ (i-1) θ, since the last element is a record by definition. This yields w(R n,i /τ ) = θ (i-1) θ for any τ ∈ S n-i in n , proving that R n,i is quotient-stable for ni, and that w q n-i (R n,i ) = θ (i-1) θ. By Lemma 2, it follows that

w(R n,i ) = θ (n) θ (n-(n-i)) • w q n-i (R n,i ) = θ (n) θ (i) • θ (i-1) • θ. 2 π τ Sum to w(Si-1) = θ (i-1) θ w n (τ ) 1 i i + 1 n
Fig. 2: The decomposition used to the probability of having a record at i. This record has weight θ and thus, for any fixed τ , the weights of all possible π sum to w(Si-1)

• θ = θ (i-1) • θ.
4 Under the Ewens-like distribution on S n for records with parameter θ, the expected value of the number of records is:

E n [record] = n i=1 θ θ+i-1 = θ • ∆(θ, n).
Corollary 9 Under the Ewens-like distribution on S n for records with parameter θ, the expected value of the first element of a permutation is: E n [σ(1)] = θ+n θ+1 . Remark: Our proof of Corollary 9 relies on calculus, but gives a very simple expression for E n [σ(1)]. We could therefore hope for a more combinatorial proof of Corollary 9, but we were not able to find it.

Number of inversions and expected running time of INSERTIONSORT

Recall that an inversion in a permutation σ ∈ S n is a pair (i, j) ∈ [n] × [n] such that i < j and σ(i) > σ(j). In the word representation of permutations, this corresponds to a pair of elements in which the largest is to the left of the smallest. This equivalent definition of inversions naturally generalizes to sequences of distinct integers. For any σ ∈ S n , we denote by inv(σ) the number of inversions of σ, and by inv j (σ) the number inversions of the form (i, j) in σ, for any j ∈ [n]. More formally, inv j (σ) = {i ∈ [j -1] : (i, j) is an inversion of σ} .

Theorem 10 Under the Ewens-like distribution on S n for records with parameter θ, for any j ∈ [n] and k ∈ [0, j -1], the probability that there are k inversions of the form (i, j) is:

P n inv j (σ) = k = 1 θ+j-1 if k = 0 and P n inv j (σ) = k = θ θ+j-1 if k = 0.
Corollary 11 Under the Ewens-like distribution on S n for records with parameter θ, the expected value of the number of inversions is:

E n [inv] = n(n+1-2θ) 4 + θ(θ-1) 2 ∆(θ, n).
Recall that the INSERTIONSORT algorithm works as follows: at each step i ∈ {2, . . . , n}, the first i -1 elements are already sorted, and the i-th element is then inserted at its correct place, by swapping the needed elements.

It is well known that the number of swaps performed by INSERTIONSORT when applied to σ is equal to the number of inversions inv(σ) of σ. Moreover, the number of comparisons C(σ) performed by the algorithm satisfies inv(σ) ≤ C(σ) ≤ inv(σ) + n -1 (see [START_REF] Cormen | Introduction to Algorithms[END_REF] for more information on INSERTIONSORT).

As a direct consequence of Corollary 11 and the asymptotic estimates of the fourth row of Table 3.

= n δ with 1 < δ < 2, it is Θ(n 3-δ ). If θ = Ω(n 2 ), it is Θ(n).

Expected Number of Mispredictions for the Min/Max Search

Presentation

In this section, we turn our attention to a simple and classical problem: computing both the minimum and the maximum of an array of size n. The straightforward approach (called naive in the sequel) is to compare all the elements of the array to the current minimum and to the current maximum, updating them when it is relevant. This is done (iv) in Algorithm 1 and uses exactly 2n -2 comparisons. A classical optimization is to look at the elements in pairs, and to compare the smallest to the current minimum and the largest to the current maximum (see Algorithm 2). This uses only 3n/2 comparisons, which is optimal. However, as reported in [START_REF] Auger | Good predictions are worth a few comparisons[END_REF], with an implementation in C of these two algorithms, the naive algorithm proves to be

Expected Number of Mispredictions in NaiveMinMax

Theorem 13 Under the Ewens-like distribution on S n for records with parameter θ, the expected numbers of mispredictions at lines 4 and 6 of Algorithm 1 satisfy respectively

E n [µ 4 ] ≤ 2 θ E n [record] and E n [µ 6 ] = 2θ∆(θ, n -1) -(2θ+1)(n-1) θ+n-1 .
Consequently, with our previous results on E n [record], the expected number of mispredictions at line 4 is O(log n) when θ = Ω(1) (i.e., when θ = θ(n) is constant or larger). Moreover, using the asymptotic estimates of the digamma function, the asymptotics of the expected number of mispredictions at line 6 is such that (again, for λ > 0, 0 < < 1 and δ > 1):

fixed θ > 0 θ := n θ := λn θ := n δ E n [µ 6 ] ∼ 2θ • log n ∼ 2(1 -) • n log n ∼ 2λ(log(1 + 1/λ) -1/(λ + 1)) • n o(n)
In particular, asymptotically, the expected total number of mispredictions of Algorithm 1 is given by E n [µ 6 ] (up to a constant factor when θ is constant).

Expected Number of Mispredictions in 3 2 MinMax

Mispredictions in Algorithm 2 can arise in any of the three if statements. We first compute the expected number of mispredictions at each of them independently. We start with the if statement of line 3, which compares T [i -1] and T [i]. For our 1-bit model, there is a misprediction whenever there is a descent at i -2 and an ascent at i, or an ascent at i and a descent at i -2. A tedious study of all possible cases gives:

Theorem 14 Under the Ewens-like distribution on S n for records with parameter θ, the expected number of mispredictions at line 3 of Algorithm 2 satisfies

E n [ν 3 ] = n -2 4 + θ(θ -1) 2 4 + θ 2 (θ -1) 2 12 1 θ + n -1 - 3 θ + n -2 - 1 θ + 1 + θ 2 (θ -1) 2 6 ∆ θ + 1 2 , n -2 2 -∆ θ 2 , n -2 2 .
As a consequence, if θ = λn, then E n [ν 3 ] ∼ We now consider the third if statement of Algorithm 2. If there is a record (resp. no record) at position i -3 or i -2, then there is a misprediction when there is no record (resp. a record) at position i -1 or i. Studying all the possible configurations at these four positions gives the following result. Theorem 16 Under the Ewens-like distribution on S n for records with parameter θ, the expected number of mispredictions at line 5 of Algorithm 2 satisfies

E n [ν 8 ] =
(n -2)((2θ 3 + θ 2 -9θ -3)n + 2θ 4 -5θ 2 + 9θ + 3) 3(θ + n -1)(θ + n -2)

+ θ(2θ 3 + θ + 3) 3 ∆ θ + 1 2 , n -2 2 - θ(2θ 3 + θ -3) 3 ∆ θ 2 , n -2 2 .
As a consequence, if θ = λn, then E n [ν 7 ] ∼ 2λ log 1 + 1 λ -λ(6λ 2 +15λ+10) 3(λ+1) 3 n.

It follows from Theorems 14, 15 and 16 that: Corollary 17 Under the Ewens-like distribution on S n for records with parameter θ = λn, the total number of mispredictions of Algorithm 2 is

E n [ν] ∼ 2λ log 1 + 1 λ - 24λ 3
+ 54λ 2 + 32λ -3 12(λ + 1) 3 n.

Fig. 4 shows that, unlike in the uniform case (θ = 1), Algorithm 2 is more efficient than Algorithm 1 under the Ewens-like distribution for records with θ := λn, as soon as λ is large enough. ≈ 0.305, and there are fewer mispredictions on average with 3 2 -minmax as soon as λ > λ0. However, since 3 2 -minmax performs n 2 fewer comparisons than the naive algorithm, it becomes more efficient before λ0. For instance, if a misprediction is worth 4 comparisons, 3 2 -minmax is the most efficient as soon as λ > 0.110.

  2, we get the expected running time of INSERTIONSORT: Corollary 12 Under the Ewens-like distribution for records with parameter θ = O(n), the expected running time of INSERTIONSORT is Θ(n 2 ), like under the uniform distribution. If θ

  6λ 2 +8λ+3 12(λ+1) 3 n. Theorem 15 Under the Ewens-like distribution on S n for records with parameter θ, the expected number of mispredictions at line 5 of Algorithm 2 satisfies E n [ν 7 ] ≤ 2 θ E n [record]. As a consequence, if θ = λn, then E n [ν 7 ] = O(1).

1 n 1 nFig. 4 :

 114 Fig. 4: The expected number of mispredictions produced by the naive algorithm (µ) and for 3 2 -minmax (ν), when θ := λn. We have En[µ] ∼ En[ν] for λ0 = √ 34-4 6

(i) Note that our array starts at index 1.

(iv) Note that, for consistency, our arrays start at index 1, as stated at the beginning of this paper.

Acknowledgments Many thanks to Valentin Féray for providing insight and references on the classical distribution and to the referees whose comments helped us clarify the presentation of our work.

† Supported by a Marie Heim-Vögtlin grant of the Swiss National Science Foundation.

Next, we study the expected number of descents. Recall that a permutation σ of S n has a descent at position i ∈ {2, . . . , n} if σ(i -1) > σ(i). We denote by desc(σ) the number of descents in σ. We are interested in descents as they are directly related to the number of increasing runs in a permutation (each such run but the last one is immediately followed by a descent, and conversely). Some sorting algorithms, like Knuth's Natural Merge Sort, use the decomposition into runs.

The following theorem is proved using Lemmas 1 and 2 and the decomposition of Fig. 3.

Theorem 5 Under the Ewens-like distribution on S n for records with parameter θ, for any i ∈ {2, . . . , n}, the probability that there is a descent at position i is:

Fig. 3: The two cases for the probability of having a descent at i. We decompose σ as π • σ(i -1) • σ(i) • τ , and we let ρ = norm(π • σ(i -1) • σ(i)). On the left, the case where σ(i -1) is a record, that is, ρ(i -1) = i: there are i -1 possibilities for ρ(i). On the right, the case where σ(i -1) is not a record: there are i-1 2 possibilities for the values of ρ(i) and ρ(i -1). In both cases, once the images of j ∈ {i -1, . . . n} by σ have been chosen, the weight of all possible beginnings sum to w(Si-2) = θ (i-2) .

Corollary 6 Under the Ewens-like distribution on S n for records with parameter θ, the expected value of the number of descents is:

2(θ+n-1) .

In the second row of Table 3.2, remark that the only way of obtaining a sublinear number of descents is to take very large values for θ.

Finally, we study the expected value of σ(1). We are interested in this statistic to show a proof that differs from the ones for the numbers of records and descents: the expected value of the first element of a permutation is not obtained using Lemma 2.

Lemma 7 Under the Ewens-like distribution on S n for records with parameter θ, for any k ∈ [0, n -1],

the probability that a permutation starts with a value larger than k is:

. Indeeed,there are n-1 k k! ways to position and order the elements of [k], and the total weight of the elements larger than k is θ (n-k) . Hence,

Theorem 8 Under the Ewens-like distribution on S n for records with parameter θ, for any k ∈ [n], the probability that a permutation starts with k is:

Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, Carine Pivoteau the fastest on uniform permutations as input. The explanation for this is a trade-off between the number of comparisons involved and an other inherent but less obvious factor that influences the running time of these algorithms: the behavior of the branch predictor.

Algorithm 1: NAIVEMINMAX(T , n)

8 return min, max

Algorithm 2: 3/2-MINMAX(T, n)

In a nutshell, when running on a modern processor, the instructions that constitute a program are not executed strictly sequentially but instead, they usually overlap one another since most of the instructions can start before the previous one is finished. This mechanism is commonly described as a pipeline (see [START_REF] Hennessy | Computer Architecture, Fifth Edition: A Quantitative Approach[END_REF] for a comprehensive introduction on this subject). However, not all instructions are well-suited for a pipelined architecture: this is specifically the case for branching instructions such as an if statement. When arriving at a branch, the execution of the next instruction should be delayed until the outcome of the test is known, which stalls the pipeline. To avoid this, the processor tries to predict the result of the test, in order to decide which instruction will enter the pipeline next. If the prediction is right, the execution goes on normally, but in case of a misprediction, the pipeline needs to be flushed, which can significantly slow down the execution of a program.

There is a large variety of branch predictors, but nowadays, most processors use dynamic branch prediction: they remember partial information on the results of the previous tests at a given if statement, and their prediction for the current test is based on those previous results. These predictors can be quite intricate, but in the sequel, we will only consider local 1-bit predictors which are state buffers associated to each if statement: they store the last outcome of the test and guess that the next outcome will be the same.

Let us come back to the problem of simultaneously finding the minimum and the maximum in an array. We can easily see that, for Algorithm 1, the behavior of a 1-bit predictor when updating the maximum (resp. minimum) is directly linked to the succession of records (resp. min-records (v) ) in the array. As we explain later on, for Algorithm 2, this behavior depends on the "pattern" seen in four consecutive elements of the array, this "pattern" indicating not only which elements are records (resp. min-records), but also where we find descents between those elements. As shown in [START_REF] Auger | Good predictions are worth a few comparisons[END_REF], for uniform permutations, Algorithm 1 outerperforms Algorithm 2, because the latter makes more mispredictions than the former, compensating for the fewer comparisons made by Algorithm 2. This corresponds to our Ewens-like distribution for θ = 1. But when θ varies, the way records are distributed also changes, influencing the performances of both Algorithms 1 and 2. Specifically, when θ = λn, we have a linear number of records (as opposed to a logarithmic number when θ = 1). The next subsections provide a detailed analysis of the number of mispredictions in Algorithms 1 and 2, under the Ewens-like distribution for records, with a particular emphasis on θ = λn (which exhibits a very different behavior w.r.t. the uniform distribution -see Fig. 4).

(v) A min-record (a.k.a. left to right minimum) is an element of the array such that no smaller element appears to its left.