FINANCIALIZATION AND VESTED INTERESTS: THE IRRELEVANCE OF SELF-REGULATION AND FINANCIAL STABILITY AS A PUBLIC GOOD

Keywords: Vested interests, financialized capitalism and regulation Financialization, financial crisis, financial regulation, institutionalism, monetary economy, public good, Thorstein Veblen JEL Classification Codes: B52, E42, G01, G18, H41

This study proposes an institutionalist analysis of financialization through the lens of Veblen, built on some peculiar characteristics of money and related financial relations in a marketbased capitalist economy. Following the case of the overcapitalization of farmlands, studied by Veblen in The Vested Interests, the analysis argues that modern capitalism is a financialized society dominated by vested interests that rely on financial liberalization-led speculative overcapitalization that often leads to a perverse accumulation process and results in systemic catastrophes. Consequently, one of the major constituent institutions of liberal finance, market-dependent self-regulation, reveals to be unable to deal with society-level issues such as financial stability. This latter must be handled at a systemic level as a public good. Therefore specific public regulation and action mechanisms must be designed to maintain society (and dominant vested-interests) within some viability limits to ensure a smooth functioning of the economy.

Introduction

This study builds on some peculiar characteristics of money and related financial relations in a market-based capitalist economy and proposes an institutionalist analysis of financialization through the lens of Veblen. I argue that liberalized finance-based capitalism transforms itself into a financialized society which is dominated by vested interests that rely on speculative activities to feed their net return expectations. As in the case of Veblenian overcapitalization of farmlands, financial liberalization leads to a speculative overcapitalization of every aspect of Common Man's life and results in economic-financial and social catastrophes.

An accurate analysis of the monetary nature of the capitalist economy shows that financial stability is a core condition for the smooth functioning of society. However, given the very specific characteristics of money and financial operations in such an economy, privatized self-regulatory mechanisms are unable to provide global solutions to macroeconomic concerns like financial (in)stability. This latter must be handled at a systemic level and considered as a public good. Therefore specific "extra-market" public regulation and action mechanisms must be designed to organize, manage and supervise financial stability.

In this aim, drawing on Veblen's work, I review first the financialization process of capitalist society that radically transforms the production relations among different economic/social groups and results in an unsustainable economic/financial structure. I then develop a monetary framework to catch the structural characteristics of a marketbased capitalist economy whose smooth working relies on the stability of financial operations at a macro level. This framework shows that micro-rationality-based selfregulation is unable to ensure a viable functioning of the economy. Finally, in logical connection with the previous arguments, I argue that financial stability is a systemic public concern and matches with the characteristics of a public good that implies a specific system-consistent organization and supervision. Therefore its production, reproduction and regulation must rest on non-market-led rules and mechanisms to be provided and implemented under public control. [START_REF] Veblen | The Vested Interests and the State of the Industrial Arts[END_REF] studies the evolution of capitalism from the 18 th century till the 1920s and notes that the economy switched from a small-sized units competition to a huge investment bankers-dominated large corporations. Veblen states that in the eighteenth century, along with certain principles (equal opportunity/self-determination/self-help) that were based on the rule of "Live and Let Live", the ownership of property became a founding social rule. However, things changed as capitalism moved toward oligopolistic/monopolistic/transnational corporations with large control power over society such that the network of ownership over holdings controls the conditions of life for the common man. More accurately, Veblen (1921: 34) defines the entrepreneur as an investment banker in this "new capitalism" -whose social characteristics changed by the 19 th century with the expansion of the capital2 : "progressively the cares of business management grew larger and more exacting, as the scale of things in business grew larger, and so the directive head of any such business concern came progressively to give his attention more and more exclusively to the "financial end". At the same time and driven by the same considerations the businesslike management of industry has progressively been shifting to the footing of corporation finance", such that "corporation finance on a sufficiently large scale had come to be the controlling factor in industry" (Ibid: 38) and "the discretionary control of industrial production is shifting still farther over to the side of finance" (Ibid.: 41).

The rise of finance and vested interests

Parallel to this evolution, the close structural linkages between banks and industrial activities, mainly relying on financial efficiency criteria 3 , were built up and gave a dominant position to financial actors in the economic decision process: "no large move in the field of corporation finance can be made without the advice and consent of those large funded interests that are in a position to act as investment bankers; nor does any large enterprise in corporation business ever escape from the continued control of the investment bankers in any of its larger transactions; nor can any corporate enterprise of the larger sort now continue to do business except on terms which will yield something appreciable in the way of income to the investment bankers, whose continued support is necessary to its success" (Veblen, 1921: 47). 4 This new order generates its own vested interests. Indeed, Veblen (1919: 160-161) states that under the "new order", social structures were modified and resulted in a new separation between two classes, the vested interests and the common man: "Invested wealth in large holdings controls the country's industrial system (…).

So that the population of these civilised countries now falls into two main classes: those who own wealth invested in large holdings and who thereby control the conditions of life for the rest 5 ; and those who do not own wealth in sufficiently large holdings, and whose conditions of life are therefore controlled by these others." [START_REF] Veblen | The Vested Interests and the State of the Industrial Arts[END_REF] then argues that the vested interests are the defenders of the status quo since they draw their interests from the continuance of the existing economic relations 6 . However, Veblen maintains that the financial captains of industry -who have to do with the higgling of the market and not with productive efficiency 7 -have not been proving their industrial competence 8 . The proponents of financial liberalization argue that government regulatory restrictions-freed markets would work at optimum since the financial repression is removed and the competition gains ground and pushes market actors toward efficient strategies. So those approaches ignore that the liberalization process usually leads to financialization such that the main decision criteria then rest on higher and quick financial profitability of operations without any real long-period engagement of market makers. In such an environment, the incentives are perverted, and vested interests are directed toward short-sighted speculative strategies. Though rational from a microeconomic perspective (individual financial gain efficiency) those strategies prove to be inefficient and system destructive from a macro-stability 4 Veblen (1921: 48-50) argues that the power of investment bankers over the real economy also determines the traffic in credit and then the level of economic activity and the direction of industrial evolution according to the objective of the largest net return on investments. 5 Those are the vested interests, the "kept classes", whose income "depends on the good will of those controlling vested interests whose power rests on the ownership of large invested wealth" (Veblen, 1919: 164). 6 "they are staunch defenders of that established order of law and custom which secures the great vested interests in power and insures the free income of the kept classes" (Veblen, 1919: 164). 7 Veblen (1919: 89). 8 Veblen (1921: 41).

perspective. An illustration of such a perverse evolution with respect to the banking behavior in markets is provided by the prevalent incentives in the last decades that made regulatory arbitrage and speculation the most profitable market strategy leading up to the 2007-2008 crisis. 9

Structural characteristics of a monetary economy and regulatory weaknesses

In his numerous works Veblen points to the peculiar nature of money and credit in capitalist development 10 without supplying a detailed analysis of financial systems.

Several studies [START_REF] Raines | Veblenian stock markets and the efficient market hypothesis[END_REF][START_REF] Toporowski | Theories of Financial Disturbance: An Examination of Critical Theories of Finance from Adam Smith to the Present Day[END_REF][START_REF] Wray | The Financial Crisis Viewed from the Perspective of the "Social Costs" Theory[END_REF][START_REF] Argitis | Veblenian and Minskian financial markets[END_REF]Forges Davanzati and Pacella, 2014, among others) state that those works could give relevant insights into how the capitalist monetary/financial system develops and changes social structures. In line with these studies and to provide further robust foundations to the analysis of financialized capitalism, I now focus on some monetary/financial characteristics of the economy. 11 In a private individuals' decisions-based market economy, the monetary system -as a social coordination process-allows individuals to undertake decentralized actions. It basically rests on two constraints: financing of private plans on debts (credit-allocation) and repayment of debts (establishment of monetary equivalence in individual balance sheets). 12 In this framework, the monetary/financial system plays a vital role since banks/financial institutions fund real/financial activities and thus directly affect the path of capital accumulation. This gives money and related financial relations a specific social/societal nature making them ambivalent and transversal. 9 Acharya and Richardson (2009, 206) document that: "In the period leading up to the crisis, bankers were increasingly paid through short-term cash bonuses based on volume and on marked-to market profits, rather than on the long-term profitability of their "bets." Thus, they had no incentive to discount for the liquidity risk of asset backed securities if their bets were wrong and nobody wanted to buy these securities. Nor was there an incentive to discount for the "maturity mismatch" inherent in structured investment vehicles-which funded long-term assets through short-term debt that had to be rolled over frequently, generally overnight. Nor, apparently, did their managers assess the true skills of those who were generating these large "profits." 10 See especially Veblen, 1915, Chapter V;Veblen, 1919, Chapter V;[START_REF] Veblen | The Engineers and the Price System[END_REF], Chapter II and Chapter III. Some parallels might also be drawn between this approach and Polanyi's "fictitious commodities" (money, labor and land). See Ülgen (2016) for further developments. 11 This is the Monetary Approach which rests on numerous analytic developments of Evolutionist, Institutionalist, Post-Keynesian and (some) Marxian approaches within the framework of "endogenous money" models. See Ülgen (2013). 12 From this perspective, in market economies money is a threefold social rule: a nominal unit of account, a minting process, and a clearing/settling procedure. Transactions are then decentralized and do not require any central clearing à la Debreu.

Ambivalent because the creation(issuance)-circulation-annulment(repayment) process of money/credit/debt and related financial assets/liabilities are generated through private profit-seeking plans which nevertheless require public support to receive institutional-social recognition. More precisely, money is endogenously generated through the private debt-financing and circulation process. But some super-individual common rules are required to give this twofold constraint-based decentralized process its social aspect and society-wide validity within a given payment system (Ülgen, 2013).

Therefore, monetary/financial relations rely on private market decisions as well as on extra-market public rules, and develop through a permanent tension between those two sides (Ülgen, 2014).

