Denis Geraads
email: denis.geraads@evolhum.cnrs.fr

Large Mammals from the late Miocene of Çorakyerler, Çankırı, Turkey

Keywords: late Miocene, Turkey, Mammalia, hominid site

I provide here a brief account of the large mammal fauna from the hominid-bearing locality of Çorakyerler near Çankırı, Turkey. It is dominated by the rhino ?Acerorhinus, an Hipparion close to H. dietrichi or H. prostylum, and spiral-horned antelopes, mainly Majoreas and Oioceros rothi. Antelopes of the Pachytragus group, other spiral-horned forms, and gazelles, are remarkably rare. There is no doubt that Çorakyerler is a Turolian site, but its faunal assemblage is unlike that of the classical Greek sites.

Introduction

The locality of Çorakyerler was first reported by BECKER-PLATEN et al. (1975), who assigned it to the Vallesian on the basis of its large mammal fauna, which included, according to their identifications: Choerolophodon pentelici; Hipparion sp. (very large); Hipparion sp. Prostrepsiceros sp. Although not stated by these authors, the main basis for this age determination was obviously Listriodon, a genus unknown after the earliest Vallesian.

More recently, in 1992, Prof. Erksin Güleç from the Dil ve Tarih Coğrafya Fakültesi in Ankara invited me to take part in her researches on several Middle and Upper Miocene sites that she was surveying or excavating. On my suggestion, she concentrated her activities on the site of Çorakyerler (E 33°38'10", N 40°37'), and the excavations that were conducted there by Ayla Sevim resulted in the discovery of a fossil hominid, first reported by [START_REF] Sevim A | A new late Miocene hominid from Turkey[END_REF] and later called Ouranopithecus turkae GÜLEÇ, SEVIM, [START_REF] Pehlevan | Corakyerler (Cankırı) Rhinocerotidae (Mammalia) buluntularının değerlendirilmesi[END_REF][START_REF] Güleç E | A new great ape from the late Miocene of Turkey[END_REF] provided a preliminary faunal list of the large mammals, together with that of the rodents studied by [START_REF] Ünay E | Rodents from the Upper Miocene Hominoid locality Corakyerler (Anatolia)[END_REF], who tentatively assigned the locality to MN11, while noting that correlations are difficult. According to [START_REF] Güleç E | A new great ape from the late Miocene of Turkey[END_REF], the fossil-bearing unit consists of pale-green mottled marl that forms the lower part of a thick succession of continental red beds interfingering with shallow lake deposits.

Most of the large mammals remain unpublished, which is most unfortunate given the importance of the site, which has yielded the latest pre-human hominid so far known in Turkey. To fill this gap, I provide in the present paper a brief description of the material collected up to 2001.

Materials and methods

The fossil material from Çorakyerler was studied in the Dil ve Tarih Coğrafya Fakültesi in Ankara, but is now stored in the Çankırı Museum. Lower teeth are in lower case, upper teeth in upper case. Measurements are in millimeters.

Systematic paleontology

PROBOSCIDEA -Choerolophodon pentelici. This is a common species in the Miocene of the Eastern Mediterranean, especially Turkey, while other species of the same genus are known from the Siwalik, Kenya, and North Africa. The genus is already present in the Middle Miocene, but rare. The best specimen from Çorakyerler is a juvenile mandible that has an elongated gracile rostrum, almost in line with the corpus, a derived feature, but inclination relative to the tooth-row is difficult to appreciate in this incomplete specimen, as it is also at Kemiklitepe-D (KTD -TASSY 1994). This mandible also includes a well-preserved dp4 (Fig. 1A), of which the comparative measurements are given in Table 1. Some authors [START_REF] Tassy P | Les Gisements de Mammifères du Miocène supérieur de Kemiklitepe, Turquie: 7. Proboscidea[END_REF][START_REF] Markov | The fossil proboscideans of Bulgaria and the importance of some Bulgarian findsa brief review[END_REF]) recognize only one species in the late Miocene of the Aegean region, whereas others [START_REF] Sanders | Proboscidea[END_REF][START_REF] Markov | The Turolian proboscideans (Mammalia) of Europe: preliminary observations[END_REF][START_REF] Konidaris | Late Miocene Proboscidea (Mammalia) from Macedonia and Samos Island, Greece: preliminary results[END_REF]) distinguish two species, Ch. anatolicus [START_REF] Ozansoy F | Etude des gisements continentaux et des Mammifères du Cénozoïque de Turquie[END_REF] from the Vallesian and earliest Turolian being the ancestor of the more common Turolian Ch. pentelici. In any case, distinction is not easy on incomplete materials, but several attempts have been made [START_REF] Gaziry | Jungtertiäre Mastodonten aus Anatolien (Türkei)[END_REF][START_REF] Tassy P | Les Gisements de Mammifères du Miocène supérieur de Kemiklitepe, Turquie: 7. Proboscidea[END_REF], GERAADS et al. 2005a) to relate the size of Choerolophodon cheek-teeth to their geological age, but Table 1 shows that this trend towards size increase is far from obvious on dp4. On the whole, the dp4 from Çorakyerler is rather narrow, and this is hard to reconcile with a DP4 from Çorakyerler reported by GAZIRY (1976, Fig. 2), which is near the upper limit of the size range of the MN9-MN12 representatives of this species (TASSY 1994 -Fig. 1), but which I have not seen. On the whole, the best fit is somewhere between the latest Vallesian, early Turolian or beginning of middle Turolian.

There are also two astragali, presumably of Choerolophodon, one of which is from a juvenile animal, but there is no evidence of another taxon. RHINOCEROTIDAE -Acerorhinus ? n. sp. The most common rhino of Çorakyerler is represented by several more or less complete skulls, mandibles, and post-crania. In terms of biomass, it is certainly the dominant large mammal. It was assigned by [START_REF] Pehlevan | Corakyerler (Cankırı) Rhinocerotidae (Mammalia) buluntularının değerlendirilmesi[END_REF] to Chilotherium kowalevskii, and its tooth morphology is indeed very similar to that of this species, best known from Grebeniki in Ukraine where it is represented by numerous beautiful remains [START_REF] Pavlow M | Mammifères tertiaires de la Nouvelle Russie. 2° partie. Aceratherium incisivum, Hipparon, Proboscidaea, Carnivora[END_REF], but also reported from some Turkish localities [START_REF] Sickenberg O | Die Gliederung des höheren Jungtertiärs und Altquartärs in der Türkei nach Vertebraten und ihre Bedeutung für di internationale Neogen-Stratigraphie[END_REF]. The upper premolars have a long curved protoloph that connects the transversely oriented metaloph, enclosing a central fossa blocked by a high bridge located very lingually (Fig. 1D). The crochet is strong on all upper cheek-teeth (although it vanishes with wear), and the antecrochet long on the molars, although perhaps less so than in C. kowalevskii. There are, however, some significant differences with this species. At Çorakyerler, the tooth-row is distinctly more anterior, as the orbit reaches only the level of the back of M2 (in a young adult) or the front of M3 (in an older specimen), whereas it reaches M2 or M1 in C. kowalevskii; similarly, the bottom of the nasal notch is above P4 at Grebeniki, above M1 at Çorakyerler (Fig. 1C). The orbit is not as high as at Grebeniki (a difference with typical Chilotherium). Furthermore, while at Grebeniki the mandibular symphysis is broad, with very robust incisors inserted far apart as is usual in Chilotherium (PAVLOW 1913, pl.5, fig.32), the incisors are not very large at Çorakyerler, and are inserted closer to each other (Fig. 1F). They are wider apart on another, imperfectly preserved mandible (Fig. 1E), but even on this specimen the symphysis is not as distinctly broadened as in typical Chilotherium. It may be that this specimen represents a different species, perhaps of a primitive Chilotherium, but since all upper teeth display the same features, it is more parsimonious to assume that only one species is present. As the mandibular features match better those of Acerorhinus, a genus based on Aceratherium zernowi from Sebastopol (BORISSIAK 1914) but also described by FORTELIUS et al. 2003 from Sinap and[START_REF] Geraads | Rhinocerotidae from the late Miocene of Bulgaria[END_REF] from Bulgaria, the Çorakyerler form should probably be assigned to this genus, but no known species of Acerorhinus display the cheek-tooth morphology seen at Çorakyerler. Acerorhinus zernowi has simple teeth; the form from Kavakdere that [START_REF] Fortelius M | Rhinocerotidae (Perissodactyla)[END_REF] described as Acerorhinus sp.nov. and the Acerorhinus from Garkin have a blocked central fossa on the premolars, but the connection is much less lingual. A new species name should probably be created for the Çorakyerler rhino, which we tentatively refer to Acerorhinus, but a detailed study of late Miocene Turkish rhinos and a clarification of the differences between Acerorhinus and primitive Chilotherium are badly needed.

Ceratotherium neumayri. [START_REF] Pehlevan | Corakyerler (Cankırı) Rhinocerotidae (Mammalia) buluntularının değerlendirilmesi[END_REF] described and illustrated some nice specimens, including a complete skull, which he assigned to this taxon. The general shape of the skull, especially that of the nasals, the rather ventrally located orbit, the lack of protocone constriction on the molars, all show that his identification is correct. The occipital crest extending caudally far behind the condyles and the forwardly located tooth-row are clear differences with modern Diceros, a genus to which this species is sometimes erroneously referred. A juvenile maxilla (PEHLEVAN 2006, pl.2) is also typical of this species by the lack of postfossette on DP2 and the presence of a crista on DP3. EQUIDAE -Although not rare, the material is rather fragmentary and many specimens have undergone the plastic deformation that is so common at Çorakyerler. The rather confused state of our knowledge of late Miocene hipparions does not help ascertaining their relationships.

