Julien Gardan
email: julien.gardan@epf.fr

Duy Cuong Nguyen

Lionel Roucoules

Guillaume Montay

Characterization of Wood Filament in Additive Deposition to Study the Mechanical Behavior of Reconstituted Wood Products

Keywords: Additive manufacturing, composite, rapid prototyping, wood pulp, fiber, mechanical characterization

The use of materials derived from biomass is unavoidable to decrease environmental impact of products. The main advantage of the Additive Manufacturing (AM) concept is the ability to create complex geometries one layer at a time. The primary aim of this study was to create objects using reconstituted wood through manufacturing with low environmental impact. Wood can be converted into various derivatives allowing the introduction of sustainable material into the product lifecycle. This work uses an AM device adapted to a Computer Numerical Control (CNC) machine [1] to produce a reconstituted wood product by filament deposition. The first part assessed the deposit of wood pulp with a 3D printing head device, while the second part focuses on the characterization of microscopic structure of the material. Fiber morphology and mechanical properties of composite materials incorporating the filaments are characterized.

INTRODUCTION

Since the appearance of rapid prototyping, many different technologies have appeared on the market. There are several available technologies based on the additive machining concept [2]: stereolithography (SLA), photo-masking, Selective Laser Sintering (SLS), Fused Deposition Modeling (FDM) and 3D printing are a few examples. Research to date has focused mainly on the influence of part orientation, slicing strategy, internal optimized structure, matching internal patterns to improve cost, product quality, built time, etc. Additive Manufacturing (AM) or 3D printing has is well developed and currently offers several solutions using synthetic polymers such as acrylonitrile butadiene styrene (ABS), polyamides (PA) and others which can have negative environmental impact. Due to the evolution of rapid prototyping technologies, it has become possible today to obtain parts representative of mass production within a very short time [3]. Today, a balance between ecologically friendly materials, economic processing and mechanical properties of the final product is highly desirable [4].

The notion of "sustainable" products leads to the use of materials and manufacturing processes compatible with sustainable environment throughout the product lifecycle. The wood lifecycle includes some compounds which involve the wood-based panels such as plywood, particle board, fiber, etc. Woodbased products are of interest due to their economic, technical and environmental attributes.

A previous paper described the applications of additive manufacturing through a piston deposition which required an extrusion system [1]. This deposition system consists of a 3D printing head integrated into a Computer Numerical Control (CNC) machine instead of the end mill and can be used to produce a reconstituted wood product with ecological advantages. This research work describes the development of a wood pulp based on starch and beech wood and use of using the deposition system pictured in

MATERIALS AND PROCESSING Additive Manufacturing Technology

The first form of creating a three-dimensional object layer by layer using computer-aided design (CAD) was rapid prototyping, developed in the 1980's for creating models and prototype parts. Building up components layer by layer in such a manner is called rapid prototyping, rapid manufacturing, layer manufacturing, solid freeform fabrication or additive manufacturing. This technology allows the creation of printed parts beyond CAD models. Advantages offered by this technology to the product development process are time and cost reduction, human interaction, and consequently more efficient product development cycles. Increasingly, this technology is being used to manufacture finished products rather than prototypes [6].

The technique used most commonly is the Dough Deposition Modeling (DDM) which consists of individual processes deposit different doughs [2]. Some technologies based on FDM (Fused Deposition Modeling) printers use a syringe to deposit such materials as silicone, food dough or chocolate. A syringe based extrusion tool uses a linear stepper motor to control the syringe plunger position [7]. The FDM technology was invented in the 1980s by Scott Crump [START_REF] Crump | Apparatus and method for creating three-dimensional objects[END_REF][START_REF] Crump | Modeling apparatus for threedimensional objects[END_REF]. Medical research uses this technology for the deposition of biomaterial and cells to realize a tissue structure. It presents a novel method for the deposition of biopolymers in high-resolution structures, using a pressure-activated microsyringe [START_REF] Vozzi | Microsyringe-based deposition of two-dimensional and three-dimensional polymer scaffolds with a well-defined geometry for application to tissue engineering[END_REF]. Other studies describe applications involving extrusion of a bio-based material using a piston and 3D printer head adapted on a CNC machine (Figure 1 (b)) to deposit a wood pulp based on wood flour, creating a reconstituted wood product [1,5].

Currently the most widely used materials in FDM are ABS, polylactic acid (PLA), and PC (Polycarbonate). Compared to ABS, PLA is more sensitive to moisture and ultraviolet (UV) radiation, resulting in discoloration and loss of mechanical properties. To predict the mechanical behavior of FDM parts, it is critical to understand the material properties of the raw material, and the effect that FDM build parameters have on anisotropic material properties [START_REF] Ahn | Anisotropic material properties of fused deposition modeling ABS[END_REF]. The disadvantages are that the resolution on the 𝑧𝑧 axis is low compared to other additive manufacturing process (0.25 mm), so if a smooth surface is needed a finishing process is required and it is a slow process sometimes taking days to build large complex parts [START_REF] Kaufui | A Review of Additive Manufacturing[END_REF]. FDM is the most widely used technology in desktop 3D printers and the less expensive professional printers.

Recently, with progress in material and enabling technology, many new AM techniques have emerged and been applied in fields such as rapid tooling/molding, direct formed usable parts, nano-/micro-AM, and biomanufacturing [START_REF] Yan | Rapid Prototyping and Manufacturing Technology: Principle, Representative Technics, Applications, and Development Trends[END_REF]. Some studies use biomaterials in AM to realize 3D structures or products with degradable polymers such as polylactic acid (PLA) [START_REF] De Ciurana | Selecting Process Parameters in RepRap Additive Manufacturing System for PLA Scaffolds Manufacture[END_REF][START_REF] Serra | Highresolution PLA-based composite scaffolds via 3-D printing technology[END_REF], but none use a material generated directly from biomass.

Biomass Material: Wood

Wood (or cellulose) is a biodegradable organic material which is more or less long term reintegrated into the natural carbon cycle. Wood takes part in the reduction of carbon dioxide emissions as an alternative to non-renewable materials, the latter leading to energy costs and other negative impacts to the ecosystem. The mechanical properties of wood are all the more interesting because they are directly related to the microscopic structure of the cell wall forming the wood fibers (composed of several layers of different thicknesses and made of microfibrils arranged helically and oriented in a specific angle for each species). This microfiber orientation is important to the mechanical behavior of material. Examination of wood fibers side by side shows that the antisymmetric inclination of the fibers increases the mechanical strength (like the synthetic composites by layer). The life cycle of wood includes certain compounds that involve all materials using wood material processed as main base, such as plywood, particle board, fiber, etc.

When wood and its by-products are cut or processed, the characteristics of the fiber cells and their provisions will change the properties of the final material [START_REF] Miller | Structure of wood, Wood Handbook : Wood as an Engineering Material[END_REF]. Wood flour, on the other hand, is an unstructured material defined by a particle size distribution of small fibers. The development of reconstituted wood products by additive manufacturing is of interest due to a more positive impact on the environment than synthetic polymers.

Wood Pulp and Processing

The wood pulp is incorporated into the manufacturing process by a cold extrusion. The solidification time will be much longer than for other AM applications. However, the application addresses the goal of Ecodesign. In this experiment, beech flour from deciduous tree is used. It was obtained from J. Rettenmaier & Soehne (JRS), under the name LIGNOCEL HB 120 (Table I). A Design of Experiment (DOE) using the following variables was employed:

-Grain sizes of beech flour: 40 µm and 120 µm -Mass of beech flour: 20 g and 40 g -Mass of ether starch: 10 g and 40 g -Volume of demineralised water: 200 ml and 300 ml A modified starch (Table II) was used to develop viscosity through crosslinking and binding properties at low temperatures or at normal heat in a waterlimited environment. Modified starch remains completely biodegradable. However, it should be noted that the nature of the starch as a natural substance decreases with the increasing use of etherification.

RESULTS AND DISCUSSION Macroscopic Parameters and Structure

The application of Additive Manufacturing through piston deposition using 3D printing head created specimens by layers similar to FDM (Fused Deposition Modeling), but using a cold process (Figure 1(b)). The layered manufacturing generates an asymmetric structure which increases the mechanical strength of the specimens (Figure 3). The orientation of each superimposed threads has an angle of 90° in AM. This interaction among the fibers improves the stiffness and strength of the specimen. However, due to the orientation of filaments and fibers in each layer, the resulting mechanical properties can differ in the three directions. The vertical direction Z to the layered plane has the lowest properties. The thread superposition should not be masked by following the microscopic study.

Microscopic Structure

The influence of material and process parameters on the microstructure was determined. The fibers are oriented according to the Additive Manufacturing process and have an angle that varied with the morphology that develops during the deposit extrusion and solidification. The influence of the following process variables on fiber morphology was examined:

