Emmanuel Gheerbrant
email: emmanuel.gheerbrant@mnhn.fr

Arnaud Schmitt

La ´szlo ´kocsis

Early African Fossils Elucidate the Origin of Embrithopod Mammals

Modern mammals rapidly evolved in the early Cenozoic in all continental provinces, including in Africa, with one of the first placental branches, the Afrotheria [1, 2]. Afrotherian evolution is at the origin of the major radiation of African ungulatelike mammals, including extant hyrax, elephant, and sea cow orders, which all belong to the

Paenungulata. The paenungulate radiation also includes the extinct order Embrithopoda of uncertain interordinal relationships, which is best known for the giant and strangely specialized Oligocene genus Arsinoitherium. The Ouled Abdoun basin, Morocco, yielded exceptional Paleocene-Eocene fossils documenting the early paenungulate evolution [START_REF] Gheerbrant | A Palaeocene proboscidean from Morocco[END_REF][START_REF] Gheerbrant | First ascertained African ''condylarth'' mammals (primitive ungulates: cf. Bulbulodentata & cf. Phenacodonta) from the Earliest Ypresian of the Ouled Abdoun Basin, Morocco[END_REF][START_REF] Gheerbrant | A new large mammal from the Ypresian of Morocco: evidence of a surprising diversity of early proboscideans[END_REF][START_REF] Gheerbrant | Paleocene emergence of elephant relatives and the rapid radiation of African ungulates[END_REF][START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF][START_REF] Gheerbrant | Ocepeia (Middle Paleocene of Morocco): the oldest skull of an afrotherian mammal[END_REF]. Here we report two new small Ypresian species, Stylolophus minor n.g., n.sp. and cf. Stylolophus sp., which are the earliest and most primitive embrithopods. The cladistic analysis relates the Embrithopoda to crown paenungulates as the stem-group of the Tethytheria, which makes crown tethytherians restricted to extant elephant and sea cow orders. The Embrithopoda is therefore an early tethytherian offshoot predating the elephant and sea cow divergence. The resulting phylogeny supports a strictly African early radiation of the paenungulates excluding the Phenacolophidae and Anthracobunia. It sustains an at least early Paleocene African origin of the Embrithopoda. The unique tooth pattern of the embrithopods (hyperdilambdodont and pseudolophodont molars) is resolved as evolving early and directly from the dilambdodont (W-shaped labial molar crests) ancestral paenungulate morphotype. The specialized upper molar morphology with two transverse crests is convergent and non-homologous in embrithopods and crown Tethytheria. These convergences for specialized folivorous diet were driven by free herbivorous African niches in the early Paleogene.

RESULTS AND DISCUSSION