Hipparion cf. prostylum. An incomplete, poorly preserved skull with the tooth-row and orbit shows the posterior border of an ante-orbital fossa located rather dorsally, far from the orbit (about 40 mm). Another specimen, with P2-P3 and the front teeth (Fig. 1B), is remarkable by the extremely short muzzle, the canine being located only 36 mm from P2. These features, plus the oval protocon, agree well with the species H. dietrichi, known from a number of sites in the Balkano-Iranian province, most of them of early Turolian age, but apparently extending into the middle Turolian (KOUFOS 1987a & b;VLACHOU, KOUFOS, 2002;[START_REF] Koufos | Equidae (Mammalia, Perissodactyla) from the late Miocene of Akkasdağı, Turkey[END_REF][START_REF] Geraads D | Upper Miocene mammals from Strumyani, South-Western Bulgaria[END_REF]. However, the incisor arch is more convex and the snout is slightly broader than usual in this species (L. Hristova, pers. comm.); an alternative identification would be Hipparion prostylum, a species defined in the Turolian of Mont Lubéron, France , and also present at Maragha. Probably of the same species are some lower tooth-rows, such as ÇO-212 (Fig. 2B; p2-p4 = 70; m1-m3 = 69; p2-m3 = 136) and ÇO-94, with heavily worn teeth (p2-p4 = 66.5; m1-m3 = 64; p2-m3 = 131.5).

Deformation and crushing of most postcranials make measurements difficult, but it is likely, although less obvious than one might have expected, that two species are represented.

Table 2 shows the main measurements of the metatarsals.

These metatarsals might well be included within a single species but, surprisingly, the three metacarpals display a wider range of proportions, the smallest one being only 193 mm long with a width of shaft of 22.3+, in contrast to respectively 238 and 29.5 for the largest one. This latter specimen at least probably belongs to the next species.

"Hipparion" sp. The only specimen that definitely does not belong to the above mentioned species is a lower tooth-row ÇO-220 (Fig. 2A; p2-p4 = 80; m1-m3 = 70; p2-m3 = 154). It is larger than the previous form, the premolars are relatively longer and thicker, but the main difference is that the metastylid, of circular shape, is connected to the center of the 'double boucle' by a very long, narrow bridge, both on the molars and premolars. No other specimen shows this morphology, but it is so distinct from that of other specimens that I have little hesitation in referring this specimen to another species. SUIDAE -Microstonyx major. Two skulls and several other specimens can be referred to a suid of the M. major / erymanthius group. Comparative measurements of the teeth (Fig. 3) show that the form from Çorakyerler is rather large. Several attempts have been made (e.g., [START_REF] Kostopoulos | Contribution to the study of Microstonyx: evidence from Bulgaria and the SE European populations[END_REF][START_REF] Liu L | Suidae (Mammalia, Artiodactyla) from the late Miocene of Akkasdağı, Turkey[END_REF] to relate the size of this species (as expressed by that of the third molars) to geological age, but results are disappointing. Figure 3 shows that, although some differences can be noted (e.g., the teeth from Dorn-Dürkheim are narrow), no general trend is obvious; for instance, the variation at Pikermi virtually encompasses that of all other sites combined [START_REF] Geraads D | Upper Miocene mammals from Strumyani, South-Western Bulgaria[END_REF]). The same is true of the development of the m3 talonid, another feature that might be expected to evolve with time. At the present time, the metric trends (if any) in this (or these) lineage(s), and the distinctive features between M. major and M. erymanthius remain obscure, and the basis for the assignment of the various populations to either species (VAN DER [START_REF] Van Der | Microstonyx (Suidae, Artiodactyla) from the Upper Miocene of Hayranlı-Haliminanı, Turkey[END_REF], mysterious.

The symphysis is long and narrow, with long diastemas between i3 and c, and between c and the first premolar; it is thus very different from that of Hippopotamodon antiquus, a species present in the Vallesian (GERAADS et al. 2005a, Fig. 10J), and this lengthening of the symphysis is certainly a derived feature. VAN DER [START_REF] Van Der | Microstonyx (Suidae, Artiodactyla) from the Upper Miocene of Hayranlı-Haliminanı, Turkey[END_REF] paid special attention to the evolution of the incisors in Microstonyx; according to them, it is marked by the lengthening of I2 (or at least increase of its L/W ratio) in connection with the reduction of i3.

There are well-preserved upper and lower incisors at Çorakyerler but, unfortunately, they are much worn (indeed, more worn than the cheek-teeth). The upper I2 does not look very long, but the lower i3s are decidedly small and short, hardly reaching farther rostrally than the base of i2. Although a definite conclusion is hard to reach, the characters of the symphysis point to an age certainly later than the Vallesian; if size increased during the Turolian, a middle Turolian age is even more likely than an early Turolian one.

Nothing suggests the occurrence of Listriodon, a mainly Middle Miocene Suid, previously reported from Çorakyerler [START_REF] Sickenberg O | Die Gliederung des höheren Jungtertiärs und Altquartärs in der Türkei nach Vertebraten und ihre Bedeutung für di internationale Neogen-Stratigraphie[END_REF], probably by mistake; as it is hard to confuse with anything else, it is likely that some mixing of collections occurred. CERVIDAE -Pliocervus sp. A fragmentary antler in MTA probably belongs to this genus known from Spain, France, Greece and the Northern Black sea, but not previously reported from Turkey. GIRAFFIDAE -Giraffids are not rare at Çorakyerler but, as usual, they are mostly represented by teeth and postcranials. Three species are almost certainly present.

Bohlinia cf. attica. This relative of the modern giraffe has much lengthened limbs, which allow easy identification. A metacarpal reached a length of c. 680 mm, similar to that of other Bohlinia specimens (review in GERAADS et al. 2005b). Some other limb bones probably belong to the same form. The species, or at least a close relative, is known as early as the late Vallesian (Ravin de la Pluie), until the latest Miocene at least. Palaeotragus cf. rouenii. Another metacarpal is similarly long and slender, but much smaller (length = 450; width of shaft = 35; distal W = 58.3), and agrees closely with P. rouenii, a relatively common species restricted to the Turolian.

Palaeotragus cf. quadricornis. The rear part of a skull has a short, conical horn with a rather square cross-section, located far from the occipital, inserted rather vertically, and located very far from its counterpart above the orbit (Fig. 4C). The occipital crest is broad and sharp. These characters are totally unlike those of the similar-sized Bohlinia (see, e.g., GERAADS 2009), but match those of the paleotragines; however, although anatomically similar, this specimen is much larger than P. rouenii from the Aegean region or P. microdon from China, being closer in size to the species described as P. expectans, P. coelophrys and P. quadricornis, which remain poorly known and are in bad need of revision [START_REF] Bohlin B | Die Familie Giraffidae[END_REF].

Thus, in spite of being the best giraffid specimen from Çorakyerler, this incomplete skull provides no biochronological indication. BOVIDAE -Miotragocerus (Pikermicerus) sp. A complete skull with the first cervical vertebrae is one of the most complete specimens from Çorakyerler (Fig. 4A) but is, unfortunately, strongly crushed transversely, preventing observation of the fronto-parietal area [START_REF] Spassov | Tragoportax Pilgrim and Miotragocerus Stromer (Mammalia, Bovidae) from the Turolian of Hadjidimovo, Bulgaria, and a revision of the Late Miocene Meditenanean Boselaphini[END_REF]. The small size, strongly convex lateral profile of the braincase, horn-cores closely approaching anteriorly, and long premolars relative to the molars, all support an assignment to the genus Miotragocerus (sensu SPASSOV, GERAADS 2004). The horns are inserted rather far from the orbits on long pedicles, they are much compressed transversely, long and slender, almost straight and parallel in front view (but divergence and / or curvature may have been reduced by crushing), moderately curved in lateral view, and show a strong demarcation at about 2/3 of their length, where the section changes to nearly circular; as in many late Miocene boselaphins.

Measurements: length from P2 to occipital crest = 230; length from M3 to back of condyles = 108; length of horn-core along anterior curve = 220; diameters of horn-core at base: 45.7 x 22; length of premolar row = 44.2; length of molar row = 53.8

The systematics of late Miocene boselaphins of the Tragoportax-Miotragocerus group, which were very common from Spain to India and Kenya in the late Miocene, is still imperfectly understood, and I prefer not to attempt a species identification, hence no biochronological conclusion; KÖHLER (1987) identified the Çorakyerler as Tragoportax gaudryi, but this not entirely satisfactory, as the horn-cores are longer and more slender than usual in this species.

Tragoportax ? sp. It may be that this genus is also represented at Çorakyerler by a skull fragment with the base of a horn-core of a very young individual. cf. Prostrepsiceros sp. I tentatively assign a fragment of horn-core to this genus.

Criotherium ? sp. An incomplete horn-core is reminiscent of this genus, best known from Samos, but also present at Kemiklitepe-D and probably (as a different species) at Kalimantsi (GERAADS, SPASSOV 2008, and refs therein), thus wholly of Turolian age.

Majoreas cf. woodwardi. This is one the most common species at Çorakyerler, together with Oioceros rothi. Numerous horn-cores and frontlets are known, but no specimen includes large parts of the skull. The horn-cores (Fig. 4B) are always twisted on their axis and spiraled, but variably so; some display only a weak curvature, resembling Nisidorcas, while others describe a clear spiral, resembling Prostrepsiceros; correlation with size is not perfect, but on the whole there is no doubt that spiralization increases with size. The inter-frontal suture is often fused and elevated in its posterior part. The main axis of the horn-core crosssection is strongly oblique relative to the sagittal plane; there is no anterior keel at base, but it is better expressed upwards, and may become strong at tip. There is no posterior keel. This form is certainly close to the Sinap form that OZANSOY (1965) called Palaeoreas elegans, but as it is probably not closely related to P. lindermayeri, type-species of this genus, I ascribe it to Majoreas, a name erected by [START_REF] Kostopoulos | Revision of some late Miocene spiral horned antelopes (Bovidae, Mammalia)[END_REF] for Prostrepsiceros woodwardi PILGRIM and HOPWOOD, 1928, whose type-specimen is the Samos frontlet BMNH M4192. [START_REF] Kostopoulos | Revision of some late Miocene spiral horned antelopes (Bovidae, Mammalia)[END_REF] considered the latter species to be descended from M. elegans from Sinap. I shall follow his interpretation, although I believe that these forms differ less from Prostrepsiceros zitteli that he thought; definite conclusions are hard to draw, because M4192 is not well preserved, and the Sinap material very fragmentary. On the whole, however, the evolutionary stage of the Çorakyerler form suggests an age close to that of Kemiklitepe-D.

Gazella sp. ? A single, small horn-core (basal diameters: 16.1 x 14.5) might represent a gazelle, as its strong inclination backwards suggests that it suffered some dorsoventral postmortem crushing, which might explain its apparent anteroposterior compression. It resembles G. capricornis, and especially the small gazelle from Kemiklitepe-D (BOUVRAIN 1994) but a species identification would be risky.

Oioceros rothi. This species is almost as common as Majoreas. Its type-locality is

Pikermi, but it is also known in Macedonia (FYROM), Bulgaria, and other localities in central Turkey, mainly of late MN11/MN12-equivalent age [START_REF] Köhler M | Boviden des türkischen Miozäns (Känozoikum und Braunkholen der Türkei. 28)[END_REF]. It is distinctly larger than O. atropatenes, a species known only from Maragha (KOSTOPOULOS in press, and refs therein). Figure 5 shows that the Çorakyerler horn-cores are smaller than those from Küçükyozgat, but I will not propose any interpretation of this difference, especially because the specimens from Çorakyerler measured by [START_REF] Köhler M | Boviden des türkischen Miozäns (Känozoikum und Braunkholen der Türkei. 28)[END_REF] are also large.

The range of morphological variation in the horn-cores is wide (Fig. 6); it concerns the length, amount of torsion, depth of the lateral groove and strength of keel, so that the extremes might have been assigned to different taxa, but the presence of all intermediate forms prompts me to include them all in the same species. Most specimens are twisted on their axis, only the largest ones describing a more open curve. However, on the whole, they are less widely spiraled than those from Pikermi [START_REF] Roussiakis | Oioceros rothii (Wagner, 1857) from the late Miocene of Pikermi (Greece): cranial and dental morphology, comparison with related forms[END_REF], and a subspecific distinction, at least, would probably be warranted.

Protoryx sp. A fragment of horn-core and a few dental remains cannot be identified to species. The scarcity of this group is a clear difference with other Turkish sites such as Akkasdağı, Kemiklitepe, and with Samos (BOUVRAIN 1994;[START_REF] Kostopoulos | The Bovidae (Mammalia, Artiodactyla) from the late Miocene of Akkasdağı, Turkey[END_REF][START_REF] Kostopoulos | The late Miocene Mammal faunas of the Mytilinii basin, Samos Island, Greece: new collection. 14. Bovidae[END_REF].

"Plesiaddax" inundatus. A few specimens had been reported by [START_REF] Köhler M | Boviden des türkischen Miozäns (Känozoikum und Braunkholen der Türkei. 28)[END_REF] who called them P. cf. inundatus, but the new material is so similar to the one from Garkin that ERDBRINK (1978) named P. inundatus that it can be confidently assigned to the same species.

The best specimens are a mandible with p2-m2 (p2-p4 = 47.8) and a mandible with m1-m3 (m1-m3 = 85). A metacarpal, probably of the same species, is remarkably long and robust (L = 315, distal W = c. 80). However, BOUVRAIN, BONIS (1984), followed by GERAADS, SPASSOV (2008) questioned the generic attribution of P. inundatus, noting that it is less derived than the type-species, P. depereti from China.

Discussion

Now that the reported occurrence of Listriodon [START_REF] Sickenberg O | Die Gliederung des höheren Jungtertiärs und Altquartärs in der Türkei nach Vertebraten und ihre Bedeutung für di internationale Neogen-Stratigraphie[END_REF][START_REF] Sen S | Mammalian biochronology of Neogene deposits and its correlation with the lithostratigraphy in the Çankırı-Çorum Basin, central Anatolia, Turkey[END_REF] has been shown to be erroneous, the fauna from Çorakyerler looks homogeneous, and no taxon appears out of place. It is clearly a Turolian fauna, ?Acerorhinus and Majoreas being perhaps the only significant taxa that might also fit an earlier age. Çorakyerler is significantly more recent than Middle Sinap or Ravin de la Pluie. Within the Turolian, most taxa suggest an age slightly earlier than Pikermi, a reference locality for MN12 in this area, and a MN13equivalent age is very unlikely. Çorakyerler is probably earlier than Akkasdağı [START_REF] Sen | Geology, mammals and environments at Akkasdağı, late Miocene of Central Anatolia[END_REF], but the composition of the latter site is quite different, with gazelles and hipparions predominant. An interesting, as yet unsettled, question is whether Çorakyerler is earlier or later than KTD, which was considered as close to the MN11 / MN12 transition [START_REF] Bonis | Les gisements de Mammifères du Miocène supérieur de Kemiklitepe, Turquie: 11 -Biochronologie, paléoécologie et relations paléobiogéographiques[END_REF]. ?Acerorhinus and Majoreas would suggest the former hypothesis, Choerolophodon and Oioceros (the latter absent from KTD) the reverse placement. The abundance of Oioceros and Majoreas, contrasting with a dearth of other small and medium-size bovids, shows that Çorakyerler is not a classical Turolian locality. The complete lack of large carnivores and of cercopithecids is also to be noted; the latter have not been reported from Turkey.

Another hominoid-bearing locality in this area is Nikiti-1 (NKT) in Greek Macedonia (BONIS, KOUFOS 1999, and ref. therein), considered by them to be of MN10/11 age.

Unfortunately, most of the material (mainly Ruminants) from this locality is in poor condition and identifications are difficult. NKT has several taxa in common with Pikermi, and three of them at least (Microstonyx, Oioceros and Miotragocerus) are also found at Çorakyerler. The evolutionary stage of the hipparion is the main argument, at the present time, for putting NKT earlier than Çorakyerler.

The fauna from the latest hominoid-bearing locality in continental Europe, Azmaka in Bulgaria, has not been published in detail [START_REF] Spassov N | A hominid tooth from Bulgaria: the last pre-human hominid of continental Europe[END_REF]) but it much differs by the presence of Anancus, the different nature of the hipparions and spiral-horned antelopes and, more generally, by the greater diversity of the fauna.

Geographic and ecological factors certainly account for some of the differences in faunal composition with other sites. I tentatively refer Çorakyerler to early MN12, bearing in mind, however, that it has very few forms in common with MN12 as defined in Spain. Its biogeographic affinities are of course first with other Turkish sites and Samos, then with Macedonia, the Black Sea and Iran, but it shares no taxon exclusively with Southern Greece.

The bulk of the animal biomass at Çorakyerler consists of Hipparion s.l. (an ubiquitous genus), ?Acerorhinus (probably a grazing Rhino) and spiral-horned antelopes (common components of the balkano-iranian Turolian faunas, absent from Spain, and therefore probably open-country forms). Giraffids are less common than at Kemiklitepe-D, but cervids are present, although quite rare, and Miotragocerus, also absent from KTD, was perhaps less bound to open country than other antelopes. Suids are also more numerous than at Kemiklitepe. None of these differences is striking, but on the whole, they suggest that the environment was slightly less open; however, the great dominance of just a few species at Çorakyerler suggests a catastrophic accumulation unlike those found in most other Upper Miocene sites.

Captions to figures

(

  medium size); Diceros neumayri (primitive, large form); Chilotherium kowalevskii; Chilotherium samium (large form); Listriodon splendens; Listriodontinae sp. indet. (bunolophodont); cf. Korynochoerus sp.; Samotherium sp. or Palaeotragus (= Achtiaria•) expectans; Palaeotraginae sp. indet. (small form); Oioceros (Samotragus) n. sp.;

Fig. 1 .

 1 Fig. 1. A, Choerolophodon pentelici, dp4; B, Hipparion cf. prostylum, muzzle in ventral

Fig. 2 .

 2 Fig. 2. A, "Hipparion" sp., sketch of the lower tooth-row CY-220; B, Hipparion cf.

Fig. 3 .

 3 Fig. 3. L x W plot (in millimeters) of the third lower molars in some Microstonyx major

Fig. 4 .

 4 Fig. 4. A, Miotragocerus (Pikermicerus) sp., skull in lateral view; B, Majoreas cf.

Fig. 5 .

 5 Fig. 5. Basal horn-core diameters (in millimeters) of Oioceros from various localities. Data

Fig. 6 .

 6 Fig. 6. Three frontlets of Oioceros rothi in front view, to show variation.

Acknowledgments

Thanks to E. GÜLEÇ for having entrusted me, a long time ago, with the study of the Çorakyerler large mammals, which I was unfortunately unable to continue. Thanks to the reviewer, N. SPASSOV, to the editor V. POPOV, and to L. HRISTOVA and G. N. MARKOV for their most useful comments on the manuscript.


V Simona

M Baera

L Torresa

S Olivierb

M Meybeckb

J P Della Massab

The impact of reduction in the benzene limit value in gasoline on airbome benzene, toluene and xylenes levels

Keywords: Benzene, Toluene, Xylene, Passive dosimeter, Urban area, BTX, Volatile organic compound (VOC)

Background benzene, toluene, xylenes (BTX) average concentrations have been measured over the urban agglomeration of Toulouse, France, during both springtime and summer periods of 1999 and 2001.

The benzene average amount over the two Toulouse campaigns in 1999 is equal to 2.2 )lg/m 3 , very close to the French air quality standard and well under the average value of 5 Jlg/m 3 recommended by European Economie Community countries, recognising that those regulations are given for a whole year. BTX pollution over Toulouse has, in particular, been produced by motor vehicle exhaust gases.

For the study conducted during the same periods of 2001, benzene concentrations were within the French quality value in the whole area. This is because the benzene limit value contained in gasoline went from 5% to 1 % since 2000 January 1.

It will be important to measure benzene over annual periods in order to know its exact values over such a period and to observe its potential seasonal variations.

Introduction

Volatile organic compounds (VOCs) play an important role in atmospheric chemistry. This is especially true for substituted aromatic VOC such as toluene and xylenes which have a high photochemical ozone creation potential. They take part in photochemical reactions and are major sources of radicals which can oxidise NO to N0 2 , the precursor of ozone [START_REF] Finlayson-Pitts | Chemistry of the upper and lower atmosphere[END_REF][START_REF] Reis | Road traffic emissions-predictions of future contributions to regional ozone levels in Europe[END_REF].

Exposure to benzene has the potential for adverse health effects as it is a genotoxic carcinogen [START_REF] Snyder | A perspective on benzene leukemogenesis[END_REF][START_REF] Zhang | Interphase cytogenetics of workers exposed to benzene[END_REF][START_REF] Lovem | Identification of benzene oxide as a product of benzene metabolism by mouses, rats and human liver microsomes[END_REF].

The regulation of major indicators for atmospheric pollution (ozone, nitrogen dioxide and sulphur dio xi de) has been updated in recent years to include additional compounds like benzene. The ORAMIP, in partnership with the "Chemistry Energy and Environment" laboratory of the ENSIA-CET, has undertaken a background benzene, to-luene, xylene (BTX) average concentration measurement over the urban agglomeration of Toulouse during bath springtime and summer periods of 1999 (May 5th to May 26th and June 14th to July 2nd) and 2001 (May 2nd to May 22nd and June 13th to July 4th).

The objective of our work was to evaluate BTX average background concentrations over a period of severa! weeks and to compare the BTX concentrations between 1999 and 2001. Samplers of passive type were selected for that purpose and were proved accurate tools under our experimental conditions. Due to their low cost and the simplicity of their positioning, it was possible to multiply the number of measurement points and hence to obtain a more precise pollution map of the area.

Methodology

BTX sampling and analysis

BTX sampling can be carried out by various methods using Tedlar or Teflon bags, canisters or adsorbents. respectively. The latter allow a sampling in either dynamic or passive mode. The advantage of a passive sampling mode is to provide a direct estimate of the average pollutant concentration corresponding to an acquisition period varying between few hours and few days [START_REF] Brown | The use of diffusive samplers for monitoring of ambient air[END_REF][START_REF] Begerow | Passive sampling for volatile organic compounds in air at enviromnentally relevant concentration levels[END_REF][START_REF] Kozdron-Zabiegala | Use of passive dosimeters for evaluation of the quality of indoor and outdoor air[END_REF][START_REF] Baldan | Laboratory test for the validation of the Radiello diffusive sampler[END_REF][START_REF] Zabiegala | Permeation passive sampling as a tool for the evaluation of indoor air quality[END_REF].

Suppor1

Radial diffusive samplers Radiello models were used (Fig. 1 ). The diffusive surface is a synthesized polyethylene cylinder. The adsmbent was activated charcoal (530 mg). The adsorbed compounds were analysed by gas chromatography (GCIFID, GC/MS) after a CS 2 extraction [START_REF] Cocheo | High uptake rate radial diffusive sampler suitable for both solvent and thermal desorption[END_REF]. The gas chromatographie column was a DB 1 (Alltech; 60 m. 0.32 mm and 0.25 セ I N @ An internai standard 2fluorotoluene was used for quantitative analysis (Meybeck et al., 2000).

The average concentration (C, j.t.g/m 3 ) relative to the sampling period is given by the following expression: C = m 10 6 /(Qt), where m (J.tg) is the mass collected over a period t (minutes) and Q (cm 3 /min) is the uptake rate (evaluated from laboratory experiments ).

Blank values were determined on preconditioned tubes which were carried with sample tubes during the sampling process. Sampling capacity and extraction efficiency of the tubes as well as stability of the compounds in the tubes were tested in earlier studies [START_REF] Meybeck | Etude de la distribution atmosphérique de Composés Organiques Volatils (COV) monoaromatiques: Benzène, Toluène, Xylènes (BTX) et du dioxyde d'azote sur l'agglomération toulousaine[END_REF]. Repeatability for benzene, toluene and xylenes was very good. The standard deviation of triplicate samples collected at same sites during bath campaigns was below 10% for all compounds.

Geographical zone and site selection

Toulouse is the fifth urban area in France with 351822 inhabitants (INSEE census, 1999). The study area affects around 380 000 inhabitants. We have selected about 60 sites spread over an area.

Adsorbent cartridge

DiiTusion body

i :r-------------------------------. セ @ 'Ô' 4t--- Z セ } @ :t--- .e. ...... 1 t --- ! Ot---
of about 250 km?. They were chosen among those previously used in 1991192 and 1996/97 N0 2 mea- surement campaigns (ORAMIP, 1997).

Results and discussion

Meteorological conditions

Fig. 2 summarizes the mean meteorological conditions for both years. Precipitations did not allow a more important atmosphere washing for one or anether campaign. For both periods, main wind directions followed a northwest to southeast line: it is the usual wind configuration in Toulouse. The 1999 period was marked by a wind speed more important.

BTX concentrations in 1999

Atmospheric average concentrations in benzene reach maximum values of 3.8 IJ.g/m 3 in the town center (Fig. 3a), whereas toluene and xylenes are characterized by maximum concentrations being respectively of the order of 14 and 11 r.tg/m 3 (Table 1; Figs. 4a and Sa), corresponding to a maximum concentration in BTX at a given site of about 23 IJ.g/m Let us note that the benzene concentrations recorded here are only representative of the sampling period of the experim.ent and remain slightly below the upper tolerated value of 5 J.Lg/m 3 imposed by the European regulation project.

It is noteworthy that the concentrations reach a maximum within the downtown center and are seen to decrease progressively toward the periphery. The zones exhibiting the highest concentrations are shifted towards the east, which can be understood because of the prevailing eastbound wind effectively recorded during the sampling period.

An evaluation of toluene/benzene and xylenelbenzene concentration ratios is useful for characterizing the distance ofvehicular emission sources [START_REF] Derwent | Analysis and interpretation of the continuous hourly monitoring data for 26 C 2 -C 8 hydrocarbons at 12 United Kingdom sites during 1996[END_REF]. Here, the average recorded concentrations led to toluenelbenzene ratios close to 3 (ranged between 2.9 and 3.7), whereas the m,p-xyleneslbenzene and o-xylenelbenzene ratios were respectively of the order of2 and 0.7 (Table 2). These ratios are of the same magnitude as those obtained from automotive exhausts, thereby confirming an origin of the pollution by BTX over Toulouse. In addition, the minimum toluenelbenzene concentration ratios are observed on remote sites of the urban area, whereas the maximum ones are detected close to areas where an intense tra.ffic exists. This is in agreement with an earlier observation by [START_REF] Gelencser | Toluene-Benzene concentration ratio as a tool for characterizing the distance from vehicular emission sources[END_REF] that the tolu-enelbenzene ratio decreases as the distance from the pollution source increases.

BTX concentrations in 2001. Comparison

Atmospheric concentrations in benzene reach maximum values of 2 J.Lg/m 3 in the town center (Fig. 3b ), whereas toluene and xylenes are characterized by maximum concentrations being respectively of the order of 11.9 and 11 J.Lg/m 3 (Table 3; Figs. 4b,5b), corresponding to a maximum concentration in BTX at a given site of about 20 J.Lg/m 3 • For both campaigns, VOC concentrations are maximum in downtown Toulouse and decrease progressively towa.rd the periphery. The highest concentration zones seem to follow a northwest to southeast line corresponding to wind axis. The wind speed more (Brocco et al.,l997;[START_REF] Guicherit | Traffic as a source of volatile hydrocarbons in ambient air[END_REF] 1.8 [START_REF] Stevenson | Air quality at Heathrow Airport Annual Report for[END_REF] 0.9 [START_REF] Guicherit | Traffic as a source of volatile hydrocarbons in ambient air[END_REF] The average concentrations in BTX over Toulouse corresponding to the two campaigns are displayed in Table 3.

For the 2001 period, benzene average concentrations have been divided by two compared to 1999, whereas toluene and xylene concentrations are statistically the same. Meteorological conditions are almost identical. Thus, for the 2001 study period, the benzene allowable rate decrease from 5% to 1% in gasoline has had a significant effect on benzene concentrations in ambient air in Toulouse. Such decrease of ambient benzene concentrations have also been observed between 1999 and 2000 in Paris (AIRPARIF network), around 42% (http://www. airparif.asso.fr ).

For the 1999 period, benzene concentrations in most of the study area exceeded 2 Jlg/m 3 (French quality focus) but they remained below 5 Jlg/m 3 (European limit value), whereas for the 2001 period, benzene concentrations were within the French quality value in the whole area. However, those regimentations are given for a whole year. Accordingly, it will be important to measure benzene over annual periods in arder to know its concentration over such a period and to observe its seasonal variations.

Conclusion

BTX, pollutants directly resulting from automotive exhausts and also from evaporative emissions, are notably taxie to human health and can also generate secondary pollutants like ozone, aldehydes and acids whose impact can be at least as deleterious toward man, ecosystems, monuments ... In this context, our goal was to evaluate average atmospheric background concentrations in BTX over the urban area of Toulouse over a period of several weeks.

We were led to adopt a passive sampling technique which appeared particularly appropriate for that purpose. About 60 sites were selected among the most representative of the Toulouse urban area. A mapping of concentrations reveals that maximum concentrations in BTX are recorded in the downtown area, with a progressive decrease toward the periphery. The areas exhibiting the maximum pollution level are slightly shifted toward east relative to the town center as a consequence of prevailing eastbound winds recorded during the time of the experiment.

Upon consideration of toluene/benzene and xylene/ benzene ratios, we conclude that BTX pollution over Toulouse is in particular linked to the motor vehicle exhaust gases.

Benzene average concentrations have been divided by two in 2001 compared to 1999, whereas toluene and xylene concentrations are approximately the same. For the 2001 study period, the benzene allowable rate decrease from 5% to 1% in gasoline has had a significant effect on benzene concentrations in ambient air in Toulouse.

The benzene average amount in 2001 remain below 2 Jlg/m 3 , the French quality standard and well under the average value of 5 Jlg/m 3 , to which is tending European regulation, knowing that those regimentations are fixed for a whole year. Accordingly, it will be important to measure benzene over annual periods in arder to know its exact amount over such a period and to observe its potential seasonal variations.

Fig. 1 .

 1 Fig. 1. Radiello diflùsive sampler.

  Fig. 3. Isoconcentration plots for benzene for both global campaign. (a) 1999; (b) 2001.

Fig. 4 .

 4 Fig. 4. Isoconcentration plots for toluene for both global campaign. (a) 1999; (b) 2001.

Table 1

 1 Average concentration in BTX over Toulouse in 1999 (May 51h to 26th and June 14th to July 2nd)

	(f.Lglm1	Benzene	Toluene	m,p-Xylene	o-Xylene	A11 xylenes	AllBTX
	Average concentration	2.0	6.6	3.7	1.2	4.9	11.0
	Standard deviation	0.7	2.5	1.5	0.5	1.9	4.1
	Maximum value	3.8	14.1	8.0	2.7	10.6	23.1
	Minimum value	1.1	3.0	1.6	0.6	2.2	5.1
	area and were taken sufficiently far away from pollu-
	tion sources to be representative of the background
	pollution level. The dosimeters were thus generally
	installed on pales, at 2-m high, in such a way to avoid
	any wall-screening e:ffect. They were placed in poly-
	ethylene boxes in arder to ensure protection against
	rain and solar radiation and to minimiz.e disturbances
	due to the wind velocity.
	2.3. Isoconcentration plots
	Cartographie representations were made with the
	geostatistic computer pro gram ISATIS which provides
	a set of statistical tools for incorporating the spatial
	coordinates of observations in data processing, allow-
	ing for description and modelling of spatial patterns,
	prediction at unsampled locations and assessment of
	the associated uncertainty.
	We provide here representative plots corresponding
	to benzene, toluene and xylenes for both global
	campaigns.
		a) 1999

Table 3

 3 Average concentration in BTX over Toulouse in 2001 (May 2nd to 22nd and June 13th to July 4th)

	H セ ァ O ュ	S I @	Benzene	Toluene	m,p-Xylene	o-Xylene	Ail xylenes	Ali BTX
	Average concentration	1.1	6.1
	Standard deviation	0.3	2.1
	Maximum value	2.0	11.9
	Minimum value	0.7	3.0
	important in 1999 does not seem to have favoured a
	better pollutant dispersion.


Thomas Nestmeyer

Paolo Robuffo Giordano

Antonio Franchi

Multi-target Simultaneous Exploration with Continual Connectivity

HAL is


Inria Emmanuel Riou

Erven Rohou

Philippe Clauss

Nabil Hallou

A PADRONE: a Platform for Online Profiling, Analysis, and Optimization

PADRONE is new platform for dynamic binary analysis and optimization. It provides an API to help clients design and develop analysis and optimization tools for binary executables. PADRONE attaches to running applications, only needing the executable binary in memory. No source code or debug information is needed. No application restart is needed either. This is specially interesting for legacy or commercial applications, but also in the context of cloud deployment, where actual hardware is unknown, and other applications competing for hardware resources can vary. We describe the infrastructure of PADRONE, and show that its profiling overhead is minimal. We illustrate its use through two examples. In the first one, we show how we measure the performance of the hotpot of benchmark. In the second one, we replace the hotspot of a function by an optimized version, while the program runs. We believe PADRONE fits an empty design point in the ecosystem of dynamic binary tools.

INTRODUCTION

Most of the studies on automatic code optimization have focused on source-to-source transformation tools. Sophisticated techniques have been developed for some classes of programs, and rapid progress is made in the field. However, there is a persistent hiatus between software vendors having to distribute generic programs, and end-users running them on a variety of hardware platforms, with varying levels of optimization opportunities. The next decade may well see an increasing variety of hardware, as it has already started to appear particularly in the embedded systems market. At the same time, one can expect more and more architecture-specific automatic optimization techniques.

Moreover, many "old" executables are still being used although they have been originally compiled for now outdated processor chips. Although most current processors are ensuring backward compatibility, these codes are obviously not taking advantage of new computing resources that appeared in recent processor chips.

All this argues for binary-to-binary optimizing transformations enabling to take advantage of current computing resources when re-compiling source codes cannot be considered. Such transformations can be applied either statically, i.e., before executing the target code, or dynamically, i.e., while the target code is running.

Dynamic optimization is mostly addressing adaptability to various architectures and execution environments. When deploying an application in the cloud, the executable file may be handled by various processor architectures providing varying levels of optimization opportunities. Anticipating numerous different adapted binary versions cannot be a general solution. Another point is related to interactions between applications sharing common hardware, where adaptation may be required to adapt to the varying availability of the resources. Finally, most code optimizations have a basic cost that has to be overcome by the gain they provide. Depending on the input data processed by the target code, an optimizing transformation may be or not profitable. One may argue about the use of programming language virtual machines as an alternative answer to these issues. However, this would enforce the re-writing of every program, while execution time performance is generally more difficult to address with virtual machines, compared to native binary code. In this paper, we show some recent progresses in profiling and analyzing running executable codes using our software framework that can be attached to any running process, in order to collect relevant information or to switch the control flow to some optimized code version. The analysis is run as a separated process, thus minimizing the instrumentation overhead. As an optimization example, we use our tools to automatically substitute binary code which has been originally vectorized for SSE processor units with AVX code. Since the main difference is related to the size of the vector registers (from 128 bits in SSE to 256 bits in AVX), such a code transformation potentially doubles the speed-up due to vectorization.

INFRASTRUCTURE

General Presentation

PADRONE is a library that provides an API. Clients developed with PADRONE are, in spirit, similar to gdb. A user can attach to an already running process, set breakpoints, define callbacks. After the process has been operated upon, PADRONE can detach and let the process run at full speed. The advantage of such an operating mode is the ability to leave the bulk of the analysis (or optimization) work to a different process. On a multicore system, the target process and PADRONE-initiated processes are likely to be scheduled by the operating system on distinct cores.

PADRONE is designed to work in a production environment, i.e., it makes absolutely no assumption about the running program: no debug information is needed, the running program can be stripped (and have no symbol table). Of course, no source code is needed, since PADRONE must be able to handle legacy applications in whatever shape they are available. The PADRONE framework assumes access only to the application binary file and memory space of the process.

PADRONE works on Gnu/Linux systems, and thus takes advantage of existing Linux mechanisms, including the perf event subsystem, the ptrace system call, the virtual /proc file system, or the ELF executable format, as detailed in the following sections. Currently PADRONE aims at optimizing x86 applications, although in the future the framework may evolve and work on other types of processors.

As Figure 1 shows, a typical PADRONE application proceeds in three steps. The first step is profiling. The idea is to observe the running process to see for instance where it spends most of its CPU time, or where some statistics of interest (e.g., IPC, cache misses, etc.) have unexpected values. The second step is the analysis. From the data collected during step one, critical functions and loops can be identified. If needed, a code cache is also created during this step. The code cache is created in the target process address space, and lets PADRONE inject additional or optimized code. The third and last step, the optimization, is usually external to the PADRONE core library, and implemented as separate user code, or even as a separate process (for instance by invoking a compiler). Typically, this step creates an optimized version of some code of the application (e.g., hot spots identified during the profiling step). This new code is then injected into the code cache in the target process address space, to be run there and complement or replace the process' own code. Note that a PADRONE client can repeat the profiling-analysis-optimization cycle as many times as necessary.

PADRONE is actually a toolbox to perform dynamic code modifications. It provides an API which can be used by third party applications to perform specific optimizations. The platform integrates three steps that are usually performed separately, typically with different tools. Sections 3.2 and 3.3 give several examples of PADRONE clients for on-line profiling and optimization tasks. The rest of this section describes the major components of PADRONE.

Profiling (Linux perf event subsystem)

PADRONE provides a profiling functionality, which is the usual first step if no information is available on the running process. It could happen that a user already knows what are the hotspots of a program, in which case that step can be skipped.

The profiling step is useful to measure where the program spends most of its CPU time. Indeed, one of the major goals of PADRONE is to identify the process hotspots, rather than trying to blindly optimize the complete running process. A statistical profiling is obtained by sampling the state of the running process, typically by probing the program counter of the running process at regular intervals. Each probe provides a sample, and each sample includes the IP (instruction pointer) and a call-chain. The handling of that list of samples is left to the analysis step, for instance to figure out the functions to which these IPs belong, and select the critical functions.

To perform the profiling, PADRONE uses the Linux perf event subsystem kernel interface which appeared in Linux version 2.6.31. That kernel interface has been initially created for the perf profiling tool, which is shipped with the kernel sources. The interface is based on performance counters: any modern processor now includes a PMU (Performance Monitoring Unit) which can be configured via dedicated registers to monitor specific hardware events. The actual values are read in other dedicated registers. Those registers (performance counters) can be used to measure for instance the number of executed instructions, number of cycles, number of cache misses, number of branch mispredictions, etc. The kernel interface manages the configuration and reading of the registers, and provides a system call called sys_perf_event_open to actually initialize a performance counter. The system call takes as parameter a data structure that indicates what kind of events we want to monitor, for which process (PID),1 and whether we want to monitor the whole system or only a specific CPU (in that case a CPU id is passed).

Another important piece of information is the profiling mode, which can be either a counting mode or a sampling mode, as discussed later. 2 The call returns a file descriptor from which the client can directly read requested values (e.g. the number of branch mispredictions for a specific process on CPU0). This is the basic mode, or the counting mode. In this mode, it is up to the programmer to decide when to read the values, either on a regular basis or only when the client needs the information.

PADRONE uses the sampling mode in most cases. This mode is dynamic: the interface is configured to receive an interrupt every x occurrences of the event we are interested in. The consequence is that there is something to read on the associated Fig. 2. Profiling sample including a call-chain file descriptor: that mode can be then easily managed using a poll, or a select. Each time an interruption is raised, a sample is produced including the instruction pointer and call chain at the time the event occurred. Typically, PADRONE's profiling step uses a PERF_COUNT_HW_CPU_CYCLE type performance counter, in sampling mode: it is therefore informed of the state of the target process every x cycles. Another option of the sampling mode lets one give a frequency, for instance requesting to get at most 1000 samples per second (instead of a sample every x cycles). In this sampling mode, samples are stored by the kernel in a circular buffer. The client gets access to it by mapping (with mmap) the performance counter related file descriptor returned by sys_perf_event_open.

As mentioned, a sample contains the call chain related to the included instruction pointer. Consider the example of Figure 2. The last address of the call chain is the address (ip) of the sample (0x4006bc), and the address just before (0x400724) is the address of the call (the call chain actually provides the return address). The call targets function foo2 where the ip of the sample is. This is how PADRONE retrieves the address of function foo2 (0x40069c), which will be very important for the analysis step.

Section 3.1 gives a detailed account of the overhead incurred during the profiling phase, for various values of profiling duration and event frequency. However, figuring out the limits of a function is not as easy as it seems. PADRONE can only rely on the binary code of the process (read directly from process address space using /proc/<pid>/mem), with no symbol table or debug information. Even though the entry point of the function is found in the call chain associated with every sample, finding the "bottom end" is much more complicated. Function calls end with ret instructions on x86, but these can appear anywhere, once or more times, inside the function body. 3 A naive linear scanning of the code is clearly insufficient.

Control Flow Graph (CFG).

A solution to that function's limit issue is to build a Control Flow Graph (CFG). The assembly code is used as an intermediate representation of the binary code and the CFG has to be built from this code only. Starting from the address of the first instruction of the function, binary code is disassembled and basic blocks are built along the way. PADRONE follows all possible control flow paths until reaching a ret instruction. 4 Building the CFG is part of PADRONE's API, and opens the way to detailed analysis actions. PADRONE goes further, by building a loop forest from the CFG. Control flow and loop iterations are central to many performance studies, and PADRONE makes this available to any client.

Code Cache

The PADRONE API allows the creation of a code cache in the target process memory space. That special memory area is typically used to host optimized versions of process's critical functions. It might happen that some functions optimizations are done in place, for instance when an instruction is replaced by another instruction of the same size or smaller (padding instructions would have to be added in that last case). But in most of the cases, functions must be significantly modified, and it would then be very hazardous to do all the modifications in place. The main reason is that one can never be certain that the overwritten code is not the target of a jump elsewhere in the program. Also, a client would be lucky if the modified version of the function is exactly the same size as the original one, leading to all sorts of problems linked to relative offsets in the code. The code cache is the solution to these issues.

PADRONE needs to allocate a buffer in the target process memory heap and manage that buffer, for instance to copy optimized functions into it. Since PADRONE and the target process do not share the same address space, some code must be injected into the target process code segment. This (small) piece of code needs to perform dynamic memory allocation as depicted on Figure 3. The ptrace system call is used to stop the process, read/write its registers or memory, resume it back in a new state, and write to /proc/<pid>/mem (the process memory space). At the time ptrace is called, the target process is stopped at a random address. PADRONE copies the injected code at that address, saving existing code and current state (registers) before the actual copy (PADRONE also has an option to indicate the address where you want the injected code to be copied into). To recover control after the injected the code is executed, this fragment ends with a trap instruction, which will stop the target process, and let PADRONE retrieve program state, restore original code, and resume execution.

The details of the code cache creation are the following:

(1) PADRONE stops the target process, obtaining the current instruction pointer IP;

(2) PADRONE saves the few bytes of code starting at IP, and replaces them with shell code;

(3) PADRONE relinquishes the process, and calls wait;

(4) execution of the target process resumes, allocating memory for the code cache, and eventually reaching a trap that suspends the process and send a SIGCHILD signal to PADRONE; (5) PADRONE retrieves relevant registers (typically, rax contains the address returned by malloc), restores the original code and IP, and let the process continue normal execution.

The actual code is only slightly more complicated, for technical reasons. Because the code cache is placed in the target process address space and because it must be executable, mprotect has to set the appropriate properties on the memory area, and this in turn has alignment requirements, which are ensured with the help of posix memalign. Section 3.3 describes an experiments where the code cache is used to hold an optimized version of a function of the original program.

USING PADRONE

Measuring Profiling Overhead

Profiling has a cost, but the mechanism just described can make the overhead minimal. To quantify the impact of PADRONE's attaching, instrumenting, and detaching, we have run several experiments on SPEC CPU-2006 benchmark programs. Run time has been measured when varying two basic quantities:

-the duration of profiling d, in seconds: this is the time during which the Linux kernel perf event subsystem is leveraged to obtain performance data about the target process; -the sampling frequency f , in units per seconds: this is the rate at which performance data is obtained by the client tool.

Our experiments have used durations of 1, 10, and 30 seconds, and sampling frequencies of 1 000, 10 000, and 100 000 samples per second. We believe this covers most of the use cases.

The run times and slowdown appear in the table of Figure 4. For each pair of parameters, the table shows the execution time, and the slowdown incurred by PADRONE's profiling. This slowdown is computed relative to a reference execution time, obtained by running the program standalone. As numbers show, the overhead is very small for short durations and reasonably low for reasonable frequencies. It is for instance perfectly possible to obtain a 10 seconds profile with a frequency of 10000 samples per second.

A:7

Program

Ref. time (s)

d = 1 s d = 10 s d = 30 s f =1K/s 10K/s 100K/s f =1K/s 10K/s 100K/s f =1K/s 10K/

Performance Analysis

PADRONE can be used for different purposes. One of the examples we give here is the capability to measure the performance (as IPC, or instructions per cycle) of a hot function. As depicted on Figure 6, we monitored the SPEC2006 LBM benchmark, and used PADRONE to detect a critical function and measure that function's IPC for 10 successive calls. The code of this client is shown on Figure 5: the call to padrone_fun_ipc_measure is the PADRONE API to capture performance counter values. You can notice in that same code that after having profiled the process and fetched the address of the critical function, we build the CFG of that hot function (padrone_cfg_build). The reason for that is explained in 2.4, i.e., we need to build the CFG to detect the function limit. With that function limit we are able to measure the function's IPC. The idea is to "trap" the beginning of the function execution, as well as all its possible return instructions. The first instruction of the function is replaced with a trap (after saving original instructions, to be restored before restarting the process), and we do the same with all the different ret instructions. Since PADRONE is "ptrace-attached" to the monitored process, it is informed of any trap execution. At the first trap PADRONE polls two hardware counters (previously configured as explained in 2.2) to get actual values of the number of cycles and number of retired instructions. The process is restarted, and the next trap signals the end of the function, at which time PADRONE can read again those same hardware counters, in order to compute the IPC.

Optimization by Function replacement

This section describes another possible usage of PADRONE, namely the replacement, at run time, of a given function by a custom, optimized version. To illustrate this task, we use a small program where the bulk of the work is made of a series of vector additions. The main function is called redstep, it performs N calls to vecadd, which adds two vectors and puts the result in a third vector. Vectors are ultimately stored in raw In this scenario, the original program is legacy. It has been compiled on a machine where SSE vector instructions are available, and the vector addition has been vectorized accordingly. We then run the same executable on a machine where AVX instructions are available, leading to a sub-optimal use of resources. The goal of our experiment is to show that, provided an AVX-enabled version of the vecadd function, PADRONE is able to replace a function on the fly.

The corresponding PADRONE client is sketched on Figure 7. The first step (profiling) is similar to the previous example, an detects the program's critical function (vecadd in our example). The tool then proceeds to replace the function with an optimized version (making full use of AVX hardware). The way the AVX binary version of the function is obtained is out of the scope of this paper which focuses on describing the infrastructure, i.e., we assume the binary code is basically provided by the user (via an array represented by the assembly 64 hw array in Figure 7). PADRONE's API provides a function called padrone_cc_insert to insert a binary code into the code cache. It returns the address of this binary code, which is in our case the address of the optimized version of the critical function. Then padrone_cc_fun_call_replace is used to replace calls to the original function with calls to the optimized version. To achieve this, padrone_cc_fun_call_replace replaces the first instruction of the original function with a trap instruction. Each time the A:11

RELATED WORK

This section reviews a number of works in the ecosystem of profiling and dynamic binary tools.

Profiling Tools

Pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF]] is a dynamic binary instrumentation framework developed and supported by Intel. Thanks to a flexible API, the community has developed a rich set of pintools for architecture exploration, emulation, security. Pin always executes from the code cache, and never executes the original code. Instead, we try to minimize the amount of code we modify, executing as much as possible from untouched original code. Pin is also more oriented toward instrumentation and analysis than optimization.

Tiptop [START_REF] Rohou | Tiptop: Hardware Performance Counters for the Masses[END_REF]] is a tool that displays events collected from the hardware performance monitoring unit. It is similar to the UNIX utility top and refreshes values at regular time intervals. However, the values are read and displayed at the granularity of the thread, without knowledge of the function or loop, and for rather large intervals (at least tenths of seconds). PADRONE focuses on much finer 3grain intervals, and takes into account the structure of the application (functions and loops). A number of tools that read performance counters have been proposed, including Rabbit6 , OProfile7 , libpfm, perfmon28 , perf [Carvalho de [START_REF] Carvalho De Melo | Performance counters on Linux[END_REF], or vtune [Intel 2003]. LiMiT [START_REF] Demme | Rapid identification of architectural bottlenecks via precise event counting[END_REF] is a very recent proposal to reduce the overhead of reading counters, by directly reading machine registers and avoiding the system call.

Dynamic Binary to Binary Optimizers

ADORE [START_REF] Chen | Continuous adaptive object-code re-optimization framework[END_REF]] also uses hardware counters to identify hotspots and phases. It then optimizes the application for the data cache, and generates helper threads. Dynamo [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF]] and DynamoRIO [START_REF] Bruening | Efficient, transparent, and comprehensive runtime code manipulation[END_REF]] insist on the need for transparency. We address it by keeping all the client and toolbox in a separate address space, and by modifying as little as necessary of the original code. DynamoRIO (and Pin) always execute code only from the code cache, while we dedicate it to newly generated code. We also incur marginal overhead by using the support of the PMU, which is independent of the size and complexity of the monitored code, while those tools rely on instrumentation. Qemu [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF]] is a fast machine emulator based on dynamic translation, and performing code generation. Valgrind [START_REF] Nethercote | Valgrind: a framework for heavyweight dynamic binary instrumentation[END_REF]] also builds its on intermediate representation. We chose to only modify the minimum possible and let original code run.

