Baptiste Nicolas Todd
email: todd@demogr.mpg.de

Baptiste Coulmont
email: baptiste.coulmont@cnrs.fr

Naming for kin during World War One

Naming for Kin during World War I: Baby Names as

Markers for War

Introduction

The structure of the family has long influenced the choice of baby names. 'Naming for kin', or the transmission of names from one generation to the next, is known to be more frequent in families with many children or comprised of multiple generations. Naming children after kin as a general rule for name choices has dominated the European naming system of the early modern period. From the late 18th century onwards, naming for kin gradually declined, giving way to choices more closely determined by parental tastes and beliefs. In such circumstances where baby names are the outcome of parental choices, they enable the study of how people react to historical events. Names have for instance been used to investigate popular support to Regime change before the era of public opinion polls, reactions to the Chinese Cultural Revolution, mass incarceration of US citizens of Japanese descent following the attack on Pearl Harbor, or diplomatic crises. In all cases, rapid changes in the popularity of specific names could be observed, e.g. in the United States an increased frequency of presidential name following a presidential assassination attempt. Less attention has been paid to systematic modifications of naming behavior. 3 World War One (WW1) unquestionably caused major social disruptions in France.

Starting on Sunday, August 2, 1914, millions of young men were mobilized, many among them to join fighting units. Couples were hastily separated. The majority of women immediately faced dire practical problems. The most pressing issue was harvest in the countryside, while urban areas saw an alarming rise in unemployment. Violent combats began in the third week of August and, immediately following, large parts of North-Eastern France were invaded by the German army. The attitude of European populations during the War has been researched at least since the seminal effort of Jean-Jacques Becker. The very early phase of the conflict has been of special interest. 3 For the traditional naming for kin practice in Western Europe, see Agnès Fine, "L'héritage Du Nom de Baptême," Annales ESC, IV (1987) Previous work notably found that only very late in July 1914 did French people realize a war could actually break out. The fighting was then expected to be short: most thought the conflict would be over by the end of 1914. Furthermore, it seems to have been unclear how much risk soldiers leaving to the front would be exposed to, before it became obvious to all that modern weapons were causing unprecedented casualties. 4 The historical sources used so far have been diverse: administrative reports, letters, diaries or newspapers have all shed some light on the perception of the War by ordinary people. None are as systematic as baby names, the exploration of which remains in its infancy in the context of WW1. Recently, heightened transmission of the father's name as a response to his death at the front has been found in an urban cohort of war orphans born 1914-1916. Specifically, a prenatal loss of father was associated with a 2.7-fold increase in the probability of transmission of the father's name, both to male and, in a feminized form, to female offspring (e.g. Joseph → Joséphine). This increased transmission was highest among officers, leading to the hypothesis that this naming practice was a concrete expression of the 'cult of the fallen soldier' phenomenon first put forward by George Mosse. This heroization process had so far been most readily investigated either on case studies or at the community level, e.g. through the 4 See Jean-Jacques Becker, 1914 : Comment Les Français Sont Entrés Dans La Guerre Contribution à L'étude de L'opinion Publique, Printemps-été 1914(Paris, 1977) and; Jean Jacques Becker, Les Français Dans La Grande Guerre (Paris, 1980) for early works; for more recent reviews see Jean-Jacques Becker, "Willingly to War. Public Response to the Outbreak of War," Berlin, 1914-1918-Online. International Encyclopedia of the First World War, (2015); André Loez, 14-18, Les Refus de La Guerre : Une Histoire Des Mutins (Paris, 2010). examination of the war memorials ("Monuments aux Morts") erected by municipalities after 1918. Previous work on orphans' names was nevertheless limited by a small sample size, an exclusively urban context, a lack of comparison to the antebellum period and the sole focus on paternal names. 5This research note aims at moving forward the systematic description of attitudes during the First World War by focusing on the determinants of kin (father and uncle) name transmission, going beyond the aformentioned limitations of previous work. Our objective was twofold. First, document ordinary people's perception of the conflict.

Second, investigate whether any evidence for heroization of soldiers could be found in naming practices following kin death. born 1905-1925 in France, to which information on the father and uncles was also attached. Specifically, the following information was available for these individuals: family name, first and middle names, sex, place and date of birth, date of death; for their fathers: first and middle names, dates of birth and death; and for their uncles: line (maternal/paternal), first and middle names and date of death. 6Record linkage. Since every time a descendant mentions a person as part of their family tree, that person is recorded in the database, one person can be recorded multiple times. To identify and merge such duplicates, we used the EM algorithm implemented by the RecordLinkage package of the R programming language. This procedure also helps correct for errors in data, since each characteristic of merged individuals is chosen by majority voting among duplicates (see Table 1 for an illustrative example). Due to the high computational cost of the deduplication process, we stratified on sex and year of birth and ran it on a computer cluster. This procedure yielded N = 3,056,387 distinct individuals born in France between 1905 and1925. All computer codes needed to replicate the deduplication process can be found at https://github.com/nptodd/NamingForKinWW1. 7 6 Geneanet is available: https://www.geneanet.org/ . Name transmission. We focused on first names. In order to include females in the analysis, comparison of father's and offspring's names was limited to the first 4 letters, e.g. transmission is considered to have occurred when the father's name is Simon and the daughter's name is Simone. This definition is conservative, since it misses some forms of transmission (e.g. Albert → Berthe), though those are likely to be quantitatively of minor importance. There was also the question of hyphenated first names. Until the mid 20th century, hyphenated names were both unstable and hard to identify, since a hyphen could sometimes be used to separate different names. The present study therefore treats both spaces and hyphens as name separators.

Diachronic analysis of paternal transmission.

We studied the rate of transmission of paternal first name (the 'transmission rate' for brevity) according to the date of birth. We first focused on the very beginning of the war, subdivided into 3 periods: diplomatic crisis of July 1914 ('July Crisis' starting with the assassination of Archduke Franz

Ferdinand on June 28); early mobilization (from the mobilization order on August 1 to first significant fightings on the third week of August); combat phase (late August and September). We then analyzed the whole war period. Excluding those for whom exact date of birth or father's name was missing, this analysis is based on N = 2,311,909 individuals.

Kin name transmission following kin death. For the N=1,421,152 individuals for whom father's date of death was known, we studied the association between paternal name transmission and age at father's death. We analyzed separately kin deaths in wartime and peacetime. While a child's birth can only occur at most 9 months after their father's death, the same is evidently not true for uncles, who may have died many years before the birth of a nephew or a niece. This enables the investigation of naming after deceased kin on a much longer time scale. One methodological difficulty is that if a child has exactly one father, he or she may have many uncles, and conversely an uncle many nieces and nephews, so that several definitions of the rate of transmission may be adopted. In the present work, we consider the proportion of uncle-nephew/niece dyads for which the first four letters of the two names match, and group the dyads according to the duration between the death of the uncle and the birth of the nephew/niece ('age at uncle's death' for short, even if avuncular death occurred prior to nephew/niece's conception). Here the dataset analysed is that of uncle -nephew/niece dyads where both uncle's and child's name are known (N = 6,055,890).

Results

Paternal transmission rate during WW1