1) Extrusion speed of the piston system (controlled by computer) 2) Average beech flour fiber size ranging from 40 to 120 μm 3) Viscosity of the starch matrix.

The microstructure and fiber orientation of the wood filaments and fibers were observed using an optical microscope (Figure 4(a)). The structure is generally dominated by fibers oriented toward the extrusion direction. Some fibers are set at various angles but never in the direction perpendicular to thread. Furthermore, following the withdrawal of starch during drying fibers consolidate into a heterogeneous mass. The drying causes the starch to stick the filaments to each other and some fibers intercalate at the junction. The mixture obtained by the DOE is heterogeneous between beech flour and starch. Drying starch has a strong influence on the final structure. The solidification behavior as illustrated in Figure 4 showed the filament diameter was 2 mm out of the nozzle and 1.2 mm after cooling. Thus the draw down is 40% in the radial direction. An electronic microscope at a 50 µm scale was used to measure fiber lengths. Fiber lengths ranging between 50µm to 150µm length were found (Figure 4(b)). Since the starch serves as a binder, further characterization of the interactions between the filaments and starch will be required to completely understand the filament microstructure.

Filament Characterization

Tensile testing was undertaken to characterize the mechanical properties of wood filaments. The tests were carried on filament lengths L i (𝑖𝑖 = 1 -4 ������� ) of 11 mm. A micro-tensile test machine Kammrath & Weiss (Figure 5) was used to carry out uniaxial tensile tests using the the method proposed by Florent Ilczyszyn [START_REF] Ilczyszyn | Effect of hemp fibre morphology on the mechanical properties of vegetal fibre composite material[END_REF]. The displacement speed of the machine was 1 μm.s-1 with a sampling period of 500m.s-1. The load cell capability is 100N with an uncertainty of 1/100N. The filament is glued on a paper with a gap to support the filament's tops, avail a test length and protect the extremities from damage when tightening the grips. Glue points at both ends of specimen to keep the filament on the support. The method focuses on a circular and constant cross section along the filament. The stress (ơ) across a filament with a circular cross section (S circular ) is based on the equation used by S. Ralf [START_REF] Ralf | Mechanical and morphological characterization of selected natural fibres[END_REF], where F is applied force.

σ = F S circular (1)
The wood filaments exhibit fragile behavior with sudden rupture. However, in some cases, there is a partial resistance of wood filament after the maximum force reached (Figure 6). The cause is that the filament is not perfectly straight. The cross section of wood filaments (d=1.2mm) is 1.13mm². The tensile properties of all specimens are presented in Figure IV. The maximum tensile load of 4 tested specimens doesn't rise above 8 N and the longitudinal displacement varies from 100 to 200 μm. The tensile strain average of 1.25% indicates the wood filaments are quite brittle. The maximum tensile stress and Young's modulus values (from Hooke's Law) are 7.03 MPa and 728.58 MPa respectively. Figure 7 presents the tensile strength evolution versus tensile strain. Before the maximum stress reached, the filament behavior is quasi-linear. After the initial yield point, the tensile stress increases at a much lower rate until filament rupture.

In the cases of curves L 3 and L 4 , the stress reduction is caused by filament cross section loss.

The differences in the failure mechanism observed are most likely a result of differences in filament to filament crystallinity and indicative of a good deal of heterogeneity in the morphology.

In this study, the number of tensile tests is limited to four. A future in-depth study with more tests is desirable in order to better understand the mechanical behavior of the wood filaments and to have a more statistically significant result.

Matrix Structure

It is well documented that the mechanical properties of composite materials depend strongly on the coupling between the fibers and the matrix at the interface-a weak interface decreases the composite strength [START_REF] Nguyen | A Pull-out Fiber/Matrix Interface Characterization of Vegetal Fibers Reinforced Thermoplastic Polymer Composites: The Influence of the Processing Temperature[END_REF]. Chemically modified starches develop viscosity and binding properties at low temperature or at normal heat temperatures in a water-limited environment. One characteristic of starch is that its granules attached to each other and form larger granules. Gelatinized starch is a viscous adhesive. The mixture of starch and wood flour created a composite of fibers. The starch wraps the beech flour and agglomerates the fibers during cooling as shown in the electron micrographs in Figure 8. The starch structure (shiny appearance) is generally present over the entire surface. In a composite, it is the relative amount of cohesion of the matrix and reinforcing medium affects the overall properties. Based on observation of the properties obtained, the adhesion between the wood fibers and the matrix appears to be similar that of a nonwoven composite.

CONCLUSION

The structure of wood composite manufactured by additive manufacturing has been characterized at macro and microscopic levels. Microscopic examination indicates agglomeration of the wood flour and adhesion to the incorporated wood fibers. The processing parameters have an influence on the mechanical and physical properties of the structure. The experiments reveal fundamental microstructure and process characteristics:

1) The macroscopic structure shows a fiber strengthening via multilayer intercalation within the matrix. 2) The microscopic structure of filament is a nonwoven composite with fibers oriented in the extrusion direction.

  Figure 1(b) to extrude samples shown in Figure 2. This process creates a wood composite structure which includes fibers from the wood flour. Mechanical properties of the extruded specimens are characterized and a Design of Experiments (DOE) is used to optimize those properties [5].

FIGURE 1 .

 1 FIGURE 1. Overview of implemented technologies: a. Fused deposition; b. Piston deposition; c. Screw deposition.

FIGURE 2 .

 2 FIGURE 2. Test samples produced using wood pulp.

FIGURE 3 .

 3 FIGURE 3. Deposition wood pulp and fibers strengthening.

FIGURE 4 .

 4 FIGURE 4. Microstructure of two wood filaments (a) and fibers size (50 µm scale X 100) (b).

FIGURE 5 .

 5 FIGURE 5. Photo of the micro-tensile test machine (a) and filament support (b) according to [19].

FIGURE 6 .

 6 FIGURE 6. Tensile force versus displacement (µm).There are two types of behavior: the fragile behavior with sudden rupture (the blue and the green curve) and the behavior with partial resistance of the wood filament after the initial yield (the red curve and the violet curve).

FIGURE 8 .

 8 FIGURE 8. Starch matrix structure and 3D representation (50 µm scale X 200).

TABLE I .

 I Wood flour properties HB 120.

TABLE II .

 II Modified starch.

	The tests were conducted with 3D printing head
	installed on a CNC machine to produce test
	specimens layer by layer. The manufacturing
	conditions are defined below:
	-Filament diameter: 1.2 mm
	-Temperature: 20 ° C
	-Humidity: 60% RH
	-Extrusion piston: compressed air
	-Extrusion speed : 1.3 m/min
	An electric piston would offer a more stable
	extrusion, but the high sensitivity to humidity
	precluded its use. A Design Of Experiment (DOE)
	was previously implemented to optimize the wood
	pulp strength [5,17,18]. The study showed that the
	interactions of beech flour and starch have the
	highest effect on the wood pulp strength. The
	optimized tensile strength is reported in Table III.

TABLE IV .

 IV Mechanical properties of wood filament.FIGURE 7. Tensile stress versus tensile strain (%).

	Specimen	Tensile strain (%)	Tensile strength (MPa)	Young's modulus (MPa)
	L 1	1.84	6.27	468.23
	L 2	1.09	7.03	728.58
	L 3	0.9	3.66	640.69
	L 4	1.15	4.86	562.86
	Average	1.25	5.45	600.09
	Deviation	0.36	1.3	96.09

Individual filament tensile strength strain average 5.45 MPa and 1.25% respectively with a Young's modulus of 600.09 MPa. The filament are relatively it with a tensile strength 25 MPa of polypropylene composite filled with 40% wood floor and a young' modulus of 3.5 GPa [START_REF] Stark | Effects of wood fiber characteristics on mechanical properties of wood/polypropylene composites[END_REF]. The strength properties are limited by the heterogeneous nature of wood fiber morphology and sensitivity of the material to ambient conditions with its humidity uptake and shrinkage on cooling. Humidity uptake is due to the hydrophilic properties of hemicellulose and starch.


domain: sdv sde

text:
Philippe Grandcolas
email: pg@mnhn.fr

1

The view of Systematics on Biodiversity Philippe GRANDCOLAS

Introduction

There are several ways to evaluate Biodiversity, which is a multi-level concept with multiple purposes. Each consideration of this concept generally involves the prism of a scientific discipline, a study level or a specific purpose [MAC 08]. Thus, scientists focus sometimes on intraspecific diversity, sometimes on interspecific diversity, or even on the diversity that can be studied at the level of ecosystems, etc. Disciplines usually concentrate on their study subject, such as genomics or population biology on diversity within genomes or populations, respectively.

For my part, I would like to share several general reflections on Biodiversity, which are inspired by the scientific contribution of a discipline, Systematics. The origin of this discipline is ancient and is still often assimilated in people's minds with description and classification tasks, as they were practiced at the time of the great naturalists of the 18 th and 19 th centuries. However, for over half a century, Systematics has been a major player in evolution biology, in particular with phylogenetic analysis, which appeared after the work of the systematist Willi Hennig in the 50s-60s and which spread throughout Biology [OHA 92].

