Manuel Núñez-Regueiro
email: nunez@grenoble.cnrs.fr

Polaron-like conduction in iron pnictides of the Ln-1111 and AE -122 families

Keywords: 71.38.-k, 72.15.-v, 74.90.+n, 74.70.-b

Examination of the electrical resistivities of iron pnictides shows that they follow a " ~T exp(E a k B T) temperature dependence. The activation energies E a show a linear behaviour with the critical temperatures of the spin density waves (SDW), T * , as both vary with pressure. The slope matches the ratio SDW gap to T * , while the intercept can be related to the transition temperature of the lattice distortion, T 0 . An adapted Landau free energy predicts the observed order of the transitions, according to which is higher, T * or T 0 . We discuss our analysis within the framework of polarons.

A new opportunity in high temperature superconductors has now appeared with the report of superconducting transition temperatures up to ~56K in compounds with iron in tetrahedral coordination [1,2,3,4]. As in cuprates, the ground state of the mother compounds exhibits antiferromagnetic order [5] . , whose residual interactions on doping are presently held responsible for the pairing. However, in contrast with cuprates it is an itinerant antiferromagnetic state of the spin density wave type (SDW) [6]. However, the lattice distortion [7] that is also always present in the ground state nor its relation to the SDW are presently understood. Besides, the reason why the phase transition towards the antiferromagnetic state is always second order, while the lattice distortion can be second order for LnFeAsO (Ln-1111), where Ln is a lanthanide, or first order for AEFe 2 As 2 (AE-122), where AE is an alkaline-earth, remains also a puzzle. More basically, the "bad metal" electrical resistance of these materials at high temperatures, lacks a coherent and straightforward interpretation.

Here it is shown that the electronic transport properties of the mother compounds follow a " ~T exp(E a k B T) dependence, as found for polarons. The analysis of the correlation obtained between the activation energy E a and the transition temperature towards the SDW, T * , using arguments extracted from polaron phenomenology suggests the existence of antiferromagnetic bipolarons. The strong coupling between the lattice and antiferromagnetic transitions is analyzed and the order of the phase transitions deduced, in agreement with experiment.

Band structure calculations for the undoped LnFeAsO (Ln-1111) oxypnictides yield [8] two dimensional cylindrical hole and electron Fermi surfaces that are prone to nesting, rendering an itinerant antiferromagnetic ground state in the form of a SDW [6], as is found experimentally [5] at T * . The archetype for this type of phase transition is chromium metal [9], which develops a SDW at T * =312K. However, the dependence of the electrical resistance of chromium, metallic above and below T * , though common to most of SDW compounds (e.g.

Cobaltites [10]), is strikingly different to the dependence observed in pnictides. As a tetragonal to orthorhombic lattice distortion (TOLD) is also observed[7] at a transition temperature T 0 > T * , it is basic to take into account possible electron-lattice coupling effects. As the crystal field effect of the arsenic tetrahedron on the five degenerate 3d Fe levels can explain several of the Ln-1111 properties [11], it is natural to refer to materials with similar configurations, such as manganites [12]. In fact, the resistivity curve on the E a has a magnitude comparable to the Fe 3d level separation in the distorted tetrahedral field [11]. It is tempting to associate this activation energy to a Jahn-Teller (JT) effect, since, as shown on Fig 3c, there is splitting of a doublet when the TOLD takes place. This analysis is suggestive of JT polarons existing above T 0 , and condensing then into a permanent TOLD, through, presumably, a cooperative JT transition [13]. Alternatively, polarons have been recently [14] predicted in pnictides, although based on the highly polarizable As 4p states, and not on crystal field JT effects.

The optimal way to determine the relationship between E a and T * is from pressure measurements on the same sample [15], as in such a way the differences between different samples (defects, impurities, etc.) are avoided. Up to date reported pressure measurements are Although at this point it may be too early to accept the evidence as proof for the existence of polarons, in the absence of an alternative, the framework applied to polarons, in manganites e.g., may be used to probe the limits of this type of analysis. Thus, it is useful to propose a band picture for the strongly coupled electron-phonon system (similar to the one on Fig. 1 of Ref. [16]) including polaronic levels (Fig 3 c). The point here is that, contrary to manganites, there is no real gap in pnictides. However, precursor fluctuations of the SDW, rendering a pseudogap above T * , are currently expected (due to a nematic phase [17] or dimensionality fluctuations [18]). Such a pseudogap has been used to explain the anomalous magnetic susceptibility [19] of undoped pnictides at T > T * . Experimentally, momentum integrated photoemission spectra show clear evidence of a pseudogap feature in SmFeAsO, also appearing well above the SDW, at temperatures T (~200K) > T * (~132K) [20]. Thus, here a pseudogap Δ * replaces the band gap of manganites.

The thermopower of small polaronic systems is similar to that of band semiconductors, governed by thermal activation of carriers across a small barrier and thus a function of the inverse temperature: Analyzing the activation energy of the electrical resisitivty, for small polarons it is, The relation between the gap and the transition temperature is " * = #k B T * , " = 1.75 in mean field. Thus, (1). In this way the linear dependence of E a on T * can be explained, with the slope α = δ /2. The ratio δ of the gap to the critical temperature is obtained from the reported optical absorption gap measurements for Ln-1111 [22] and AE-122 [23] It is interesting to note that while the intercept ε for the Ln-1111 compounds is positive, that for Ba-122 is also positive but very small, and is negative for Sr and Ca. It is reasonable to assume within the polaron picture that the intercept, may translate the lattice part of the activation energy, while the rest corresponds to the magnetic contribution. When positive (Ln-1111 and eventually Ba-122) the TOLD will appear before the SDW, i.e. T 0 ≥ T * ,while when negative (Sr, Ca) T * » T 0 . In other words, the intercept ε may be related to the part of the activation energy that is due to the JT deformation, positive for the Ln-1111 compounds and thus increasing their stability, while for the AE-122 it is almost zero or negative and decreasing their stability.

S = k B e E S k B T + b " # $ % & '
E a = E S + W H " J ,
E a = E S + "k B T * 2 # J
A Landau free energy analysis is useful here to study the scenario of the interrelation between the transitions, in particular the order of the phase transformations. According to specific heat measurements, the phase transitions are of second order for the Ln-1111 (ε>0)

and Ba-122 (ε>~0) [24] (although for this last compound this seems to be sample dependent

[25], as would be expected due to its very small ε), and of first order for [26] and Ca-122 [27]. The Landau free energy for the system reads

F = a(T" u T * )# SDW 2 + a'(T" u T 0 )# LD 2 + b# LD # SDW 2 " c# LD 2 # SDW 2 + d# SDW 4 + d'# LD 4 (2)
where a,a',b,c,d,d' are parameters, u T * and u T 0 the uncoupled transition temperatures and LD and η SDW are the order parameters for the TOLD and the SDW, respectively. The first, second, fifth and sixth terms are standard. The third linear-quadratic one is a particular coupling allowed by symmetry [START_REF] Tolédano | The Landau Theory of Phase Transitions[END_REF], as the wavevector for the TOLD is twice the one of the SDW (this term is common in spin-Peierls systems) and the fourth one explicits a strong favorable coupling that is assumed between the two transitions based on the same bands. The coupling translates the fact that due to the SDW transition, the bands degenerate at M and Γ split [8], as in a band JT transition Ca-122 compounds, the energy gain from the antiferromagnetic coupling will stabilize the otherwise unstable polarons, while the distortion is the only way to create a magnetic moment (~0.35µ B , Ref. [11]) on the Fe atom. The supposition of antiferromagnetic bipolarons would also justify the existence of a pseudogap at T>T * . It must be noted here that these are not standard bipolarons, as the latter are singlet coupling of two polarons that have no localized spin. Transport at T>T * would be performed through antiferromagnetic bipolarons (BP) and free carriers (FC). FC would have a short constant mean free path due to scattering against the disordered BP and a comparatively small T dependence, while the certainly pinned BP can be excited through E a to FC and re-pinned elsewhere, i.e. " BP ~T exp(E a k B T) . Below T * , BP order into the coupled TOLD-SDW, while the ungapped FC would have a mean free path increasing with the TOLD-SDW gap temperature dependence.

In conclusion, it is shown that the "bad metal" electrical resistivity of the mother compounds of the superconducting iron pnictides follows an activated behaviour similar to that of polarons. From the analysis of the variation with pressure of the activation energy and the SDW transition temperature, it is speculated that they are coupled in pairs of antiferromagentically coupled Jahn-Teller bipolarons, that could be crucial in the understanding of the pairing mechanism of pnictides [31,14], if their existence were attested also in the doped materials. Finally, it is also demonstrated that the order of the SDW and TOLD transitions is the consequence of their particular linear-quadratic coupling within a

Landau free energy analysis.

The author acknowledges Gastón Garbarino, Marie-Bernardette Lepetit, José Emilio Lorenzo, Pascal Quemerais and Rubén Weht for help during analysis, and Blas Alascio, Michel Avignon, Claudine Lacroix, Pierre Monceau and Julius Ranninger for fruitful discussions. , Gd [36],Ce [37,38],Tb [39] , Nd [37], Gd [37], Pr [37] and Sm [32,40]. The data shown with half-squares corresponds to structural and electrical resistance measurements on Sm-1111 under pressure [41]. (b) Same as (a) for the AE-122 family, Ba[4],