Prewar trend. On the brink of WW1, about 12% of all baby boys and 4% of all baby girls were given the first name of their father (Figure 1 Heightened transmission of paternal first name as a measure of risk perception.

Having identified mobilization (and the subsequent separation of couples) in August 1914 as strongly associated with increased transmission, we wondered whether separation alone was its reason, or if this phenomenon was more specifically related to the risks taken by the soldiers who were mobilized. Consistent with the notion that the increase in name transmission was indeed correlated to the level of risk incurred by the father, we found that for infants born to men older than 35 (and therefore expected to be mobilized in less exposed, 'territorial', units), the increase is negligible (Figure 2).

Accordingly, the surge in transmission observed in August 1914 almost exclusively took place for babies born to young fathers (below 35).

If risk incurred by the father was actually the factor driving higher transmission, name transmission and paternal death during the War must be correlated, since by definition fathers who died were statistically more at risk. Among those born to young fathers, one can assess name transmission depending on whether the father died during the War (excluding the trivial case of a prenatal death of father -see below) or not. Indeed, the transmission rate was 11.0% (95% CI 10.8-11.2) for babies whose fathers died after the War, but 15.7% (95% CI 14.9-16.5) for those whose father died during the War.

Naming for dead kin in war and peace

Prenatal loss of father. Between 30 and 55% of all prenatal orphans (those still in the womb when the father died) received the first name of their father, irrespective of gestational age at father's death (Figure 3). Transmission rates were consistently, albeit moderately, higher for those whose father died during the War vs. in peacetime. At large, a loss of father during pregnancy leads in our sample to a 2.7-fold increase in the transmission rate, consistent with previous estimates. Due to a higher baseline value (transmission rate for a postnatal loss of father), the fold-increase is lower in wartime (e.g. in boys: 2.2) than in peacetime (boys: 2.8). The loss of a father during the first trimester of pregnancy further led to increased transmission, while a death occurring in the last month of pregnancy was associated with a more modest increase (2-fold increase). Competing hypotheses are that for these births, (1) the mother was still not aware of the death of her husband, (2) the parents had already agreed upon a baby name, (3) the need to symbolically link a baby to his or her father was less important when the pregnancy was already well-established at the time of the father's death.

Prenatal loss of uncle. In our sample, the transmission rate of avuncular name to nephew was about 5% at baseline, i.e. for uncles still alive at nephew's birth (Figure 4).

The transmission rate was distinctly higher in uncle-nephew/niece dyads in which the uncle died before the birth of his nephew/niece. Within the prenatal period, a marked difference was also visible between wartime and peacetime avuncular deaths. For deaths within the year preceding the birth, the rate of transmission to nephews was 14.0% (95% CI: 13.2-14.8) for a death in peacetime vs 16.0% (95% CI: 15.0-16.9) for a death in wartime. The response induced by a wartime death of uncle was also more lasting, so that the differences between wartime and peacetime avuncular deaths are still extremely notable ten years after the uncle's death.

Discussion

A simple behaviour, child naming, can yield considerable insight into the reactions to a historical event.

In order to investigate this behaviour at the population level, we relied on digitized genealogies, a data source that, due to the sample size and chronological coverage it offers, is becoming increasingly popular in fields such as population genetics and social

history. Yet it has several shortcomings. The distribution of producers is skewed, so that few users contribute a large number of records, possibly for religious reasons (as is the case with members of the Mormon Church). Amateur genealogists tend to focus on the prestigious branch(es) of their family. Lower class individuals are underrepresented because of common law marriages, unregistered birth, illegitimate birth, infant mortality, child abandonment and everyday resistance to policing. If it may be the case that the precise effect sizes we measure in our sample do not generalize to the population of all those born 1905-1925 in France, we have no reason to believe selectivity could explain our results, all based on large differences measured between groups within our dataset. 9

July 1914 retrospectively appears as the tragic month during which the European course reported the assassination of Archduke Franz Ferdinand and the diplomatic tensions that followed, the importance of this stream of events was essentially misunderstood and downplayed by the press for weeks. Unsurprisingly, no evidence for changes in paternal transmission rates could be found during this time period. The possibility of a war then brutally materialized during the last week of July. For instance, while the international crisis was still reported on page 3 only in the newspaper L'Humanité as late as July 24, on the next day a front-page article by Jean Jaurès, the head of the newspaper and a major socialist figure, made clear to all readers that war was most likely, with only a "suprême chance de Paix" left. Unions and the socialist party also organized demonstrations in large cities during this week. Yet we found no evidence for a change in naming behavior, suggesting French parents did not grasp the enormity of the threat. Only with mobilization did the naming pattern change. On the whole, the study of paternal name transmission in July 1914 is congruent with previous work: as stated by Becker, "when the church bells began to ring on 1 August and it became clear that this was not to warn of fire but to announce mobilisation for war, the first reaction was one of stunned shock and consternation".10

Our analysis then shows a quick change in behavior: during the first weeks of August, before the first deadly military engagements, paternal names suddenly became more popular than ever. This change was so brutal it was certainly not driven by imitation: it is extremely unlikely that mothers even realized a change in naming practices was under way. The change is quantitatively more important for children born to young fathers (the majority sent to fighting units) than for children of older fathers (mostly sent to nonfighting units). Risks taken by the father, rather than the separation of parents alone, seem to have boosted the father's name transmission. The fact that the rate of transmission did not change in late August -early September is puzzling, since one could have expected that mothers initially underestimated the risk of paternal death, then re-estimated a higher risk once the first casualty rates were known. This stable transmission suggests that parents correctly estimated a high risk of death from the very beginning of the war. Past experience of the 1870 Franco-Prussian War or knowledge on lethality of modern weapons gained from the Balkan wars may have been sufficient

to inform people's risk assessment. At odds with previous narratives, we conclude that even in its earliest phase, ordinary people did not underestimate the severity of the conflict.

Localized family de-structuration rather than large-scale social disruption seems to lie at the root of the change in behavior we observe. The war and the mobilization of young men away from their village might have changed the established social hierarchies. If responsible for the over-transmission we observe, this large-scale disruption of the social order should have affected each and every parents of babies born after July 1914. By contrast, we observe that after May 1915, the transmission rate fell back to its pre-war level even as the war continued. The general disruption of social order went on without influencing the parents. Furthermore, only a modest increase in paternal name transmission could be found for babies born to older fathers, mobilized in territorial units ("armée territoriale"). To the best of our knowledge, the most likely explanation for our results is that changes in naming behavior were located in families where the separation of parents entailed a heightened risk of death. This hypothesis could further be tested using microdata linking individual military experience and name transmission.

Turning to the subpopulation of children who lost their father or an uncle, we could systematically investigate differences in mourning practices in war and peace. Many studies have already been devoted to the unprecedented mass grief induced by the First World War. Its best-known aspects relate to the postwar period, namely the construction of war memorials in virtually every French town and village, and pilgrimages to military cemeteries. Documentation regarding intimate rituals, their frequency and their temporality, has been more scattered. Testimonies have reported photographs and medals played an important role in preserving a trace of the dead after the war. Case studies have frequently mentioned children who were given the name of a dead kin during the war, without being able to assess how widespread and how specific to WW1 this behaviour was.

We found that in early 20th century France, even in peacetime, the death of the father during pregnancy led to a high probability that his name would be given to his offspring.

The traumatic nature of the event was apparently sufficient to elicit a sharp increase in transmission. During WW1, paternal name transmission, already boosted in the general population of births by the risks soldiers leaving to the front incurred, was further stimulated for prenatal orphans. It is also likely that the practice took a new meaning, since the name given was not only that of the father, but also that of a patriotic hero.

Browsing the wartime Social Announcements section of the conservative, upper class oriented, newspaper Le Figaro, it is not infrequent to find birth announcements which specifically stressed that the father had 'gloriously died for France'.

The study of uncle to nephew/niece transmission enabled us to disentangle the effect of trauma from the cult of a fallen hero. The names of uncles who died during the War were significantly and lastingly more transmitted to nephews and nieces than those of uncles who died in peacetime: we show that, during the War and after the Armistice, first names were indeed massively used by the French population to maintain alive the memory of fallen soldiers.

To conclude, we found a weakening anthropological tradition, naming for kin, was brutally given renewed impetus in a matter of days in early August 1914 by families that were suddenly confronted to a horrendous prospect they could never have anticipated.

In families plunged into mourning, naming for kin additionally stressed the sacrifice that had been made by the dead soldier, and therefore happened to comply with the patriotic ideology of the time. Our study highlights there is no contradiction between anthropological stability and behavioral fluidity. A social theory of action should be able to take into account both the durability of habits and the fluidity of practice.

  , 853-877; Ólöf Garđarsdóttir, "Naming Practices and the Importance of Kinship Networks in Early Nineteenth-Century Iceland," The History of the Family, IV (1999), 297-314; Frans Van Poppel et al., "Naming for Kin and the Development of Modern Family Structures: An Analysis of a Rural Region in the Netherlands in the Nineteenth and Early Twentieth Centuries," The History of the Family, IV (1999), 261-295. For baby names as reactions to historical events, see; Michael Wolffsohn and Thomas Brechenmacher, "Nomen Est Omen: The Selection of First Names as an Indicator for Public Opinion in the Past," International Journal of Public Opinion Research, XIII (2001), 116-139; Elena Obukhova, Ezra W. Zuckerman, and Jiayin Zhang, "When Politics Froze Fashion: The Effect of the Cultural Revolution on Naming in Beijing," American Journal of Sociology, CXX (2014), 555-583; Martin Saavedra, Kenji or Kenneth? Pearl Harbor and Japanese-American Assimilation (Oberlin College, 2018); Robert Urbatsch, "The American Public's Attention to Politics in Conflict and Crisis, 1880-1963," The Journal of Interdisciplinary History, XLVI (2015), 225-244.

  1918)," Revue Internationale de Sociologie, XXVI (1918), 508-513; Édouard Lévy, Manuel Des Prénoms (Paris, 1922); for the analysis of paternal name transmission to orphans, see Nicolas Todd, Alain-Jacques Valleron, and Pierre Bougnères, "The Naming of Orphans in France During World War One: A Study of a Nationwide Cohort of Pupilles de La Nation," Historical Methods: A Journal of Quantitative and Interdisciplinary History, LI (2018), 82-91; for classic references on the cult of the fallen and mourning practices during the Great War, see George Lachmann Mosse, Fallen Soldiers : Reshaping the Memory of the World Wars (New York Oxford, 1990) ; Stéphane Audoin-Rouzeau and Annette Becker, 14-18, Retrouver La Guerre (Paris, 2003).

  it private. Geneanet granted us access to the 5.5 million open records of individuals

  7 R Core Team, R: A Language and Environment for Statistical Computing (Vienne (Autriche), 2019); Murat Sariyar and Andreas Borg, "The RecordLinkage Package: Detecting Errors in Data," The R Journal, II (2010), 61-67.

  , top panel, inset). Transmission to boys was declining, as parents increasingly turned to fashion. By contrast, until the beginning of the 1920s, transmission to girls was becoming more common, in part due to the general increase in popularity of male names' variants (e.g. Marcelle or Paulette) that enabled fathers' names to be transmitted as fashionable names. No period before 1914, including the 'Moroccan crises' of 1905 and 1911 when France and Germany threatened warfare, saw any disruption to these trends.July Crisis and early August 1914. We found no evidence for an increase in the transmission rate during the July Crisis. This stability echoes that which was observed during the Moroccan crises. Even for those born in the last week of July (Monday, July 27 to Sunday, August 2), no increase in the transmission rate was found. By contrast, a surge is visible in the first week of August (Monday, August 3 to Sunday, August 9), immediately following the mobilization order but before any actual fighting: 14.0% (95% Confidence Interval (CI): 11.9%-16.0%) of boys born during the last week of July were named after their father, and 17.7% (95% CI: 15.5%-19.9%) of boys born during the following week. A similar increase in transmission by about 50% was observed in female births (Figure1, lower panel).First combats and subsequent months. After the early August surge, the transmission rate remained stable until around May 1915, when it fell back to its prewar level. This phenomenon helps formulate hypotheses regarding both the mechanisms behind heightened transmission and the subpopulation involved. First, it suggests that it was not the large scale social disruption caused by the War that induced the phenomenon, since social disruption evidently did not vanish in May 1915 when large parts of France were still occupied, and combats were still ongoing. Second, the fact that the return to baseline was specifically centered on May 1915 suggests increased transmission mostly occurred in families where the father was mobilized. Children born after May 1915 were conceived after August 1914 -and hence predominantly by fathers who were not separated from their spouse when mobilization took place: the men available for conception after August 1914 were in their vast majority those free from military obligations. Of note, it has already been observed that for the same reason the monthly proportion of orphans in the total population of births plummeted in May 1915 in a fashion consistent with this 'mobilization effect.' 8

  governments made the decisions that led to the World War. Though newspapers of 9 For a recent use of crowdsourced genealogies in population genetics, see: Joanna Kaplanis et al., "Quantitative Analysis of Population-Scale Family Trees with Millions of Relatives," Science, CCCLX (2018), 171-175; in social history: Arthur Charpentier and Ewen Gallic, "Using Collaborative Genealogy Data to Study Migration: A Research Note," The History of the Family, XXV (2020), 1-21; Tine De Moor et al., "Long-Term Trends in Marriage Timing and the Impact of Migration, the Netherlands (1650-1899)," Historical Life Course Studies, VI (2017), 40-68; for resistance to state policy in relation to names: James C Scott, John Tehranian, and Jeremy Mathias, "The Production of Legal Identities Proper to States: The Case of the Permanent Family Surname," Comparative Studies in Society and History, XLIV (2002), 4-44; for an in-depth assessment of demographic characteristics of the Geneanet genealogies, see Arthur Charpentier and Ewen Gallic, "La Démographie Historique Peut-Elle Tirer Profit Des Données Collaboratives Des Sites de Généalogie ?" Population, LXXV (2020), NN-NN.

