Emmanuel Polonowski
email: emmanuel.polonowski@u-pec.fr

DBGen User Manual

Introduction

DBGen is a tool for the Coq Proof Assistant. It generates Coq definitions and properties from a term structure with binding handling, providing a framework in the De Bruijn setting.

Source syntax

The source syntax of DBGen is a valid coq (inductive) term structure annotated with comments for binding information, defined inside a module whose name will be used in the generated content. We assume the knowledge of basic inductive definitions in Coq and of De Bruijn encodings. Annotations are given as Coq comments, i.e. between (* and *), placed in strategic locations to indicate the binding structure of the defined syntax. End LambdaTerms.

index annotation

Given a term structure, the (* index *) annotation must be placed before every index arguments in any syntactic category. It will generate an index structure for the category, along with lifting and substitution functions able to deal with it.

Remark 2. Indices definition are subject to the following restrictions:

• Constructors having index parameters (as var in Example 1) may not have other arguments.

• Only one index constructor per category is allowed.

bind annotation

Binding annotations are placed before the subterm in which the binding occurs. A binding is defined by two informations: the index category that is bound in the subterm and the number of bound variables. Shortcut can be used, as in Example 1, when only a single variable is bound.

Remark 3.

• Due to the lack of source code static analysis by DBgen, some errors can occur in the generated code when incorrect binding information is provided. More precisely, there is no verification of the index category name given by the user, and the generated source code will not display informative error message in that case.

• The number of bound variables can be a natural number constant, an identifier (i.e. previously defined or declared as a preceeding parameter in the same constructor), or an arithmetic expression combining constants and identifiers with the coq standard operations +, -and *. General expression should be allowed as soon as the developper team will embed the coq expressions parser in the tool.

Complete BNF grammar

Here follows the complete source grammar definition.

exp ::= n | Id | exp + exp | exp -exp | exp * exp 3 Generated code
The output of DBGen is a single file defining a module whose name is exactly the module name given in the source file. This allows the user to take advantage of the separate compilation process of Coq.

The generated module is organized as follows:

Module ModuleName .

--Database and tactics definition.

--De Bruijn structure definition.

--Lifting and substitution function definitions.

--Auxiliary structure and function definitions.

--Basic functions properties w.r.t. index cases.

--Index tactic definition.

--Advanced functions properties and corresponding tactics.

--Main tactic definition.

End ModuleName.

The generated Coq code is quite clear and well presented, this allows the user to check and look for definitions and properties he needs in addition to this short (and incomplete) guide.

Name of generated definitions and functions

The initial De Bruijn structure is defined exactly as in the source code: category, constructor and parameter names will be identical. DBGen generate also a named version of the syntax (with strings constants for variable and explicit binding): a '_' is put as a prefix of every names in order to distinguish them from the De Bruijn structure.

For each generated function, a name is build using the names of the involved syntactic categories in order to automatically generate tactics working with those functions. The process of function name generation might help the end user to easily access the function needed in its own Coq development.

Let us consider the following example (formalization of System F):

Module SYS_F_terms. End SYS_F_terms.

Given such a grammar with syntactic categories τ 1 , , τ n , among which τ i1 , , τ ik contain an index constructor, DBGen will produce, for every τ im a lifting and a substitution function for every categories τ p from which the grammar graph allows to reach τ im (including τ im itself). Hence, for a given pair (τ im , τ p ), the function name will be build from the names of those categories.

• Lifting function name: τ im _lift_in_τ p , its type will be nat -> nat -> τ p -> τ p .

For our example, it gives us three functions: type_lift_in_type, type_lift_in_term and term_lift_in_term.

• Substitution function name: τ im _subst_in_τ p , its type will be τ im -> nat -> τ p -> τ p .

For our example, it gives us three functions: type_subst_in_type, type_subst_in_term and term_subst_in_term.

The developer can use those function, for instance, to define β-reduction (as a predicate reduce): forall t u : term, reduce (app (lam t) u) (term_subst_in_term u 0 t) Some functions process the grammar only once, without the need of a specific treatment for every indexed categories, for instance the translation function from the named syntax to the De Bruijn syntax. In such cases, only the τ p name is used.

Name of generated infrastructure and tactics

At the beginning of the module, a hint database is declared in order to take advantage of coq automation. Its name is build from the module name as follows:

Create HintDb ModuleName _database.

A tactic is then immediatly defined to use this database and perform trivial simplifications and arithmetic proofs (using the library Omega), named crush_tac. This tactic is intended to be quick in its work. Another tactic, named ecrush_tac, is similar to crush_tac but use eauto instead of auto.

Several other tactics are the defined, whose goal is to simplify arbitrary terms containing generated function in order to help the end user to perform subsequent proofs. The main tactic, named dbgen_tac, which combines the strength of all the generated tactics, is probably powerful enough to deal with any specific case. The other tactics can of course be invoked separately by the user, their definitions and names are to be found in the geenrated module.

Usage

The DBGen tool takes as argument the source file name and the output file name. If a file exists whith the output file name, it will be replaced by the generated file.

usage: dbgen [ -version ][ -debug ] in-file out-file

The -version option causes DBGen to print its version number and immediately exit. The -debug option displays informations about the internal treatment for debugging purposes.

Examples

Several examples are provided in the Test subdirectory.

Table of contents

Example 1 .

 1 Here follows the source syntax for ordinary λ-calculus: Module LambdaTerms. Inductive term : Type := | var ((* index *) x : nat) | app (t1 : term) (t2 : term) | lam ((* bind term in *) t : term).

  Inductive cats. cat ::= CatName : Type := constrs | CatName : Type := constrs with cat constr ::= | ConstrName params param ::= ((* index *) ParamName : nat) | ((* bind shifts in *) ParamName : CatName) | (ParamName : CatName) shifts ::= shift , ... , shift shift ::= CatName | [ exp CatName ]

  Inductive type : Type := | tvar ((* index *) i : nat) | tconst (n : nat) | tarrow (A : type) (B : type) | tall ((* bind type in *) A : type). Inductive term : Type := | var ((* index *) x : nat) | app (t1 : term) (t2 : term) | lam (A : type) ((* bind term in *) t : term) | tapp (t : term) (A : type) | gen ((* bind type in *) t : term).

123

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Source syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 index annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 bind annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.3 Complete BNF grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Generated code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Name of generated definitions and functions . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 Name of generated infrastructure and tactics . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5


Guillaume Stoltz

R Gallo

D Poulain

Nathalie Touze

Testing procedure with an

INTRODUCTION

The use of geosynthetic materials is a widespread technical solution for various specific/combined applications in geotechnical structures like watertightness, drainage, filtration and protection. The design of such systems on slope requires the knowledge of friction characteristics at soil-geosynthetic or geosynthetic-geosynthetic interfaces. These characteristics are fundamental in the context of space optimisation that induces steeper slopes (e.g. landfill cells). The measurement of interface friction angle including geosynthetics can be performed using the direct shear box test, following the European standard EN ISO 12957-1 (AFNOR, 2005), and the inclined plane (IP) test, following the European standard EN ISO 12957-2 (AFNOR, 2005). It has been shown that the IP test is more appropriate than the direct shear box test for the friction angle measurement at geosynthetic interfaces under normal stresses lower than 10 kPa [START_REF] Koutsourais | Interfacial friction study of cap and liner components for landfill design[END_REF][START_REF] Izgin | Geomembrane-sand interface frictional properties as determined by inclined board and shear box tests[END_REF][START_REF] Palmeira | Interaction between soils and geosynthetic layers in large-scale ramp tests[END_REF]. However, some recent studies indicated that the standardised testing procedure of the IP test could give a non conservative measurement of the friction angle.

In fact, Reyes [START_REF] Reyes-Ramirez | Use of the inclined plane test in measuring geosynthetic interface friction relationship[END_REF] showed that the standardised testing procedure of the IP test assessed the friction angle 1 50 from a static analysis for conditions that were actually dynamic. [START_REF] Pitanga | Interface shear strength of geosynthetics: evaluation and analysis of inclined plane test[END_REF] showed that the friction angle corresponding to the initiation of sliding and the friction angle corresponding to sliding at constant acceleration were generally lower than 1 50 . However, they did not conclude on the friction angle value that should be considered. Briançon et al. (2011) proposed a modified procedure IP device, called "force procedure". From this procedure, they obtain lower angle friction values than those obtained from the standardised testing procedure of the IP test. From these various studies, it appears that the measurement of the friction angle at geosynthetic interfaces is a pending question.

The aim of this paper is to propose a testing procedure with an IP device that allows the measurement of residual friction angle at geosynthetics interfaces with uniform sliding motion condition. From tests performed on a geomembrane (GMB) -geotextile (GTX) interface, the proposed testing procedure is compared to the standardised one.

The following paragraph depicts the IP device and then describes the standardised testing procedure of the IP test and the proposed testing procedure. Lastly, the experimental program carried out on a geomembrane -geotextile interface is presented.