Transversal because monetary/financial relations involve every individual, directly (if enrolled within market activities) or indirectly (if affected by others' activities) within market operations since the economy operates on money-creation-debt-repayment relations. Although related to private decentralized decisions, financial relations have societal consequences and no economic agent, living within capitalist society, can avoid those consequences. Those who initiate and control monetary/financial operations control the faith of the economy. This is capitalism and the "barons" of such a society are financiers and their (economic-political-social) relatives.

Given this crucial role of the financial system, the evolution of institutions and subsequent regulatory schemas such as the scope of public supervision, private rating agencies and banks' internal ratings based models, among others, must be considered relatively to the problem of sustainable organization of economies and systemic stability. This latter continuously requires presence, supervision and intervention of public institutions (central bank, public agencies).

Therefore, three remarks can be stated to argue that market-dependent self-regulation (micro-prudential regulation) is not a relevant way of organizing sound financial systems. First, self-regulation consists of improving the safety of individual operations and relies on private information and profit/rent-seeking rationality while information and actions required to ensure society-wide stability are beyond the reach of individuals. The aim and the relevant scope of the former is not the same than the prerequisites of the latter. Second, in self-regulation, the necessary separation between the regulator and the regulatee does not hold. This then provokes conflicts of interests since the external objectivity of the regulator loses ground in favor of the interests of the regulatee. The assertion consisting of the possible confusion between the judge and the judged is not consistent with financial stability as a macro-economic concern. Third, such a confusion does suffer the fallacy of composition since micro-rational behavior does not obviously generate macro-rational outcomes. Even though one could assert, on the basis of efficient markets hypothesis, that private individuals do behave in a rational way searching for improving their own situation, such a behavior does not result in an optimal situation at society's level and may harm society by weakening the soundness of financial markets.

The growth process of the last decades mainly rested on speculative attraction that gained ground through enlarged vested interests as it included the ordinary and lowincome people involved into rent-seeking speculative operations through popularized financial investment possibilities or housing bubble-related mortgage engagements. This relied on loose market-friendly regulation that supplied to the banking/financial system (very) bad incentives in their operations of repackaging mortgages into mortgage-backed securities though offering huge rent areas. This allowed them to reduce the amount of capital they held against securitized mortgages (that remained on their balance sheets) if those assets were AAA-rated [START_REF] Acharya | Causes of Financial Crisis[END_REF]. This came to concentrate the risk of mortgage defaults in the banks rendering them excessively vulnerable against market turmoil. When the housing bubble popped, the money market dried up and the entire banking system along with the real sector became insolvent causing the economy to falter. Consequently, in the wake of the 2007-2008 crisis, self-regulation-led financialized economy proved to be an unstable accumulation regime 13 whose systemic outcome was an economic/social catastrophe with increasing poverty and inequalities. 14 13 Although beyond the scope of this article, it is worth noting that the 2007-2008 turmoil pointed out the crucial role of institutional framework with regard to financial stability but also the global nature of financial stability in light of increasing number of interconnected transnational financial institutions and banks around the world. Financial stability concerns must then be dealt with at a global systemic level and without any private-interests-related mechanisms. 14 It is worth noting that financialization generates bad incentives for market actors and puts them up to prefer short-term speculative rent-seeking activities at the expense of the real economy, resulting not in growing income and sustainable demand, but in growing inequalities. Indeed, evolution of property share and the Gini ratio over 1950-2010 points to a worsening of the inequalities from the 1980s. Giovannoni shows that from the late 1970s, the Gini ratio for families and the property share with the 1% share in the US economy grow together to reach high levels, up to 0.46 for the former and to 40% for the latter:

In the face of such an experience, some urgent questions are: how to reorganize financial regulation to ensure financial stability and what could a possible relevant financial macro-regulation, alternative to market-dependent self-regulation, be?

Implications for financial stability

In the aftermath of the 2007-2008 "financialization crisis", numerous scholars and analysts did use Minsky's ideas on the financial fragility of a capitalist economy, and called the crisis "a Minsky moment" with emphasis put on system-wide securitization and speculation processes. However, as the monograph published by the Levy Economics Institute of Bard College (2011: 5) documents, in response to this crisis, the crucial discussion of the hypotheses and results of Minsky's work with respect to the endogenous fragilities of capitalism and to necessary reregulation framework, alternative to financial liberalism, has virtually disappeared and "replaced by more pragmatic lobbyists seeking to defend vested interests". So going beyond the popularized slogans such as "Minsky moment" and "exuberant finance" requires a rigorous analysis of the systemic nature of financial stability.

From this perspective, [START_REF] Claessens | An Overview of Macroprudential Policy Tools[END_REF] notes that macroprudential policies (caps on loan to value ratios, limits on credit growth and other balance sheets restrictions, countercyclical capital and reserve requirements, etc.) have become part of the policy paradigm. Although much remains to be studied -including tools as well as the relevant institutional design-macroprudential regulation is motivated by market failures and externalities. In this vein, a specific institutional feature of capitalism might be designed through the assumption that financial stability is a public good which should be produced, managed and supervised by public authorities in order to direct markets toward common-welfare objectives and system-consistent strategies. As a public good, financial stability is needed and used by everyone without being excludable (its use by some individuals cannot prevent the others from using it) and rival (its use by some individuals cannot reduce its availability for the others). Moreover financial stability is always "consumed" simultaneously by everyone as it makes the continuous working of the whole economy possible. Since every economic agent needs it but nobody could produce it at the individual basis, the provision of financial stability cannot be ensured "Unbalanced economic growth is mostly manifested through the rise of top incomes, with rising property shares on one side and increasing inequality on the flip-side." [START_REF] Giovannoni | What Do We Know About the Labor Share and the Profit Share? Part II: Empirical Studies[END_REF]. by local, separate private decisions and actions, and needs to be organized and implemented by a common/collective agency. It is worth noting, however, that asymmetrically, financial instability as a bad can be provided by decentralized individual decisions and actions when those latter have a systemic importance (such as the "toobig-to-fail banks and financial institutions). Indeed, financial operations involve the whole society within the payments network (they are transversal) and their sustainability (financial stability) is a prerequisite for all economic relations in a market economy. Therefore, financial stability cannot be regarded only at a micro-safety level such as the individual insurance schemes. It matters for the entire economy while its production remains beyond the reach of individual micro-prudential frameworks.

Financial stability is related to the stability of the monetary system which is the set of rules and practices that govern the way(s) debts could be created, used as money within the economy and finally repaid/honored in the aim of ensuring the viability of economic relations. When the system works in a smooth and stable way, all individuals get gain from economic operations, but when it breaks down, they are unable to individually sustain social and economic relations. All have an interest in regulatory reforms that would improve the system for the public benefit but not many people care for, and even fewer are prepared to pay for [START_REF] Camdessus | International Financial and Monetary Stability: A Global Public Good?[END_REF]. To ensure a sustainable provision of financial stability, reframing of finance and financial activities in markets is a necessary step. One must then consider finance in a hybrid/ambivalent way (as money is): a public good to be organized and managed by the public power and agencies, and a private means of undertaking economic activities. This kind of ambivalence is inherent to capitalism and calls for the public will to be managed in a coherent way.

Conclusion

Almost a century after its publication, the work of Thorstein Veblen is a relevant source to dissect the evolution of capitalism, particularly in its financialized version. Drawing liberally on numerous works of Veblen, this article analyzed the characteristics of the financialization process of capitalism and its consequences for financial regulation and stability. As Veblen states in his long-term economic and social analysis of capitalism, the expansion of credit relations and the ascendancy of financial relations and vested interests over society characterize the modern business.

In this line, I developed some core characteristics of the capitalist monetary/financial system focusing on the ambivalence and transversality of monetary rules and financial relations, and then argued that liberal market-dependent self-regulation was not a relevant way of organizing sound financial systems. Three arguments were provided to support such an assertion: first, the aim and scope of self-regulation are not consistent with the prerequisites of society-wide macro stability; second, self-regulation provokes conflicts of interests, weakens the capacity of the regulatory system to deal with stability concerns and then falters the social reproduction schema; and third, micro-prudential self-regulation suffers the fallacy of composition such that micro-rational behavior does not lead to an optimal macro situation since it contributes to weaken the soundness of financial markets.

Provided that appropriate regulation and supervision of financial activities at the global level is required for a viable and sustainable (global) working of the economy, the article pointed to a core question: how to reorganize financial regulation to ensure financial stability and what could a possible relevant financial macro-regulation, alternative to market-dependent self-regulation, be?

A judicious angle of analysis can be given by the system-wide public character of money and related financial operations. In this aim, the direction suggested is a specific approach to financial stability and required macroprudential regulation. This approach maintains that stability must be considered at a systemic level as a public good that should be produced (organized), managed and supervised by a specific public structure. This latter that must be designed and framed as a neutral "extra-market" framework according to collectively and publicly implemented rules and constraints. It must seek systemic coherence and be able to direct financial activities through collective objectives. Therefore it must remain out of market relations and incentives.

[START_REF] Veblen | The Engineers and the Price System[END_REF]

31) states that: "This captain of industry, typified by the corporation financier, and latterly by the investment banker, is one of the institutions that go to make up the new order of things…".3 That is, the objective of a higher net return on investment.


Guillaume Aupy

Ana Gainaru

Valentin Honoré

Padma Raghavan

Yves Robert

Hongyang Sun

Reservation Strategies for Stochastic Jobs (Extended Version)

Keywords: scheduling, stochastic cost, computing platform, sequence of requests, neuroscience applications ordonnancement, coût stochastic, plateformes de calcul, séquences de réservations, applications de neurosciences

In this paper, we are interested in scheduling stochastic jobs on a reservation-based platform. Specifically, we consider jobs whose execution time follows a known probability distribution. The platform is reservation-based, meaning that the user has to request fixed-length time slots. The cost then depends on both (i) the request duration (pay for what you ask); and (ii) the actual execution time of the job (pay for what you use). A reservation strategy determines a sequence of increasing-length reservations, which are paid for until one of them allows the job to successfully complete. The goal is to minimize the total expected cost of the strategy. We provide some properties of the optimal solution, which we characterize up to the length of the first reservation. We then design several heuristics based on various approaches, including a brute-force search of the first reservation length while relying on the characterization of the optimal strategy, as well as the discretization of the target continuous probability distribution together with an optimal dynamic programming algorithm for the discrete distribution. We evaluate these heuristics using two different platform models and cost functions: The first one targets a cloud-oriented platform (e.g., Amazon AWS) using jobs that follow a large number of usual probability distributions (e.g., Uniform, Exponential, LogNormal, Weibull, Beta), and the second one is based on interpolating traces from a real neuroscience application executed on an HPC platform. An extensive set of simulation results show the effectiveness of the proposed reservation-based approaches for scheduling stochastic jobs.

Introduction

Scheduling a job onto a computing platform typically involves making a reservation of the required resources, say of duration t 1 seconds, and running the job on the platform until either the job has successfully completed, or the reservation time has elapsed, whichever comes first.

While in some instances the exact duration of the job may be known, in many other cases it is not known a priori (see, for examples, two neuroscience applications shown in Fig. 1, whose execution times have been characterized to exhibit input-dependent yet unpredictable behavior). In the latter case, the user has to guess a good value for t 1 . Indeed, if the job does not complete successfully within these t 1 seconds, the user has to resubmit the job, this time requiring a longer reservation, say of length t 2 > t 1 . If the job still does not complete successfully within t 2 seconds, the user has to try again, using a reservation of length t 3 > t 2 , and so on until the job would succeed eventually. The cost to the user is then the cost associated with all the reservations that were necessary to the successful completion of the job.

A reservation strategy could well depend on the context, the type of jobs and the platform. As an example, the MASI Lab [START_REF]Medical-image Analysis and Statistical Interpretation (MASI) Lab[END_REF] at Vanderbilt takes the average execution time from the last few instances of a neuroscience job to determine the first reservation time for its next instance. If the reservation is not enough, a standard practice is to resubmit the job using between 1.5x and 2x the requested time in the last failed run, effectively doubling the reservation time. As another example, on HPC platforms, some users tend to reserve a walltime that "guarantees" execution success (say up to the 99 th execution quantile). If this is not enough, they can ask for the 99 th execution quantile of the remaining possibilities, etc.

(a) Functional MRI quality assurance (fMRIQA) [START_REF] Friedman | Report on a multicenter fMRI quality assurance protocol[END_REF] (b) Voxel-based morphometry quality assurance (VB-MQA) [START_REF] Mechelli | Voxel-based morphometry of the human brain: methods and applications[END_REF] Figure 1: Traces of over 5000 runs (historgrams in purple) from July 2013 to October 2016 of two neuroscience applications from the Vanderbilt's medical imaging database [START_REF] Harrigan | Vanderbilt university institute of imaging science center for computational imaging XNAT: A multimodal data archive and processing environment[END_REF]. We fit the data to LogNormal distributions (dotted lines in orange) with means and standard deviations shown on top.

This reservation-based approach is agnostic of the type of the job (sequential or parallel; single task or workflow) and of the nature of the required computing resources (processors of a large supercomputer, virtual machines on a cloud platform, etc.). The user just needs to make good guesses for the values of successive reservation durations, hoping to minimize the associated cumulated cost. Here, we refer to cost as a generic metric. It could be paid either in terms of budget (e.g., a monetary amount as a function of what is requested and/or used in a cloud Inria service), or in terms of time (e.g., the waiting time of the job in an HPC queue that depends on the requested runtime as shown in Fig. 2).

(a) Jobs that requested 204 procs.

(b) Jobs that requested 409 procs.

Figure 2: Average wait times of the jobs run on the same number of processors (204 and 409) as a function of the requested runtimes (data from [START_REF] Tang | Reducing fragmentation on torusconnected supercomputers[END_REF]). All jobs are clustered into 20 groups, each with similar requested runtimes. Each point (in blue) shows the average wait time of all jobs in a group and the dotted lines (in orange) represent affine functions that fit the data.

The cost is usually proportional to the reservation length, with a possible initial and fixed value (start-up overhead). One example is the Reserved Instance model available on Amazon AWS [START_REF]AWS pricing information[END_REF], which is up to 75% cheaper than the flexible On-Demand model that does not require advanced reservations. We also investigate scenarios where an additional cost is paid in proportion to the actual execution time, again with a possible start-up overhead. This latter scenario is relevant when submitting jobs to large supercomputing platforms, where each user requests a set of resources for a given number of hours, but only pays for the hours actually spent; however, the assigned waiting queue, and hence the job's waiting time, both depend upon the number of hours asked for in the request.

Altogether, the cost function 1 for a job with a reservation of length t 1 and an actual execution duration of length t can be expressed as:

αt 1 + β min(t 1 , t) + γ (1)
where α, β and γ are constant parameters that depend on the platform and the cost model. Again, if t > t 1 , another reservation should be made and paid for. Although we do not know the exact execution time of the job to be scheduled, we do not schedule completely in the dark. Instead, we assume that there are many jobs of similar type and that their execution times obey the same (known) probability distribution (e.g., see Fig. 1). Each job is deterministic, meaning that a second execution of the same job will last exactly as long as the first one. However, the exact execution time of a given job is not known until that job has successfully completed. Our only assumption is that job execution times are randomly and uniformly sampled from a target probability distribution.

While the core of the theoretical results of this paper are valid for general continuous probability distributions, we focus on the usual distributions for the evaluation. In particular, we consider Uniform, Beta and Bounded Pareto distributions if the execution times are upper-bounded, i.e., they belong to some interval [a, b]; and we consider Exponential, Weibull, LogNormal and a few others if there is no upper bound for the execution times (see Section 5 for details). Note that the LogNormal distribution has been advocated to model file sizes [START_REF] Feitelson | Workload modeling for computer systems performance evaluation[END_REF], and we assume that job durations could naturally obey this distribution too. Note that we only consider distributions whose support is included in [0, ∞), because execution times must have positive values. This precludes the use of Normal distribution, for instance.

This paper aims at proposing effective strategies to the following reservation problem: given a probability distribution, determine a (possibly infinite) sequence of reservations S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) such that the expected cost to execute a job, whose execution time is randomly and uniformly sampled from the distribution, is minimized. Of course, any reservation sequence induces a greedy scheduling algorithm: for any given job, make (and pay for) a reservation of length t 1 , then a reservation of length t 2 if the job has not succeeded (meaning its execution time t was greater than t 1 ), and so forth until success. The natural objective is to minimize the average cost of this algorithm over all possible job durations, hence the quest for a reservation sequence whose expected cost is minimal.