Systematics contribution pertains to the field of comparative biology [NEL 70]: it compares organisms and their characteristics, and draw conclusions in term of evolutionary relationships (phylogenies, homologies); it establishes diagnoses (taxonomy). Far from denying the variability of the living world [DEB 01], which is especially integrated in species concepts, it studies it on the contrary to select invariants, which will make it possible to study the origin of Biodiversity, namely the way organism characters set up.

My goal is not to present Systematic case studies of biodiversity, but to highlight several significant points which Systematics can help us to understand or value regarding Biodiversity, and which are linked in a very interesting way to those uncovered by ecological approaches. The purpose of this presentation is obviously not to promote a discipline for its own sake, but to provoke reactions and reflections through the contrast between different points of views.

Species: all different

In the 80s, the creation of the concept of Biodiversity and the advent of phylogenetic analysis made it possible to reintroduce in people's minds a very valuable asset: the notion of diversity between species, which had faded away since the rise of General Biology2 at the beginning of the 20 th century [GRA 17].

In fact, General Biology and what we still call today Life Sciences (with components called System Biology 3 or Integrative Biology 4 ) appeared and developed with the idea of seeking and defining main general principles common to all organisms, like for example the "laws of heredity". It is also at this time that organisms-models, which were supposed to represent on their own entire sections of the living world, emerged, such as the Thale Cress Arabidopsis thaliana for plants or the common fruit fly Drosophila melanogaster for insects. From the moment one focuses on the main constitution or operation principles supposedly common to all organisms, one is concerned far less with their differences and diversity. General Biology then contributes to the study of organism evolution, because it identifies general heredity or operation mechanisms of organisms. However, it does not then study the evolutionary History of different groups of organisms in interaction with the environment, which is the source of Biodiversity. This eclipse of History (meaning evolutionary History), as the systematist Dan Brooks and the ethologist Deborah McLennan called it [BRO 91], then stopped in the 80s when the community of biologists became aware again of the importance to consider differences between species. At that time, the term biodiversity was coined by Thomas Lovejoy, Walter G. Rosen and Edward Osborne Wilson [WIL 88]. Phylogenetic analysis was formalized at the same time [WIL 81], which allowed it to benefit from the advent of molecular biology and its massive provision of data to study Biodiversity. The study of the living world thus regained not only intraspecific variation (population genetics in particular) and interspecific interactions (ecology), the study of which was well developed since the beginning of the 20 th century, but also differences between species, the study of which was less advanced, especially at the evolutionary level. In all these ways, differences between species became again a subject of analysis and not a background noise to be removed in order to study the laws of the living world. This awareness that the variety of living organisms must be a subject of scientific and societal concern, as much as the unicity of some processes in the whole living world was reflected in many different ways, including in Biodiversity sciences. For example, Biodiversity metrics changed, especially thanks to Systematics. We went from the rather universal use of specific richness, a traditional measure in ecology which considers all species as identical (a tribute to General Biology at the beginning of the 20 th century), to more sophisticated metrics. This way, Faith [FAI 92] offered phylogenetic diversity or PD, a measure taking into account for a set of individuals the total length of the phylogenetic tree branches connecting them: it thus expresses the quantity of common characteristics and differences characterizing them. Even though it is correlated with the specific richness (the more species are considered, the more the number of branches linking individuals in a tree increases, and therefore the sum of their lengths), PD provides much more information than a simple cardinal sum. It has the great advantage of being a potentially overall measure of genetic and phenotypic diversity, and thus goes beyond geographic, regional or local levels [VER 15; PEL 16-1]. We could mention another example with the first version of the "comparative method" of the 80s, which offered to calculate statistical causal relations between traits or environments [CLU 79]. This method considered species as equivalent here again and simply controlled that they were not statistically independent in case of close relationships (comparing ten squirrels and ten mice would statistically come to only comparing two groups!).

Figure N.1 A theoretical phylogenetic tree in which two sets of 3 species are chosen (dotted lines)

. The specific wealth of the two sets is the same (N=3), but the PD of the left selection is much higher (with especially sp.5 which is the sister-group of the rest of the tree instead of sp.2, the sister-group of sp.1).

This method then evolved into the phylogenetic analysis of evolution (with modern "comparative phylogenetic methods"), which compares several species evolutionary histories immediately considered as different, histories that are rebuilt by establishing potential homologies [BRO 91].

How about studying the other 90%?

This welcome awareness of the significance of the variety of living organisms certainly also helped to become fully aware of the terrifying disaster represented by the current crisis of Biodiversity. The Biodiversity crisis is serious, because individuals belonging to different species represent different values, functions and services: reducing their number and variety is equivalent to direct losses in all these aspects.

Nevertheless, there is still an intellectual frontier that Systematics can help us to cross, we mean understanding the significance of the 90 % of current Biodiversity still unknown. It is in fact a paradox to read the alarming numbers of extinctions, which are unfortunately already effective or to come within a few decades [BAR 11; REG 15] and which apply to what we know (10%), and which unintentionally bypass what we do not know (90%). Without being particularly concerned with cataloguing or inventory, we should still acknowledge that our sample of the living world is hardly representative in the light of the numerous issues raised, including the crucial issue of the extinction crisis.

Sp.1 Sp.2 Sp.3 Sp.4 Sp.5

Sp.1 Sp.2 Sp.3 Sp.4 Sp.5

N 1 = N 2 PD 1 >> PD 2
Thus, do we really know what is going to disappear and, a fortiori, what was the role of the biodiversity that disappeared before we could know it [REG 09]? Can we be content with the possibility of a probable functional redundancy essential to the operation of ecosystems, without really knowing how many species are concerned and really redundant? From this point of view, and knowing that rare species can play significant parts in ecosystems [MOU 13], which serious consequences are going to have the extinctions of rare species that are still unknown? What would the 90% remaining Biodiversity provide in terms of knowledge, especially in the very current field of Biomimetics or Bioinspiration [BEN 16]? For the record, out of approximately one million known species, only 76,000 are concerned by patents [OLD 13]. What would it be with ten times more species known?

In view of this paradox -extinction of a mostly unknown set -the most common response is often only operational or logistic: we do not know enough about Biodiversity, never mind, let us use such and such tool or procedure and, in 20 years, we will have substantially increase our knowledge [MAY 04; DAL 12]. However, without neglecting the main programs of Biodiversity exploration, to which we can only subscribe with enthusiasm, it seems mainly important to realize that we should all address the issue of the still unknown Biodiversity and not leave it to the exploration programs of the living world alone (Systematics Agenda 2000, Barcode of Life, La Planète revisitée, and soon Planetary Biodiversity Mission). Almost as if the genomics discipline had only been built and practiced by consortiums composed for the sequencing of the first complete genomes. This means that there is a requirement to improve ethics and to make taxonomic knowledge available, requirement that should be shared by all scientists studying Biodiversity. Let us not continue thinking in terms of general biology, as if knowledge research should only be content with the quest of universal aspects (laws, processes, etc.). We must realize that the increase in knowledge on Biodiversity specificities is also a key study subject. In this respect, the Nagoya Protocol and its national regulatory implementation are often seen as a restriction by scientists, whereas they helpfully remind us our ethical obligations. Laboratories studying biodiversity must train or house scientists competent in taxonomy, who are nowadays disappearing [GRA 12]: it is not enough to barcode, metabarcode, database, digitalize, geolocalize, etc. specimens to save information specific to a study or useful to society. It is also very often necessary to directly contribute to taxonomy, by describing or reviewing taxons. Information and knowledge access and sharing are only possible through a taxonomic system with reference specimens and names. The amazing molecular, digital and computer means, which are rapidly developing, only make this linkage even more vital [PEL 16-2]. This challenge is particularly crucial in the case of micro-organisms, whose accessibility is limited by our powers of perception, and which are important in all respects, including through their omnipresence within other organisms, with which their interactions (for example, mycorrhizae, intestinal microbiome, etc.) are essential [SEL 17]. In their case, molecular data are directly integrated into a traditional taxonomy, which is very much alive. Nevertheless, beyond metabarcoding approaches, the ability to cultivate species or keep strains are significant issues, that microbiology laboratories have well understood.

Biodiversity changes

Systematic and comparative design of Biodiversity also reminds us that it is derived from a long evolutionary process, that it can be phylogenetically characterized, including at a specific level, and that it is not defined as such, in a kind of "fixist" or more specifically essentialist abstraction [ROB 17] as our short human perception level would suggest.