Auto-vectorization

Several techniques have been proposed to dynamically generate SIMD instructions at run-time. Yardımcı and Franz [Yardımcı and Franz 2008] dynamically vectorize (and parallelize) loops based on a static analysis of the executables. Our approach is purely dynamic. El-Shobaky et al. [START_REF] El-Shobaky | Automatic vectorization using dynamic compilation and tree pattern matching technique in Jikes RVM[END_REF]] added automatic vectorization based on tree pattern matching to a JIT compiler. Nie et al. [START_REF] Nie | Vectorization for Java[END_REF]] also added auto-vectorization to a Java virtual machine. [START_REF] Nuzman | Vapor SIMD: Auto-vectorize once, run everywhere[END_REF] perform speculative vectorization at the level of the bytecode in the context of split-compilation. The statically generated bytecode is speculatively vectorized in an abstract target-independent form and a JIT compiler materializes the actual parameters, such as vector length, alignment constraints, and other existing idioms. [START_REF] Clark | Liquid SIMD: Abstracting SIMD hardware using lightweight dynamic mapping[END_REF] propose to convey SIMD opportunities within standard scalar A:12 assembly code, relying on a dynamic translation mechanism to recognize instruction patterns that can be vectorized (in hardware).

CONCLUSION

This paper introduces a new infrastructure, called PADRONE, for dynamic binary optimization. It operates by profiling a target program with minimal overhead, analyzing profiling results, and acting on the running executable code. We argue that it fills an empty design point, and we show its potential for analysis and optimization of binary executable programs. We have shown that PADRONE's profiling overhead is reasonable, and illustrated the use of the platform in two applications: extracting performance data for compute intensive functions, and replacing a time-consuming function with an optimized version.