18 306Figure 1 :

 181 Figure 1: Weekly paternal name transmission rate ± standard error (s.e.). 307

Figure 2 :

 2 Figure 2: Monthly paternal name transmission (± s.e.), according to paternal age, May 1914 -

Figure 3 : 314 Figure 4 :

 33144 Figure 3: Paternal transmission rate (± s.e.), according to age at father's death. Prenatal ages

Table 1 :

 1 Illustration of the deduplication process. Four versions ('duplicates') of the same individual are identified, and contribute information to the merged version (bottom line) used in subsequent analyses.

	Family name	Names	Date of birth	Father's names	Father's date of birth
	Lafforgue	Robert Joseph	1905	Jules	1888-06-05
	Laforgue	Robert Joseph	1905-02-07		1888-05-06
	Laforgue	Robert	1905-07-02	Jules Philippe	1888-05-06
	Laforgue	Joseph Robert	1905-02-07	Jules Philippe
	Laforgue	Robert Joseph 1905-02-07	Jules Philippe	1888-05-06

For early work on first names during the War, see Édouard Lévy, "Les Prénoms de La Guerre(1914-

It is only in July 1915 that a leave system was organized by the French army, so that a few times a year soldiers could spend a few days at the rear. For a detailed analysis of the mechanism behind the May 1915 plunge, see Nicolas Todd, "Long-Term Health Effects of World War I Stresses" (Université Pierre-et-Marie-Curie thesis, 2017), 69-76.

Becker, "Willingly to War. Public Response to the Outbreak of War."

Data and methods

Genealogical data. Geneanet is a crowd-sourced genealogy website on which registered users can choose either to share their family tree ('open records') or to keep


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

Louis-Claude Canon

Redouane Elghazi

Pierre-Cyrille Héam

Shelf schedules for independent moldable tasks to minimize the energy consumption

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P ||Cmax problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One can then decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.

I. Introduction

We consider the problem of scheduling independent tasks. Even though this problem has already been widely studied, in particular when aiming to minimize the total execution time (or makespan) for sequential tasks, there remain avenues for improvement for variants of the problem. Using the Graham notations [START_REF] Graham | Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey[END_REF], the typical problem that is studied is P ||C max , i.e., the goal is to minimize the makespan when scheduling independent sequential tasks on a set of identical processors. The decision version of this problem in its simplest form is already NP-complete (it is indeed identical to 2-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF] when considering two processors). However, several well-known heuristics lead to very good approximation algorithms, as the classical Longest Processing Time (LPT) heuristic, or even some PTAS or FPTAS algorithms [START_REF] Hochbaum | A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach[END_REF].