It is necessary nowadays to reconcile so-called functionalist, "microevolutionist" and "macroevolutionist" designs. There is no useful and significant microevolutionist evolution biology considering the population mechanisms to which we are confronted at our timescale (a few years or a few decades), and another quaint and "cultural" macroevolutionist evolution biology dealing with fossils and building phylogenies * for Platypus, Ginkgos and other Dodos at a timescale incompatible with our existence (millions of years).

We must know the origin and selective context of phenotypic traits to study them and understand the adaptive phenomenon at the population level. The great development of "tree-thinking" (i.e. the use of phylogenetic trees) in biology since the 90s has thus taught us that a lack of macroevolution contextualization often made us build the microevolutionary explicative model backwards [BRO 91]: for example, in some spiders, models trying to explain sexual dimorphism through male dwarfism strayed by not considering the gigantism of females [COD 97]. Not linking micro-and macroevolutionary studies would be like rejecting all the watches with no second hand, because we are disappointed not to see the movement of the hour and minute hands when quickly looking at the watch face. And yet, we need to tell time. This level of -systematic and phylogenetic -Biodiversity macroevolutionary study is not only an essential explanatory foundation to conduct microevolutionary studies, it also helps to assess and perceive the living world in all its diversity. Once more, phylogenetic diversity is not only a good overall metrics, but it also allows us to ethically consider Biodiversity.

In a phylogenetic tree, no organism is superior to another. All current or fossil organisms, although they are very different, are the leaves of a tree, the root of which is an abstraction: there are only sister-groups within a tree, which does not show genealogies, but the kinship relationships between species [GRE 08; CRI 05; GRA 14]. Phylogenetic trees are then good media to explain that gradist 5 or anthropocentered reasoning is absurd, both for scientists and all publics [FOR 09; MAC 12].

Challenging decades

We are then at a crucial and paradoxical moment for the study and consideration of Biodiversity. It has never been so well known, but its greatest part still remains to be discovered. This whole biodiversity -known and unknown -is at risk of major extinction in the next decades. Our means to study it have never been so powerful but, paradoxically, the flood of data created by these means is in itself a challenge for knowledge access and sharing. This challenge has also a strong geopolitical component. Biodiversity is particularly significant in the South, and access and sharing must not only be an ethical concern common to the whole humanity, but also a desire to balance again knowledge, expertise and means between North and South political powers, in order to better share the environment common to all of us.

General biology studies in detail mechanisms in a few species and draws conclusions that can supposedly be generalized to the functioning of whole living world.

System biology studies the functioning of living systems from the cell to the tissue, by focusing on cellular and molecular approaches.

Integrative biology integrates physiological and biophysical aspects in the study of organism functioning.


Mickaël Dardaillon
email: mickael.dardaillon@insa-rennes.fr

Stefanos Skalistis
email: stefanos.skalistis@inria.fr

Isabelle Puaut
email: ‡isabelle.puaut@irisa.fr

Steven Derrien
email: steven.derrien@irisa.fr

Reconciling Compiler Optimizations and WCET Estimation Using Iterative Compilation

Keywords: Worst-Case Execution Time Estimation, Compiler optimizations, Iterative Compilation

Static Worst-Case Execution Time (WCET) estimation techniques operate upon the binary code of a program in order to provide the necessary input for schedulability analysis techniques. Compilers used to generate this binary code include tens of optimizations, that can radically change the flow information of the program. Such information is hard to be maintained across optimization passes and may render automatic extraction of important flow information, such as loop bounds, impossible. Thus, compiler optimizations, especially the sophisticated optimizations of mainstream compilers, are typically avoided. In this work, we explore for the first time iterativecompilation techniques that reconcile compiler optimizations and static WCET estimation. We propose a novel learning technique that selects sequences of optimizations that minimize the WCET estimate of a given program. We experimentally evaluate the proposed technique using an industrial WCET estimation tool (AbsInt aiT) over a set of 46 benchmarks from four different benchmarks suites, including reference WCET benchmark applications, image processing kernels and telecommunication applications. Experimental results show that WCET estimates are reduced on average by 20.3% using the proposed technique, as compared to the best compiler optimization level applicable.

I. INTRODUCTION

Safe upper bounds of Worst-Case Execution Times (WCET) are the key input of schedulability analysis, that ensures that deadlines of hard real-time tasks are met in all situations, including the worst case. WCET calculation techniques must be safe (provide upper bounds of execution times) and as tight as possible (provide a bound as close as possible to the actual WCET, which is in general unknown).

Many WCET estimation techniques have been developed in the past [START_REF] Wilhelm | The worst-case execution-time problem -overview of methods and survey of tools[END_REF], using either static analysis techniques or measurement-based techniques. Static WCET analysis techniques do not execute the code, and operate on the structure of the binary code. A hardware-level analysis step first calculates the worst-case execution time of sequences of instructions (basic blocks); this step has to be performed on the binary code, because the timing of instructions within basic blocks depends on the actual instructions generated by the compiler, as well as the mapping of instructions to memory addresses. A calculation phase then computes the WCET estimate of the entire program from the WCET of its basic blocks [START_REF] Li | Performance analysis of embedded software using implicit path enumeration[END_REF]. On the other hand, measurement-based techniques use end-to-end measurements to estimate WCETs. Contrary to measurementbased techniques, static WCET estimation techniques, used in this work, are guaranteed to provide safe upper bounds of WCETs, provided that they are able to build a safe model of the target hardware.

Static WCET estimation techniques require that all paths in programs are of bounded length, meaning the maximum number of iterations of loops, and the maximum depth of recursion are both bounded. Flow information (loop bounds, bounds on recursion or more elaborate flow information such as mutually exclusive paths) may be obtained using static analysis, or provided by the user as annotations. In general, automatic extraction of flow information using static analysis is to be preferred to annotations, that are error-prone.

Compilers translate high-level languages into binary code, fit for microprocessors. Modern compilers typically apply tens of optimizations (loop transformations, dead code elimination, factorization of redundant code, function inlining, etc.) to deliver more performance. While optimizations are key in delivering performance for the average case, optimizations are not always beneficial for the WCET. In addition, some optimizations may radically alter the program control flow and, thus, may break the automatic determination of flow information (such as loop bounds). The general problem when optimizing code in compilers, either for average or worstcase execution time, is that there is no precise processor performance model in the compiler because of the processor complexity. Additionally, optimization passes are programspecific and interdependent, in that they may have additive or destructive impact dependent on the optimization combination and the program to optimize. This prevents the use of exact optimization techniques such as Integer Linear Programming (ILP) or dynamic programming, and motivates research in the field of iterative compilation.

In this paper, we propose for the first time a technique to reconcile compiler optimizations (to have as good as possible performance, in average case and worst case) and WCET estimation, using mainstream compilers. Inspired from iterative compilation, commonly used to optimize averagecase performance [START_REF] Chen | Deconstructing iterative optimization[END_REF], [START_REF] Ashouri | A survey on compiler autotuning using machine learning[END_REF], we propose a technique for an automatic selection of optimization passes that both allows (i) the automatic extraction of precise flow information; (ii) optimization of WCETs. Since the space of optimizations to be explored is huge, techniques for selecting sequences of optimization passes have to find good candidate sequences in reasonable amount of time. More precisely, our contribution is an exploration technique for selecting optimization sequences tailored to a specific program, which improves analyzability and reduces the program's WCET estimate, compared to standard optimization levels (O0 to O3). Experimental results show that the proposed exploration technique results in lower WCET estimates than using random or genetic selection of optimization sequences.

The contributions of this research are the following:

• We propose a technique for automatic selection of optimization passes that allows (i) automatic WCET analysis, in particular automatic flow fact extraction, and (ii) WCET estimates minimization compared to standard optimization levels (O0 to O3). The optimization sequences selection stage uses a machine learning technique that exploits correlations between optimization passes.

In contrast to most research on iterative compilation, which focuses on average-case performance, our exploration technique optimizes analyzability and worst-case performance.