MATERIALS AND METHOD

Inclined plane device

The IP device consists of a tilting plane onto which an upper box is set up that can move thanks to wheels on rails located on either side of the plane. The length and width of the upper box are both equal Testing procedure with an inclined plane device to assess the residual friction characteristics at geosynthetics interfaces ABSTRACT: This study presents a new testing procedure to assess the residual friction characteristics of geosynthetics-geosynthetics (GSY-GSY) interfaces using an inclined plane (IP) device. The residual friction characteristic corresponds to the friction angle of a GSY-GSY interface determined for a uniform sliding motion condition. A series of tests on a geotextile-geomembrane interface was performed following this residual friction testing procedure. From the results, it was shown that the proposed new testing procedure assessed a residual friction angle 1 res that did not depend on the "sliding history". It was shown that this residual friction angle is more conservative than the friction angle obtained from the European standard EN ISO 12957-2 (AFNOR, 2005). to 1 m. A monitorised winch, managed by computer, allows to control the inclination rate.

Standardised testing procedure

The standard EN ISO 12957-2 (AFNOR, 2005) is a testing procedure to assess the friction angle at geosynthetics or soil-geosynthetic interfaces, under low normal stress using an IP device. The test consists in measuring the plane inclination 2 50 , increasing at constant rate, when the upper box, filled with soil to applied normal stress, slides to a tangential displacement 3 of 50 mm (Figure 1). The length and the width of the tested interface have to be at least equal to 0.3 m. The required inclination rate of the plane is d2/dt = 3.0°±0.5°/min. The initial normal stress 4 0 (for 2 = 0°) is equal to 5.0 ± 0.1 kPa. The normal stress 4 varies during the test as a function of the plane inclination 2, i.e. 4 = 4 0 cos2. To obtain a uniform normal stress on the whole interface area, the front and rear sides of the upper box should be tilted before the test beginning to be inclined close to the vertical during the sliding phase.

The standardised procedure determines the interface friction angle 1 50 (Equation 1) when the plane inclination 2 50 is reached, that is to say when the upper box slides to a tangential displacement 3 of 50 mm. The interface friction angle 1 50 is calculated, according to the free-body diagram displayed on Figure 1, by the following equation:

2 cos W ) 2 ( fr 2 sin W 1 tan ⋅ + ⋅ = (1)
where W s is the weight of the soil and fr(2 50 ) is the resulting force required to hold back the empty upper box.

Three tests on virgin interfaces are required to calculate the arithmetic mean 50 1 , mean friction angle of the studied interface.

It is essential to note that Equation (1) results from a static analysis whereas sliding conditions are dynamic, that is to say the dynamic force of the upper box is neglected. That is why some authors like Reyes [START_REF] Reyes-Ramirez | Use of the inclined plane test in measuring geosynthetic interface friction relationship[END_REF] showed that the standardised procedure was not suitable to determine the friction angle of geosynthetics interfaces.

Residual friction testing procedure

This procedure aims at determining the residual friction characteristics at geosynthetics interfaces. It consists in measuring the force F required to retain the upper box that can slide on the tilting plane, whatever the plane inclination, thanks to a spring. The force F is linked to the tangential displacement 3 by the spring following the relationship:

3 k F ⋅ = (2)
where k (N.m -1 ) is a constant that depends of the spring that has to be chosen in order to allow a tangential displacement at least equal to 20 mm at the end of the test and to hold down a negligible acceleration during the test.

Initially, the spring used to retain the upper box is lightly tightened with a force lower than or equal to 100 N. This initial force permits to avoid an accelerated sliding motion of the upper box. Then, the plane inclination 2 is increased. For a plane inclination 2 0 depending of the tested interface, the beginning of the upper box sliding is observed (tangential displacement 3 >> 0 mm). Then, the test continues and the plane inclination 2 keeps on increasing. The elastic strain of the spring induces a uniform sliding motion of the upper box and the measurement of the force F permits to determine the friction strength T at the interface using Equation 3, deduced from the free-body diagram (Figure 2):

) ( F ) ( fr sin W T s β - β + β ⋅ = (3)
where F(2) is the resulting force required to hold back the upper box.

The friction characteristics of the tested interface can be determined following the (2, T/N) curve. If the (2, T/N) curve presents a peak (T/N) peak , corresponding to the maximal friction strength, and a plateau (T/N) res , corresponding to the ultimate friction strength, it is possible to determine two friction angle values 1 peak and 1 res using respectively Equations 4 and 5. If the (2, T/N) curve does not present any peak, only 1 res can be determined. (5)

The parameter (T/N) is selected to determine the friction angle because, when the ultimate shearing strength is reached, the friction strength T varies due to the variation of the normal force N. It can be noted that Equation 3 is valid if: (1) the upper box is static (condition reached before the beginning of sliding), (2) the upper box has a uniform sliding motion (condition reached in the last part of the test), and (3) the upper box has a negligible acceleration 8 (condition that has to be verified at the beginning of sliding). The equation of the force diagram that includes the dynamic force arisen from the acceleration 8 is expressed as follow:

g W ) ( F T ) ( fr sin W s s γ ⋅ = β - - β + β ⋅ (6) Equation 6 simplifies in Equation 3 if: g 8 2 sin >> (7)
Equation 7 has to be verified throughout the test to determine the friction strength T using Equation 3. If these conditions are not verified, the spring has to be changed to adjust the adequate constant k. In this study, the spring was chosen to have a constant k, defined by Equation 2, equal to 25.10 3 N.m -1 .

Experimental program

The tested interface was a structured geomembrane (with spikes) fixed to the tilting plane on which was a woven geotextile fixed to the upper box. Three tests on virgin interfaces were carried out following the standardised procedure EN ISO 12957-2 (AFNOR, 2005) of the IP test. The slight difference compared to the standardised procedure were the inclination rate which was d2/dt = 1.5°/min instead of 3°/min and the initial normal stress which was 4 kPa. Three tests on virgin interfaces were carried out following the residual friction testing procedure. The three interfaces were denoted A, B and C and the corresponding first test on the virgin interface was denoted A-0, B-0, C-0. To test a non virgin interface, that is to say an interface which has already slid, two additional tests were performed on interfaces A and B, respectively denoted A-1, A-2 and B-1, B-2. For these tests, the normal stress 4 0 = 4 kPa was maintained between the tests that is to say that test A-0 was performed on a virgin interface, then the IP was put back in its initial position and then test A-1 started. Test A-2 followed test A-1. The same sequence was applied to interface B. Lastly, to test the "sliding history" of an interface, the interface B that had slid three times was unloaded (4 = 0 kPa) after test B-3 and then reloaded (4 0 = 4 kPa) to undergo a new series of three tests denoted B'-0, B'-1 and B'-2.

RESULTS AND DISCUSSION

Results from the standardised testing procedure

The friction angle of the studied interface obtained from the standardised testing procedure of the IP test ranged between 25° and 27° (Figure 3). The three tests allowed to assess a mean friction angle of 25°. It is worth noting that the sliding behaviour of the studied interface corresponded to a "sudden sliding".

Results from the residual friction testing procedure

Virgin interfaces A, B and C

For each test, the upper box displacement 3, the Force F retaining the upper box, the calculated friction strength T (Equation 3) and the corresponding T/N parameter are given in Figure 4 as a function of the plane inclination 2. The results show that for 2 in the range 24° to 26°, 3 and F increased significantly. These plane inclination values 2 peak corresponded to a peak value for the friction, approximately equal to 28° for tests A-0 and A-1 and 30° for test A-2. After 2 peak , 3 and F increased linearly with 2 corresponding to a uniform sliding motion of the upper box. This resulted in a plateau for the friction angle, corresponding to the residual friction angle 1 res . From the three tests on virgin interfaces, 1 res could be assessed at 21°.

To apply Equation 3 throughout the test, Equation 7 has to be verified to confirm the negligible acceleration of the upper box at the beginning of sliding. The stronger acceleration for the tests was obtained for test A-2 at a plane inclination of 26.5°. This maximal acceleration was assessed at about 1.10 -4 m.s -2 . Equation 7 with sin 2 equal to 0.446 is then well verified.

The residual friction testing procedure does thus allow to assess a residual friction angle 1 res for a geosynthetic interface for a uniform sliding motion condition.

Successive tests A-1, A-2 and B-1, B-2

Tests A-0 and B-0 carried out on virgin interfaces are compared to tests A-1, A-2 and B-1, B-2 respectively (Figure 5), corresponding to the interfaces that had already slid but had not been unloaded to 0 kPa. The result showed that the peak friction angle 1 peak was around 23° for the four tests A-1, A-2, B-1 and B-2 whereas it was larger than 28° in tests A-0 and B-0 on virgin interfaces. 1 peak is then significantly reduced once the interface has slid for the first time.

For tests A-1, A-2, B-1 and B-2, the residual friction angle 1 res can be assessed between 20° and 20.5°, values very close to those obtained from virgin interfaces (tests A-0 and B-0). Thus, the decrease of 1 peak does not alter the value of 1 res .

Tests on non-virgin interface B'-0, B'-1, B'-2

Results in tests B'-0, B'-1 and B'-2 can be compared to results in tests B-0, B-1 and B-2, carried out on the same interface B but not subjected to unloaded. From tests B-0 and B'-0, the same values of peak friction angle were obtained although the interface B' had already been subjected to sliding during tests B-0, B-1 and B-2. Moreover, test B'-0 presents the same value of residual friction angle than test B-0. It can thus be concluded that the interface B was not damaged by tests B-0, B-1 and B-2. So, the decrease of the friction angle from 1 peak to 1 res does not correspond to a damage of the interface and the behaviour peak-plateau of the curve (2,T/N) is characteristic of the IP test. A maximum value of 1 peak is obtained when the tested interface has never slid. Thus, in the case of an interface which is not damaged during sliding, 1 res does not depend on the "sliding history" unlike 1 peak which is not an intrinsic characteristic of the interface.

Comparison between the standardised and the residual friction testing procedure

The standardised testing procedure of the IP test assesses the interface friction angle in sliding condi-tions by considering a free-body diagram in static condition. Moreover, this friction angle is measured from the interface which has never slid.

From the tests performed following the residual friction testing procedure, it was shown that the friction angle measured during uniform sliding motion condition (1 res ) is lower than the friction angle measured at the interface sliding initiation (1 peak ). Moreover, the peak friction angle has a maximum value at the first interface sliding.

So, if the two testing procedures are compared, it can be concluded that the testing conditions of the standardised procedure are close to those of the residual friction testing procedure that measures the peak friction angle. This is confirmed by friction angles values which are close: 50 1 equal to 26° and peak 1 equal to 29° for the first tests A-0; B-0; C-0. Thus, the standardised testing procedure of the IP test assesses a non conservative friction angle unlike the residual friction testing procedure that assesses a conservative residual friction angle 1 res .

CONCLUSION

This study presents a new testing procedure to assess the residual friction characteristics of geosynthetics interfaces using an IP device. This residual friction testing procedure was compared to the standardised testing procedure of the IP test, the European standard EN ISO 12957-2 (AFNOR, 2005) from tests performed on a geotextile-geomembrane interface.

From the results obtained from the residual friction testing procedure of the IP test, the main conclusions can be drawn:

The proposed new testing procedure assessed a residual friction angle 1 res for the tested geosynthetic interface in uniform sliding motion condition.

The tested interface was not damaged during sliding that permits to show that 1 res does not depend on the "sliding history" unlike 1 peak which is not an intrinsic characteristic of the interface.

The standardised testing procedure of the IP test assesses a non conservative friction angle 1 50 unlike the residual friction testing procedure that assesses a conservative residual friction angle 1 res for the tested interface.

Figure 1 .

 1 Figure 1. Free-body diagram for the standardised procedure of the IP test.

Figure 2 .

 2 Figure 2. Schematic of the residual friction testing procedure of the IP test and corresponding free-body diagram.

Figure 4 .

 4 Figure 3. Results obtained from the standardised procedure of the IP test.

Figure 5 .

 5 Figure 5. (2,T/N) curves and calculated friction angles of the various interfaces obtained from the residual friction testing procedure of the IP test.

  Stoltz 1 , R. Gallo 1 , D. Poulain 2 , N. Touze-Foltz 1 1 Irstea, Hydrosystems and bioprocesses Research Unit, Antony, France. 2 Irstea, Water network, purification and quality Research Unit, Bordeaux, France.

G.


Mark Stillwell

Vivien Frédéric

Henri Casanova

Virtual Machine Resource Allocation for Service Hosting on Heterogeneous Distributed Platforms

We propose algorithms for allocating multiple resources to competing services running in virtual machines on heterogeneous distributed platforms. We develop a theoretical problem formulation and compare these algorithms via simulation experiments based in part on workload data supplied by Google. Our main finding is that vector packing approaches proposed in the homogeneous case can be extended to provide high-quality solutions in the heterogeneous case, and combined to provide a single efficient algorithm. We also consider the case when there may be bounded errors in estimates of performance-related resource needs. We provide a heuristic for compensating for such errors that performs well in simulation, as well as a proof of the worst-case competitive ratio for the single-resource, single-node case when there is no bound on the error.

I. INTRODUCTION

The increasing use of virtual machine technology in the data center, both leading to and reinforced by recent innovations in the private sector aimed at providing lowmaintenance cloud computing services, has driven research into developing algorithms for automatic instance placement and resource allocation on virtualized platforms [START_REF] Andreolini | Dynamic load management of virtual machines in a cloud architectures[END_REF], [START_REF] Urgaonkar | Agile dynamic provisioning of multi-tier internet applications[END_REF], including our own previous work [START_REF] Stillwell | Resource allocation algorithms for virtualized service hosting platforms[END_REF]. Most of this research has assumed a platform consisting of homogeneous nodes connected by a fast local network, e.g., a cluster. However, there is also a need for algorithms that are applicable to heterogeneous platforms.

Heterogeneity comes about when collections of homogeneous resources formerly under different administrative domains are federated into a single logical resource pool (e.g., grid computing, sky computing). Studies have shown that multi-cluster scheduling in these environments can improve performance at the workload level, even for workloads that contain parallel applications with communicating tasks [START_REF] Banen | A measurementbased simulation study of processor co-allocation in multicluster systems[END_REF]. The production cycle is also a common source of heterogeneity -when the time comes to purchase new machines, it generally makes more economic sense to purchase a more powerful machine than was used previously. In budget shops or when a large collection of individually owned (desktop) machines is assembled, one obtains a highly heterogeneous environment in which no two machines may even share the same hardware specification.

In this work we propose virtual machine placement and resource allocation algorithms that, unlike previous proposed algorithms, are applicable to virtualized platforms that comprise heterogeneous physical resources. More specifically, our contributions are:

• We give a formulation of the service placement and resource allocation problem in heterogeneous virtualized platforms. This formulation is in fact more general, even for homogeneous platforms, than our previously proposed formulation in [START_REF] Stillwell | Resource allocation algorithms for virtualized service hosting platforms[END_REF], and allows for specifying minimum allocations of arbitrary resources to satisfy Quality-of-Service (QoS) constraints.

• Using this problem formulation, we extend previously proposed algorithms to the heterogeneous case. • We evaluate these algorithms via extensive simulation experiments, using statistical distributions of application resource requirements based on a real-world dataset provided by Google. We find that combining heterogeneous vector bin packing approaches leads to a practical and efficient solution.

• Most resource allocation algorithms rely on estimates regarding the resource needs of virtual machine instances. We study the impact of estimation errors, propose different approaches to mitigate these errors, and identify a strategy that works well empirically. This paper is organized as follows. In Section II we formalize the resource allocation problem. In Section III we provide an overview of our heuristic algorithms. We describe our experimental procedure for evaluating these algorithms in Section IV and present the obtained results in Section V. In Section VI we discuss the problem of scheduling in the presence of errors in estimated needs, and provide theoretical and experimental results. Section VII discusses related work. Section VIII concludes the paper with a summary of our results and a discussion of future directions.

II. PROBLEM STATEMENT

We consider a service hosting platform composed of H heterogeneous hosts, or nodes. Each node comprises D types of different resources, such as CPUs, network cards, hard drives, or system memory. For each type of resource under consideration a node may have one or more distinct resource elements (e.g., a single real CPU, hard drive, or memory bank). In this work we assume that all resource elements of the same type on a given host are homogeneous. That is, we do not consider resources that comprise heterogeneous sub-units, such as the Cell TM processor [START_REF] Buttari | Limitations of the PlayStation 3 for high performance cluster computing[END_REF]. Services are instantiated within virtual machines that provide analogous virtual elements. For some types of resources, like system memory or hard disk space, it is relatively easy to pool distinct elements together at the hypervisor or operating system level so that hosted virtual machines can effectively interact with only a single larger element. For other types of resources, like CPU cores, the situation is more complicated. These resources can be partitioned arbitrarily among virtual elements, but they cannot be effectively pooled together to provide a single virtual element with a greater resource capacity than that of a physical element. For example, with current technology, a virtual machine instance with 3 virtual processors can run on a dual-core system with each of the virtual CPUs receiving 66.6% of the processing power of a single physical CPU [START_REF] Gupta | Comparison of the three CPU schedulers in Xen[END_REF], but it is impossible to pool two physical CPUs together to provide a single virtual CPU that is more powerful than the individual physical CPUs. For these types of resources, it is necessary to consider the maximum capacity allocated to individual virtual elements, as well as the aggregate allocation to all virtual elements of the same type.

Thus, each node is represented by an ordered pair of Ddimensional vectors. The elementary capacity vector gives the capacity of a single element in each dimension while the aggregate capacity vector gives the total resource capacity counting all elements. In practice, each value of the aggregate capacity vector is expected to be an integer multiple of the corresponding value in the elementary capacity vector, but our proposed approach does not rely on this assumption.

An allocation of resources to a virtual machine specifies the maximum amount of each individual element of each resource type that will be utilized, as well as the aggregate amount of each resource of each type. Expectedly, an allocation is thus represented by two vectors, a maximum elementary allocation vector and an aggregate allocation vector. Note that in a valid allocation it is not necessarily the case that each value in the second vector is an integer multiple of the corresponding value in the first vector, as resource demands may be unevenly distributed across virtual resource elements. For example, consider an application that uses two virtual CPUs: The application consists of one CPUbound process that can utilize 100% of a physical CPU, and of one I/O-bound process that uses at most 10% of a physical CPU. The aggregate CPU resource allocation needed to run this service without degrading performance would then be 110% (easily achieved on a dual-core system), which is not an integer multiple of the maximum elementary resource allocation of 100%.

When determining how much of each resource to allocate to a virtual machine it is necessary to consider both the rigid requirements of the service as well as its fluid needs. The requirements for service j are given by an ordered vector pair (r e j , r a j ) that represents the resource allocation needed to run the service at the minimum acceptable service level. If this requirement cannot be met, then resource allocation fails. The needs of the service are given by a second ordered vector pair (n e j , n a j ) that represents the additional resources required to run the service at its maximum level of performance when it is by itself on a reference machine. While in general the most sensible reference machine is the best one for running the service on the target platform, this is not imposed. There are situations where it may make sense to set the needs based on some other criteria: the system or pricing structure may impose maximum virtual machine allocations that are less than the maximum of what is physically available, or it may be desirable to compare the relative performance of the same workload across a variety of platforms.

In this formulation of the problem, rather than attempting to maximize the performance of individual applications we choose to focus on maintaining an appropriate proportional allocation of resources, as resource allocations are known to be transformable into higher level service objectives [START_REF] Chen | Translating service level objectives to lower level policies for multitier services[END_REF]. Toward this end, we define the yield of a service to be a value between 0 and 1, representing the relative performance of that service. A service with an assigned yield of 0 would be running at the lowest acceptable rate of service for a resource allocation to not be considered a failure, while a service with an assigned yield of 1 would be running at the maximum performance possible on the reference machine. The allocation needed to run a service j with yield y j is then defined by the couple (r e j +y j n e j , r a j +y j n a j ). This linear correlation between resource consumption levels in different dimensions is established in the literature [START_REF] Dolev | No justified complaints: On fair sharing of multiple resources[END_REF] and easily justified for a wide class of applications. Benchmarking studies have validated the approach for scientific workload applications [START_REF] Becerra | Batch job profiling and adaptive profile enforcement for virtualized environments[END_REF].

We can now define the service placement and resource allocation problem precisely: maximize the minimum yield over all services. This amounts to making the least satisfied service as satisfied as possible, thus promoting both performance and fairness. This objective is directly motivated by known results derived in the context of stretch optimization [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF], [START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF]. In particular, it is well known that simply minimizing the average stretch (and thus maximizing the average yield) is prone to starvation. For the single-node case maximizing the minimum yield addresses the problem of fair-sharing of multiple resources, potentially in the presence of multiple bottlenecks as discussed in Dolev et al. [START_REF] Dolev | No justified complaints: On fair sharing of multiple resources[END_REF], though we choose to focus on maximizing the performance of the most-penalized service, rather than ensuring that services receive their fair share of bottleneck resources. Figure 1 illustrates the above for a simple example with two nodes and one service. Node A comprises 4 cores and a large memory. Its resource capacity vectors show that each core has elementary CPU capacity 0.8 (i.e., no single virtual CPU can run at 0.9 CPU capacity on this node) for an aggregate capacity of 3.2. Its memory has capacity 1.0, with no difference between elementary and aggregate values because the memory, unlike cores, can be partitioned arbitrarily. Node B has two, more powerful, cores, each of elementary capacity 1.0, and a smaller memory. The service has a 0.5 elementary CPU requirement, and a 1.0 aggregate CPU requirement. For instance, it could contain two threads that must each saturate a core with 0.5 capacity. The memory requirement is 0.5. The elementary CPU need is 0.5 and the aggregate is 1.0. The memory need is 0.0, meaning that the service simply requires a 0.5 memory capacity. The figure shows two resource allocations one on each node. On both nodes the service can be allocated the memory it requires. If the service is placed on Node A, then the after elementary CPU requirement of 0.5 is satisfied, only 0.8 -0.5 = 0.3 of the elmentary CPU capacity is left over to meet elementary CPU needs. Thus, the maximum yield possible for the service with this allocation is 0.3/0.5 = 0.6.

The aggregate CPU capacity of the machine is not a limiting factor since this value, 3.2, exceeds the total of the aggregate requirements and needs of the service (2.0). On Node B, the service can fully saturate two cores, completely satisfying all of the elementary and aggregate requirements and needs, for a yield of 1.0. If there is only one service to consider, then placing this service on Node B maximizes the (minimum) yield.

III. ALGORITHMS

The minimum yield maximization problem defined in the previous section is NP-hard in the strong sense via a straightforward reduction to vector-packing (in fact, the reduction to vector packing also denies the existence of an asymptotic polynomial-time approximation scheme) [START_REF] Wöginger | There is no asymptotic PTAS for twodimensional vector packing[END_REF]. We therefore seek heuristic algorithms that work well in practice for a wide range of relevant scenarios.

A. Linear Program Formulation

Our problem can be framed as a linear program (LP) with both integer and rational variables, i.e., a Mixed Integer Linear Program (MILP). Using 0 ≤ j < J to index the services, 0 ≤ h < H to index the nodes, and 0 ≤ d < D to index the resource dimensions, we define the following variables: e jh is set to 1 if service j is placed on node h, or 0 otherwise; and y jh is the yield of service j on host h. We use r e jd (resp. r a jd ) to denote the elementary (resp. aggregate) resource requirement of service j for resource d, n e jd (resp. n a jd ) to denote the elementary (resp. aggregate) resource need of service j for resource d, and c e hd (resp. c a hd ) to denote the elementary (resp. aggregate) resource capacity of node h for resource d. Given these notations, the constraints of the MILP are given by Equations 1-7.

∀j, h e jh ∈ {0, 1}, (1) ∀j
, h y jh ∈ [0, 1], (2) ∀j
Constraints 1 and 2 define the ranges of the variables. Constraint 3 states that a service must be placed on exactly one node. Constraint 4 states that a service has a non-zero yield only on the node on which it is placed. Constraint 5 states that the elementary resource capacities of the nodes are not overcome, and Constraint 6 states that the aggregate resource capacities of the nodes are not overcome. Finally, Constraint 7 defines variable Y as the minimum of the yields of all services. The optimization objective is thus to maximize Y .

B. Exact and Relaxed Solutions

We have implemented a resource allocation problem solver that can use either the Gnu Linear Programming Toolkit (GLPK) [13] or the IBM iLog CPLEX Optimization Studio [START_REF]CPLEX[END_REF] as back-end MILP solvers. Since solving a MILP takes exponential time, for large instances we relax the problem by assuming that all variables are rational. The MILP becomes a rational LP, which can be solved in polynomial time in practice. The solution of the rational LP may be infeasible but has two important uses. First, the achieved minimum yield is an upper bound on the solution of the MILP. Second, the rational solution may point the way toward good feasible solutions as seen in the next section.

C. Algorithms Based on Relaxed Solutions

We propose two algorithms, RRND and RRNZ, that use a solution of the rational LP as a basis and then round off rational e ij values. Due to licensing restrictions, we could not run large numbers of CPLEX solvers. Consequently, we use the solutions produced by GLPK.

1) Randomized Rounding (RRND): For each service j (taken in an arbitrary order), this algorithm allocates it to node h with probability e jh . If the service cannot fit on the selected node because of memory constraints, then probabilities are adjusted and another attempt is made. If all services can be placed in this manner then the algorithm succeeds. Such a probabilistic approach has been used successfully in previous work [START_REF] Marchal | Steadystate scheduling of multiple divisible load applications on wide-area distributed computing platforms[END_REF].