From a theoretical perspective, it is not clear that there always exists a reservation sequence with finite expected cost. However, we show that it is true for any continuous distribution with finite expectation and variance, which is the case for all the distributions considered in this work.

The main contributions of this work are the following:

• The characterization of an optimal reservation sequence up to the value of its first reservation duration t 1 . While we do not know how to compute t 1 analytically, we provide an upper bound that allows us to limit the range of a numerical search for its value;

• The design of several heuristics based on various approaches: one explores a brute-force search for t 1 while relying on the optimal characterization mentioned above; one discretizes the target continuous distribution and uses an optimal dynamic programming algorithm for the discrete distribution; and some rely on standard measures (e.g., mean, variance, quantiles) of the distribution.

• An extensive set of simulation results under two different platform models and cost functions that show the effectiveness of the proposed strategies. The first one targets a cloudoriented platform using jobs that follow a large number of usual distributions and the second one is based on interpolating traces from a real neuroscience application executed on an HPC platform.

The rest of the paper is organized as follows. Section 2 introduces the framework and main notations. Section 3 discusses the properties of the optimal solution. We propose several heuristics in Section 4, and evaluate their performance under two platform models in Section 5. Section 6 is dedicated to related work. Finally, we provide concluding remarks and hints for future work in Section 7.

Framework

In this section, we introduce some notations and formally define the optimization problem.

Inria

Stochastic jobs

We consider stochastic jobs whose execution times are unknown but (i) deterministic, so that two successive executions of the same job will have the same duration; and (ii) randomly and uniformly sampled from a given probability distribution law D, whose density function is f and cumulative distribution function (CDF) is F . The probability distribution is assumed to be nonnegative, since we model execution times, and is defined either on a finite support [a, b], where 0 ≤ a < b, or on an infinite support [a, ∞) where 0 ≤ a. Hence, the execution time of a job is a random variable X, and

P(X ≤ T ) = F (T ) = T a f (t)dt
For notational convenience, we sometimes extend the domain of f outside the support of D by letting f (t) = 0 for t ∈ [0, a].

Cost model

To execute a job, the user makes a series of reservations, until the job successfully executes within the length of the last reservation. For a reservation of length t 1 , and for an actual duration t of the job, the cost is αt 1 + β min(t 1 , t) + γ, as stated in Equation ( 1), where α > 0, β ≥ 0 and γ ≥ 0. If t > t 1 , another reservation should be paid for. Hence, the user needs to make a (possibly infinite) sequence of reservations S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ), where:

1. t i < t i+1 for all i ≥ 1. Indeed, because jobs are deterministic, it is redundant to have a duration in the sequence that is not strictly larger than the previous one, hence that duration can be removed from the sequence;

2. all possible execution times of the job are indeed smaller than or equal to some t i in the sequence. This simply means that the sequence must tend to infinity if job execution times are not upper-bounded.

Throughout the paper, we assume that both properties hold when speaking of a reservation sequence. For notational convenience, we define t 0 = 0, in order to simplify summations. Now, for a sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ), and for a job execution time t, the cost is

C(k, t) = k-1 i=1 (αt i + βt i + γ) + αt k + βt + γ ( 2
)
where k is the smallest index in the sequence such that t ≤ t k (or equivalently, t k-1 < t ≤ t k ; recall that t 0 = 0).

Objective

The goal is to find a scheduling strategy, i.e., a sequence of increasing reservation durations, that minimizes the cost in expectation. Formally, the expected cost for a sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) can be written as:

E(S) = ∞ k=1 t k t k-1 C(k, t)f (t)dt (3)
Indeed, when t k-1 < t ≤ t k , the cost is C(k, t), which we weight with the corresponding probability.

Here are two examples:

• Uniform(a, b): for a uniform distribution over the interval [a, b] where 0 < a < b, we have f (t) = 1 b-a if a ≤ t ≤ b, and f (t) = 0 otherwise. Given a finite sequence S = ( a+b 2 , b), the expected cost is

E(S) = a+b 2 a (α a + b 2 + βt + γ) 1 b -a dt + b a+b 2 (α a + b 2 + β a + b 2 + γ) + (αb + βt + γ) 1 b -a dt
The first term is for values of t that are in [a, a+b 2 ] and the second term is for larger values of t in [ a+b 2 , b]. For the latter term, we pay a constant cost

α a + b 2 + β a + b 2 + γ
for the first reservation, which was unsuccessful, and then a cost that depends upon the value of t for the second reservation if β = 0.

• Exp(λ): for an exponential distribution with rate λ and support in [0, ∞), we have f (t) = λe -λt for all t ≥ 0. Given an infinite and unbounded sequence S = ( 1 λ , 2 λ , . . . , i λ , i+1 λ , . . . ), the expected cost is

E(S) = ∞ k=1 k λ k-1 λ k-1 i=1 (α i λ + β i λ + γ) + α k λ + βt + γ λe -λt dt Again, when t ∈ [ k-1 λ , k λ ],
we pay a fixed cost for the k -1 first reservations, and a possibly variable cost for the k-th reservation. Looking at the expression of E(S) above, we easily see that the given sequence S has a finite expected cost E(S). In fact, there are many sequences with finite expected cost, such as those defined by t i = ui + v for i ≥ 1, where u and v are positive constants.

We are now ready to state the optimization problem: Definition 1 (Stochastic). Given a probability distribution (with CDF F ) for the execution times of stochastic jobs, and given a cost function given by Equation (1) (with parameters α, β and γ), find a reservation sequence S with minimal expected cost E(S) as given in Equation (3).

We further define ReservationOnly to be the instance of Stochastic where the cost is a linear function of the reservation length only, i.e., when β = γ = 0. For ReservationOnly, we can further consider α = 1 without loss of generality. For instance, such costs are incurred when making reservations of resources to schedule jobs on some cloud platforms, with hourly or daily rates.

Throughout the paper, we focus on the usual probability distributions, hence we assume that the density function f and the CDF F of D are smooth (infinitely differentiable), and that D has finite expectation.

Characterizing the optimal solution

In this section, we establish key properties of an optimal solution in the general setting.

Inria

Cost function

We start by establishing a simpler expression for the cost function of Stochastic.

Theorem 1. Given a sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ), the cost function given by Equation (3) (with parameters α, β and γ) can be rewritten as (with t 0 = 0):

E(S) = β • E[X]+ ∞ i=0 (αt i+1 +βt i +γ) P(X ≥ t i ) (4)
Proof. We first expand Equation (3) as follows:

E(S) = ∞ k=1 t k t k-1 k i=1 (αt i +γ)+ k-1 i=1 βt i +βt f (t)dt (5)
We compute the three terms on the right-hand side separately. By defining t 0 = 0, the first term can be expressed as:

∞ k=1 t k t k-1 k i=1 (αt i + γ) f (t)dt = ∞ k=1 k i=1 (αt i + γ) t k t k-1 f (t)dt = ∞ k=1 k i=1 (αt i + γ) P(X ∈ [t k-1 , t k ]) = ∞ i=1 ∞ k=i (αt i + γ) P(X ∈ [t k-1 , t k ]) = ∞ i=1 (αt i + γ) P(X ≥ t i-1 )
Similarly, we obtain the second term:

∞ k=1 t k t k-1 k-1 i=1 βt i f (t)dt = ∞ i=1 βt i P(X ≥ t i )
and the third term:

∞ k=1 t k t k-1 βtf (t)dt = β • E[X]
Plugging these three terms back into Equation ( 5), we get the desired expression for the cost function as given by Equation (4).