• We provide a detailed experimental evaluation of the proposed technique on code for a LEON3 processor. Experiments are performed using the mainstream compiler LLVM [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis and transformation[END_REF] and the aiT industrial timing analysis tool [START_REF]aiT:the industry standard for static timing analysis[END_REF].

Experimental results show that the WCET estimates of a large selection of benchmarks (46 benchmarks from the benchmark suites Mälardalen, Polybench, MiBench and PolyMage) are reduced by an average of 20.3%, as compared to the best compiler optimization level (O0 to O3) applicable without failure. Thanks to the very general nature of our approach, this technique can be implemented in industry realistically. • As a side result, our research also provides a technique to select the best unrolling factor parameter for the aiT industrial static WCET estimation tool. The unrolling factor is a parameter of aiT that allows to trade the quality of WCET estimates (higher unrolling factor results in better WCET estimates) against analysis time (higher unrolling factor results in higher analysis time).

The rest of this paper is organized as follows. Section II further motivates this research, by highlighting the difficulty of selecting optimization sequences that optimize WCET estimates. Section III then presents the proposed method for selecting optimization passes. Section IV evaluates the quality of our proposal on a large set of benchmarks. Section V then presents the automatic selection of the aiT's unrolling factor parameter. Our research is compared to related work in Section VI. Concluding remarks and directions for future research are given in Section VII.

II. MOTIVATION

Mainstream compilers provide standard code optimization levels (from O0, no optimization, to O3, highly optimized code), and also provide ways manually select optimization sequences, defined as an ordered list of optimization passes in which repetitions are allowed. This section motivates our research on WCET-oriented exploration for the best optimization sequence, through observations on examples. The experimental setup used in this section is the same used for the experimental evaluation of our work, i.e. use of the aiT WCET estimation tool for the LEON3 processor (see Section IV). All observations are made by randomly selecting 1000 optimization sequences of size 10 to 80, on two benchmarks (des and harris), with the virtual unrolling factor of the aiT timing analysis tool of 2 and 4 respectively.

Timing analysis may fail on optimized code

Figure 1 shows the number of failures encountered during the experiments. Failures encompass compiler failures (compiler internal errors, for example due to unsupported sequences of optimizations) and WCET analysis errors (mainly incapability of the tool to derive flow information, more marginally memory exhaustion or very long analysis times). The figure shows a significant number of analysis failures, outlining that some optimizations, either in isolation or in conjunction with other optimizations, hinder temporal analysis of the code. Obviously, the optimization sequences resulting in failures should not be selected. The presence of analysis failures is specific to WCET-directed search for compiler optimizations, as compared to iterative compilation techniques optimizing average-case performance.

Optimization sequences may result in WCET estimates better than O3 or worse than O0

As already observed for average-case performance [START_REF] Chen | Deconstructing iterative optimization[END_REF], Figure 2 shows that some optimization sequences result in WCETs that are lower than when using optimization level O3. For the des benchmark, 20% of the observations provide better estimated WCETs than O3; for Harris, 14% of the observations are better than O1, and levels O2 and O3 make the WCET analysis fail.

Figure 2 also shows that a significant number of optimization sequences result in WCETs estimates that are much larger (up to a factor of two for harris) than when compiling at O0. In addition, we observed that a significant amount of sequences have a negligible impact on the WCET estimate compared to O0 (18% for des, 16% for harris result in WCET estimates that are within 2% of WCET estimates at O0).

Optimizations are application specific

Figure 3 shows the distribution in the number of activated optimization passes for the best 100 WCET estimates. The results demonstrate that the number of optimization passes, that yields low WCET estimates, varies among benchmarks. More optimizations have to be activated for des than for Harris. The actual optimization sequences (i.e. the number of optimizations passes, their type and their particular ordering), yielding low WCET estimates are also benchmark dependent, as illustrated in Table I, that shows the sequence with the best WCET for des and Harris.

Finally, WCET estimation tools such as aiT use parameters that enable a trade-off between analysis precision vs analysis time. The virtual unrolling parameter is one of such parameters. As further detailed in Section V, larger unrolling factors improve the precision of WCET analysis at the cost of a longer analysis runtime. The best value for this parameter is also benchmark-dependent (2 for des and 4 for Harris), and therefore has to be part of the search.

Compared to iterative compilation techniques for averagecase performance, our work (i) optimizes a different metric (WCET estimate instead of average-case performance), (ii) disregards optimization sequences that hinder analysis, (iii) not only selects the best optimization sequences but also the best parameters of the timing analysis tool.

III. SELECTION OF OPTIMIZATION SEQUENCES

As highlighted in Section II, selecting the sequence of optimization passes that improves WCET estimates for a given program is rather challenging. This stems from intricate correlations among optimization passes, with unpredictable impact on the estimated WCET. In addition, sequences can be arbitrarily long, thus the space of optimization sequences is vast, that is practically impossible to fully explore.

In order to reduce the explored space and improve WCET estimates within reasonable time, our approach focuses on characterizing the impact (positive, neutral or negative) of the individual passes of a sequence with respect to already evaluated sequences. By construction, the characterization strategy classifies as neutral and negative the passes that frequently exhibit that behavior after a significant number of attempts. The main purpose of the characterization is to avoid passes that frequently exhibit a neutral or negative impact, as such passes are not likely to improve the estimated WCET. Conversely, passes that have been observed to frequently exhibit a positive impact, or passes that have not been applied often enough to establish their impact, are considered beneficial.

After having characterized the individual passes of each evaluated sequence, we apply a weighting scheme to guide the selection of passes towards those having frequently a positive impact, and away from passes that have frequently a neutral impact. The weighting scheme is inspired by association rule learning of the data mining domain [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. Association rule learning identifies frequent causality relations among subsets within transactions of a database. In a similar manner, our characterization strategy and weighting scheme identifies frequent causality relations between sets of optimization passes and impact on the resulting WCET. We opted for a weighting scheme, instead of an established algorithm from the domain, as such learning to be successful requires a large dataset. Acquiring such a large dataset is not only computationally expensive, which is not in line with our motivation, but also is not reusable across programs, since the behavior of optimization passes is program-specific.

The proposed approach, illustrated in Figure 4, follows a typical iterative compilation workflow. Given a program in high-level language and a compiler for the target architecture, the approach starts by compiling the given program with no optimization (O0) and follows by analyzing it with a WCET estimation tool. This establishes a baseline WCET for the program. Subsequently, a new optimization sequence is generated, by selecting (i) its length randomly and (ii) each pass of the sequence in a weighted random manner, according to the proposed weighting scheme (weights are initially equal). The program is then recompiled and analyzed, resulting in a new WCET estimate. The newly generated sequence is then compared to the previously evaluated sequences with the most common passes, and the impact of its passes is established. According to this new characterization of passes, the weights are updated and the process is repeated.

A. Characterization of optimization passes

Discovering the impact of passes (positive, neutral or negative) is not straightforward, as there is not enough information to individually evaluate which passes contribute positively/negatively to the estimated WCET. For example, consider two sequences, ABC and ABD that have improved WCET (compared to O0). Let their WCET estimates have the following ordering WCET ABD < WCET ABC (lower is better). It is hard to decide, whether optimization pass D is responsible for the improved WCET estimates of ABD or optimization pass A has a negative impact on ABC.

To establish the impact of a sequence of passes with respect to another sequence, the proposed characterization is founded upon the lattice of their sets 1 of passes (the partial order in the lattice is set inclusion, see Figure 5). The characterization strategy for a given sequence starts by finding the largest subset that has been already evaluated. The comparison of their WCET estimates characterizes the given sequence as positive, neutral or negative. This characterization is applied to their non-common passes, while the common passes inherit the characterization from the largest subset. For example (Figure 5), if sequence AB is evaluated as positive compared 1 A sequence of passes is denoted as ABC and the corresponding set of passes is denoted as {A, B, C} to A which in turn is neutral compared to the empty sequence, B is characterized as positive, whereas pass A remains neutral.

{ A, B, C } { A, C } { A, D } { B + , C + } { A ○ } { ∅ } { B } { C } { D } { A ○ , B + , C + , D ○ } { A ○ , B + } WCET AB < WCET A WCET A = WCET { B, D } { C, D } { A, B, D } { A, C, D } WCET ABCD < WCET AB WCET ABCD = WCET BC { B, C, D } WCET BC < WCET Fig. 5.
Example of the characterization strategy for four optimization passes. Bold sets have been evaluated, while grey have not. Optimization pass X is denoted as X + , X • ,X -when characterized as positive, neutral or negative, respectively. For each arrow (subset to superset ordering in the lattice), the corresponding variation of estimated WCET is shown (lower is better).

In case there are more than one largest subset for a given sequence, then (i) the non-common passes among all the sets and the given sequence, are characterized according to the sequence characterization, (ii) the non-common passes among the sets retain their characterization of their set and (iii) the common passes retain the most frequent characterization among the sets, with ties being resolved by the characterization of the sequence. Continuing our previous example, consider the sequence ABCD is evaluated as positive compared to {A, B} and as neutral compared to {B, C}; the sequence is characterized as neutral, its WCET is equal to WCET BC . Pass D is characterized as neutral as it is not present in any of the subsets. Passes A and C retain the characterization of their corresponding set (as the non-common part among the largest subsets) and pass B retains its characterization since it is positive in both sets.

B. Weighting scheme

The objective of the weighting scheme is to avoid passes that have frequently been observed to be neutral and promote passes that either have been frequently positive or have not been tried many times. This is achieved by setting the weight of each pass to:

W pass = N + pass max 1, N • pass × 85% + 15% (1)
where, N + pass is the number of times it has been characterized as positive among evaluated sequences, and N • pass is the number of times it has been characterized as neutral. In order to avoid convergence to local optima, we add a fixed 15%, determined experimentally, to maintain some randomness. Also note that while our weighting scheme does not include a term for negative passes, passes with frequently negative impact are avoided, since the weights are normalized in the weighted random selection.

C. Cleaning of optimization passes

In order to enhance the detection of neutral passes, we use an additional cleaning phase. This method is largely used in iterative compilation [START_REF] Chen | Deconstructing iterative optimization[END_REF], [START_REF] Martins | Clustering-Based Selection for the Exploration of Compiler Optimization Sequences[END_REF], and its impact in WCET estimation is outlined in the experimental evaluation in Section IV. The cleaning phase, after a sequence has been evaluated, generates a new sequence by removing one pass from the previous sequence. If the resulting sequence has the same or higher WCET estimate as the original one, the pass is removed for all subsequent sequences of the cleaning phase, otherwise it is kept. The cleaning phase continues to the next optimization pass, until all optimization passes have been selected.

Note that all the sequences generated and evaluated by the cleaning phase are also characterized. In this manner, not only neutral passes are identified, but also the confidence of positive (or negative) passes is re-enforced. Cleaning gives a precise characterization of each optimization, at the expense of a large runtime overhead, given that WCET analysis has to be run for every optimization in the sequence. For this reason, the cleaning phase is not applied to all optimization sequences, as further explained in Section IV.

IV. EXPERIMENTAL EVALUATION A. Experimental setup

A standard workflow for iterative compilation is used to explore optimization influence, adapted to WCET estimation, as illustrated previously in Figure 4. The platform targeted for the experimentation is a 32-bit RISC LEON3 processor (compatible with SPARC V8 instruction set) with separate 16 KB 2-way instruction and data caches. Programs are compiled using LLVM 4.0 for the SPARC architecture, using Gaisler BCC 2.0.5 implementation [START_REF]Gaisler bare-c cross-compiler system[END_REF]. The LLVM optimizer opt was compiled separately, and all its 53 optimizations passes are used in the experiments. Timing analysis is carried out by AbsInt aiT [START_REF]aiT:the industry standard for static timing analysis[END_REF] version 18.04 targeting the LEON3 architecture. aiT implements value analysis using abstract interpretation, to determine the range of values in registers, as well as static analysis of the processor micro-architecture and automatic detection of loop bounds [START_REF] Cullmann | Data-Flow Based Detection of Loop Bounds[END_REF]. The virtual unrolling factor for each benchmark is chosen as described is Section V. All experiments were conducted inside a virtual machine running Ubuntu version 18.04, on a MacBookPro with an Intel i7-7660U processor and 16 GB of RAM.

By its non standard use of compiler and analysis tool, iterative compilation tends to find corner cases causing bugs during evaluation. To circumvent those bugs the workflow includes timeouts of 60 seconds for LLVM and 120 seconds for aiT. Failures in compiler were similar to those observed in iterative compilation for average case, and accounted for less than 1% of the evaluated sequences. Failures in analysis tool were mostly due to the timing analysis requiring more time than the given timeout, or more rarely due to memory exhaustion from large virtual unrolling factor. Timeout failures were considered as a failure to obtain an estimated WCET and treated as such in the rest of the workflow.

Evaluation of the optimization selection is supported by a large selection of benchmarks from different domains: Mälardalen benchmark suite, that are reference benchmarks for WCET estimation [START_REF] Gustafsson | The Mälardalen WCET Benchmarks: Past, Present And Future[END_REF]; Polybench benchmarks [START_REF] Pouchet | PolyBench/C[END_REF] for linear algebra, physics and statistics; MiBench [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] benchmarks for its applications in security and telecommunications; and PolyMage [START_REF] Mullapudi | PolyMage: Automatic Optimization for Image Processing Pipelines[END_REF] for image processing. As this work focuses on optimization, we paid special attention to include complex kernels, which can be challenging for WCET estimation.

All benchmarks were refactored into three parts: initialization, computation and result transmission. This separation supports the objective to focus on computation optimization, with analysis carried only on the computation part. Using the computation output with result transmission is essential, otherwise the compiler could consider parts of the computation as dead code and remove them.

As part of this separation, Mälardalen benchmarks bs, cover, lcdnum and ud were removed as they do not produce output values. Polybench was the easiest to port, as it was already structured in this way. MiBench provides a large selection of benchmarks used in embedded systems, but many of them access the file system during their execution which limits analysis possibilities. In order to increase the number of large applications from different application domains, several benchmarks were heavily modified to be analyzable. The list of all benchmarks used is presented in Table II, with their estimated WCET at O0, using virtual unrolling as defined in Section V.

Four methods were used for the selection of optimization sequences, with two reference methods: random and genetic, and the two newly introduced methods association and cleaning (shortcut for association combined with cleaning). All methods use 1000 different optimization sequences for evaluation (duplicates are removed).

a) Random: This method uses sequences of random size from 1 to 50, and each optimization pass is then randomly selected.

b) Genetic: This method follows the main structure of genetic algorithms [START_REF] Conroy | Handbook of genetic algorithms by lawrence davis[END_REF]. It uses generations of 200 individuals, each individual being an optimization sequence, and each gene encoding an optimization. The first generation is created using the random method previously presented. At each generation, half of the population is kept based on the estimated WCET of its individuals. The population is then doubled using crossover, whereby two random individuals are selected and duplicated, their duplicates are split at a random position and their genes are exchanged after the split point. Mutation is applied randomly to 15% of the individuals as a change to a single optimization pass at a randomly selected position in the sequence. Estimation is ran for as many generations as needed until 1000 different individuals are evaluated. c) Association: This method is based on the association rule learning presented in Section III. It starts with 200 sequences generated using the random method. Optimizations are characterized with the proposed strategy, and weights are derived for each optimization as defined in Section III-B. The next 800 sequences are generated using a weighted random generator to select the optimizations. The model and the weights are updated after each analysis. d) Cleaning: This method is an extension of the association method. Each time a new best result is found, the sequence is cleaned as defined in Section III-C to characterize each of its optimization passes precisely. This cleaning is applied to each new best result after the first 200 sequences only. III presents the geometric mean of the best estimated WCET per benchmark for each method. All results are normalized to the best estimated WCET using the four standard optimization levels (O0 to O3).

