Jean Dubranna
email: jean.dubranna@mines-paristech.fr

Thierry Ranchin
email: thierry.ranchin@mines-paristech.fr

Lionel Ménard #
email: lionel.menard@mines-paristech.fr

Benoit Gschwind
email: benoit.gschwind@mines-paristech.fr

Production and Dissemination of Marine Renewable Energy Resource Information

Keywords: Marine energy, Earth observation system, hindcast database, dissemination, open data

This paper investigates the capacity of appropriate Earth Observation Systems (EOS)in situ and satellite measurements, numerical modelsto deliver basic variables from which high level information relevant for Marine Renewable Energy (MRE) resource assessment can be generated. In addition, an operational solution for the production and dissemination of such information is proposed and set up. First, the parameters expected by end-users for accurate MRE resource assessment are identified. It turns out that a combination of appropriate spatial coverage and resolution, duration of time series and accuracy has to be met for the EOS data set to be relevant for the production of such parameters. Consequently, long term, high resolution hindcasts of sea states are identified as offering the best compromise over in situ and remote sensing measurements, which are best suited for models calibration and validation. Based on this analysis, a 19-year seastate hindcast, Homere, has been selected. Homere accurately delivers relevant basic variables at appropriate time and spatial scales, over an area covering the south of the North Sea, the Channel, and the Atlantic coast of France and has been used to produce high level, end-user oriented information for the characterization of marine energy resource. Finally, dissemination tools, respecting international standards of interoperability, have been developed with a user-oriented state of mind in order to deliver the information.

I. INTRODUCTION

Marine energy is a fast developing industry and research domain if we rely on the recent evolution of the number of patents or scientific publications related with Marine Renewable Energy (MRE) ( [START_REF]Ocean Energy Technology Readiness, Patents, Deployment Status and Outlook[END_REF], Fig. 1). Several recent papers and reports address the topic of marine energy potential in terms of resource, technology and development maturity either in France, Europe or worldwide ( [START_REF]Ocean Energy Technology Readiness, Patents, Deployment Status and Outlook[END_REF], [START_REF] Uicn | Développement des énergies marines renouvelables et préservation de la biodiversité[END_REF], [START_REF] Smith | Resource Assessment for Cornwall , Isles of Scilly and PNMI[END_REF], [START_REF] Rourke | Renewable energy resources and technologies applicable to Ireland[END_REF], [START_REF] Rourke | Tidal energy update 2009[END_REF], [START_REF] Smith | Best Practice Guidelines for Wave and Current Resource Assessment Task 1 . 6 of WP3 from the MERiFIC Project[END_REF]). Also, many MRE-related projects are being funded at the national or European level (EMACOP, MaRINET, OceaNET, OCEANERA-NET, etc.).

Amongst the pool of information/guidelines considered to be relevant for supporting the marine energy sector, precise characterization of physical environmental constraints specific to the marine environment, usually reduced to the expression "marine resource assessment", is one of the key elements.

Such information is quite a recent topic and its nature and scope follows an ongoing research and end-users' consultation process. The aim of this paper is to demonstrate the addedvalue brought by the Earth Observation Systems (EOS), as referred to by the Global Earth Observation System of Systems (GEOSS), i.e. integrating data coming from remote sensing, in situ measurement networks and large scale numerical models, for the assessment of marine resources. The first part is dedicated to presenting the basics of marine resource assessment, focusing on wave and tidal current technologies, which experience steadiest development and highest investments. Then, the suitability of each EOS to produce basic variables relevant for marine resource assessment is investigated and discussed. Afterwards, focus is brought on the production of marine resource assessment parameters from Homere database ( [START_REF] Boudière | A suitable metocean hindcast database for the design of Marine energy converters[END_REF]) and on their dissemination. Finally, the capacity of Homere-like databases against on-site measurements for appropriate assessment of MRE resource is developed within the Discussion part, and added value of the dissemination platform that is being developed is addressed in the Prospects part.

Fig. 1: Number of published articles where the terms "ocean energy" or "marine energy" appear in keywords, abstract or title (from [START_REF] Chong | Ocean renewable energy in Malaysia: The potential of the Straits of Malacca[END_REF]).

II. MARINE ENERGY RESOURCE ASSESSMENT

Resource assessment is possibly the most critical component of the site selection process for the deployment of a marine renewable energy farm. It is aimed at i) achieving an understanding of wave and tidal climate from which estimates of energy production can be made, ii) providing information for engineering design and operating management. Therefore, it should provide an estimate of the available energy resource and an assessment of the operating and survival characteristics of a specific site. The potential resource for energy production should be ascertained, including seasonal and inter-annual variations, and constraints on resource harvesting should be identified. In this part, some technology-specific key parameters will be presented that are suitable for wave and tidal resource assessment, as well as for installation and operating conditions.

A. Wave Energy 1) Technology: Amongst others, comprehensive and up to date report on wave energy technologies and status is presented in [START_REF]Wave Energy Technology Brief[END_REF]. Also, more details about wave extraction equipment and theory can be obtained from the reference work [START_REF] Falcão | Wave energy utilization: A review of the technologies[END_REF].

Wave energy research has not yet led to a dominant wave energy conversion technology, with new devices and concepts being proposed continually. This is partly due to the different characteristics of the wave resources available at various water depths, which will ultimately require different technical solutions for power capture. In addition, and depending on the concept, wave energy devices have not reached the same stage of development. Many projects are still in the concept validation phase. Amongst more than 100 existing pilot and demonstration projects throughout the world, only a handful of technologies have undergone large scale testing and are close to commercialization.

The wide variety of technologies yields a lack of industrial cohesion and limited supply chains for the variety of components required. Also, evaluation and comparison of technologies and their potential for large scale development is difficult.

2) Key wave parameters: Following extensive consultation with marine energy stakeholders, [START_REF] Ingram | Protocols for the Equitable Assessment of Marine Energy Converters[END_REF] have identified basic key wave parameters that should be obtained through the marine energy resource assessment process (Table 1). All wave parameters presented in Table 1 can be computed from the directional wave spectra, as measured by dedicated devices, or simulated by state of the art wave models. Non-directional spectra miss the directional characteristics of the wave field (Fig. 2).

The wave spectra describe the relationship between the spectral density of free surface elevation (m 2 s) and the frequency (Hz). The convention is to describe the spectrum in non-directional form S(f), which is expanded by a directional distribution D(f, θ) where f and θ are the frequency and direction respectively. The directional spectrum is given by: Key wave parameters are calculated from the nondirectional spectra, using spectral moments. The n th spectral moment is defined as:

The wave power density per linear meter of wave crest (kW/m) is given by (deep water approximation):

Where ρ and g are the seawater density and the acceleration due to gravity respectively. P corresponds to the basic quantity rendering the power per unit of wave crest contained in the wave train.

B. Tidal Current Energy

1) Technology: Amongst others, comprehensive and up to date report on tidal current technologies and status is presented in [START_REF]Tidal Energy Technology Brief[END_REF].