2) Randomized Rounding with No Zero probabilities (RRNZ): One problem with RRND is that a service, j, may not fit (in terms of resource requirements) on any of the nodes, h, for which e jh > 0, in which case the algorithm would fail to generate a solution. To remedy this problem, we first set each zero e jh value to , where << 1 (we use = 0.01). For those problem instances for which RRND provides a solution RRNZ should provide nearly the same solution, but RRNZ should also provide a solution for some instances for which RRND fails.

D. Greedy Algorithms

In general greedy algorithms operate by making a series of fast, locally-optimal decisions. They run quickly, but may provide poor results for some problem instances. One way to deal with this issue is to run several greedy algorithms and choose the best solutions from those computed. In our previous paper [START_REF] Stillwell | Resource allocation algorithms for virtualized service hosting platforms[END_REF], in the context of homogeneous platforms, we proposed a family of greedy algorithms that first sort the services under consideration and then go through the list in sorted order, selecting the best node for each item by various criteria. We considered the following service sorting strategies: S1: no sorting; S2: decreasing order by maximum need; S3: decreasing order by sum of needs; S4: decreasing order by maximum requirement; S5: decreasing order by sum of requirements; S6: decreasing order by the maximum of sum of requirements and sum of needs; and S7: decreasing order by the sum of requirements and needs. We also proposed a number of strategies for selecting a node from the set of those capable of running the current service: P1: choose the node with the most available resource capacity in the dimension of maximum need; P2: choose the node with the minimum ratio of sum of loads over all dimensions to sum of resource capacities over all dimensions after service placement, P3: choose the node with the least remaining capacity in dimension of largest requirement (best fit), P4: choose the node with the least aggregate available capacity (best fit), P5: choose the node with the most capacity remaining in dimension of largest requirement (worst fit), P6: choose the node with the most total available resource (worst fit), P7: choose the first node (first fit). Each sorting strategy can be paired with any selection strategy to obtain a greedy algorithm, for a total of 7 × 7 = 49 combinations. Given that these 49 algorithms can be executed quickly, we simply define the METAGREEDY algorithm which runs all 49 greedy algorithms and picks the solution that results in the largest minimum yield.