B. Experimental results

1) Global analysis of results: Table

Geometric mean is used due to the large variation between the normalized estimated WCET to give a representative number. From these results the random method is the worst with a 16.8% improvement, and genetic third with an 17.6% improvement. Association is second with a 19.4% improvement, and cleaning brings an additional 1% to reach 20.3% of improvement over the best standard optimization level. Although there are differences in improvement for the different methods, the results motivate the use of iterative compilation in the domain of real-time systems.

The best estimated WCET per method, normalized to the best standard optimization level is detailed in Figure 6 for all benchmarks. The benchmarks present very different characteristics, with significant variations in estimated WCET as already presented in Table II, but also in sensitivity to optimizations. The worst acquired result from all four methods is an absence of improvement for benchmark 3mm, and less than 1% improvement for jacobi-1d, jfdctint and rijndael. The best improvement in estimated WCET comes to doitgen with a 74% improvement.

2) Analysis per method: In order to compare the four methods we ranked the best estimated WCET for each benchmark between the methods. Ties in estimated WCET were solved by giving all the methods in the tie the same ranking. The results of this ranking are presented in Figure 7.

The random method is clearly dominated by all the other methods, but still finds 17% of the best results. Genetic is leading with more than 43% of the best results. Association and cleaning methods are in between with 30% and 39% of the best results respectively. Both methods share a very similar algorithm, which means they explore a similar space, thus splitting the results between them. This is confirmed by observing the cumulative best and second best results, where cleaning gets the best results with 78%, followed by association with 70% and genetic with 67%.

Comparing the ranking with the geometric mean results on Table III, we observe that genetic is leading in terms of best results, but dominated on average by the association and cleaning methods. This highlights a difference between these methods, with genetic being more hit or miss, whereas others are more consistent.

Figure 8 presents the percentage of failures for each method during compilation and analysis. It highlights the particularities of each algorithm related to failures.

In the case of genetic, every failure will be filtered out at the next generation, resulting in fewer failures overall. In the case of association and cleaning, the chosen weighting does not use the negative characterization information, which means we get nearly as many failures as a random exploration.

One thing to note is that a single addition or removal of an optimization pass can turn the best sequence into a failure, which is unique to WCET estimation. This observation was established during cleaning of the best sequences, where the removal of optimizations led to one compiler and two analyzer failures, starting from the best result. As such, failure is not a good indicator for finding the best results. Evaluation of runtime per method requires particular care given the inherent variability of running on top of an operating system, inside a virtual machine. We use two measurements for runtime, with timestamps at the beginning and the end of a method to measure total runtime, and the runtime reported by aiT per analysis for analysis runtime. Both measurements are reported in seconds. To obtain reliable results we removed benchmarks with a total runtime of less than 2000 seconds, meaning less than 2 seconds per analysis. Figure 9 presents the geometric mean of the runtime across benchmarks for each method. Geometric mean was chosen to compute a meaningful runtime given the large variability across benchmarks (from 360 seconds for sqrt, which is excluded, to 34082 seconds for fdtd-2d).