PADRONE is still in an early stage of development, and we plan to extend it along several dimensions. Our next research target is to integrate various forms of dynamic optimization right in the platform (rather than using pre-packaged variants, as in Section 3.3), by leveraging abstract program structures, like functions and loops. PADRONE is already able to recognize these structures, and we think that reasoning at that level of abstraction opens up a whole new range of potential dynamic optimizations. We plan to use PADRONE to explore this space.

Fig. 1 .

 1 Fig. 1. Analysis and Optimization with PADRONE

Fig. 3 .

 3 Fig.3. Code cache creation in target process instruction pointer, PADRONE is able to detect the containing function. Given profile data, a typical pre-processing step consists in replacing individual instruction pointers with function addresses. This often removes unneeded details, providing data at the right level of abstraction.However, figuring out the limits of a function is not as easy as it seems. PADRONE can only rely on the binary code of the process (read directly from process address space using /proc/<pid>/mem), with no symbol table or debug information. Even though the entry point of the function is found in the call chain associated with every sample, finding the "bottom end" is much more complicated. Function calls end with ret instructions on x86, but these can appear anywhere, once or more times, inside the function body. 3 A naive linear scanning of the code is clearly insufficient.

Fig. 5 .

 5 Fig. 5. Performance measurement (IPC) using the PADRONE API