Placentals comprise the largest radiation of living mammals, as the result of an evolutionary history dating back to the Cretaceous-Paleogene (K-Pg) transition. Molecular phylogeny identified the first major splitting clades at the base of placentals [1,[START_REF] Springer | Placental mammal diversification and the Cretaceous-Tertiary boundary[END_REF]. Unfortunately, the fossil record of the initial placental radiation remains poor, especially for the key K-Pg period of evolution and for some major continental centers of evolution. This is especially true for the Arabo-African Island, which was the center of radiation of one of the main placental clades, the Afrotheria. The Ouled Abdoun phosphate series, in Morocco, yielded the only known Paleocene and early Eocene fossil remains of stem and early crown paenungulate afrotherians [START_REF] Gheerbrant | A Palaeocene proboscidean from Morocco[END_REF][START_REF] Gheerbrant | First ascertained African ''condylarth'' mammals (primitive ungulates: cf. Bulbulodentata & cf. Phenacodonta) from the Earliest Ypresian of the Ouled Abdoun Basin, Morocco[END_REF][START_REF] Gheerbrant | A new large mammal from the Ypresian of Morocco: evidence of a surprising diversity of early proboscideans[END_REF][START_REF] Gheerbrant | Paleocene emergence of elephant relatives and the rapid radiation of African ungulates[END_REF][START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF][START_REF] Gheerbrant | Ocepeia (Middle Paleocene of Morocco): the oldest skull of an afrotherian mammal[END_REF]. The paenungulates, today represented by orders of hyraxes (Hyracoidea), elephants (Proboscidea), and sea cows (Sirenia), were major components of the African endemic herbivorous megafauna during the Paleogene. The paenungulates also include a remarkable extinct order, the Embrithopoda. Embrithopods are strangely specialized and large, ungulate-like mammals known in the Paleogene of Arabo-Africa and Eurasia. The best known is the rhino-sized Arsinoitherium zitelli, discovered in the early Oligocene of the Fayum [START_REF] Andrews | A Descriptive Catalogue of the Tertiary Vertebrata of the Fayum, Egypt. British Museum[END_REF][START_REF] Sanders | Embrithopoda. In Cenozoic Mammals of Africa[END_REF]. It is characterized by a highly specialized dentition with hyperdilambdodont molars [START_REF] Court | A unique form of dental bilophodonty and a functional interpretation of peculiarities in the masticatory system of Arsinoitherium (Mammalia, Embrithopoda)[END_REF] and by a pair of huge hollow nasal horns [START_REF] Andrews | A Descriptive Catalogue of the Tertiary Vertebrata of the Fayum, Egypt. British Museum[END_REF].

Embrithopods are enigmatic placentals with uncertain phylogenetic relationships because of their unusual autapomorphic morphology. They are included in the Paenungulata [START_REF] Simpson | The principles of classification and a classification of mammals[END_REF], but with debated interordinal relationships. The order initially related to the Hyracoidea [START_REF] Andrews | A Descriptive Catalogue of the Tertiary Vertebrata of the Fayum, Egypt. British Museum[END_REF] is most consensually placed as the sister group to the Proboscidea [START_REF] Court | The skull of Arsinoitherium (Mammalia, Embrithopoda) and the higher order interrelationships of ungulates[END_REF][START_REF] Tassy | The Tethytheria: elephants and their relatives[END_REF][START_REF] Fischer | The interrelation between Proboscidea -Sirenia -Hyracoidea -Mesaxonia: the morphological evidence[END_REF], although it is sister group to the Sirenia in some recent works [START_REF] Seiffert | A new estimate of afrotherian phylogeny based on simultaneous analysis of genomic, morphological, and fossil evidence[END_REF]. Here, we report the discovery of the oldest and most primitive known embrithopods from Ypresian Ouled Abdoun phosphate levels. They shed new light on the origin and early history of the Embrithopoda. Their phylogenetic analysis helps to clarify the basal radiation and interordinal phylogeny of the Paenungulata and Tethytheria, as well as the evolution of key embrithopod synapomorphies. LSID urn:lsid:zoobank.org:act:B4367769-7BE7-4EBF-A9EA-2E18E409D80E.

Systematic Paleontology

Figures 1 and2. Holotype OCP DEK/GE 668, right dentary bearing roots of I 1-2 , alveolae of I 3 , C 1 , and P 2 , and crown of P 1 , P 3-4 , and M 1-3 . Hypodigm (Figures 1 and2) Three specimens documenting upper and lower dentition: holotype; OCP DEK/GE 667, a damaged skull rostrum (maxillary and premaxillary fragments, with cheek teeth); and MNHN.F PM30, fragment of left dentary with broken dP 4 and M 1 and tooth germs of M 2 and P 4 . Etymology Generic name from stylos (Greek ''pillar''), styles, and lophos (Greek ''crest''), lophs, in reference to the upper molar lophs corresponding to the transverse development of the labial crests linking the enlarged parastyle and mesostyle; species name refers to the small size.

Localities and Horizon

Morocco, northeast Ouled Abdoun basin (Grand Daoui and Sidi Chennane quarries), intercalary phosphate beds II/I and possibly phosphate bed I, early Ypresian. Diagnosis S. minor shares with the Embrithopoda the hyperdilambdodont morphotypic molar pattern. It differs from all known embrithopods, including Palaeoamasia, by its very small size and primitive state of hyperdilambdodonty, with less lingual paracone and metacone and correlatively shorter pseudolophs (preparacrista, premetacrista) and with retention of more developed postparacrista, postmetacrista, and pseudohypocone; cheek teeth with brachyodont low crown; M 1-2 with one lingual root and with separated paracone and protocone roots; P 2 singlerooted and simple; and P 2 double-rooted and simple. Anterior incisors are enlarged (especially their root), and I 1 is partially hypsodont. Description See characters 0-208 in Data S1 (detailed description in preparation; E.G., A.S., and L.K., unpublished data). The molar series of S. minor (Figures 1 and2) is about 20% longer than that of Phosphatherium escuilliei [START_REF] Gheerbrant | Nouvelles donn ees sur Phosphatherium escuilliei (Mammalia, Proboscidea) de l'Eoce `ne inf erieur du Maroc, apports a `la phylog enie des Proboscidea et des ongul es lophodontes[END_REF]. We inferred from tooth size [START_REF] Damuth | Body Size in Mammalian Paleobiology[END_REF] a 20-31 kg body mass for S. minor.

cf. Stylolophus sp. indet. Referred Material (Figures 3 andS1) MNHN.F PM53, several pieces of a broken skull of the same individual, including a fragment of the snout with anterior part of parietals, right frontal and nasal, left maxillary with cheek teeth, and broken petrosals.

Locality and Horizon

Morocco, northeast Ouled Abdoun Basin (unknown quarry), upper phosphate horizons, probably sillons A-B, middle Ypresian (Data S1B). Description See characters 0-208 in Data S1 (detailed description in preparation; E.G., A.S., and L.K., unpublished data). This species is most closely related to the younger species S. minor in dental morphology. It differs most remarkably in its larger size (30%-40% larger in tooth size). It also differs by derived traits of the molars such as longer pseudolophs and smaller postparacrista, postmetacrista, and pseudohypocone. The body mass of cf. Stylolophus sp. indet. is estimated from tooth size as 60-88 kg, i.e., about 3.6 times heavier than S. minor.

Comparisons

The Moroccan Ypresian species S. minor and cf. Stylolophus sp. share several key morphotypic dental features of the order Embrithopoda, such as the hyperdilambdodont pattern (enlarged W-shaped ectoloph linked to enlarged styles); presence of two sharp pseudolophs (elongated preparacrista and premetacrista); hypoconulid cingulid-like and lingually located; M 3 hypoconulid lobe small, compressed laterally and lingually set; cristid obliqua lingual on the trigonid; and reduced entocristid (postfossid opened lingually). Comparisons emphasize the primitive morphology of the two Moroccan species within the Embrithopoda. They differ from all other embrithopods, including Palaeoamasiidae, by their small size and plesiomorphic traits, such as a primitive hyperdilambdodont state with less lingual paracone and metacone and correlatively shorter pseudolophs, and by retention of prominent postparacrista, postmetacrista, and pseudohypocone (metaconule in Paenungulata [START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF]). Other primitive features of Stylolophus with respect to palaeoamasiids are the lower crown of cheek teeth, M 1-2 with only one lingual root and with separated paracone and protocone roots, P 2 single rooted and simple, and P 2 double rooted and simple. In addition, the petrosal of cf. Stylolophus sp., although damaged, shows a likely separated foramen for the aquaeductus cochleae, in contrast to Arsinoitherium, in which this foramen and the fenestra cochleae remain undivided as a single perilymphatic foramen [START_REF] Court | Periotic anatomy of Arsinoitherium (Mammalia, Embrithopoda) and its phylogenetic implications[END_REF]. S. minor reveals a remarkable mor- photypic condition of the Embrithopoda in the presence of enlarged anterior incisors with hypertrophied root (Figures 1A and2C). I 1-2 are large and procumbent (Figure 2C), and I 1 is partly hypsodont, as shown by its open root in the holotype (adult individual) (Figure 2D).

Enlarged and procumbent anterior lower incisors are most likely representative of the ancestral embrithopod morphotype. However, the anterior dentition remains poorly known in the order, even in Arsinoitherium, in which the first incisor is unknown. Andrews [START_REF] Andrews | A Descriptive Catalogue of the Tertiary Vertebrata of the Fayum, Egypt. British Museum[END_REF] reconstructed in A. zitelli a quite distinctive homodont anterior tooth battery with all teeth, from P 1 / 1 to I 1 / 1 , of similar size, orientation, and morphology. It displays especially subvertical I 1-2 , in contrast to Stylolophus. However, some specimens of A. zitelli, such as MNHN.F LBE 579, display large and procumbent alveoli of I 1-2 , in a quite similar disposition to the holotype of S. minor. If Andrews's reconstruction [START_REF] Andrews | A Descriptive Catalogue of the Tertiary Vertebrata of the Fayum, Egypt. British Museum[END_REF] is correct, it suggests that the small and vertical I 1-2 is secondary in the order, as are some other remarkable characters of Arsinoitherium, such as the orbit posterior and the narrow zygomatic arches.

The dental morphology of the new Moroccan species is clearly closer to that of the Palaeoamasiidae than to the more derived Arsinoitheriidae Arsinoitherium and Namatherium, which have more specialized hyperdilambdodonty. Arsinoitheriids differ indeed in the absence of a pseudohypocone (fully regressed), P 3-4 with postcingulum extended posteriorly, and M 3 more offset lingually with respect to M 1-2 . In addition, Namatherium has a lingual cingulum on the upper premolars and a more anterior zygomatic process, and Arsinoitherium has molarized premolars with a hypocone.

Our comparative anatomical study unambiguously confirms unique specialized embrithopod features in Stylolophus, but also its plesiomorphic morphology within the order.

Phylogenetic Relationships and Character Evolution in Embrithopoda, Tethytheria, and Paenungulata

We investigated the relationships of S. minor and cf. Stylolophus sp. among various lophodont and stem ungulate-like placentals using parsimony analysis with TNT [START_REF] Goloboff | TNT, a free program for phylogenetic analysis[END_REF] of 209 dental and cranial characters, 68% of which are known in S. minor (Data S1). It unambiguously places S. minor and cf. Stylolophus sp. as the basal-most embrithopods, arranged in sequence with S. minor being the first branch (Figure 4A). S. minor and cf. Stylolophus sp. are therefore the most primitive known embrithopods. Although being very plesiomorphic within the order, their embrithopod relationship is indicated by noticeable specialized traits. The most remarkable is the hyperdilambdodont pattern (Figures 1 and3). Other embrithopod molar synapomorphies of Stylolophus are homoplastic, but they form altogether a suite of characters exclusive to the Embrithopoda: hypoconulid lingual, cristid obliqua very lingual on the trigonid, small and lingually located hypoconulid lobe in M 3 , and talonid widely open lingually. Some embrithopod skull synapomorphies are also identified in S. minor, such as the palate concave between the premolars. In addition, cf. Stylolophus sp. shows a remarkable intranasal rostrum pattern through the development of large paranasal sinuses (Figure S1), which is reminiscent of the very large hollow air space developed in the nasal horn of Arsinoitherium. As a result, S. minor shows that the ancestral morphotype of the order Embrithopoda was well established by the earliest Eocene, even in early small plesiomorphic species.

Within the Embrithopoda, the cladistic analysis does not include the new Moroccan species S. minor and cf. Stylolophus sp. in a single generic clade. cf. Stylolophus sp. most remarkably differs by its larger size, consistently with its slightly higher stratigraphic provenance (Data S1B). Otherwise, their close morphological affinity argues against a distinct genus for the larger Ouled Abdoun species that is provisionally referred to an unnamed new species of Stylophus. S. minor and cf. Stylolophus sp. are regarded as successive chronospecies of a new Ypresian mammal lineage found in Ouled Abdoun series. The intraordinal relationships of other embrithopods remain poorly solved in our analysis, and especially for the poorly known palaeoamasiids Hypsamasia and Crivadiatherium, as previously found by Erdal et al. [START_REF] Erdal | New material of Palaeoamasia kansui (Embrithopoda, Mammalia) from the Eocene of Turkey and a phylogenetic analysis of Embrithopoda at the species level[END_REF]. It should be particularly noted that the node grouping the palaeoamasiids Hypsamasia and Crivadiatherium with arsinoitheriids, to the exclusion of Palaeoamasia (Figures 4A and4B), relies mostly on character optimizations, and it is poorly supported with low Bremer support.

At higher, interordinal systematic rank, our cladistic analyses (analyses 1-10; Table S1 and Data S1) recover two topologies within Tethytheria: (1) a clade (Embrithopoda (Proboscidea, Sirenia)) and (2) a clade (Embrithopoda, Proboscidea). The sistergroup relationship of the Embrithopoda to both the Sirenia and Proboscidea, i.e., its stem tethytherian position, is found in nearly all our analyses (Table S1 and Data S1). It is supported by analyses constraining the Afrotheria and Afroinsectiphilia (analyses 7-10), and it is also found in unconstrained analysis (analysis 1) and in analysis with TNT's ''implied weighting'' option (analysis 2; Figure 4A). Of note, it is most usually associated with the clade Paenungulatomorpha [START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF]. The alternative, previously consensual sister-group relationship of the Embrithopoda and the Proboscidea is found marginally in three analyses (analyses 1, 3, and 7), especially with unordered features (analysis 3).

The relationship of Eritherium within Tethytheria is noticeably unstable in our analyses, depending on relationships of the Proboscidea with respect to the Sirenia and the Embrithopoda. Eritherium is found as a stem proboscidean, as initially established [START_REF] Gheerbrant | Paleocene emergence of elephant relatives and the rapid radiation of African ungulates[END_REF], only in cladograms recovering the clade (Proboscidea, Embrithopoda). In other MPTs, it is sister group either to both the Proboscidea and Sirenia (most frequent topology) or to all tethytherians. Consequently, in this study, the Eritherium position is unexpectedly unresolved within Tethytheria (polytomy in consensus trees or low Bremer support).

The stem tethytherian position of the Embrithopoda is the best supported phylogenetic hypothesis found here, both in our parsimony analyses and in character transformation within paenungulates. It implies that the crown-group Tethytheria only includes extant orders. It is most consistent with an ancestral dilambdodont tooth morphotype of the paenungulates [START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF][START_REF] Gheerbrant | Ocepeia (Middle Paleocene of Morocco): the oldest skull of an afrotherian mammal[END_REF] from which evolved the specialized hyperdilambdodont and pseudolophodont molar pattern of the embrithopods (Figure 4C). Such a paenungulate ancestral dilambdodont morphotype is supported by our MPTs (Figure 4A) recovering the clade Paenungulatomorpha, with a stem paenungulate relationship of early dilambdodont genera Ocepeia and Abdounodus [START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF], and also by the dilambdodont morphology of early crown paenungulates such as Eritherium and Seggeurius. Embrithopods' hyperdilambdodont and pseudolophodont molars evolved by enlargement of labial molar structures of the ''primary trigon'' such as the styles, stylar shelf, and ectoloph, at the expense of the lingual structures [START_REF] Court | A unique form of dental bilophodonty and a functional interpretation of peculiarities in the masticatory system of Arsinoitherium (Mammalia, Embrithopoda)[END_REF]. The stem tethytherian position of the Embrithopoda found here allows to identify a remarkable opposite early trend of the crown Tethytheria (Sirenia, Proboscidea) to reduce labial molar structural elements (stylar shelf and cusps, ectoloph), combined with development of the lingual lophs and true bilophodonty (A) Strict consensus of the two most parsimonious trees (MPTs) resulting from parsimony analysis of Stylolophus relationships using TNT with the ''implied weighting'' option. These trees most noticeably recover the embrithopod relationship of S. minor and cf. Stylolophus sp. and the stem tethytherian relationships of the Embrithopoda. Crown Tethytheria are indeed restricted in this topology to the extant orders Sirenia (sea cows) and Proboscidea (elephants). It should be noted that the relationship of Eritherium is unstable in our analyses (Data S1). Its basal position to both the sirenians and proboscideans seen in this tree, instead only to proboscideans [START_REF] Gheerbrant | Paleocene emergence of elephant relatives and the rapid radiation of African ungulates[END_REF], is actually poorly supported (e.g., low bootstrap and Bremer indices; see Data S1). The relationship of Eritherium within crown tethytherians is best considered unresolved in our analyses (see the main text). Besides the wellsupported stem embrithopod position of Stylolophus, the intraordinal relationship of the embrithopods remains also poorly solved, mostly because of our still poor knowledge of the palaeoeamasiids. Retention index (RI): 57.9; consistency index (CI): 35.7; tree length (L): 883 steps. Matrix and details of the cladistic analysis, including Bremer index, are provided in Data S1. Drawing of the skull of Arsinoitherium zitelli by Charle `ne Letenneur (MNHN). (B) Strict consensus of 24 MPTs resulting from parsimony analysis of Stylolophus relationships using TNT with the clade Afrotheria (extant and fossil taxa) constrained. It should be noted that most of the resulting MPTs (19 trees) support the sister-group relationship of the Embrithopoda to the clade (Sirenia, Proboscidea), i.e., the stem tethytherian position of Embrithopoda. RI: 57.7; CI: 35.6; L: 885 steps. See comments in the main text. (C) Hypothesis on the origin of the hyperdilambdodont and pseudolophodont molar pattern of the Embrithopoda within the Paenungulatomorpha, based on the interordinal relationships found in this study (Figure 4A). The recovered stem Tethytheria position of the Embrithopoda implies that their autapomorphic hyperdilambdodont pattern originated directly from the paenungulate ancestral dilambdodont morphotype. In this topology, two major and non-homologous lophodont structural trends of upper molars are recognized in the early tethytherian evolution: (1) in the Embrithopoda, there is enlargement of the labial cusps (styles) and crests (ectoloph) forming the hyperdilambdodont and pseudolophodont pattern and a reduction of the lingual structures (protocone and pseudohypocone); and (2) in the crown Tethytheria (Proboscidea and Sirenia), there is a reduction of the labial structures (styles and ectoloph) and a development of the lingual crests and cusps forming the protoloph and metaloph and the true bilophodont pattern. These two structural trends are mutually exclusive within the Tethytheria. The hyperdilambdodont-pseudolophodont pattern of the Embrithopoda results from the transverse extension of the dilambdodont ectoloph (mostly preparacrista and premetacrista) inherited from the ancestral morphotype of the paenungulatomorphans and paenungulates, which is elucidated especially by Ocepeia and Abdounodus [START_REF] Gheerbrant | Convergence of Afrotherian and Laurasiatherian Ungulate-Like Mammals: First Morphological Evidence from the Paleocene of Morocco[END_REF][START_REF] Gheerbrant | Ocepeia (Middle Paleocene of Morocco): the oldest skull of an afrotherian mammal[END_REF]. Drawings by Charle `ne Letenneur (MNHN).Occlusal sketches of upper molars (not to scale): Ocepeia daouiensis (M 1-3 ), Abdounodus hamdii (M 1-2 ), Hyracoidea: Seggeurius amourensis (M 1 and M 3 ), Embrithopoda: Stylolophus minor (M 1-3 ), Palaeoamasia kansui (M 2-3 ), Proboscidea: Eritherium azzouzorum (M 2-3 ), Sirenia: Eotherioides sandersi (M 1-3 ), and Protosiren sp. (M 2? ). Black circles, paracone and metacone; red circles, mesostyle and parastyle; red lines, ectoloph; green line, protoloph and metaloph linking paracone to protocone and metacone to pseudohypocone. See also Figure S2, Table S1, and Data S1.

(Figure 4C). As a result, S. minor helps to elucidate two divergent and non-homologous lophodont specializations at the tethytherian root (Figure 4C), with morphological and functional emphasis of either (1) labial molar crests and cusps in the hyperdilambdodont and pseudolophodont pattern of embrithopods or (2) lingual molar crests and cusps in the true lophodont pattern of crown tethytherians (extant elephant and sea cow orders). These two structural trends are mutually exclusive in the Tethytheria; by contrast, the hyraxes order retained both structural trends with the evolution of more or less specialized and combined dilambdodonty (selenodonty) and true bilophodonty in several lineages [START_REF] Rasmussen | The oldest hyracoids (Mammalia: Pliohyracidae): new species of Sagatherium and Thyrohyrax from the Fayum[END_REF].

Significance of Stylolophus

The discovery of the earliest and basal-most embrithopods in the early Eocene of Morocco sheds new light on the basal diversification of the Tethytheria and the early evolution of African ungulate-like mammals. The phylogenetic trees including Stylolophus exclude any relationships of the Asian phenacolophids to the Embrithopoda, in agreement with enamel microstructure [START_REF] Von Koenigswald | Unique differentiation of radial enamel in Arsinoitherium (Embrithopoda, Tethytheria)[END_REF]. More generally, they support a strictly African endemic early radiation of the paenungulates and tethytherians, independently from early non-African bilophodont ungulates such as phenacolophids, anthracobunids, and desmostylians that are instead related to Laurasian Euungulata and Perissodactyla (Figure 4A), as found in recent studies [START_REF] Cooper | Anthracobunids from the middle eocene of India and pakistan are stem perissodactyls[END_REF]. They also show that the order Embrithopoda is an extinct stem tethytherian branch that evolved before the divergence of the extant orders Proboscidea and Sirenia (Figure 4A). It supports at least an early Paleocene origin and early evolution of the Embrithopoda, taking into account the age of earliest crown tethytherians [START_REF] Yans | First carbon isotope chemostratigraphy of the Ouled Abdoun phosphate Basin, Morocco; implications for dating and evolution of earliest African placental mammals[END_REF][START_REF] Kocsis | Comprehensive stable isotope investigation of marine biogenic apatite from the late Cretaceous-early Eocene phosphate series of Morocco[END_REF]. Phylogenetic analysis of Stylolophus also elucidates the evolution of major dental specializations in Paenungulata and Tethytheria, including the most specialized one of the Embrithopoda (hyperdilambdodonty) that is homologized here with the dilambdodont ancestral morphotype of the paenungulates (Figure 4C) and is shown to correspond to an early lophodont functional convergence with the crown Tethytheria. The repeated lophodont specializations for the folivorous diet within tethytherians and paenungulates was driven by remarkable favorable herbivorous niches of the Island Africa during the Paleogene.

By the onset of the Eocene, embrithopods already had the morphotypic hyperdilambdodont dental pattern and specialized skull characters such as a developed nasal sinus system. They display distinctive specializations and are larger with respect to coeval (and sympatric) crown tethytherians from the early Ypresian of Ouled Abdoun basin such as Phosphatherium.

Our cladistic analysis supports the Embrithopoda monophyly [START_REF] Erdal | New material of Palaeoamasia kansui (Embrithopoda, Mammalia) from the Eocene of Turkey and a phylogenetic analysis of Embrithopoda at the species level[END_REF]. The embrithopods distribution in both Arabo-Africa (Stylolophus, Arsinoitheriidae) and Eurasia (Palaeoamasiidae) [START_REF] Erdal | New material of Palaeoamasia kansui (Embrithopoda, Mammalia) from the Eocene of Turkey and a phylogenetic analysis of Embrithopoda at the species level[END_REF][START_REF] Sen | Dispersal of African mammals in Eurasia during the Cenozoic: ways and whys[END_REF] is the most demonstrative mammalian evidence of trans-Tethyan dispersals involving Africa (Figure S2). The basal embrithopod position and early age of Stylolophus, as well as the supraordinal relationships to the Afrotheria/Paenungulata, all indicate at least an earliest Paleogene African center of origin for the Embrithopoda. This supports the embrithopod colonization of Eurasia from Africa, most consistently following aremarkable-early or middle Eocene trans-Tethyan dispersal event.

STAR+METHODS

Detailed methods are provided in the online version of this paper and include the following:

d KEY RESOURCES

Figure 1 .

 1 Figure 1. Stylolophus minor n. g., n. sp. Specimen OCP DEK/GE 667. (A) Right premaxillary in occlusal view showing alveoli of I 1-3 . (B) Anterior part of left maxillary with P 2-3 and alveoli of P 1 , C 1 , and I 3 in occlusal stereophotographic view. (C) Posterior part of right maxillary with P 4 and M 1-3 in occlusal stereophotographic view. (D) Sketch of occlusal outlines of right P 4 and M 1-3 . Length of M 1-3 series: 40 mm. Scale bar, 10 mm. Photographs by Philippe Loubry (CR2P, MNHN).

Figure 2 .

 2 Figure 2. Stylolophus minor n. g., n. sp. Holotype, specimen OCP DEK/GE 668. (A) Right lower jaw in occlusal setereophotographic views. (B) Reconstruction of lower tooth row: sketch of occlusal outlines of M 1-3 , P 3-4 , and P 1 and of alveoli of I 1-3, C 1 , and P 2 . (C) 3D model reconstructed from computed tomography (CT) scans of the lower jaw OCP DEK/ GE 668 (holotype) showing by transparency the large and proclive roots of I 1 and I 2 in S. minor; the view shows the teeth roots of M 1-3 , P 3-4 , P 1 , and I 2-1 and the teeth alveoli of P 2 , C 1 , and I 3 . (D) Detail of I 1 root (3D model reconstructed from CT scans), showing the widely open pulp canal at the root apex, which indicates that the tooth was still growing in adult stage (partial hypsodonty). Length of M 1-3 series: 38.5 mm. Scale bar, 10 mm. Photographs by Philippe Loubry (MNHN). Drawing by Charle `ne Letenneur (MNHN).

Figure 3 .

 3 Figure 3. cf. Stylolophus sp. Specimen MNHN.F PM53, left maxillary with upper cheek teeth. (A) P 4 (damaged), M 1-3 in occlusal stereophotographic view. (B) Sketch of the occlusal view of P 4 and M 1-3 . Length of M 1-3 series: 55.3 mm. Scale bar, 10 mm. Photographs by Philippe Loubry (MNHN). See also Figure S1.

Figure 4 .

 4 Figure 4. Relationships of Sylolophus and the Embrithopoda.

TABLE d

 d

	Ana-	Type of analysis and	Trees	Trees	RI;	Comments
	lysis	constraint	number	Length	CI
	1.	"Traditional search", 51	12	876 58.4;	Clades: "Altungulata";
		characters ordered			36	Desmostylia sister-group (Perissodactyla,
						Anthracobunia); Embrithopoda: 1) sister-group to
						Proboscidea (6 MPTs); 2) sister-group to
					CONTACT FOR REAGENT AND RESOURCE SHARING (Proboscidea + Sirenia) (6 MPTs).
	2.	Idem 1 with "Implied	2	d EXPERIMENTAL MODEL AND SUBJECT DETAILS 883 57.8; Clades: Paenungulatomorpha; Desmostylia sister-
		Weighting"			d METHOD DETAILS 35.7; group (Perissodactyla, Anthracobunia);
					B Institutional abbreviations Embrithopoda sister-group to (Proboscidea,
					B Phylogenetic analysis Sirenia)
	3.	"Traditional search", no character ordered	4	B Geochemical study 816 56.6 Clades: "Altungulata"; Desmostylia sister-group d DATA AND SOFTWARE AVAILABILITY 38.4 of Perissodactyla + Anthracobunia;
						Embrithopoda sister-group to Proboscidea
	4.	Idem 3 with "Implied	1	825 55.9;	Clade Paenungulatomorpha ; Desmostylia sister-
		Weighting"			37.9	group of Perissodactyla and Radinskya ;
						Embrithopoda sister-group to (Sirenia,
						Proboscidea)
	5.	Analysis without Desmostylia,	16	836 61.3;	Clades: Paenungulatomorpha; Embrithopoda
		"Traditional search", 51			37.7	sister-group to (Sirenia, Proboscidea), with
		characters ordered				unresolved position of Eritherium
	6.	Idem 5 with "Implied	2	845 59; 37 Clades: Paenungulatomorpha; Embrithopoda
		Weighting"				sister-group to (Sirenia, Proboscidea)
	7.	Clade Afrotheria constrained	24	885 57.7
		(extant and fossil taxa) ;			35.6
		"Traditional search", 51
		characters ordered
		Clade Afrotheria constrained	1	893 57.1;	Clades: Paenungulatomorpha; Embrithopoda
		(extant and fossil taxa); idem 7			35.3	sister-group to (Eritherium (Sirenia,
		with "Implied Weighting"				Proboscidea))
	9.	Clade Afroinsectiphilia	40	888 57.5;	Clades: Paenungulatomorpha; Embrithopoda
		constrained; "Traditional			35.5	sister-group to (Sirenia, Proboscidea);
		search", 51 characters ordered				Eritherium with unsolved position to
						(Proboscidea, Sirenia) and Embrithopoda; 19
						MPTs recovering Afrotheria (Afroinsectiphilia +
						Paenungulata)
	10. Clade Afroinsectiphilia	1	899 56.6;3	Clades: Paenungulatomorpha;
		constrained; idem 9 with			5.0
		"Implied Weighting"

Clades: Paenungulatomorpha; polytomy of Tethytheria: 5 MPTs with Embrithopoda and Proboscidea sister-group; 19 MPTs with Embrithopoda sister-group to (Sirenia, Proboscidea); Eritherium stem Tethytheria or sister-group to (Proboscidea, Sirenia) 8.

Embrithopoda sister-group to (Eritherium (Sirenia, Proboscidea))

Table S1 -Cladistic analyses performed in this work of the relationships of Stylolophus.

 S1 Related to Figure4, STAR Methods and Data S1. All parsimony analyses were made with the "traditional search" command of TNT. Matrix with 33 taxa, 209 characters, 17 uninformative characters (inactivated for calculation of the indices), 51 additive (ordered) characters.

ACKNOWLEDGMENTS

We thank F. Escuilli e and S. Xerri for donation of S. minor specimens to the OCP collection, making them available for study. With thank the Office Ch erifien des Phosphates (OCP Group, Morocco) for housing paleontological collections of Moroccan phosphate basins (acronym OCP DEK/GE). Study of the OCP collections benefited from the ''Phosphapal'' collaborative agreement with the OCP, Ministe `re de l'Energie, des Mines, de l'Eau et de l'Environnement (Rabat), Mus eum National d'Histoire Naturelle (Paris), Universities Cadi Ayyad (Marrakech), and Chouaib Doukkali (El Jadida). We thank P. Loubry (CR2P-MNHN) and L. Cazes (CR2P-MNHN) for photographs, R. Vacant (CR2P-MNHN) for preparation and casts, and M. Garcia (MNHN) for CT scanning. We thank F. Goussard and C. Letenneur (CR2P-MNHN) for reconstruction of Stylolophus material (3D models, retrodeformation, and drawings). We thank S. Sen (CR2P-CNRS) for providing Figure S2. We thank M. Godinot (CR2P-EPHE) and P. Janvier (CR2P-CNRS) for English editing and comments on the manuscript. L.K. was supported by Universiti Brunei Darussalam research grant UBD/PNC2/2/RG/1(325) and E.G. and A.S. by CR2P-UMR 7207 (CNRS, MNHN, UPMC) research grants. We thank the two reviewers who helped to improve our manuscript.

SUPPLEMENTAL INFORMATION

Supplemental Information includes two figures, one table, and one data file and can be found with this article online at https://doi.org/10.1016/j.cub. 2018.05.032.

AUTHOR CONTRIBUTIONS

E.G. designed and performed research, analyzed data, and wrote the paper. A.S. and LK performed research, analyzed data, and wrote the paper. L.K. made the geochemical analysis.

DECLARATION OF INTERESTS

The authors declare no competing interests.

STAR+METHODS KEY RESOURCES TABLE CONTACT FOR REAGENT AND RESOURCE SHARING

Further information and requests for resources, reagents and scripts should be directed to and will be fulfilled by the Lead Contact, Dr. Emmanuel Gheerbrant (emmanuel.gheerbrant@mnhn.fr).

EXPERIMENTAL MODEL AND SUBJECT DETAILS

The fossil specimens here identified as S. minor and cf. Stylolophus sp. come from the phosphate series of the Ouled Abdoun Basin (Morocco), and in particular from the North-Eastern quarries (Grand Daoui and Sidi Chennane quarries). Most of this material was found by local people living close to the phosphate quarries. Specimen OCP DEK/GE 667 of the species S. minor was donated to Office Cheriffien des Phosphates (OCP) collections by F. Escuilli e; specimen OCP DEK/GE 668, holotype of S. minor, was donated to OCP collections by S. Xerri. These specimens are in provisional deposit for study in the MNHN (CR2P laboratory), prior to their final deposit in the Office Cheriffien des Phosphates (specimens registered with OCP acronym). Casts are deposited in MNHN paleontological collections.

The age of S. minor and cf. Stylolophus sp. material was determined based on the associated selachian fauna and on a geochemical analysis that is detailed in Data S1B (see also Method Details below). S. minor comes from the Intercalary phosphate Beds II/I [START_REF] Yans | First carbon isotope chemostratigraphy of the Ouled Abdoun phosphate Basin, Morocco; implications for dating and evolution of earliest African placental mammals[END_REF][START_REF] Kocsis | Comprehensive stable isotope investigation of marine biogenic apatite from the late Cretaceous-early Eocene phosphate series of Morocco[END_REF], and possibly from the phosphate Bed I, and it is dated as early Ypresian, ca. 56 to 54 ma (see Data S1). Specimen MNHN.F PM53 of cf. Stylolophus sp. comes from upper levels of the local phosphate series of middle Ypresian age, probably from the so called ''sillons'' phosphate levels [START_REF] Yans | First carbon isotope chemostratigraphy of the Ouled Abdoun phosphate Basin, Morocco; implications for dating and evolution of earliest African placental mammals[END_REF][START_REF] Kocsis | Comprehensive stable isotope investigation of marine biogenic apatite from the late Cretaceous-early Eocene phosphate series of Morocco[END_REF]. The selachians found in the matrix of MNHN.F PM53 and the geochemical analysis support a middle Ypresian age and a stratigraphical correlation with the beginning of the EECO climatic event [START_REF] Yans | First carbon isotope chemostratigraphy of the Ouled Abdoun phosphate Basin, Morocco; implications for dating and evolution of earliest African placental mammals[END_REF][START_REF] Kocsis | Comprehensive stable isotope investigation of marine biogenic apatite from the late Cretaceous-early Eocene phosphate series of Morocco[END_REF], corresponding to an age of ca. 53-51 ma (see Data S1).

Study, preparation and casts of the material of S. minor and cf. Stylolophus sp were all made at the CR2P (MNHN) laboratory.

The new taxonomic actions established herein are registered in ZooBank LSID urn:lsid:zoobank.org:pub:8F4A215C-4A62-4B27-B42E-E17965590A38 .

METHOD DETAILS

Institutional abbreviations OCP DEK/GE: collections of the Office Cheriffien des Phosphates, Direction des Exploitations, Service G eologique, Khouribga, Morocco; MNHN.F: paleontological collections of the Museum national d'Histoire Naturelle, Paris, France.

Phylogenetic analysis

Comparative character analysis and phylogenetic relationships of Stylolophus minor and cf. Stylolophus sp. among various lophodont and non lophodont ungulate-like mammals were studied using maximum parsimony analyses with the programs TNT1.5, Winclada, and Nona [START_REF] Goloboff | TNT, a free program for phylogenetic analysis[END_REF][START_REF] Nixon | Winclada (BETA) Version 0[END_REF].

Details of the 209 studied dental and cranial characters and of the phylogenetic analysis are provided in Data S1. Our cladistic reference analysis and resulting MPTs, which recover the clade Paenungulatomorpha (stem and crown paenungulates), are based on the implied weighting analysis (Analysis 2, Data S1). The unweigthed analysis (Analysis 1, Data S1) recovers the Altungulata group clustering the Perissodactyla and Paenungulata, instead the Paenungulatomorpha found in the implied weighting analysis. It is not retained here because it conflicts with molecular phylogenies showing that the lophodont ''ungulates'' Perissodactyla and Paenungulata are convergent clades that belong respectively to the distinct major supraordinal placental clades Laurasiatheria (Euungulata) and Afrotheria.

Geochemical study

Trace element analyses of the matrix and in some case of the material of Stylolophus minor and cf. Stylolophus sp. provide valuable data on their stratigraphic provenance in the Ouled Abdoun Basin [START_REF] Kocsis | Gradual changes in upwelled seawater conditions (redox, pH) from the late Cretaceous through early Paleogene at the northwest coast of Africa: negative Ce anomaly trend recorded in fossil bio-apatite[END_REF]. The analyses were performed on polished surface of the fossils with Laser Ablation ICP-MS at the Institute of Earth Sciences of University of Lausanne in Switzerland (for details see [START_REF] Kocsis | Gradual changes in upwelled seawater conditions (redox, pH) from the late Cretaceous through early Paleogene at the northwest coast of Africa: negative Ce anomaly trend recorded in fossil bio-apatite[END_REF]). To support the stratigraphic origin of the here described fossils, Ce-anomaly was calculated from the obtained rare earth element concentrations: Ce/Ce* = 2Ce N / (La N +Pr N ), where N refers to Post Achaean Australian Shale normalized values. Then the data were compared with existing database [START_REF] Kocsis | Gradual changes in upwelled seawater conditions (redox, pH) from the late Cretaceous through early Paleogene at the northwest coast of Africa: negative Ce anomaly trend recorded in fossil bio-apatite[END_REF]. Further details are provided in Data S1.

DATA AND SOFTWARE AVAILABILITY

All data are provided in the Supplemental Information: Figures S1 andS2 and Table S1 include data related to Figures 3 and4 and STAR Methods. Phylogenetic data and analyses related to Figure 4


Victor De

Leon Gomez

Chiara Barone

Yannick Aoustin

Christine Chevallereau

Study of the walking efficiency of a human with a cane

This paper proposes a mathematical model of the walking with canes for an anthropomorphic biped with two identical legs with massless feet, two identical arms, and a torso. The walking is performed in the sagittal plane. The walking gait, which is cyclic, is composed of single support (SS) phases and impacts. The period of this cyclic walking is determined by the stride, because the motion of coupled arms is synchronized on this stride. The cane is considered massless. Thus in order to compare the walking with and without massless cane, the dynamic dynamic. Numerical tests show that the magnitude of the ground reaction in the stance foot is less with a massless-cane assistance than without one. Especially, the results prove that it is better to use canes with a handle.

Introduction

Walking can become difficult for people due to age, injuries disability or medical reasons such as the consequences of a stroke. Thus several works are devoted to the study and development of assistive devices. Since long time ago, the well-known canes/walking sticks or crutches are used to compensate temporary or even permanently a weakness in the lower limbs. Furthermore these assistive devices can sometime improve the walking activity, especially in the case of cerebral disorders. The canes/walking sticks are the most commonly used type of mobility aid than crutches [START_REF] Wade | Design and implementation of an instrumented cane for gait recognition[END_REF]. We can also observe the emergence of new mechanical devices as exoskeletons. Their usefulness depends on the magnitude of the handicap. The current exoskeletons, nevertheless, have limitations and they do not provide autonomous walking. To avoid falls, the use of these existing support exoskeletons for lower limbs require the use of canes [START_REF] Agrawal | First steps towards translating hzd control of bipedal robots to decentralized control of exoskeletons[END_REF]. In future, canes will not probably disappear among the rehabilitation tools. A stick can be also used by a bipedal robot for walking. In [START_REF] Shimizu | Biped walking robot using a stick on uneven ground[END_REF] a walking control strategy by using a stick is proposed for the walking of a biped robot on uneven terrain. The main advantage of using a stick is to obtain a more robust walking with a good energy efficiency. In [START_REF] Le | A humanoid mini-walking robot with a stick[END_REF] it is shown that a stick helps a small-walking robot to move around stably, by supporting most of its weight, and by avoiding an overpressure on its legs. An experimental intelligent cane is presented in [START_REF] Di | A real time posture control for stability improvement of intelligent cane robot[END_REF] and [START_REF] Di | Fall detection and prevention control using walking-aid cane robot[END_REF]. This cane is composed of an aluminium stick, which is fixed on an omni-directional mobile base with three wheels. A 6-axis force/torque sensor, on the handle of the stick, allows to estimate the user's walking intention. The users has shoes equipped of force sensors to detect a possible fall, then a control law adapts the velocity of the omni-directional mobile base to prevent this fall. Furthermore this cane is connected to a rescue center. In order to monitor the ambulation of Parkinson patients [START_REF] Pf | Wireless instrumented cane for walking monitoring in parkinson patients[END_REF] propose also an instrumented cane. These assistive devices modify the interaction of the human with his environnement, especially with the ground.

The dynamic effects of a cane as assistive device is not very well known. [START_REF] Ivanov | Formal'skii. Mathematical modeling of crutch walking[END_REF], with experimental data from capture motions and force platforms, Ivanov and Formal'skii propose a mathematical model of a human walking in sagittal plane. They show that in crutch walking, the ground reaction applied to the feet are lower than the reaction forces applied to the crutches. The crutch used to support the human use the axilla as fulcrum. The torque applied to the crutches by the shoulders is comparable in magnitude with the torques developed by the lower limbs. Despite these previous remarkable contributions, there is a lake of theoretical study about the cane walking. This is a gap that needs to be filled in order to design new canes to better overcome a disability on the lower limbs. In this paper we consider a walking of a human with two identical legs with massless feet, a torso, and two arms. Due to the motion of the arms, which is different from one step to the next step, the walking gait is determined over two steps. The stride is the period of the walking gait. Both steps of the stride are respectively composed of a SS phase and an impact. The assistance of the canes is defined by optimizing the torques, which are provided by the human. We compare the efficiency of the assistive canes, which takes place during the first step, and the redistribution of torques and ground reaction by assuming a weakness on the stance leg. For the assistance of the canes we consider two cases: 1) when the person applies only a force on the handle of the cane; and 2) when the person applies a force and a moment on this handle.