Sr [32], Ca [42]. (c) Plot of the activation energy as a function of the SDW transition temperature. Only Sm-1111 [41] and La-1111 [43] have been measured under pressure where each point corresponds to one pressure. (d) Same as (c) for the AE-122 compounds, Ba [44] ,

Sr [START_REF] Kotegawa | the Bilbao Crystallographic Server[END_REF], Ca [42]. The dependences are surprisingly linear and parallel within each family of compounds.

Figure 3 (a) Thermopower of Ln-1111 compounds to determine an average activation energy E S (Sm [32], Nd [34], Pr [34] and Ce [34] ). Same as (a) but for the case u T L * (=200K)> u T 0 (=0K). This is the strictest case, higher u T 0 will give almost identical final transition temperatures, but for all T * T 0 cases the TOLD transition will be of first order. (c) Possible structure of the antiferromagnetic bipolaron and its conducting mechanism. The energy levels and spin disposition have been taken from Ref.

11. The bipolarons are in the deformed state and can be excited to the undeformed state through the excitation energy E a , that frees the uppermost electrons (circles) for a FC conduction though they are later pinned down to a new bipolaron state.

  Fig 1(a) bears many resemblances with the behaviour observed in those materials[12], where the transport at high temperatures is attributed to small Jahn-Teller polarons with a " ~T exp(E a k B T) temperature dependence, ρ being the resistivity, E a an activation energy, and k B the Boltzmann constant. Applying this type of transport behaviour on pnictides, the subsequent Arrhenius plot of Fig 1(b) allows determining E a for the Sm-1111 oxypnictide. Although this sample is polycrystalline an identical behaviour is observed for the monocrystalline Sr-122 pnictide, Fig. 1(c) and Fig 1(d), thus confirming that it is an intrinsic feature. E a can thus be obtained from the Arrhenius plot of the published data on Ln-1111 and AE-122 pnictides electrical resistivity data, while T * can be determined from the peak of the derivative of the resistivity with respect to temperature, dρ/dT . Both parameters are plotted on Fig 2 a and Fig 2 b as a function of the basal lattice parameter resulting in a linear correlation for all the rare earths (with the exception of La, whose doped samples also have an anomalously low superconducting transition temperature) on the Ln-1111 plot and for Ca and Sr on the AE-122 plot. Remarkably,

  found on Sm and La -1111 and Ca, Sr and Ba-122. The activation energy and the transition temperature for each pressure are now extracted from the published data, and plotted one against the other on Fig 2c and Fig 2d, each point being one different pressure. The dependences are extremely linear, i.e. E a = " C #T * , with the same slope α for each family materials but different intercept energy ε for each  compound.

  where S is the thermopower, E S is an activation energy, e the electronic charge and b other, negligible terms. The value of the activation energy E S for several Ln-1111 samples can thus be determined from the measured thermopowers through the plot on Fig 3 (a). It can now be compared to the activation energy E a , Fig 3 (b). It is clear that the difference, proportional to the polaron formation energy E P , is positive.

  materials, yielding δ 1111 ≈1.04±0.4 and δ 122 ≈1.75±0.05. These values are almost identical to the slopes α 1111 =1.16±0.1 and α 122 =1.60±0.06, obtained from Fig2c and 2d, respectively, while according to formula (1) they should be twice their value. Thus, the precedent analysis agrees qualitatively and quantitatively with experiments if the factor ½ is eliminated, i.e. if electronic transport is performed by two polarons simultaneously, in a first approximation bipolarons. This ½ factor that points towards bipolarons appears in the formulas through the relation that states that the hopping of polarons costs half their energy of formation, relation that has been recurrently time-tested[12,21].

  [29]. Solving first for T 0 ≥ T * , putting as for the Ln-1111 case u T 0 = 155K and u T * = 90K (the expected transition temperature from the ratio δ 1111 /1.75 if mean field holds), both transitions are second order and the actual transitions temperatures T 0 = 155K and T * = 145K , in agreement with measurements (Fig 4 a), i.e. due to the coupling with the TOLD the SDW transition increases in temperature. While if the SDW appears before the TOLD, i.e. T * b T 0 , putting tentatively u T 0 ~0K and u T * = 200K , as expected for Sr-122, the SDW transition is second order but the TOLD transition is now first order, as is precisely found experimentally[30], with T * = 200K and (Fig. 4 b) T 0 = 185K , very near to the observed values (the same a,a',b,c,d,d'have been used for both calculations). The order of the phase transitions is thus the immediate consequence of the expected by symmetry linearquadratic coupling of the SDW-TOLD states. A structure for the bipolaron would be nearest neighbours polarons coupled antiferromagnetically (Fig 4c), in a minimalist version of the TOLD-SDW. For Sr-122 and

Figure 1 .

 1 Figure 1. (a) Electrical resistance of a SmFeAsO sample[32] (b) Data of (a) plotted in an