Fig. 6 .

 6 Fig. 6. Performance measurements (IPC) of SPEC2006 lbm hot function using PADRONE

  Profiling overhead on SPEC CPU-2006 programs: for every combination of d (duration) and f (sampling frequency), both run time and overhead (as a fraction of reference execution time) are shown. All quantities are rounded to the nearest integer.

	s 85 1% 117 39% 118 40% 100K/s 64 1% 75 20% 91 45% 22 76% 22 74% 22 76% 470 472 0% 474 0% 477 1% 474 0% 476 1% 481 2% 472 0% 486 3% 512 8% 84 84 0% 84 0% 85 1% 83 0% 87 3% 93 10% 63 63 0% 63 0% 64 2% 63 0% 64 1% 68 8% 12 12 1% 13 6% 13 4% 13 3% 15 22% 15 22% 378 381 0% 378 0% 383 1% 381 0% 383 1% 391 3% 383 1% 404 7% 475 25% 281 273 -2% 270 -3% 271 -3% 272 -3% 281 0% 286 1% 273 -2% 281 0% 309 9% 324 323 0% 320 -1% 325 0% 323 0% 325 0% 330 1% 325 0% 333 3% 351 8% 325 328 0% 329 1% 330 1% 329 1% 332 1% 335 2% 329 1% 356 9% 450 38% 328 334 1% 331 1% 336 2% 334 1% 337 2% 342 4% 333 1% 354 7% 416 26% 598 600 0% 615 2% 619 3% 615 2% 612 2% 610 1% 612 2% 626 4% 651 8% 278 279 0% 283 1% 281 1% 281 0% 281 1% 288 3% 280 0% 297 6% 349 25% 340 343 1% 343 0% 341 0% 348 2% 346 1% 350 3% 344 1% 356 4% 392 15% 76 76 0% 77 1% 78 3% 76 0% 79 4% 89 17% 82 8% 147 94% 142 86% 82 83 1% 83 1% 84 2% 83 0% 85 3% 89 8% 84 1% 94 13% 122 47% 141 141 0% 141 0% 141 0% 141 0% 146 3% 152 7% 142 0% 165 16% 205 44% 652 647 0% 653 0% 654 0% 647 0% 655 0% 656 0% 654 0% 670 2% 737 13% 265 265 0% 265 0% 266 0% 265 0% 266 0% 270 1% 266 0% 277 4% 306 15% 450 451 0% 452 0% 451 0% 448 0% 453 0% 459 1% 453 0% 475 5% 537 19% 293 293 0% 291 0% 294 0% 293 0% 295 0% 304 3% 294 0% 308 5% 374 27% 292 296 1% 300 2% 299 2% 295 0% 304 4% 302 3% 296 1% 315 7% 330 12% 381 393 3% 382 0% 386 1% 384 0% 389 2% 393 3% 385 1% 459 20% 570 49% 360 361 0% 363 0% 364 1% 362 0% 368 2% 370 2% 362 0% 402 11% 496 37% 246 249 1% 249 1% 250 1% 249 1% 250 1% 254 3% 249 1% 259 5% 279 13% 306 310 1% 289 -5% 316 3% 313 2% 316 3% 326 6% 314 2% 340 11% 412 34% 212 213 0% 214 1% 216 1% 217 2% 214 0% 217 2% 216 1% 220 3% 242 14% 430 435 1% 437 1% 437 1% 436 1% 438 1% 437 1% 436 1% 474 10% 575 33% return EXIT_FAILURE; 400.perlbench 401.bzip2 403.gcc 410.bwaves 416.gamess 429.mcf 433.milc 434.zeusmp 435.gromacs 436.cactusADM 437.leslie3d 444.namd 445.gobmk 450.soplex 453.povray 454.calculix 456.hmmer 458.sjeng 459.GemsFDTD 462.libquantum 464.h264ref 465.tonto 470.lbm 471.omnetpp 473.astar 481.wrf err = padrone_profile(&padrone, duration, frequency, &prof_result); if (err < 0) goto failure; mfs = padrone_profile_get_mfs(&prof_result); err = padrone_fun_fetch_address_from_sample(&padrone, &fun_info, mfs); if (err < 0) goto failure; padrone_cfg_init(&cfg, &fun_info); err = padrone_cfg_build(&cfg); if (err < 0) goto failure; padrone_fun_ipc_measure(&fun_info, 10); padrone_profile_destroy(&prof_result); padrone_cfg_destroy(&cfg); failure: padrone_leave(&padrone); Fig. 4. if (padrone_init(&padrone, pid) < 0) return err;

