Sarina Kawahara

Yoshie Niijima
email: yoshieniijima@gmail.com

Alexandra Mendreke-Laske

Reina Tanase

Yuichi Hosoya
email: hosoya@law.keio.ac.jp

Yuko Kasuya
email: ykasuya@law.keio.ac.jp

Takeharu Okubo
email: tokubo@law.keio.ac.jp

Yoshikazu Shiobara
email: shiobara@law.keio.ac.jp

Christophe Bouillaud
email: christophe.bouillaud@sciencespo-grenoble.fr

Philippe Droz

Olivier Ihl
email: olivier.ihl@sciencespo-grenoble.fr

Keywords: modali8es, performance, resilience

Liberal Democracy

• Are we witnessing the decline of liberal democracy and the emergence of alterna've forms of democracy? • In recent years, it has become increasingly commonplace to cri8cize democracy of the liberal kind that historically emerged in modern Western Europe but eventually spread to the rest of the world by the end of the 20 th century Democracy, an unfinished journey

• John Dunn: Democracy, the unfinished journey, may always be improved and spread • From Stealth democracy (let the elites decide, and rec8fy at the margins) to democracy made manifest by democrats (an increased democra8c offer for an alleged increasing demand for democra8c prac8ces) • A "par8cipatory turn"? A new interna8onal norm? A new democra8c spirit?

• « many ci'zens are a7ached to a delegate model of representa'on more than a fully par'cipatory view of democracy, and they see direct democracy not as a method to govern by but as a mean to be7er instruct their representa'ves (Bowler, Donovan, Karp, 2007, p. 359) • Same with « interna8onal democracy »?

(controlling IGOs and States' interven8ons)

Stealth or direct democracy?

• « we agree that many people would seXle for Stealth democracy given a restricted range of choices. However (...) it is not what they ul8mately prefer if they believe that effec8ve republican consulta8on might be available » • « people do not really hold Stealth democracy as their first preference. Instead, they will seXle for Stealth democracy if the civics textbook version of delibera8ve representa8ve democracy is not achievable » • Neblo et al., 2009, p. 11 & 24 A New Demand for Democracy?

• « Younger people, racial minori'es, and lower income people are significantly more willing to deliberate, all of which are reversals from tradi'onal par'cipa'on pa7erns. • Similarly, women, less par'san people, and non-church goers are slightly more likely to want to deliberate, though not to a sta's'cally significant degree. • On these criteria, it would appear that the kinds of people a7racted to delibera'on are fairly dis'nct from those drawn to par'san poli'cs and interest group liberalism, • consistent with delibera've democracy's claim to provide an outlet for those frustrated with status quo poli'cs » (Neblo et al., 2009, p. 17).

• Today, democracy is first and foremost a language of poli8cal legi8macy. And more osen than not, it serves as a language of self-jus8fica8on, even self-praise. • Emerging countries like China, Russia, Indonesia, Nigeria, and even the Arab Emirates, while considerably less democra8c by liberal standards, have become more and more vocal in stressing their own versions of democracy, thus posing some challenges to the liberal view Doubts about the meaning, the outreach and the universality of democracy

Deepening Democracy

• Debates about the "quality of democracy" (vs.

"malfunc8oning democracy"), "democra8c responsiveness", "accountability" and "transparency" • as well as "par8cipatory" or "delibera8ve" democracy. There is even a new quest for "cosmopolitan" democracy.

Enhancing democracy

• Post-colonialist outlook: forms of regimes should match the diversity of poli8cal cultures • Promo8on of allegedly "specific" concep8ons of democracy that rely on "Asian", "Muslim", "African", "Hindu" or even La8n America's "indigenous/Indian" values Two opposing strands of democra8c thought

• One more liberal, egalitarian and procedural, grounded on cons8tu8onalism and ins8tu8onal designs • another more hierarchical, substan'al and group-oriented, with a greater stress on social rights and cultural iden8ty • e.g. the debate between John Rawls and Amartya Sen, the respec8ve promoters of Athenian and Mesopotamian concep8ons of jus8ce

A democracy that existed "before" the others?

• supporters of each form claim that it embodies "true" democracy • Each found its own journey towards a balanced and legi8mate poli8cal system • Memory of a reconstructed if not imagined past is accordingly mobilized to probe such claims. • Great efforts are made to show that ideas and ins8tu8ons that may each, separately, be considered as being at the core of democracy were invented here and not elsewhere.

Democracy or democra8c ins8tu8ons ?

• A great variety of structures, prac8ces and ideas assumed to be mutually compa8ble • But a common goal-the quest for a "civiliza'on" of social and interna'onal rela8ons, albeit with their own trajectory towards achieving this aim Democracy in the West and what in the Rest ?

• Democracy = a cons8tu8on + a Bill of rights rule of law (and not only ruling by law: laws should be equally applying to all) pluralism (since it was brought by coali'ons) inclusive poli8cal and economical ins8tu8ons

• The democra8c game is made of alternance guarantees for the minori8es (the opposi8on; social minori8es)

What else?

• Illiberal or imperfect democracy • Oligarchy = monopolies, slavery or cheap labor, clientelism, use of force

• Autocracy = authoritarianism = « democratorship », dictatorship
The course

Contents and schedule List of references

• Explores these various paths towards a more democra8c world • With cases chosen from diverse regions of the world, at different periods in 8me -A resounding no… We are witnessing the enduring dialec8c of democra8c advances and autocra8c resilience (though revamped authoritarianism, not in the "old sense" "à la Juan Linz", cf. debates about Lucan Way and Steven Levitsky, Andreas Schedler) and a dialec8c that takes place in an interna8onal society (in the sense of the English school of IR) -We will try a give a concrete sense to this dialec8c by dealing with two areas in compara8ve ways, Asia and the Middle East… there is no need to say that these two areas are of crucial importance for the fate of world poli8cs (cf. China/US rivalry) and hence for the future of democracy and poli8cs.

Session 2: Part 1, Yuichi Hosoya

• Part 1 /(20mn Y H) +discussion Is Democracy Necessary for an Interna8onal Society?

-Aser the end of the Cold War, "democracy" has become one of the most important norms for interna8onal society. -Anthony Lake, Na8onal Security Advisor for U.S. President Bill Clinton, and President Clinton himself, began to talk that the enlargement of democracy could spread peace in the world. Can democracy really bring peace in interna8onal society?

• Text to read for discussion:

-Mark Beeson, "Democracy, development and authoritarianism", in Mark Beeson and Richard Stubbs (eds.), Routledge Handbook of Asian Regionalism, Routledge, 2012, pp. 236-247.

-------BREAK 10 mn---------Session 2: Part 2, Yuichi Hosoya

• Part 2/ (20mn Y H) +discussion Democracy in East Asia:

-Japan:

• under Prime Minister Shizo Abe Japan is now trying to establish a new order in the Asia-Pacific It will be based on liberal norms such as democracy, freedom, the rule of law, and human rights.

-Two ques8ons emerge

• Will China be antagonis8c and eventually deny interna8onal order based on democracy? • Will the liberal order stabilize East Asia or destroy the stability in this region?

• • 8:50-9:40 / 16:50-17:40 Discussion (2 presenta8ons from both Grenoble and Keio sides for about 7-10 minutes, followed by a general debate)

• Texts to read for discussion:

-Barbara A. Misztal ( 2005) "Memory and Democracy," American Behavioral Scien 'st, 48-10: 1320-1338. -Duncan Bell (2006) "Introduc8on: Memory, Trauma and World Poli8cs," in Duncan Bell, ed., Memory, Trauma, and World Poli'cs: Reflec'ons on the Rela'onship Between Past and Present. Palgrave Macmillan: 1-29 + 231-240 (fn).

• 17:40-18:00 Break Session 3: Olivir Ihl's Class design

• 18:00-18:25 General descrip8on of the issue "Vo8ng Systems, Memory, and Democracy Building" by Prof. Ihl

-Several issues will be discussed :

-Why should we remember? -Is History the enemy of Memory in Democracy ? -Can we talk of na8onal style of commemora8on? -Is there a specifically European form of commemora8on?

• 18:25-19:15 Discussion

• 19:15-19:30 Conclusion (Profs. Ihl and Yamamoto)

• Texts to read for discussion:

-Cruz, C. (2000). Iden8ty and persuasion: How na8ons remember their pasts and make their futures. World Poli 'cs, 52 (3), pp. 275-312. -Judt, T. (1992, Fall) -In the class, we will discuss on the following two ques8ons: 1) Will China's authoritarian regime be sustained into the future? 2) What is the desirable democracy for Chinese people? -First, the lecturer will introduce principal arguments on these ques8ons (45-50min). Aserwards, we will have free discussions.

• Texts: The following books will be useful to join the discussion. • Grenoble: Raul Magni-Berton: "Checks and balances in modern democracies" -(Prof. Magni-Berton specializes in the quality of democracy, liberal thought, and ra8onal choice approaches)

Session 5: Yuko Kasuya

• Class design:

-Research ques8on: focuses on the concept of accountability and have students apply this concept/framework to analyze problems facing French and Japanese poli8cs (or any other regions/countries of their interest). -Two 90 min. sessions, each professor lectures and does a Q & A session for the first 30 minutes, then students do group presenta8ons (or present individually, depending on the number of students).

• Text:

assigned background reading: Yuko Kasuya and Yuriko Takahashi, « Streamlining Accountability: Concepts, Subtypes, and Empirical Analys », January 20, 2013 -hXp://papers.ssrn.com/sol3/papers.cfm?abstract_id=2493654

• In the beginning of the session I will make a short lecture to overview policies and the social contexts on foreign workers/immigrants in contemporary Japan, and examine the discourse of Tabunka kyosei, the Japanese version of official mul8culturalism. • In the end of the lecture I will raise ques8ons to Japanese and French students; in terms of liberal democracy what kinds of mul8culturalism as norma8ve principle are possible in contemporary Japanese society, and what kinds of poli8cal and social condi8ons are necessary to make the principle happen in reality. Aser the lecture we will discuss the ques8ons based on the informa8on from the lecture and journal ar8cles I will deliver the students in advance which they are required to read before aXending the class. • In the first part of the session I will make a short lecture to overview four main dimensions of poli8cal cultures:

-Poli8ciza8on -Poli8cal par8cipa8on -Poli8cal orienta8on -Democra8c values.

• For each of these four dimensions, two ques8ons will be raised:

-What changed along 8me, in the last decades, in poli8cal cultures? -What differences exist between European countries (between the North and the South of Europe, or West and East)?

•

  Part 3/ (20mn, Ph D-V): The breach of authoritarian rule in the Arab World in 2011, what kind of transi8ons? • + (20mn) discussion • Texts to read for discussion: -T. Carothers "The end of the transi8on paradigm", Journal of Democracy, January 2002 -Philippe Droz-Vincent, in F Gerges, ed, The New Middle East, Part 4/ (20mn): The role of the security sector in transi8ons and authoritarian resilience, and the risks of transi8ons, the Syrian case • Texts to read for discussion: -S Lipset, "The Social Requisites of Democracy Revisited", American Sociological Review, February 1994 -Philippe Droz-Vincent, "Prospects for Democra8c Control of the Armed Forces", Armed Forces and Society, October 2014 -Philippe Droz-Vincent, "State of Barbary (Take Two)", The Middle East Journal, Winter 2013-2014

remarks by the Dean and Vice-Dean of

	Session 2: Interna)onal Democracy
	Friday 17 October 16:30-19:30 (JST) / 09:30-12:30 Session 2: Class Design
	• Introduc8on (5mn Ph D-V):	(France)
	• Research Ques8on: Are we witnessing global trends towards • Keio: Yuichi Hosoya "Democracies in democra8za8on, a fourth wave and the end of history once again? (cf. Interna8onal Society" John Mueller on Fukuyama)
	-(Prof. Hosoya specializes in interna8onal rela8ons, Keio Law Faculty European and Japanese diploma8c history)
	• Grenoble coordinator's presenta8on: Yves • Grenoble: Philippe Droz-Vincent "Autocracies in Schemeil Interna8onal Society, post-2011 Revolu8onary
	Situa8ons in the Arab Word, and the Military" • Keio coordinator's discussion: Ken -(Prof. Droz-Vincent specializes in Middle Eastern Tsutsumibayashi • Professors' comments Studies and Interna8onal security)
	• General discussion with students