E. Vector-Packing (VP) Algorithms

As has been noted in the literature, resource allocation is closely related to bin packing [START_REF] Coffman | An application of bin-packing to multiprocessor scheduling[END_REF]. Bin-packing can be extended to vector-packing [START_REF] Csirik | On multidimensional vector bin packing[END_REF], also called multi-capacity bin-packing by some authors [START_REF] Leinberger | Multi-capacity bin packing algorithms with applications to job scheduling under multiple constraints[END_REF], in the case where multiple resource dimensions are under consideration. In our previous work we discussed a straightforward method of applying any vector packing heuristic to our resource allocation problem with the objective of maximizing the minimum yield: since the amount of each resource that needs to be allocated to a given service is fixed for a particular yield value, it is possible to determine whether or not a given heuristic can find a solution for that yield value. Since we seek to maximize the minimum yield value, without loss of generality we can assume that all services have the same yield. Thus, we perform a binary search for the largest yield for which the heuristic can find a solution. We stop when the upper and lower bounds of the binary search are within some threshold distance of each other (0.0001 in our simulation experiments).

The largest source of difficulty in designing vectorpacking heuristics is that there is no single unambiguous definition of vector "size" or "order". Any mapping from vectors to a scalar metric can be used, and the use of different metrics must be evaluated in simulation as analytical comparison is typically not feasible. We consider the following metrics: size of maximum dimension (MAX), sum of all dimensions (SUM), ratio of maximum and minimum dimension (MAXRATIO), and the difference between maximum and minimum dimensions (MAXDIFFERENCE). We also consider ordering the vectors lexicographically (LEX), though the ordering of the dimensions is necessarily arbitrary. Some strategies may also specify NONE, to leave items in their natural order and not attempt sorting. Since there are 5 mappings of vectors to scalars under consideration that can be used to sort vectors in either ascending or descending order, and one option to not sort vectors, we consider 11 distinct strategies for vector sorting. In general, we should expect algorithms that sort items in decreasing order by size and bins in increasing order by capacity (e.g., algorithms that first try to put the largest items into the smallest bins) to have the best performance. For each of the sorting options, we can now define vector packing algorithms as follows.

1) First and Best Fit: Once the items are sorted using one of the sorting strategies, the First Fit algorithm places each item in this order in the first bin in which it fits using an arbitrary bin order. The Best Fit algorithm considers bins in descending order of the sum of their loads across all dimensions.

2) Permutation-Pack and Choose-Pack: The Permutation-Pack and Choose-Pack heuristics for multicapacity bin packing, also known as vector-packing, were first proposed by Leinberger et al. [START_REF] Leinberger | Multi-capacity bin packing algorithms with applications to job scheduling under multiple constraints[END_REF] The basic strategy used by these algorithms is to go bin-by-bin and select items that go against the current "capacity imbalance" in the first w most-loaded dimensions. The idea behind this strategy is to keep a bin from becoming full in one dimension while it still has remaining capacity available in other dimensions. The value of w is called the "window size" for the algorithm.

Let us use D to denote the number of dimensions of bin and item vectors. To select an item to put into the current bin, the Permutation Pack algorithm ranks the dimensions of the current bin in ascending order by their load and ranks the dimensions of each of the items in descending order by their size. The items are then ordered by how well their dimension ranking matches against that of the current bin in the first w dimensions. An item that has a permutation matching that of the bin will have its largest requirement in the dimension where the load on the bin is smallest and its smallest requirement in the dimension where the load on the bin is largest. The Choose Pack algorithm relaxes this ordering slightly and only considers which dimensions fit within the window, but not their relative ordering. It should be noted that when the window size is 1, the Permutation Pack and Choose Pack algorithms operate identically.

The implementation proposed by Leinberger et al. in [START_REF] Leinberger | Multi-capacity bin packing algorithms with applications to job scheduling under multiple constraints[END_REF] separates the items into D! lists-one for each potential permutation of item dimensions imposed by ordering the dimensions in descending order by their size. The items in these lists are further sorted by one of the vector sorting criteria discussed previously. For each bin it selects items by going through these lists in a lexicographic order determined by the permutation imposed on the bin dimensions by sorting them in ascending order by their current load. That is, it first looks for an item in the list with a permutation matching that of the current bin. If no such item can be found then it looks for an item in the list where the positions of the two least important dimensions are reversed. This continues until an item that fits in the current bin is found, with items whose dimensional permutation is opposite of the current bin considered last. If the algorithm cannot find any item that fits in the current bin, then it moves on to the next one.

In the case that D! ≤ J (i.e., for small D) the algorithm essentially makes multiple passes through all of the items, selecting one to place in the current bin at each step, and so is order O(J 2 ). For the case when D! >> J, Leinberger et al. note that searching for the matching list can require O(D!) operations; In fact, if these permutations are not first mapped into an easily comparable set then each comparison of permutations is an O(D) operation, potentially leading to an overall cost of O(J 2 + JDD!) operations for this heuristic. Their proposal to use a window to check only the first few, most important, dimensions reduces the cost of the search to O(DD!/(D -w)!), for an overall complexity of O(J 2 + JDD!/(D -w)!).

To reduce the high complexity of this algorithm, we have made the following improvement. Instead of needlessly splitting the items into D! lists, many of which may be empty when D is large, and checking each list in order, we simply assign each item a sorting key by mapping its dimension permutation into the permutation space defined by the bin's dimensional ordering, a O(JD) operation. For example, consider a bin with dimensional ordering (4, 2, 3, 1) in a 4-dimensional case (meaning that its largest capacity is its 4th dimension, the next largest capacity is its 2nd dimension, etc.), and an item with ordering (3, 1, 4, 2) (i.e., its largest requirement is its 3rd dimension, its next largest demand is its 1st dimension, etc.). The key assigned to this item is then (3, 4, 1, 2) (the 1st dimension of the item ordering is the 3rd dimension of the bin ordering, the 2nd dimension of the item ordering is the 4th dimension of the bin ordering, etc.). Once these permutations are computed for each item, we simply chose the first item in the lexicographic order of the permutations. In our example, an item with permutation (1, 2, 3, 4) would be perfectly fitted for the bin. No sorting of the services is involved and a single scan through the list is necessary, or O(JD) operations. Thus, our implementation is O(J 2 D), which is a significant improvement when D is large, or O(J 2 w) if a window is used.

3) METAVP: At each step of the binary search, this algorithm iteratively applies all of the above vector packing strategies until a solution is found, including all of the options for sorting items-3×11 = 33 strategies overall for each step of yield optimization. METAVP necessarily performs at least as well as all previously discussed algorithms, but also has much longer run time.

4) Heterogeneous Vector-Packing (HVP) Algorithms: These algorithms explicitly consider the heterogeneity of the platform and try to sort the vector bins. The Best-fit, Permutation-Pack algorithm is also modified to consider total remaining capacity rather than total load.

5) METAHVP:

This algorithm tries all of the above heterogeneous bin-packing heuristics at each step of the binary search. Since Best-Fit and Permutation-Pack can consider bins in sorted order, but Best-Fit imposes its own criteria on bin selection, this is is 11 + 2 × 11 × 11 = 253 strategies overall. METAHVP necessarily performs at least as well as any of the HVP algorithms, but its run time can be high.

IV. SIMULATION EXPERIMENTS