Workshop on Dynamic Compilation Everywhere, Vol. V, No. N, Article A, Publication date: January 2014.

Permission rights apply: if PADRONE is launched as non-privileged user, only their processes can be monitored.

2 An example is available with the manual page of the system call, available at http://www.man7.org/linux/ man-pages/man2/perf_event_open.2.html

2.3. Analysis (Finding Critical Functions)Once the profiling phase is done, PADRONE has a list of instructions pointers available for further analysis. The relative frequencies of occurrence of the addresses give an indication of where the "hottest regions" of the code are. Individual instruction pointers are moderately useful however, most optimization opportunities targeting coarser-grain structures, like functions and loops. PADRONE provides support for both. This sections illustrates function-level analysis.Indeed functions are often the most convenient abstractions, since they are delimited pieces of code activated by a special instruction (call instruction on x86). Consequently, it is easy enough to substitute a function by another one. A basic feature of the PADRONE framework is to substitute a critical function with an optimized one, and make sure the optimized version is called instead of the original one. Given an Workshop on Dynamic Compilation Everywhere, Vol. V, No. N, Article A, Publication date: January 2014.

Tail call elimination also complicates the matter.

Indirect jumps are currently handled in an unsatisfactory way, and optimized tail calls are considered part of the callee.

PADRONE's API also provides a way to install a code trampoline in original function. This basically replaces original function's first instruction with a jmp instruction to optimized binary code in the code cache.Workshop on Dynamic Compilation Everywhere, Vol. V, No. N, Article A, Publication date: January 2014.