• Which makes it fully compara8ve in the selec8on of cases and the use of a variety of approaches Session 1: Introduc)on Friday, October 3, 16:30-19:30 (JST) / 09:30-12:30 (France)

• Introduc)on / Plenary session • Welcome

  . The Past is Another Country: Myth and Memory in Postwar Europe. Daedalus, (121), pp. 83-118.

	Session 4: Emerging and Consolida)ng
	Democracies Session 4: Kazuko Kojima's Class Design
	Friday, November 14, 16:30-19:30 (JST) / 08:30-11:30 (France)
	• Keio: Kazuko Kojima "'Democracy in China"
	-(Prof. Kojima specializes in modern and
	contemporary Chinese poli8cs)
	• Grenoble: Christophe Bouillaud "Democracy
	in France and Italy"
	-(Prof. Bouillaud specialized in Italian Poli8cs and
	the history of poli8cal thought)

• Class Design:

  The following texts will be useful to join the discussion.

	Session 5: The Quality of Democracy Session 4: Christophe Bouillaud's Class Design Friday, November 28, 16:30-19:30 (JST) / 08:30-11:30 (France)
	• "What's next? Which future(s) for radical(ized) protest(s) in old democracies? -The growing impact of informed and subtle • Keio: Yuko Kasuya "Democracy and the repression on protest movements. -The case of Italian "M5S" (2009-2014), a new radical and non-violent 'an8-par8es' Variety of Accountability Mechanisms"
	1) Andrew J. Nathan, Larry Diamond, and Marc F. PlaXner eds., Will China Cricket. Beppe Grillo Shakes Italian Poli8cs, South European 3) 张明树《中国⼈人想要什什么样⺠民主》社会科学⽂文献出版社 2013. • Fabio Bordignon & Luigi Ceccarini (2013) Five Stars and a Princeton University Press, 2000. 10.3917/rfspe.616.0001 2) Daniel A. Bell, East Meets West: Human Rights and Democracy in East Asia, de science poli'que (English), 2011/6 Vol. 61, p. 1-24. DOI : Democra'ze?, The John Hopkins University Press, 2013. party. " -(Prof. Kasuya specializes in compara8ve poli8cs, compara8ve government, South East Asian • Texts: • Combes Hélène et Fillieule Olivier, « Repression and Protest Structural Models and Strategic Interac8ons », Revue française poli8cs)
	Society and Poli'cs, 18:4, 427-449, DOI
	10.1080/13608746.2013.775720

•

  This lecture will be based on the data of the European Values Studies, displayed and analyzed in: -Bréchon Pierre, Gonthier Frédéric (eds.), Atlas des Européens, Armand Colin, 2013. -Bréchon (Pierre), Gonthier Frédéric (eds.), Les valeurs des Européens, Evolu'ons et clivages, Armand Colin, 2014. • Aser the lecture in the second part of the session, we shall discuss the lecture, a student presenta8on, and the required readings. • Ar8cles to be read in advance: -Halman Loek, Sieben Inge, van Zundert Marga, Atlas of European Values. Trends and Tradi'ons at the turn of the Century, Leiden: Brill, pp. 76-84. -Norris Pippa, Democra'c Deficit: Cri'cal Ci'zens revisited, Cambridge University Press, 2011, pp. 3-11, Introduc8on and chapter 12, Conclusions and implica8ons, 12 pages.

• Research Ques8on: The consequences of different paXerns of separa8on of powers -The study of differences between regimes in which presidents are popularly elected (like France) and regimes in which they are not (like Japan)

• Text:

-Raul Magni-Berton, « Reassessing Duvergerian semi-presiden8alism: An electoral perspec8ve • Keio's sec8on (90 minutes) facilitated by Yoshikazu Shiobara: Mul8culturalism and democracy -In the beginning of the session I will make a short lecture to overview policies and the social contexts on foreign workers/immigrants in contemporary Japan, and examine the discourse of Tabunka kyosei, the Japanese version of official mul8culturalism. In the end of the lecture I will raise ques8ons to Japanese and French students; in terms of liberal democracy what kinds of mul8culturalism as norma8ve principle are possible in contemporary Japanese society, and what kinds of poli8cal and social condi8ons are necessary to make the principle happen in reality. Aser the lecture we will discuss the ques8ons based on the informa8on from the lecture and journal ar8cles I will deliver the students in advance which they are required to read before aXending the class.

• Timetable:

-Introduc8on and short lecture (45 minutes) -Discussion (45 minutes)

• Ar8cles to be read in advance:

-Kashiwazaki, Chikako, 2013, "Incorpora8ng immigrants as foreigners: mul8cultural policies in Japan," Ci'zenship Studies 17 (1): 31-47. -Nakamatsu, Tomoko, 2014, "Under the Mul8cultural Flag: Japan's Ambiguous Mul8cultural Framework and its Local Evalua8ons and Prac8ces," Journal of Ethnic and Migra'on Studies 40(1): 137-154.

Reference List

General References


Global democracy

Keywords: insCtuCons., Session 7: Progress towards more democracy, accountability, and transparency

Session 5: Revisionism: non-state actors and new claims for a more

AT THE LOCAL/NATIONAL LEVEL

Democracy

Global democracy

• Global (?) + Democracy (?)

• Demos (one people) + kratos (power + authority) • "Government of the people, by the people, for the people"