Upper bound on t o 1 and finite expected cost

In this section, we extract an upper bound for the first request t o 1 of an optimal sequence S o to Stochastic, which allows us to show that the expected cost E(S o ) is upper bounded too, and hence finite. This result holds in a general setting, namely, for any distribution D such that E(X 2 ) < ∞.

Obviously, if the distribution's support is upper bounded, such as for Uniform(a, b), a solution is to choose that upper bound for t o 1 (e.g., t o 1 ≤ b for Uniform(a, b)). Hence, we focus on distributions with infinite support [a, ∞) and aim at restricting the search for an optimal t o 1 to a bounded interval [a, A 1 ] for some A 1 . We derive the following result.

A 1 = E[X]+1+ α+β 2α (E[X 2 ]-a 2 )+ α+β +γ α (E[X]-a) (6)
A 2 = β • E(X) + αA 1 + γ (7)
Proof. We consider the sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) with t i = a + i for i ≥ 1 (and t 0 = 0), and compute:

E(S) -β • E[X] = ∞ i=0 (αt i+1 + βt i + γ)P(X ≥ t i ) = ∞ i=0 (α(a + i + 1) + β(a + i) + γ)P(X ≥ a + i) = α(a + 1) + γ + ∞ i=1 (α + β)(a + i)P(X ≥ a + i) + (α + γ) ∞ i=1 P(X ≥ a + i) = α(a + 1) + γ + (α + β) ∞ i=1 a+i a+i-1 (a + i)P(X ≥ a + i)dt + (α + γ) ∞ i=1 a+i a+i-1 P(X ≥ a + i)dt
Note that for all t ∈ [a + i -1, a + i], we have both

a + i ≤ t + 1 and P(X ≥ a + i) ≤ P(X ≥ t) Thus, (a + i)P(X ≥ a + i) ≤ (t + 1)P(X ≥ t)
Hence, we can write:

E(S) -β • E[X] ≤ α(a + 1) + γ + (α + β) ∞ i=1 a+i a+i-1 (t + 1)P(X ≥ t)dt + (α + γ) ∞ i=1 a+i a+i-1 P(X ≥ t)dt = α(a + 1) + γ + (α + β) ∞ a (t + 1)P(X ≥ t)dt + (α + γ) ∞ a P(X ≥ t)dt ≤ α(a + 1) + γ + (α + β) ∞ a t • P(X ≥ t)dt + (2α + β + γ) ∞ a P(X ≥ t)dt
For the last inequality, we have split

∞ a (t + 1)P(X ≥ t)dt Inria into ∞ a tP(X ≥ t)dt and ∞ a P(X ≥ t)dt
Extending the support of D to [0, ∞) by letting f (t) = 0 for 0 ≤ t ≤ a, and hence P(X ≥ t) = 1 for 0 ≤ t ≤ a, we have the following property for any integer p ≥ 1:

∞ 0 t p-1 • P(X ≥ t)dt = ∞ t=0 t p-1 ∞ x=t f (x)dxdt = ∞ x=0 f (x) x t=0 t p-1 dtdx = ∞ 0 x p p f (x)dx = E[X p ] p
Hence, using p = 1, we have:

∞ a P(X ≥ t)dt = ∞ 0 P(X ≥ t)dt- a 0 P(X ≥ t)dt = E[X]-a
and using p = 2, we get:

∞ a t • P(X ≥ t)dt = ∞ 0 t • P(X ≥ t)dt - a 0 t • P(X ≥ t)dt = E[X 2 ] -a 2 2
Altogether, we derive that:

E(S) ≤ β • E[X] + αA 1 + γ (8)
where A 1 is given by Equation [START_REF] Canon | Evaluation and optimization of the robustness of dag schedules in heterogeneous environments[END_REF]. From Equation (4), the expected cost of any sequence S satisfies E(S) ≥ β • E[X] + αt 1 + γ (cost of expected execution time and cost of first request). Hence, necessarily in an optimal sequence, the first reservation t o 1 satisfies to t o 1 ≤ A 1 . Thus, Equation ( 6) gives the desired bound on t o 1 .

Properties of optimal sequences

We now derive a recurrence relation between the successive requests in the optimal sequence for Stochastic.

Theorem 3. Let S o = (t o i ) i≥1 denote an optimal sequence for Stochastic. For all i ≥ 1, if t o i
is not the last element of the sequence and F (t o i ) = 1, we have the following property:

αt o i+1 + βt o i + γ = α 1 -F (t o i-1 ) f (t o i ) + β 1 -F (t o i ) f (t o i ) (9)

RR n°9211

Proof. We fix an index j ≥ 1 such that F (t o j ) = 1 and consider the expected cost when we replace t o j by an arbitrary value t ∈ [t o j-1 , t o j+1 ]. This amounts to using the sequence 4), is the following:

S o j (t) = (t o 1 , t o 2 , • • • , t o j-1 , t, t o j+1 , • • • ) whose expected cost, according to Equation (
E(S o j (t)) = β • E[X] + i =j-1,j (αt o i+1 + βt o i + γ)P(X ≥ t o i ) + (αt + βt o j-1 + γ)P(X ≥ t o j-1 ) + (αt o j+1 + βt + γ)P(X ≥ t)
which we can rewrite as: = 0. This gives:

E(S o j (t)) = C j + αt(1 -F (t o j-1 )) + (αt o j+1 + βt + γ)(1 -F (t)) where C j is some constant independent of t. By definition, the minimum of E(S o j (t)) on [t o j-1 ,
α(1 -F (t o j-1 ))+β(1 -F (t o j )) -(αt o j+1 +βt o j +γ)f (t o j ) = 0 (10)
To get the final result, it remains to show that f (t o j ) = 0. Otherwise, we would get from Equation ( 10) that:

α(1 -F (t o j-1 )) + β(1 -F (t o j )) = 0 which implies that: F (t o j-1 ) = 1 because α > 0 (and β(1 -F (t o j )) ≥ 0). But then, F (t o j ) ≥ F (t o j-1
) = 1 which contradicts the initial assumption. Hence, f (t o j ) = 0, and rewriting Equation ( 10) directly leads to Equation [START_REF] Dong | Resource load based stochastic DAGs scheduling mechanism for Grid environment[END_REF].

Note that the condition F (t o i ) = 1 in Theorem 3 applies to distributions with bounded support, such as Uniform(a, b), where F (b) = 1. For the usual distributions with unbounded support, such as Exp(λ), we have F (t) < 1 for all t ∈ [0, ∞) and an optimal sequence must be infinite. In essence, Theorem 3 suggests that an optimal sequence is characterized solely by its first value t o 1 : Proposition 1. For a smooth distribution with unbounded support, solving Stochastic reduces to finding

t o 1 that minimizes ∞ i=0 (αt i+1 +βt i +γ) P(X ≥ t i )
where t o 0 = 0, and for all i ≥ 2,

t o i = 1 -F (t o i-2 ) f (t o i-1 ) + β α 1 -F (t o i-1 ) f (t o i-1 ) -t o i-1 - γ α (11)
For a smooth distribution with bounded support, the recurrence in Equation (11) still holds but the optimal sequence stops as soon as it reaches

t o i with F (t o i ) = 1.
Inria Proposition 1 provides an optimal algorithm for general smooth distributions, up to the determination of t o 1 . However, computing the optimal t o 1 , remains a difficult problem, except for simple distributions such as Uniform(a, b) (see Section 3.4).

Uniform distributions

In this section, we discuss the optimal strategy for a uniform distribution Uniform(a, b), where 0 < a < b. Intuitively, one could try and make a first reservation of duration, say, t 1 = a+b 2 , and then a second reservation of duration t 2 = b. However, we show that the best approach is to make a single reservation of duration t 1 = b, for any value of the parameters α, β and γ: Proof. We proceed by contradiction and assume there is an optimal sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) for Stochastic where t 1 < b. Necessarily, this sequence contains more elements: either it is finite of length n and then necessarily t n = b (hence n ≥ 2): otherwise t n < b and E(S) = ∞ because the interval [t n , b] has non-zero measure; or it is infinite and then the conclusion holds (note that in that case, lim i→∞ t i = b: otherwise the strictly increasing sequence (t i ) i≥1 converges to some value b < b and E(S) = ∞ because the interval [b , b] has non-zero measure). Altogether, t 2 always exists and t 1 < t 2 ≤ b.

We can compute E(S) by distinguishing whether the job execution time t satisfies:

(i) a ≤ t ≤ t 1 ; or (ii) t 1 ≤ t ≤ t 2 ; or (iii) t 2 ≤ t ≤ b. Note that the last case (iii) may disappear if t 2 = b.
We obtain:

E(S) = t 1 -a b -a (αt 1 + β a + t 1 2 + γ) + t 2 -t 1 b -a (αt 1 + βt 1 + γ + αt 2 + β t 1 + t 2 2 + γ) + b -t 2 b -a (αt 1 + βt 1 + γ + αt 2 + βt 1 + γ + Z)
In the equation above, we have used the fact that:

β t1 a tP(X = t|a ≤ t ≤ t 1 )dt = β a + t 1 2
and similarly,

β t2 t1 tP(X = t|t 1 ≤ t ≤ t 2 )dt = β t 1 + t 2 2
Also, b-t2 b-a Z represents the expected cost of the third and following reservations for t ∈ [t 2 , b]. Now, we suppress t 1 in the optimal sequence S and get a new sequence S = (t 2 , t 3 , . . . , t i , t i+1 , . . . )

We can compute its expected cost just as before:

E(S ) = t 2 -a b -a (αt 2 + β a + t 2 2 + γ) + b -t 2 b -a (αt 2 + βt 2 + γ + Z)
where Z has the same value as above, because only the beginning of the sequence has been modified. We can then derive that:

E(S) -E(S ) = 1 b -a (αu + βv + γw) where u = t 1 (b -t 2 ) + a(t 2 -t 1 ) > 0, v = t 1 (b -t 1 ) > 0, and w = b -t 1 > 0. Hence E(S) > E(S ),
and S was not an optimal sequence, the desired contradiction.

Exponential distributions

In this section, we provide partial results for the ReservationOnly problem (β = γ = 0 and α = 1) with an exponential distribution Exp(λ). From Theorem 2 (and the example in Section 2.3), we know that there exist sequences of finite expected cost. We further characterize the optimal solution as follows:

Proposition 2. Let S 1 = (s 1 , s 2 , . . . , s i , s i+1 , . . . ) denote the optimal sequence for Reserva-tionOnly with X 1 ∼ Exp(1). It is the sequence that minimizes

E(S 1 ) = s 1 + 1 + ∞ i=1 e -si ,
such that, s 2 = e s1 , and for i ≥ 3,

s i = e si-1-si-2 (12)
We denote by

E 1 = s 1 + 1 + ∞ i=1
e -si . The optimal sequence for ReservationOnly for

X λ ∼ Exp(λ) is the infinite sequence S λ = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) such that t i = si λ for i ≥ 1. Its expected cost is E(S λ ) = 1 λ E 1 .
Proof. The results on S 1 (Eq. ( 12) and E 1 ) follow directly from Proposition 1 and Equation [START_REF] Friedman | Report on a multicenter fMRI quality assurance protocol[END_REF]. Consider an Exp(λ) distribution: X λ . From Equation ( 4), the expected cost of the optimal sequence S λ is