http://www.scl.ameslab.gov/Projects/Rabbit

http://oprofile.sourceforge.net

http://perfmon2.sourceforge.net Workshop on Dynamic Compilation Everywhere, Vol. V, No. N, Article A, Publication date: January 2014.

process is stopped in the trap, PADRONE fetches the function's return address from the stack, to find out the address of the call site, and replace it with a call to the new function in the code cache. This is the quickest way to redirect flow of execution from original function to the optimized one. 5 A run of the vecadd-sse program is depicted on Figure 8 (the PADRONE tool invocation is not shown). Every line in the output shows the time taken by a call to redstep (and the average time of calls to vecadd, of which there are one hundred). What appears on this figure is the fact that, after a certain numbers of calls, the vecadd function is replaced, leading to a large reduction of execution time for redstep. The 65 th call to redstep is the phase-transition call: a few first calls to vecadd have used the original version, the next ones have used the new one.


Romain Deveaud
email: romain.deveaud@univ-avignon.fr

Florian Boudin
email: florian.boudin@univ-nantes.fr

Effective Tweet Contextualization with Hashtags Performance Prediction and Multi-Document Summarization

In this paper we describe our participation in the INEX 2013 Tweet Contextualization track and present our contributions. Our approach is the same as last year, and is composed of three main components: preprocessing, Wikipedia articles retrieval and multi-document summarization. We however took advantage of a larger use of hashtags in the topics and used them to enhance the retrieval of relevant Wikipedia articles. We also took advantage of the training examples from last year which allowed us to learn the weights of each sentence selection feature. Two of our submitted runs achieved the two best informativeness results, while our generated contexts where almost as readable as those of the most readable system.

Introduction

Tweets are short and ambiguous by nature and it can be hard for a user without any background knowledge to understand what the Tweet is about. The INEX Tweet Contextualization track makes the assumption that it is possible to overcome this lack of knowledge by providing the user with a bunch of sentences that give some context or additional information about the Tweet. While topical information may certainly be the most important for this task, one may also want some political context to understand a sarcastic Tweet for example. Our approach specifically focuses on the topical context, and aims at producing informative contexts.

Within the framework of this track, sentences must be extracted from the version of Wikipedia provided by the organizers. Our approach sequentially involves Information Retrieval (IR) and Text Summarization (TS) techniques. First, we extend the Tweet's topical context by retrieving related Wikipedia articles that are likely to contain contextually relevant sentences or passages. Then, we tackle the context generation step as a summarization task where we summarize the retrieved Wikipedia articles. The sentences achieving the best linear combination of weighted features are added to the context (in the 500 words limit established by the organizers). So far, this approach is the same as the one we experimented last year [START_REF] Deveaud | LIA/LINA at the INEX 2012 Tweet Contextualization track[END_REF][START_REF] Sanjuan | Overview of the inex 2012 tweet contextualization track[END_REF], we however added a hashtag performance prediction component to the Wikipedia retrieval step.