The problem becomes more complicated when dealing with parallel tasks. Now, each task i is a parallel task that executes concurrently on p i processors. The greedy list scheduling algorithm that gives priority to longest jobs is then known to be a 2-approximation when tasks are rigid (p i is given and fixed) [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF].

In order to ease the scheduling, it can be useful to group tasks by shelves (or batches, packs, levels, etc.), and then the shelves are scheduled one after the other. Each task in a same shelf starts its execution at the same time, and the next shelf starts only when all tasks of the previous shelf are done. This is typically referred to as shelf-scheduling or co-scheduling. Of course, one may then waste time, due to idle resources if tasks do not all take the same time. However, such schedules are easy to implement and they also may have some theoretical guarantees. Indeed, the list scheduling that gives priority to longest jobs is known to be a 3-approximation when imposing to use shelves [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] (recall that it is a 2approximation without this restriction).

Such co-schedules are also very useful for moldable tasks, i.e., tasks whose degree of parallelism p i can be chosen at execution. For such parallel moldable tasks, an easy way to proceed is to execute tasks sequentially, each task using the whole platform. However, it may be more efficient to group tasks by shelves, since the execution profile of a task may lead to less efficiency when using many processors. While the general problem is NPhard, Aupy et al. [START_REF] Aupy | Co-scheduling algorithms for highthroughput workload execution[END_REF] propose an optimal polynomialtime algorithm to decide the processor assignment that minimizes the makespan when there are at most two tasks in a shelf.

While most scheduling problems are focusing on makespan minimization, another core problem is the energy consumption. In order to optimize this energy consumption, modern processors can run at different speeds, and their power consumption is then the sum of a static part (the cost for a processor to be turned on) and a dynamic part, which is a strictly convex function of the processor speed. Indeed, the execution of a given amount of work costs more power if a processor runs at a higher speed [START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a PC cluster[END_REF]. More precisely, a processor running at speed s dissipates s 3 watts [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF], [START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF], [START_REF] Chandrakasan | JouleTrack: A Web Based Tool for Software Energy Profiling[END_REF], [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF], [START_REF] Chen | Multiprocessor energyefficient scheduling for real-time tasks[END_REF] per time-unit, hence consumes s 3 × d joules when operated during d units of time. Faster speeds allow for a faster execution, but they also lead to a much higher (supralinear) power consumption. A more general model states that the power can be in s α , where 2 ≤ α ≤ 3 [START_REF] Bambagini | Energy-aware scheduling for real-time systems: A survey[END_REF]. While minimizing the makespan helps reducing the energy consumption, which increases with execution time, to the best of our knowledge, no study has been aiming at minimizing the energy consumption for shelf schedules.

For the static energy consumption, it depends on the time during which processors are powered. We consider two models: in the independent model, each processor is independently powered and can be turned off when not computing, hence the static power is paid only while processors are running. However, in the simultaneous model, the platform is turned on as long as one processor is running, hence the static power must be also paid for idle processors.

Our main contributions are the following:

• We formalize the problem of scheduling independent moldable tasks to minimize energy consumption (MinE-Mold problem), with various model variants.

• We prove that MinE-Mold-Indep can be solved in polynomial time when processors are independently powered (with or without co-schedules), while the problem becomes NP-complete with simultaneously powered processors (MinE-Mold-Sim).

• We establish multiple approximation ratios for both classical list scheduling algorithms, and shelf-based schedules.

• We provide an optimal dynamic programming algorithm to minimize the energy consumption of a single shelf: the goal is to decide on how many processors to execute each task of the shelf, and at which speed to operate the task.

• We perform an empirical study and we show that, for most instances, a single speed can be used for all tasks without increasing the energy consumption. Also, as expected, shelf-based solutions consume more energy, but they are easier to implement and solutions are derived with a much lower complexity.

We first discuss related work in Section II. Next, we detail the model (platform, tasks, energy consumption) and schedules, and we introduce the target optimization problems in Section III. The complexity of the problems is established in Section IV. Approximation ratios for MinE-Mold are derived in Section V, and optimal algorithms for a single shelf are provided in Section VI. Finally, a comprehensive empirical study is proposed in Section VII. We conclude and give hints for future research directions in Section VIII.

II. Related work

Although the problem of minimizing the energy consumption of parallel platforms has been extensively studied, few works propose guaranteed scheduling algorithms for moldable tasks. We first cover approximation algorithms for the problem of minimizing the makespan because our approach relies on such results. We then proceed on heuristics proposed for real-time systems.

Classical list scheduling algorithms, ListBased, constitute the simplest and first heuristic proposed for the rigid case. Tasks are ordered in a priority list and are then scheduled by order of priority, as presented by Garey and Graham [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF]: any time a processor is idle, the list is scanned in order and the first task that can be executed is started. Another way to say it, the principle of the algorithm is as follows: when resources are released, we see if a task can be started right now. If it is the case, we start it. If several tasks can be started, we take the one with the highest priority, given by an ordering of the tasks in a list. ListBased is a 2approximation for the makespan. More precisely, it is a 2•max( W p , t max )-approximation, where W p is the average work and t max is the execution time of the longest task.

Coffman et al. [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] made a landmark paper proving the approximation ratio of several shelf-based algorithms when considering rigid tasks only. They introduce the problem as a two-dimensional packing problem and focus on asymptotic performance bounds for the makespan. They show that the performance bounds of classic binpacking heuristics Next-Fit Decreasing and First-Fit Decreasing are 3 and 2.7, respectively.

In [START_REF] Krishnamurti | An approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems[END_REF], Krishnamurti et al. study a problem similar to ours: processors are partitioned and each task is submitted to one such partition with the objective to minimize the execution time. The number of partitions is bounded, which limits the maximum number of simultaneous tasks. Although it is similar when considering a single shelf, it differs from our problem with multiple shelves.

In [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], Turek et al. study the multi-shelves problem. They first offer an allocation strategy for rigid tasks, and then use this strategy on several "allocation candidates" for the moldable case. This first strategy involves coschedules, ShelfBased [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]LTF], where rigid tasks are partitioned into shelves, and all the tasks in a same shelf begin their execution at the same time (this is equivalent to Next-Fit Decreasing). Tasks are sorted in order of decreasing execution times. Then, tasks are inserted iteratively in the current shelf until the next task cannot be inserted. At this point, a new shelf is created and the process continues. A possible extension consists in allowing backfilling of previous shelves (which is done in Section VII). ShelfBased is a 3-approximation for the makespan. More precisely, it is a 2 • W p + t maxapproximation. To deal with moldable tasks, the authors also present an overall design [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF] that works as follows. First, a task and a number of processors are selected. We assume that for a given speed, all tasks will have a shorter execution time than this one. Next, for each other task, we select the number of processors such that the work is minimized. Finally, we solve this instance with rigid tasks and repeat the process for all pairs of tasks and number of processors.

The same year [START_REF] Turek | Scheduling parallelizable tasks: Putting it all on the shelf[END_REF], Turek et al. give a 2.7approximation for the multi-shelves problem, with a fixed number of shelves. However, this algorithm is exponential in the number of shelves.