This paper is outlined as follows. The dynamic model of the human with and without canes is defined Section 2. The walking reference trajectory is presented Section 3. In Section 4, the statement of problem is developed.

The numerical results are shown in Section 5. Section 6 offers our conclusion and perspectives.

Dynamic model of the human with and without walking canes

The planar geometric model of a human without and with walking canes is shown in Fig. 1. This model is composed of two identical legs with a knee and a massless foot, a torso, two identical upper arms and two identical forearms linked in the sagittal plane by revolute joints at the hip, shoulders, ankles and elbows. The walking canes are also assumed massless. Although there are two upper arms, two forearms and two walking canes in this model, the arm segments and the canes will be named in singular throughout the rest of the text because the motion of both arms are assumed identical and coupled. The parameters of the human model are taken from the literature [START_REF] Formalskii | Locomotion of Anthropomorphic Mechanisms[END_REF]. The whole mass of the biped is 75 kg, its height is 1.75 m. Table 1 gathers the parameters of the model of human. The head of the human is taken into account in the parameters of the torso. Considering the human

Mass (kg)

Length (m) Inertia moment center of (kg .

I f a = 0.05 s f a = 0.22 Massless feet - l p = 0.30 - - Cane - l c = 0.8 - -
Table 1. Physical parameters of the human subject.

in SS phase with a flat foot of leg 1 and that his feet are massless, its configuration can be described with the following generalized vector: q = [q 1 , q 2 , q 3 , q 4 , q 5 , q 6 , q 7 , x, y] ⊤ .

The purpose of the vector definition ( 1) is to create a dynamic model of the robot. When the stance foot is flat on the ground, an unilateral constraint between the ground and the stance foot is written. When the cane is in contact with the ground, an external force r c is exerted by the ground to the tip of the walking cane. As the walking stick is massless, this force is lt ls lp l f a lua q 1 q 2 q 3 q 4 q 5 q 6 q 7

x, y (a) the exact opposite of the exerted force from the arm tip to the walking cane Fig. 1 (c). Let r cx and r cy be the horizontal and vertical components of this force r c and let M H be the moment applied at the point H from the massless walking stick, see Fig. 1 (b). As shown in Figure 1 (b), we show the eight torques applied at the hip-, knee-, elbow-, shoulder-, and ankle-joints. The dynamic model is defined as follows:

Γ 1 Γ 2 Γ 3 Γ 4 Γ 5 Γ 6 Γ 7 Γ 8 M H H (b) -rcx -rcy rcx rcy -M H H (c)
A(q)q + h(q, q) = DΓ + J ⊤ r1 r 1 + J ⊤ r2 r 2 + J ⊤ c   r cx r cy M H   , (2)
Here A(q) is 9×9 symmetric positive definite inertia matrix, h(q, q) is 9×1 vector, which groups the centrifugal, Coriolis, and gravity forces. Γ is 8 × 1 vector of the seven joint torques applied by the human. Vectors r i , with i = 1, 2, are the wrench ground reactions applied to the massless feet (and consequently to the ankle-joints). Vector r i = (r ix , r iy ) ⊤ is composed of the horizontal r ix and vertical r iy components of the ground reaction. Let us remark that the feet being massless we can consider a balance equation between the actuator torque applied at the ankle of the stance leg and the moment due to the ground reaction. Thus considering this balance equation we are able to constraint the center of pressure to stay inside the surface of contact of the sole with the ground for the design walking.

The following constraint equations are correct when the front or/and rear leg is/are on the bearing surface.

J ri ẍ + Jri ẋ = 0, for i = 1 or/and 2. ( 3
)
The matrices D, J r1 , J r2 , and J c can be calculated by using the principle of virtual work (an analysis of matrix D can be found in [START_REF] De-Leon-Gomez | A procedure to find equivalences among dynamics models of planar biped robots[END_REF]).

The reference periodic walking gait

The goal of this study is to compare the energy consumption during a gait cycle (i.e. a stride that is composed of a SS phase on the first leg an instantaneous double support and a SS phase on the other leg and an instantaneous second double), performed by the biped without and with its walking cane. The cane will assist the human only during the first phase.

During the second SS phase the arm will transfer the cane from back to front.

The reference walking gait is defined for the biped without the help of the assistive cane. That means that in Section 2 the component of the wrench applied on the cane r cx , r cy , and M H are equal to zero. This walking gait is periodic, i.e. all strides are identical. The design of the walking over a stride allows to recover the initial position of the massless cane and the arms for performing the next stride. In SS the stance foot has a flat contact with the ground and the torque applied in the ankle of the swing foot is null since massless feet are considered. When the swing foot impacts the ground the other foot takes off. The evolution of each joint of the locomotor system of the biped is prescribed with a polynomial function, of which the coefficients are calculated through a parametric optimization algorithm. The minimized criterion is the integral of the square of joint torques, called sthenic criterion [START_REF] Chevallereau | Bipedal robots: modeling, design and building walking robots[END_REF] for a given walking step length at several velocities; see [START_REF] Beletskii | Parametric optimization in the problem of bipedal locomotion[END_REF] and [START_REF] Chevallereau | Optimal reference trajectories for walking and running of a biped[END_REF] for further details. The cyclic walking gait is defined such that the conditions of the flat contact for the stance foot are satisfied, i.e. there is no rotation of this stance foot. The maximal magnitude of the joint torques are chosen to be 180 N.m. The reference trajectory of the hand is given during the stride, following the motion of a virtual cane Fig. 2. By using the inverse and kinematic models the joint evolution of the elbow and the shoulder are deduced. A sequence of figures that exhibit the stride for this reference trajectory is shown inFig. 2.

Study of the optimal distribution of the torques for the biped with walking cane

The biped with the help of the walking cane tracks the walking periodic gait defined in the previous Section. The cane assists the human only during the first SS phase on leg 1. For the human we assume a weakness in the hip joint of the stance leg during the SS phase. During the second SS the human brings his cane to the front. During the first SS, since the foot of the swing leg is massless we have Γ 8 = 0, and the dynamic model ( 2) includes nine equations. If the human applies a force and an moment on the handle of the cane there are 12 following unknown variables which are:

Γ 1 , Γ 2 , , Γ 3 , Γ 4 , Γ 5 , , Γ 6 , Γ 7 , r 1x , r 2y , r cx , r cy , M H . (4)
Thus, an optimization problem at each sampling time of the first support phase is defined by chosing variables r cx , r cy , andM H to track the walking periodic gait. The dynamic model ( 2) can be rewritten:

[D 1 , D 2 , D 3 , D 4 , D 5 , D 6 , D 7 , J ⊤ r1 ]      Γ 1 . . . Γ 7 r 1      = A(q)q + h(q, q) -J ⊤ c   r cx r cy M H   , (5)
where

D i with i = 1 • • • 7 is the i-column of matrix D.
If the human applies a force only on the handle of the cane there are 11 unknown variables which are:

Γ 1 , Γ 2 , , Γ 3 , Γ 4 , Γ 5 , , Γ 6 , Γ 7 , r 1x , r 2y , r cx , r cy . (6)
In this case the optimization problem deals with two chosen optimization variables r cx , r cy to track the walking periodic gait. The dynamic model ( 2) can be rewritten:

[D 1 , D 2 , D 3 , D 4 , D 5 , D 6 , D 7 , J ⊤ r1 ]      Γ 1 . . . Γ 7 r 1      = A(q)q+h(q, q)-[J ⊤ c1 , J ⊤ c2 ] r cx r cy , (7)
where J ⊤ c1 and J ⊤ c2 are the two first column of the matrix J ⊤ c . For people with disabilities, the minimisation of the human action for walking is an obvious criterion. Thus the following criterion for the first step will be considered.

C = Γ ⊤ Γ. (8)
Constraints are defined to ensure that the vertical component of the ground reactions both on the stance foot and the cane tip is positive. Furthermore, a constraint on the centre of pressure is applied in order to keep it inside the surface the sole of the stance massless foot.

In conclusion the statement of the problem is such that, let us define a given walking trajectory with its intrinsic features, how a human with his upper limbs and an assistive cane can compensate a weakness of his stance leg, what is the new distribution of the efforts between the lower and upper limbs.

Numerical results and discussion

Figures 34are devoted to the three cases, which are respectively: the human walking without a cane (blue curves); the human walking using the cane with an effort wrench with the components r cx , r cy , and M H (red curves); and the human walking using the cane by an effort force with the components r cx , r cy only (black curves). For the assistance with the cane, the magnitude of the applied forces along x-axis and y-axis are limited to 300 N. Of course it is physically possible to consider a greater limit magnitude but we would like to focus our study for elderly people with limited muscular capacities of the upper limb. As shown in Fig. 3 (a) the influence of the cane is big, as expected, in the ankle joint. That means that the magnitude of the ground reaction is much less with the cane as shown in Fig. 4 (a). We can also observe this effect in the knee and the hip of the stance leg. Moreover, there is also an influence of the cane on the swing leg. Fig. 4(b) shows the wrench applied by the cane on the hand for both cases. When the whole wrench is considered we can observe a big reduction of the joint torques for the knee and the hip of the stance leg, unlike when only the force is considered. However, there is no difference in the reduction of joint torques for the swing leg for the two cases of assistance. This simulated "handle" does not influence the vertical component of the ground reaction in the stance foot of the biped, Fig. 4 (a). There is just a small difference at the beginning for the vertical component of the ground reaction. The horizontal component of the ground reaction the difference is more influenced by the simulated "handle". We can observe that in general, a cane with a handle that can deals with the whole wrench is better for the assistance of the stance leg than a cane with a handle that deals only with the force.

Conclusion and perspectives

This paper is devoted to a preliminary study about the walking with a cane. This assistive device is well-known from long-time ago but few studies are devoted to its bio-mechanical benefits and thus the possible improvements of its geometric design. With a simple planar model we can analyze nu-merically the main features, which are experimentally well-known, of the walking cane. We proved that it is better to have a cane with a handle. In the future, it will be interesting to investigate the optimal values of the initial and final position and orientation of the cane. It will be interesting to look for the best physical parameter of the cane, its length, shape designed specifically for one human. Figure 3. Profiles of the torques applied in the seven joints, without assistance "blue curves"; by considering a wrench interaction between the human and the cane "red curves"; and by considering only force interaction between the human and the cane "black curves". ; by considering a wrench interaction between the human and the cane "red curves"; and by only considering a force interaction between the human and the cane "black curves". (b) Profiles of the efforts applied by the human to the cane: by considering only "black curves", by considering the wrench "red curve".

IEEE on Robotics and Automation

  m 2 ) mass (m) Human calf m s = 4.6 l s = 0.55 I s = 0.0521 s s = 0.324 Human thigh m t = 8.6 l t = 0.45 I t = 0.75 s t = 0.18 Human torso m T = 41 l t = 0.75 I T = 11.3 s T = 0.386 Human upper arm m ua = 3.9 l ua = 0.35 I ua = 0.044 s ua = 0.16 Human forearm m f a = 4.28 l f a = 0.45