E(S λ ) = ∞ i=0 t i+1 e -λti
where t 0 = 0, t 1 is unknown, and the value of t i for i ≥ 2 is given by Equation [START_REF] Friedman | Report on a multicenter fMRI quality assurance protocol[END_REF] as

t i = e λ(ti-1-ti-2) λ for i ≥ 2.
We define u i = λt i for all i ≥ 0, we derive that

E(S λ ) = 1 λ ∞ i=0 u i+1 e -ui
with u i = e ui-1-ui-2 for all i ≥ 2. Hence u i is the sequence that minimizes

E(S λ ) = ∞ i=0 t i+1 e -λti = 1 λ ∞ i=0 u i+1 e -ui = 1 λ u 1 + 1 + ∞ i=1 e -ui
We can notice that the sequence

U = (u 1 , u 2 , • • • , u i , • • •
) solves the same system of equations as S 1 , hence S 1 is a valid solution for U.

Hence the result.

Inria

Again, the optimal sequence is fully characterized by the value of t 1 or s 1 . Here, s 1 is independent of λ. In other words, the solution for Exp(1) is generic, and the solution for Exp(λ) for an arbitrary λ can be directly derived from it. Unfortunately, we do not know how to compute s 1 analytically. However, a brute-force search provides the value s 1 ≈ 0.74219, which means that the first reservation for Exp(λ) should be approximately three quarters of the mean value 1 λ of the distribution, for any λ > 0.

Heuristics for arbitrary distributions

The results of the preceding section provide an optimal strategy for Stochastic up to the determination of the optimal t o 1 , since Theorem 3 and Proposition 1 allow us to compute the subsequent t o i 's. However, while we have derived an upper bound on t o 1 , we do not know how to compute its exact value for an arbitrary distribution. In this section, we introduce several heuristics for solving the problem.

Brute-force procedure

We first present a procedure called Brute-Force that simply tries different values for the first reservation length t 1 in a sequence S, and then computes the subsequent values according to Equation [START_REF] Friedman | Report on a multicenter fMRI quality assurance protocol[END_REF]. Specifically, we try M different values of t 1 on the interval [a, b], where a is the lower bound of the distribution and b is the upper bound if the distribution is finite. Otherwise, we set b = A 1 , which is an upper bound on the optimal t o 1 as given in Equation ( 6). For each m = 1, . . . , M , we generate a sequence that starts with

t 1 = a + m • b -a M
Given a sequence S, its expected cost is evaluated via a Monte-Carlo process, as described in Section 5.1: we randomly draw N execution times from the distribution, and compute the expected cost incurred by the sequence over the N samples. We finally return the minimum expected cost found over all the M values of t 1 . Note that some values of t 1 may not lead to any result, because the sequence computed based on it and using Equation [START_REF] Friedman | Report on a multicenter fMRI quality assurance protocol[END_REF] may not be strictly increasing. In this case, we simply ignore the sequence. The complexity of this heuristic is O(M N ).

We point out that the actual optimal value for the first request t o 1 would possibly lie in between two successive values of t 1 that we try. However, because we deal with smooth probability distributions, we expect to return a t 1 and an associated expected cost that are close to the optimal when M and N are sufficiently large. In the performance evaluation, we set M = 5000 and N = 1000.

Discretization-based dynamic programming

We now present a heuristic that approximates the optimal solution for Stochastic by first discretizing the continuous distribution and then computing an optimal sequence for the discrete problem via dynamic programming.

Truncating and discretizing continuous distributions

If a continuous distribution has finite support [a, b], where 0 ≤ a < b, then we can directly discretize it. Otherwise, for a distribution with infinite support [a, ∞), where 0 ≤ a, we need to first truncate it in order to operate on a bounded interval. In the latter case, we define

b = Q(1 -) where Q(x) = inf{t|F (t) ≥ x}
is the quantile function. That is, we discard the final ∈ (0, 1) quantile of the distribution, which for usual distributions ensures that b is finite. In either case, the discretization will then be performed on the interval [a, b]. Let n denote the number of discrete values we will sample from the continuous distribution. The result will be a set of n pairs (v i , f i ) i=1...n , where the v i 's represent the possible execution times of the jobs, and the f i 's represent the corresponding probabilities. We envision two schemes for the discretization:

• Equal-probability: This scheme ensures that all the discrete execution times have the same probability. Thus, for all i = 1, 2, . . . , n, we can compute

v i = Q i • F (b) n
with associated

f i = F (b) n
• Equal-time: This scheme makes the discrete execution times equally spaced in the interval [a, b]. Thus, for all i = 1, 2, . . . , n, the execution times and their probabilities are computed as

v i = a + i • b -a n associated to f i = F (v i ) -F (v i-1 )
Note that when the continuous distribution has unbounded support, the probabilities for the n discrete execution times do not sum up to 1, i.e., n i=1

f i = F (b) = 1 -
A smaller value of and a larger number n will provide a better sampling of the continuous distribution in either discretization scheme. In the performance evaluation, we set = 10 -7 and n = 1000.

Dynamic programming for discrete distributions

We now present a dynamic programming algorithm to compute the optimal sequence for any discrete probability distribution. It will be used with the discretization schemes to approximate the optimal solution for an arbitrary continuous distribution.

Theorem 5 (Discrete distribution). If X ∼ (v i , f i ) i=1...n , then Stochastic can be solved optimally in polynomial time.

Inria

Proof. Let E *

i denote the optimal expected cost given that X ≥ v i . In this case, to compute the optimal expected cost, the probability distribution of X needs to be first updated as

f k = f k n j=i f j , ∀k = i, . . . , n
which guarantees that

n k=i f k = 1.
We can then express E * i based on the following dynamic programming formulation:

E * i = min i≤j≤n αv j +γ + j k=i f k • βv k + n k=j+1 f k βv j +E * j+1
In particular, to compute E * i , we make a first reservation of all possible discrete values (v j ) j=i...n and select the one that incurs the minimum total expected cost. For each v j considered, if the job's actual execution time is greater than v j (with probability n k=j+1 f k ), the total cost also includes the optimal cost E * j+1 for making subsequent reservations. The dynamic program is initialized with E * n = αv n + βv n + γ, and the optimal total expected cost is given by E * 1 . The complexity is O(n 2 ), since each E * i depends on n -i other expected costs, with associated probability updates and summations that can be computed in O(n -i) time. The optimal sequence of reservations can be obtained by backtracking the decisions made at each step.

Note that the sequence obtained by dynamic programming always ends with the largest value v n = b. When applying it back to a continuous distribution with unbounded support, more values will be needed, because the sequence must tend to infinity as explained in Section 2.2. In this case, additional values can be appended to the sequence by using other heuristics, such as the ones presented next in Section 4.3.

Other heuristics

We finally present some simple heuristics that are inspired by common resource allocation strategies in the literature. These heuristics do not explore the structure of the optimal solution nor the probability distribution, but rely on simple incremental methods to generate reservation sequences.

In the following, we will use µ = E(X) to denote the mean of a given distribution, σ 2 = E(X 2 )-µ 2 to denote its variance, and m = Q( 12 ) to denote its median, where Q(x) = inf{t|F (t) ≥ x} represents the quantile function. The different heuristics are defined as follows:

• Mean-by-Mean: start with the mean (i.e., t 1 = µ) and then make each subsequent reservation request by computing the conditional expectation of the distribution in the remaining interval, i.e.,

t i = E(X|X > t i-1 ) = ∞ ti-1 tf (t)dt 1 -F (t i-1 )
, ∀i ≥ 2

• Mean-Stdev: start with the mean (i.e., t 1 = µ) and then increment the reservation length by one standard deviation (σ) for each subsequent request, i.e.,

t i = µ + (i -1)σ, ∀i ≥ 2
• Mean-Doubling: start with the mean (i.e., t 1 = µ) and then double the reservation length for each subsequent request, i.e.,

t i = 2 i-1 µ, ∀i ≥ 2
• Median-by-Median: start with the median (i.e., t 1 = m) and then make each subsequent reservation request by using the median of the distribution in the remaining interval, i.e.,

t i = Q(1 - 1 2 i ), ∀i ≥ 2
The sequence of reservations for all heuristics above can be easily computed for the usual distributions considered in this paper. Appendix A provides some key parameters (e.g., mean, variance, quantile) to facilitate the computation. Note that deriving the sequence for Mean-by-Mean is straightforward for some distributions (e.g., exponential, uniform), but more involved for others. Recursive formulas are provided in Appendix B to compute the sequence for this heuristic under different distributions.

Performance evaluation

In this section, we evaluate the different heuristics presented in Section 4, and compare their performance. The code and setup of the experiments presented in this section are publicly available on https://gitlab.inria.fr/vhonore/ipdps_2019_stochastic-scheduling.

Evaluation methodology

For each heuristic that generates a reservation sequence S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) under a particular probability distribution D, we approximate its expected cost via a Monte-Carlo process2 : we randomly sample N possible execution times from the distribution, and then average over the cost of all the N samples, i.e.,

Ẽ(S) = 1 N N i=1 C(k, t)| t←D (13)
where C(k, t) is the cost for a specific execution time t drawn from the distribution, computed using Equation (2). For the presented evaluation results, we set N = 1000.

To get uniform results, we normalize the expected cost of each heuristic by the expected cost of an omniscient scheduler, which knows the job execution time t a priori, and thus would make a single request of length t 1 = t. Averaging over all possible values of t from the distribution D, the omniscient scheduler has an expected cost:

E o = ∞ 0 (αt + βt + γ)f (t)dt = (α + β) • E[X] + γ
Hence the normalized ratio will always be larger than or equal to 1, and a smaller ratio means a better result.

We perform the evaluation of the heuristics under two different reservation-based scenarios.

-λt λ = 1.0 t ∈ [0, ∞) Weibull(λ, κ) κ λ t λ κ-1 e -t λ κ λ = 1.0 κ = 0.5 t ∈ [0, ∞) Gamma(α, β) β α Γ(α) t α-1 e -βt α = 2.0 β = 2.0 t ∈ [0, ∞) LogNormal µ, σ 2 1 tσ √ 2π e -1 2 ln t-µ σ 2 µ = 3.0 σ = 0.5 t ∈ (0, ∞) TruncatedNormal(µ, σ 2 , a) 1 σ 2 π • e -1 2 t-µ σ 2 1-erf a-µ σ √ 2 µ = 8.0 σ 2 = 2.0 a = 0.0 t ∈ [a, ∞) Pareto(ν, α) αν α t α+1 ν = 1.5 α = 3.0 t ∈ [ν, ∞)
Distributions with finite support Uniform(a, b)

1 b-a a = 10.0 b = 20.0 t ∈ [a, b] Beta(α, β) t α-1 •(1-t) β-1 B(α,β) α = 2.0 β = 2.0 t ∈ [0, 1] BoundedPareto(L, H, α) αH α L α t -α-1 H α -L α L = 1.0 H = 20.0 α = 2.1 t ∈ [L, H]
• ReservationOnly (Section 5.2): This scenario is based on the Reserved Instance pricing scheme available in AWS [START_REF]AWS pricing information[END_REF], where the user pays exactly what is requested. Hence, we set α = 1, β = γ = 0. We consider nine probability distributions in this case, six of which have infinite support and the remaining three have finite support. Table 1 lists these distributions with instantiations of their parameters used in the evaluation.