Though we provide a general framework capable of representing an arbitrary number of resource constraints, in practice the two most important resources to consider are processing power (CPU) and memory. Often, these are the only resources with consumption levels reported in log files, and thus the only ones for which it is possible to build reasonable statistical models of demand. These are also resources for which current virtualization technology provides accurate performance throttling and isolation. For these reasons in our simulation experiments we choose to focus on the two-dimensional problem with one CPU resource dimension and a memory resource dimension.

In order to control the relative levels of node heterogeneity, rather than reflecting the statistics of any actual set of machines we draw aggregate CPU and memory capacities from a normal distribution with a median value of 0.5, limited to minimum values of 0.001 and maximum values of 1.0. The coefficient of variation is varied from 0.0 (completely homogeneous) to 1.0. To generate consistent elementary capacities, we assume that despite differences in total computational power all machines are quad core, and therefore have CPU elements with 1/4 the aggregate machine power.

To instantiate service resource requirements and needs, we use a production dataset provided by Google Inc. [START_REF]Google cluster data archive[END_REF]. As this dataset only provides information about the number of requested cores and the percentage of system memory used, we assume that aggregate CPU needs of services are proportional to the number of requested cores, while elementary CPU requirements are equal to the same reference value for all services.

We consider scenarios with 64 hosts, 100, 250 and 500 services and coefficient of variation values 0.0 to 1.0 in increments of 0.025 For each scenario we generate 100 random instances, for a total of 12,300 base instances. Each base instance is then use to generate a family of scaled problem instances with specified memory slack, defined at the fraction of total memory that would remain free in a successful resource allocation. The memory slack is a value between 0 and 1 that quantifies the hardness of the instance in terms of memory bin packing, with a low value corresponding to a more difficult instance. We experiment with slack values between 0.1 and 0.9, in 0.1 increments. We also scale CPU needs so that the sum of all service CPU needs is equal to the sum of all CPU resources available.

V. EXPERIMENTAL RESULTS

We evaluate a large number of algorithms over a large dataset, and these algorithms can vary both in terms of how often they are able to find solutions to problem instances (success rate) and how good their solutions are when found (minimum yield). It is thus difficult to provide a single metric that can be used as a basis for determining an overall winner. For this reason we first perform pairwise comparisons of the algorithms using the following metrics: (i) Y A,B : the average percent minimum yield difference between A and B, relative to the minimum yield achieved by B, computed on instances for which both algorithms succeed. (ii) S A,B : the percentage of instances for which A succeeds and B fails, minus the percentage of instances where B succeeds and A fails; and For both measures, a positive value means an advantage of A over B. Since no single simple vector packing heuristic can perform as well as the aggregate METAVP and METAHVP algorithms in terms of either failure rate or achieved minimum yield, for now we only consider the RRND, RRNZ, METAGREEDY, METAVP, and METAHVP algorithms.

Pairwise comparisons of the major heuristics under consideration are given by Table I. Perhaps surprisingly, RRND can lead to much better performance than RRNZ, but it has an extremely low success rate relative to the other algorithms, so is dropped from further consideration. META-GREEDY widely outperforms RRNZ both in terms of success rate and minimum yield, but is in turn beaten my METAVP. The METAVP algorithm is itself outperformed by METAHVP.

While not large, the advantage of METAHVP over METAVP becomes more pronounced as the number of services per node increases. METAVP solves 15,376 of the 36,000 100-service instances, while METAHVP only solves 1 additional instance (METAVP does not solve any instances not solved by METAHVP). METAHVP achieves yield values more than 0.002 greater than METAVP on 311 instances, while METAVP beats METAHVP by the same margin on only 1. The average yield values on instances solved by both algorithms are close together: 0.504 for METAHVP and 0.503 for METAVP. METAVP solves 30,596 of the 36,900 250-service instances, while METAHVP solves an additional 162 instances (METAVP does not solve any instances not solved by METAHVP). METAHVP achieves yield values at least 0.002 higher on 17,256 of those instances, while METAVP beats METAHVP by at least the same amount on 86 instances. The average yield values on instances solved by both algorithms is larger (0.820 for METAHVP and 0.803 for METAVP). Both algorithms solve 36,844 of the 36,900 500-task instances (neither algorithm solves any instances not solved by the other). METAHVP achieves yield values that are at least 0.002 higher on 28,680 of these instances, compared to the 44 where METAVP achieves a higher yield value by the same margin. METAHVP achieves an average yield of 0.897, compare to 0.850 for METAVP. While there is no commonly accepted target for virtual machines per node, 8 is probably reasonable in current production platforms, which corresponds to our 500-service instances.

Higher levels of consolidation are likely to be expected, thus increasing the advantage of METAHVP over METAVP.

To gain more insight into our results, Figure 2 shows results for instances with 500 services and a memory slack of 0.3. Each data point (x, y) corresponds to one problem instance and one of RRNZ, METAGREEDY, or METAVP.

x is the coefficient of variance of the CPU and memory capacities of the nodes in the platform, and y is the difference between the achieved yield and that achieved by METAHVP. Points on the x = 0 axis are for perfectly homogeneous platforms. Points below the y = 0 axis correspond to instances in which METAHVP does not achieve the best yield. Figure 3 shows the same information for problem instances where the CPU was held homogeneous (i.e., all servers have a CPU resource of 0.5), while Figure 4 does the same for memory. As expected based on our previous set of results, METAGREEDY never outperforms METAHVP, and is generally worse than METAVP. RRNZ is never a contender and leads to markedly poorer performance than the other algorithms on most instances, without ever outperforming METAHVP. METAHVP is the best algorithm in all three figures. The interesting observation is that while METAVP performs close to METAHVP over a wide range of problem instances, its performance relative to METAHVP time than METAVP by a factor 3 on the average, requiring more than 6 seconds to solve problem instances with 500 tasks. Recall that these results are for "only" 64 nodes. Given that production cloud platforms comprise orders of magnitude more nodes, and thus hosts orders of magnitude more services, using METAHVP in production systems is likely impractical. For example, METAHVP requires an average of 134.52 seconds when run on a 2.27 Ghz Intel Xeon processor with 512 hosts and 2000 services.

A. METAHVPLIGHT

Given the high run time of METAHVP, in this section we design a version of METAHVP called METAHVPLIGHT that includes only a subset of the HVP algorithms.

An exploration of our results shows that no single (small) group of algorithms emerges as a clear winner, and in fact every single algorithm is best on some instances. To filter out the worst performing algorithms, we sorted the basic HVP algorithms first by success rate, then by average achieved minimum yield. Looking at the top 50 algorithms for each dataset, some trends are clear. 1) The Best-Fit, First-Fit, and Permutation-Pack approaches all perform well when paired with appropriate item and (except in the case of Best-Fit) bin sorting strategies, and each outperforms the others on a small subset of the instances. 2) The descending by MAX, SUM, and MAXDIFFERENCE item sorting strategies are those used by most of the high-performing algorithms, and MAXRATIO can also be a good item sorting strategy for some algorithms. 3) The ascending by LEX (considering CPU needs before memory), MAX, and SUM bin sorting strategies were unsurprisingly among the most successful, but also present were descending by MAX, MAXDIFFER-ENCE, and MAXRATIO, and the option to not sort bins (NONE), which was somewhat of a surprise.

From these observations we built a simple METAHVP-LIGHT algorithm that uses essentially the same procedure as METAHVP, but only considers the descending by MAX, SUM, MAXDIFFERENCE and MAXRATIO item sorting strategies and the ascending by LEX, MAX, SUM, and descending by MAX, MAXDIFFERENCE and MAXRATIO bin sorting strategies, as well as the option to not sort bins. This reduces the number of heterogeneous vector packing heuristics considered at each step of yield optimization from 253 to 4 + 2 × 4 × 7 = 60.

We ran METAHVPLIGHT on all our problem instances and observed the following. Both METAHVP and METAHVPLIGHT successfully solve the same set of 100service instances (15,377 out of 36,900) and achieve the same average minimum yield of 0.504. METAHVPLIGHT solves 30,737 of the 250-service instances, and METAHVP solves an addition 21 instances that METAHVPLIGHT does not solve. On the instances that both algorithms solve METAHVP achieves an average minimum yield value of 0.817 versus 0.814 for METAHVPLIGHT. Finally, both algorithms solve the exact same 36,844 (out of 36,900) 500task instances. On these instances both algorithms achieve an average minimum yield of 0.897 .

These results show that METAHVPLIGHT expectedly achieves slightly lower solution quality on a few instances, but the overall performance is quite Importantly, its run time is drastically lower than that of METAHVP. For instance, on the 512-node and 2000-service instance reported in the previous section, METAHVPLIGHT runs in 15.25 seconds as compared to the 134.52 needed by METAHVP.

B. Results Conclusion

• Algorithms based on vector packing, known to work well in homogeneous settings, can be adapted to handle heterogeneity and outperform linear programming and greedy approaches.