Tide-related currents represent a major ocean energy resource. Tidal current technologies have had more than 40 new devices introduced between 2006 and 2013. Some have successfully undergone full scale demonstration testing. Tidal technologies are expected to commercialize earlier than wave technologies, as evidenced by the number of tidal concepts that have managed to generate electricity during full-scale demonstration with devices in the range of 1 MW. Unlike wave technologies, there seems to be a convergence in tidal current technologies towards horizontal axis designs (76% of the devices), which are similar to designs (albeit smaller) used for wind turbines. 12% are vertical axis turbines and other technologies encompass reciprocating devices (2%), tidal kite and Archimedes screw. 2) Key tidal parameters: The principal goal is to assess the power generation capability of a tidal flow. The total energy available in the flow is given by: where ρ is the density of the water, u is the flow velocity, A is the flow cross-sectional area and t is time. Tidal ranges can provide a quick overview of hot spots, worldwide, with greatest ranges yielding higher resource. Tidal currents can be easily predicted but are highly sensitive to local scale features such as local bathymetric constrictions or capes. This contributes to the fact that accurate tidal resources are largely unmapped. Major tidal streams have been identified along the coastlines of every continent, making it a global resource, albeit very localized.

The key parameters that should be obtained and reported through the resource assessment are the mean high and low water levels at spring and neap tide, the tidal constituents of sea surface elevation and currents (Table 2) as well as the flow velocity exceedance curves.

C. Weather Windows

Verifying that all aspects of a project, including deployment, service and recovery can be conducted safely is an additional issue for MRE projects.

The statistical characterization of weather windows for a particular site is used by the operation and maintenance teams to design tasks so they can be safely carried out in appropriate sea conditions, within a specific time frame. Also, this information is of primary importance when estimating the availability of the devices which, eventually, will impact the energy production and the profitability of the project.

Operational criteria for the characterization of sea states are usually based on the wave height. The information should be compiled in three formats:

• wave height exceedance, • event duration occurrence, • event temporal spacing. Harmonic elements in the formulas for tide and tidal currents. A is the amplitude, ω is the pulse and φ is the phase of the constituent.

D. Extremes and Long Term Extrapolation

Estimates of the m-year return value of significant wave heightthe value which is exceeded on average once every m years, typically 20-year to 100-yearare needed for the safety control and design of ships and offshore structures such as marine energy converters. This information typically provides engineers with "metocean" conditions which induce loadings and response of the structure capable to lead to its failure. The probability of occurrence or exceedance of such conditions during the operational life of the structure should be sufficiently low to correspond to an acceptable risk.

The low level of probability considered, combined with (mostly) short duration of the time series available, make that these extreme conditions have generally not been encountered during the duration of observation/simulation of the "metocean" parameters. Therefore, extreme values are extrapolated from standard distribution functions matched with exceptional values of time series of shorter duration. The result, however, can be very sensitive to the extrapolation model and to the accuracy of the exceptional values extracted from the time series.

III. EARTH OBSERVATION SYSTEMS FOR MARINE ENERGY RESOURCE APPLICATION Earth Observation Systems as referred to by the Global

Earth Observation System of Systems (GEOSS) 1 , i.e. integrating data coming from remote sensing, in situ measurements and large scale numerical models, are expected to produce relevant information for marine energy applications.

A. Measurements

Resource measurement is a fundamental part of any resource assessment study for marine renewable energy development. It provides the only means of quantifying the available resource with high degree of accuracy, providing spectral wave data, tidal components and time series of raw data.

Wave buoys are the preferred method for in situ measurement of wave spectra ( [START_REF] Venugopal | Wave and Tidal Resource Characterisation[END_REF]). However, they are costly floating surface devices, and therefore are vulnerable to collision, interference and severe weather conditions. An alternative method is the use of Acoustic Doppler Profilers (ADPs) which can be deployed on the seabed. Benefits of using ADPs for wave measurements include subsurface (seabed) positioning, capacity to measure both wave spectra and current velocity profiles and relatively affordable price. However, and for wave energy deployment, ADPs are reaching their operating limits at 50 to 60 m depths. Moreover, they cannot transmit data to shore unless advanced mooring/transmission system is set up. Remote sensing instrumentation includes satellite, aircraft and terrestrial sensors. The parameters accurately retrieved from satellites (H m0 and T p ) are not sufficient for accurate wave resource assessment and are mostly used for model calibration. Landbased high frequency (HF) radar is a relatively new technology for wave and tidal resource assessment and has the potential to combine the benefits of measured data with the geographical coverage provided by local to regional modelling.

For tidal energy, summary statistics of current profiles are the basics to assess the performance of the device, in addition to peak ebb and flood currents at neap and spring tides. These parameters can be derived from time series essentially obtained from ADP sensors. One month measurement campaign is the minimum duration to be able to distinguish the main tidal constituents from harmonic analysis and predict tidal streams in the future. Such predictions cannot account for flow variations related with atmospheric and other nonperiodic effects, which are likely to be of lesser importance at sites with energetic tidal flows. Turbulence parameters that affect the efficiency and survivability of the device can also be determined from the analysis of current time series, provided the sampling rate of the current meter is sufficiently high.

B. Modelling

Modelling sits alongside measurements as an essential component of any wave and tidal resource assessment study. While measurements will always be necessary in order to provide calibration and validation data for models, models are able to provide wide spatial coverage and long-term datasets that cannot be retrieved through measurements alone.

Numerical simulations that could appropriately be used for wave resource assessment should provide basic variables over a refined grid (< 200 m in coastal areas) and during a minimum of about 20 years.

For tidal resource assessment applications, hydrodynamic models simulating coastal flows at regional down to local scales (10 to 50 m resolution) are appropriate. The simulation of current velocities averaged over the water column can be sufficient (2D hydrodynamic models) for resource assessment purposes provided that they are run using a combination of high resolution bathymetry and refined mesh. 3D models provide current velocity information for several levels of the water columns. Considering their high requirements in computational capacities, they should only be used at advanced stage of development of a tidal energy project, and for very site-specific simulations.

C. Current Uses of EOS for Marine Energy Applications

Some advanced products specifically dedicated to wave energy resource assessment and based on sea state hindcasts have been published ( [START_REF] Soares | Numerical evaluation of the wave energy resource along the Atlantic European coast[END_REF], [START_REF] García-Medina | Wave resource assessment in Oregon and southwest Washington, USA[END_REF], [START_REF] Hughes | National-scale wave energy resource assessment for Australia[END_REF], [START_REF] Mattarolo | Wave energy resource off the French coasts : the ANEMOC database applied to the energy yield evaluation of Wave Energy Converters[END_REF]). In particular, wave and tidal resource assessment presented in [START_REF] Smith | Resource Assessment for Cornwall , Isles of Scilly and PNMI[END_REF] and [START_REF] Rourke | Renewable energy resources and technologies applicable to Ireland[END_REF] are based on the processing of Homere basic variables and could be considered as a reference work for preliminary resource assessment.

A Geographical Information System (GIS) dedicated to MRE is developed by the CEREMA, the CETE Normandie Centre and Ifremer. It allows efficient overview of more than 100 GIS layers of marine and coastal data related with MRE. It is updated with new layers on a regular basis and aims at establishing the most appropriate sites for the deployment of MRE farms.

However, information currently available from most sources are not suitable for the marine energy resource assessment regarding accuracy, completeness, easy-to-access information and following criteria:

• Spatial resolution is too low (usually > 1 km) and limits the relevance of corresponding information to early stage of development of an MRE project.

• Basic wave variables delivered are not always appropriate (T e is typically missing) or computed from parametric spectrum rather than full directional spectrum.

• Sea level and wave/current interactions are typically not taken into account which impacts the accuracy of the model, especially in coastal waters.

• Information for extensive resource characterization is too limited (little information on weather windows, extreme values or wave scatter diagrams).

• Dissemination tools/formats often require some level of computing knowledge to get access to the information.