The total runtime is divided into analysis runtime, as reported by aiT, and overhead runtime, as the total minus analysis runtime. We observe that runtime for all methods is dominated by the WCET analysis runtime. The overhead runtime is similar for all methods. Genetic total runtime is smaller than the others, which is correlated to the number of failures presented previously. This can be explained by the longer runtime resulting from failures caused by timeouts.

Figure 10 presents the distribution of lengths for the best sequence of each benchmark across all four methods, before and after cleaning the sequence. Specifically, each sequence and associated benchmark was evaluated using cleaning to remove all neutral and negative optimizations. Comparing the length of the best sequence before and after cleaning, we can observe that a significant amount of optimization passes -in the best sequences -are not effectively useful. Based on this observation one might want to use short sequences to find the best results. We explored this direction, but yielded results 10% worse than random. We expect that this is due to the fact that using a large sequence increases the chances to have an optimization with a positive influence on the estimated WCET.

3) Sensitivity to benchmark: As illustrated in the previous section, iterative compilation brings significant improvements to estimated WCETs. One would be tempted to derive general (benchmark agnostic) rules to improve WCET estimates, without going through the lengthy process of iterative compilation. In this section we investigate this opportunity in terms of sequence, optimization and finally learnt model.

Figure 11 presents the best estimated WCET for each benchmark using the best optimization sequences from other benchmarks, as they were acquired in the previous section. To evaluate the specialization of sequences to a given benchmark we use a leave-one-out cross validation, whereby each sequence is used to estimate the WCET for all benchmarks except the one it was found with. Using cross-validation allows us to check if the sequence brings improvement specifically to this benchmark, or if it can considered general across multiple benchmarks.

0.0 0.5 The geometric mean of the best estimated WCET for the cross validation is 0.823, 4% worse than the geometric mean of the best estimated WCET across all methods of 0.786. In terms of ranking, cross-validation gets 20% of the best results. This is only slightly better than random, which confirms our hypothesis that sequences are tailored to specific benchmarks.

Figure 12 is based on the best sequence for each benchmark across all methods, and presents the percentage of sequences containing a given optimization pass, after cleaning was applied to remove neutral and negative optimizations.

0% 25% 50% 75% -bb-vectorize -constmerge -die -globaldce -lcssa -loop-simplify -loweratomic -lowerinvoke -memcpyopt -mergereturn -prune-eh -strip-dead-debug-info -strip-dead-prototypes -strip-debug-declare -tailcallelim -always-inline -constprop -dce -deadargelim -functionattrs -mergefunc -sccp -sink -globalopt -loop-deletion -lowerswitch -strip -strip-nondebug -adce -argpromotion -break-crit-edges -dse -loop-unswitch -reassociate -loop-extract-single -reg2mem -jump-threading -partial-inliner -mem2reg -ipsccp -loop-reduce -ipconstprop -codegenprepare -indvars -licm -loop-extract -loop-unroll -inline -gvn -instcombine -simplifycfg -sroa -loop-rotate
Sequences containing optimization We observe that best results are brought by only a subset of optimizations, with -loop-rotate, -sroa and -simplifycfg being present in more than 50% of the best sequences. On the contrary, we see that many optimizations are never present in best results, which hints at their neutral or negative effect on WCET estimates.

Figure 13 presents the percentage of neutral characterizations for each optimization. The presented characterizations are based on the 1000 sequences per benchmark, obtained using the cleaning method, and averaged across benchmarks using an arithmetic mean. The arithmetic mean was used due to the characterization similar nature and range. The optimizations are presented in the same order as in Figure 12, where the percentage of their presence in best sequences was illustrated. This ordering is used to relate the neutral characterization with the final best result.

0% 10% 20% 30% -bb-vectorize -constmerge -die -globaldce -lcssa -loop-simplify -loweratomic -lowerinvoke -memcpyopt -mergereturn -prune-eh -strip-dead-debug-info -strip-dead-prototypes -strip-debug-declare -tailcallelim -always-inline -constprop -dce -deadargelim -functionattrs -mergefunc -sccp -sink -globalopt -loop-deletion -lowerswitch -strip -strip-nondebug -adce -argpromotion -break-crit-edges -dse -loop-unswitch -reassociate -loop-extract-single -reg2mem -jump-threading -partial-inliner -mem2reg -ipsccp -loop-reduce -ipconstprop -codegenprepare -indvars -licm -loop-extract -loop-unroll -inline -gvn -instcombine -simplifycfg -sroa -loop-rotate

Neutral characterizations

Fig. 13. Percentage of neutral characterizations per optimization across all benchmarks based on cleaning results.

We observe a small inverse correlation between the neutral characterization and its presence in the final result. This confirms that optimizations with neutral characterizations are on average not providing benefit to the best result. One exception is optimization -loop-reduce which has the highest neutral characterization, but is still present in 25% of best sequences. It may be caused by the fact that the optimization by itself is providing no gain (i.e. neutral), but combined with another optimization provides significant improvement.

V. SELECTION OF THE AIT'S VIRTUAL UNROLLING

FACTOR

The aiT timing analysis tool uses a parameter named virtual unrolling factor to trade-off WCET estimation accuracy with analysis complexity (Section V-A). The automatic selection of this parameter in our proposal is presented in Section V-B.

A. Virtual unrolling in aiT and its impact on WCET estimates Analysis of routines in aiT is achieved per context, e.g. a calling context for a routine with specific parameter values. Those contexts are used to restrict the possible values for each register. Contexts are used for all analyses (value analysis, loop bound analysis, cache analysis, etc).

The virtual unrolling factor option defines the number of contexts used to analyze loops. This concept is similar to loop peeling in compilers, which extracts the first N iterations of a loop. Unrolling is virtual, that is no code transformations are performed, and unrolling is only used in the timing analysis. In aiT, higher virtual unrolling translates into more loop contexts, with a different context computed for each of the first N iterations of the loop. Virtual unrolling is essential for loop bound analysis: a low virtual unrolling factor may result in a failure in finding the loop bound of some loop and, thus, in failure of the whole timing analysis. A high unrolling factor in contrast improves the precision of value analysis and consequently the quality of estimated WCETs.

The downside of a more accurate analysis is a longer analysis time due to the additional contexts. This extra time does not necessarily increase linearly with the virtual unrolling factor. In the case of kernels with two nested loops, virtually unrolling the outer loop creates multiple contexts, for each of which the inner loop is also virtually unrolled. Image processing kernels use triple nested loops, which could create a cubic complexity for virtual unrolling. This is an acute problem in iterative compilation in which WCET estimation has to be done for a large number of optimization sequences for each application. To investigate this influence we ran WCET estimations for code compiled with standard optimizations levels (O0 to O3) for different unrolling factors. Results for six of the selected benchmarks are plotted in Figure 14 for the estimated WCET, and Figure 15 for the runtime of the analysis. Analysis failures are represented with an estimated WCET equal to -1. We observe that increasing the unrolling factor improves the estimated WCET for some benchmarks (e.g. gemm, lu), but may also provide no noticeable improvement on larger virtual unrolling factors (e.g. harris, matmult). In terms of runtime, increasing the virtual unrolling factor increases the analysis runtime, whether there is improvement in the estimated WCET (e.g. gemm, lu) or not (e.g. adpcm decoder, harris). In some cases the virtual unrolling may completely unroll the loop (e.g. doitgen, matmult), after which there is neither gain in estimated WCET nor additional runtime.

B. Selection of virtual unrolling factor

Our objective is to maximize the quality of the estimated WCET, by selecting an unrolling factor tailored to each specific program, with a small overhead for its selection. We define this quality in two ways:

• Tightness: the estimated WCET is as close as possible to the actual WCET. • Fidelity: the ordering of estimated WCETs for any pair of optimization sequences matches the one of their actual WCETs. For example, if W CET ABC < W CET BCD for estimated WCETs at virtual unrolling factor 2 and W CET ABC > W CET BCD for actual WCETs, virtual unrolling factor 2 has a low fidelity. Validating both criteria would require a WCET oracle which is, in practice, impossible to acquire. For this purpose, we use the estimated WCET with the largest virtual unrolling factor as an indicator of the actual WCET.

Referring back to Figure 14, we have separated the results for the standard optimizations and 100 random sequences repeated for each virtual unrolling factor. For tightness, we observe that the standard optimizations and random sequences follow the same trend for each benchmark. An improvement in estimated WCET is visible on the standard optimization levels, which means standard optimization levels are a good indicator for a potential gain to be obtained by increasing the virtual unrolling.