Aupy et al. tackle the problem of optimizing the power consumption, the makespan and the reliability with dependent non-parallel tasks [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. They show that most problems are NP-hard and propose heuristics. This paper focuses on moldable tasks.

Finally, many similar works have been proposed in the context of real-time systems with moldable tasks, power constraints and deadlines. The closest considers level-based scheduling (similar to shelves) with rigid or moldable tasks [START_REF] Kong | Energy-efficient scheduling for parallel real-time tasks based on levelpacking[END_REF]. They propose heuristics that extend bin-packing ones such as First-Fit Decreasing, Best-Fit Decreasing, etc. Most other works related to realtime systems propose heuristics [START_REF] Xu | Energy minimizing for parallel real-time tasks based on level-packing[END_REF], [START_REF] Zahaf | Energy-efficient scheduling for moldable real-time tasks on heterogeneous computing platforms[END_REF], [START_REF] Litzinger | Scheduling moldable parallel streaming tasks on heterogeneous platforms with frequency scaling[END_REF]. In this paper, we do not consider deadlines and we investigate algorithms with guarantees.

III. Model

We first describe the platform model (Section III-A), the task model (Section III-B), the energy model (Section III-C), before formally defining general schedules, single-speed schedules and co-schedules in Section III-D. Finally, we introduce the target optimization problems in Section III-E.

A. Platform

The target platform consists in p identical processors, whose frequency can be scaled using DVFS (Dynamic Voltage and Frequency Scaling).

These processors have a static power P stat and a set S = {s 1 , s 2 , . . . , s k } of possible speeds (or frequencies). For convenience, we let s min = s 1 and s max = s k be the minimum and maximum speeds. Indeed, current processors have a set of predefined speeds (or frequencies), which correspond to different voltages that the processor can be subjected to [START_REF] Okuma | Software energy reduction techniques for variable-voltage processors[END_REF]. Switching frequencies is usually not allowed during the execution of a given task, but two different tasks scheduled on a same processor can be executed at different frequencies.

B. Tasks

We consider n moldable tasks {T 1 , T 2 , . . . , T n } with execution profiles (w i,j ) i∈ 1,n ,j∈ 1,p , where w i,j is the total work required to execute T i on j processors. The work is the total number of elementary operations to be executed by the processors. If executed at a speed of 1, the time per processor is then t i,j = wi,j j . We assume that:

• ∀i, (t i,j ) j is non-increasing in j (the more processors there are, the less time it will take per processor); • ∀i, (w i,j ) j is non-decreasing in j (when using more processors, there is more overhead due to the parallelization, which is a common assumption [START_REF] Blazewicz | Approximation algorithms for scheduling independent malleable tasks[END_REF], [START_REF] Benoit | Resilient coscheduling of malleable applications[END_REF]). Furthermore, for task

T i (1 ≤ i ≤ n),
• p i is the number of processors allocated to T i ; • s i is the speed of the processors during their execution of T i ;

• t i,pi,si = wi,p i si×pi is the execution time of the task; • a i,pi,si = wi,p i
si is the area of the rectangle representing the task.

C. Energy consumption

The energy consumption consists first of a static part, which corresponds to the power consumed when processors are turned on. The static power is denoted P stat , and the corresponding static energy is t stat P stat , where t stat is the duration during which the processor is powered.

There is also a dynamic energy consumption, directly related to the speed s at which the processor operates, and the time t dyn spent computing (which may be equal to or smaller than the time t stat ). The most general model states that the dynamic energy consumption is t dyn s α [START_REF] Bambagini | Energy-aware scheduling for real-time systems: A survey[END_REF]. Hence, for task T i , the dynamic energy consumption on each processor is t i,pi,si s α i (since t dyn = t i,pi,si ), and the total dynamic energy consumption for the task is a i,pi,si s α i (the same energy is consumed by each of the p i processors operating task T i ) with α > 1.

The case where t stat = t dyn is the independent model, where each processor is independently powered, and hence turned off when it is not computing. We also consider the simultaneous model, where the whole platform remains powered as long as at least one processor is executing.

D. Schedules

Given a computational platform and a set of moldable tasks as described above, a schedule λ is a function that maps each task T i to a tuple (M i , s i , δ i ), where M i is the set of processors assigned to T i (hence the number of processors assigned to the task is p i = |M i |), s i is the speed of these processors to execute T i , and δ i ≥ 0 is the starting time of T i . Moreover, λ must verify the following conditions:

• There exists i such that δ i = 0 (there is a task starting at time 0);

• If tasks T i and T i (1 ≤ i, i ≤ n and i = i ) are such that M i ∩ M i = 0, then [δ i , δ i + t i,pi,si ] ∩ [δ i , δ i + t i ,p i ,s i ] = ∅ (
a processor cannot be used for two different tasks at the same time).

We also have the following aggregated quantities depending on a schedule λ:

• C max (λ) = max i {δ i + t i,pi,si }, is the makespan (or total execution time); • W (λ) = n i=1 w i,pi is the cumulative work; • T dyn (λ) = n i=1 t i,pi,si is the cumulative execution time of all tasks; • A dyn (λ) = n i=1 a i,

pi,si is the cumulative execution time on all processors;

• A stat (λ) is the cumulative time on all processors during which they are powered. It is either A dyn (λ) in the independent model, or it is p×C max (λ) in the simultaneous model.

We can then express the total energy consumption of a schedule λ as:

E(λ) = n i=1 a i,pi,si × s α i + A stat (λ) × P stat .
If there is no ambiguity on λ, we write C max for C max (λ); and similarly for W , T dyn , A dyn , A stat and E.

Finally, we pay a particular attention to two classes of particular schedules:

• Single-speed schedules are schedules such that all the speeds are equal for all tasks, i.e., for 1 ≤ i ≤ n, s i = s ∈ S.

• Co-schedules are organized as shelves, as motivated in Section I. A co-schedule consists of a partition of the tasks into shelves and such that:

• if two tasks are in the same shelf, then they start their execution at the same time; • if two tasks are not in the same shelf, then one finishes its execution before the other one starts.

E. Optimization problems

The general problem is MinE-Mold: Given n moldable tasks and p processors, the goal is to find a schedule that minimizes the total energy consumption. The processors can either be considered to be simultaneously powered (Sim), or to be independently powered (Indep). Hence, MinE-Mold-Sim (resp. MinE-Mold-Indep) is the problem with simultaneously-powered (resp. independently-powered) processors.

We also consider the variant of the problem with rigid tasks, i.e., when the number of processors per task p i is fixed (MinE-Rig problem).

Finally, since we are interested in co-schedules, we consider the more constrained problem with a single shelf, i.e., all tasks must start at time 0 and be executed concurrently. The corresponding problem is MinE-OneShelf: Given a set of n tasks and p processors, the goal is to minimize the energy consumption knowing that all tasks start at time 0 (δ i = 0 for 1 ≤ i ≤ n). Solving this particular problem will help us derive efficient co-schedules for the general MinE-Mold problem. More precisely, a solution to MinE-OneShelf is an assignment ((p i ) i∈ 1,n , (s i ) i∈ 1,n ) such that:

• ∀i ∈ 1, n , task T i is executed on p i ≥ 1 processors at speed s i ∈ S;
• n i=1 p i ≤ p (at most p processors are used, since all tasks execute concurrently).

IV. Problem complexity We prove that MinE-Mold-Indep can be solved in polynomial time (Section IV-A), while MinE-Mold-Sim is NP-complete (Section IV-B).

A. Optimal algorithm for MinE-Mold-Indep

In the independent model, the total energy consumption is the sum of the individual energy consumption of each task. We can therefore optimize the energy consumption of each task independently, and execute the tasks one after the other. This is done by executing each task on a single processor, since (w i,j ) is non-decreasing in j, and hence a i,1,si ≤ a i,pi,si for all 1 ≤ p i ≤ p. Here, we focus solely on energy optimization, and the time to completion might be very large (a single processor is used).

There is a tradeoff between executing the task fast to reduce the static energy consumption of the task, and running at a slower speed to reduce the dynamic energy consumption. In fact, for each task T i , we choose the same speed s i ∈ S that minimizes s α-1 i + Pstat si , since the energy consumption of the task is t i,1,si (s α i + P stat ), and t i,1,si = wi,1 si . Finally, we obtain the optimal value of s i in Θ(|S|), by comparing the value for every possible s i ∈ S.

The optimal solution to this problem can therefore be found in polynomial time. In the rest of this paper, unless otherwise stated, we focus on simultaneously powered processors (A stat = p × C max ).

B. NP-completeness of MinE-Mold-Sim

When moving to the simultaneous model, it becomes crucial to also minimize the total execution time. We show that the MinE-Mold-Sim problem actually is NPcomplete, even when a single speed is available.

Theorem 1. The decision problem associated to MinE-Mold-Sim is NP-complete.

Proof: We first prove that the decision problem associated to MinE-Mold-Sim is in NP: a certificate is a schedule, i.e., the number of processors and the speed of each task, as well as the starting time of each task, and it is easy to check in polynomial time whether the bound on energy consumption is achieved.

To prove that MinE-Mold-Sim is NP-hard, we do the reduction from the problem of 3-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]: Given 3n integers {a 1 , . . . , a 3n } whose sum is nB = 3n i=1 a i and with B 4 < a i < B 2 for 1 ≤ i ≤ 3n, does there exist a partition of {1, . . . , 3n} into n subsets S 1 , . . . , S n , such that i∈Sj a i = B for 1 ≤ j ≤ n?