The rest of the paper is organized as follows. Section 2 describes the process we followed to extract candidate sentences, which includes Tweet formatting and document retrieval on Wikipedia. Then, we describe in Section 3 the various sentence-level features that we used.

Candidate Sentence Extraction

Considering that the task is to provide context from Wikipedia text, one crucial step is to retrieve Wikipedia articles that are relevant to the Tweet. Hopefully, these articles contain sentences that provide enough contextual information to (fully) understand the meaning of the Tweet.

#HashtagSplitting and Tweet formatting

Hashtags in Tweets are very important pieces of information, since they are tags that were generated by the user. Making a parallel with TREC-like topics, we can view the hashtags as the title while the Tweet itself is the description.

However the main problem with hashtags is that they often are composed of several words concatenated together (e.g. #WhitneyHouston). We used an algorithm based on Peter Novig's chapter on "Natural Language Corpus Data" in [START_REF] Segaran | Beautiful Data: The Stories Behind Elegant Data Solutions[END_REF] to split the hashtags. For each Tweet, all the hashtags we converted into a short keyword query.

We also removed all the retweet mentions (RT), user mentions (@somebody) and stopwords (based on the standard INQUERY stoplist) from the Tweets. The final output of this Tweet formatting process is a clean Tweet without stopwords or useless mentions, as well as a very short and user-generated representation of this Tweet.

Retrieving Wikipedia articles

Retrieving relevant Wikipedia articles is the first crucial part for finding contextually relevant sentences. For this purpose we use the well-known Markov Random Field model [START_REF] Metzler | A markov random field model for term dependencies[END_REF] to represent dependencies between query words. It has indeed performed consistently well on several variety of ad-hoc search tasks across the years.

Given an initial Tweet T , the output of the method described in the previous section is a set of hashtags H T and a set of terms Q T . We then score a Wikipedia article D according to the following function:

s(H T , Q T , D) = α × score M RF (H T , D) + (1 -α) × score M RF (Q T , D)
where α is the parameter which controls the influence of the hashtags with respect to the entire Tweet text. We describe in the following section how we set this parameter. We used the Sequential Dependence Model instantiation of MRF, which is defined as follows:

score M RF (Q, D) = λ T q∈Q f T (q, D) + λ O |Q|-1 i=1 f O (q i , q i+1 , D) + λ U |Q|-1 i=1 f U (q i , q i+1 , D)
where the features weights are set according to the author's recommendation (λ T = 0.85, λ O = 0.1, λ U = 0.05). f T , f O and f U are the log maximum likelihood estimates of query terms in document D, computed over the target collection with a Dirichlet smoothing (µ = 2500).

Hashtags performance prediction

The importance of hashtags is also contextual. Since they can sometimes be noise rather than useful pieces of information, we need an automatic way of setting a varying α for each Tweet. We thus rely on a well-known pre-retrieval query performance predictor: the clarity score [START_REF] Cronen-Townsend | Quantifying Query Ambiguity[END_REF]. This score being actually the Kullback-Leibler divergence between the hashtags language model and the background Wikipedia collection language model, it is formally defined as:

α = w∈V P (w|H T ) P (w|H T ) P (w|C)
where V is the vocabulary. The hashtags language model is estimated through pseudo-relevant feedback:

P (w|H T ) = D∈R P (w|D)P (D|H T )
The set R of pseudo-relevant documents is composed of the top 5 ranked Wikipedia articles for a the H T query. Then α achieves higher values when documents of R are homogeneous and different from the background documents of the collection. This parameter thus allows us to predict if hashtags are discriminative, and to weigh their importance in the query accordingly.

Sentence scoring

From the ranked list of Wikipedia articles, we only consider the top 5 articles as relevant. The underlying assumption is that a Tweet may discuss only a very limited amount of topics, due to the 140 characters limit. Since encyclopedic topics are very well delimited between Wikipedia articles, we think that 5 articles is a reasonable number allowing us to avoid topic drift while hopefully providing a comprehensive coverage of the Tweet's topics. After selecting the 5 best ranked Wikipedia articles with respect to a Tweet T , the next step is sentence segmentation. Each article is divided into sentences using the nltk1 toolkit. We describe in this section the various scoring methods we use to estimate their importance with respect to the Tweet's context.

Sentence features

We computed several features for each candidate sentence in order to further rank them and produce the Tweet's context. There are four categories of features:

centrality of the sentence within the Wikipedia article from which the sentence is extracted, -relevance of the sentence with respect to the Tweet (also including hashtags), -relevance of the sentence with respect to an URL embedded in the Tweet, -relevance of the Wikipedia article from which the sentence is extracted.

All the computed features use cleansed versions of sentences and Tweets. We remove stopwords and stem remaining words using the standard Porter stemming algorithm.

Sentence centrality

The importance of a sentence within the document where it appears is estimated using the TextRank [START_REF] Mihalcea | Textrank: Bringing order into text[END_REF] algorithm.

Sentence relevance regarding the Tweet We compute the word overlap and the cosine similarity between the candidate sentence and the entire Tweet, and also between the candidate sentence and the hashtags alone.

Sentence relevance regarding the URL Tweets sometimes provide link to external web pages which generally contain a lot of contextual information. Organizers consider these web pages as the "answer" of the question asked by the Tweet. This is why using these web pages (even automatically) is considered as a manual run in the Tweet Contextualization track. Considering it worked very well for us last year, we still computed some features using the text of these web pages. More specifically, we compute the word overlap and the cosine similarity between the candidate sentence and the entire text of the linked page, as well as with the title of the web page.

Wikipedia article relevance

The articles from which candidate sentences are extracted contain different contextual information and thus have different importance. Then, a sentence belonging to a high ranked document has a higher chance of being relevant. We use as feature the probability of the document from which the candidate sentence has been extracted.

Final score of a candidate sentence We compute the final importance score of each sentence as a weighted linear combination of the above features. The weights were learned using the 2012 data and are presented in Table 1. After every sentence has been attributed a score, they are ordered and the top-ranked sentences are selected to form context (within the limit of 500 words). If two sentences are extracted from the same document, we keep their original order to improve readability and coherence.

Feature

Runs

We submitted three different runs this year, which we describe in this section.

LIA-title-only-notrain This first run only uses features c2, c3 and c10 without using the trained weights. Sentences of the context are thus ordered using their linear combination of three features.

LIA-all-notrain For this run we use all features described in the previous section without using the trained weights.

LIA-all-train Finally, this runs uses all features combined with the weights from Table 1.

Official Results

We report in Table 2 the official results released by the organizers of the 10 best performing systems. The evaluation measure computes divergences [START_REF] Sanjuan | Overview of the inex 2012 tweet contextualization track[END_REF], hence lower scores are better. We see that our approach performed very well and achieved the best results of the track. Although our best performing run was tagged as manual, we did not manually intervene at any time in our contextualization process.

In Table 3 are reported the readability results of the top 10 best systems. Although our best informative run does not achieve the best readability results, we see that it is very close to the run 275. It also produces the less redundant contexts overall. We however do not clearly understand why our three runs achieve such different readability results since the context generation process is the same. We can for example hypothesize from Table 2 that the contexts which LIA-titleonly-notrain outputs are very similar to those of LIA-all-notrain. Then what could explain such a huge readability difference between the two (very similar) approaches? We think that these problems are worth further investigation.

Table 1 .

 1 Feature weights used for our 2013 runs, learned on the 2012 available data.

		Name	Value Significance
	c1	TextRank	8.996 p < 2 -16
	c2	Overlap Tweet	2.496 p = 2.38 -6
	c3	Cosine Tweet	5.849 p = 4 -15
	c4	Overlap hashtags -2.051 p = 0.1368
	c5	Cosine hashtags	0.671 p = 0.3074
	c6	Overlap title URL	1.373 p = 0.2719
	c7	Cosine title URL	0.788 p = 0.6287
	c8	Overlap text URL	0.543 p = 0.4337
	c9	Cosine text URL 10.374 p = 0.0195
	c10 Document score	0.782 p < 2 -16

Table 2 .

 2 Official informativeness results of the 2013 Tweet Contextualization track (top 10 best performing systems). Starred runs are manual runs.

	Run	All.skip All.bi All.uni
	LIA-all-notrain *	0.8861 0.881 0.782
	LIA-title-only-notrain 0.8943 0.8908 0.7939
	275	0.8969 0.8924 0.8061
	273	0.8973 0.8921 0.8004
	274	0.8974 0.8922 0.8009
	LIA-all-train *	0.8998 0.8969 0.7987
	254	0.9242 0.9229 0.8331
	276	0.9301 0.927 0.8169
	270	0.9397 0.9365 0.8481
	267	0.9468 0.9444 0.8838

Table 3 .

 3 Official readability results of the 2013 Tweet Contextualization track (top 10 best performing systems).

	Run	Mean Average Relevancy Non redundancy Soundness Syntax
	275	72.44% 76.64%	67.30% 74.52% 75.50%
	LIA-all-notrain	72.13%	74.24%	71.98%	70.78% 73.62%
	274	71.71%	74.66%	68.84%	71.78% 74.50%
	273	71.35%	75.52%	67.88%	71.20% 74.96%
	LIA-all-train	69.54%	72.18%	65.48%	70.96% 72.18%
	254	67.46%	73.30%	61.52%	68.94% 71.92%
	LIA-title-only-notrain	65.97%	68.36%	64.52%	66.04% 67.34%
	276	49.72%	52.08%	45.84%	51.24% 52.08%
	267	46.72%	50.54%	40.90%	49.56% 49.70%
	270	44.17%	46.84%	41.20%	45.30% 46.00%

http://nltk.org/

We presented in this paper our contributions to the INEX 2013 Tweet Contextualization Track as well as the official results released by the organizers. We saw that a simple contextualization system composed of an effective Wikipedia retrieval system and a multi-document summarizer achieved the best informativeness results of the track. While it did not achieve the best readability results, it was very close to the best system.