• The people is homogeneous (ethnically, linguisCcally, or commiYed to the same values) • The people is sovereign (it makes laws; it appoint bureaucrats and rulers)

Government by the people The democraVzaVon of IOs The globalizaVon of benefits and costs

• Global public goods, the ulCmate goal (instead of the vague "public interest") • Can be provisioned only beyond each single state, interstate cooperaCon is required • This implies interorganizaConal cooperaCon: each organized stakeholder parCcipates in a sort of "checks and balances" system, a mutual control

Our topic

• This implies interorganizaConal cooperaCon: each organized stakeholder parCcipates in a sort of "checks and balances" system, a mutual control • Therefore we shall address here:

Our topic

• The democraCzaCon of decision-making processes / • within internaConal organizaCons / • to deliver global public goods / • and exercise a mutual control over their respecCve outcomes

Our topic

• The democraCzaCon of decision-making processes within internaConal organizaCons to deliver global public goods and exercise a mutual control over their respecCve outcomes

Government for the people

	• Ancient Greece, Swiss cantons : parCcipatory • US: government by the elites, above the
	democracy, every ciCzen votes (within limits: ordinary people (educated, enlightened, indigenous men only) wealthy) • Modern revoluCons (UK, US, F): representaCve democracy (to some extent: • Dedicated to
	government of the "natural" aristocracy) since
	"the people's self rule is non feasible"

the promoVon of the public interest AT THE GLOBAL/INTERNATIONAL LEVEL DemocraVzaVon More challenging

• DemocraCc deficit, lack of democraCc responsiveness: even more dramaCc! • Greater heterogeneity, bigger numbers: no "demos" • No "individuals"? (at least, not everywhere) • No world parliament, no world government, no world supreme court No

World Parliament The UN General Assembly The Glarus Canton Assembly (CH) The UN: regionalized, one state one vote

	SoluVon: DemocraVzaVon by proxies InternaVonal stakeholders
	• DomesCcally, "all individuals significantly • DemocraCzaCon, a process (rather than • IGOs, Banks, Funds, Programs)
	affected by a decision-making process should "democracy", which is the outcome of this • NGOs, "advocacy" groups
	African Group Asia-Pacific Group Eastern European Group have an equal say in how that power is exercised" process) • Business lobbies and unions, FoundaCons, • DemocraCzaCon by Proxies: InternaConal think tanks, epistemic communiCes, etc. • Globally, individual internaConal organizaCons stakeholders rather than the people • They do not make law, but impose standards that contribute to rule making and promote new norms (e.g. ISO, ICANN)

Group of LaCn American and Caribbean States (GRULAC) Western European and Others Group (WEOG) No group

Problem: What is the "demos"?

• Interview with an ICANN / Gac representaCve: hYps://www.icann.org/news/mulCmedia/


Guillaume Aupy

Emmanuel Jeannot

Nicolas Vidal

Scheduling periodic I/O access with bi-colored chains: models and algorithms

Keywords: High performance computing, complexity, algorithmics, approximations Calcul Haute performance, ordonnancement, complexité, algorithmique, approximations

Observations show that some HPC applications periodically alternate between (i) operations (computations, local data-accesses) executed on the compute nodes, and (ii) I/O transfers of data and this behavior can be predicted before-hand. While the compute nodes are allocated separately to each application, the storage is shared and thus I/O access can be a bottleneck leading to contention. To tackle this issue, we design new static I/O scheduling algorithms that prescribe when each application can access the storage. To design a static algorithm, we emphasize on the periodic behavior of most applications. Scheduling the I/O volume of the different applications is repeated over time. This is critical since often the number of application runs is very high. In the following report, we develop a formal background for I/O scheduling. First, we define a model, bi-colored chain scheduling, then we go through related results existing in the literature and explore the complexity of this problem variants. Finally, to match the HPC context, we perform experiments based on use-cases matching highly parallel applications or distributed learning framework

Introduction

Until now, the performance of a supercomputer was mainly measured by its computational power. However, as platforms grow larger and the amount of data involved increases, we encounter new issues. Indeed, the way data is allocated, moved or stored takes an increasing part in the performance of these parallel applications. For instance, on large-scale platform, I/O movement is critical as fetching data out of the storage is becoming a growing fraction of the total runtime. Moreover, while the compute nodes are allocated separately to each application, the storage is shared by many applications. It is often seen that the concurrent I/O access to the storage degrades performance [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF][START_REF] Skinner | Understanding the causes of performance variability in hpc workloads[END_REF]. There are two main reasons for that. First, I/O access from the compute node uses the storage infrastructure (network, disks, etc.) and hence several concurrent accesses in "best-effort" mode lead to contention on these resources. Such contention is often over-additive : due to hardware restrictions, the time spent by each application executed simultaneously is larger than the time that each application would spend without contention if they were executed alone. The second reason is that when applications compete for resources, they are blocked waiting for their request to be completed. This is suboptimal if we compare this to the case where each application access these resources one at a time: the time spent doing I/O is much more reduced in the latter case. Therefore, we need to design algorithms that shift the focus from raw computational power to handle the bottleneck due to data management.

To tackle this problem, some approaches aim at reducing the amount of data by compressing or pre-processing it [START_REF] Tessier | Topology-aware data aggregation for intensive i/o on large-scale supercomputers[END_REF][START_REF] Di | Fast error-bounded lossy hpc data compression with sz[END_REF][START_REF] Dorier | Damaris: How to efficiently leverage multicore parallelism to achieve scalable, jitter-free i/o[END_REF]. Moreover, new hardware features, such as burst buffers, are designed to absorb spike in storage access. However, these solutions do not fully address the problem of resource contention : compression does not prevent several applications to access the storage at the same time, and a burst buffer is limited in size and hence, can also suffer from congestion. Here, the solution we explore adopts a very different point of view that is complementary to the reduction of the amount of data that transit. We aim at managing the I/O data in the system, by scheduling the access at the scale of the system Our solution is based on observations that show that some HPC applications [START_REF] Carns | 24/7 characterization of petascale i/o workloads[END_REF][START_REF] Dorier | Omnisc'io: a grammar-based approach to spatial and temporal i/o patterns prediction[END_REF][START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] periodically alternate between (i) operations (computations, local data accesses) executed on the compute nodes, and (ii) I/O transfers of data and this behavior can be predicted beforehand. Taking this structural argument, along with HPC-specific applications characteristics (there are in general very few applications running concurrently on a machine, and the applications run for many iterations with similar behavior) the goal is to design new algorithms for scheduling periodic I/O access. In this paper, we study several approaches (namely periodic and list scheduling) that takes into account the different application pattern (computation time, I/O time, number of iterations, etc.), and aim at defining the time when each application has to perform I/O. Based on different sub-cases, we are able to provide optimal algorithms, approximation algorithms or heuristics. We validate these algorithms using use cases from the literature. We show that given some criteria on the instance, we outperform the best-effort strategy. As the I/O schedule is static, we also study its robustness when inputs are subject to error or noise: in this case we show that, in many cases, our strategies still outperform the best effort one even if the characteristic of the applications are not perfectly known in advance.

Model

In this section we present a formal model to represent HPC applications alternating between compute phases and I/O phases. The model used has been verified experimentally to be consistent with the behavior of Intrepid and Mira, supercomputers at Argonne [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] and Jupiter, a machine at Mellanox [START_REF] Aupy | Periodic i/o scheduling for supercomputers[END_REF].

To do this we introduce a more general notion that we call bi-colored chains, where the chain consists of two types of operations (e.g. in this case compute and I/O), that need to be run on two different types of machine. One can then choose how to parametrize the machine consistently with the problem under study (here compute nodes and I/O bandwidth). We call Hpc-IO the name of the parametrized instance under consideration in this work.

Machine Model

We consider a platform consisting of two types of machines: type A and type B. Each of these machines can have either a bounded number of resources or an unbounded number of resources as would be the case in a typical scheduling problem.

In the I/O problem under consideration here, we consider that the jobs are already scheduled on the compute nodes (machine of type A) and that there is no competition at this level. Hence, we can assume w.l.o.g an unbounded number of such resources. On the contrary the bandwidth of the Parallel File System (PFS) (machine of type B) is shared amongst the different jobs. Hence, we say that it has a bounded number of resources B. In this work we consider B = 1. We call this instance of the platform an I/O platform.

We give a schematic overview of this model and of jobs executed on this platform in Figure 1.

Job Model

We consider scientific applications running simultaneously onto a parallel platform [START_REF] Aupy | Periodic i/o scheduling for supercomputers[END_REF][START_REF] Aupy | Sizing and partitioning strategies for burst-buffers to reduce io contention[END_REF]. The set of processing resources is already allocated to each application. With respect to I/O, applications consist of consecutive non-overlapping phases: (i) a compute phase (executed on machine A); (ii) an I/O phase (executed on machine B) which can be either reads or writes.