Figure 1 .

 1 Figure 1. (a) The geometric model, generalized coordinates, and positions of the centers of mass of the links. (b) Inter-link torques of human and the moment M H . (c) The forces and moment applied to the walking cane.

Figure 2 .

 2 Figure 2. Biped alone, walking gait as a sequence of stick figures.

Figure 4 .

 4 Figure 4. (a) Profiles of the ground reaction components in the stance foo without assistance "blue curves"; by considering a wrench interaction between the human and the cane "red curves"; and by only considering a force interaction between the human and the cane "black curves". (b) Profiles of the efforts applied by the human to the cane: by considering only "black curves", by considering the wrench "red curve".

  , pages 5904-5909, Seattle, USA, 2015.

	t = 0 s	t = T /4 s	t = T /2 s
	t = 3T /4 s	t = T s	t = 5T /4 s
	t = 3T /2 s	t = 7T /4 s	t = 2T s


Issam Raïs
email: issam.rais@inria.fr

Mathilde Boutigny

Laurent Lefèvre
email: laurent.lefevre@inria.fr

Anne-Cécile Orgerie
email: anne-cecile.orgerie@irisa.fr

Anne Benoit
email: anne.benoit@ens-lyon.fr

Building the Table of Energy and Power Leverages for Energy Efficient Large Scale Systems