• NeuroHpc (Section 5.3): This scenario is based on executing large jobs on HPC platforms, where the cost, as represented by the total turnaround time of a job, is the sum of its waiting time in the queue and its actual execution time. We set β = 1 for the execution time and instantiate the waiting time function (α, γ) by curve-fitting the data from Fig. 2b. The probability distribution is derived from execution traces of neuroscience applications as shown in Fig. 1b.

Results for ReservationOnly scenario

Table 2 presents, for each heuristic, the normalized expected cost, i.e., Ẽ(S)/E o , under different probability distributions. The Brute-Force heuristic tries M = 5000 values of t 1 , and both discretization heuristics set the truncation parameter to be = 10 -7 and use n = 1000 samples. First, the normalized costs allow us to compare the performance of these heuristics with that of the omniscient scheduler to access the relative benefits of using Reserved Instance (RI) vs.

On-Demand (OD). Indeed, if the per-hour price for RI is c RI and the corresponding price for OD is c OD , it is beneficial to use RI and compute a reservation sequence S,

if c RI • Ẽ(S) ≤ c OD • E o , that is Ẽ(S)/E o ≤ c OD /c RI .
In the case of Amazon AWS [START_REF]AWS pricing information[END_REF], the price for the two types of services can differ by a factor of 4, i.e., c OD /c RI = 4. We can see in the table that the normalized costs of all heuristics satisfy Ẽ(S)/E o < 4 for all distributions. Overall, the results show the benefit of using the reservation-based approach for the considered problem. We also observe that, compared with other heuristics, Brute-Force has better performance (see values in the brackets in the table), and this is because it computes a reservation sequence by exploring the properties of the optimal solution (Section 3.3). To validate this observation, we plot Figure 3 that shows the normalized cost using the Brute- Force heuristic for a Lognormal distribution3 of mean µ ≈ 8 min when the standard deviation varies between 0 and 2µ. We see that, for this instantiation, it is always beneficial to use RI rather than OD when using the Brute-Force heuristic.

We now study the Brute-Force heuristic in more detail. Table 3 shows the best t 1 found, which we denote by t bf 1 , and some other values of t 1 at different quantiles of the distributions with their normalized costs (in brackets). First, we can see that some values of t 1 can lead to invalid sequences that are not increasing (i.e., t i+1 < t i for some i), which are indicated by null cost values in the table. Moreover, even if the sequence is valid, compared to using t bf 1 , randomly guessing a t 1 can result in a cost that is not good enough in most cases. Fig. 4 further shows the Monte-Carlo simulations of the normalized cost of Brute-Force while trying different values of t 1 in the search interval for all considered distributions. One can observe some "gaps" in the figure (e.g., Fig. 4a between 0.25 and 0.75), which are due to the "bad" choices of t 1 that lead to invalid sequences. Although we can sometimes extract t 1 's that could give a reasonable cost (e.g., in the case of Exponential distribution, t 1 = 0 results in a cost that is close to that given by t bf 1 ), it is difficult in general to guess a good value for t 1 without using a systematic approach. We point out that more efficient algorithms may exist to search for the best t 1 , but our Brute-Force procedure takes just a few seconds to run on an Intel i7 core with M = 5000 and N = 1000, thus providing a practical solution that is close to the optimal for the problem.

Table 4 shows the performance of the two discretization-based heuristics as presented in Section 4.2 with different numbers of discrete samples. We can see that, for all distributions considered, the normalized costs of both heuristics improve as we increase the number n of samples. The performance converges and gets close to that of Brute-Force when n = 1000, despite the differences in the convergence rate under different distributions and discretization schemes (Equal-time and Equal-probability). Again, both heuristics take just a few seconds to run on an Intel i7 core, and the results provide good approximate solutions to the problem with sufficient samples.

Results for NeuroHpc scenario

We now present the evaluation results for the NeuroHpc scenario when using a real job execution time distribution under an HPC cost model. The distribution (shown in Fig. 1b) is generated from the execution traces of a neuroscience application (VBMQA [START_REF] Bazin | Volumetric neuroimage analysis extensions for the mipav software package[END_REF]). It follows a LogNormal law with parameters (µ = 7.1128, σ = 0.2039) obtained by fitting the execution time data to the distribution curve, and this gives a mean of µ d = 1253.37s ≈ 0.348 hour and a standard deviation of σ d = 258.261s ≈ 0.072 hour. The average waiting time function (shown in Fig. 2b) is obtained by analyzing the logs from 20 groups of jobs run on 409 processors of Intrepid [START_REF] Tang | Reducing fragmentation on torusconnected supercomputers[END_REF] with different reservation requests. We get an affine function with parameters (α = 0.95, γ = 3771.84s ≈ 1.05 hour) obtained also by curve fitting. The execution time parameter is set to β = 1. Figure 5 plots the normalized expected costs of different heuristics in this scenario. To evaluate the robustness of the results, we also vary the distribution parameters so that its mean and standard deviation are increased by up to a factor of 10 from their original values4 , i.e., up to µ d ≈ 3.48 hours and σ d ≈ 0.72 hour. We can see from the figures that, regardless of the parameter variations, Brute-Force and the two discretization-based heuristics (Equaltime and Equal-probability) have very close performance, which is significantly better than the performance of the other heuristics. The results are consistent with those observed in Section 5.2 for the ReservationOnly scenario, and altogether they demonstrate the effectiveness and robustness of the proposed Brute-Force and discretization schemes for the Stochastic problem.

Related work

In this section, we review some related work on HPC/cloud resource scheduling and cost models, as well as on stochastic scheduling of jobs with uncertain execution times.

HPC resource scheduling. Most schedulers for HPC systems use an iterative repetitive algorithm triggered by state changes, such as new job submission, job starting or ending, or timeout. They use different policies to determine which job should execute when and on what resources. Jobs are usually placed in one or multiple queues with different priorities before being scheduled onto the available resources. For example, the Slurm scheduler [START_REF] Yoo | Slurm: Simple linux utility for resource management[END_REF] uses two queues, one for high-priority jobs and the other for low-priority jobs. A job is placed in a queue based on its resource requirement, generally with long-running jobs that require a large amount of resources having higher priorities. Jobs that are kept in the waiting queue for a long period of time could also be upgraded and moved up in the queue. Slurm schedules the jobs from the top of the high-priority queue and moves down. Even though larger jobs (in term of time and space) have higher priorities, generally the lack of resource availability in the system leads to longer wait times. On the other hand, smaller jobs, despite having lower priorities, are usually scheduled quickly thanks to the backfilling algorithms that place them in the unused time slots between successive large jobs. Some studies (e.g., [START_REF] Mu | Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[END_REF][START_REF] Rodrigo Álvarez | HPC system lifetime story: Workload characterization and evolutionary analyses on NERSC systems[END_REF][START_REF] Yamamoto | The K computer operations: Experiences and statistics[END_REF]) have analyzed the impact of scheduling strategies on the performance of applications in large HPC centers. Some of these studies show that the penalty for jobs with longer requested walltimes and/or larger numbers of nodes is higher than that for jobs with shorter elapsed times and smaller numbers of nodes. This is observed, for example, in [START_REF] Yamamoto | The K computer operations: Experiences and statistics[END_REF] for the K computer from Riken Advanced Institute for Computational Science. The study shows that, for applications requesting similar computing resources, the wait time generally increases with larger requested processing times and can cause delays of hours for large scientific applications, although it is also dependent on other workloads submitted to the system. Some HPC centers divide the resources into seasons for users to utilize the reserved resources. Users tend to submit more jobs toward the end of a season causing contention at the scheduler level which results in even longer waiting times. The study in [START_REF] Rodrigo Álvarez | HPC system lifetime story: Workload characterization and evolutionary analyses on NERSC systems[END_REF] presents a trend of the evolution of the workload of HPC systems and the corresponding scheduling policies as we move from monolithic MPI applications to high-throughput and data-intensive jobs. The paper shows that the cost paid in terms of the wait time of applications in the queue has generally increased over the years with less uniform workloads. The study in [START_REF] Mu | Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[END_REF] shows that systems that give each job a partition of the resources for exclusive use and allocate such partitions in the order of job arrivals could suffer from severe fragmentation, leading to low utilization. The authors propose an aggressive backfilling algorithm for dealing with such fragmentation. However, users are still expected to provide accurate runtime estimates. The study shows that over-estimation may lead to a long wait time and possibly excessive CPU quota loss, while under-estimations can lead to job terminations before completion. Some recent schedulers [START_REF] Park | 3sigma: distributionbased cluster scheduling for runtime uncertainty[END_REF] consider the distribution of execution time of the submitted jobs to take their scheduling decision in order to increase their overall utility.