Inria A J 1 A 1,1 A 1,2 J 2 A 2,1 A 2,2 A 2,3 J 3 A 3,1 A 3,2 A 3,3 B Time 0 0 B B 2,1 B 1,1 B 3,1 B 2,2 B 3,2 B 1,2 B 2,3 B 3,3
Figure 1: Schematic overview of three jobs J 1 , J 2 , J 3 scheduled on a bi-colored platform.

Formally, a job J i consists of n i successive operation A i,j , B i,j (j ≤ n i ). The dependencies that need to be respected are such that: A i,j+1 (resp. B i,j ) can only start its work when operation B i,j (resp. A i,j ) is done entirely. We denote by a i,j (resp. b i,j ) the volume of work of operations A i,j (resp. B i,j ). In the Hpc-IO problem, because there is no constraint on the number of compute nodes allocated to J i , we can assume w.l.o.g that it is equal to 1 and a i,j also corresponds to the execution time of operation A i,j . Similarly, when B i,j uses the full I/O bandwidth (B = 1), b i,j corresponds to the minimal time to execute operation B i,j .

We call such jobs bi-colored chains and write them:

J i = (Π ni j=1 (A i,j , B i,j )) (1)
The minimal execution time of J i is given by the equation:

C min i = ni j=1 a i,j + b i,j (2)
In addition, in this work we consider some specific jobs called Periodic jobs. They consist in successions of identical (in volume/time) compute operations and I/O operations. Those are typical patterns in High Performance Computing [START_REF] Carns | 24/7 characterization of petascale i/o workloads[END_REF][START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF][START_REF] Dorier | Omnisc'io: a grammar-based approach to spatial and temporal i/o patterns prediction[END_REF]. We extend the notation for bi-colored chains to these jobs:

J i = ((A i , B i ) ni ) (3)

Optimization problem

In this Section we detail the Hpc-IO optimization problem. In this work, we consider the specific model where the I/O of tasks is rigid: for all applications, the I/O is always performed at full bandwidth and cannot be pre-empted. This model is what is currently implemented in Clarisse [START_REF] Isaila | Clarisse: A middleware for data-staging coordination and control on large-scale hpc platforms[END_REF].

A schedule S is fully defined by giving an order for the different I/O operations on the machine of type B. Indeed, because there is no competition for the resources of type A:

• A i,1 can start immediately;
• B i,j can start as soon as both events are finished: (i) A i,j is finished; (ii) all jobs anterior to B i,j in the schedule on the machine of type B are finished.

• A i,j+1 can start as soon as B i,j is finished.

Hence, we can formally define a schedule: Definition 1 (A schedule S). Given a set of jobs J i = (Π ni j=1 (A i,j , B i,j )), a schedule S is defined by a permutation of the jobs ((B i,j ) j≤ni ) i that satisfies, for all i, j, B i,j is before B i,j+1

We consider the classical objective function for scheduling problem. It corresponds to the system performance (makespan or execution time). In the future, we may study system fairness as well.

Let C i be the end of the execution of a job J i in the schedule S. We define the makespan C S max of the schedule S to be:

C S max = max C i (4)
Definition 2 (MS-Hpc-IO). Given a set of rigid bi-colored chains J i = (Π ni j=1 (A i,j , B i,j )), and an I/O platform. Find a schedule that minimizes the makespan C S max .

3 Complexity of Hpc-IO

Intractability

In this section we briefly present some intractability results from the literature for MS-Hpc-IO.

MS-Hpc-IO

In the literature, several results relate to this problem. The closest to our model is the Precedence Constrained Scheduling problem introduced by Wikum [START_REF] Wikum | One-machine generalized precedence constrained scheduling problems[END_REF], which studies the special case of MS-Hpc-IO.

Theorem 1 ([24, Proposition 2.3]). MS-Hpc-IO is NP-complete, even in the simplest case when n 1 = 2, and for all jobs J i , i = 1, n i = 1.

Polynomial algorithms

In this Section we present some instances where one can compute the optimal solution in polynomial time. We focus here on instances that are important for the Hpc-IO problem. Several other specific instances have been studied by Wikum [START_REF] Wikum | One-machine generalized precedence constrained scheduling problems[END_REF].

Case when ∀i, n i = 1 When for all jobs J i , n i = 1, it is easy to see that any greedy solution that schedules the I/O as soon as they are available is optimal for MS-Hpc-IO [24, Proposition 2.1].

Uniform jobs

We study the case of uniform jobs which is a specific case of periodic jobs. Specifically we consider that there exists A, B s.t., for all i, j, A i,j = A and B i,j = B. We can then write:

J i = ((A, B) ni ).
Those jobs can be used to represent some new types of workloads such as hyperparametrization in Machine Learning (see Section 5.3 for more details). In this context, all jobs are part of a bigger job and are released at the same time. Because they are part of a bigger job, we are interested in solving MS-Hpc-IO. In this section, w.l.o.g we assume that the jobs (J i ) 1≤i≤n are sorted by decreasing value of n i .

Definition 3 (Uniform). Given a set of jobs (J i ) 1≤i≤n s.t. ∀i, r i = 0, n i ≥ n i+1 and there exists A, B s.t., for all i, j, A i,j = A and B i,j = B, Uniform is the problem of solving MS-Hpc-IO.

Theorem 2. Uniform can be solved in polynomial time.

To show this result, we show that Algorithm 1 (Hierarchical Round-robin) solves the problem in polynomial time. The idea of Hierarchical Round-robin is to structure the schedule around the job with the largest n i .

Inria B Time 0 0 B B 2,1 B 1,1 B S 0 B 4,1 B 3,1 B 2,2 B 1,2 B S 1 B 5,1 B 3,2 B 2,3 B 1,3 B S 2 B 4,2 B 2,4 B 1,4 B S 3 Figure 2: J 1 = (2.5, 1) 4 , J 2 = (2.5, 1) 4 , J 3 = (2.5, 1) 2 , J 4 = (2.5, 1) 2 , J 5 = (2.5, 1) 1 Algorithm 1 Hierarchical Round-robin 1: procedure HRR(J i = (Π j≤ni A i,j , B i,j )) ∀i, j, n i ≥ n i+1 , A i,j = A, B i,j = B 2:
Let S 0 , • • • , S n1-1 be n 1 empty stacks.

3:

Id b ← 1.

4:

for i = 1 to |{J i }| do 5:

if n i = n 1 then 6:

for j = 1 to n i do 7:

Add B i,j to S j-1 .

8:

else

We do not schedule anymore on S 0 .

9:

Id e ← 1 + (Id b + n i mod (n 1 -1)) J i is scheduled from S Id b +1 to S Ide 10:
if Id b ≤ Id e then 11:

for j = 1 to n i do 12:

Add B i,j to S j+Id b .

13: else 14:

for j = 1 to Id e do 15:

Add B i,j to S j .

16:

for j = Id e + 1 to n i do 17:
Add B i,j to S (n1-1)-(ni-j) .

18:

Id b ← Id e . return S HRr = S 0 • S 1 • • • • • S n1-1
We start by scheduling each B operation of J 1 . Then, we schedule before each of those B operations all B operations of jobs such that n i = n 1 . Finally, we schedule all remaining jobs in a round-robin fashion between B 1,1 and B 1,n1 . We present in Figure 2 an example of a schedule.

We now show formally Theorem 2. To do so:

1. We define of a cost function C (Def. 5) such that for all schedule S, C S max C(S) (Prop. 1);

2. We show that there exists an optimal schedule S opt such that C(S opt ) C(S HRr ) (where S HRr is the schedule returned by Hierarchical Round-robin);

3. Finally, we show that C S HRr max = C(S HRr ) (Prop. 2), showing the result.

In the rest of this Section, we let

J i = (0, Π ni j=1 (A i,j , B i,j
)) be a set of uniform jobs sorted by decreasing n i . We denote by a (resp. b) the execution tasks of tasks A i,j (resp. B i,j ).

We introduce the notion of block :

Definition 4 (Block of a schedule S and its cost). Given a schedule S,

for k ∈ [[1, n 1 ]],
we define the block B S k to be:

• If k = 1, B S
1 is the set of tasks scheduled to be executed before (including) B 1,1 .

• Otherwise, B S k is the set of tasks scheduled to be executed after (excluding) B 1,k-1 and before (including) B 1,k .

We define the cost of a block to be:

C(B S k ) = a + |B S 1 | if k = 1 max(a + b, |B S k | • b) else
We represent the notion of Blocks on Fig. 2 Definition 5 (Cost of a schedule). Given a schedule S, its cost is