Let I 1 be an instance of 3-Partition. We create an instance I 2 of MinE-Mold-Sim with n processors, and 3n tasks that cannot be parallelized, i.e., their execution time is not improved when using more than one processor. Hence, task i (1 ≤ i ≤ 3n) is such that t i,j = a i for 1 ≤ j ≤ n. Furthermore, there is a single speed S = {1}, and we have P stat = 1 and α = 3.

Therefore, it is always better to execute each task on a single processor, hence leading to a dynamic energy consumption of a i for task i, and a total dynamic energy consumption of nB. The static energy consumption depends on the total execution time t, and it is t × n. Finally, we set the bound on energy consumption for I 2 to 2nB.

If I 1 has a solution, we execute tasks of a same subset S j onto processor j, for 1 ≤ j ≤ n. Each processor completes in time B, and the static energy consumption is nB, hence a total energy consumption of 2nB (static energy plus dynamic energy). Therefore, I 2 has a solution.

If I 2 has a solution, we define S j as the set of tasks executed on processor j. Since the energy consumption is not greater than 2nB, the total execution time is such that t ≤ B, and the sum of a i 's in each subset S j cannot exceed B. Therefore, I 1 has a solution, which concludes the proof.

V. Approximation ratios for MinE-Mold-Sim

To solve MinE-Mold-Sim, we extend a strategy [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF] that transforms a moldable instance into multiple rigid ones by fixing the number of processors (and possibly the speed) of each task. Then, each rigid instance is solved with a heuristic such as ListBased or ShelfBased. We thus start by considering the rigid case. Moreover, we first consider a simplified version of the problem where all tasks have the same speed in Section V-A, before moving to the general case in Section V-B.

A. Processors with a single speed (s i = s)

We first consider the case where the speed must be the same for all tasks, i.e., s i = s for 1 ≤ i ≤ n. The energy simplifies as:

E = s α n i=1 a i,pi,si + A stat × P stat , with α > 1.
1) Rigid case: We start with the rigid case, which means that, for 1 ≤ i ≤ n, the number of processors p i for task i is fixed. Hence, the workload for task i is also known (w i,pi ). Moreover, for a given schedule λ, all the s i 's are equal to s λ . The tuple λ(i) is hence denoted as (M i , s λ , δ i ).

Given any ρ > 0, we denote by ρλ the schedule associating to each task i the tuple (M i , ρs λ , δi ρ ), i.e., the speed is scaled by a factor ρ, and the starting times are adjusted accordingly, without any modification in the processor allocation. One can easily check that ρλ is also a rigid single-speed schedule.

Two schedules λ 1 and λ 2 are equivalent, denoted

λ 1 ∼ λ 2 , if there exists ρ > 0 such that λ 1 = ρλ 2 . The relation ∼ is an equivalence relation. The equivalence class of λ is denoted [λ]. Recall that C max (λ) = Astat(λ) p
is the makespan: it is the total duration during which the whole system is powered. For convenience, we define K [λ] = s λ ×pC max (λ). It is easy to see that this is a constant for the equivalence class of λ; indeed, given any ρ > 0, C max (ρλ) = Cmax(λ) ρ , and

s ρλ = ρ × s λ .
The goal of this section is to prove the following theorem. The idea consists in considering algorithms with a given approximation ratio on the makespan and show how these ratios extend to the energy minimization. Theorem 2. In the rigid single-speed context ( MinE-Rig-Sim with a single speed) and assuming that there exists an algorithm A that yields a c-approximation of the optimal makespan, then one can compute in polynomial time a schedule consuming at most c times the optimal energy. Proof: In the rigid case, we have

n i=1 a i,pi,si = n i=1 wi,p i si . Let us denote W = n i=1 w i,pi
, which is independent of the schedule λ. We can then write the energy as:

E(λ) = W s α-1 λ + A stat (λ) × P stat (1) = W s α-1 λ + C max (λ) × p × P stat . ( 2
)
The problem can be split as two decisions to take:

• the choice of speed s;

• the actual scheduling, i.e., the choice of the moment at which we start each task. We start with a preliminary lemma comparing the energy consumption of two schedules using the same speed: Lemma 1. Let λ 1 , λ 2 be two single-speed schedules such that s λ1 = s λ2 . If E(λ 1 ) ≤ E(λ 2 ), then for any ρ > 0, E(ρλ 1 ) ≤ E(ρλ 2 ).

Proof: Using Equation ( 2),

E(λ 2 ) -E(λ 1 ) = p × P stat × (C max (λ 2 ) -C max (λ 1 )).
Furthermore, C max (λ 1 ) = ρC max (ρλ 1 ) and C max (λ 2 ) = ρC max (ρλ 2 ). It follows that:

E(λ 2 ) -E(λ 1 ) = p × P stat × ρ(C max (ρλ 2 ) -C max (ρλ 1 )) = ρ(E(ρλ 2 ) -E(ρλ 1 )),
hence proving the lemma. Note that if λ * is a single-speed schedule minimizing the makespan (necessarily s λ * = s max ), then for any single-speed schedule λ with

s λ = s max , C max (λ * )s max ≤ C max (λ)s max . It follows that K [λ * ] ≤ K [λ] .
Let us denote by λ A the schedule returned by A.

Let s *

[λ A ] ∈ S be a speed for which min λ∈[λ A ] E(λ) is attained. Let λ opt be a single-speed schedule minimizing the energy. From Equation (2), we have:

E opt = W s α-1 λ opt + pC max (λ opt ) × P stat . By definition of λ * , E opt ≥ W s α-1 λ opt + pC max (λ * ) × P stat . Now, by optimality of s * [λ A ] and since K [λ A ] ≤ cK [λ * ] ≤ cK [λ opt ] and since c ≥ 1: min λ∈[λ A ] E(λ) = W (s * [λ A ] ) α-1 + K [λ A ] s * [λ A ] • P stat ≤ W (s λ opt ) α-1 + K [λ A ] s λ opt • P stat ≤ W (s λ opt ) α-1 + c K [λ * ] s λ opt • P stat ≤ W (s λ opt ) α-1 + c K [λ opt ] s λ opt • P stat ≤ cW (s λ opt ) α-1 + c K [λ opt ] s λ opt • P stat ≤ c • W s α-1 λ opt + c • C max (λ opt ) • p • P stat ≤ c • E opt ,
thus proving the theorem.

2) Moldable case: We present the overall design of the algorithm MinE-Mold-Sim:

• First, we select one task T i , a number of processors p i for this task, and we assume that for any given speed s, all tasks will have an execution time at most t max ∆ = t i ,p i ,s (t i,pi,s ≤ t i ,p i ,s = t max for 1 ≤ i ≤ n). There are np such assumptions to consider.

• For each value of (T i , p i ), we select the number of processors of each other task to be associated with the lowest work such that t i,pi ≤ t i ,p i still holds:

p i = arg min 1≤j≤p jt i,j such that t i,pi ≤ t max .
Intuitively, we analyze the approximation ratio of any moldable scheduling algorithm with the following approach based on [28, GF]:

• For a given t max , we bound the cumulative work to be executed assuming all task execution duration is bounded by t max . • We then bound the maximum makespan achievable with a heuristic for MinE-Rig-Sim. • Finally, we bound the maximum total energy consumption during this duration. We can state the main result of this section.

Theorem

3.

In the moldable single-speed context ( MinE-Mold-Sim), we assume that there exists a polynomial-time algorithm A for MinE-Rig-Sim that returns a schedule λ A such that Proof: The proof is done for

K [λ A ] ≤ a • W ([λ A ]) p + b • t max (λ A ) (resp. K [λ A ] ≤ max a • W ([λ A ]) p , b • t max (λ A ) ),
K [λ A ] ≤ a • W ([λ A ]) p + b • t max (λ A ) • s λ A .
The other case (max of the two terms instead of sum) is similar.

Let λ opt be a schedule minimizing the energy (for MinE-Mold-Sim with a single speed).

Let G =

w i,p p | 1 ≤ i ≤ n, 1 ≤ p ≤ p .
For any task i and any number k ≤ m of processors, we denote by λ i,k the schedule returned by A on the (rigid) instance: for all i , p i is the integer in {1, . . . , p} minimizing w i , under the constraint

w i ,p p ≤ w i,k
k . There are at most pn different λ i,k . Let λ • be a schedule minimizing the E(λ i,k ).

Denoting by i opt and p i opt respectively the task and the number of processors such that t max (λ opt ) = t i opt ,p i opt , one has by construction of the

λ i,k , W (λ i opt ,p i opt ) ≤ W (λ opt ). Set λ g opt = λ i opt ,p i opt .
Running λ i,k at a speed s i,k ∈ S that minimizes the energy, we have

E(λ•) ≤ E(λ g opt ) ≤ E( sopt s λ g opt λ g opt ) ≤ W (λ g opt ) α-1 + K [λ g opt ] sopt ≤ (W OP T ) α-1 + (a + b) • K [λ opt ] sopt ≤ (a + b) • (W OP T ) α-1 + (a + b) • K [λ opt ] sopt ≤ (a + b) • E(λ opt ),
which concludes the proof.

Recall that ListBased is an algorithm with a max and a = 2 and b = 2 [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF], hence it is a 2-approximation algorithm. ShelfBased, an algorithm with a sum and a = 2 and b = 1 [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]LTF], is thus a 3-approximation algorithm.

B. Processors with different speeds for each task

When generalizing to multiple speeds, the approach is close to the one used for the single-speed problem where all tasks are executed at the same speed. Theorem 4. In the moldable context ( MinE-Mold-Sim), we assume that there exists a polynomial-time algorithm A for MinE-Rig-Sim that returns a schedule

λ A such that C max (λ A ) ≤ a• A dyn (λ A ) p +b•t max (λ A ) (resp. C max (λ A ) ≤ max a • A dyn (λ A ) p , b • t max (λ A ) )
, where a and b are constants satisfying a ≥ 1. One can compute in polynomial time a schedule λ • such that:

E(λ • ) ≤ (a + b)E opt (resp. E(λ • ) ≤ max(a, b + 1)E opt ).
Proof: We consider in this proof the max case for A. The proof is similar for the sum.

Let

G = {t i,p ,s | 1 ≤ i ≤ n, 1 ≤ p ≤ p, s ∈ S}.
Note that G can be computed in polynomial time. For a schedule λ, set X i (λ) = s α i a k,pi,si + P stat a k,pi,si . For any i, p , s we consider the rigid instance defined by: p i , s i in order to minimize s α i a i ,p i ,s i +P stat a i ,p i ,s i under the constraint t i ,p i ,s i ≤ t i,p ,s . The schedule returned by A for this problem is denoted λ i,p ,s . There are a polynomial number of such schedules, and each one can be computed in polynomial time.

Let λ • be a scheduled among the λ i,p ,s minimizing the energy. Let λ opt be a schedule minimizing the energy for the main problem. Let also i opt , s i opt and p i opt satisfying t max (λ opt ) = t i opt ,p i opt ,s i opt .

By construction, one has:

i X i (λ i opt ,p i opt ,s i opt ) ≤ i X i (λ opt ). (3)
To simplify the notation, we denote λ i opt ,p i opt ,s i opt by λ g . Now,

E(λ•) ≤ E(λ i opt ,p i opt ,s i opt ) = E(λg) ≤ i X i (λg) + Pstat • p • Cmax(λg) E(λ•) ≤ i X i (λ opt ) + Pstat • p • Cmax(λg) ≤ i X i (λ opt ) + Pstat • p • max(a • A dyn p , b • tmax(λg)) ≤ max( i X i (λ opt ) + aPstatA dyn , i X i (λ opt ) + bpPstattmax(λg)) ≤ max(a i X i (λ opt ) + aPstatA dyn , E opt + bpPstatCmax(λ opt )) ≤ max(aE opt , (b + 1)E opt ) ≤ max(a, b + 1)E opt ,
which concludes the proof. In this case, the bound is 3 for both ListBased and ShelfBased algorithms.

VI. Optimizing for a single shelf

We propose to further optimize co-schedules by designing a polynomial-time algorithm for the MinE-OneShelf problem, i.e., to optimize the execution of a single shelf. Formally, given a set of n tasks and p processors, the goal is to find an assignment ((p i ), (s i )) 1≤i≤n that minimizes E = n i=1 p i t i,dyn s α i + p i t i,stat P stat , where • t i,dyn = t i,pi,si = ti,p i si , and • t i,stat = max 1≤i≤n t i,dyn (simultaneous model).

A. Preliminaries

Since the static energy spent depends on the total length of the shelf (max 1≤i≤n t i,pi,si ), the algorithm proceeds by fixing the shelf length to T , and aims at finding the optimal number of processors and speed for each task, such that the time bound T is respected and the total energy consumption is minimized.

Hence, for a single processor, given an amount of work w to complete and a length of shelf of T , we consider the function OptS(w, T ) that returns the optimal speed such that w s ≤ T and the energy consumption ws α-1 + T P stat is minimized. Since the energy consumption is an increasing function of s for s ≥ 0, the optimal speed is the smallest speed such that the shelf length is not exceeded. Therefore, OptS(w, T ) = min s ∈ S | s ≥ w T . In the case no such speed exists, the function returns None.

Note that this function can be computed in Θ(log(|S|)) by doing a binary search within values of S.

B. Optimal algorithm for MinE-OneShelf-Sim

The idea is to try every possible duration of the shelf: all possible durations are recorded in the set T , and then for a given duration T ∈ T , we compute the solution for each set of tasks T 1 , . . . , T i , i ∈ 1, n and each number of processors q ∈ 1, p .

Let e i,q be the minimum energy consumed by task T i on q processors, while not exceeding time T . It is computed by using the function OptS(t i,q , T ), since t i,q is the amount of work on one processor if task T i is executed on q processors.

We then proceed with a dynamic programming algorithm, to compute E i,q , the minimum energy consumption for the first i tasks, when using a total of q processors. The goal is to compute E n,p (using all tasks and all processors). E i,q is recursively defined for 1 ≤ i ≤ n and 1 ≤ q ≤ p as:

E i,q = min 1≤k≤q-i+1 E i-1,q-k + e i,k ,
with E 0,q = 0. If there are no tasks left, the energy consumption is null; otherwise we try all possible numbers of processors k for task i, while keeping at least one processor for each of the remaining tasks. We then take the best possible solution amongst the different possible durations in the set T , and Algorithm 1 provides the corresponding pseudo-code of this dynamic programming algorithm. Theorem 5. MinE-OneShelf-Sim can be solved optimally in polynomial time.