• These algorithms do much better than other approach for tightly constrained and highly heterogeneous problem instances. No single algorithm, however, emerges as the best. This motivates a "brute-force" approach that runs many of the algorithms and selects the best solution among those produced. • The brute-force approach leads to unreasonably high times to solution, but one can engineer a "light" algorithm that only runs a smaller subset of the base algorithms. This solution improves the runtime by nearly a factor 10 while leading to solutions of sensibly equivalent quality.

VI. THE EFFECTS OF ERROR IN CPU NEEDS ESTIMATES

An important consideration for any scheduling algorithm is how well the resource requirements and needs are known. Although some work has been done with regards to memory consumption [START_REF] Batat | Gang scheduling with memory considerations[END_REF], it is in general difficult if not impossible to know all of a service's resource requirements before it is run. One option is to rely on benchmark results for services that comprise the workload [START_REF] Urgaonkar | Resource overbooking and application profiling in shared hosting platforms[END_REF]. But any service that performs data-dependent computations or reacts to a user-dependent workload will necessarily have variations in moment-to-moment requirements each time it runs. CPU needs estimation in particular can be problematic, as the use of this resource tends to be "noisy" and/or "spikey" and prone to varying over time [START_REF] Abrahao | Characterizing application workloads on CPU utilization for utility computing[END_REF].

An interesting question is, given a set of erroneous CPU need estimates, how do errors affect the minimum yield achieved by our algorithms. In particular, how would our algorithms compare to a baseline algorithm that assumes no knowledge of CPU needs? In the total absence of knowledge the best policy is likely to distribute services as evenly as possible across the available nodes (as done in the "scheduling in the dark" approach [START_REF] Edmonds | Scheduling in the dark[END_REF]) and then use a work-conserving scheduler that makes some effort to distribute available cycles fairly (for some definition of fairness) among processes. It is common for modern virtual machine CPU scheduling systems to offer a work-conserving mode in which processes are given access to the CPU in proportion to administrator-assigned weights. For instance, two CPU intensive competing virtual instances would be initially restricted to using at most 50% of the available CPU cycles, but if one of the instances reduced its CPU consumption, then the other would be allowed to use the unused portion of the CPU resource [START_REF] Gupta | Comparison of the three CPU schedulers in Xen[END_REF].

We propose an iterative algorithm for determining the CPU consumption of competing services when their needs are not known precisely by the scheduler. First, each service is allocated a portion of the node relative to its weight (e.g., if the weights of all currently active services sum up to 100, and a given service is assigned a weight of 30, then it will initially be able to use up to 30% of the CPU). Any service with actual needs that are less than or equal to its initial allocation is considered "satisfied" and any portions of the CPU that are left unused (because some services have needs strictly less than their initial allocation) are pooled together and redistributed to remaining unsatisfied services again by their weight. This process continues until either all of the services are satisfied or there is no more CPU available. We assume that CPU allocations cannot be smaller than some epsilon (0.0001 in our simulations) in order to avoid potentially infinite recursion. We consider three methods for allocating CPU (or other dynamic) resources to competing tasks once they are assigned to a particular node. The first, ALLOCCAPS, simply assigns limitations on CPU utilization based on the proportion required to maximize the minimum yield on the current node, given known estimates of CPU utilization. The second, ALLOCWEIGHTS, uses the values computed to maximize the minimum yield on the current node as weights, assuming the use of a work conserving scheduler. The third, EQUALWEIGHTS, assumes a workconserving scheduler as well, but simply assigns equal weights to all competing services.

A. A Theoretical Result

It turns out that, for the EQUALWEIGHTS algorithm, one can quantify how far the obtained solution is from the optimal, as stated in the following theorem.

Theorem 1: In the on-line minimum-yield maximization resource allocation problem for a single dimension, EQUAL-WEIGHTS is 2J-1 J 2 competitive in the worst case, and there is an instance that achieves exactly this performance ratio.

Proof: Let {n a j } J j=1 be a one-dimensional set of aggregate service needs (we do not consider elementary needs in this proof). By an abuse of notation, let us assume that the values in this set represent scalar values rather than one-dimensional vectors. As the scheduler is work-conserving, for any resource allocation where J j=1 n a j ≤ 1, no service will have a yield of less than 1, therefore let us assume the opposite, that is, J j=1 n a j > 1. Since the EQUALWEIGHTS algorithm does not take needs into consideration when allocating resources to unsatisfied services, the services with the minimum yield will necessarily be those with the maximum need. Let us denote na = max{n a j } J j=1 , and let ĵ be an arbitrary service with need na . Clearly n a ĵ = na > 1 J . Case 1: All of the services in the system have needs of at least 1 J . The allocation to the service with need na is thus 1 J and the minimum yield achieved by EQUALWEIGHTS is no less than 1 J na . The yield achieved by the optimal algorithm is

1 J j=1 n a j .
We compute the lower bound on the competitive ratio of EQUALWEIGHTS as follows:

1 J na 1 J j=1 n a j = J j=1 n a j J na ≥ J-1 J + na J na ≥ J-1 J +1 J = 2J-1 J 2
Case 2: There is at least one service (clearly not ĵ) with a need of less than 1 J . Denote the fraction of the resource consumed by services other than ĵ as S. As ĵ will consume at least 1 J of the resource, S ≤ J-1 J . Since the scheduler is work conserving and the sum of the resource needs is greater than 1, it must be the case that 1-S ≤ na . The allocation to the service ĵ is thus 1 -S and the minimum yield achieved by EQUALWEIGHTS is 1-S na . The lower bound on the ratio to the optimal is is thus:

1-S na 1 J j=1 n a j = ( na +S)(1-S) na ≥ (1 + S)(1 -S) = 1 -S 2 ≥ 1 -( J-1 J ) 2 = 2J-1 J 2
A problem instance that achieves this ratio is n a 1 = 1, n a j = 1 J for j = 2, ..., J.

B. Error Experiments

Starting from the same data set as in Section V, we selected those problems with slack values of 0.2, 0.4, 0.6, and 0.8 and COV values of 0.0, 0.5 and 1.0. We then specified maximum error values from 0.0 to 0.3 in increments of 0.02. For each of these problems and maximum error values we perturbed the CPU needs by selecting values between the negative and positive maximum value from a uniform random distribution and adding this error to the true total CPU needs (to a minimum of 0.001). Elementary CPU needs were perturbed so as to maintain the same proportion with the aggregate needs are before the error was applied. It should be noted that an average node in our simulations has an aggregate CPU power of 0.5. Services in the 100service case have a mean CPU need of 0.317, while those in the 250-service case have a mean CPU need of 0.127, and those in the 500-service case have mean CPU need of 0.063. Thus, errors can be large in proportion to average service needs.

These modified values were then used by the METAHVP algorithm to assign nodes and CPU allocations to the services. After the services were mapped to nodes we assessed performance based on the following criteria: 1) the expected yield for each, assuming the estimates had been completely correct; 2) the minimum actual yield, if the output of METAHVP was used used to allocate CPU using the ALLOCCAPS algorithm; 3) the minimum actual yield, if the output of METAHVP was used as input to the ALLOCWEIGHTS algorithm; and 4) the minimum actual yield, assuming that after services are assigned to nodes CPU allocations were determined using the EQUALWEIGHTS algorithm.

Unsurprisingly, using the ALLOCCAPS algorithm is a losing proposition in the presence of errors, and we found that it consistently leads to poor performance (worse than the zeroknowledge case) when the error exceeded approximately 30% of the average service need (i.e., 0.08 in the 100-service case, 0.04 in the 250-service case, 0.02 in the 500-service case). Initially, simply switching to the ALLOCWEIGHTS or EQUALWEIGHTS algorithm can help for some instances, but the average-case performance of ALLOCWEIGHTS closely tracks that of ALLOCCAPS, while EQUALWEIGHTS gives initially worse results, but can often remains better than zeroknowledge until the maximum error exceeds the average service need.

A likely reason for poor performance under these circumstances is underestimating the needs of relatively small services. To combat this problem we propose rounding up the estimate of each CPU need to a minimum threshold value. Estimates larger than this threshold are not affected. This allows the algorithm to use some of the information about relative service sizes to make placement decisions, while effectively holding some of the CPU resource in reserve in order to avoid penalizing those services that are the most vulnerable. This strategy necessarily requires the use of ALLOCWEIGHTS or EQUALWEIGHTS rather than ALLOCCAPS to be successful, as it can result in allocating small services more CPU than they need. Figures 5, 6 and 7 plot the average minimum achieved yield vs. the maximum estimation error for 100-service, 250-service, and 500-services instances, respectively, on moderately heterogeneous platforms (specified coefficient of variation = 0.5).