Stochastic job scheduling. Many works deal with stochastic job scheduling (e.g., [START_REF] Canon | Evaluation and optimization of the robustness of dag schedules in heterogeneous environments[END_REF][START_REF] Dong | Resource load based stochastic DAGs scheduling mechanism for Grid environment[END_REF][START_REF] Tang | A stochastic scheduling algorithm for precedence constrained tasks on grid[END_REF][START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF][START_REF] Weiss | Turnpike optimality of smith's rule in parallel machines stochastic scheduling[END_REF]). Various models [START_REF] Canon | Scheduling independent stochastic tasks under deadline and budget constraints[END_REF] have been proposed to model the performance of executing stochastic jobs on computing platforms. For instance, in [START_REF] Li | Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems[END_REF], stochastic jobs are modeled as a DAG of tasks whose execution times and communication times are stochastically independent. In this paper, we model jobs by an execution time following a probability distribution. The authors in [START_REF] Tang | A stochastic scheduling algorithm for precedence constrained tasks on grid[END_REF] propose a model based on resource load in grid systems. Several refinements can be envisioned, such that improving scheduler performances by including distribution features in order to optimize final performance. Also, dealing with heterogeneous nodes increases problem complexity [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF]. We refer the reader to the book by Pinedo [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF] which contains a comprehensive survey of stochastic scheduling problems, and to the book chapter [START_REF] Gaujal | Comparisons of stochastic task-resource systems[END_REF] for a detailed comparison of stochastic task-resource systems.

Pricing and reservation schemes in the cloud. Cloud computing platforms have emerged as another option for executing HPC applications. Job scheduling in the cloud has an even bigger challenge [START_REF] Gupta | Evaluating and improving the performance and scheduling of HPC applications in cloud[END_REF], since it needs to deal with highly heterogeneous resources with a wide range of processor configurations, interconnects, virtualization environments, etc. Different pricing and reservation schemes are also available for users who submit jobs to a cloud service. Several works have been done to study these schemes in the cloud, and from a computer science perspective, many of these studies focus on the pricing strategies and service management of platform providers [START_REF] Afanasyev | Service provider competition: Delay cost structure, segmentation, and cost advantage[END_REF][START_REF] Chen | Pricing schemes in cloud computing: Utilization-based versus reservation-based[END_REF][START_REF] Dierks | Cloud pricing: the spot market strikes back[END_REF][START_REF] Xu | Dynamic cloud pricing for revenue maximization[END_REF]. Some works consider modeling the delays for users [START_REF] Afanasyev | Service provider competition: Delay cost structure, segmentation, and cost advantage[END_REF] and how providers manage the idle resources [START_REF] Dierks | Cloud pricing: the spot market strikes back[END_REF]. The work in [START_REF] Xu | Dynamic cloud pricing for revenue maximization[END_REF] studies the pricing practices of Amazon AWS [START_REF]AWS pricing information[END_REF] when the price is dynamically adapted to real-time demand and idle resources. In [START_REF] Chen | Pricing schemes in cloud computing: Utilization-based versus reservation-based[END_REF], authors provide an analytical model of pricing for reservation-based scheme (used by Amazon AWS) and utilization-based scheme (used by Google GCP [START_REF]GCP pricing information[END_REF]). They show that the effective price mainly depends on the variation of platform usage and the competition for customers. Some tools are also provided for users to perform cost evaluation in order to select which type of platform to use. They show that users with high-volatility demand should consider using AWS offers while one should use GCP in the other case. Our experimental results in this paper suggest that, compared with on-demand or utilization-based services, reservation strategies can provide cost-effective options for executing stochastic jobs when there is significant difference in the offered price.

Inria 7 Conclusion

In this paper, we have studied the problem of scheduling stochastic jobs on a reservation-based platform. We have shown the existence of an optimal reservation sequence when the job execution time follows a set of classical distributions, and we have characterized the optimal solution up to the duration of the first reservation. We do not know how to compute this duration analytically, but we have provided an upper bound and a brute-force procedure to generate a solution that is close to the optimal. We have also introduced several heuristics, one based upon discretizing the continuous distribution and some relying on standard measures, such as the mean, variance and quantile of the distribution. We have demonstrated the effectiveness of these heuristics via comprehensive simulations conducted using both classical distributions and execution traces of a real neuroscience application.

Future work will include allowing requests with variable amount of resources, hence offering a combination of a reservation time and a number of processors. Another interesting direction is to include checkpoint snapshots at the end of some reservations. We expect the solutions such as the one introduced in this work not to work because of the difficulty of choosing which reservations to checkpoint. Indeed we do not expect the strategy "checkpoint all reservations" to be optimal. Hence the checkpointing approach calls for a complicated trade-off between doing useful work through the reservations and sacrificing some time/budget in order to avoid restarting the job whenever its execution time exceeds the length of the current reservation. The cost will then depend both on the length of the reservation and on a conditional probability based on previous checkpointing decisions.

A Properties of different probability distributions (see Table 5)

Numerical functions referenced in the table include:

• erf(x) = 2 √ π
x 0 e -t 2 dt: the error function;

• erf -1 (z) = inf{x| 2 √ π
x 0 e -t 2 dt = z}: the inverse error function;

• Γ(x) = ∞ 0 t x-1 e -t dt: the gamma function; • Γ(x, y) = ∞ y t x-1 e -t dt: the upper incomplete gamma function; • Γ -1 (x, z) = inf{y| ∞ y t x-1 e -t dt = z}: the inverse upper incomplete gamma function; • B(x, y) = 1 0 t x-1 (1 -t) y-1 dt: the beta function. • B(a; x, y) = a 0 t x-1 (1 -t) y-1 dt: the incomplete beta function. • B -1 (z; x, y) = inf{a| a 0 t x-1 (1 -t) y-1 dt = z}: the inverse incomplete beta function.
CDF: F (t) Mean: µ Variance: σ 2 x-Quantile: Q(x) Exponential (λ) 1 -e -λt 1 λ 1 λ 2 -ln(1-x) λ Weibull(λ, κ) 1 -e -( t λ ) κ λΓ(1 + 1 κ ) λ 2 Γ(1 + 2 κ ) -Γ(1 + 1 κ ) 2 λ κ -ln(1 -x) Gamma(α, β) 1 -Γ(α,βt) Γ(α) α β α β 2 Γ -1 α,(1-x)Γ(α) β LogNormal µ, σ 2 1 2 + 1 2 erf ln t-µ √ 2σ e µ+ σ 2 2 e σ 2 -1 e 2µ+σ 2 e √ 2σ•erf -1 (2x-1)+µ TruncatedNormal(µ, σ 2 , a) erf t-µ σ √ 2 -erf a-µ σ √ 2 1-erf a-µ σ √ 2 µ + σ 2 π • η(a), where
η(a) = e -1 2 ( a-µ σ ) 2 1-erf a-µ σ √ 2 σ 2 1 + a-µ σ • η(a) -η(a) 2 µ + σ √ 2 • erf -1 (z), where z = x + (1 -x)erf a-µ σ √ 2 Pareto(ν, α) 1 -ν t α αν α-1 (for α > 1) αν 2 (α-1) 2 (α-2) (for α > 2) ν α √ 1-x Uniform(a, b) t-a b-a a+b 2 (b-a) 2 12 (1 -x)a + xb Beta(α, β) B(t;α,β) B(α,β) α α+β αβ (α+β) 2 (α+β+1) B -1 (xB(α, β); α, β) BoundedPareto(L, H, α) H α (1-L α t -α ) H α -L α α α-1 • H α L-HL α H α -L α (for α = 1) α α-2 • H α L 2 -H 2 L α H α -L α -α α-1 • H α L-HL α H α -L α 2 (for α = 1, 2) L α 1-(1-( L H ) α )x

Inria

B Recursive formulas to compute sequence of reservations for the Mean-by-Mean heuristic

In this section, we present recursive formulas to compute the sequence of reservations S = (t 1 , t 2 , . . . , t i , t i+1 , . . . ) using the Mean-by-Mean heuristic for the considered distributions. As described in Section 4.3, the heuristic computes a new reservation value t i from the previous value t i-1 as follows:

t i = E(X|X > t i-1 ) = ∞ ti-1 tf (t)dt 1 -F (t i-1 ) , for all i ≥ 2 (14)
The following subsections present the derivations of the formulas for different distributions, while Table 6 summarizes results for all distributions.

t i = 1 λ , if i = 1 t i-1 + 1 λ , otherwise Weibull(λ, κ) t i =    λΓ 1 + 1 κ , if i = 1 λe t i-1 λ κ Γ 1 + 1 κ , ti-1 λ κ , otherwise Gamma(α, β) t i = α β , if i = 1 1 β α + (βti-1) α e -βt i-1 Γ(α,βti -1)
, otherwise LogNormal(µ, σ 2 )

t i =      e µ+ σ 2 2 , if i = 1 e µ+ σ 2 2 • 1-erf ln t i-1 -µ σ √ 2 -σ √ 2 1-erf ln t i-1 -µ σ √ 2 , otherwise TruncatedNormal(µ, σ 2 , a) t i =          µ + σ 2 π • e -1 2 ( a-µ σ ) 2 1-erf a-µ σ √ 2 , if i = 1 µ + σ 2 π • e -1 2
t i-1 -µ σ 2 1-erf t i-1 -µ σ √ 2
, otherwise Pareto(ν, α)

t i = α α-1 ν, if i = 1 α α-1 t i-1 , otherwise (for α > 1)
Uniform(a, b) , otherwise BoundedPareto(L, H, α)

t i = 1 2 (a + b), if i = 1
t i =    α α-1 • H 1-α -L 1-α H -α -L -α , if i = 1 α α-1 • H 1-α -t 1-α i-1 H -α -t -α i-1
, otherwise (for α > 1)

RR n°9211

B.1 Exponential distribution

For Exponential (λ), substituting f (t) = λe -λt and F (t) = 1 -e -λt into Equation ( 14), we get:

t i = ∞ ti-1 tλe -λt dt e -λti-1 = [-te -λt ] ∞ ti-1 + ∞ ti-1 e -λt dt e -λti-1
(integrating by parts)

= t i-1 e -λti-1 + [-1 λ e -λt ] ∞ ti-1
e -λti-1 = t i-1 e -λti-1 + 1 λ e -λti-1 e -λti-1

= t i-1 + 1 λ

B.2 Weibull distribution

For Weibull(λ, κ), substituting f (t) = κ λ t λ κ-1 e -( t λ ) κ and F (t) = 1-e -( t λ ) κ into Equation ( 14) and simplifying, we get:

t i = ∞ ti-1 κ t

B.3 Gamma distribution

For Gamma(α, β), substituting f (t) = β α Γ(α) t α-1 e -βt and F (t) = 1 -Γ(α,βt) Γ(α) into Equation ( 14) and simplifying, we get:

t i = ∞ ti-1 β α t α e -βt dt Γ (α, βt i-1 ) = 1 β • ∞ βti-1
x α e -x dx Γ (α, βt i-1 ) (by letting x = βt) into Equation ( 14) and simplifying, we get:

= 1 β • α ∞ βti-1 x α-1 e -x dx -[x α e -x ] ∞
t i = 1 σ 2 π • ∞ ti-1 e -1 2 ( ln t-µ σ ) 2 dt 1 -erf ln ti-1-µ σ √ 2 = e µ+ σ 2 2 • 2 √ π ∞ ln t i-1 -µ σ √ 2 -σ √ 2 e -x 2 dx 1 -erf ln ti-1-µ σ √ 2 by letting x = ln t -µ σ √ 2 - σ √ 2 = e µ+ σ 2 2 • 2 √ π ∞ 0 e -x 2 dx -2 √ π ln t i-1 -µ σ √ 2 -σ √ 2 0 e -x 2 dx 1 -erf ln ti-1-µ σ √ 2 = e µ+ σ 2 2 • erf(∞) -erf ln ti-1-µ σ √ 2 -σ √ 2 1 -erf ln ti-1-µ σ √ 2 = e µ+ σ 2 2 • 1 -erf ln ti-1-µ σ √ 2 -σ √ 2 1 -erf ln ti-1-µ σ √ 2
where erf(x) = 2 √ π

x 0 e -t 2 dt denotes the error function.

B.5 TruncatedNormal distribution

For TruncatedNormal(µ, σ 2 , a), substituting f (t) = 1 into Equation ( 14) and simplifying, we get:

RR n°9211 t i = 1 σ 2 π • ∞ ti-1 te -1 2 ( t-µ σ ) 2 dt 1 -erf ti-1-µ σ √ 2 = 2 √ π • ∞ t i-1 -µ σ √ 2 (xσ √ 2 + µ)e -x 2 dx 1 -erf ti-1-µ σ √ 2 by letting x = t -µ σ √ 2 = 2 √ π • σ √ 2 ∞ t i-1 -µ σ √ 2 xe -x 2 dx + µ ∞ 0 e -x 2 dx - t i-1 -µ σ √ 2 0 e -x 2 dx 1 -erf ti-1-µ σ √ 2 = 2 √ π • σ √ 2 -1 2 e -x 2 ∞ t i-1 -µ σ √ 2 + µ √ π 2 erf(∞) -erf ti-1-µ σ √ 2 1 -erf ti-1-µ σ √ 2 = 2 √ π • σ √ 2 0 + 1 2 e - t i-1 -µ σ √ 2 2 + µ √ π 2 1 -erf ti-1-µ σ √ 2 1 -erf ti-1-µ σ √ 2 = µ + σ 2 π • e -1 2 t i-1 -µ σ 2 1 -erf ti-1-µ σ √ 2
where erf(x) = 2 √ π

x 0 e -t 2 dt denotes the error function.

B.6 Pareto distribution

For Pareto(ν, α) with α > 1, substituting f (t) = αν α t α+1 and F (t) = 1 -ν t α into Equation [START_REF] Gupta | Evaluating and improving the performance and scheduling of HPC applications in cloud[END_REF] and simplifying, we get:

t i = α ∞ ti-1 t -α dt t -α i-1 = α 1 -α • [t 1-α ] ∞ ti-1 t -α i-1 = α 1 -α • 0 -t 1-α i-1 t -α i-1 = α α -1 t i-1

B.7 Uniform distribution

For Uniform(a, b), substituting f (t) = 1 b-a and F (t) = t-a b-a into Equation ( 14), we get:

Inria t i = b ti-1 t 1 b-a dt 1 -ti-1-a b-a = b 2 -t 2 i-1 2(b -t i-1 ) = b + t i-1 2

B.8 Beta distribution

For Beta(α, β), substituting f (t) = t α-1 (1-t) β-1 B(α,β)

and F (t) = B(t;α,β) B(α,β) into Equation ( 14) and simplifying, we get:

t i = 1 ti-1 t α (1 -t) β-1 dt B (α, β) -B (t i-1 ; α, β) = 1 0 t α (1 -t) β-1 dt - ti-1 0 t α (1 -t) β-1 dt B (α, β) -B (t i-1 ; α, β) = B (α + 1, β) -B (t i-1 ; α + 1, β) B (α, β) -B (t i-1 ; α, β)
where B(x, y) = 1 0 t x-1 (1 -t) y-1 dt represents the beta function and B(a; x, y) = a 0 t x-1 (1t) y-1 dt represents the incomplete beta function.

B.9 BoundedPareto distribution

For BoundedPareto(L, H, α), substituting f (t) = αH α L α t -α-1 H α -L α and F (t) = H α (1-L α t -α ) H α -L α into Equation ( 14) and simplifying, we get:

t i = αH α H ti-1 t -α dt H α t -α i-1 -1 = α 1 -α • H α (H 1-α -t 1-α i-1 ) H α t -α i-1 -1 = α α -1 • H 1-α -t 1-α i-1 H -α -t -α i-1 RR n°9211

Theorem 4 .

 4 For a uniform distribution Uniform(a, b), the optimal sequence for Stochastic is S o = (b).

Figure 3 :

 3 Figure 3: Normalized expected cost of the Brute-Force heuristic using a LogNormal distribution when σ varies from 0 to 2µ (µ ≈ 8min).

Figure 4 :

 4 Figure 4: Monte-Carlo simulations of the normalized costs of the Brute-Force heuristic with different values of t 1 in the ReservationOnly scenario under all considered distributions.

Figure 5 :

 5 Figure 5: Normalized expected costs of the different heuristics in the NeuroHpc scenario with different values for the mean (in hours) and standard deviation (in hours) of the LogNormal distribution (µ = 7.1128, σ = 0.2039) with α = 0.95, β = 1.0, γ = 1.05.

Distribution

if i = 1 B

 1 (α+1,β)-B(ti-1;α+1,β) B(α,β)-B(ti-1;α,β)

  x, y) = ∞ y t x-1 e -t dt denotes the upper incomplete gamma function.