Keywords: Energy Leverages, High Performance Computing, Energy Efficiency

Large scale distributed systems and supercomputers consume huge amounts of energy. To address this issue, an heterogeneous set of capabilities and techniques that we call leverages exist to modify power and energy consumption in large scale systems. This includes hardware related leverages (such as Dynamic Voltage and Frequency Scaling), middleware (such as scheduling policies) and application (such as the precision of computation) energy leverages. Discovering such leverages, benchmarking and orchestrating them, remains a real challenge for most of the users. In this paper, we formally define energy leverages, and we propose a solution to automatically build the table of leverages associated with a large set of independent computing resources. We show that the construction of the table can be parallelized at very large scale with a set of independent nodes in order to reduce its execution time while maintaining precision of observed knowledge.

I. INTRODUCTION

Large scale distributed systems consume huge amounts of energy. This consumption has direct financial and environmental consequences for Cloud and supercomputer infrastructures.

To increase the energy efficiency of data centers and to lower their consumption, several techniques have been developed. These techniques, named energy leverages, can act at three levels: hardware, middleware, and application. At the hardware level, Dynamic Voltage and Frequency Scaling (DVFS) [START_REF] Al | Dynamic voltage frequency scaling (DVFS) for microprocessors power and energy reduction[END_REF], [START_REF] Mei | A survey and measurement study of GPU DVFS on energy conservation[END_REF] and shutdown techniques [START_REF] Al | Impact of Shutdown Techniques for Energy-Efficient Cloud Data Centers[END_REF], [START_REF] Benoit | Reducing the energy consumption of large scale computing systems through combined shutdown policies with multiple constraints[END_REF] constitute the two most studied leverages. DVFS reduces the voltage and frequency of processors when they do not require all their computational power. As for shutdown techniques, they consist in switching off entire servers or putting them in sleep modes when they are idle.