This kind of information can also be purchased from consulting agencies that offer end-users oriented products and services. They usually use a combination of open source models and data sets as a basis for the production of relevant, target-oriented and cost-efficient information. When a specific measurement campaign is necessary, the prices of the service can reach very important amounts. Fugro Oceanor, BMT Argoss, Actimar (France) and OpenOcean (France) are some of the main companies in this field.

IV. INFORMATION PRODUCTION AND DISSEMINATION

Homere database ( [START_REF] Boudière | A suitable metocean hindcast database for the design of Marine energy converters[END_REF], [START_REF] Boudière | Manuel de l'utilisateur de la base de données HOMERE[END_REF]) is a sea state hindcast produced by Ifremer in order to fulfil the requirements for Marine Energy Converters design and optimization. It is built on a refined grid with spatial resolution down to 200 m near the coast, over a domain extending from the south of the North Sea down to the north of Spain. Homere provides 19-year long, hourly time series of all the basic variables necessary to generate accurate description of the spatial and temporal variability, and statistics of MRE resource from a national scale down to the scale of a production site. All the high level information produced in this work is based on the processing and analysis of the basic variables delivered by Homere which is, to our knowledge, the most advanced and appropriate source of data for proper MRE resource assessment. The objective is to deliver to marine energy stakeholders information that supports the different stages of development of a marine energy project. Note that characterizing the uncertainty of the information produced, albeit highly recommended, will not be tackled in the present article. We are relying on the fact that Homere has experienced a full range of calibrations and validation tests against in situ and satellite measurements (8 different altimetry sensors) as well as against the National Oceanic and Atmospheric Administration's (NOAA) model. The correlation coefficients between H m0 measured by wave buoys at 15 different sites and H m0 taken from Homere vary between 0.89 and 0.97. When compared to altimetric data, the correlation coefficient reaches at least 0.97, and is between 0.94 and 0.97 when H m0 values are compared with NOAA's outputs for deep and intermediate water depths. Further results about Homere's validation are detailed in [START_REF] Boudière | Manuel de l'utilisateur de la base de données HOMERE[END_REF] and testify to the accuracy of the variables computed.

A. Information Produced

A number of indicators relevant for marine energy applications have been produced on a limited geographic area (study area, Fig. 3). This area was chosen because strong tidal currents and significant wave energy resource combined with important spatial gradients could be expected. Those gradients show how much appropriate spatial resolution, down to a couple hundred meters in coastal areas, is essential for accurate resource assessment and optimal site selection. The choice of the information produced was based on the description of the relevant parameters for marine energy resource assessment presented in Part II. Two different kinds of information were produced: spatialized information and point information.

1) Spatialized information: For spatialized information, one single numerical value of a specific quantity is assigned to each Homere Computational Grid Points (HCGP), e.g. annually-averaged H m0 , winter-averaged wave power density, 20-year return value of H m0 , etc. All these quantities can be displayed, for instance, as colour maps (Fig. 4, Fig. 5) with spatial resolution depending on the local density of the HCGP. Spatialized information that has been computed within the frame of this work is presented in Table 3.

Fig. 4 clearly shows Homere's potential in terms of accurate localization of marine energy sites with most interesting resource. It also emphasizes the very high seasonal variability at sites where the resource is most important. Therefore, and considering the important issue of extracting power from a variable resource, it might be more reasonable to target sites with lower resource, but also lower seasonal signal. The capacity of a wave device to extract energy from a certain sea state is given by its power matrix (Fig. 5, middle panels). Wave scatter diagrams describe the probability of occurrence of those sea states. Scatter diagrams are highly sitespecific, especially in coastal/shallow areas, and power matrices are highly device-and design-specific. Combining both, it is possible to give a first approximation of energy generation by a wave device at a certain site. For instance, right panels of Fig. 5 show that the energy produced by the first technology (in kWh per kW of nominal power installed) is likely to be much lower than the energy yield of the second technology. It means that the power matrix of the second technology matches much better the resource of the investigated area than the power matrix of the first technology. The information delivered is twofold. Not only does it inform the wave device developers about the power matrix and corresponding design they should target for their system, but also does it directly assess the amount of electricity production. Similar information can be produced using Homere's basic variables for tidal devices, provided the power curve of the device is known. 4. Some examples of such information are presented in Fig. 5. Fig. 5a is showing the height-dependant directional distribution of the wave field. We can observe that for this site, wave azimuth window is quite narrow, with a large majority of the waves coming from the west. This information is capital when addressing the issue of farm layout, directionally sensitive devices, anchoring design, etc. Fig. 5b shows the probability of exceedance of a certain wave height and participates in characterizing the access to the site, fatigue aging, loadings on structure, etc. The site-specific wave scatter diagram, used for first approximation of energy yield by a certain wave device is presented in Fig. 5c. Fig. 5d and 5e give the same information as Fig. 5a and 5b but for the current. Fig. 5f1, 5f2 and 5f3 present the annual evolution of monthly wave height, period and power. Low variability of these parameters is preferred when estimating the exploitability of a site. Precise statistics defining the conditions of accessibility of a certain site, often based on the significant wave height, is essential when designing operation and maintenance strategy. This information is delivered in Fig. 6.

Combining the pool of both spatialized and point information allows accurate characterization of the resource. Precise inter-site comparison is also permitted considering the geographical extent where this information is being produced.

B. Information Dissemination Strategy

The purpose is to have high level information relevant for marine energy at end-users' disposal. In consequence, appropriate strategy for disseminating previously generated information is necessary.

In order to make the information as widely disseminated and used as possible amongst the MRE community, attention has been paid to consider and use international and recognized open standards to support interoperability. The Open Geospatial Consortium (OGC) is developing and implementing a series of open standards for geospatial content and services. Amongst those services, the Web Map Service (WMS) is a standard for serving georeferenced map images over the Internet. To enable the "search and discovery" of the information produced, metadata has been created for each WMS. It ensures the user to have access to the most critical information about the map/data that are being displayed (e.g. image format, map bounding box, coordinate reference system, abstract, etc.). Metadata meeting the recommendations of the ISO 19139 international standard have been created then deployed into an OGC CSW (Catalog Service for the Web) compliant Catalog. Using such standard and interoperable approach enables information layers and corresponding metadata to be accessed by any desktop, webbased or mobile software respecting OGC standards. Access to resulting information from the current work is achieved through the webservice-energy.org GEOSS Community Catalog: http://geocatalog.webservice-energy.org Thanks to imbedded interactive map display function to view and possibly query result maps, the Catalog enables to access the numerical values of spatialized information using a WMS "GetFeatureInfo" operation for any HCGP. This operation opens up a window where the values of the main sea-state parameters at the requested point are displayed. From the same window, point information as defined in the previous chapter can be accessed through a dedicated URL. For instance, graphs representing the monthly variations of H m0 , T e and wave power density can be accessed clicking on the corresponding link. The same operation is used to access scatter diagrams, weather windows and any other HCGPspecific information defined in Table 4. Fig. 5: Wave technology-specific annual electricity production (in kWh/kW installed) for a submerged, bottom-referenced heaving buoy (upper panel) and a floating, two-body heaving converter (lower panel). Technology-specific power matrices were taken from [START_REF] Babarit | Numerical benchmarking study of a selection of wave energy converters[END_REF], and were used against each HCGP-specific (Hm0, Tp) scatter diagram to assess the electricity production over the area. Note that energy yield calculations do not take into account the technology-specific constraints such as limitations in deployment depth or farm effects. This figure essentially focuses on how much the fitting between the power matrix and the local resource influences the energy yield.