βti- 1 Γ

 1 (α, βt i-1 ) (integrating by parts)= 1 β • αΓ (α, βt i-1 ) + (βt i-1 ) α e -βti-1 Γ (α, βt i-1 ) i-1 ) α e -βti-1 Γ(α, βt i-1 )where Γ(x, y) = ∞ y t x-1 e -t dt denotes the upper incomplete gamma function.InriaB.4 LogNormal distributionFor LogNormal(µ, σ 2 ), substituting f (t) = 1

σ 2 π • e - 1 2

 21 (

  Theorem 2. For any distribution D with infinite support [a, ∞) such that E[X 2 ] < ∞, the value t o 1 of an optimal sequence S o = (t o 1 , t o 2 , . . . , t o i , t o i+1 , . . . ) satisfies t o 1 ≤ A 1 , and E(S o ) ≤ A 2 , where

Table 1 :

 1 Probability distributions and parameter instantiations

	Distribution	PDF f (t)	Instantiation	Support
		Distributions with infinite support
	Exponential (λ)	λe

Table 2 :

 2 Normalized expected costs of different heuristics in the ReservationOnly scenario under different distributions. The values in the brackets show the expected costs normalized by those of the Brute-Force heuristic.

	Distribution	Brute-Force	Mean-by-Mean	Mean-Stdev	Mean-Doub.	Med-by-Med	Equal-time	Equal-prob.
	Exponential	2.15	2.36 (1.10)	2.39 (1.11)	2.42 (1.13)	2.83 (1.32)	2.31 (1.07)	2.36 (1.10)
	Weibull	2.12	2.76 (1.30)	3.58 (1.69)	3.03 (1.43)	3.05 (1.44)	2.40 (1.13)	2.22 (1.05)
	Gamma	2.02	2.26 (1.12)	2.18 (1.08)	2.24 (1.11)	2.51 (1.24)	2.20 (1.09)	2.13 (1.05)
	Lognormal	1.85	2.19 (1.19)	2.09 (1.13)	1.95 (1.06)	2.30 (1.24)	1.87 (1.01)	1.93 (1.04)
	TruncatedNormal	1.36	1.98 (1.46)	1.83 (1.35)	1.98 (1.46)	2.16 (1.60)	1.38 (1.02)	1.36 (1.00)
	Pareto	1.62	1.82 (1.12)	2.18 (1.34)	1.75 (1.08)	2.26 (1.39)	1.71 (1.05)	1.66 (1.03)
	Uniform	1.33	2.21 (1.66)	1.90 (1.43)	1.67 (1.26)	2.21 (1.66)	1.33 (1.00)	1.33 (1.00)
	Beta	1.75	2.02 (1.15)	2.11 (1.20)	1.98 (1.13)	2.45 (1.40)	1.79 (1.02)	1.80 (1.02)
	BoundedPareto	1.80	1.84 (1.02)	2.09 (1.16)	1.83 (1.01)	2.81 (1.56)	2.00 (1.11)	1.91 (1.06)

Table 3 :

 3 The best t bf 1 found by the Brute-Force heuristic and other values of t 1 at different quantiles of the distributions with their normalized expected costs (in brackets) in the Reser-vationOnly scenario.

	Distribution	t bf 1 (assoc. cost)	Q(0.25)	Other values of t1 (associated cost) Q(0.5) Q(0.75) Q(0.99)
	Exponential	0.73 (2.15)	0.29 (-)		0.69 (-)	1.39 (2.67)	4.61 (4.83)
	Weibull	0.18 (2.12)	0.08 (2.51)	0.48 (2.35)	1.92 (3.87)	21.21 (13.49)
	Gamma	1.23 (2.02)	0.48 (-)		0.84 (-)	1.35 (2.11)	3.32 (3.36)
	Lognormal	29.64 (1.85)	14.34 (-)		20.09 (-)	28.14 (-)	64.28 (2.97)
	TruncatedNormal	10.22 (1.36)	7.05 (-)		8.00 (-)	8.95 (-)	11.29 (1.42)
	Pareto	2.59 (1.62)	1.65 (-)		1.89 (-)	2.38 (-)	6.96 (4.23)
	Uniform	19.95 (1.33)	12.50 (-)		15.00 (-)	17.50 (-)	19.90 (-)
	Beta	0.81 (1.75)	0.33 (-)		0.50 (-)	0.67 (-)	0.94 (1.89)
	BoundedPareto	2.10 (1.80)	1.15 (-)		1.39 (-)	1.93 (-)	8.27 (4.64)

Table 4 :

 4 Normalized expected costs of the two discretization-based heuristics with different numbers of samples in the ReservationOnly scenario. = 25 n = 50 n = 100 n = 250 n = 500 n = 1000 n = 10 n = 25 n = 50 n = 100 n = 250 n = 500 1000

	Distribution n = 10 n Exponential 2.61 2.40	2.33	Equal-time 2.33 2.39	2.35	2.31	3.68	2.76	Equal-probability 2.56 2.59 2.28	2.34	2.36
	Weibull	17.03	7.19	4.11	3.14	2.66	2.95	2.40	15.77	7.46	5.75	4.24	3.47	2.84	2.22
	Gamma	2.22	2.17	2.17	2.13	2.12	2.08	2.20	2.66	2.39	2.38	2.23	2.27	2.27	2.13
	Lognormal	1.93	1.86	1.96	1.89	1.93	1.96	1.87	2.93	2.52	2.18	2.00	1.92	1.91	1.93
	TruncatedNormal	1.38	1.34	1.36	1.38	1.37	1.37	1.38	1.41	1.39	1.39	1.38	1.36	1.36	1.36
	Pareto	31.54	13.02	6.88	3.80	2.09	1.74	1.71	32.05	12.99	3.76	5.09	2.97	1.99	1.66
	Uniform	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33	1.33
	Beta	1.82	1.82	1.81	1.86	1.78	1.79	1.79	1.79	1.82	1.78	1.81	1.79	1.81	1.80
	BoundedPareto	2.18	1.88	1.84	2.04	1.98	1.91	2.00	2.59	2.17	1.90	1.99	1.91	1.94	1.91

Table 5 :

 5 Properties of different probability distributions.

Table 6 :

 6 Recursive formulas to compute sequence of reservations for Mean-by-Mean.

Distribution

Sequence of t i 's for i ≥ 1

Exponential(λ)

Other cost functions could be envisioned. In particular, the cost for a reservation could be a more general function than a simple affine one. Several results of this paper can be extended to convex cost functions (see Appendix C). We focus on affine costs because of their wide applicability under various scenarios.RR n°9211

RR n°9211

The possibly infinite sequence prevents us from analytically evaluating its expected cost.Inria

Recall that we assume that job durations can obey LogNormal distribution.Inria

Given a desired mean µ d and a standard deviation σ d , the LogNormal distribution can be instantiated with parameters σ = ln(( σ d µ d ) 2 + 1) and µ = ln µ dσ d 2 2 . Inria

Acknowledgments

We thank Bennett Landman and his MASI Lab at Vanderbilt for sharing the medical imaging database used to extract the execution time distributions. This research was supported in part by the National Science Foundation grant CCF1719674, Vanderbilt Institutional Fund, and Inria-Vanderbilt associated team Keystone. Part of this work was done while Valentin Honoré was visiting Vanderbilt University.

C Extension to convex cost functions

We briefly show that the results of this paper can be easily extended to convex cost functions. To do so, we extend Theorem 3 and Proposition 1 in the case of a general convex cost function. Theorem 6. Let S o = (t o i ) i≥1 denote an optimal sequence for Stochastic. For all i ≥ 1, if t o i is not the last element of the sequence and F (t o i ) = 1, we have the following property:

where G (x) is a convex cost function.

The proof follows the same principle as the one for Theorem 3.

Proposition 3. For a smooth distribution with unbounded support and a convex cost function G (x), solving Stochastic reduces to finding t o 1 that minimizes

where t o 0 = 0, and for all i ≥ 2,

For a smooth distribution with bounded support, the recurrence in Equation ( 16) still holds but the optimal sequence stops as soon as it reaches t o i with F (t o i ) = 1.

Proof. Directly comes from rewriting Equation [START_REF] Harrigan | Vanderbilt university institute of imaging science center for computational imaging XNAT: A multimodal data archive and processing environment[END_REF].