C(S) = Σ n1 k=1 C(B S k )
, where C is the function cost of a block. Proof. To obtain this result, one can observe that the blocks partition the schedule until B 1,n1 , and hence the total makespan is greater than the sum of the makespan of all blocks1 . Then, we need to show that the makespan of each block is greater than the cost of each block, hence showing the result. This comes naturally from the fact the makespan of a block is necessarily greater than the maximum between (i) the total work that has to be performed during this block (|B S k | • b), and (ii) the minimal length imposed by J 1 (an execution of A i,j and an execution of B i,j ). Hence, the makespan of a block is greater than its cost, showing the result. Definition 6 (Dominant schedules). For Uniform, we say that a schedule is dominant if:

1. Prop. (Dom.1) The last task executed on platform B is B 1,n1 ; 2. Prop. (Dom.2) For all J i , (n i -j + i) < n 1 , implies B i,j is executed after B 1,1 . 3. Prop. (Dom.3) For all J i s.t. n i = n 1 , B i,1 is executed before B 1,1 .
In practice Dominant Schedules are schedules that finish by the last operation of J 1 , and that start by all first operations of long jobs and then by B 1,1 . Lemma 3. There exists a dominant schedule which is optimal.

Proof. We show the result in three steps:

1. First, we show that there exists an optimal algorithm which ends by the execution of B 1,n1 ; 2. Amongst those optimal algorithms, we show that there exists at least one where for all J i s.t.

(n i -j + 1) < n 1 , implies B i,j is executed after B 1,1 ;

3. Finally, amongst those, we show that there exists at least one s.t. for all J i s.t.

n i = n 1 , B i,1 is executed before B 1,1 .
There exists an optimal algorithm that satisfies Prop. (Dom.1) We show the result by contradiction. Assume there does not exist an optimal schedule which ends by the execution of B 1,n1 .

Let S be an optimal schedule for Uniform that minimizes the number of operations following B 1,n1 . Let B i,k be the operation directly subsequent to B 1,n1 in the schedule.

If k = n 1 , then because all A i,j are identical, for 1 ≤ j ≤ k, we can permute all B i,j operations with B 1,j without increasing the makespan, and the number of operations after B 1,n1 decreased strictly, contradicting the minimality of S.

Otherwise, necessarily k < n 1 (indeed, by definition, for all i, n i ≤ n 1 ). In this case, necessarily there exist two consecutive operations of J 1 such that there are no operations of J i between them. Let us call B 1,n1-j0-1 and B 1,n1-j0 those last operations. Then, because all jobs are identical, for 0 ≤ j ≤ j 0 , we can permute all B i,k-j operations with B 1,n1-j operations without increasing the total makespan. In this new schedule, the number of operations after B 1,n1 decreased strictly, hence contradicting the minimality of S.

We denote by A 1 OP T the non-empty set of optimal schedules that satisfy Prop. (Dom.1).

There exists a schedule in A 1 OP T that satisfies Prop. (Dom.2) Similarly, we show the result by contradiction. Assume that for all schedules of A 1 OP T , none satisfy Prop. (Dom.2). Let S ∈ A 1 OP T that minimizes the number of operations B i,j that satisfy (i) B i,j is scheduled before B 1,1 ; (ii) n i -jn 1 -1. Let B i,j0 be the last of these operations before B 1,1 in S.