Proof: Let us prove by induction over i ∈ 0, n that for all q ∈ 1, p , E i,q is the minimum energy consumed to process the i first tasks with q processors.

Base case: ∀q ∈ 0, p , the energy consumed to handle no task on q processors is 0, meaning that the E 0,q values for q ∈ 0, p are correct.

Inductive step: Let i ∈ 0, n -1 , and we assume that ∀q ∈ 1, p , E i,q is correct. The expression of E i+1,q is min 1≤k≤q-i E i,q-k + e i+1,k . If task T i+1 is given k processors, then the i first tasks will be handled by q -k processors. As the task i + 1 must be given a number of processors k ∈ 1, q -i , the expression gives the correct value for E i+1,q .

It means that E n,p is correct, and therefore that the for q ← 1 to p do 10 s i,q ← OptS(t i,q , T ) ; 11 if s i,q = None then 12 e i,q ← ∞ ; 13 else 14 e i,q ← qt i,q s α-1 i,q + qT P stat ;

15 for q ← 0 to p do 16 E 0,q ← 0 ; algorithm is also correct.

17 for i ← 1 to n do 18 for q ← i to p do 19 for k ← 1 to q -i + 1 do 20 if E i-1,q-i + e i,k < E i,q then 21 E i,q ← E i-
The number of total durations is at most np|S|, because we must choose a task, the number of processors allocated for this task, and its speed. The complexity of the algorithm is thus O(n 2 p 3 |S|).

VII. Empirical Study

A. Experimental setup

All the base algorithms rely on the global mechanism presented in Section V-A2 [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF] with either a single speed or multiple speeds. It is then combined with the strategies presented in Section II: ListBased and ShelfBased (for a total of four heuristics). Moreover, we also implemented two optimization algorithms that can only be applied to an output of ShelfBased:

• OptiShelf, which optimizes each shelf once each task has been allocated to a shelf using the algorithm from Section VI (this may change the number of processors used for each task); • De-shelf, which takes a ShelfBased solution and starts each task as soon as possible by removing the shelf constraint while keeping the allocations and the order in which the tasks are started.

For both of these optimizations, the energy consumption cannot be worse after the optimization than before. When both optimizations are selected, OptiShelf would be performed first but we discarded this combination because it did not outperform De-shelf in practice. This represents a total of ten heuristics.

To compare the different heuristics, we implemented them in C++17 compiled with gcc 9.3.0 with optimization option -O3.

We rely on Python 3.8.5 to generate the instances and to analyze the results. The code of these experiments can be found on Figshare 1 .

B. Instance generation

The following characteristics were extracted from a realistic platform [START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF], [START_REF] Benoit | A different re-execution speed can help[END_REF]: p = 32 Intel Xscale with P stat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}. The number of tasks varies from 20 to 1000, with a step every 20 tasks. The workload was generated as follows:

• half of the task profiles are generated with Amdahl's law

[1] [26] (w i,pi = w i,1 • β + wi,1•(1-β) pi
, where w i,1 and β are chosen through uniform distribution U (0, 1));

C. Results

In order to evaluate the performance of the various heuristics and show whether they return results close to the optimal, we compare the results with a lower bound that consists in an optimal execution in the MinE-Mold-Indep case (Section IV-A). In that case, the static energy is paid only while a task is executed, and any solution to MinE-Mold-Sim will consume at least as much energy as this lower bound.

Figure 1 presents an overview of the results for all heuristics, for the case with n = 500 tasks. We report both the ratio between the energy consumption of each heuristic with the lower bound (the lower the better), and also the execution time of the heuristics. For convenience, SS refers to the single-speed variants, and MS to the multiple-speed ones. A first remark is 1 https://doi.org/10.6084/m9.figshare.14854395 that single-speed and multiple-speed variants give very similar results. Indeed, in practice, the multiple-speed heuristics give the same speed to most tasks.

In Figure 2, we compare the most efficient heuristic, ListBased-MS, with the fastest one, ShelfBased-SS. We can see that ListBased-MS provides schedules with lower energy than ShelfBased-SS, but at the cost of a much larger execution time for the algorithm2 .

In Figure 3, we use the solution delivered by Shelf-Based with a single speed for all tasks, and pass this solution through two possible optimizations: OptiShelf or De-shelf. With this comparison, we can see that both optimizations increase the quality of the solution, but OptiShelf does it at the cost of a very large increase in the execution time. On the other hand, the overhead of De-shelf is small, allowing to get a solution of better quality at a small cost. Finally, in Figure 4, we compare ListBased with multiple speeds to ShelfBased with a single speed, with De-shelf, which we found to be the best optimization for ShelfBased. For small instances, ListBased still performs better than ShelfBased with De-shelf. However, when n grows larger, ShelfBased with Deshelf performs as well as ListBased, but with a lower time complexity.

VIII. Conclusion

With the growing concern regarding the energy consumption of current parallel platforms, it is crucial to bound the worst-case performance. This paper is the first to propose such bound on the energy consumption when scheduling moldable tasks. We highlight the relation between the energy and the completion time (determined by the DVFS mechanism) and rely on the numerous approximation algorithms, which have already been proposed to minimize the completion time. This leads to a general mechanism to bound the energy consumption of such existing approximation algorithms for the completion time. In particular, we show that a shelf-based approach is a 3-approximation algorithm for the energy. Empirical results reveal that such an approach, when combined with a fast optimization postoperation, is beneficial in practice because of its low cost. This paper also contributes to the optimization of a single shelf by providing a polynomial algorithm.

To complete this study, we could consider variations of the power model. In particular, we assume that changing frequencies with the DVFS mechanism does not incur any energy cost or delay, which may not be accurate in practice. Also, we assume that the set of available frequencies is finite and discard continuous frequencies even though they may provide insights or lead to optimal solutions, which may then be used as a basis for the finite case.

Overall, this paper aims at providing the theoretical foundations to the problem. Since current task systems do not yet have moldable task profiles that can be used, we have focused on classical models that have already been largely considered in the literature. As soon as moldable task profiles are available, it would be very interesting to conduct experiments on real HPC systems.

  where a and b are constants satisfying a + b ≥ 1. One can compute in polynomial time a schedule λ • such that λ • running at a speed that minimizes the energy consumption consumes at most a + b (resp. max(a, b)) times the optimal energy.

Algorithm 1 :for i ← 1 to n do 3 for q ← 1 to p do 4 for s ∈ S do 5 T

 1345 Optimal algorithm forMinE-OneShelf-Sim 1 T ← ∅ ; 2 ← T ∪ { ti,q s } ; 6 res ← ∞ ; 7 for T ∈ T do 8 for i ← 1 to n do

9

 9

  • half of the task profiles are generated with the Power law[START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF] [15][START_REF] Sun | Scheduling parallel tasks under multiple resources: List scheduling vs. pack scheduling[END_REF] (w i,pi = wi,1 p β i where w i,1 and β are chosen through uniform distribution U (0, 1)).

Figure 1 .Figure 2 .

 12 Figure 1. Output energy consumption and execution time to compute the solution for all ten heuristics with n = 500 mixed power and tasks and p = 32 processors (with Pstat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}).

Figure 3 .

 3 Figure 3. Output energy consumption and execution time to compute the solution for ShelfBased-SS and optimizations (OptiShelf and De-shelf) for instances with mixed power and Amdahl's tasks and p = 32 processors (with Pstat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}).

Figure 4 .

 4 Figure 4. Output energy consumption and execution time to compute the solution for ListBased-MS and De-shelf-SS for instances with mixed power and Amdahl's tasks and p = 32 processors (with Pstat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}).

ListBased could be implemented in a faster way with a segment tree to compute which task can be started, making this operation log n instead of n. However, this complex data structure would probably not be included in most implementations.

This work has been supported by the EIPHI Graduate School (contract ANR-17-EURE-0002).