Access to MRE resource assessment is still under development and only a limited number of information is currently delivered at each point. The quantity of information will increase as the development continues. We are also considering providing a dedicated tool to generate tailor-made interactive outputs. Please contact the authors for details about upcoming and planned developments.

V. DISCUSSION As water depth decreases (typically shallower than about 100m), spatial variability of off shore sea conditions gradually switches from being essentially driven by ocean-atmosphere exchanges of momentum, to being driven by bathymetric/topographic features. In coastal areas, it is common that for atmospheric variations, characteristic length scales are much longer than for bathymetric gradients. Spatial gradients of sea states have therefore much shorter length scale near the coast (typically a few hundred of meters) than offshore (typically a few kilometers to tens of kilometers). In the current situation, a majority of MRE projects or MRE-related prospection focus on depths shallower than 100 m, and are taking place between the preliminary and the development stages. According to Fig. 7, on-site measurements are either appropriate for evaluation of the resource during early preliminary stage (global network, Fig. 7, dark gray) or from very advanced development stage onward (site-scale network, Fig. 7, gray). The spatial distribution of the global network is presently insufficient and too unevenly distributed for precise, spatially resolved description of the resource in shallow waters. Moreover, unless an MRE project is precisely planned close to this measurement site, site-scale measurement networks are not suitable for this exercise either, due to the site-exclusive information they are providing. In consequence, on-site measurements are missing the transition between the first 2 stages of development of an MRE project.

In contrary, hindcasts like Homere, if correctly calibrated and validated by onsite measurements, perfectly fill the gap (Fig. 7, light gray). HCGP density relevantly adapts with bathymetry in order to describe the sea state variations at appropriate resolution. In addition, time series are sufficiently long for strong statistics and trends to be inferred from a national, down to a site scale.

VI. CONCLUSION

We have investigated the suitability of Earth Observation Systems as referred to by the Global Earth Observation System of Systems (GEOSS), i.e. integrating data coming from remote sensing, in situ measurement networks and large scale numerical models, to provide relevant basic variables for marine resource assessment. First, the most appropriate sources of data have been identified and then they have been exploited to produce high level, marine energy-oriented information. Finally, the information produced has been disseminated with a user-oriented and interoperability state of mind. More precisely, the main outcomes of this work are threefold:

i) The capacities of each category of Earth Observation Systems for marine energy applications, in particular their relevance for marine resource assessment, have been identified. On-site measurements and remote sensing systems are mostly suitable for the calibration and the validation of numerical models. Sea state hindcasts that combine sufficient spatial coverage, high spatial resolution (few hundred of meters) and long simulation time series (several decades) offer the best potential to deliver the basic variables from which marine resource assessment can be inferred.

ii) From Homere database, which has been identified as the most appropriate hindcast for the collection of basic variables, we have produced a number of high level information relevant for marine resource assessment. Two kinds of information were computed. Spatialized information can be displayed as colormaps showing the spatial distribution of some specific variables (e.g. average significant wave height, maximum flow velocity, etc.). Point information is point-specific and consists in graphs/tables/scatter diagrams. It was computed at each output point of Homere database.

iii) The information produced is being implemented in the webservice-energy catalog, and disseminated following GEOSS recommendations on interoperability. Spatialized information is displayed as color maps selected by the user. Point information can be accessed by the user by clicking on any grid point, and following the various information-specific links. Fig. 7: Relevance of EOS time series for appropriate resource characterization depending on the state of progress of an MRE project. The properties of Homere as well as global and site-scale measurement networks are reported on the 'Characteristics of the EOS' arrows, with closer to the tip of the arrow meaning better characteristic. For instance, coarse spatial resolution (~10 km), 1 year time series over a global geographical extent is sufficient for very early preliminary stage, but advanced development stage requires spatial resolution of about 100 m, and longer time series over a geographical coverage that can be below the regional scale but should be wider than the site-scale. This figure was realized based on the recommendations provided by the EquiMar project ( [START_REF] Ingram | Protocols for the Equitable Assessment of Marine Energy Converters[END_REF]).

VII. PROSPECTS A.

Resource Characterization The work carried out has proven that Homere's design is suitable to characterize the marine energy resource from a national down to a site scale provided that the set of variables it is delivering is appropriately processed. For instance, wave power density precisely informs about available power for wave energy extraction and, in a GCOS-like sense, could be considered as an essential variable for wave resource assessment [START_REF] Gcos | The second report on the adequacy of the global observing systems for climate in support of the UNFCCC[END_REF]. So far, the scripts, algorithms and dissemination methods have been developed for a limited geographic area and a rather short duration (5 years out of 19 years available) compared to the total length of the time series. The extension of this work to the entire geographic area and time period covered by Homere is in progress.

B. Dissemination Tool

Resource assessment is intended to inform about both the energy available to a device and the conditions under which the energy farm will operate. The combination of both information is critical when deciding how and where to site a marine energy device, and provides essential insight for planning, operations and construction. The information our project is producing is targeting both aspects of the resource, and the dissemination tool we are developing is intended to provide the users with a "one-stop shop" for collecting that information from a national down to a site scale, in a format that is suitable for a wide range of down the line applications. Information about energy resource is necessary to device developers, investors, utilities and government. Information for wave and current loadings, on a site basis, is likely to be dimensioning parameters or at least, will impact the final design of a device. This information is useful for designers, insurers and classifiers. Finally, statistics about accessibility to the site, for a fully operating project, helps defining the installation and maintenance strategy. This information is required for designers, marine contractors, insurers and classifiers. Further stakeholders consultation is in progress in order to precisely meet their expectations in terms of resource characterization. Considering the wide range of potential users, a flexible, adaptive and user-oriented dissemination tool is being designed. Focus has been brought on:

1 -Interoperability: Resource mapping is one of the many parameters that come into consideration when bringing together multiple users of the sea to make informed and coordinated decisions about how to sustainably use maritime area, which is referred to as Marine Spatial Planning (MSP). Interoperability fully complies with the integrative role of MSP, which is an initiative adopted by the European Union. It dramatically increases the capacity of the information produced by the current work to be integrated into MSP or any GIS-type tool, efficiently providing MRE stakeholders with comprehensive description of marine energy resource characteristics at all scales from site to national.

2 -Open and easy access: The dissemination tool is being designed keeping in mind that maps, graphs and, most of all, corresponding numerical values are intended to be downloaded by the users for a more personalized processing of the information delivered. This ensures that the information can be reused for user-specific applications, such as modelling early insight into the economics of a marine energy project. This is an essential aspect that most of the dissemination platforms do not offer so far.

Fig. 2 :

 2 Fig. 2: Example of non-directional wave spectrum

Fig. 3 :

 3 Fig. 3: Geographical coverage of Homere and study area detailing Homere Computational Grid Points (HCGP) distribution

Fig. 4 :

 4 Fig. 4: Seasonal averages of wave power density P (in kW per m of wave front). a) winter, b) spring, c) summer, d) fall.

Fig. 5 :Fig. 6 :

 56 Fig. 5: Yearly characteristics of the sea sate for one specific HCGP. Similar information has been computed at all HCGP. a) Color-coded distribution of wave azimuth, colors are based on Hm0 values; b) Hm0 exceedance curve; c) Scatter diagram of (Hm0, Te); d) Color-coded distribution of current direction, colors are based on current velocity values; e) Current velocity exceedance curve; f1-f2-f3) Monthly means 10% and 90% quantiles of Hm0, Te and wave power density respectively.