The main conclusion from these results is that our proposed strategy is effective. Algorithms that must contend with error cannot perform as well as the perfect-knowledge algorithm. But the key observation is that our algorithms perform better than the zero-knowledge algorithm over a wide error range. As the minimum threshold used by the algorithms increases, the sensitivity of the algorithm to increasing error diminishes. That is, the curves becomes flatter, but the performance of the algorithm becomes worse on the average, decreasing toward the zero knowledge case.

VII. RELATED WORK

Resource allocation for distributed cluster platforms is currently an active area of research, with application placement [START_REF] Rolia | Automating enterprise application placement in resource utilities[END_REF], load balancing [START_REF] Andreolini | Dynamic load management of virtual machines in a cloud architectures[END_REF], [START_REF] Van | Autonomic virtual resource management for service hosting platforms[END_REF], and avoiding QoS constraint violations [START_REF] Hoyer | Statistical static capacity management in virtualized data centers supporting fine grained QoS specification[END_REF], [START_REF] Petrucci | A dynamic optimization model for power and performance management of virtualized clusters[END_REF] being primary areas of concern. Some authors have also chosen to focus on optimizing fairness or other utility metrics [START_REF] Carrera | Utility-based placement of dynamic web applications with fairness goals[END_REF]. Most of this work focuses on homogeneous cluster platforms, i.e., platforms where nodes have identical available resources. Two major research areas that consider heterogeneity are embedded systems and volunteer computing.

In the embeded systems arena, the authors of [29] also employ heterogeneous vector packing algorithms for scheduling, with many of the underlying heuristics being similar to what we propose in this paper. This work is not directly relevant as their solutions are tightly constrained by the data bus, and they consider a narrower range of algorithms. They do show that bin packing by decreasing item size as measured by maximum vector dimension is important.

Most of the existing theoretical research on multi-capacity bin packing has focused on the off-line version of the problem with homogeneous bins. Epstein considers allowing a limited number of different classes of bins, though with the objective [START_REF] Epstein | On variable-sized vector packing[END_REF] of minimizing the total cost of the bins, which is a slightly different problem. There are obvious connections to multiple-choice multi-dimensional vector bin packing as explored by Patt-Shamir and Rawitz [START_REF] Patt-Shamir | Vector bin packing with multiple-choice[END_REF], but our version of the problem is more constrained since we cannot choose the types of the available bins, and must also contend with elementary requirements and needs. The authors of [START_REF] Baruah | A dynamic programming approach to task partitioning upon memory-constrained multiprocessors[END_REF] consider a dynamic programming approach for when tasks fall into one of a finite number of types.

As stated previously, the problem of properly modeling resource needs is a challenging one, and it becomes even more challenging with the introduction of error. To date we are not aware of other studies that systematically consider the issues of errors in CPU needs estimates.

VIII. CONCLUSION

In this paper we have considered the problem of offline resource allocation on heterogeneous platforms, with the explicit goal of maximizing the minimum task performance. We have defined the problem to allow for multiple resource dimensions and for discrete resource elements, such as CPUs, that cannot be pooled together arbitrarily. We have provided a MILP that can be solved in a reasonable amount of time for small instances, and heuristic algorithms that perform well in practice for solving larger problem instances. We have also considered the problem of inaccurate CPU needs estimates, and developed an effective strategy for minimizing the worst-case penalty imposed while still taking advantage of some of the improvements in resource allocation offered by aggressive heuristic algorithms.

One next step in this research is to implement our METAHVPLIGHT algorithm in combination with our strategy to mitigate estimate errors as part of the resource management component of an open cloud computing infrastructure. This infrastructure, once deployed on a testbed, will allow for an evaluation of our results with both synthetic and production workloads. One interesting problem will be to develop a method for determining and adapting the threshold used to mitigate estimate errors.

Figure 1 .

 1 Figure 1. Example problem instance with two nodes and one service, showing two possible resource allocations.

30 Figure 5 .

 305 Figure 5. Achieved Minimum Yield from Baseline vs Maximum Specified Error on problem instances with 64 hosts, 100 services, memory slack = 0.4, coefficient of variation = 0.5; values given are averages over successful instances.

30 Figure 6 . 30 Figure 7 .

 306307 Figure 6. Achieved Minimum Yield from Baseline vs Maximum Specified Error on problem instances with 64 hosts, 250 services, memory slack = 0.4, coefficient of variation = 0.5; values given are averages over successful instances.

Table I MAJOR

 I HEURISTICS, ORDERED PAIRS OF (Y A,B , S A,B ), WITH A GIVEN BY THE ROW AND B BY THE COLUMN.

			100 services
	A/B	RRND	RRNZ	METAGREEDY	METAVP	METAHVP
	RRND		(66.7%, -19.7%)	(-41.8%, -22.2%) (-71.6%, -22.2%) (-71.6%, -22.2%)
	RRNZ	(-40.0%, 19.7%)		(-69.7%, -2.5%)	(-85.2%, -2.5%)	(-85.3%, -2.5%)
	METAGREEDY (71.7%, 22.2%)	(230.3%, 2.5%)		(-50.9%, 0.0%)	(-51.0%, 0.0%)
	METAVP	(252.4%, 22.2%) (577.6%, 2.5%)	(103.6%, 0.0%)		(-0.2%, 0.0%)
	METAHVP	(252.4%, 22.2%) (578.9%, 2.5%)	(104.0%, 0.0%)	(0.2%, 0.0%)
			250 services
	A/B	RRND	RRNZ	METAGREEDY	METAVP	METAHVP
	RRND		(76.9%, -41.3%)	(-38.2%, -52.8%) (-73.3%, -52.4%) (-73.3%, -52.9%)
	RRNZ	(-43.5%, 41.3%)		(-69.4%, -11.5%) (-86.5%, -11.1%) (-86.7%, -11.6%)
	METAGREEDY (61.7%, 52.8%)	(227.2%, 11.5%)		(-55.4%, 0.4%)	(-56.4%, -0.1%)
	METAVP	(273.9%, 52.4%) (643.0%, 11.1%) (124.3%, -0.4%)		(-2.1%, -0.4%)
	METAHVP	(275.2%, 52.9%) (652.6%, 11.6%) (129.5%, 0.1%)	(2.1%, 0.4%)
			500 services
	A/B	RRND	RRNZ	METAGREEDY	METAVP	METAHVP
	RRND		(74.5%, -49.2%)	(-32.7%, -59.6%) (-69.0%, -59.6%) (-69.3%, -59.6%)
	RRNZ	(-42.7%, 49.2%)		(-62.8%, -10.4%) (-82.3%, -10.4%) (-83.0%, -10.4%)
	METAGREEDY (48.6%, 59.6%)	(168.6%, 10.4%)		(-51.5%, 0.0%)	(-54.1%, 0.0%)
	METAVP	(222.9%, 59.6%) (464.7%, 10.4%) (106.3%, 0.0%)		(-5.2%, 0.0%)
	METAHVP	(226.0%, 59.6%) (489.1%, 10.4%) (117.7%, 0.0%)	(5.5%, 0.0%)

Table II ALGORITHM

 II RUN TIMES IN SECONDS WHEN RUN ON AN INTEL XEON 2.27GHZ PROCESSOR, AVERAGED OVER ALL INSTANCES.TableIIshows algorithm run times averaged over all instances. Expectedly, the RRNZ algorithm has high run times because it solves a linear program (albeit rational). The main observation is that METAHVP leads to higher run

		1
		0.8
	minimum yield difference	0 0.2 0.4 0.6
		-0.2
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
						coefficient of variation
						RRNZ			RRNZ (avg.)
				METAGREEDY	METAGREEDY (avg.)
					METAVP		METAVP (avg.)
	Figure 3. Difference in Achieved Minimum Yield from METAHVP vs
	Coefficient of Variation on problem instances with 64 hosts, 500 services,
	memory slack = 0.3, CPU held homogeneous
		1
		0.8
	minimum yield difference	0 0.2 0.4 0.6									Algorithm RRNZ METAGREEDY METAVP METAHVP	100 tasks 250 tasks 500 tasks 4.855 45.782 270.245 0.014 0.061 0.154 0.142 0.564 1.715 0.514 1.943 6.432
		-0.2
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
						coefficient of variation				decreases as the platform becomes more heterogeneous.
						RRNZ			RRNZ (avg.)
				METAGREEDY	METAGREEDY (avg.)
					METAVP		METAVP (avg.)	1
	Figure 4. Difference in Achieved Minimum Yield from METAHVP vs	0.8
	Coefficient of Variation on problem instances with 64 hosts, 500 services, memory slack = 0.3, Memory held homogeneous	minimum yield difference	0 0.2 0.4 0.6
											-0.2
											0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
											coefficient of variation
											RRNZ	RRNZ (avg.)
											METAGREEDY	METAGREEDY (avg.)
											METAVP	METAVP (avg.)
											Figure 2. Difference in Achieved Minimum Yield from METAHVP vs
											Coefficient of Variation on problem instances with 64 hosts, 500 services,
											memory slack = 0.3

ACKNOWLEDGMENT

Simulations presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).