At the middleware level, data center managers can employ energy-efficient resource allocation policies to schedule the jobs by respecting energy budget or power cap [START_REF] Al | A scheduler-level incentive mechanism for energy efficiency in hpc[END_REF], consolidating the workload on fewer servers [START_REF] Speitkamp | A mathematical programming approach for server consolidation problems in virtualized data centers[END_REF], benefiting from intermittent renewable energy sources [START_REF] Li | Balancing the use of batteries and opportunistic scheduling policies for maximizing renewable energy consumption in a Cloud data center[END_REF], or modifying the number of used OpenMP threads [START_REF] Al | Hybrid MPI/OpenMP power-aware computing[END_REF].

Finally, leverages at the application level include green programming [START_REF] Al | Towards a Green and Sustainable Software[END_REF], vectorization techniques [START_REF] Al | Improving energy efficiency through parallelization and vectorization on intel core i5 and i7 processors[END_REF], and computation precision [START_REF] Han | Approximate computing: An emerging paradigm for energy-efficient design[END_REF].

While studies have been conducted on each of these leverages, only few work considers combining them. For instance, in [START_REF] Al | Hybrid MPI/OpenMP power-aware computing[END_REF], and [START_REF] Al | A run-time system for power-constrained HPC applications[END_REF], the authors combine the number of OpenMP threads and DVFS, and in [START_REF] Al | Designing autonomic management systems by using reactive control techniques[END_REF], the authors combine shutdown and DVFS leverages. In the case of shutdown, this leverage has obvious impacts on other leverages: in the off state, no other leverage can be employed at the application level, for instance. Indeed, the utilization of a given energy leverage can impact both the utilization and the efficiency of another leverage. Moreover, the variety of leverages and the complexity of modern hardware architectures, in terms of size and heterogeneity, makes the energy efficiency more complex to reach for users. The authors of [START_REF] Eastep | Global Extensible Open Power Manager: A Vehicle for HPC Community Collaboration Toward Co-Designed Energy Management Solutions[END_REF] and [START_REF] Al | Run-time exploitation of application dynamism for energyefficient exascale computing (readex)[END_REF] propose energy-aware runtimes that exploit the dynamic behavior of HPC applications in order to improve performance and energy-efficiency. Yet, energy leverages' characterization is a prerequisite for building such runtimes.

In this paper, we propose a first approach toward a completely automated process to characterize the energy leverages available on data center servers. The key idea of our contribution consists in building a score table with a value for each leverage combination and each studied metric. These scores are obtained through the execution of a representative benchmark. Based on this score table, we can provide hints to users about the most suitable solution for their application.

This paper makes the following contributions:

1) We propose a generic framework formalizing the combination of leverages through the definition of a table of energy leverages; 2) We present a comprehensive experimental method based on benchmarks and a detailed overview of its concrete implementation to build the table of energy leverages; 3) We analyze experimental results on several servers demonstrating how to parallelize the building of the table.

The remaining of this paper is structured as follows. Section II presents our definition and formalism of a leverage and details the leverages that are used as examples in this study. Section III shows our process to build the table of leverages, and Section IV explains how this formalism is implemented. Section V presents the experimental setup and a first full example of table of leverages. Section VI demonstrates the parallelization of the creation process of the table of leverages. Finally, Section VII concludes this work and gives perspec-tives.

II. LEVERAGE DEFINITION

A leverage L is composed of S = {s 0 , s 1 , . . . , s n }, the set of available valid states of L, and s c , the current state of L.

An energy or power leverage is a leverage that has an impact on the power or energy consumption of a device: the energy consumption may differ depending on the current state at which the application is executed. Of course, switching from one state to another can have a cost in terms of time and energy, but we focus on studying the impacts of leverage combinations over a single intensive application phase, and thus we do not study the switching costs between states in this work.

We focus on three leverages that are available on current hardware: multi-thread, computation precision and vectorization. While multi-thread is a middleware level leverage, the two last are at the application level, as detailed below.

1) Multi-thread leverage: Multi-core architectures are nowadays the de facto standard in modern supercomputers. The first studied leverage is a middleware-level leverage that permits the usage of multiple cores during computation. OpenMP [START_REF] Al | OpenMP: an industry standard API for shared-memory programming[END_REF], a well-known application programming interface abstraction for multi-threading, can be used to exploit this intra-node parallelism of multi-cores. In particular, it is well known for its simplicity and portability. It consists of a set of directives that modifies the behavior of the executed code, where a master thread forks a specific number of slave threads that run concurrently. This multi-thread leverage increases the CPU utilization of the node. Consequently, because of the nonpower proportionality of current hardware architectures [START_REF] Al | Impact of Shutdown Techniques for Energy-Efficient Cloud Data Centers[END_REF], this leverage can improve the energy efficiency of the node.

This leverage is denoted by nbThreads or #Threads, and the set of states is {1, . . . , n max }, where 1 means that one OpenMP thread is used, and n max corresponds to the maximum number of threads that could be launched simultaneously on the node without hyperthreading.

2) Computation precision leverage: The second leverage belongs to the application level and exploits the various computation precision options available on actual hardware (i.e., int, float, double). Such a leverage alters the precision of the results computed by the application, but lower precision translates into shorter data representation and so, less computation and less energy consumption. At the application level, the user can specify a desired Quality-of-Service that can be expressed as accessible computation precision states.

This precision leverage is denoted by Precision or Prec., and the set of states is {int, float, double}, corresponding to the data format for the application. For each of these states, a different code version is provided.

3) Vectorization leverage: Finally, the last studied leverage concerns the application level. Current CPUs allow the usage of vectorization capabilities to exploit intra-core parallelism. On Intel architectures, it started with MMX instruction in Pentium P5 architectures in 1997 [START_REF] Al | MMX technology extension to the Intel architecture[END_REF]. It was then extended to SSE [START_REF] Al | Embedded Pentium (R) processor system design for Windows CE[END_REF]. SSE was then extended to SSE2, SSE3, SSSE3 and finally SSE4. AVX [START_REF] Lomont | Introduction to intel advanced vector extensions[END_REF] then introduces new instructions, followed by AVX2 and finally AVX512 available in XeonPhi architecture. In this paper, we focus on SSE3 and AVX2, which are representative of the SSE and AVX families. These instruction sets permit single instruction on multiple data (SIMD) at application level.

This vectorization leverage is denoted by Vectorization or Vect.. The set of states is {none, SSE3, AVX2}, where none means that no vectorization is used. For each of these states, a different code version is provided using the adequate compilation flags for each version.

Note that the methodology proposed in this paper can be applied to any number and any type of energy leverages, even though we focus here on three leverages, chosen to be representative examples of available energy leverages on modern architectures.

III. FORMALISM OF TABLE OF LEVERAGES

In this section, we describe the methodology applied to build a table of energy leverages, which relies on metrics and benchmarks to characterize the performance and energy impact of each leverage combination on a given node. For each metric and each benchmark, a score is attributed to a given leverage combination. First, we describe the basic concepts used to build the table: the metrics and benchmarks. Then, we present the formal definition of the table of leverages, and finally, the methodology for building it.

A. Metrics

Leverages may influence the quality of service or performance of an application. For instance, shutdown techniques may induce latency in waking up the required nodes. Consequently, for these leverages, users need to determine their acceptable trade-off between energy-related metrics and performance metrics.

Here, three different metrics that represent both energy and performance constraints are explored. These metrics are measured for a given period of time corresponding to the time spent during the execution of the benchmark.

The two first metrics are energy and power related metrics. To define them, we introduce the following notations:

• T = {t 0 , . . . , t N } is the set of time stamps of energy consumption measurements of a given run; t 0 and t N represent the starting and ending timestamps, respectively; • p j , j ∈ [0, N ], represents the power consumption (in Watt), of the considered node for the timestamp t j .