TABLE 1 : KEY WAVE PARAMETERS TO BE COMPUTED FOR WAVE RESOURCE ASSESSMENT, ADAPTED FROM [11] Symbol Formulation Notes Significant wave height

 1

		H m0	4	Statistical measure of the largest wave heights
	Mean Wave Period	T 02		Measure of the mean time between wave cycles
				Period of a monochromatic wave of height H
	Energy wave period	T e		which contains the same mean energy as the
				irregular sea where H m0 = sqrt(2)H during T e .
	Peak wave period	T p		Inverse of the most energetic frequency of the energy spectrum
	Mean direction	ϴ m		Mean direction of propagation of wave energy
	Spectral bandwidth			Characterize the spectral spread of the sea-state

TABLE 2 :

 2 KEY TIDAL PARAMETERS TO BE COMPUTED FOR TIDAL RESOURCE

ASSESSMENT Symbol/ Formulation Notes Mean high water springs MHWS

			Average height of the high water
			occurring at the time of spring
			tides
	Mean high water neaps	MHWN	Average height of the high water occurring at the time of neap tides
	Mean low water springs	MLWS	Average height of the low water occurring at the time of spring tides
	Mean low water neaps	MLWN	Average height of the low water occurring at the time of neap tides
	Tidal
	constituents of
	sea surface
	elevation and
	currents

A.cos(ωt + φ)

TABLE 3 :

 3 SPATIALIZED INFORMATION PRODUCED

		Annual Avg./Std	Seasonal Avg./Std	Monthly Avg./Std
				
	Te			
	Tp			
	P ϴm	 	 	 
	Extreme values	NA	NA	NA
	Tidal Current Ellipses	
	Power of Flow	
	Max. Flow Velocity	NA	NA	NA
	Techno.-Spec. electricity production			
	2) Point information: Point information refers to HCGP-
	specific quantities that are represented by a set of numerical
	values/graphs/tables, e.g. scatter diagrams, exceedance tables,
	monthly variability, etc. Point information that has been
	generated at every single HCGP of the study area is presented
	in Table

TABLE 4 :

 4 POINT INFORMATION PRODUCED

		Annual	Seasonal	Monthly	Interannual variability	Monthly variability
	Scatter diagrams (H m0 , T e /T p /T 02 )		
	Weather windows		
	Flow velocity exceedance curve	
	Wave rose (H m0 , ϴ m )			
	Current rose	
	Techno.-Spec. electricity production					

http://www.earthobservations.org/

ACKNOWLEDGEMENT