Then, because (n i -j 0 + 1) < n 1 , necessarily there exists k < n 1 s.t. there are no operations of J i between B 1,k and B 1,k+1 . Let us denote by k 0 the smallest of such k. Then, for j ∈ {1, • • • , k 0 }we can permute in S all operations B 1,j and B i,j0-1+j without increasing the schedule length. Indeed, there is no new idle time between any pair of operations B 1,j and B 1,j+1 for j < k 0 (because a 1,j = a i,j0-1+j = a, nor between B 1,k0 and B 1,k0+1 because B 1,k0 was advanced in time while B 1,k0+1 did not move. Similarly, there is no new idle time created in the schedule between B i,j0-1+j and B i,j0+j . B i,j0+k0 is scheduled after B 1,k0+1 while B i,j0-1+k0 is scheduled where B i,k0 was scheduled, so the time difference between them is greater than a.

Finally, this did not impact either any other jobs because the number of jobs on B between two occurrences on any other jobs was kept the same.

We can conclude that this transformation did not increase the execution time. In addition, it did not change the schedule after B 1,k0+1 where k 0 + 1 ≤ n 1 , hence Prop. (Dom.1) is still respected in this new optimal schedule. There was, however, one fewer job before B 1,1 , contradicting the minimality of S.

We denote by A 2 OP T the non-empty set of optimal schedules that satisfy both Prop. (Dom.1) and Prop. (Dom.2).

There exists a schedule in A 2

OP T that satisfies Prop. (Dom.3) Similarly, we show the result by contradiction. Assume that for all schedules of A 2 OP T , none satisfy Prop. (Dom.3). Let S ∈ A 1 OP T that minimizes the number of operations B i,1 that satisfy (i) B i,1 is scheduled after B 1,1 ; (ii) n i = n 1 . Let B i0,1 be the first of these operations after B 1,1 in S.

By a reasoning very similar to the one used to prove the existence of the set A 2 OP T , one can show that S can be chosen such that B i0,1 is the operation directly subsequent to B 1,1 .

Because n i0 = n 1 , and because S satisfies Prop. (Dom.1), there exists j 0 ≥ 1 such that B i0,j0 and B i0,j0+1 are scheduled between B 1,j0 and B 1,j0+1 .

Thanks to the property that ∀i, j, a i,j = a, we can then create a new schedule whose execution time is not greater than that of S by permuting for 1 ≤ j ≤ j 0 , B i0,j and B 1,j . This schedule still satisfies Prop. (Dom.1) (we have not modified the location of B 1,n1 ), and Prop. (Dom.2) (the only task that was moved before B 1,1 is B i0,1 ), contradicting the minimality of S.

Finally, this concludes the proof that there exists an optimal schedule that is dominant.

q 1 = i ni-l1 (n1-1)
Then, we have the following results:

• |B S HRr 1 | = l 1 , • for j = 2 to r 1 + 1, |B S HRr j | = q 1 + 1, • for j = r 1 + 2 to n 1 , |B S HRr j | = q 1 .
Proof. This is a direct consequence from Algorithm 1. One can notice that B S HRr k corresponds to S k-1 as returned at the end of the execution.

Hence, B S HRr 1 only contains the first operation of jobs of length n 1 (hence l 1 operations), and the rest of the blocks share the remaining operations minus those l 1 operations, hence the result. Lemma 5. Given S a dominant schedule, then C(S) ≥ C(S HRr ).

Proof. In this proof we use the definition of l 1 , q 1 and r 1 as defined in Lemma 4.

Let S be a dominant schedule. Denote by p min = min n1 k=2 {|B S k |} (resp. p max = max n1 k=2 {|B S k |}, the smallest (resp. largest) block size for all blocks of S but the first one.

We show the result by recurrence on . By definition of a dominant schedule, we know that

n1 k=2 |B S k | = i n i -l 1 ,
hence necessarily p min ≤ q 1 ≤ p max . By definition of q 1 and r 1 , if p max -p min ≤ 1, then p min = q 1 and there are exactly r 1 blocks of size p max and n 1 -r 1 blocks of size p min . Hence, C(S) = C(S HRr ). In the following we assume that p max -p min > 1. In particular we have: Again, the path of solutions may not theoretically exist, however this process shows that their cost is indeed greater than that of S HRr . Proof. We study the stacks S 0 , • • • , S n1-1 as returned by Algorithm 1. Note that we have seen that there execution time is necessarily at least equal to their cost because of J 1 . We now show that this time is enough for a successful execution of the schedule.

p min ≤ q 1 < q 1 + 1 ≤ p max . If p min • b ≥ a + b (resp. p max • b ≤ a + b) Then, we have: n1 k=2 C(B S k ) = n1 k=2 |B S k | • b = b ( i n i ) -l 1 = b n1 k=2 |B S HRr k | = n1 k=2 C(B S HRr k ) (resp.
The time to execute S 0 is exactly C(S 0 ), indeed all jobs in this stack are executed for the first time, hence we need to wait for a time a, then all I/O operations are ready and we can execute them consecutively (taking a time |S 0 | • b.

We then show the result on the other stacks by studying the l th element from the bottom of the stack (the first element of each stack S k is B 1,k+1 ).

Given stack S k , denote by B i,j its l th element:

• Either j = 1, in which case it was ready since S 0 and there are no additional time constraints;

• Or B i,j-1 was put on stack S k-1 , then it was at the l th position of the stack because the stack is balanced. In which case, there are exactly l -1 (resp. |S k | -l) operations on stack S k-1 (resp. S k ) between those two operations, hence a total time of (|S k | -1) • b. Hence, we need an idle time at the beginning of the execution of S k of length max(0, a -(|S k | -1) • b), and an execution time for S k of C(S k ) is enough for its successful execution.

• Finally, with the round robin property, B i,j-1 could be scheduled on stack S k where k < k -1.

In this case the time constraint is also respected because S k-1 takes by definition more than a units of time.

Hence, the result, we have shown that an execution time equal to the cost for each task was enough to satisfy all the time constraints.

Proof of Theorem 2.

There exists an optimal schedule S opt to Uniform, such that (i) C Sopt max ≥ C(S opt ) (Prop. 1); (ii) C(S opt ) ≥ C(S HRr ) (Lemma 3 and Lemma 5). Finally, we have seen (Prop. 2) that C(S HRr ) = C S HRr max , proving that Hierarchical Round-robin is optimal.

Approximation algorithms for MS-Hpc-IO

We have seen in Section 3 that MS-Hpc-IO was in general intractable. A natural question to this is whether there exist efficient approximation algorithms. In this section we show some results on list-scheduling algorithms, then discuss a specific framework of algorithms, periodic algorithms.

Definition 7 (Approximation algorithm). For a maximization (resp. minimization) problem P, we say that an algorithm A is a λ-approximation algorithm, if for any instance I ∈ P, A(I) ≤ λA OP T (I) (resp. A(I) ≥ λA OP T (I)) (where A OP T is an optimal algorithm for P).

RR n°9255

List Scheduling algorithms

We start by considering list scheduling strategies (also called greedy) which are often considered the most natural algorithms: at all time, either the machine B is busy or no work of type B is available. When the machine becomes idle and some multiple operations are available, the machine sorts them (and schedule them) following a priority order.

Theorem 6. Any list-scheduling algorithm is a 2-approximation for MS-Hpc-IO and this ratio is tight.

Proof. First, we show that any list-scheduling algorithm is at best a factor two of the optimal for MS-Hpc-IO. We create the instance I ε :

J 1 = ((A 1,1 = 0, B 1,1 = 1)), J 2 = ((A 2,1 = ε, B 2,1 = ε) • (A 2,2 = 1, B 2,2 = 0)).
The makespan of any list-scheduling algorithm is: 2 + ε. Indeed, at t = 0, a listscheduling algorithm has to schedule B 1,1 because it is the only operation ready. Then, once it is done, it can schedule B 2,1 , which will be followed by the execution of A 2,2 and B 2,2 .

On the other hand, an optimal schedule waits for ε units of time so it can schedule B 2,1 first. Then, it schedules B 1,1 while A 2,1 executes. The total execution time is 1 + 2ε. Hence, the approximation ratio is at least:

λ = sup ε>0 2 + ε 1 + 2ε = 2
We now show that any list-heuristic algorithm is at most a 2-approximation. Given an instance of the problem, let C List max be the makespan of a list-scheduling algorithm and C OP T max be the makespan of an optimal algorithm.

Necessarily, C OP T max ≥ max i ( j a i,j + b i,j ) which is the minimal time needed for the longest application J i . We focus on the occupation of platform B. C List max = i j b i,j + t idle , where t idle is the time where platform B is waiting for work. Let B i0,ni 0 be the last operation scheduled on B. Then, necessarily, t idle ≤ ni 0 j=1 a i,j . Hence, we have:

C List max = i j b i,j + t idle ≤ C OP T max + ni 0 j=1 a i,j ≤ 2C OP T max 4.

Periodic algorithms

In this section we focus on periodic applications as defined in Section 2. Those applications are very frequent in our target framework, High-Performance Computing2 . To tackle them, we study a specific sort of algorithms: Periodic algorithms. Indeed those algorithms have many efficient property such as a low memory and compute overhead when the number of operations per jobs is very high [START_REF] Aupy | Periodic i/o scheduling for supercomputers[END_REF]. We start by showing that in some context, those algorithms are efficient approximations for the MS-Hpc-IO problem.

We define formally a periodic algorithm:

Definition 8 (Periodic Algorithm). Given a periodic instance J = ((a i , b i ) ki•n ).
A periodic algorithm P constructs a period which is a schedule of J = ((a i , b i ) ki ): then returns a schedule built by n periodic repetition of the period.

Periodic algorithms for MS-Hpc-IO We start by considering periodic jobs whose n i are all equal. In this case Hierarchical Round-robin is a periodic algorithm.

Theorem 7. Hierarchical Round-robin is a 1 + 1/n-approximation algorithm for MS-Hpc-IO where all jobs are periodic with the same number of periods (there exists n, such that ∀i, J i = ((A i , B i ) n )), and the bound is tight.

Proof.

Relire cette preuve First, we discuss the way of ordering tasks within a period and then discuss the performance of such scheduling algorithms.

• In the following, I call "idle time" of a schedule S, the time t i (S) = M S S -Σ i nb i

• In Periodic, all jobs have only one task in each period. We can define the order ≺: i ≺ j if and only if b i appears before b j in the period.

The overall idle time of the periodic schedule is:

t i (P eriodic) = (n -1).max i a i -Σ j =i b j + max k a k -Σ k≺j b j
The order within a period does not change the overall idle time, therefore we can sort tasks by non-increasing A-task length in a period with gives:

t i (P eriodic) ≤ (n -1).max i a i -Σ j =i b j + max k (a k )
Given an optimal schedule S opt , the idle time is:

t i (S opt )max i na i -n Σ j =i b j + Σ j≺i b j ≥ n. max k a k -Σ j =k b j
where i is the last task running on A and i 1 is its first iteration. Therefore, using straightforward bounds, the difference between these periodic and opt is at most:

n.max i (a i ) -n max k a k -Σ j =k b j ≤ n.max i (a i )
The optimal makespan is at least n.max i (a i + b i )

Remark. One can notice that Hierarchical Round-robin is asymptotically optimal for MS-Hpc-IO when all jobs are periodic with the same number of periods. In addition, one can slightly improve the result by sorting the jobs by decreasing values of a i . Additional work aimed to develop periodical algorithms is ongoing. We want to discuss period building given the objective function. In the meantime, we use simple heuristics to run experiments.

Other simple heuristics for periodic strategies Given an instance J i = (a i , b i ) ni , we can sort all couples (a i ,b i ) following any order to have an ordered sequence of tasks. This sequence can then be used as a period for the algorithm. The completion of a job or the release of a new one does not change the relative order of the other. Hence, the period holds after such events.

Among the possible possibilities, we can use the FIFO or the Johnson order.

Definition 9 (Johnson's order). Given a set of couples (a i , b i ), divide the values into two disjoint groups G 1 and G 2 , where G 1 contains all couples (a i , b i ) with a i b i , and G 2 contains all couples (a j , b j ) with a j > b j . Order the couples in a sequence such that the first part consists of the values in G 1 , sorted in nondecreasing order of a i , and the second part consists of the values in G 2 , sorted in nonincreasing order of b j .

Remark. If jobs are J i = (a i , b i ) 1 , the schedule using Johnson order minimizes the completion time of the flowshop. [START_REF] Wu | On scheduling two-stage jobs on multiple twostage flowshops[END_REF].

Results

In Figure 3, we present the makespan for the general case. The presented graph is the smoothed conditional means on a set of 1000 instances of each case as a function of the weight of I/O, W ,that accounts for a normalize way of measuring the amount of I/O :

W = i j b i,j j a i,j + b i,j
In this Figure, we see that, when the weight of I/O is small, the best effort strategy provides the fastest makespan. This is due to the fact that when there are few I/O, scheduling them is not very useful. However, as soon as the amount if I/O increases, the scheduling strategies improves and outperform the best effort one. Moreover, we see two groups of curves. Periodic schedules and listscheduling ones. The periodic strategies, FIFO Periodic, Johnson Periodic and Most Remain Periodic are superposed. If we compare these two sets of strategies, we see that when the amount of I/O is small relative to the total of work, list scheduling perform better than periodic strategies and when the weight of I/O increases the periodic strategies are better than the list-scheduling ones. Indeed, when there is few I/O the periodic schedule can force an application to wait for their turn while when there is a high amount of I/O, the short view of the problem by list scheduling algorithm hinder their capacity to handle I/O burst. Uncertainty and noise In our implementation, list scheduling and periodic policies assume that the I/O and computation duration are known in advance. However, in practice these values can never be known with a complete certainty. To model this uncertainty we have added noise to I/O and computation duration. This means that the computation or the I/O phase can be subject to a variation around the expected, periodical amount. This variation is generated based on a seed that is included with the application specification in order to be reproducible. Indeed, we want this variation to be the same without any concern of the application order.

In Fig 4, we present the results with respectively 20% and 50% of noise using the same inputs as for the one in Fig 3.

We see that adding noise slightly degrades the performance when the amount of I/O is small compared to the total amount of work. However, when the weight of I/O increases we observe Machine Learning Use-Case We describe here a use case where a set of applications is launched at the same time and perform periodic I/O. The goal is to train, in parallel, several deep-learning networks (DLNs) on the same dataset. It works as follows. A set of m nodes of a parallel machine is reserved. m DLNs are generated and trained separately on each node. The goal is to find the best network among the m ones. Therefore, they are trained on the same dataset. Each DLN access a subpart of the dataset from the storage and train itself on this subpart using supervised learning (e.g. with a gradient descent). Then, if the network has not converged it fetches another subpart of the dataset and iterate the learning part. As, for a given DLN, the subpart is of the same size, the IO time (without congestion) and learning time is constant across iterations. However, as each DLN is different (e.g. in terms of topology and meta parameters) the number of iterations is different across DLN. Therefore, according to our nomenclature this use-case fits the Uniform case :

J i = (A, B) ni , i ∈ [1, m].
In Figure 5, we compare best effort and the FIFO list scheduling strategies which are both nonclairvoyant (they do not know in advance the number of periods) against the Hierarchical Roundrobin for which the closed form of the makespan is given as follows. We are in the Uniform case: the set of jobs is J i = (0, (a, b) ni . We denote by n = max i n i , l = |{J i0 |n i0 = n}| (the number of jobs of maximum n i ), q = ( i ni)-l n-1 and r = (( i n i ) -l) mod (n -1). Then, the makespan of Hierarchical Round-robin C HRr max is:

C HRr max = a + l • b + (n -1 -r) • max(a + b, qb) + r • max(a + b, (q + 1)b)
According to Theorem 2], Hierarchical Round-robin is asymptotically optimal. Moreover, the FIFO list-scheduling is a 2-approximation algorithm (Theorem ). For this use case, we see that despite the fact that the FIFO list-scheduling is non-clairvoyant it provides a makespan very close to Hierarchical Round-robin (less than 10% slower). Concerning the best effort strategy, we see that it performs worse than FIFO list-scheduling and up to 60% slower than Hierarchical Roundrobin. Indeed, in this case, the access of the I/O is synchronized and the best-effort strategy maintain this synchronization and hence the I/O contention during the whole execution of the instance.

To test the case where we can have desynchronization due to uncertainty in computation or I/O execution, we have added 20% of uniform noise on these two costs. The results are presented on the right of Figure 5. In this case, we see that the noise has almost no impact on the FIFO list-scheduling Inria strategy. For the best effort strategy, we see that it has a better performance than without noise but it is still worse than the FIFO list-scheduling. This shows that the best effort strategy does not behave well in case of high congestion of the network.

6 Related work

Related theoretical problems

The MS-Hpc-IO problem may recall the classical job shop problem (see definition in [START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF]). In both problems jobs are composed of dependent tasks that have to be performed on specific machines. However, here, we do not have constraints on the computation machine therefore if knowledge of job shop can help to develop insight of solutions, it can not be used straightforwardly for Hpc-IO. Variants of job shop and flow shop are abundantly discussed : [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF][START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF][START_REF] Tanaev | Scheduling theory. Single-stage systems[END_REF][START_REF] Brucker | Scheduling algorithms[END_REF]. Recall that flow shop is a particular case of job shop where the operation sequences do not depend on jobs.

State of the art in I/O management for HPC systems

We are not the first to study performance variability caused by I/O congestion. In this section we will detail some of the existing work and different approaches to understand this issue.

Data transformation As contention arises with large amount of data, recent studies propose application-side strategies based on I/O management and transformation. Lofstead et al. [START_REF] Lofstead | Managing variability in the io performance of petascale storage systems[END_REF] study adaptive strategies to deal with I/O variability due to congestion by modifying at certain times both the number of processes sending data , and the size of the data being sent. Tessier and al. [START_REF] Tessier | Topology-aware data aggregation for intensive i/o on large-scale supercomputers[END_REF] focus on the locality of aggregate nodes. These nodes are compute nodes dedicated data sent by other compute nodes during the I/O phase of an application. Those nodes also have the possibility to transform the data being sent (for instance by compressing it [START_REF] Dorier | Damaris: How to efficiently leverage multicore parallelism to achieve scalable, jitter-free i/o[END_REF]). To go further, data can even be compressed in a lossy way [START_REF] Di | Fast error-bounded lossy hpc data compression with sz[END_REF]. In-situ/intransit analysis developed in recent works [START_REF] Dreher | A flexible framework for asynchronous in situ and in transit analytics for scientific simulations[END_REF] try to deal with file systems reaching their limit. In the past, some workflows used to create the data and to store it on disks before analyzing it as a second step. In-situ/in-transit analysis offers to dedicate some specific nodes to the analysis and to perform it as the data is created. The hope is to reduce the load on the file systems.

We consider that all these solutions occur uphill to our problem and hence can be used conjointly.

Software to deal with I/O movement On the application side, the I/O congestion issue can be seen as scheduling problem [START_REF] Lofstead | Managing variability in the io performance of petascale storage systems[END_REF][START_REF] Zhang | Opportunistic data-driven execution of parallel programs for efficient i/o services[END_REF]. Work using machine learning for auto tuning and performance study [START_REF] Behzad | Taming parallel i/o complexity with auto-tuning[END_REF][START_REF] Kumar | Characterization and modeling of pidx parallel i/o for performance optimization[END_REF] can be applied for I/O scheduling but do not provide a global view of the I/O requirements of the application. Coupling with a platform level I/O management ensure better results.

Cross-application contention has been studied recently [START_REF] Hashimoto | Evaluation of performance degradation in hpc applications with vm consolidation[END_REF][START_REF] Skinner | Understanding the causes of performance variability in hpc workloads[END_REF][START_REF] Uselton | Parallel i/o performance: From events to ensembles[END_REF]. The study in [START_REF] Hashimoto | Evaluation of performance degradation in hpc applications with vm consolidation[END_REF] evaluates the performance degradation in each application program when Virtual Machines (VMs) are executing two application programs concurrently in a physical computing server. The experimental results indicate that the interference among VMs executing two HPC application programs with high memory usage and high network I/O in the physical computing server significantly degrades application performance. An earlier study in 2005 [START_REF] Skinner | Understanding the causes of performance variability in hpc workloads[END_REF] cites application interference as one of the main problems facing the HPC community. While the authors propose ways of gaining performance by reducing variability, minimizing application interference is still left open. In [START_REF] Xie | Characterizing output bottlenecks in a supercomputer[END_REF], a more general study analyzes the behavior of the center wide shared Lustre parallel file system on the Jaguar supercomputer and its performance variability. One of the performance degradations seen on Jaguar was caused by concurrent applications sharing the filesystem. All these studies highlight the impact of having application interference on HPC systems, without, but they do not offer a solution. Closer to this work, online schedulers for HPC systems were developed such as Aupy et al. [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF], the study by Zhou et al [START_REF] Zhou | I/oaware batch scheduling for petascale computing systems[END_REF], and a solution proposed by Dorier et al [START_REF] Dorier | Calciom: Mitigating i/o interference in hpc systems through cross-application coordination[END_REF]. In [START_REF] Dorier | Calciom: Mitigating i/o interference in hpc systems through cross-application coordination[END_REF], the authors investigate the interference of two applications and analyze the benefits of interrupting or delaying either one in order to avoid congestion. Unfortunately their approach cannot be used for more than two applications. Another main difference with our previous work is the light-weight approach of this study where the computation is only done once. Clarisse [START_REF] Isaila | Clarisse: A middleware for data-staging coordination and control on large-scale hpc platforms[END_REF] proposes mechanisms for designing and implementing cross-layer optimizations of the I/O software stack. The specific implementation of the problem considered here is a naive First Come First Served approach. They, however, provide an excellent opportunity to study our results in a real framework.

Hardware solutions Diminishing I/O bottleneck can also be thought at an architectural level. Previous papers [START_REF] Liu | On the role of burst buffers in leadership-class storage systems[END_REF] noticed that congestion occurs on a short period of time and the bandwidth to the storage is often underutilized. As the computation power used to increase faster than the I/O bandwidth, this observation may not hold in the future. In the meantime, delaying accesses to the system storage can smoothen the I/O request over time and tackle latency. An example of this technique is presented in Kougkas et al [START_REF] Kougkas | Leveraging burst buffer coordination to prevent i/o interference[END_REF]. A dynamic I/O scheduling at the application level, using burst buffers, stages I/O and allows computations to continue uninterrupted. They design different strategies to mitigate I/O interference, including partitioning the PFS, which reduces the effective bandwidth non-linearly. Note that for now, these strategies are designed for only two applications, furthermore they are not coupled with an efficient I/O bandwidth scheduling strategy and can only work because they considered an underutilized I/O bandwidth.

Conclusion

In this report we have studied the problem of scheduling I/O access for applications that alternate computation and I/O. We have formally described the problem as scheduling bi-colored chains. Then, we have studied theoretical results. Despite the fact that the general case is NP-complete, we have provided an optimal algorithm for the Uniform case. Moreover, we have studied two classes of strategies: periodic and list scheduling ones. We have shown that any list-scheduling algorithm is a 2-approximation and that Hierarchical Round-robin is asymptotically optimal for the periodic case. We have also studied different order for instantiating several heuristics (both periodic and Inria list-scheduling ones).

We have experimentally tested, through simulations, the proposed approaches on realistic cases. We have shown that periodic approaches are the best ones when the relative amount of I/O is high and that the best effort strategy is the worst one. Moreover, we have studied the case where the input is not known with complete certainty but subject to noise. In this case the proposed approaches are shown to be robust. Last, we have studied the case of a distributed learning phase for deep-learning. Results show that the FIFO list-scheduling strategy is very close to the optimal one (despite being non-clairvoyant) and much better than the best effort.

In future work, we want to study several directions. The first one, concern the study of fairness. Indeed, the proposed strategies may favor some applications against others. We would like to devise algorithms that could guarantee that the worst degradation is bounded. We would also like to study the impact of release dates. In this study all the applications start at the same time, which is not realistic. When evaluating the makespan, having release dates makes little sense, however, if we want to study fairness, release dates is a parameter that we will have to take into consideration. Last, we would like to implement strategies based on what we have learned here into an I/O scheduling framework such as Clarisse. We have started a collaboration with the University of Madrid to work in that direction.

Proposition 1 .

 1 For any schedule S, C S max C(S).

Lemma 4 .

 4 Denote by l 1 = |{J i |n i = n 1 }| and S HRr the solution returned by Hierarchical Roundrobin. Let r 1 = ( i n i -l 1 ) mod (n 1 -1), and

  meaning that C(S) = C(S HRr ). Inria Else, p min • b < a + b < p max • b In this case, because |p max -p min | ≥ 2, we can show that the cost is strictly greater to the cost of a solution with one element fewer in the largest block, and one more element in the smallest block. This can be done recursively until one of the initialization case as seen above (either |p max -p min | ≤ 1, p min • b ≥ a + b, or p max • b ≤ a + b) for which we have shown that the cost is equal to C(S HRr ). Indeed, assume the cost of the smallest block increases by 0 ≤ δ < b (resp. cost of the largest bock decreased by 0 < δ ≤ b). Then, a + b ≤ (p max -1) • b (resp. (p min + 1) • b ≤ a + b), and the cost of the largest block decreased by b (resp. the cost of the smallest block did not increase). Hence, the total cost decreased by b -δ > 0 (decreased by δ > 0).

Proposition 2 .

 2 C(S HRr ) = C S HRr max

Figure 3 :

 3 Figure 3: Policies performance comparison on generic inputs for the makespan relative to the Best effort strategy.

Figure 4 :

 4 Figure 4: Policies performance comparison on generic inputs for the makespan relative to the Best effort strategy with uniform noise on the computation or I/O duration

Figure 5 :

 5 Figure 5: Policies performance comparison of the ML use case for the makespan relative to Hierarchical Round-robin (left no noise, right 20% of uniform noise).

RR n°9255

Where the makespan of block B S k (resp. B S 1 ) is naturally defined as the time between the beginning of the execution of B 1,k on platform B and the beginning of the execution of B 1,k+1 on platform B.Inria

Think, for instance, of applications storing its checkpoint at regular intervals Inria

Inria

avenue de la Vieille Tour 33405 Talence Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Evaluation

In this section we present the experimental evaluation of the proposed solutions. To evaluate them we have designed a simulator that implements the model described in section 2.

Heuristics

We implemented different kind of policies in our simulator.

List scheduling

In list scheduling policy, as soon as I/O is free, we execute the most critical, available application. We used different orders to define the criticality of a given application:

• FIFO: the applications I/O are executed in the order of their request.

• Johnson: the application I/Os are executed following Johnson's order (see definition 9)

• Most Remain: When scheduling an I/O, pick in priority the application with the most remaining work to do.

Periodic We use periodic heuristics as defined in 4.2 : recall that jobs are sorted upstream, then the schedule repeat periodically one task of each job following this order. In this study we use the same 3 orders as for the list-scheduling case.

Best effort With the best effort strategy, there is no schedule of I/O accesses. Instead of waiting their turn to perform I/O operations, concurrent applications accessing the storage system share equally the bandwidth without additional loss. If k applications are performing I/O operations, an application with b amount of I/O will have, after t units of time, b -t k remaining amount of I/O. The best effort strategy models what happens in real systems when there is no congestion control or I/O scheduling at the level of the applications.

Scenarios/Use-case and instantiation

Applications are modeled by their computation, I/O durations, and their number of periods. An input file describes an instance of the problem as a set of m applications and is generated according to table 1. We have two different cases that represent realistic settings. The Uniform case is used for a machine learning multi-parameter training and covers the results of Section 3.2.

Inria


Jean-Pascal Andraud

S Criquet

Benjamin Oursel

Stephane Greff

Thierry Woignier

Hervé Macarie

Test of chlordecone dechlorination by chemical reduction using Fe(II

est destinée au dépôt

Degrade the chlordecone stock of FWI soils by using Fe(III)-oxides present in situ via biological iron-reduction.

1. Show that chlordecone can be dechlorinated by chemical reduction using Fe(II)/Fe(III)-oxides coupling (Fig. 2 : "Abiotic step") 2. Couple biological iron reduction with chemical reduction of chlordecone, using Iron-Reducing Bacteria (IRB) 3. Test chemical and biological steps on FWI soils incubated under anoxic conditions at lab-scale.

The Sixth International Symposium on Environmental Biotechnology and Engineering

Ciudad Obregón, Sonora, México. November 5 th to 9 th , 2018

Test of chlordecone dechlorination by chemical reduction using Fe(II)/Fe(III)-oxides coupling

Jean-Pascal ANDRAUD 1 *, Stéven CRIQUET 1 , Benjamin OURSEL 2 , Stéphane GREFF 1 , Thierry WOIGNIER 1,3 , Hervé MACARIE 1

1 Aix Marseille Univ, Univ Avignon, CNRS, IRD, IMBE, Marseille, France. 2 Aix Marseille Univ, Université de Toulon, CNRS, IRD, MIO, Marseille, France.

Results & Conclusions

FWI soils are very rich in iron, which accounts for 7 to 11% of their dry weigh. As these soils are oxic, iron is found mainly in the form of Fe(III)-oxides, and more precisely in the form of goethite, hematite and ferrihydrite whose proportions vary according to the type of soil (Fig. 1).

The potential (E 0' ) of the redox couples formed by Fe(III)-oxides/Fe(II) and Fe(II)/Fe 0 (E 0' ≈ -470 mV) are similar (Fig. 2 : Redox scale). This indicates that the Fe(II) resulting from the Fe(III)-oxides microbial reduction could be an electron donor as effective as Fe 0 for attacking CLD. Today, chlordecone (CLD), an organochlorine pesticide spread on the soil to control the populations of the banana weevil, is responsible for an unprecedented health, environmental, social and political crisis in the French West Indies (FWI). Despite the health management measures implemented by the authorities to prevent CLD from reaching the consumer's plate, the population continues to be exposed. A definitive solution to the problem would be to destroy the CLD stock in the soil.

Objectives

 Dechlorination test at acid pH: no degradation showed by measuring chlorides with ionic chromatography.

 Negative redox potentials are required for dechlorination, and these are mostly conditioned by the pH as derived from the literature (Fig. 3).

 With NaHCO 3 buffer, the formation of a FeCO 3 precipitate appears. The Eh measured therefore correspond to the Fe(III)-oxides/FeCO 3 couple which are theoretically less negative than the Fe(III)-oxides/Fe(II) couples (Table 1).

E h (NaHCO 3 ) > E h (MOPS)

 Coming soon: dechlorination test in both types of buffer with goethite and then the other Fe(III)-oxides.

  3 IRD, IMBE, Campus Agro-environnemental Caraïbe, Le Lamentin, Martinique, France. * Corresponding author: jean-pascal.andraud@imbe.fr  Anoxic incubation under agitation at 25°C (room temperature)  25 mL of buffer to maintain a pH of the reaction mixture at 7.5-8:  Organic buffer: MOPS (25 mM)  Inorganic buffer: NaHCO 3 (11.9 mM)  Fe(III)-oxides: hematite, goethite, ferrihydrite, magnetite  1 mM FeSO 4 , 7 H 2 0  Redox potentials and pH measurements under anoxic conditions

Figure 1 :

 1 Figure 1: Fe(III)-oxides powders (Goethite, Ferrihydrite, Hematite)

Figure 3 :

 3 Figure 3: Reduction potential (Eh) values of goethite suspensions as a function of aqueous Fe 2+ concentration and pH. Error bars represent the standard deviation from triplicate reactors. No error bars are present for the pH 6.0 and 6.5 reactors because only one reactor was measured for each point. The dashed gray lines represent the model fit. Experimental details: 1 g/L goethite, 25 mM KCl, 50 mM buffer, and 10 μM mediator.