a) Average Watt: denoted avrgW att, it represents the average power consumption of a chosen run. It is defined as follows:

avrgW att = j∈[0,N ] p j N + 1 . (1)
b) Joules: denoted Joules, it represents the energy consumption of the run. It contains the energy consumption of the complete node used between t 0 and t N . It is defined as follows:

Joules = j∈[0,N -1] (t j+1 -t j ) × p j . (2)
c) Execution time: The execution time, denoted T ime, is the whole execution time of a run (initialization time included).

B. Benchmarks

A benchmark corresponds to a self-contained application that is representative of typical applications or portions of applications. The benchmark is compiled before the run, and once launched, the metrics previously defined are collected during its execution.

Here, for the sake of clarity, we evaluate only one benchmark for a set of embedded leverages. We chose to focus on a well-known CPU intensive code: the line per line matrix multiplication (LpL MM) of dense random matrices. The same algorithm is implemented for the various leverage combinations. As detailed in Section II, the considered leverages are multi-thread, computation precision and vectorization. For the last two leverages, a different state means a different version of code, here generated by hand. Automatic generation is possible but it is not the focus of this paper.

C. Formalization of the table of leverages 1) Format of the table of leverages:

Here, we describe how to compute the score associated to each metric for each leverage. Let X, Y, Z be the sets of available states of three leverages χ, ψ, ω: X = {x 0 , . . . , x nx }, Y = {y 0 , . . . , y ny }, and Z = {z 0 , . . . , z nz }.

Let g 1 , . . . , g m be the measured metric functions, as for instance avrgW att, Joules, and T ime. For all u (1 ≤ u ≤ m), g u (x i , y j , z k ) is the value of metric g u for the states x i , y j , z k respectively for the leverages χ, ψ, ω.

In the table of leverages, each line corresponds to a combination of states for each leverage and the columns correspond to the measured metrics. In order to ease the comparison, we normalize each value on the minimum value for each metric. These normalized values constitute the scores indicated in the table of leverages. Let h 1 , . . . , h m be the normalized versions of g 1 , . . . , g m . So, we have, for 1 ≤ u ≤ m:

h u (x i , y j , z k ) = g u (x i , y j , z k ) min x i ∈X,y j ∈Y,z k ∈Z g u (x i , y j , z k )
, with h u (x i , y j , z k ) being the value in the table of leverages in column of metric u and corresponding to the line for the states x i , y j , z k respectively for the leverages χ, ψ, ω.

2) Methodology to build the table: Building the table of leverages requires to run the benchmark in its adequate version for each leverage combination. Hereafter, we describe our methodology for running all the required executions.

Algorithm 1 shows the generic pseudo-code to execute the adequate benchmark version on the correct leverage combination for a given set of metrics. This algorithm has two inputs: LeverageT ree is a tree representing the set of Algorithm 1: Building the table of leverages: benchmark execution for each leverage combination for a given set of metrics.

Input: LeverageTree: leverages to benchmark Input: SelectedStates: name of states of leverages being currently benchmarked 1 mM : metric measurements; 2 for s c in root(LeverageTree).S do 3 if root(LeverageTree) is leaf then selected states on the studied leverages, and SelectedStates keeps trace of every current state of leverage involved so far. The functions root(X) and unseen children(X) return respectively the root of tree X, and the first unseen children node of tree X. mM corresponds to an entity gathering metric values (as defined before in our case: avrgW att, Joules, and T ime). Benchmark corresponds to the entity that matches the current state of every leverage SelectedStates and the corresponding binary file to execute, exec corresponds to the execution of the benchmark. Thus, for all the considered leverages (LeverageT ree), the algorithm is executed recursively over their respective states (S) and collects the metrics (mM ) before moving to the next leverage combination. The metrics gathered during the executions are saved in the T ableOf Leverages entity. Figure 1 shows an example of input used for Algorithm 1 in the following table of leverages of this paper. Rounded bullets represent states of the three considered leverages. The benchmark chooses the corresponding binary, for leverages having different binaries in set of states S, here Precision and Vectorization. Leverage nbThreads changes its state through environment variable.

When the execution of Algorithm 1 with Figure 1 as input is finished, the table of leverages is complete for the considered benchmark.

IV. IMPLEMENTATION OF FORMALISM

In order to be able to build the table of leverages, we created a framework able to identify available known leverages on a given hardware, benchmark the leverages combination and collect the associated metrics. This tool can run on a single node or on an entire cluster. It is designed to be as flexible as possible on three basic concepts: leverage, metric and benchmark. This framework fits the needs of a wide type of users, going from basic users without specific knowledge to more experts ones capable of implementing new leverages, benchmarks and metrics collection methods.

A. Leverages

As shown in Figure 2, the framework provides multiple interfaces, or contracts, to fully describe our basic concepts. These contracts are implemented through a fully abstract class, forcing a class inheriting from it to implement the needed functions. Thus, every leverage class must be able to detect it's availability (is leverage available()), to retrieve it's current status (get actual status()), to retrieve it's list of available statuses (get all statuses()) and to change it's actual status with a valid one (set new status()). For example, the availability of the DVFS can be validated if the file /sys/devices/system/cpu/cpu0/cpufreq exists. The actual status of the DVFS leverage for a specific core, here 0, can be found in a configuration file /sys/devices/system/cpu/cpu0/cpufreq/cpuinfo cur freq. Reading the scaling available frequencies 1 file permits to extract all statuses. Finally, the current state can be changed using the command cpufreq-set.

B. Metrics

The framework provides an interface for the metrics. It imposes to be able to start and end the monitoring of a metric. It also imposes a metric to check the validity of obtained results (check validity results()). The actual implementations of the metric contract allows various focus for various metrics.

Grid'5000 provides the Kwapi API [START_REF] Al | A Generic and Extensible Framework for Monitoring Energy Consumption of OpenStack Clouds[END_REF], to get the collected data from the wattmeters for a given time period. Once a benchmark has been executed on a node, the contract asks Kwapi for the node's consumption during this time period.

Another possibility given by Grid'5000 is to use the live metric webpage. This webpage returns the consumption metrics of the nodes of Grid'5000 every second. We created a script that collects them every second. The framework then gets the metrics from the script by giving the starting and ending timestamps of the benchmark execution.

Such method could also be exported to platforms without wattmeters. For example, we implemented the contract for 1 Path file is /sys/devices/system/cpu/cpu0/cpufreq/ captors such as RAPL or IPMI, also to get energy related metrics.

The framework also implements a contract to retrieve FLOPs (FLoating point OPeration per seconds). In order to retrieve the FLOPs, a script that collects the flops metrics during a benchmark execution using the PAPI framework is deployed on used nodes. This method is not specific to Grid'5000 and could be used on a different architecture.

C. Benchmark

The final contract is relative to the benchmark execution. The first function executes the given binary. The second gives the current states of application leverages. A family of leverage is relative to the application. Thus, the state of application leverages changes for every binary (get app leverages state()).

The framework copies and executes the given binary on chosen nodes. We assume that compiled and ready to used binary files are passed to the framework.

D. Construction of the table of leverages

The table of leverage class uses previously presented contracts to implement algorithm 1. Various mode of construction are provided. a) Default method: construct() method runs the same experiment on every node. Thus, every node will make the same leverage exploration. This method can be time consuming. For example, using our testbed, combining the first and last status of nbThreads leverage, Precision (int, float and double) and Vectorization (SSE3 and None) leverages, takes approximately 1 hour and 30 minutes.

b) Automatic node spread work method: In the construct parallel() method, the framework runs one scenario by dividing and assigning automatically work on nodes. The execution time of the framework would be divided by the number of used nodes. If we take the previous example combining the nbThreads, Precision and Vectorization, with 5 nodes, the execution time of the framework for this scenario is around 18 minutes. However, the user will need to have a good knowledge of the nodes and asked metrics in order to ensure coherent results.

LEVERAGES

In this section, we present the table of leverages built on a node from our experimental testbed.

A. Experimental setup

To evaluate our methodology in various computing environments, Grid'5000, a large-scale and versatile testbed for experiment-driven research in all areas of computer science, is used as a testbed [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF]. Grid'5000 deploys clusters linked with dedicated high performance networks in several French cities (Lille, Nancy, Sophia, Lyon, Nantes, Rennes, Grenoble). As our focus is on energy and performance related metrics, we used the Grid'5000 Lyon site, where the energy consumption of every node from all available clusters, as shown in Table I, is monitored through a dedicated wattmeter, exposing one power measurement per second (0.125 Watts accuracy).

B. Table of leverages for three leverages

We applied our previous methodology for the three chosen leverages to the CPU intensive benchmark. This allows us to explore all possible states of chosen leverages, and thus to build a complete table of leverages. In this paper, it has the following format: the first three columns present the states of the nbT hreads, P recision, and V ectorization leverages respectively, while the last three columns show the normalized results of the three metrics avrgW att, Joules, and T ime, respectively, for every combination of leverage. As described in Table II, a line of the table of leverage represents results of all gathered metrics for the execution of a representative load for a chosen combination of leverages. The results are normalized as shown in Section III-C. The table of leverages gathers the knowledge of a node, here Nova (Table I), for a given workload done for multiple states of leverages combined.

Note that the best combination for all metrics used here is always the {32, int, AVX2} combination. This result is the best combination to choose only if we have no constraints about leverage choices. For example, this table could help a user to choose a combination taking into account a fixed leverage state. Or to answer the following question: is there a leverage or a state of leverage that is always better for a given metric?

VI. PARALLELIZATION OF THE TABLE CONSTRUCTION

The construction of the table of leverages may take a long time if many different leverage combinations are considered. In this section, we explain how the construction could be parallelized, so that the time to generate a complete table of leverages could be significantly reduced.

A. Re-usability of energy and performance metric, one node

The first hypothesis to be considered, is the fact that a node, exposed to the same load, gives the same metric results, with very low variation.

Previous work on HPC applications indicates that phases could be recognized thanks to an analysis of existing registers [START_REF] Chetsa | A user friendly phase detection methodology for hpc systems' analysis[END_REF]. We run various intensive workloads using stress 2 , a tool that applies a specific phase to the used node. We execute 30 times every stress on a unique "Nova" node. Figure 3 shows results of such a protocol. For HDD stress (hard drive usage), three types of patterns could be recognized. The first one from t = 0s to t = 10s and last one from t = 35s to t = 80s are the same for every run. The variation occurs between t = 10s and t = 35s. When the disk is active and writing in various regions, the energy cost could differ depending on the chosen region for writing. We observe that for CPU, IO and RAM stress, all runs have approximately the same behavior, meaning that one run on the same node always has the same energy consumption, for this kind of stress.

B. Re-usability of energy and performance metric, one family hardware

The second hypothesis that we have to evaluate here is the fact that extracted metrics could also be used by different nodes with the same hardware.