In order to evaluate the fidelity of the estimated WCET we compute the rank correlation at each virtual unrolling factor using Kendall's τ correlation coefficient [START_REF] Javaid | Fidelity metrics for estimation models[END_REF]. Rank correlation is a way to evaluate the fidelity of a ranking compared to a reference ranking. It is used in design space exploration to evaluate the fidelity of a model compared to the actual system. In this work we use it to evaluate the quality of the ordering at a given unrolling factor compared to our reference, a virtual unrolling of 32. Results of this analysis are presented in Figure 16, a coefficient of 1 being a perfect ranking. We observe that we reach good rankings when the estimated WCET reaches a plateau in Figure 14. This means that an absence of variation in the estimated WCET is an indicator that a given unrolling factor provides a high fidelity. Based on the previous observations, we propose in Algorithm 1 the selection of the unrolling factor for a program. For efficiency considerations, we rely on standard optimizations as an indicator to select the unrolling factor. In addition, we limit the unrolling factor to the largest one that improves the estimated WCET, i.e. when reaching a plateau. Finally, we limit the unrolling factors explored to {2, 4, 8, 16, 32}. The threshold θ to consider an improvement is set to 0.9, meaning a 10% improvement. To further speed up exploration, an additional condition is added to only consider WCET estimations with a runtime smaller or equal than 30 seconds. This limits the virtual unrolling for benchmarks adi, fdtd-2d, FFT, floyd-warshall, heat-3d, jacobi-2d, nussinov, harris, pyramid blend and seidel-2d. The selected virtual unrolling factor for each benchmark is presented in Table IV.

VI. RELATED WORK

Information on the flow of control of applications improves the tightness of WCET estimates. Beyond loop bounds, [START_REF] Knoop | Replacing conjectures by positive knowledge: Inferring proven precise worst-case execution time bounds using symbolic execution[END_REF] or annotations added by the application developer [START_REF] Kirner | WCET Analysis: The Annotation Language Challenge[END_REF].

Compiler optimizations are often not used when designing hard real-time systems. One reason is the increased difficulty of automatic flow fact extraction using static analysis techniques on highly optimized code as compared to nonoptimized code. Another difficulty, arising when flow information is given through developer-provided annotations is to safely transform them along with code optimizations. Finally, the certification of optimizing compilers is known to be difficult because of the inherent complexity of optimizing compilers [START_REF] Leroy | Formal certification of a compiler back-end, or: programming a compiler with a proof assistant[END_REF].

However, using optimizing compilers is key for improved performance, both in the average case [START_REF] Triantafyllis | Compiler optimization-space exploration[END_REF] or in the worst case [START_REF] Li | Traceability of flow information: Reconciling compiler optimizations and wcet estimation[END_REF], [START_REF] Puaut | Finegrain iterative compilation for wcet estimation[END_REF]. Several attempts have been made in the past to reconcile compiler optimizations and WCET estimation (that require safe and precise estimation of flow information).

A first research direction is to design WCET-aware compiler optimizations, that are known to improve WCET estimates, and have a well-known impact on flow information. Examples of WCET-directed compiler optimizations aim at optimizing the worst-case behavior of the memory hierarchy [START_REF] Lokuciejewski | Wcet-driven cache-based procedure positioning optimizations[END_REF], [START_REF] Suhendra | WCET centric data allocation to scratchpad memory[END_REF] branch predictors [START_REF] Bodin | A wcet-oriented static branch prediction scheme for real time systems[END_REF], or perform WCET-aware loop transformations [START_REF] Lokuciejewski | Combining worst-case timing models, loop unrolling, and static loop analysis for wcet minimization[END_REF]. In contrast to these approaches, we take benefit of the full set of compiler optimization from mainstream compilers, designed for average-case performance, and automatically select the ones that minimize WCET estimates. In addition, in contrast to most related work that perform optimizations along the worst-case execution path (WCEP) our technique is a black-box technique that does not use the WCEP, and therefore does not have to handle WCEP variations.

When using source-level flow annotations for WCET estimation, these annotations have to be transformed together with code transformations [START_REF] Li | Traceability of flow information: Reconciling compiler optimizations and wcet estimation[END_REF], [START_REF] Engblom | Facilitating worst-case execution times analysis for optimized code[END_REF]- [START_REF] Lokuciejewski | Approximating pareto optimal compiler optimization sequencesa trade-off between wcet, ACET and code size[END_REF]. From an engineering perspective, tracing flow information in a compiler, albeit opensource, is a time-consuming task and the flow fact traceability code has to be maintained and be consistent alongside the code of the optimizations.

A last class of approaches, is to rely on mainstream compilers and automatically select optimizations that minimize the WCET. Many research, surveyed in [START_REF] Ashouri | A survey on compiler autotuning using machine learning[END_REF], has been devoted to the automatic selection of the best set of compiler optimizations and the best ordering of applied optimization passes to optimize average-case performance. Compared to this rich set of techniques (see for example [START_REF] Cooper | ACME: adaptive compilation made efficient[END_REF], [START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF]) the metric we wish to optimize is worst-case performance, and not average-case performance. To our best knowledge, only two recent studies have focused automatic selection of compiler optimization for WCET optimization. The study presented in [START_REF] Becker | Optimizing worst-case execution times using mainstream compilers[END_REF], uses feedback-directed compilation to optimize WCET estimates, by feeding the compiler with WCET-oriented profile data. In contrast to [START_REF] Becker | Optimizing worst-case execution times using mainstream compilers[END_REF], our work does not require any support from the compiler. The work presented in [START_REF] Puaut | Finegrain iterative compilation for wcet estimation[END_REF] automatically selects compiler optimizations and their ordering to minimize WCETs, using random or genetic techniques. As compared to [START_REF] Puaut | Finegrain iterative compilation for wcet estimation[END_REF] that suggests a fine-grain approach (per loop, using outlining) our work selects the same optimization sequence for all files, to reduce the search space, and the technique used for optimization selection outperforms both random and genetic search algorithms. In addition, compared to these two works, our research also automatically selects the best parameters for WCET estimation (the virtual unrolling parameter of the aiT timing analysis tool, that allows to find tradeoffs between analysis precision and analysis run time).

VII. CONCLUSION

In this work, we have outlined the challenges raised when using mainstream compilers to improve the estimated WCETs of programs. In particular, the experimental evaluation, over 46 varied benchmarks using an industrial static WCET estimation tool, shows that optimizations are application-specific, have uncertain impact on estimated WCETs and often render timing analysis impossible. To address these challenges and obtain improved WCET estimates within reasonable time, we proposed a novel learning approach that characterizes the impact of individual optimization passes in order to construct an optimization sequence that minimizes the estimated WCET. Results show that WCET estimates are reduced on average by 20.3% using the proposed technique, as compared to the best compiler optimization level applicable.

As future work, we consider sequence construction upon blocks of passes to take advantage of optimization passes interaction, and a more efficient identification of neutral passes than the time-consuming cleaning. An open question we would like to answer is whether the effect of optimizations on the estimated WCET could be predicted based on features observed in the application source/binary code. This would enable reusability of the learnt models for other applications and, thus, speed-up the exploration. Such directions are inline with compiler optimization heuristics [START_REF] Kulkarni | Automatic construction of inlining heuristics using machine learning[END_REF] and constitute a significant challenge.

Fig. 1 .

 1 Fig. 1. Percentage of compiler and analyzer failures for 1000 random generated sequences of size 10 to 80.

Fig. 2 .

 2 Fig.2. Distribution of WCET estimates on 1000 random generated sequences normalized to the estimated WCET at O0, excluding failed analyses.

Fig. 3 .

 3 Fig. 3. Distribution of the best 100 estimated WCET for 1000 random generated sequences of size 10 to 80.

Fig. 4 .

 4 Fig. 4. Iterative compilation workflow

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig.6. Best estimated WCET per method normalized to the best standard optimization (O0 to O3)

Fig. 9 .

 9 Fig. 9. Geometric mean of runtime for 1000 analyses per method.

Fig. 10 .

 10 Fig. 10. Length of best optimization sequence per benchmark across methods originally and after cleaning.

Fig. 12 .

 12 Fig. 12. Percentage of best sequences overall containing an optimization after cleaning.

Fig. 14 .

 14 Fig.[START_REF] Mullapudi | PolyMage: Automatic Optimization for Image Processing Pipelines[END_REF]. WCET estimation of standard optimizations and 100 random generated sequences for virtual unrolling factor from 2 to 32.

Fig. 15 .

 15 Fig.[START_REF] Conroy | Handbook of genetic algorithms by lawrence davis[END_REF]. WCET estimation runtime of standard optimizations and 100 random generated sequences for virtual unrolling factor from 2 to 32.

ACKNOWLEDGMENT

This work was funded by European Union's Horizon 2020 research and innovation program under grant agreement No 688131, project Argo. The authors would like to warmly thank Kelig Lesourd for his work on the experimental evaluation, and the anonymous reviewers for their helpful comments on earlier drafts of this paper.