Figure 2 (

 2 Figure 2 (a) Transition temperature T * to the SDW state, as determined by the peak of the

  (b) Comparison of the variation of E a to E S as a function of the basal lattice parameter, showing that the polaron formation energy is positive. (c) Schematic band diagram for pnictides. The density of states derived from the conduction has a dip corresponding to the pseudogap 2Δ* that exists above T * [20]. Two narrow polaronic bands are shown, separated by an energy 2E S , corresponding to hole or electron polarons. E P the formation energy of a polaron. (d) Levels at the Fe site for (i) a tetrahedral environment, (ii) the tetragonal high temperature structure and (iii) the low temperature orthorhombic structure 46 . The filling explains the JT effect, as the splitting of the degenerate level induced by the orthorhombic distortion causes an energy gain (ε>0), in the case of the Ln-1111 and Ba-122 compounds (for the other 122 materials the doublet and the singlet are probably inversed).

Figure 4

 4 Figure 4 (a) Temperature dependence the order parameter of the SDW (red) and the TOLD

  where W H is one half[12,21] of energy E P , and J is the transfer integral. As from the diagram on Fig 3 (c) Δ * = E S + E P , then E a = E

P + " * 2 # J.


Manuel Núñez-Regueiro

Gastón Garbarino

María Dolores Núñez-Regueiro

The relationship between the normal state Fermi liquid scattering rate and the superconducting state

Many superconductors show a low temperature electrical resistivity of Fermi liquid type ρ =AT 2 . We show empirically that there exists a relationship between A and T c when both vary under an external parameter, such as pressure. The more resistive the compound the higher the T c . Through the analysis of Landau theory of FL, we find that it is a general feature of FL, due to the fact that the scattering that is the main cause of τ is the same one that bounds the pairs that condensed at T c . We devise a method that allows the determination of the coupling constant λ, which is validated through application to 3 He-'s superfluid transitions and τ's extracted from different properties. This method works for conventional superconductors, but fails with heavy fermions.

Introduction

The standard electrical resistance of a metal is controlled by electron-phonon scattering yielding a ! = "T dependence at high temperatures and a! = "T n !,!n ~5 dependence at low temperatures.

However, in some special materials, the low temperature electrical resistivity is of the type ! = AT 2 .

It has long been attributed to electron-electron scattering (e-e-s) and is considered as the signature of a Fermi liquid (FL) behavior for the electronic spectra of the studied compound. The term A has been related to the electronic linear term of the specific heat ! of each material through the Rice- Kadowaki-Woods [1,2] relation A ! " 2 through their common dependence on the effective mass m * . The precise origin of the AT 2 term has been elucidated for certain materials: direct Coulomb scattering for ultra-pure alkali metals [3] or spin fluctuations for heavy fermion materials [4]. † Present address : European Synchrotron Radiation Facility (ESRF), 6 Rue Jules Horowitz 38043 BP 220 Grenoble # Deceased A num ber of supe r c onduc tor s of dif f e r e nt type pr e se nt the ! = AT 2 dependence above the superconducting transition at T c : heavy fermions, A ! 15 compounds, borocarbides, etc. It is natural to expect that the pre-transitional scattering is related the pairing interaction, as has been shown, e.g. for aluminum, where the ! = AT 2 has been traced down to phonon mediated e-e-s [5]. In particular, it would be interesting to study the T c !vs!A correlation. However, this can only be done properly if both properties vary simultaneously under a external parameter, e.g. pressure. A long term study of superconductors, together with the reanalysis of published data has allowed us to determine a direct relationship between the coefficient A and the superconducting transition temperature, T c , that we present on Fig. 1. It is clear from the figure that T c is a monotonous increasing function of A , thus the stronger the scattering the stronger the T c . The empirical relationship that follows from the results shown on this figure has never been reported (nor even addressed). [8]; V 3 Si (green squares)[Our data]; MgB 2 (red diamonds) [9]; UPt 3 (magenta squares) [10]; Sr 2 RuO 4 (magenta diamonds) [11]; UBe 13 (magenta dots) [12]; (TMTSF) 2 ClO 4 (brown dots) [13], (TMTSF) 2 PF 6 (brown squares) [13].

Theory

We can understand this relationship within Landau theory for Fermi liquids as follows.

Theoretical relationship between τ and T c

We reduce the inverse quasiparticle-quasiparticle scattering time and the transition temperature to the superfluid phase, to the Landau amplitude scatterings within the s-p approximation. From standard Landau FL theory [START_REF] Baym | Landau-Fermi Theory and Low Te m pe r a tur e P r oper tie s of Normal Liquid 3 He The Physics of Liquid and Solid Helium[END_REF] we obtain the inverse quasiparticle-quasiparticle scattering time ! "1 ,

! "1 = m *3 < W (#,$) > (k B T) 2 8% 4 ! 6 = m * < W (#,$) > N k F ( ) 2 (k B T) 2 8% 2 ! 2 V 2 E F (1)
Where m * is the effective mass, V the volume, N(k F ) the density of states at the Fermi level, < W (!,") > is the transition probability which describes the scattering of two quasiparticles whose momenta are related by the standard angles ! and ! , the bracket indicating the angle average through the Abrikosov-Khalatnikov angles; k B t h e B o l t z m a n n c o n s t a n t a n d ! t h e P l a n c k ' s c o n s t a n t .

Developing in Legendre polynomials within the s-p approximation [START_REF] Dy | [END_REF] we obtain for the triplet transition probability

W !! (",#) = 2$ ! A !! (",#) N(k F ) 2 ~(1+ A 0 a ) N(k F ) 2 (2)
and where we have limited the development to l 0,1 within the s-p approximation and we have neglected singlet scattering. For singlet scattering, neglecting triplet scattering, we have ! 4 $ 2A 1 ep .

(!" T 2 ) #1 ~m* k B 2 1+ A 0 a ( ) 2 4$! 3 V 2 E F % 1+ A 0 a ( ) 2 (3)
From ( 3) and ( 4) we conclude that (!T 2 ) "1 # $ %% 2 , the same for singlet scattering. Thus T c ! e "# / ($T 2 ) "1

(5)

Electrical resistivity formula

The FL resistivity of metals [18] is given by ! ee m * ne 2 " R , where n is the carrier density, m * the effective mass, e the electronic charge and ! R = number " ! . From (1) , ( 2) and ( 4) we find now that ee "

m * 2 k B 2 1+ A 0 a ( ) 2 ne 2 4#! 3 V 2 E F T 2 A m * 2 k B 2 ne 2 4 ! 3 V 2 E F # $$ 2 (6)
A similar result can be obtained for singlet scattering.

The case of Helium 3

We can test formula (5) adapting it for the most studied Fermi liquid, i.e.

3 He ; it becomes

T c / T F ** = !e "# / ($T 2 ) "1 (7)
, where T F ** is the Fermi temperature renormalized by all the interactions at each pressure. We plot T c / T F ** (P) data as a function of the thermal conductivity scattering rates [19] and fit with expression ( 7) with ! and ! as adjustable parameters (Figure 2). We can thus extract the coupling constant ! = "T 2

( ) / # . The obtained values 0.2 < ! < 0.4 are in very good agreement with theoretical calculations [20]. We must note, though, that all pressure effects other than those on ! are probably taken into account by the renormalization with T F ** (P).The application on 3 He confirms our analysis based on the idea that the pre-transitional scattering determines T c . (blue line) allows the determination of the parameter ! and the coupling constant ! ("T 2 ) #1 /$ in excellent agreement with theory [20].

Application to superconductors

Having shown the utility of expression (5), we come back to the superconductors of Figure 1. As A ! "T 2 #1

, we can now attempt an equivalent type of fit T c !e "# / A . We must bear in mind, though, that application of elementary FL to materials with complex Fermi surfaces is bound to be cumbersome. In this case other parameters that are now present besides λ in Α, may vary, as well.

Figure 3 The dependence of T c on A and the fit with expression T c .e " A (solid black) for a V 3 Si sample (Our data). The agreement of the obtained ! with published data [21] is excellent.

Figure 1

 1 Figure 1 Empirical relation between T c and the coefficient A of the quadratic temperature term for different values of an external parameter is applied, pressure unless specified otherwise. PrPt 2 B 2 C(blue squares)[6]; Y-Pd-B-C(blue dots)[7]; YNi 2 B 2 C(blue diamonds)[Our data]; Nb 3 Sn (α or e -irradiation, green dots)[8]; V 3 Si (green squares)[Our data]; MgB 2 (red diamonds)[9]; UPt 3 (magenta

  where A 33 ( ,#) is the triplet scattering amplitude and T F the Fermi temperature and l ! the Landau scattering amplitudes (we have taken A 0 s =1). A similar result, ( T 2 ) #1 $ A 1 ep P , is obtained for singlet scattering taking A l s = A l a = A l ep , as in this case the interaction does not depend on spin direction. Now, following Ref. [16], Patton and Zaringhalam [17] (PZ) estimated the transition temperature to a condensed state as a function of the Landau scattering amplitudes, T F being the Fermi temperature and ! "" the triplet coupling constant, and ! a parameter, T c 1.13!T F e 1/" ## ! "" A "" (#,$) /3cos(

Figure 2

 2 Figure 2 Superfluid transition temperature T c of 3 He normalized by T F ** (P), the Fermi temperature renormalized by all the interactions at each pressure, as a function of the inverse square root of the scattering time extracted from the thermal conductivity multiplied by the square of the temperature. Fitting with T c / T F ** = !.e "# / ($T 2 ) "1

Figure 4

 4 Figure 4The same type of fit shown for the compounds of Fig.1, presented now with each T c normalized to the fitting parameter ! and as a function of ! = A /" . The values of λ we obtain for A-15 compounds and borocarbides agree within 10% with those obtained from other methods, while those of heavy fermions are much lower than reported previously.

Si data, that allows us to obtain! and ! , and hence the coupling constant ! = A /" . It yields ! " 0.87 at ambient conditions, in excellent agreement with the value obtained from tunneling methods ! = 0.89[21]. Thus, the variation of T c and A seems to be controlled mainly by the variation of ! .

Applying the same procedure to the compounds of Fig. 1, we can obtain for each material the corresponding ! and ! . Plotting now T c / ! against ! = A / " we obtain Fig. 4. All the dispersed data of Fig. 1 collapse onto one single curve, that scales the compounds according to their respective superconducting coupling constants, derived from their resistivity coefficients Α. For heavy fermions, the variation of Α with pressure seems to be controlled by m * not ! , invalidating our method. The fact that our analysis works properly on irradiated Nb 3 Sn, suggests that it may be interesting to study the variation of T c and A in heavy fermions by using irradiation, not pressure, as defects should have a stronger effect on the scattering rate τ than on m * .


Gaston Garbarino

Amadou Sow

Pascal Lejay

André Sulpice

Pierre Toulemonde

Mohamed Mezouar

Manuel Nunez-Regueiro

M Núñez-Regueiro

High temperature superconductivity ( ! T c onset at 34K) in the

We have studied the structural and superconducting properties of FeSe -β under pressures up to using synchrotron radiation and diamond anvil cells. The bulk modulus of the tetragonal phase is , much smaller than the rest of based superconductors. At we observe a phase transition from the tetragonal to an orthorhombic symmetry. The high pressure orthorhombic phase has a higher reaching at . The discovery of superconductivity 1, , , 2 3 4 with critical temperatures between 30K and 55 K in the layered iron arsenides has induced a wide scope exploration of phases with iron in a similar environment in the hope of finding new superconducting compounds and going beyond these high superconducting transition temperatures ( ). In particular, the report c T 5 of superconductivity in the structure of is tantalizing, as strong pressure effects at relatively low pressures seem PbO FeSe 6, , 7 8 to strongly increase c T up to around for the onset of the transition. On the other hand, partial replacement with tellurium also noticeably increases 9 K 25 c T . However, superconductivity seems to coexist with magnetically ordered states accompanied by lattice distortions 10 that are much more stable than superconductivity 11 . In this letter, we have studied the evolution of both superconductivity and structure under pressure.

We find that in our samples an orthorhombic high pressure phase develops above that presents superconductivity above 34K. cullet diamonds. The transmitting media used was Helium and the pressure was determined using the equation state of copper 12 , introduced next to the sample.

The structural studies have been done at ambient temperature. The diffraction patterns were collected with a CCD camera and the intensity vs. patterns were obtained using the fit2d software Theta 2 13 . A complete Rietveld refinement was done with the GSAS-EXPGUI package 14 , all the estimated standard deviations were multiplied by a factor of 5 due to the underestimation of the GSAS calculation 15 .

The electrical resistance measurements were performed using a Keithley 220 source meter and a Keithley 2182 nanovoltmeter. Pressure measurements, (between and ), were done in a sintered diamond Bridgman anvil apparatus using a pyrophillite gasket and two steatite disks as the pressure medium

2 -22GPa K 2 . 4
K 300 16 .

The magnetization (M) data was measured in the so-called zero field cooling process.

The sample was cooled down to 2K with in a zero field. Then, the 50Oe magnetic field was applied and M was measured at increasing temperature up to room temperature.

From the diffraction data at ambient pressure condition, we refined the lattice parameters, peak profile, occupancy and position of the Se atom in z ) , , ( Pbnm GPa 5 . 8 18 .

By inspection of the lattice parameters of the tetragonal phase, determined by

Rieteveld refinement, we observe a smooth variation over the full range to .

The lattice parameters and the volume V of the From a fit of the cell volume, V , with pressure, P up to , with a third order Murnaghan Equation of State (EoS)

GPa 12 ' 0 1 0 ' 0 0 1 K K P K V V - ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + =
, we obtained a bulk modulus ( )GPa 3 (c)).

Therefore, the separation between layers (labeled " " in fig. 3(c))

decreases abruptly, reaching a value below at 12GPa. In contrast, the bond length ( in fig. 3(c It is clear that the structural phase transition at 12.5GPa induces an abrupt change of the superconducting temperature pressure dependence. Thus, the orthorhombic phase has a higher that reaches its maximum value of 34K at the highest applied pressure. In contrast, the c T * T transition shows a monotonic increase up to 15GPa followed by a reduction that could be fitted with a quadratic polynomial.

For the low pressure variation ( GPa P 12 < ) of and , we obtained 1.4K/GPa and 0.8K/GPa, respectively. These values are smaller that the ones reported in Ref. During the preparation process of this publication, two other papers 22,23 To try to elucidate other reason for the large differences we discuss the possible effect of the pressure transmitting media. As it has been mentioned before, the structural study was done using Helium as media. Taking into account the small atomic radii of the noble gas, one can speculate about He intercalation during the compression process considering the layered crystal structure of the . Three important aspects must be taken into account in order to discard any effect of the pressure media. First, the resistance experiment was done using solid steatite as media where no possible intercalation is expected and even there is an excellent agreement in the determination of the critical pressure of the T-O transformation from the kink in the resistance at

Se Fe Se

--Thus, we believe that the mentioned discrepancies can be assigned to a small difference in Se stoichiometry that could reduce the superconducting critical temperature at ambient pressure of our sample, and induce a different structural and superconducting behavior under pressure.

In summary, we have studied the structural and superconducting properties of under pressures up to using synchrotron radiation X ray diffraction and FeSe GPa diamond anvil cells. We show that under compression, transforms from the original tetragonal structure to an orthorhombic one that has a higher superconducting temperature, . The data correspond to 0, 0.

  @esrf.fr 74.70.-b, 61.50.Ks

GPa 12 Polycrystalline

 12 samples were synthesized from high quality starting materials: Fe and Se in molar ration of . The reactants were weighted, mixed and homogenized in an agate mortar in a dry box under purified argon atmosphere. The mixture was packed and sealed under vacuum in a quartz tube and calcined at during 48h with intermediate grindings. The polycrystalline sample was checked using X-ray powder diffraction technique. The pattern was indexed according to the tetragonal with space group. Small peaks of the hexagonal were observed as an impurity phase. NiAsThe angle dispersive X-ray diffraction studies on powder samples were performed at the ID27 high-pressure beamline of the European Synchrotron Radiation Facility using monochromatic radiation ( ) and diamond anvil cells with

  a)). From this results, and considering the study presented inRef 17 we can conclude that our sample correspond to an stoichiometric composition , that is consistent with the Se occupancy refined from the ambient pressure X ray data of 1(a) we show the X-ray diffraction pattern and the Rietveld refinement at 6.6GPa. The refinement was done considering both the tetragonal FeSe -The pressure effects on the diffraction patterns can be observed in fig.1 (b). Clearly, at 12.5GPa there is a phase transition from a tetragonal towards an orthorhombic (T-O) phase. Although it was not straightforward to determine the space group of this phase, considering group-subgroup operation, we can propose a structure of the type. It is also important to mention that we also observed the phase transition in the hexagonal phase at already reported

  in the case of LaFeAsO19 and 0.1%, 13% and 15% in the case of LiFeAs20 , respectively. This reduction may explain the low critical pressure of the structural phase transition.The pressure evolution of the lattice parameters and , the normalized ratio and the volume V of the tetragonal phase, are presented in fig.2(a) and (b), respectively. The ratio decreases down to at meaning a larger compression of the structure along the stacking direction of the layers compared with the basal plane and it is consistent with the higher atom density in the plane.

6 '

 6 K 0 =. This is the lowest value reported up to 0 K now in the iron based superconductors family. Such a small value can explain the low critical pressure for the T-O transformation. A similar value for the bulk modulus was obtained for this compound in recent high pressure neutron diffraction the magnetic measurement at ambient pressure, we can clearly observe the existence of two anomalies. The first at 125K (named * T ) can be associated with the spin density wave transition, while the second one at 7K evidences the appearance of the superconductivity (see fig. 3 (a)). In the same figure the temperature dependence of the resistance at is presented, where both the anomaly at GPa 6 * T and the superconductivity are marked by an arrow. In the fig. 3 (b) the temperature dependence of the normalized resistance is shown for various applied pressures up to 22GPa. The pressure dependence of the resistance at 50K (inset of Fig. 3 (a)) shows a kink at 13GPa. This anomaly can be associated to the T-O phase transition determined from the high pressure diffraction studies. From the Rietveld refinement of X-ray data, we obtained the pressure dependence of the characteristics distances between and atoms (see fig. 3 (c)) and the angles (see fig. 3 (d)). The Se height in the structure does not show an evident variation while the pressure increases; it remains fixed at r o m the basal plane. The interlayer

. 4 .

 4 )) and the thickness of the layers ( in fig.3(c)) show a slight decrease at low pressure (P<6GPa) followed by a constant behavior up to 12GPa. The pressure are similar to the ones obtained in Ref 10 and correspond to a deviation from the ideal value for the non-distorted tetrahedron, . For pressure below 1GPa, the difference between the two angles increases rapidly inducing a bigger distortion in the structure, and then it remains constant up to 6GPa. Further increase in pressure develops again the distortion of the structure. We also present in this figure with two different background colors the stability pressure range of the tetragonal and orthorhombic phase.

  /GPa) and Ref. 8 (5K/GPa).

FeSe50K,

  and in the pressure dependence of the superconducting critical temperature. Second, the T-O phase transition was completely reversible during decompression in the diffraction study. Finally, the fact that the neutron diffraction results and the data presented in Ref. 23 (where Daphne TM oil was used as pressure media) show the same bulk modulus helps discarding the He intercalation hypothesis. Using this three arguments we can also discard any oxygen doping or moisture effect on the sample, considering that in this case the cell parameters would be increased and the drastically modified. The measurements in Ref. and 23 were performed using hydrostatic conditions, no media and quasihydrostatic (NaCl) conditions, respectively. While in our case, solid quasihydrostatic environment (steatite) was used. It is possible that hydrostatic compression may be more effective in compressing the parameter, but our structural measurements are hydrostatic and the T-O transition in both of our measurements, hydrostatic and non-hydrostatic, coincides. a Finally, from our structural data, we show that the interlayer distance shows more important pressure dependence that the one reported in Ref angles and the Se height (not shown) show also a different behavior with pressure.

FeSe 3 /

 3 Figure1: (color online) (a) X-ray synchrotron radiation diffraction pattern of the

FeSe

Figure 2 :Figure 3 :

 23 Figure 2: (color online) (a) Evolution of the lattice parameters and the

Figure 4 :

 4 Figure 4: (color online) Evolution of the transition temperatures as a function of


Florian Brandner
email: florian.brandner@ensta-paristech.fr

Alexander Jordan

Subgraph-Based Refinement of Worst-Case Execution Time Bounds

As real-time systems increase in complexity to provide more and more functionality and perform more demanding computations, the problem of statically analyzing the Worst-Case Execution Time bound (WCET) of realtime programs is becoming more and more time-consuming and imprecise.

The problem stems from the fact that with increasing program size also the number of potentially relevant program and hardware states to be considered during the WCET analysis increases. However, only a relatively small portion of the program actually contributes to the final WCET bound. Large parts of the program are thus irrelevant and are analyzed in vain. In the best case this only leads to increased analysis time. Very often, however, the analysis of irrelevant program parts interferes with the analysis of those program parts that turn out to be relevant.

We explore a novel technique based on graph pruning that promises to reduce the analysis overhead and, at the same time, increase the analysis' precision. The basic idea is to eliminate those program parts from the analysis problem that are known to be irrelevant for the final WCET bound. This reduces the analysis overhead, since only a subset of the program and hardware states have to be tracked. Consequently, more aggressive analysis techniques can be applied to the smaller problem, effectively reducing the overestimation of the WCET. As a side-effect, interference from irrelevant program parts are eliminated, e.g., on addresses of memory accesses, on loop bounds, or on the cache or processor state.

First experiments using a commercial WCET analysis tool show that our approach is feasible in practice and leads to reductions of up to 6% when a standard IPET approach is used for the analysis.

Introduction

Foremost size and complexity of software are causing the analysis overhead to grow rapidly, as the number of potential states of the program under analysis increases. For WCET analysis this effect is amplified since in order to arrive at a safe WCET bound, hardware states need to be considered as well, adding to the number of potential software states. Even when only small portions of a complex software program are relevant for the final WCET estimation, the analysis, has to account for all of the program's code to derive a safe bound. Except for trivial analysis problems, this inevitably reduces the precision of the WCET analysis, as irrelevant code parts interfere with the analysis of relevant code parts and lead to unnecessary overestimation of the determined WCET bound compared to the actual worst-case behavior.

Previous work is able to eliminate instructions irrelevant to flow analysis (program slicing) and refine the WCET bound by identifying infeasible paths (see Section 5 for details). With Iterative Graph Pruning (IGP), described in detail in the following sections, we also aim to limit WCET analysis to relevant parts of a program, but do so on the lower CFG-level. Based on criticality, basic blocks are grouped into sets according to the length of their respective paths. The sets are then processed iteratively by decreasing path length. During each iteration a subgraph of the original CFG is formed by unifying the subgraph of the previous iteration with the basic blocks from the currently considered set. A potentially more advanced WCET analysis is then applied to the program represented by the new subgraph. The algorithm terminates, with a possibly refined WCET estimate, as soon as a safe bound, valid for the original program, has been reached.

The benefits from this approach are that (1) the analysis problems defined by the subgraphs at each iteration are much smaller than the original analysis problem. This promises to reduce the analysis overhead, while still providing tight bounds. Furthermore, [START_REF] Brandner | Static profiling of the worstcase in real-time programs[END_REF] processing the sets of basic blocks according to their decreasing path lengths, eliminates interference from other basic blocks, whose longest paths are known to be shorter. This improves the precision of the WCET analysis precisely for those code parts of the real-time program that impact the WCET estimate the most.

The main contributions of this paper are as follows:

• We present a novel WCET analysis technique based on graph pruning that focuses the analysis effort on relevant code parts of the real-time program.

• Due to reduced analysis overhead, more elaborate analysis techniques can be applied to the smaller sub-programs, leading to improved precision.

• We evaluate our approach using a commercial off-the-shelf WCET analysis tool and demonstrate considerable improvements of WCET bounds.

The remainder of this paper is structured as follows. We first give some background and motivation in Section 2. We then describe our novel graph pruning technique and follow its main steps on a realistic example in Section 3. Section 4 presents a detailed evaluation of our approach on well-established real-time benchmarks and a realistic processor architecture. Related work is covered in Section 5 before concluding in Section 6.

Background and Motivation

This section covers some basic definitions of control-flow graphs, paths, and WCET analysis, followed by a brief discussion of recent findings motivating this work.

Background

We assume that static WCET analysis proceeds in two phases as proposed by Theiling et al. [START_REF] Theiling | Fast and precise wcet prediction by separated cache and path analyses[END_REF]. Local worst-case execution times of individual basic blocks and control-flow edges are computed first, followed by a longest path search over a weighted CFG, where the weights are given by the local worst-case execution times.

Weighted Control-Flow Graph A weighted Control-Flow Graph (CFG) is a tuple G = (V, E, r, t, W), where V is a set of nodes representing basic blocks that are connected by control-flow edges in E. We assume that every CFG contains a root node r and sink node t. The function W : V ∪ E → R associates the basic blocks and edges with a weight.

Longest Path An ordered sequence of nodes (v 1 , . . . , v n ) such that for 0 < i < n all edges (v i , v i+1 ) are in E, is called a path. The length of a path |p| is given by the sum of all its node and edge weights:

0<i≤n W(v i ) + 0<i<n W((v i , v i+1 )).
A path p is a longest path, when there exists no other path q such that |p| < |q|.

Local Execution Times The weight of individual CFG nodes and edges is usually computed using program analysis techniques that derive information on potential program and processor states at all relevant program points. This information is then combined to compute an upper bound of the local execution time of each basic block and CFG edge.

Longest Path Search From the local execution times a weighted CFG is constructed and a longest path search is performed to find the global WCET. This problem can be solved via Integer Linear Programming (ILP) using the Implicit Path Enumeration Technique (IPET) [START_REF] Yau-Tsun | Performance analysis of embedded software using implicit path enumeration[END_REF][START_REF] Puschner | Computing maximum task execution times -a graph-based approach[END_REF]. Here, ILP variables represent execution counts of basic blocks and constraints define legal execution paths in the CFG. A standard ILP solver then determines the WCET. Alternatively dynamic programming [START_REF] Thomas | Introduction to Algorithms[END_REF] allows to directly compute the longest path on acyclic CFGs. Cyclic CFGs can be handled by applying this technique to acyclic subgraphs [START_REF] Stappert | Efficient longest executable path search for programs with complex flows and pipeline effects[END_REF].

Worst-Case Execution Path A Worst-Case Execution Path (WCEP) is a longest path in the weighted CFG as computed by the longest path search.

Worst-Case Execution Time The WCET of a program corresponds to the length of the WCEP as computed by the longest path search. It is generally not feasible to compute the actual WCET, we thus usually seek a (tight) estimation, the WCET bound. For the purpose of brevity, we will use the term WCET to refer to the WCET bound.

Motivation

Recent work [START_REF] Brandner | Static profiling of the worstcase in real-time programs[END_REF][START_REF] Brandner | Criticality: Static profiling for real-time programs[END_REF] proposes a technique to profile the worst-case in real-time programs using static program analysis. The authors define the Criticality metric for each basic However, the metric is not only interesting for program optimization. In particular the distribution of the Criticality values in a real-time program is highly interesting. Table 1 and 2 show profiling results of several WCET analysis problems for the Debie1 and PapaBench real-time programs. From the columns I 0 , ..., I 5 , the number of basic blocks in six predefined Criticality intervals can be seen. The variation of block distributions hints at an underlying difference of program structure with regard to WCET-critical code. A surprisingly large number of basic blocks is relatively unimportant with a Criticality value below 0.8. Only 13% of the basic blocks of the debie-4a benchmark, for instance, are highly critical. Over all analysis problems of Debie1 only 54% of the basic blocks have a Criticality above 0.80. Considering all analysis problems, in the mean 67% of the basic blocks are highly critical, i.e., have a Criticality above 0.8.

* Intervals: 0 ≤ I 0 < 0.25 < I 1 < 0.5 < I 2 < 0.75 < I 3 < 0.9 < I 4 < 0.99 < I 5 ≤ 1
* Intervals: 0 ≤ I 0 < 0.25 < I 1 < 0.5 < I 2 < 0.75 < I 3 < 0.9 < I 4 < 0.99 < I 5 ≤ 1
Considering this observation, one could ask whether it would be possible to improve the precision and computation time of a WCET analysis by excluding the uncritical code parts from the analysis? This is precisely the goal of this work. We exclude uncritical code parts by pruning the control-flow graph and iteratively deriving a refined, but still provably correct, WCET bound. A detailed description of this approach follows in the next section.

Algorithm

In a nutshell, iterative graph pruning (IGP), presented as pseudo code in Algorithm 1, performs WCET analysis by iteratively merging a sequence of basic block sets (S i ), terminating when an upper bound (ub wcet ) is found to be a safe bound for the input program.

The blocks are then inserted into sets S i based on the path length. The respective path length of a set can later be retrieved by longestpath(S i ). The sets S i are generated by computing the longest path going through every basic block within G [START_REF] Brandner | Static profiling of the worstcase in real-time programs[END_REF][START_REF] Brandner | Criticality: Static profiling for real-time programs[END_REF]. At every iteration i, the vertex-induced subgraph G ′ is created from the union of the i first (and most critical) sets S i (l. 7 -l. 8). G ′ is then targeted by a full WCET analysis run (WCEToverAny l. 13), which entails abstract interpretation on the program's subgraph G ′ to generate the weighting function W ′ , followed by a longest path search. WCEToverAny, additionally, forces the longest path search to only consider those paths passing through blocks in the current S i . All other paths in G ′ are uninteresting, since these paths have already been bounded in the previous iterations. Note that G ′ may not contain any such path that is feasible. WCEToverAny then returns 0 and the current upper bound remains unchanged. If, at the end of an iteration, the current upper bound (ub wcet ) is less than the just computed bound (WCET i ), it needs to be updated (l. 10).

The algorithm terminates at the latest when all sets have been considered (i.e., V ′ = V and G ′ is the same as the graph of the original program) or before when the termination

Let V ′ ← S 1 ∪ • • • ∪ S i , E ′ ← E ∩ V ′ × V ′ in 8: G ′ ← (V ′ , E ′ , r , t) 9:
WCET i ← CalcPrunedWCET(G ′ , S i , ub wcet ) return WCEToverAny(G ′ , S i ) condition (l. 4) is met. The latter case occurs when the remaining longest path induced by the remaining S i s is shorter than the current WCET bound ub wcet . We will prove that ub wcet is a valid bound for G in the next section.

Example 1. Consider the CFG shown in Figure 1, where weights are shown for each basic block along with the longest paths passing through the respective blocks. Furthermore, assume that the number of loop iterations at BB4 depends on a variable x either assigned to 10 in BB1 or 7 in BB2.

A first, unmodified WCET analysis discovers both assignments to x. Thus, it derives a loop bound of 10 iterations for BB4. The resulting longest path (p 1 ) has length 60 and covers r, BB0, BB2, BB4, BB5 and t. These blocks are thus assigned to the basic block set S 0 . The second longest path passing through a node not covered by p 1 is p 2 , with length 56. Since all blocks on p 1 are already assigned to S 0 , the only new block of p 2 is assigned to S 1 = {BB1}. The same applies to path p 3 and block set S 3 = {BB3}.

Our Algorithm starts by reanalyzing subgraph G 1 induced by S 0 shown by Figure 2. The analysis now discovers that there is only a single assignment to x, limiting the number of loop iterations at BB4 to 7. In addition, a more precise estimation of the local execution time within the loop is derived, i.e., W(BB4) is now 4 instead of 5. The initial length of 60 for p 1 alone was heavily overestimated, since the longest path in G 1 is much shorter. This results in an upper bound ub wcet of 38. The algorithm continues to iterate at this point since the path length associated with S 1 is longer than the current upper bound. The second iteration leads to the construction of G 2 induced by S 0 ∪ S 1 (see Figure 2 new WCET analysis run is forced to consider only those paths passing through BB1 and finds a loop bound of 10 iterations. This results in an upper bound ub wcet of 56. Since the upper bound now represents a path longer than any that could be uncovered by including the next block set S 3 , the algorithm terminates with a more precise WCET bound of 56 instead of the initial 60.

). A r BB0 W(BB0) = 2 BB1 W(BB1) = 3 BB2 W(BB2) = 7 BB3 W(BB3) = 1 BB4 W(BB4) = 5 BB5 W(BB5) = 1 t |p 1 | = 60 |p 2 | = 56 |p 3 | = 7

Correctness

To show the correctness of our approach, we have to consider the impact of graph pruning on the typical phases of a WCET analysis run. We assume, without loss of generality, that WCET analysis is performed in two phases [START_REF] Theiling | Fast and precise wcet prediction by separated cache and path analyses[END_REF]. A first phase, based on abstract interpretation [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF], delivers local worst-case execution times for each basic block. In the second phase, a longest path search [START_REF] Yau-Tsun | Performance analysis of embedded software using implicit path enumeration[END_REF][START_REF] Puschner | Computing maximum task execution times -a graph-based approach[END_REF] is performed on a weighted CFG, computed from these local execution times.

In our approach, abstract interpretation is applied to a subgraph G ′ of the original CFG G of the input program. In order to show correctness we thus have to investigate some properties of the subgraph G ′ .

r BB0 W(BB0) = 2 BB2 W(BB2) = 7 BB4 W(BB4) = 4 BB5 W(BB5) = 1 t (a) 1st iteration r BB0 W(BB0) = 2 BB1 W(BB1) = 3 BB2 BB4 W(BB4) = 5 BB5 W(BB5) = 1 t (b) 2nd iteration
Lemma 1. A subgraph G ′ = (V ′ , E ′ , r, t) constructed by Algorithm 1 is connected, i.e., for every CFG node v ′ ∈ V ′ a path from r to t, passing through v ′ , exists.

Proof. This follows immediately from the way subgraphs are constructed. Remember that the blocks in the subgraph G ′ of the m-th iteration are computed by unifying all the basic block sets S i , i ∈ {0...m}, whose path lengths are longer than the path length associated with S m , i.e., V ′ = i∈0..m S i . Assume G ′ is not connected, i.e., a CFG node v ′ exists that is not reachable from the root node r in G ′ . Since v ′ ∈ V ′ it follows that a corresponding path p = (r, ..., n ′ , ..., t) has to exists in the original graph G. The length of this path corresponds to the path length associated with S m . As G ′ is not connected, at least one node of p is not in V ′ . However, this is impossible, since the existence of p implies that this node either is in S m or another set S k , k < m. The subgraph G ′ is thus connected. Lemma 2. Abstract interpretation applied to a subgraph G ′ delivers correct results with respect to the potential execution paths through G ′ .

Proof (sketch). A sound analysis based on abstract interpretation delivers sound results with regard to potential executions of a program, e.g., represented by its CFG G. When applying the same analysis to a subgraph G ′ , the set of potential executions is reduced (excluding those executions that do not lead to the sink node t). Since the analysis is sound, this approximation trivially remains sound with regard to the executions represented by G ′ . Note, however, that the analysis result is not guaranteed to be sound with regard to all executions of the original program.

The previous two lemmas ensure that, independent of the concrete analysis performed, the local execution times obtained by abstract interpretation in the WCET analysis tool are sound with respect to a subgraph G ′ . It remains to show that the WCET bound computed during the longest path search by Algorithm 1 is a safe bound.

Lemma 3. The worst-case execution time bound computed by Algorithm 1 for a subgraph G ′ is safe.

Proof. Consider the subgraph G ′ and its basic block set S m of the m-th iteration as well as the subgraph G ′′ , with its bound WCET(G ′′ ), of the previous iteration.

First, assume that the longest path p through G ′ represents a valid path in G ′′ , i.e., p does not contain any node in S m . In relation to the previous iteration, the current WCET estimate for p might increase, due to overestimation of the local worst-case execution times, i.e. WCET(G ′′ ) ≤ WCET(G ′ ). However, irrespective of the WCET computed for G ′ , the bound established by the previous iteration for G ′′ still holds. Paths of this structure are thus uninteresting, as the length of all paths in G ′′ has been bounded by the previous iteration. It remains to bound those paths in G ′ that do not have a corresponding path in G ′′ . The longest path search thus only needs to consider paths containing at least one node in S m .

Three cases for the longest path p need to be considered:

1. |p| > WCET(G ′′ ):
Since |p| is longer than the previously established WCET bound, it follows that WCET(G ′ ) = |p|.

|p| ≤ WCET(G ′′ ):

As the length of p is not longer than the previously established bound, it follows that WCET(G ′ ) = WCET(G ′′ ). The longest path through G ′′ also represents the longest path through G ′ , ignoring any additional overestimation caused by blocks in S m .

3. No feasible path containing a block in S m exists: This case happens when the abstract interpretation finds that no execution in G ′ exists that passes through a block in S m , i.e., none of the conditions of the branches leading to a block in S m can be satisfied. It follows that WCET(G ′ ) = WCET(G ′′ ).

Note that paths over these blocks might become feasible in later iterations, e.g., when code making the, yet unsatisfiable, conditions satisfiable is added.

Using induction, we can finally prove that Algorithm 1 delivers safe WCET bounds for all subgraphs considered during the iterative processing. Proof. This follows immediately from the previous lemmas and the termination condition of the algorithm.

The lemmas prove that applying abstract interpretation on subgraphs is sound and that the algorithm computes safe bounds with respect to the subgraphs considered during the iterative processing.

It remains to show that no other paths exist, which could be longer than the WCET bound delivered by the last iteration. This is guaranteed by the order in which the sets of blocks are processed and the termination condition (Algorithm 1, l. 4). Together these ensure that all basic blocks not yet considered by the iterative refinement can only induce paths that are shorter than the computed bound.

Complexity

The number of sets S i is an upper bound on the iterations that will be performed by IGP. The former is again bounded by the number of basic blocks in the input program. Since its iterations are linear in the number of blocks, IGP is dominated by the complexity of the WCET analysis, i.e., abstract interpretation and longest path search.

The sets S i , which are assumed as input in Algorithm 1, can be efficiently computed using the criticality algorithms [START_REF] Brandner | Static profiling of the worstcase in real-time programs[END_REF][START_REF] Brandner | Criticality: Static profiling for real-time programs[END_REF]. This may be performed either during a preprocessing step, or on demand, while the graph pruning algorithm iterates.

Algorithm 2 WCET computation function CalcPrunedWCET using two-stage analysis

Require: G ′ = (V ′ , E ′ , r, t) . . . A CFG.

S i . . . The set of newly added blocks. ub wcet . . . The current upper bound of the WCET.

1: WCET i ← WCEToverAnyFast(G ′ , S i ) 2: if WCET i > ub wcet then 3: WCET ′ i ← WCEToverAnyPrecise(G ′ , S i ) 4:
return WCET ′ i 5: return WCET i

Algorithm Variants

It may be the case that the WCET analysis tool targeted by graph pruning, can be configured for different levels of precision. This usually involves a trade-off between tightness (precision) of the WCET bound and longer analysis runtime. IGP can be used to incorporate analyses with different precision. Running the higher-precision analysis on a previously pruned graph would be a straight-forward way of further improving the WCET bound. But Algorithm 1 can also be modified to make use of multiple levels of precision directly. To do this, we replace the CalcPrunedWCET function in Algorithm 1 with the variant given in Algorithm 2. This algorithm performs a second, more precise WCET analysis (WCEToverAnyPrecise) to lower the estimate of WCET i for the current graph G ′ , whenever the imprecise analysis (WCEToverAnyFast) would increase the overall WCET bound. Another valid, but trivial way of incorporating a higher-precision analysis into graph pruning, would be to run WCEToverAnyPrecise on the pruned subgraph exactly once after the iterative processing. This would reduce the computational overhead and further lower the WCET bound (down to the path length of the next block set). One could even avoid the iterative processing entirely, by heuristically constructing a subgraph and applying the precise analysis to this subgraph. This would foremost reduce the computational overhead and leave the burden of reducing overestimation on the precise WCET analysis.

Evaluation

We start by giving a complete example of running iterative graph pruning on the first problem from the Debie1 benchmarks, which has no loops and 83 basic blocks. We then extend our evaluation to a number of WCET benchmarks using standard Iterative Graph Pruning (IGP) and its two-stage variant (IGP-TS).

Case Study: debie-1

We start by analyzing the original program represented by its CFG G. This yields a first valid global WCET bound in cycles (denoted by WCET(G)).

Set S i longestpath(S i ) At the same time we can perform a basic-block-level WCET profiling according to the definition of criticality. This yields, for every block b in the CFG G, the maximum length (a value in the range [0, WCET(G)]) of all paths going through b. Blocks with a value close to the global WCET are considered critical, while those close to 0 are uncritical. Based on their longest paths, we now insert blocks into several sets, so that blocks with the same path length end up in the same set. In our example 15 such sets exist, their path length (longestpath(S i )) and cardinality is given in Table 3.

S
The pruning algorithm kicks off with a WCET analysis, but this time considers only the blocks on the global WCEP, i.e., the blocks in S 0 . Using these blocks a vertex-induced subgraph G 1 is created and its WCET bound is analyzed.

Iteration 1: G 1 = S 0 WCET(G 1 ) = 334
WCET(G 1 ) is drastically lower than the original WCET, even though all blocks of the original WCEP are contained in G 1 . Using abstract interpretation the WCET tool has derived that the path is actually infeasible, i.e., no legal execution for the path exists. It is necessary to add more blocks back to the program at this stage. And since we suspect that those blocks with longer paths have a larger impact on the attainable WCET bound, we select the most critical blocks available, namely S 1 .

Iteration 2: G 2 = G 1 ∪ S 1 WCET(G 2 ) = 334 Iteration 3: G 3 = G 2 ∪ S 2 WCET(G 3 ) = 334 Iteration 4: G 4 = G 3 ∪ S 3 WCET(G 4 ) = 1423
Adding S 1 to the graph did in fact not change the current WCET bound, neither did S 2 . But after adding S 3 , a considerably longer path becomes feasible and our current WCET bound jumps to 1423 cycles. Let us pause for a moment and consider what we have done so far. G 4 contains the most critical code (S 0 ∪ • • • ∪ S 3 ), it contains 42 basic blocks (compared to 80 for the whole program). Blocks from eleven sets have not yet been added and we have a current bound of WCET(G 4 ) < WCET(G). Is this already a valid WCET bound for the original problem? No, looking at the remaining sets, we can see there are still blocks in sets S 4 , . . . , S 8 , which may be part of a longer path in an extended subgraph, i.e., longestpath(S i ) ≥ 1423, 4 ≤ i ≤ 8. With this in mind, we resume adding blocks with S 4 . Iteration 5:

G 5 = G 4 ∪ S 4 WCET(G 5 ) = 1525 Iteration 6: G 6 = G 5 ∪ S 5 WCET(G 6 ) = 1525 Iteration 7: G 7 = G 6 ∪ S 6 WCET(G 7 ) = 1525
When we are about to add set S 7 , we notice that in the worst case, it would uncover a path with length 1472. Since the WCET bound changed again in iteration 5, this is below the current value of 1525 and thus would have no impact. This signals termination for our algorithm. At this point, blocks from all sets are either already part of the current graph, or do not contain blocks which could enable a path longer than 1525 cycles. Our result is the pruned graph G 7 , which is a WCET-bound-maintaining subgraph of the original program. By using this graph, we have reduced the initial WCET bound of the analysis by 96 cycles (∼ 6%).

Setup for Experiments

We evaluate our approach using the commercial WCET analysis tool aiT (a3 version 12.10i) and well-establisheded WCET benchmarks: The Mälardalen benchmark suite1 , Debie1 [START_REF] Holsti | Using a worst-case executiontime tool for real-time verification of the DEBIE software[END_REF] (version e) and PapaBench [START_REF] Nemer | Papabench: A free real-time benchmark[END_REF] (version 0.4). The analysis problems for the latter two are taken from the WCET Tool Challenge 2011.

The prototype implementation of graph pruning that we use for this evaluation, treats the WCET analysis tool as a black-box and thus works with an unmodified version of aiT. The graph pruning is realized through scripting and the AIS annotations (IS NEVER EXECUTED and FLOW). This means that due to our setup, all information computed by an iteration is discarded and not reused by the following iteration. Thus, any analysis runtime results would be dramatically increased. We discuss this shortcoming of our evaluation in Section 4.5).

We apply the two graph pruning variants to an overall of 37 analysis problems and compare the attainable WCET bound with the original result of aiT. The first variant (IGP), performs iterative graph pruning using standard IPET (Algorithm 1). The second variant (IGP-TS), uses the two-stage WCET computation (Algorithm 1 with the extension in Algorithm 2). Here, the standard computation is potentially refined by a second, more precise, but also more expensive, WCET analysis using aiT's prediction file technique [START_REF] Stein | ILP-based Path Analysis on Abstract Pipeline State Graphs[END_REF].

We additionally examine properties of the analysis problem that have a direct influence on overestimation. These are (1) hardware splits, a measure for the amount of dupli-

Iterative Graph Pruning

Table 4 summarizes the WCET bound improvement and aggregates it by benchmark suite. The selected Mälardalen programs, especially the ones representing algorithmic cores with almost single-path execution behavior, not surprisingly do not benefit from graph pruning. Their WCET bound improvement is 2% at best. However, the larger application-like programs, Debie1 and PapaBench, benefit from graph pruning and some of their analysis problems have their WCET bound reduced significantly. When we look at f1a from PapaBench in detail, we can see in Figure 3 that within the first 20 iterations, the upper bound (ub wcet ) leaps to a level close to its final value. At this point, the most critical basic block sets have been added to the subgraph and WCET analysis returned a good candidate for the actual global WCEP.

Step sizes subsequently decrease and from iteration 35 on, the upper bound (ub wcet ) roughly holds while more blocks are added to the IGP subgraph (see Figure 4). Another group of problem instances does not exhibit properties that are exploitable by graph pruning. These can be identified in Table 5 by their low number of iterations: after one or two iterations, IGP terminates since all (feasible) blocks are either on the global WCEP, or there is no interference between WCET-critical and unrelated code.

There is also a third class of benchmark problems, which exhibits a high number of iterations without a significant improvement of the WCET bound. Studying the most severe cases (problems a2a and a2b from PapaBench), we have found that almost all of the WCEPs found in subgraphs are infeasible on their own (i.e., their feasibility depends on blocks in other block sets). This is likely caused by a particular program structure and the WCET analysis failing to exclude infeasible paths from the longest path search (flow facts). For all non-trivial benchmarks (two IGP iterations or more), we see that the minimal (and average) reduction of hardware splits is high (see Figure 5). Average subgraph sizes (Figure 6) are likewise significantly smaller than their originals. This tells us that overestimation is being effectively addressed by IGP. At the same time it can benefit from analysis problems, which are roughly half the original size. In Table 5 we present the detailed results from graph pruning using the IGP algorithm. It contains the number of iterations in column "Iter.", the number of unique WCET paths encountered in column "|P|", and a comparison of graph sizes before and after pruning in the last two columns. Note that the number of infeasible blocks is contained in |V | and will always be pruned. IGP improves WCET bounds up to 6% compared to aiT's result on the original program. The average improvement among non-trivial benchmark problems is 2%.

WCET (cycles)

Two-stage Iterative Graph Pruning

To evaluate the two-stage approach of iterative graph pruning (IGP-TS), we make use of the prediction file (PF) based IPET solver in aiT as a second stage analysis (i.e., for the WCEToverAnyPrecise invocation in Algorithm 2). When performing PF-based WCET computation, the timing information during longest path search is not restricted to a single WCET for each basic block, but may encompass multiple architectural states [START_REF] Stein | ILP-based Path Analysis on Abstract Pipeline State Graphs[END_REF]. Tightening WCET bounds in this way comes at the cost of -depending on program size-much larger ILP problems and thus time needed for solving. (Note that resource demand, i.e., memory, for the larger problems of papabench on a related out-of-order PowerPC architecture is bordering on infeasibility.) Fast WCET analysis remains unchanged with regard to IGP.

The WCET bound improvement of IGP-TS, compared to the PF-enabled analysis as a baseline, behaves similar to that of IGP. Benchmark problems, for which the WCET bound was improved by IGP, also improve by IGP-TS, but the effect is less pronounced (see Table 4). We thus conclude that our approach is profitable even compared to a state-of-the-art WCET analysis tool using its most sophisticated analysis technique. How its profitability increases inversely proportional to the use of mechanisms that prevent overestimation.

The reduction of hardware splits and graph sizes measured over all iterations also behaves similar (compare IGP and IGP-TS in Figures 5 and6), although it fails to "cut off" sources of overestimation in the same was as IGP does. Furthermore, as we expected, the number of unique WCEPs found by IGP-TS is higher (see |P| in Table 5 versus Table 6). This is due to the more precise analysis being used. For the same reason, we can see an increase in the number of iterations.

Discussion

We have evaluated graph pruning using a state-of-the-art, commercial WCET tool. aiT uses powerful abstract interpretation and is able to produce good WCET bounds on its own. Even so, graph pruning can eliminate sources of overestimation and significantly tighten the WCET bound. While we can configure aiT to analyze subgraphs and extract all results we need from it, our setup is only suitable as a proof-of-concept. The analysis tool is treated as a block box, which leads to needless overhead that could be avoided. We thus do not present detailed measurements of the analysis time here. However, even with these short-comings we observed an increase in analysis time by a factor of 9 on average (tests were performed on an AMD Opteron 8356 at 2.3 GHz, running Linux Kernel version 2.6, with CPLEX version 10 solving the IPET ILP problems).

We expect that most of the analysis overhead can, in fact, be eliminated by designing the WCET analysis to take advantage of the iterative processing. The overhead of performing a complete run of abstract interpretation on every iteration can, for instance, be avoided. Abstract interpretation usually is performed by searching for a fixed-point. Adding basic blocks, as done by our algorithm, can easily be handled by this approach. The fixed-point search can continue from the abstract states computed for the previous iteration to quickly derive a new fixed-point for the current subgraph. Other forms of incremental analysis should equally reduce the overhead of performing a longest path search on structurally similar subgraphs. These techniques, combined with smaller problem sizes (due to smaller subgraphs and reduced hardware splits), promise to even reduce the analysis overhead, compared to a full analysis run using aiT's prediction file technique. We even observed this behavior in our tests for IGP-TS and the a2b benchmark. Despite an increase in the analysis time by a factor of 14 for the abstract interpretation, a reduction of the ILP solving time lead to an overall reduction of the analysis time of about 15%.

We observed that our technique addresses the problem of overestimation very well, in particular during early iterations. However, we also observed that in many cases the overestimation grew fast, often outweighing large initial gains. The main problem is that the subgraphs steadily grow larger. We could address this problem by restricting the subgraphs to only those nodes reachable from the current basic block set (S i ). However, one could similarly change the strategy for growing subgraphs, e.g., by estimating the impact on the number of hardware splits. In a similar way, neighboring basic block sets may be merged in order to avoid excessive iteration counts.

Related Work

We divide related approaches for tightening WCET bounds roughly by the main technique they employ. Since most methods -ours included-are complementary to each other and thus can be combined within an integrated analysis, some natural overlap occurs.

Program Slicing

Several pruning techniques, similar in spirit to our technique, have been proposed in the past based on program slicing [START_REF] Weiser | Program slicing[END_REF]. The basic idea of program slicing is to improve the precision and the computational overhead of static program analyses by discarding program statements that are irrelevant to the goal of the analysis. Consider, for instance, the case when the goal of a static analysis is to determine the value of a given variable in a program. When forming a slice for that particular variable, only those statements are considered during the analysis that directly and indirectly contribute to the computation of that variable. All other statements are ignored. The goal in our approach is to improve the analysis of the WCET itself, our technique thus can be seen as a form of program slicing on the timing domain.

Sandberg et al. [START_REF] Sandberg | Faster WCET flow analysis by program slicing[END_REF], for example, propose to use program slicing to improve the static analysis of flow facts. They construct program slices based on either all conditions of branches in a program, on all loop-exit conditions, or on the loop-exit conditions of a particular loop. Based on the computed slices, flow facts, such as loop bounds, are computed. In contrast to our work, the focus here is on deriving flow facts only, regardless of the relevance or impact to the final WCET. Their technique can, however, be combined with our approach. This would, for instance, allow to derive flow facts that are only valid with respect to the current subgraph under consideration.

A similar approach is proposed by Lokuciejewski et al. [START_REF] Lokuciejewski | A fast and precise static loop analysis based on abstract interpretation, program slicing and polytope models[END_REF]. They combine abstract interpretation, polytope models, and program slicing to derive precise loop bounds. The approach again does not consider the relevance of the respective loops under analysis with regard to the final WCET.

Infeasible-Path Elimination

Bang and Kim [START_REF] Ho | An iterative refinement framework for tighter worst-case execution time calculation[END_REF], similar to our technique, propose an iterative approach to refine the attainable WCET using standard IPET. The basic idea is to perform a regular WCET analysis run. The resulting WCEP is subsequently checked for feasibility and, in the case of an infeasible WCEP, additional constraints are added to the IPET problem to exclude the path. This process is repeated until a feasible path is encountered. It is important to note that the presented feasibility checks are conservative and only consider individual basic blocks and pairs or blocks, but not the entire path. The major problem of this approach is that the refinement is based on individual paths through the program, whose number is potentially exponential in the number of conditional branches in the program. The additional constraints are, furthermore, only applied during the final IPET run. Contrary to our approach, the technique thus cannot improve the precision of previous analysis phases, such as the cache-or pipeline analysis.

Zwirchmayer et al. [START_REF] Knoop | WCET squeezing[END_REF] propose a related scheme called WCET Squeezing. The authors iteratively check the feasibility of the current WCEP using symbolic execution and exclude paths found to be infeasible from the IPET problem. In contrast to Bang and Kim, this technique considers the entire path and may thus potentially derive more complex constraints. The technique similarly does not allow to improve the precision of other analysis phases than the final IPET. To its advantage, WCET squeezing is an anytime algorithm, i.e., when interrupted at any time, a possible up-to-then achieved refinement is sound. Our current graph pruning algorithm does not have the anytime property, in fact it needs to run until the WCET bound from a pruned subgraph has been proved valid.

Abstract Interpretation

We evaluated graph pruning using AbsInt's aiT WCET analyzer, which makes use of abstract interpretation for its value analysis. While in this specific setting, the precision of value analysis benefits from the smaller graphs that we provide through pruning, context-sensitive abstract interpretation techniques [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF][START_REF] Ermedahl | Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis[END_REF] themselves, in fact, share the same goal with us. They are used for the automatic computation of control-flow bounds (i.e. loop bounds or flow facts) that ultimately aim to tighten the WCET bound. The challenge for abstract interpretation is to cope with an overwhelming combination of program-, pipeline-, and cache states through safe approximation of values withing their domain and the merging of related hardware states. Efficient widening (and narrowing) operations are essential for analysis precision. [START_REF] Cortesi | Widening and narrowing operators for abstract interpretation[END_REF] The approach presented here is inspired by the Criticality metric proposed by Brandner et al. [START_REF] Brandner | Static profiling of the worstcase in real-time programs[END_REF]. The metric assigns a numeric value in the interval [0, 1] to each basic block of a real-time program, where values close to 0 indicate code that is irrelevant and values close to 1 indicate code that is critical to the final WCET. We adopt the idea of discovering the longest path passing through basic blocks to refine the attainable WCET bound. The authors' algorithm to compute Criticalities on-demand has been adopted for our approach [START_REF] Brandner | Criticality: Static profiling for real-time programs[END_REF].

Conclusion

Exploiting problem structure has proven to be a key element in many optimization problems. We argue about the structure of a program's CFG and its properties specifically with regard to WCET analysis.

WCET analysis tools have to continuously restrict problem size, in order to meet space as well as time constraints and maintain feasibility: (1) During abstract interpretation, the overwhelming combination of program-, pipeline-, and cache states may require merging. (2) Solving the longest path problem, while accounting in detail for all processor states, again is only feasible up to a certain magnitude of states (variables). The downside of these techniques is, that the precision of the attainable WCET bound is reduced. While other approaches for tightening an IPET-based WCET bound are designed to refine the worst-case path in a post-processing step, graph pruning can be used in order to decrease problem size and increase precision during WCET analysis. Compared to existing program slicing techniques, our approach extends to the lower-level timing analysis too. With the algorithms given above, we further demonstrated, that WCET profiles are a suitable first guide to this search.

Figure 1 :

 1 Figure 1: A weighted CFG and its longest paths (see Example 1)

Figure 2 :

 2 Figure 2: Weighted CFGs formed during Iterative Graph Pruning.

Theorem 1 .

 1 Algorithm 1 computes a safe WCET bound.

Figure 3 :

 3 Figure 3: WCET bounds per iteration for the f1a benchmark using Iterative Graph Pruning. (IGP, lower is better)

Figure 5 :Figure 6 :

 56 Figure 5: Reduction of hardware splits using Iterative Graph Pruning. (IGP vs. IGP-TS, lower is better. Vertical bars display iterations' min./max., marker is average.)

  Criticality Intervals * Problem BBs I 0 I 1 I 2 I 3 I 4 I 5

	debie-1	83	4	2	0 13 19
	debie-2a	23 16	0	0	0	0
	debie-2b	23	1	0	0	6	1
	debie-2c	23	8	0	0	0	1
	debie-3a	74 16	0	0	0	1
	debie-3b	74 15	0	0	0	0
	debie-3c	74 15	0	0	0	0
	debie-4a	285 31 192	0 19	3
	debie-4b	285 236	3 14	0	3
	debie-4c	285 260	0	4	0	5
	debie-4d	285 264	0	4	0	1
	debie-5a	138 13	0	0	1	4
	debie-5b	138	5	0	0	0	1
	debie-6a	376 53 24	2 105	0
	debie-6b	376 52 22	4 106	0
	debie-6c	376 52 22 143	4	0
	debie-6d	376 12 24	2	0 144

Table 1 :

 1 Criticality statistics for the Debie1 benchmark

			Criticality Intervals *
	Problem BBs I 0 I 1 I 2 I 3 I 4	I 5
	papa-a1	626 45	0 0	0 271
	papa-a2a 1522 535	0 0	0 19
	papa-a2b 1522 66 125 0 220	8
	papa-a3a	981 717	0 2	0 59
	papa-a3b	981 201	0 0	2 89
	papa-a4	334 56	0 0	0 54
	papa-a5	438	0	0 0	2 10
	papa-a6	682 25	0 4 42 81
	papa-f1a	285	1	0 0	0 122
	papa-f1b	285 279	0 0	0	0
	papa-f2	8	0	0 0	3	1

Table 2 :

 2 Criticality statistics for PapaBench block in the CFG as the length of the longest path passing through a basic block divided by the global WCET. This gives a value between 0 and 1 that indicates how relevant a given basic block is in relation to the WCET of the program. This information can then be used to guide program optimizations in order to improve the WCET of the program.

Table 3 :

 3 Criticality based basic block sets for debie-1

		0 43	1,621
		S 1	1	1,613
		S 2	1	1,608
		S 3	5	1,601
		S 4	1	1,592
		S 5	4	1,585
		S 6	8	1,560
		S 7	1	1,472
		S 8	3	1,456
		S 9	3	1,415
		S 10 3	1,352
		S 11 3	1,324
		S 12 1	1,231
		S 13 2	657
		S 14 1	321
	Pre-run:	WCET(G) = 1621

Table 4 :

 4 WCET Reduction using Iterative Graph Pruning (Summary)

Table 5 :

 5 Detailed results for Iterative Graph Pruning (IGP)

	Graph size (nodes)

Table 6 :

 6 Detailed results for two-stage Iterative Graph Pruning (IGP-TS)

http://www.mrtc.mdh.se/projects/wcet/benchmarks.html

Acknowledgments

This work is partially funded under the European Union's 7th Framework Programme under grant agreement no. 288008: Time-predictable Multi-Core Architecture for Embedded Systems (T-CREST) and was supported by the Austrian Science Fund (FWF) under contract P21842.