We stress several nodes of the same hardware (Taurus or Nova clusters) to observe how the standard variation concerning various energy-efficiency and performance-related metrics evolve. We chose these two families of hardware to evaluate a newly acquired node family ("Nova", 2017) and an old one ("Taurus", 2012). This evaluation is done with various intensive workloads that stress differently the energy consumption of a node (CPU, IO, hard drive usage, RAM). workloads. For this experiment, every node is doing the same work at the same time. We get interesting metrics for every run (10 run averages on every node). We then average interesting values for families of nodes. 10 Taurus nodes were used, while 5 Nova nodes were used. The standard variation for the three chosen metrics are negligible for all stress benchmarks, except HDD (as already explained in the previous subsection). Even for the Joules metric, we note that the variation is under the second of idle consumption of both nodes for every benchmark, meaning that differences between metric results from the same family of hardware are negligible.

These experiments show that for the same workload, same energy and performance behavior could be witnessed for various nodes having the same configuration.

C. Table of leverages, variability between nodes

In this section, we evaluate the same hypothesis for our previously defined table of leverage (Table II) with 5 nova nodes. For every leverage combination, we evaluate the standard deviation of obtained metrics on all nodes. For every leverage combination, we extract the average and the standard deviation of all used nodes. To understand these numbers easily, we also extract the percentage that represents the standard deviation to the average.

Table IV presents the same exploration that the previously presented Table of leverages II for 5 nova nodes with average, standard variation and percentage represented by the standard deviation to the average, respectively, for every extracted metrics. Table V presents the same exploration but for Taurus nodes. The same matrix dimension is used for both exploration (8192). Note that Taurus nodes don't have AVX as available state for the vectorization leverage.

Table IV underlines the fact that the most stable metric is undeniably time, with only three combinations of leverage above or equal to 1% and only one combination, {1, int, none}, with a standard deviation above 1 second. Same goes for Table V, where only two combinations of leverages are above 1%.

For Joules metric, every percentage is under 3.33% for Table IV, except for the less consuming combination of leverages, {32, int, AVX} at 7.07%, which is still reasonable. This high value for this combination could be explained by the fact that our wattmeters are giving a power value every second, thus if a run is a bit longer than the 9 seconds, it will get an extra power value that others won't have. Because there are not a lot of values (one per second), an extra value on such a short run has high repercussions on the standard deviation. Because runs are longer on Table V, percentage are more stable, between 2.34% and 1.32%. Finally, for the AvrWatt metric, every percentage is under 3.27% for Table IV and under 3.55 for Table V.

These previous results (Table III, Table IV and Table V) analysis underlines the fact that for the same workload, same energy and performance behavior could be witnessed for various nodes having the same configuration, under a low percentage of difference. Thus, for large scale computing systems with large amount of computing nodes with the same configuration, the table of leverage could be done on only one node, or derived from a segmented construction on multiple nodes, and used as knowledge for other nodes.

VII. CONCLUSION

Energy efficiency is a growing concern. In the context of HPC and datacenters where the size of infrastructures grows drastically, energy consumption has to be taken into account as a high expense.

There is a wide range of hardware and software techniques, that we formally define as leverages, that permits to modulate the computing capabilities and/or the energy/power used by a device. We propose a generic solution to create a score table about multiple metrics for a given set of leverages, called the table of leverages. We propose a fully implemented and highly modular framework which allows an easy discovery, combination and exploration of leverages. Finally, we underline the fact that parallelization of the building of the table of energy and power leverages permits high gain of time while maintaining high precision.

Possible future work concerns reducing the completion time for building such a table. In fact, the time to solution here could be greatly reduced, for example by predicting which run is not necessary to know values of relevant metric using learning or prediction techniques.

4

  Add s c to SelectedStates; 5 mM .start(); 6 Benchmark(SelectedStates).exec(); 7 mM .end(); 8 tableOf Leverages[SelectedStates] ← mM ;

Fig. 1 :

 1 Fig. 1: Example of LeverageT ree input for Algorithm 1.

Fig. 2 :

 2 Fig. 2: Framework UML diagram

Fig. 3 :

 3 Fig. 3: Nova-1, 30 runs of various stresses for Time (seconds) and Power (Watts) metrics

TABLE I :

 I SERVER NODE CHARACTERISTICS

	Features	Taurus	Nova
	Server model	Dell PowerEdge R720 Dell PowerEdge R430
	CPU model	Intel Xeon E5-2630	CPU E5-2620 v4
	# of CPU	2	2
	Cores per CPU	6	8
	Memory (GB)	32	32
	Storage (GB)	2 x 300 (HDD)	2 x 300 (HDD)
	Date of arrival	11.2012	03.2017

TABLE II :

 II

  TABLE OF ENERGY LEVERAGE STATES FOR LPL MM

		BENCHMARK ON A NOVA NODE
	Leverage states #Threads Prec.	Vect.	avrgWatt(W) Joules(J) Time(sec)
	1	int	none	1.05	65.09	61.89
	1	int	SSE3	1.06	28.26	26.56
	1	int	AVX2	1.06	29.32	27.67
	1	float	none	1.05	72.97	69.67
	1	float	SSE3	1.06	33.8	31.89
	1	float	AVX2	1.05	36.8	34.89
	1	double	none	1.06	81.59	76.89
	1	double	SSE3	1.07	58.52	54.89
	1	double	AVX2	1.06	57.72	54.22
	32	int	none	1.43	13.48	9.44
	32	int	SSE3	1.4	4.68	3.33
	32	int	AVX2	1.0	1.0	1.0
	32	float	none	1.45	7.4	5.11
	32	float	SSE3	1.41	3.76	2.67
	32	float	AVX2	1.56	3.11	2.0
	32	double	none	1.53	8.34	5.44
	32	double	SSE3	1.53	8.52	5.56
	32	double	AVX2	1.54	7.0	4.56

TABLE III :

 III AVERAGE (AV.) AND STANDARD DEVIATION (STD.) Metrics and standard deviation averages of families of nodes are exposed in Table III for CPU, HDD, IO, and RAM 2 https://people.seas.harvard.edu/ ∼ apw/stress/

	OF VARIOUS WORKLOADS FOR VARIOUS ENERGY AND
	PERFORMANCE RELATED METRICS FOR VARIOUS HARDWARE
		ARCHITECTURES
	Hardware family	Joules (J)	AvrgWatt(W)	Time(t)
		Av. -StD.	Av. -StD.	Av. -StD.
		CPU
	Taurus	6807.0 -68.8	205.84 -1.37	32.81 -0.39
	Nova	4998.86 -49.3	154.91 -1.09	32.06 -0.43
		HDD
	Taurus	5055.98 -365.33	140.58 -2.98	35.85 -2.4
	Nova	9381.94 -251.5	107.8 -0.57	87.01 -2.47
		IO
	Taurus	3957.52 -34.98	123.46 -0.21	32.0 -0.3
	Nova	4194.53 -68.06	130.3 -0.67	32.04 -0.66
		RAM
	Taurus	5097.83 -55.81	222.14 -2.2	32.5 -0.52
	Nova	7282.26 -115.89	158.53 -0.8	31.93 -0.44

TABLE IV :

 IV TABLE OF ENERGY LEVERAGE STATES FOR LPL MM BENCHMARK ON A 5 NOVA NODES, AVERAGE, STANDARD DEVIATION AND PERCENTAGE OF STANDARD DEVIATION FOR AVERAGE

	Leverage states			avrgWatt (W)			Joules (J)			Time (sec)
	#Threads	Prec.	Vect.	avrg	std dev % std dev	avrg	std dev	% std dev	avrg	std dev % std dev
	1	int	none	118.99	3.53	2.96	66041.42 2016.32	3.05	555.0	1.1	0.2
	1	int	SSE3	120.48	3.44	2.86	28844.54	865.88	3.0	239.4	0.49	0.2
	1	int	AVX2	120.02	3.38	2.81	29862.48	881.6	2.95	248.8	0.4	0.16
	1	float	none	118.55	3.32	2.8	74258.92 2085.38	2.81	626.4	0.49	0.08
	1	float	SSE3	120.08	3.35	2.79	34416.58 1005.18	2.92	286.6	0.49	0.17
	1	float	AVX2	119.48	3.44	2.88	37445.13 1079.41	2.88	313.4	0.49	0.16
	1	double	none	120.06	3.43	2.86	83060.58 2379.14	2.86	691.8	0.4	0.06
	1	double	SSE3	120.75	3.48	2.88	59578.0	1735.06	2.91	493.4	0.49	0.1
	1	double	AVX2	120.45	3.44	2.86	58661.37 1740.92	2.97	487.0	0.89	0.18
	32	int	none	161.0	4.41	2.74	13684.79	374.68	2.74	85.0	0.0	0.0
	32	int	SSE3	158.72	4.67	2.94	4761.68	140.14	2.94	30.0	0.0	0.0
	32	int	AVX2	113.39	3.62	3.19	1044.21	73.82	7.07	9.2	0.4	4.35
	32	float	none	163.04	4.46	2.73	7499.91	205.06	2.73	46.0	0.0	0.0
	32	float	SSE3	158.58	4.13	2.6	3805.9	99.07	2.6	24.0	0.0	0.0
	32	float	AVX2	174.68	5.7	3.26	3211.55	48.17	1.5	18.4	0.49	2.66
	32	double	none	171.79	5.14	2.99	8450.54	198.45	2.35	49.2	0.4	0.81
	32	double	SSE3	172.62	4.97	2.88	8594.98	205.08	2.39	49.8	0.4	0.8
	32	double	AVX2	173.6	5.27	3.03	6978.92	231.53	3.32	40.2	0.4	1.0

TABLE V :

 V

  TABLE OF ENERGY LEVERAGE STATES FOR LPL MM BENCHMARK ON A 5 TAURUS NODES, AVERAGE, STANDARD DEVIATION AND PERCENTAGE OF STANDARD DEVIATION FOR AVERAGE

	Leverage states			avrgWatt (W)			Joules (J)			Time (sec)
	#Threads	Prec.	Vect.	avrg	std dev % std dev	avrg	std dev	% std dev	avrg	std dev % std dev
	1	int	none	143.3	3.34	2.33	101226.43	2371.0	2.34	706.4	0.49	0.07
	1	int	SSE3	146.49	2.57	1.76	39406.17	693.39	1.76	269.0	0.0	0.0
	1	float	none	143.74	2.63	1.83	109872.73 2050.37	1.87	764.4	0.49	0.06
	1	float	SSE3	146.56	2.7	1.84	46926.95	842.17	1.79	320.2	0.4	0.12
	1	double	none	145.88	2.89	1.98	121376.55 2457.85	2.02	832.0	0.63	0.08
	1	double	SSE3	147.59	2.71	1.84	81676.02	1498.01	1.83	553.4	0.49	0.09
	24	int	none	215.39	2.9	1.35	24684.46	420.55	1.7	114.6	0.49	0.43
	24	int	SSE3	211.95	2.99	1.41	8308.44	146.41	1.76	39.2	0.4	1.02
	24	float	none	218.57	3.3	1.51	14906.06	197.2	1.32	68.2	0.4	0.59
	24	float	SSE3	210.8	3.15	1.5	6619.05	147.45	2.23	31.4	0.49	1.56
	24	double	none	228.68	3.38	1.48	16739.08	252.47	1.51	73.2	0.4	0.55
	24	double	SSE3	225.99	3.55	1.57	16044.3	221.76	1.38	71.0	0.63	0.89

ACKNOWLEDGMENTS

This work is supported by the ELCI project, a French FSN ("Fonds pour la Société Numérique") project that associates academic and industrial partners to design and provide software environment for very high performance computing. Experiments were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (https://www.grid5000.fr).