The authors are grateful to Ifremer for giving full access to Homere database. Access can be requested through the PREVIMER website (http://www.previmer.org/).


Ikbel Belaid
email: ikbel.belaid@inria.fr

Lionel Eyraud-Dubois
email: lionel.eyraud-dubois@inria.fr

Column generation integer programming for allocating jobs with periodic demand variations

In the context of service hosting in large-scale datacenters, we consider the problem faced by a provider for allocating services to machines. An analysis of a public Google trace corresponding to the use of a production cluster over a long period shows that long-running services experience demand variations with a periodic (daily) pattern, and that services with such a pattern account for most of the overall CPU demand. This leads to an allocation problem where the classical Bin-Packing issue is augmented with the possibility to co-locate jobs whose peaks occur at different times of the day, which is bound to be more efficient than the usual approach that consist in over-provisioning for the maximum demand. In this paper, we propose a column-generation approach to solving this problem, where the subproblem uses a sophisticated SOCP (Second Order Cone Program) formulation. This allows to explicitely select jobs which benefit from being co-allocated together. Experimental results comparing with theoretical lower bounds and with standard packing heuristics shows that this approach is able to provide very efficient assignments in reasonable time.

Introduction

The Cloud paradigm provides an illusion of infinite elasticity and seamless provisioning of IT resources. However, as providers keep scaling their infrastructures year after year, the efficient allocation of services in Platform-as-a-Service (PaaS) becomes crucial.

We concentrate on the case of a Cloud platform in which several independent services, typically virtualized as Virtual Machines (VMs) or lightweight containers, are serving user queries and need to be allocated onto physical machines (PMs) [START_REF] Zhang | Cloud computing: state-of-the-art and research challenges[END_REF][START_REF] Armbrust | Above the clouds: A berkeley view of cloud computing[END_REF]. We consider the static case where a set of dominant services define the overall resource usage of the physical platform, which has proved to be commonplace in large datacenters [START_REF] Beaumont | Analyzing real cluster data for formulating allocation algorithms in cloud platforms[END_REF]. In this context, mapping services with heterogeneous computing demands onto PMs is amenable to a multi-dimensional Bin-Packing problem (each dimension corresponding to a different kind of resource, memory, CPU, disk, bandwidth,. . . ). Indeed, on the infrastructure side, each physical machine presents a given computing capacity (i.e. the number of Flops it can process during one time-unit), a memory capacity and a failure rate (i.e. the probability that the machine will fail during the next time period). On the client side, each service has a set of requirements along the same dimensions (memory and CPU footprints) and a reliability requirement that has been negotiated typically through an SLA [START_REF] Cirne | Web-scale job scheduling[END_REF].

In this work, we consider a specific feature of CPU demand that arises in the context of service allocation. Previous work on the subject [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF] argues that many services representing most of the overall CPU demand exhibit daily patterns and their demand can be modeled as a set of sinusoids, each comprising a constant component, an amplitude and a phase. This premise gives rise to a model for jobs with time-varying resource demands and to the associated packing problem. Such a model can be used to aggregate onto the same physical machines more resources than it would be possible based on their maximal demands only, taking advantage of the fact that different phases for different services imply that peak demands do not occur simultaneously. In this paper, we propose an algorithm based on column generation for packing jobs with periodic demands on the hosting platform. This algorithm provides very efficient allocations, compared to state-of-the-art greedy packing heuristics.

The remaining of this paper is organized as follows. We discuss some related works in Section 2. In Section 3, we present the formulation of the optimization problem as a Second Order Cone Program (SOCP). In Section 4, we propose our efficient packing algorithm based on column generation, whose performance is analyzed and validated on realistic and simulated data in Section 5. Finally, conclusions are drawn in Section 6.

Related works

In order to deal with resource allocation problems arising in the context of Clouds, several sophisticated techniques have been developed in order to optimally allocate user services onto PMs, either to achieve good load-balancing [START_REF] Calheiros | A heuristic for mapping virtual machines and links in emulation testbeds[END_REF][START_REF] Beaumont | Heterogeneous Resource Allocation under Degree Constraints[END_REF] or to minimize energy consumption [START_REF] Beloglazov | Energy efficient allocation of virtual machines in cloud data centers[END_REF]. Most of the approaches in this domain are based on offline [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF] and online [START_REF] Hochbaum | Approximation Algorithms for NP-hard Problems[END_REF] variants of Bin-Packing strategies.

In this paper, we concentrate on the allocation of jobs that last for a long time and whose CPU demands exhibit periodic patterns. Some other work deal with allocating jobs whose demands varies over time, either with predictable (static) or unknown (dynamic) behavior. In the static case which is the focus of this present work, historical average resource utilization is typically used as input to an algorithm that maps services to physical machines. Therefore, the mapping is done off-line. In contrast, dynamic allocation schemes are implemented on shorter timescales. Dynamic allocation leverages the ability to perform runtime migrations of jobs and to recompute resource allocation amongst services. A dynamic migration algorithm Measure Forecast Remap is introduced in [START_REF] Bobroff | Dynamic placement of virtual machines for managing sla violations[END_REF], where highly variable workloads are forecast over intervals shorter than the time scale of demand variability to ensure dynamic execution minimization of the number of required machines. Based on stochastic vector packing model, the static scheme proposed in [START_REF] Shahabuddin | Stream-packing: Resource allocation in web server farms with a qos guarantee[END_REF] makes use of customers' periodic access patterns in web server farms to assign each customer to a server so as to minimize the total number of required servers. In this latter work, the variable demand is analyzed at a different time scale to extract probability distributions that are independent of time. Then, stream-packing heuristics are employed to select the most complementary jobs to be packed in the same server. Urgaonkar et al. [START_REF] Urgaonkar | Resource overbooking and application profiling in shared hosting platforms[END_REF] rely on on-line application profiling to demonstrate the feasibility and benefits of overbooking resources in shared platforms to guide the application placement onto dedicated resources while providing performance guarantees at runtime. A new mechanism for dynamic resource management in cluster-based network servers [START_REF] Aron | Cluster reserves: A mechanism for resource management in cluster-based network servers[END_REF], called cluster reserve, allows performance isolation between service classes and provides a minimal amount of resources, irrespective of the load imposed by other requests. In contrast to these other directions, our work focuses on a part of the workload which exhibits deterministic periodic variability. In this context, dynamic resource management is unnecessary: the migration cost can be avoided by using periodicity-aware static approaches for service allocation. By focusing on long-running services with high workloads, it is possible to apply sophisticated techniques to provide efficient packing policies, which results in increased resource usage. Smaller or short-lived jobs, which are much more numerous but represent a smaller part of the resource usage, can be handled with usual greedy allocation schemes. This paper is a followup to [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], which analyzes the performance of several standard packing heuristics in the context of packing jobs with periodic demand variation. In this paper, we propose the use of the Dantzig-Wolfe decomposition [START_REF] Vanderbeck | On dantzig-wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] to solve very efficiently the corresponding packing problem. In fact, mathematical programs featured by a large space of integer variables are particularly suited for Dantzig-Wolfe decomposition that reformulates the original compact problem to provide a tighter linear programming relaxation bound. This decomposition relies on delayed column generation algorithm. The overarching idea of this algorithm is that many programs are too large to consider all the variables explicitly. Since most of the variables will be neglected in the optimal solution, only a subset of variables need to be considered in theory when solving the problem. Column generation leverages this idea to generate only the variables which have the potential to improve the objective function, that is, to find variables with negative reduced costs. Section 4 details the utilisation of Dantzig-Wolfe decomposition to reformulate the packing of jobs with variable demands on hosted parallel machines based on the original formulation and employing the column generation algorithm.

The Dantzig-Wolfe reformulation gives rise to a master problem and subproblems, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm. Solving the master problem does not require an explicit enumeration of all its columns because the column generation algorithm allows one to generate columns if and when needed. In many cases, this allows huge integer programs that had been previously considered intractable to be solved. The technique of Dantzig-Wolfe using the approach of column genera-tion has been applied successfully in many classical problems as: cutting stock, vehicle routing, crew scheduling, etc.

Packing of jobs with periodic demands

An analysis of a publicly available Google trace [START_REF] Reiss | Google cluster-usage traces: format + schema[END_REF][START_REF] Reiss | Towards understanding heterogeneous clouds at scale: Google trace analysis[END_REF] has shown that about twothirds of the dominant, normal production jobs in that trace exhibit significant daily pattern [START_REF] Beaumont | Analyzing real cluster data for formulating allocation algorithms in cloud platforms[END_REF]. Based on this analysis, and following [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], we consider a packing problem for those long running jobs, which account for a large portion of the workload.

Notations and problem formulation

Let us assume that the cloud platform we consider consists of M homogeneous nodes M 1 , . . . , M k , . . . , M M and let us denote the processing capacity of a node by C. For the sake of simplicity and in order to focus on issues related to the aggregation of periodic demands, we will concentrate on CPU demands only. The tasks of a job (corresponding to a service in the trace) can run on any node, and job J j is split into N j tasks denoted by T j,1 , . . . , T j,l , . . . , T j,Nj , who share the same characteristics in terms of CPU demand.

In turn, platform nodes are allowed to run several tasks, provided that at any time, their capacity is not exceeded. We assume that the set of tasks running on a node does not change over time, what is a realistic assumption for dominant Normal Production jobs, and we model the instantaneous demand at time t of task T j,l , which does not depend on l, as

W j (t) = C j + ρ j sin 2π t P j + φ j
where C j denotes the average of CPU demand of Task T j,l , ρ j denotes its maximal amplitude with respect to C j , P j denotes its period and which is common for all the jobs. In the remainder of the paper, job period will be named P . φ j denotes its phase.

In this context, our aim is to provide a static packing for the set of tasks T j,l such that at any step and on any resource, capacity constraints are not exceeded and such that the number of required nodes is minimized. More specifically, this model allows to take advantage of daily variations in order to obtain an efficient packing of tasks. Indeed, most packing strategies are based on the maximal demand of each task, what corresponds to C j + ρ j for a task of job j. Taking advantage of the fact that all tasks do not achieve their peak demand at the same time in the day, it is possible to pack more tasks, and therefore to use fewer nodes whilst packing statically all the tasks.

The corresponding capacity constraint for a given machine M k is thus ∀t,

j,l: T j,l ∈M k W j (t) ≤ C,
and it can be rewritten [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF] as an expression which does not depend on t:

∀k, j,l: T j,l ∈M k C j + ( j,l: T j,l ∈M k ρ j cos(φ j )) 2 + ( j,l: T j,l ∈M k ρ j sin(φ j )) 2 ≤ C
(1) This modified packing constraint yields a quadratically constrained programming (QCP) formulation of the problem. This formulation uses two types of variables: integer variables X j,k representing the number of tasks of job j allocated on the node M k , and boolean variables Y k representing whether node N k is used. With these variables, the formulation is the following:

Minimize k Y k ∀j ∈ J, k∈M X j,k = N j (2) ∀k ∈ M, ( j∈J X j,k ρ j cos(φ j )) 2 + ( j∈J X j,k ρ j sin(φ j )) 2 ≤ (C Y k - j∈J X j,k C j ) 2 (3) ∀k ∈ M, C Y k - j∈J X j,k C j ≥ 0 (4)
In this formulation, constraint [START_REF] Aron | Cluster reserves: A mechanism for resource management in cluster-based network servers[END_REF] ensures that all instances of all jobs are allocated. Tasks belonging to the same job could co-exist in the same node. Constraints (3) and ( 4) are a quadratic reformulation of Equation ( 1), ensuring that an unused node does not contribute any resource to the platform. Due to the nature of this constraint, this formulation can be expressed as a Second Order Cone Program (SOCP) [START_REF] Hans D Mittelmann | An independent benchmarking of sdp and socp solvers[END_REF], and can thus benefit from efficient general purpose solvers [START_REF] Hans D Mittelmann | An independent benchmarking of sdp and socp solvers[END_REF] for convex optimization. However, as noticed in [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], on realsize instances with thousands of machines, this formulation can not be solved in reasonable time with integer and boolean values. Relaxing the problem by allowing rational variables makes it possible to obtain a lower bound on the necessary number of resources in reasonable time.

In the next Section, we describe how to reformulate this problem with a Dantzig-Wolfe decomposition, which allows to quickly obtain very good solutions to the packing problem.

Integer programming Column generation

Dantzig-Wolfe decomposition has been an important tool to solve large structured models that could not be solved using standard algorithms as they exceeded the capacity of solvers. The main idea behind this technique is to decompose the original problem into a number of independent subproblems, whose solutions are then assembled by solving a so-called master problem. This master problem is then solved iteratively. In our case, we can identify the natural decomposition of the problem: for two different values of k (i.e. for each machine), the corresponding sets of constraints ( 3) and ( 4) are independent, because they contain disjoint sets of variables. Since we assume that machines are homogeneous, all those subproblems are actually identical, and we obtain a special case where solving it only once is enough.

In the Dantzig-Wolfe reformulation, we obtain a master problem which contains one variable for each solution to this subproblem. In our case, such a solution is simply a valid packing configuration for a machine, i.e. a set of jobs which can be allocated together on a single machine while respecting the capacity constraint. One configuration Z i can be represented as a J-uplet (X 1,i , X 2,i , . . . , X J,i ), where X j,i is the number of tasks of job j in configuration i. As discussed previously, this configuration is valid if it satisfies equation [START_REF] Armbrust | Above the clouds: A berkeley view of cloud computing[END_REF].

In the following, we will denote as K the set of all valid configurations. The master problem contains one variable Y i for each configuration Z i ∈ K, which represents the number of machines which use the configuration Z i , i.e. the number of machines to which X j,i tasks of job j are allocated. The packing problem can now be formulated as follows:

Master Problem:

Minimize i∈K Y i s.t ∀j ∈ J, i∈K X j,i Y i ≥ N j (5)
Y i ∈ N (6)
This master problem cannot be solved directly due to an exponential number of variables. However, the column generation approach consists in considering variables only from a subset K ⊂ K, and to solve the resulting restricted master problem (RMP) on this set of variables.

This restricted problem may provide a sub-optimal solution, since there might exist a configuration in K\K which improves the solution. In order to find this configuration, one can write the dual of the master problem, in which there is one variable π j for each job, and one constraint for each configuration:

Dual Master Problem: Maximize j∈J N j π j s.t ∀i ∈ K, j∈J X j,i π j ≤ 1 ( 7
)
π j ≥ 0 (8)
The sub-optimal solution obtained from the restricted master problem provides a solution π * j of the dual master problem which is possibly infeasible, since not all constraints are included in the dual of the RMP. From this solution π * j , we can identify a variable to add to the problem by searching for a violated constraint in the dual, i.e. a configuration Z i ∈ K such that j∈J X j,i π * j > 1. This gives rise to the following subproblem, with one variable U j for each job:

Subproblem: Periodic Knapsack : Minimize 1 -j∈J π * j U j s.t ∀j ∈ J, ( j∈J U j ρ j cos(φ j )) 2 + ( j∈J U j ρ j sin(φ j )) 2 ≤ (C - j∈J U j C j ) 2 (9) U j ∈ N (10)
If the optimal solution of this subproblem has a negative value, then we have identified a configuration to add to the RMP. On the other hand, if this problem has no solution with negative value, it means that all constraints in the dual of the master problem are satisfied with the current solution, which implies that this current solution of the RMP is actually optimal for the master problem.

This subproblem can be seen as a knapsack problem: given profits π * j for each job, we search for the set of tasks with maximal profit which can fit in a single machine. The strong point of the Dantzig-Wolfe reformulation in this case is that we have isolated the quadratic constraint in the subproblem, which is of much smaller scale than the original problem, with only one variable per job. This problem can now be solved (quite efficiently as we will see in Section 5) with a general integer SOCP solver.

The column generation algorithm is summarized in Algorithm 1: starting from an initial set of configurations (which we describe below), the algorithm iteratively solves the RMP, and then uses the values of the dual variables as prices in the knapsack subproblem. The solution to this subproblem yields a new configuration which is added to the set, and a new iteration is performed. The process ends when no solution to the subproblem has a negative cost. The obtained RMP is then solved with integer constraints to obtain a feasible solution to the original problem. In practice, this last step is often too time consuming for the solver to obtain an optimal solution in reasonable time, so in our experimental evaluation, we included a 5 minute time limit and use the best feasible solution obtained by the solver in that time.

The initial set of configurations can be chosen arbitrarily, as long as the first RMP is feasible, i.e. all jobs are represented in at least one configuration. For simplicity, we build the initial set K 0 with one configuration per job, where the configuration for job j contains C Cj +ρj tasks of job j (as many as can fit on one machine), and 0 tasks of all other jobs.

Experimental evaluation

In this section, we present the results of synthetic and realistic experiments provided by column-generation algorithm and best-effort heuristics. We investigate the performance of each in reducing the number of used nodes as well as their margin towards the lower bound. We show that our column generation algorithm delivers good results in reducing the number of iterations and computation time.

Complexity and Lower Bound

The optimization problem that consists in packing tasks with periodic demands into nodes is clearly NP-Complete, since it is amenable to classical Bin-Packing problems [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF][START_REF] Hochbaum | Approximation Algorithms for NP-hard Problems[END_REF] in its most simplified setting where ∀j, ρ j = 0, i.e. the case when demands do not change over time. Indeed, in many cases the last step of our column generation algorithm (where we look for an integer solution) is unable to obtain an optimal solution in the alloted time. In order to asses the performance of the obtained results, we rely on a simple but powerful lower bound: the total workload at time t is j∈J W j (t), whose peak can be computed like in Section 3 as W = j∈J C j + ( j∈J ρ j cos(φ j )) 2 + ( j∈J ρ j sin(φ j )) 2 . Since in any solution, the sum of the capacity used on each machine is not lower than P , we know that any solution must use at least W C machines. This solution is not feasible in general but it provides a lower bound on the number of necessary nodes.

Heuristics

In this Section, we present some heuristics introduced in [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], adapted from classical efficient greedy Bin-Packing algorithms to the case of tasks exhibiting daily patterns. In the following, we denote by L(M k , T j,l ) the peak load on machine M k after adding one task T j,l of job J j to M k .

-Best-Fit Decreasing BF D is a greedy algorithm in which tasks are considered by decreasing values of C j . At any step, task T j,l (from job J j ) is allocated to the node M k such that L(M k , T j,l ) is maximized (while remaining below C). Note that contrarily to what happens in classical BF D, the size that is considered is the size after the allocation. If no such node exists, then a new node is added to the system to hold the task. -In Min-Max MM(M ), the target number of nodes is fixed to M a priori.

Then, MM is a greedy algorithm where tasks are considered by decreasing values of C j . At any step, task T j,l (from job J j ) is allocated to the node M k such that L(M k , T j,l ) is minimized, in order to balance the load between the different nodes. The allocation may fail if M is too small. We thus use dichotomic search to find the smallest value of M which allows to obtain a solution.

-Min-Max-Module MMM is similar to MM, except that tasks are represented using their maximal demand over time C j + ρ j only. This is typically what happens when one neglects the possibility to take advantage of the fact that peak demands do not occur at the same time for all jobs.

Simulated synthetic Data

First, we perform a set of experiments with synthetic data in order to assess the influence of the parameters on the performance of the different proposed methods. In all the experiments, we set the capacity of the nodes to 20, and we display the ratio between the number of nodes provided by the corresponding method against the lower bound on the number of necessary nodes described in Section 5.1.

For synthetic jobs, we consider the following parameters:

-CPU footprint of the tasks: we consider the case of Large Tasks, Medium Tasks and Small Tasks where C j is chosen uniformly at random respectively in [0, 10], [0, 5] and [0, 1]. To keep the total workload constant, we set the number of tasks N j in each job to 50 for Large Tasks, 100 for Medium Tasks, and 500 for Small Tasks. -Daytime amplitude: we consider the case of Large Daytime Amplitude (where ρ j is chosen uniformly at random in [0, C j ]) and Small Daytime Amplitude (where ρ j is chosen uniformly at random in [0,

Cj 2 ]).
In all cases, the phase of each job is chosen uniformly at random in [0, 2π[, and the number of jobs is set to 100. We performed other experiments with different number of jobs and tasks, but the results showed very little sensitivity to these parameters and were excluded from the paper in order to save space.

For each scenario, we have performed 20 experiments, and the results are shown on Figure 1, where the 20 experiments for each scenario and each algorithm are q q q q q q q q q q q q q q 1.0

Large Amplitude Small Amplitude Large Tasks Medium Tasks Small Tasks Ratio to lower bound Algorithm ColGen BestFit MinMax MinMaxModule q q q q q q q q q 1.00 Fig. 1: Performance of all algorithms on synthetic data. The right plot is a focus on the most efficient algorithms.

grouped together in a boxplot showing the mean, the first and third quantiles, and minimum and maximum values.

The figure shows that the column generation algorithm is able to consistently provide solutions with a number of required nodes very close to the lower bound, in all of the scenarios. Actually, for some of the Large Tasks scenarios , the solver is able to obtain a provably optimal integer solution in the final step of the algorithm, meaning that the column generation algorithm actually provides an optimal solution in these cases. This also shows that the lower bound is actually very precise, since it is possible to exhibit a feasible solution with very close performance.

In the Small Tasks scenarios, in which each node can hold a few tens of tasks, Min-Max MM performs extremely well and is always at most within 1% of the lower bound. This behaviour is usual in Bin-Packing problems: the presence of very small objects makes the packing easier since they can be used to fill the wasted space in the bins. Indeed, the results of Min-Max MM degrade when tasks get larger: in this case, the number of tasks per node is relatively small (a few units) and greedy heuristics fail to achieve close to optimal performance. On the other hand, in the Small Tasks scenarios, the solution provided by the column generation algorithm is not as good. This comes from the fact that the integer problem of the final step is very difficult to solve in that case.

Nevertheless, the number of nodes required by the column generation algorithm is always within 1% of the lower bound. It is worth noting that in the context which we consider in this work (long-running services with heavy workload), the task sizes are not small, and the medium-large task sizes are the most realistic cases (see Section 5.4 for a comparison on a real trace).

The BestFit heuristc BF D represents the standard packing algorithm used in such Cloud systems. We can see that its performance is consistently 10% above the lower bound , and even worse in the case of small tasks. This advocates strongly in favor of more sophisticated algorithms like the one we propose. Finally, we can also see that failing to take periodic demand variations leads to a large waste of resources. Indeed, the performance of Min-Max-Module MMM is consistently far from the lower bound, by 50% in the case of Big Amplitudes and by 25% in the case of Small Amplitudes. Task Size Time per iteration (ms) q q q q q Large Amplitude Small Amplitude Figure 2 analyses the computation time for the first phase of the columngeneration algorithm, which solves the rational relaxation of the problem (the second phase is the final step where we obtain an integer feasible solution, whose time is limited to 5 minutes in our experiments). We observe that the number of iterations remains below 300, and the time per iteration is very low (around 200ms), showing that the SOCP formulation for the subproblem is very efficient. This allows the column generation algorithm to complete its first phase in about 40 seconds in all scenarios.

Jobs and Tasks of Google Trace

Then, we concentrate on the set of realistic periodically variable jobs in the trace released by Google [START_REF] Wilkes | More Google cluster data[END_REF] and corresponding to one production center. In [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], Therefore, there exists a potential improvement on the number of required nodes of 5%, what should be considered as large in the context of an actual production center. We have applied our column-generation algorithm on this instance, and the results achieved are displayed in Table 1.

The results of MM are deemed extremely good in [START_REF] Beaumont | Allocating jobs with periodic demand variations[END_REF], because the number of required machines is only 1.1% higher than the lower bound. Our columngeneration algorithm CG is able to provide an even more efficient solution, with a number of nodes only 0.6% higher than the lower bound, effectively halving the gap between the best solution and the lower bound. As shown previously, the time complexity of our algorithm is very reasonable, showing that our column generation algorithm can really make an impact for improving resource usage in actual production centers.

Conclusions

Allocating computing resources for multiple time-varying job workloads is an attractive yet challenging target for many providers of large-scale infrastructures of cloud computing. Towards this end, we address in this paper a resource allocation problem for jobs that exhibit daily periodic sinusoidal patterns. Such jobs have been shown to represent a significant part of the workload of large production clusters, as exemplified by a trace from a Google center. Taking the periodic pattern into account allows to coallocate jobs which reach their peaks at different times, and this allows to to significantly increase the resource usage on these platforms.

In this paper, we present a novel packing technique relying on job aggregation mechanism by employing an exact method using column generation integer programming. The Dantzig-Wolfe reformulation allows to isolate the quadratic constraint in a small size subproblem, which can be solved very efficiently. Solving iteratively this subproblem and the reformulated packing problem allows to efficiently identify the relevant machine configurations, i.e. the set of jobs which should be allocated together. This technique is then compared to best-effort heuristics inspired from the standard bin-packing methods, on both simulated and realistic data. Experimental results show that this algorithm obtains good results very consistently, even in difficult cases in which task sizes are large and few tasks can fit together on the same machine. In the most realistic cases, the column generation improves over the best heuristic by up to 5%, effectively halving the gap between the best known solutions and the lower bound.

As future work, we plan to extend job aggregation strategies to provide performance guarantees for other resources like memory, disk, network bandwidth, etc. Improving the column generation algorithm could focus on two different directions: using a more efficient routine to solve the subproblem could lower further the running time of the first phase, and more efficient branching schemes could improve the efficiency of the last step of the algorithm. Besides, we target to address the problem of resource allocation and sharing for dynamically arriving jobs while considering the already assigned static ones. This problem is challenging and attractive computing paradigm in cloud computing for a wide variety of applications. This dynamic co-allocation for unpredictable jobs presents new challenges to resource management in multicluster systems, such as locating sufficient resources for these dynamic jobs in distributed sites, managing temporarily the job assignment and coordinating their executions with the processing of the static jobs.

Fig. 2 :

 2 Fig. 2: Running time of column generation algorithm.

  Job characteristics: Cj, ρj, φj and Nj Result: Feasible solution: a set Kt of configurations and values (Yi)i∈K

	t stating
	how many machines use each configuration
	t ← 0
	Kt ← K0
	repeat
	Solve RMP with variables in Kt
	Generate dual values π * j from the RMP solution
	Solve the subproblem with prices π * j
	if strictly negative reduced cost then
	Col ← new column with the coefficients of the subproblem solution
	t ← t + 1
	Kt ← Kt-1 ∪ Col
	end
	until no negative reduced cost solution;
	Solve RMP with variables in Kt as an integer program
	Algorithm 1: Column generation algorithm

Data:

Table 1 :

 1 Number of nodes required per heuristic. a instance has been extracted from this trace with 89 jobs corresponding to a total of 22600 tasks. The largest job in terms of tasks consists of 1608 tasks and the largest job in terms of CPU demand corresponds to the capacity of 184 nodes at its peak demand. A capacity equivalent to 2198 nodes would be required if all jobs reached their peak demand at the same instant. The overall peak demand for the whole set of jobs is equivalent to the capacity of 2090 nodes.

		Column generation Best-Fit Min-Max Min-Max-Module
		CG	BFD	MM	MMM
	Number of Nodes	2103	2182	2114	2226