Jiuqiang Chen1
email: chenj@lri.fr

Christine Froidevaux

Carole Goble
email: carole.goble@manchester.ac.uk

Alan R Williams
email: alanrw@cs.man.ac.uk

Sarah Cohen-Boulakia

DISTILLING STRUCTURE IN SCIENTIFIC WORKFLOWS

Motivation and Objectives

Scientific workflows management systems, (e.g., [START_REF] Missier | Taverna, Reloaded[END_REF][START_REF] Ludaescher | Scientific workflow management and the Kepler system[END_REF]Goeck et al. 2011)) are increasingly used to specify and manage bioinformatics experiments. An experiment is then represented by a workflow in which a large number of bioinformatics tasks are linked to each other. A workflow specification is a framework for the execution of workflows. It specifies the order to be observed between the different tasks and their relationships with the workflow inputs and workflow outputs. According to the input data given to the workflow specification and assignments of values to the task parameters, different workflow runs are then obtained and may lead to different intermediate and final output data. Both workflow specifications and runs are represented by graphs. Faced with the increasing complexity of runs and the need for reproducibility of results, provenance has become an important research topic. A significant number of tools for managing vast amounts of data provenance have been designed to assist the storage of provenance data (e.g., indexing), query the data (e.g., difference between executions, search for patterns), visualize the workflow provenance or (re)schedule executions... (See (Cohen-Boulakia and Leser, 2011) for a review on that topic). These tools all make intrinsically complex operations on graph structures (search for subgraphs in a graph, comparing graphs, ...), which, if carried out on Directed Acyclic Graphs (DAGs), with no other restriction of structure, lead to NP-hard problems. Instead, these problems can be solved in polynomial time when specific restrictions are imposed on graphs, such as considering series-parallel (SP) structures [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF]. Some provenance management approaches such as [START_REF] Bao | Differencing provenance in scientific workflows[END_REF][START_REF] Callahan | Vistrails: visualization meets data management[END_REF] have therefore chosen to restrict workflow graphs to SP structures. As in general, workflows obtained using workflow systems are DAGs with any structure, graphs transformation approaches such as [START_REF] Escribano | Performance implications of synchronization structure in parallel programming[END_REF] can be exploited to transform workflow graphs into SP graphs. [START_REF] Cohen-Boulakia | Scientific Workflow Rewriting while Preserving Provenance[END_REF] has recently designed SPFlow, the first algorithm able to rewrite any scientific workflow graph structure into an SP workflow structure while preserving provenance information. As expected, such an approach has a cost in that nodes and/or edges have to be duplicated in the rewritten workflow. Determining the reasons why some workflows have non SP structures may help users to directly design workflows having a structure closer to SP structures. The rewriting process may then be used on less complex, distilled, workflows. The aim of this paper is to present the results obtained on the study that we have conducted on the set of Taverna workflows [START_REF] Missier | Taverna, Reloaded[END_REF] available on myExperiment [START_REF] De Roure | The Design and Realisation of the myExperiment Virtual Research Environment for Social Sharing of Workflows[END_REF] to analyze the reasons why workflows have non SP structures.

Methods

Our study has been conducted on a set of 1,014 distinct workflows extracted from the Taverna workflows available in myExperiment in May 2012. We have implemented the algorithm of [START_REF] Valdes | The recognition of series parallel digraphs[END_REF] to detect whether workflow graphs are SP. Intuitively, SP structures are graph structures having one main input (I in figure 1(a)) and one main output (O in Figure 1(a)), without loops and which can be synchronized. In particular the pattern highlighted in Figure 1 (b) is forbidden (in this pattern, arcs can be replaced by paths involving intermediate nodes). In this pattern, node w is responsible for the graph non to be SP. Such a node is called a reduction node [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF] and is duplicated in SPFlow. In the workflow depicted in Figure 1(a) the getGeneInfo processor is a reduction node so that the workflow is not SP. Among the 390 workflows with non SP structures (38,5%), we have focused on identifying reduction nodes and analyzed the forbidden pattern in which they were involved.

We have then driven two series of experiments: -The first series of experiments has consisted in analyzing the structure of a subset of workflows having complex non SP structures. -In the second series of experiments, we have considered all the non SP workflows of Taverna and we have conducted a study of the processors involved in non SP structures. We have identified the kinds of processors mostly involved in non SP structures and we have then made a more precise analysis by examining the processors themselves.

Results and Discussion

Trace links: The first series of experiments highlight the fact that some intermediate processors are directly linked to the workflow outputs merely for the sake of keeping track of intermediate results. We call such intermediate processors trace nodes and their outgoing edges linked to the workflow outputs are called trace links. On a total of 13,754 nodes in the set of non SP workflows, we found 1,524 reduction nodes including 631 reduction nodes that are also trace nodes (representing 41% of the reduction nodes) and involved in 361 workflows (representing 92.6% of non SP workflows).

Interestingly, trace links could be removed by exploiting the powerfulness of the provenance module of Taverna that is in charge of collecting all intermediate and final results obtained and consumed during each execution.

Ongoing work includes focusing on the workflows for the BioVeL project and work in close collaboration with the workflow writers for potential improvement in the structure of some workflows when trace links may appear.

Non-SP-only processors: The second series of experiments revealed that most reduction nodes correspond to local processors (processors provided by Taverna to workflow designers) and web services processors. In particular, among a set of 92 web services, 40 services only appear in non SP workflows and occur at least once as reduction nodes. More interestingly, nine services appear only as reduction nodes in Non SP workflows. We call them Non-SP-only processors. As for local services, we found one Non-SP-only local processor. Ongoing work includes investigating ways to modify the use of Non-SP-only processors (e.g., changing the processors ports, grouping several consecutive calls of the same processor, designing SP patterns of joint use) so that they are not anymore systematically associated to (and possibly responsible for) non SP structures.

In conclusion, we have identified several reasons why workflows may not have an SP structure.

Following the solutions underlined, we will get distilled workflows in which the number of reduction nodes should importantly be reduced and we hope that a large part of workflows may become SP. In our approach, users do not have to consider structural constraints when they design workflows; our aim is instead to provide them with designing guidelines ensuring that distilled workflows are naturally produced.

Figure 1 :

 1 Figure 1: (a) Example of a non SP structure from myExperiment; (b) forbidden pattern

Acknowledgements

This work has been partly supported by the INRA-INRIA ASAM project. J. Chen has been supported by the China Scholarship Council (CSC).


Zahira Aslaoui-Errafi

Sarah Cohen-Boulakia

Christine Froidevaux

Pauline Gloaguen

Anne Poupon

Adrien Rougny

Meriem Yahiaoui

Towards a logic-based method to infer provenance-aware molecular networks

Providing techniques to automatically infer molecular networks is particularly important to understand complex relationships between biological objects. We present a logic-based method to infer such networks and show how it allows inferring signalling networks from the design of a knowledge base. Provenance of inferred data has been carefully collected, allowing quality evaluation. More precisely, our method (i) takes into account various kinds of biological experiments and their origin; (ii) mimics the scientist's reasoning within a first-order logic setting; (iii) specifies precisely the kind of interaction between the molecules; (iv) provides the user with the provenance of each interaction; (v) automatically builds and draws the inferred network.

Context

Biological objects (proteins, genes, small molecules, etc.) interact with each other (physical interactions, activations, inhibitions, catalyses, etc.) and form biological networks. Studying such networks allows the discovery of emerging properties and the understanding of complex biological systems. With the rise of highthroughput experimental methods and the rapid development of bioinformatics analysis methods, there has been a dramatic increase in the quantity and heterogeneity of available data. Providing methods able to automatically construct molecular networks from experimental data is thus of paramount importance. While the series of DREAM workshops competitions have been attempting to address these issues since 2007 (http://www.the-dream-project.org/), they are still challenging. In the ASAM project, we aim to meet the challenging task of designing performant algorithms to infer the topology (or influence graph) of signalling networks (subtask of current DREAM7), a first step in the process of elaborating predictive dynamical models. Given the components of the network, building the influence graph consists in determining which relationships they share (e.g., enzymatic catalysis, (de-)phosphorylation, etc.).

Among the approaches available, some provide focused solutions: on connectivity reconstruction (finding which molecules interact with each others from a dataset, without specifying the type of relationship), or on causal reconstruction (finding effects that molecules may have on each others) [START_REF] Papin | Reconstrution of cellular signalling networks and analysis of their properties[END_REF]. Some approaches proceed by refining existing molecular networks [START_REF] Morris | Training Signaling Pathway Maps to Biochemical Data with Constrained Fuzzy Logic: Quantitative Analysis of Liver Cell Responses to Inflammatory Stimuli[END_REF], which requires the knowledge of an initial network to be analyzed. Others proceed by inferring the network, considering only a single type of experimental method at a time, mostly DNA micro-arrays [START_REF] Bansal | How to infer gene networks from expression profiles[END_REF] [4] [START_REF] Chiquet | SIMoNe: Statistical Inference for MOdular NEtworks[END_REF], but also phosphoproteomics [START_REF] Prill | Crowdsourcing Network Inference: The DREAM Predictive Signaling Network Challenge[END_REF] [22] [START_REF] Mitsos | Identifying drug effects via pathway alterations using an integer linear programming optimization formulation on phosphoproteomic data[END_REF], or metabolomics [START_REF] Cakir | Metabolic network discovery through reverse engineering of metabolome data[END_REF] etc. Therefore they cannot infer complete pathways involving interactions of different types, failing to provide an holistic view necessary to the understanding of the complexity of living cells [START_REF] Markowetz | Inferring cellular networks -a review[END_REF].

Approaches integrating a variety of different experimental data types have also been proposed [START_REF] Hwang | A data integration methodology for systems biology: Experimental verification[END_REF][24], but they reconstruct only partial network topologies, and define relations without causality (the interactions are not marked as being activations or inhibitions).

Automatic inference of topological networks is performed using various computational approaches that range from statistics [START_REF] Drozdov | Gene Network Inference and Biochemical Assessment Delineates GPCR Pathways and CREB Targets in Small Intestinal Neuroendocrine Neoplasia[END_REF] to machine learning techniques (e.g. bayesian networks [START_REF] Bansal | How to infer gene networks from expression profiles[END_REF]) through logic-based techniques such as boolean networks [START_REF] Wittmann | From Qualitative to Quantitative Modeling[END_REF] [START_REF] Inoue | Logic Programming for Boolean Networks[END_REF] or fuzzy logic networks [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF]. Most of these techniques allow performing model-based prediction as well. In addition, logic-based approaches are particularly well-suited to analyze the consistency of a network towards experimental data by model-checking [START_REF] Guziolowski | Curating a Large-Scale Regulatory Network by Evaluating Its Consistency with Expression Datasets[END_REF], [START_REF] Gebser | Detecting inconsistencies in large biological networks with answer set programming[END_REF]. Our approach to automatically build the inference graph underlying signalling networks leads to the design of a logicbased model (see Figure 1), in the same spirit as [START_REF] Eduati | A Boolean approach to linear prediction for signaling network modeling[END_REF] but with a more expressive logical formalism which allows making explicit the expert reasoning. The rest of this paper is organized as follows. Section 2 introduces the Knowledge Base where expert's reasoning is made explicit and a wide variety of experimental data is stored, and shows how the network can be deduced. Section 3 is dedicated to the process of building and drawing the network automatically. Section 4 presents our validation approach while Section 5 draws conclusions and perspectives.

Building the Knowledge Base (KB)

Our network inference method is based on the application of reasoning rules to experimental facts. These general rules formalize how experts deduce from experimental facts the belonging of a given molecule to the network and the relationships it shares with other molecules of the network. To achieve the proofof-concept for this method, we have formalized the knowledge necessary for inferring the signalling network triggered by the FSH receptor [START_REF] Gloaguen | Mapping the folliclestimulating hormone-induced signaling networks[END_REF]. This involved the creation of first-order rules for seven types of experiments.

The design of the KB classically consists of a set of predicates, rules, and facts (ground predicates) described here after.

Predicates

We distinguish three classes of predicates, depending on their biological meaning. Basic predicates provide ontological types or indicate simple relationships between data (e.g., AntibodyAgainst(A,X) means that A is an antibody recognizing molecule X). Experiment predicates describe a wide panorama of experiments on molecular data from simple to more complex experiments involving perturbators. An example of a simple experiment is PA(X,Y,A,E), meaning that "in a phosphorylation assay (PA) we observe more (resp. less, the same quantity) of the molecule revealed by antibody A, which is a phosphorylated form of molecule Y, in presence of X than in absence of X, where E can be either 'increase', 'decrease' or 'noeffect'". An example with a perturbator is ICPPA(X,Y,I,A,E) meaning that "in a phosphorylation assay (PA) in presence of X we observe more (resp. less, the same quantity) of the molecule revealed by antibody A, which is a phosphorylated form of molecule Y, in presence of inhibitor I than in absence of I, where E can be either 'increase', 'decrease' or 'noeffect'". Table 1 shows all the experiment predicates relative to phosphorylation assays (in the variables, the antibody variable A is replaced by the molecule variable Z it triggers). All the experiments have been formalized by predicates divided into three types depending on the kind of conclusion they allow one to obtain: modulation of a reaction, structure, or localization, and each predicate has been carefully designed and documented as depicted in Table 1. Network Predicates formalize the different types of biological relationships that can exist between two or more biochemical species (modification, phosphorylation, translation, transcription, complexation, dissociation) taking into account the modulation of these relationships by another species (activation, inhibition or no effect). The modulation of the relationships may be associated with a level of confidence, expressed by the status variable (taking values among: 'invalidated', 'confirmed' or 'hypothesis'). Additionally, the precision of the mod- meaning that "If in a phosphorylation assay where A is an antibody that recognizes B, B is a phosphorylated form of Y at position POS, we observe more (resp. less, the same quantity) of B in presence of X than in absence of X, then X activates (resp. inhibits, does not have any effect on) the phosphorylation of Y in B, with an unknown distance, where E can be 'increase', 'decrease' or 'noeffect'".

Initial and Deduced Facts

Based on the study of the literature and data from public databases (e.g., SBEAMS, http://www.sbeams.org/), predicates have then been instantiated into facts. Facts have been carefully attached to their provenance, specifying the article(s) and/or the data base(s) from which they have been extracted. Various data quality features have been made as explicit as possible in particular the level of confidence to be associated to a set of experimental results. Initial facts have then been used to produce deduced facts by triggering rules. As expert rules are mostly Horn rules, we have mainly considered using forward chaining procedures for rules-base systems [START_REF] Forgy | Rete: A Fast Algorithm for the Many Pattern-Many Object Pattern Match Problem[END_REF], leading to a saturation of the KB. In order to tackle more expressive rules (e.g. typing rules) and facts involving functional terms that describe molecular complexes, we have also been considering first-order consequence-finding techniques. In these settings, provenance information of deduced facts is obtained from their proof(s) making it possible to assess their quality from the quality of initial facts used in the deduction process.

The network topology is automatically built from our initial and deduced facts using the software CellDesigner [START_REF] Kitano | Using process diagrams for the graphical representation of biological networks[END_REF], that is widely used to model molecular networks. CellDesigner uses (and extends) two standards, SBML (Systems Biology Markup Language) [START_REF] Hucka | The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models[END_REF] and SBGN (Systems Biology Graphical Notation) [START_REF] Novère | The Systems Biology Graphical Notation[END_REF], for the description and representation of molecular networks. CellDesigner can represent: cell compartments, biochemical species (nodes of the network) and reactions (arcs). Each biochemical species is localized in one or more compartment, and assigned to a biological type (e.g., complex, protein). Each reaction has a type (e.g., translation, transcription) and at least one reactant species and one product species, and can be modulated (e.g., activated/catalyzed) by one or more modifier species. The various species, reactions and types are represented in the network by different forms of nodes and arcs (e.g. ovals for simple molecules; plain lines for state transitions).

Our facts (initial and deduced) are automatically translated into the extended version of SBML that CellDesigner uses. Initial facts are used to describe the chemical species of the networks (name, type and residue modifications, e.g a phosphorylation on the residue S132). The deduced facts are used to describe the reactions (type, reactants, products and modulations) and species localizations. The status and the distance of the reaction modulations are modelled by different line-styles of arcs linking a modifier species to a reaction (e.g. black line for a confirmed status or red line for a hypothesis status) in the network. The layout of the network is then automatically calculated by CellDesigner. This automatic process is illustrated by a short example.

Example. Let phosphorylate(fsh,mek1,pmek1s17,indirect,confirmed,increase) be a deduced fact to be represented with CellDesigner. First, the fact has to be translated into (extended) SBML. It describes a relation between the molecules (first three arguments) fsh, mek1 and pmek1s17 (the latter being phosphorylated-mek1 at position S17). To declare precisely these molecules into CellDesigner, the KB is queried to get their type (protein(fsh), protein(mek1) and phosphoprotein(pmek1s17)), their localization in the cell (localization(fsh,extracellular), localization(mek1,cytosol) and localization(pmek1s17,cytosol)) and their possible residue modifications (phosphoform(pmek1s17,mek1,s17)). This is given by initial facts of the KB that are retrieved by exploiting the predicates typology. Second, the deduced fact is translated into an SBML reaction. Here, the type of reaction is a state transition (phosphorylation), the reactant is the second argument (mek1), the product the third (pmek1s17) and the reaction is activated (increase) by the first argument (fsh). Because the modulation of the reaction has a status confirmed and is indirect, the line-style of the arc representing the modulation is declared as being black and dashed. A phase of trial and error may be necessary in order to validate the method, before using it in production phase. This validation phase will require an important accumulation of data. Indeed, we need to infer automatically the networks from experimental data and compare them to networks of the literature to seek for missing links (links absent while expected), indicating missing reasoning expert rules which will need to be written. This upstream work has already been done for the follicle-stimulating hormone receptor (FSH-R) [START_REF] Gloaguen | Mapping the folliclestimulating hormone-induced signaling networks[END_REF]. Even with this quite simple network, over 400 initial facts and 100 expert rules were necessary. Once processed, the KB contained over 1,000 (initial and deduced) facts. Two different serotonin receptors (5HT2 and 5HT4) and Epidermal Growth Factor receptor (EGF-R) are currently considered. We envisage to speed up the detection of biological objects in the literature that will be used within facts by using text mining tools such as PathText [START_REF] Kemper | PathText: a text mining integrator for biological pathway visualizations[END_REF]. We expect that after studying a few networks, expert rules will be complete, validating the KB. During this validation phase and the following production phase, the inferred networks will be analyzed and all the unexpected conclusions will be validated experimentally.

We have introduced a bottom-up method to infer molecular networks whose originality lies in its knowledge-driven basis. More precisely: (i) domain knowledge is collected from experts, literature and public databases, and data from classical and high-throughput experiments; (ii) the scientist's reasoning is mimicked within an expressive logical setting (first-order logic); (iii) the kind of interaction between the molecules is precisely specified; (iv) provenance of deduced facts (translated into interactions) is provided, allowing users to evaluate the quality of the inferred pieces of knowledge; (v) the inferred network is automatically built and drawn, offering the possibility of interacting with it.

Such an automated method, allowing automated exploitation of experimental data and resulting in molecular networks, will become increasingly necessary with the spread of huge amounts of data produced by large-scale experimental methods.

Ongoing work include considering techniques to formalize efficiently expressive rules and facts (including considering encoding into a propositional setting). Importantly, while all our current efforts have been made on deductive reasoning, we need also to consider exploring abductive reasoning to help scientists understanding how the biological system can be perturbed to reach a desired behaviour. Users may wish to know which facts or rules are to be added to reinforce the reliability of an existing arc or to add a new arc in the network. Determining the rules and pieces of data to be added to the initial KB to get the desired behaviour is obtained by the abduction reasoning that will provide all the possible hypotheses expressed in terms of initial facts and logical rules. Advices will thus be given to the scientists about the new experiments to be conducted to validate some hypothesis. As a consequence, we are currently looking at systems able to provide both deductive and abductive reasoning and are considering the SOLAR system as a first excellent candidate [START_REF] Iwanuma | SOLAR: An automated deduction system for consequence finding[END_REF].

Fig. 1 .

 1 Fig. 1. Workflow of our logic-based method to infer molecular networks

Fig. 2 .

 2 Fig. 2. Building elements of network with CellDesigner

Fig. 3 .

 3 Fig. 3. Workflow for validation of our method to infer molecular networks

Table 1 .

 1 Phosphorylation assays predicates.We have designed two sets of rules. Simple rules use experimental data to draw conclusions on new relationships between biochemical species. Complex rules use the conclusions obtained by other rules and either provide new data relationships or refine existing relationships. They include transitive rules and rules that

	Pred name Deduction Method Variables Res type Type (y) Type (z) Perturbator (i)
	PA, PRA			Phosphoryl.		None
	ACPPA Modulation Measure x,y,z,e of y into z Protein Phospho-Antagonist
	ICPPRA	of a	of an x,y,i,z,e	in the	Protein	Inhibitor
	ICPPA	reaction activity	presence		Inhibitor
	SCPPA			of x		siRNA
	ulation may vary, which is expressed through the distance variable (taking the
	values 'direct', 'indirect', or 'unknown'), meaning that a molecule has a direct
	effect on a relationship (for example, it catalyzes a reaction) or it has an effect
	via intermediaries, or that this information is currently not available.
	2.2 Rules

deduce an indirect distance (see above) from an unknown distance for a network fact. A simple rule is: IF PA(X,Y,A,E) AND AntibodyAgainst(A,B) AND PhosphoForm(B,Y,POS) THEN PHOSPHORYLATE(X,Y,B,unknown,confirmed,E)

This work has been supported by the INRA-INRIA ASAM project.


Ghislain Landry

Tsafack Chetsa

Laurent Lefevre
email: laurent.lefevre@ens-lyon.fr

Jean-Patrick Gelas
email: jean-patrick.gelas@ens-lyon.fr

On Applying DTNs to a Delay Constrained Scenario in Wired Networks

The Delay/Disruption Tolerant Networking (DTN) architecture has been successful in addressing communication issues such as disruption, variable delay, and network partitioning. DTN uses intermittently available links to communicate opportunistically regardless of delivery delay. In the literature, much work has been done mainly to improve the rate of message delivery and routing algorithms. However, previous work has not focused on guaranteeing the message delivery delay in a DTN scenario. In addition, real deployments of DTN systems have so far been mostly proof-of-concepts in research projects. We address the problem of delivery delay in a wired DTN scenario where messages are moved across a time-varying graph topology whose dynamics are known in advance and can be modified. We propose a framework that guarantees bounded delivery delay of users' data. To demonstrate the feasibility of our network management approach, we evaluate our framework on a 10-node wired DTN topology deployed on the Grid5000 platform 1 .

I. INTRODUCTION

Delay/Disruption Tolerant Networking (DTN) [START_REF] Cerf | Delay-Tolerant Network Architecture[END_REF] has been used successfully in challenging environments to address several communication issues such as disruption, long delays, and network partitioning. Examples of scenarios where DTNs have been employed include terrestrial civilian networks connecting mobile wireless devices; wireless military networks connecting troops on battlefields, aircrafts, satellites and sensors; exotic media networks using near-earth satellite communications; and long distance radio. A DTN works using a Store and Forward message switching approach for packet delivery, which is more resilient to disruption [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF].

The DTN technique can be useful in scenarios ranging from interconnecting sensors to connecting PCs over the Internet. Considering wired networks, the asynchronous message delivery system used on the Internet can benefit from a DTN abstraction [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. Moreover, Peer-to-Peer (P2P) networks may exhibit many DTN-like characteristics such as link and node unavailability. Nevertheless, DTN has been used in rather few scenarios in wired networks. In this work, we present a scenario of wired networks with delivery delay constraints that benefits from DTN. Our work focuses on dedicated networks with advance bandwidth reservation features used for bulk data transport. The network is designed to switch off links and nodes not used by data transfers for specific reasons (e.g. to achieve energy savings). In this context, to avoid affecting the utilisation of the network and degrading its performance, users should be able to send bandwidth reservation requests irrespective of the state of the network. In addition, users should be able to receive a response within a reasonable time.

This paper introduces the Management Framework for On/Off Network (MFO 2 N); the foundation for providing management of information transfer with quality of service in a DTN-like manner, with the primary goal of making network unavailability transparent to users. The quality of service (QoS) is perceived in terms of delivery delay. For this purpose, we combined the DTN Store and Forward message switching with a proactive switch On/Off mechanism to transmit user requests, which may either (1) arrive at a network node where the link to the next hop towards its destination is down (or the next hop itself) or (2) be timed out in a DTN router's forwarding queue. We present preliminary results that permit us to validate our approach.

The rest of the paper is organized as follows. Section II presents a short overview of the DTN architecture. Motivations for applying DTNs to a wired-network scenario are presented in Section III. Section IV details our solution. We present and analyse evaluation results in Section V, and finally conclude and present future work in Section VI.

II. BACKGROUND

The DTN architecture is a generalization of the interplanetary Internet defined by NASA. The main improvement offered by the DTN architecture with respect to the traditional ISO protocol stack is the implementation of the Bundle Protocol (BP) [START_REF] Scott | Bundle Protocol Specification[END_REF].

The most popular implementation of the delay tolerant network architecture's Bundle Protocol include the DTN2 [4] reference implementation and the ION software [START_REF] Jpl D-48259 | [END_REF], [START_REF] Burleigh | Interplanetary overlay network: An implementation of the DTN bundle protocol[END_REF]. ION implements the Contact Graph Routing (CGR), which is suitable to our work. The CGR is a procedure for computing efficient bundle forwarding routes between source and destination endpoints of Delay-Tolerant Networks when connectivity between pairs of neighboring bundle protocol agents is scheduled and discrete rather than continuous. Some DTN projects include the SARAH project [7], the Haggle project from the European Union Framework Program [8] and the MISUS (Multi-Rover Integrated Science Understanding System) project [9] from NASA JPL.

The literature does not describe many DTN scenarios in the context of wired networks, which is reasonable as the DTN architecture was originally designed to enable communication within extreme environments. In [START_REF] Laoutaris | Delay-Tolerant Bulk Data Transfer on the Internet[END_REF], the authors present the DTN architecture as a feasible approach for transferring bulk data over the Internet, taking advantage of already-paid and off-peak bandwidth from commercial Internet Service Providers (ISP). Similarly, in [START_REF] Laoutaris | Good Things Come to Those Who (Can) Wait or How to Handle Delay Tolerant Traffic and Make Peace on the Internet[END_REF] the authors introduce the delay tolerant traffic on internet. They leverage on the delay tolerance characteristic of some types of traffic over internet including P2P bulk data download to shift them to non-peak load hours, therefore guaranteeing bulk data transfer at flat rate.

III. WIRED DTN SCENARIO DESCRIPTION

Recent work by Orgerie et al. [START_REF] Orgerie | Energy-Efficient Bandwidth Reservation for Bulk Data Transfers in Dedicated Wired Networks[END_REF] has resulted in the design of a bandwidth scheduler for bulk data transfer applied to high performance reservation-based networks. The work attempts to reduce the energy consumed by such networks by switching nodes and links off and on according to their usage. Our work builds on previous efforts by employing DTN to handle the disruption that the energy saving approaches may cause and by making this process transparent to users.

In the work of Orgerie et al., a scheduler assigns a pointto-point path between two nodes A and B once a bandwidth reservation request is successful (a reservation request is successful when a positive acknowledgement message is send back to the sender by the receiver). Once the point-topoint path is found, the scheduler aggregates all bandwidth reservations per link locally on each node of the path and then creates a local schedule named On/Off agenda, denoted as Ag. The On/Off agenda, local to each node, is actually a chronologically ordered list of On/Off events describing the future network usage. Thus, a given network node N maintains an agenda whose elements are of the form (t i , N, ACTION), and (t i ,l, ACTION) where:

• t i is the time when the action ACTION starts.

• l corresponds to a network link connected to N.

• There are two types of actions: when the action is On, the corresponding network component is switched on ( when that component is a node, the "switch on" event is triggered by a remote note via the control network described in Section IV-A5) conversely, when the action is Off the link/node is switched off. For instance, (t i , N, On) is literally equivalent to "at time t i if the node N is off, then switch it on". Based on the On/Off agenda described above, we define an algorithm, which is executed simultaneously on all network nodes and maintains active only network components (links and nodes) needed for a preplanned data transfer. This algorithm intends to keep the network off while making links/nodes available for data transfers if necessary. However, this cannot be transparent to users since to reserve the path (by sending bandwidth reservation requests) for their upcoming data transfer they would like to keep using the network irrespective of its state. To this purpose, knowing that the network is liable to be off (or partially off), we associate a lifespan with each reservation request. The request's lifespan, fixed at its submission time by the user, is actually the maximum number of seconds after which the user expects to receive a response to his/her request. It determines how long the request can be kept in the network while waiting for a communication opportunity. Hence, all requests according to their lifespan have delay tolerance that range from a few seconds to several hours, i.e., they can be several orders of magnitude greater than the time scales of Internet traffic engineering.

!"#$%&$ '()* #)+*,-.$)/)0+1 23034)- 54)0%3 23034)- 6(0.1 23034)- 7,0+-,8 2,%98) :*(+7;(04 +3&8) '(-+938$-)<9)1+1 23034)- $-)<9)1+1 23034)-
DTNs are designed to overcome long and variable delays [START_REF] Warthman | Delay-tolerant networks (DTNs) : A tutorial v1[END_REF], but from the best of our knowledge they cannot guarantee on-demand response times. To enable this feature, we combine the DTN Store and Forward message switching with the proactive switch-on mechanism, making links/nodes available to service management information transport (bandwidth reservation requests in this case).

IV. MANAGEMENT FRAMEWORK FOR ON/OFF NETWORKS (MFO 2 N)

A. Functions

We present in this section the Management Framework for On/Off Networks, an implementation of the network management model described in Section III. The main objective of the proposed framework is to guarantee on-demand response time to users as well as reliable transport of requests. To guarantee the response time that users expect, which corresponds to the offered QoS in a network that is likely to be off, MFO 2 N manages to switch on network links/nodes for servicing timedout requests. MFO 2 N relies on the Interplanetary Overlay Networking (ION) software, an implementation of the DTN architecture to which we have made substantial changes. MFO 2 N consists of several functional elements (see Figure 1) of which a detailed description is given below.

MFO 2 N could be used for transmitting several type of information including data messages. However for simplicity sakes only bandwidth reservation requests are submitted to the DTN architecture while propagating in the network, whereas data messages are routed the usual way along an end-to-end chain of available links and nodes.

1) Agenda Manager: Each network node maintains an agenda, a list of events describing its future behaviour. The agenda manager local to each node is responsible for making resources (links and nodes) available for data transfers. It periodically browses the agenda to trigger events whose start time is the current clock time. Thus, when an event is triggered, the corresponding action is executed. If that action is an "Off" action, then the network manager checks the corresponding link state (the link may be transmitting data) and switches it off if the link is not transmitting data; otherwise it is tagged. The tagging introduced here can serve various purposes. For instance, it can be used to monitor the network traffic crossing the link in order to take more intelligent decisions in case of link's proactive switch on. However, in our case, it is only used to determine whether the state in which a link is (on or off) was planned or not.

2) Links and Requests Manager: The main goal of the link manager is to achieve pro-active switch-off mechanism monitoring and switching off tagged links, i.e., links proactively powered on. An important consideration in the design of MFO 2 N is how long should a link, pro-actively powered on, remain on before it is switched off. Three approaches can be considered.

1) Each tagged link has a minimum lifespan of min_lifespan seconds (the choice of which depends on the network topology), that is tuned according to the network traffic crossing the link. This approach is however difficult to implement. 2) Easier to implement, the second approach considers an arbitrary lifespan of max_lifespan seconds after which the link is switched off if not in use. The maximum lifespan can be the maximum delay on the Internet.

3) The third approach, called the ACK-based, sits between the previous two approaches. It is based on a straightforward principle described as follows: when a link is proactively switched on, an acknowledgement of the pushed request is created and stored locally on the node. As the request reaches its destination, an acknowledgement is sent back to the sender. The acknowledgement then triggers on each node the destruction of its "local acknowledgement" if any. The link is normally powered down after the local acknowledgement is deleted, but the acknowledgement may not reach the node, in which case the link is powered down after max_lifespan seconds.

The minimum lifespan of a link is chosen according to the network topology as follows: given a network of N nodes, let k be the number of links in the longest path without loop between two network nodes. Assuming that the difference between the moment at which a link is powered on and the moment when it can transmit data is t seconds, the minimum lifespan of a link noted min_lifespan in the worst case is given by t * k seconds.

The request manager task consists of transmitting users bandwidth reservation requests to the under-layer communication software. However, it can switch on a link if needed for transmitting users data.

3) Virtual request manager: The DTN retransmission mechanism requires that each message traversing a forwarder node (router) be stored before retransmission. We leverage that to make a copy of each request stored by ION in its data structure known as an ION database or SDR for Software Data Recorder. The duplicated request known as "virtual request" is then stored in an MFO 2 N data structure, which is for convenience called the application database. As a request leaves the node (is forwarded), its corresponding virtual request is removed from the application database.

The virtual request manager, not mandatory on non-router nodes, periodically browses the application database and switches on one or several links when either it finds a request whose lifespan has expired or the application database size has exceeded a given threshold TH. This process is called "proactive switch on" of link and is summarised in Algorithm 1.

4) Network Events Manager:

The events manager is responsible for all communication with the control network and "non standard" communication with the under-layer communication software ION. The non-standard communication mentioned above refers to all accesses from the designed application to ION software's specific data such as its outgoing queues size, dynamic routing decisions and user data.

5) Control Network/Module:

The Magic Packet Technology was recently introduced to remotely wake up sleeping nodes on a network. Since this is accomplished by sending a specific packet of information, called the Magic Packet to the sleeping node, the communication will fail when the receiver is down. To overcome this problem, it is becoming common to believe that an alternative low power consuming network should be used to access switched-off network components. Called control network in our work, the alternative low-power network can be a GPRS (General Packet Radio Service) network.

B. MFO 2 N Design Considerations

One of the most important features of MFO 2 N is its capability to switch on/off links when needed, but the problem is how to determine which links should be powered on given a specific user request. The routing process usually forwards packets on the basis of the routing table, which maintains a record of the routes to various network destinations. Similarly, MFO 2 N makes links available on the basis of a switching table that maintains a record not of the routes but of the links to various network destinations.

1) Links Selection: The switching table maintained by each routing node reflects the routing process performed by the communication protocol ION. It therefore needs to be updated each time a new communication opportunity appears. To this end, MFO 2 N uses previous routing decisions made by ION to predict which link should be used to various network destinations.

There can be many entries for the same destination, but our implementation always chooses the first. However, a more intelligent design would take the link leading to the less power consuming path.

2) Link Representation: ION uses unidirectional links, thus a bidirectional link connecting a node A to a node B denoted A←→ B will be represented by a couple of unidirectional links as follows: A←B, B→A. Each node maintains a record of links of each of the extremities. For instance, considering the following network configuration A←→ B←→ C, nodes A, B, and C will maintain respectively A{A→B}, B{B→A, B→C}, and C{C→B}. So doing, we ensure that links power on/off are synchronised.

C. Example

This section presents an example scenario for better understanding of the MFO 2 N execution model. The most representative execution steps are depicted in Figure 2. Each node maintains an agenda per outgoing link, but only one agenda is shown here for the sake of clarity.

Initially, i.e, at time t = 0, no path exists between source and destination. At time t = 2s (step 2) the source node S has a message of lifespan 30 seconds destined for the node D. As the link to the next hop i.e, node 1 toward the destination is on, the message is forwarded without any delay to node 1. The message is then stored by node 1 as the link l2 to the next hop toward the destination is off. A transmission opportunity arises at t = 11 (when a link is switched on, the time after which it is able to send and/or receive data can vary significantly according to many factors including its technology, the distance between its extremities, etc. In our case we assume that a link after being switched on will be available for transmitting or receiving data only after 1s) between node 1 and node 2, the message is then forwarded to node 2 which immediately transmits it to node 4. At this point node 4 does not have any next hop to route the message to the destination D, so the message is stored while waiting either for a communication opportunity or for its lifespan to expire. At time t = 32 (step 4) since the message lifespan is expired, the proactive switch-on mechanism powers on the link to the next hop which is actually the destination. The message is forwarded to the destination D at time t = 33s. Upon receiving the message, node D then sends an acknowledgement (ACK) to the source node S. On the path to node S the ACK requests all links that were switched on pro-actively to switch off if necessary.

V. E VA L UAT I O N

The evaluation of MFO 2 N was performed on the Grid5000 platform [START_REF] Cappello | Grid'5000: A large scale, reconfigurable, controlable and monitorable grid platform[END_REF]. We deployed via ION a 10-node network topology comprising 6 DTN forwarders (core nodes) and 4 end-nodes all running the 2.2.1 version of the customized ION software. The considered network topology is realistic as it includes heterogeneous links, and exhibits many Internet-like characteristics such as: cross traffic, multiple routing possibilities between nodes, and bandwidth sharing. For simplicity and clarity sakes, the bandwidth is reduced by factors of 10 and 20; network nodes numbered from 1 to 10, and links denoted as shown in Figure 3.

During all experiments, max_lifespan and min_lifespan parameters were set to 35 and 10 seconds respectively. Links previously switched on pro-actively were switched off following the ACK-based approach whereas the maximum number of requests (TH) residing on a forwarder was set to 10.

We consider several agenda scenarios of a few minutes in which end nodes, i.e, nodes 1, 2, 3 and 4, send and/or receive bandwidth reservation requests. A bandwidth reservation request is injected into the network by one of these nodes every 10 seconds; source and destination nodes are chosen randomly. In this way, we are able to repeat the experiment with the same number of requests crossing the network at any moment. However, for simplicity all requests injected in the network along with the experiment do not alter the agenda. It is worth to mentioned that a reservation request normally alter the agenda once it is acknowledged.

Due to lack of space, we only present results from one scenario, in which we consider an empty agenda (i.e., an agenda with only one event calling the network to switch off at the beginning of the experiment) along with requests whose lifespan is 5 seconds each.

We instrumented the requests' acknowledgement messages to derive the response time of bandwidth reservation requests sent during the experiment. Figure 4a presents the distribution of response times for the bandwidth reservation requests. It can be seen from the figure that many requests are acknowledge before the end of their expected response time, which is 5s. However, some requests are acknowledged several seconds after their expected response time, a factor that can be attributed to these requests following a path along which many links had to be switched on (in our scenario, once a link is switching on, it will be able to send or receive messages after 1s). We are investigating whether we can provide bounds for response time.

The variation in the number of active links on the network over time is presented in Figure 4b. The plot shows that despite the network being rarely entirely active, only half of the links are on average powered on all the time. Figure 4b actually demonstrates the ability of our framework of guaranteeing reasonable response times in a network that is likely to be off to save energy.

VI. CONCLUSION

In this paper, we looked at the possibility of deploying a DTN system over a high performance dedicated wired network infrastructure which, for specific reasons such as saving energy, is designed with the capability of switching equipments off and on. Our main objective was to make the network infrastructure's off-periods transparent to users by guaranteeing on demand response times and connectivity during these periods. To this end, we developed MFO 2 N, a DTN-based fault tolerant framework that offers, in addition to the DTN ability to enable communication through intermittently available links, the capability of ensuring specific delivery delays. We then run MFO 2 N on a 10-node network topology deployed on the Grid5000 platform and showed through experiments and examples the feasibility of our approach. One of the major contributions of this paper is the ongoing DTN deployment effort in wired networks which is almost non-existent in the literature due to the lack of feasible scenarios. This work is ongoing, and we envisage to integrate our framework as a module of the under-layer communication software.

Figure 1 :

 1 Figure 1: MFO 2 N architectural model.

Figure 2 :

 2 Figure 2: An example of MFO 2 N execution scenario.

Figure 3 :

 3 Figure 3: Network topology.

Figure 4 :

 4 Figure 4: Evaluation scenario.

The Grid'5000 platform is an initiative of the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (http://www.grid5000.fr)

ACKNOWLEDGEMENT

This work is supported by the Hemera INRIA Large Wingspan project. The authors would like to acknowledge Anne-Cécile Orgerie (Ecole Normale Superieure of Lyon) for her help in providing trace results as well as the ION software developer's team.


Ghislain Landry

Tsafack Chetsa

Laurent Lefevre
email: laurent.lefevre@ens-lyon.fr

Jean-Marc Pierson
email: pierson@irit.fr

Patricia Stolf
email: stolf@irit.fr

Georges Da Costa
email: dacosta@irit.fr

DNA-inspired Scheme for Building the Energy Profile of HPC Systems

Energy usage is becoming a challenge for the design of next generation large scale distributed systems. This paper explores an innovative approach of profiling such systems. It proposes a DNA-like solution without making any assumptions on the running applications and used hardware. This profiling based on internal counters usage and energy monitoring allows to isolate specific phases during the execution and enables some energy consumption control and energy usage prediction. First experimental validations of the system modeling are presented and analyzed.

Introduction

Software solutions to improve the energy consumption of computing systems often fall into two categories, namely application-level solutions and system-level solutions. At the application level, a power-aware application design can use technologies such as Dynamic Voltage and Frequency Scaling (DVFS) for CPU energy reduction and the Low Power Idle (LPI) techniques for networks to reduce the application power usage at runtime with low performance penalty [START_REF] Kansal | Fine-grained energy profiling for power-aware application design[END_REF]. Code instrumentation can be used to adapt the processor's frequency and voltage according to the application's needs, so to reduce the application's overall power consumption [START_REF] Kimura | Runtime energy adaptation with low-impact instrumented code in a power-scalable cluster system[END_REF][START_REF] Ge | Performance-constrained distributed dvs scheduling for scientific applications on power-aware clusters[END_REF][START_REF] Lim | Adaptive, transparent frequency and voltage scaling of communication phases in mpi programs[END_REF]. Instrumented-code, inserted into the application source code, aims at dividing the application into regions having the same characteristics (memory intensive, CPU intensive, network intensive or disk intensive). The appropriate "power-saving" scheme (often the CPU frequency and voltage or P-state) is then selected for each defined region accordingly.

Software approaches could be very effective if a system designer (cloud or grid provider) has sufficient knowledge of the applications running on its system. For example an action applied to a single node may impact the power consumption of the remaining nodes running the same application and therefore the overall system energy consumption. Therefore, an effective use of these power saving schemes on a multi-node system require a view of the system as a whole. The commonly used approach consists of instrumenting the source program to determine when to trigger an action on a computing node and how to handle that action's side effects on the remaining nodes running the same application. Instrumenting the program source code requires a specific expertise from the platform provider, which can not be assumed. Our work overcomes that necessity of instrumenting the application source code in order to apply power saving schemes.

A large body of work highlights the effectiveness of high performance computing (HPC) applications' power and energy consumption estimation via dedicated system registers known as hardware monitoring counters or performance counters. Hardware monitoring counters provide a means to understanding an application's resource utilization patterns. Power or energy estimation models based on hardware performance counters are often tailored for a specific type of applications: Indeed a power consumption model built for a workload having frequent memory accesses may not fit well a workload having infrequent memory accesses, and the same goes for frequent disk/network accesses workloads. Hence we believe that it is necessary to model phases of applications instead of applications, and therefore it is first needed to recognize and identify the successive phases of the system.

This paper studies how to represent the system into different phases considering their power consumption and hardware performance counters (including disk read/write and network bytes received/sent count) accessed throughout the phase. Observations led us to the following assumptions: (a) Hardware performance counters are accurate predictors of the system's energy consumption, (b) Any change in the set of performance counters relevant to power consumption prediction over a given duration reflects a change in the system's computational state over that duration. Based on these assumptions, we propose an approach to model the whole system's runtime (from a single node system to a cluster system) as a sequence of phases where each phase exhibits a computational behavior. This modeling paves the way to providing fine-grained control of HPC application power consumption without a priori knowledge of the application.

The major contributions of this paper are the following:

-We propose a DNA-like system model in order to better control large scale systems energy consumption. We focus on dividing applications into different phases. Its effectiveness is proven experimentally. -We develop a cross platform energy consumption prediction model as a usecase of our system modeling approach.

This paper is organized as follows. Background and related work are presented in Section 2. We propose a representation model denoted as "DNA-like" representation of a system in Section 3. Based on this model, we propose an application mapping to the system representation and present some experimental results in Section 4. Section 5 concludes and introduces future works.

Many applications have recurring phases during execution. Many works investigate methods to use these phases for architectural and system adaptations. Weissel et al. propose to adapt processor execution by monitoring memory boundedness of applications [START_REF] Weissel | Process cruise control-event-driven clock scaling for dynamic power management[END_REF] . Dhodapkar et al. investigate dynamic hardware reconfiguration [START_REF] Dhodapkar | Managing multi-configurable hardware via dynamic working set analysis[END_REF]. Murali Annavaram and al. [START_REF] Annavaram | Mitigating amdahl's law through epi throttling[END_REF] also point out the use of sequential and parallel phases in parallel applications for efficient distribution of threads on an asymmetric multiprocessor. These works open the door to any kind of system's optimization based on phases recognition including controlling and limiting the power consumption of large-scale systems.

A common approach to minimize the power consumption of large-scale systems is to identify phase-based applications [START_REF] Kimura | Runtime energy adaptation with low-impact instrumented code in a power-scalable cluster system[END_REF]. The core idea is to schedule the processors to a higher frequency for CPU (Central Processing Unit) intensive phases, and to a lower frequency for non-CPU bound phases and workload [START_REF] Kimura | Runtime energy adaptation with low-impact instrumented code in a power-scalable cluster system[END_REF][START_REF] Curtis-Maury | Online power-performance adaptation of multithreaded programs using hardware eventbased prediction[END_REF]. Focusing on highly iterative applications which allow them to predict the future behavior of an application based on its past, Freeh et al. identify nodes having been assigned small computations to reduce their frequency [START_REF] Freeh | Just-in-time dynamic voltage scaling: Exploiting inter-node slack to save energy in mpi programs[END_REF]. These approaches are quite effective, however to our knowledge the source code of the application needs to be analyzed carefully to determine the different phases thus the CPU frequency at which each phase should run. Therefore, detecting phases is not only application specific but also requires extensive knowledge given the complexity of today's high performance applications. In comparison, our work does not attempt to estimate or reduce the system's power or energy consumption, instead, we investigate the possibility of detecting and characterizing application's execution phases at runtime for using insights gathered form hardware monitoring events and the system's energy consumption. The particularity of our approach is that it almost does not require any knowledge of the application under consideration.

DNA-like System Modeling

As mentioned earlier in this paper, a fine-grained power control of a whole cluster system requires a view of that system as a whole. In this section, we introduce a very simple model for describing a system's runtime behavior. We assume a system or a cluster system is a set of computing nodes with their applicative states (the system state during application execution); network devices such as routers and switches are not taken into account. The strength of our model is that it provides insights about the system's computational state as well as its power/energy consumption. Our model represents a cluster system runtime as a state graph whose initial and final states are the system's idle state (or configuration). A transition from one state S1 to S2 is weighted by the conditional probability that the system goes to S2 given that it is in S1.

We represent each system state including the idle state as a column vector of size n;w h e r en is the number of computing nodes in the system, and whose entries describes the system behavior over a fixed period of time. An entry of a system's state vector is defined considering what we call the "DNA-like" structure of the system, which is a succession of computational behaviors exhibited by the system over time. We call such a computational behavior a "letter" and the set of possible computational behaviors the "system description alphabet".

A letter itself is modeled as a column vector of hardware monitoring counters including disk read/write and network bytes (respectively packets) sent/received counts to capture non memory-or CPU-intensive behavior. Details on their construction are provided later in this paper. On some platforms, it may not be possible to measure the system power/energy consumption using the power distribution unit. To avoid this limitation, one of our design constraint is that a letter in addition to describing the computational system, should provide a way to estimate the system power/energy consumption over a time period.

Letter Model

Observation Efforts to model HPC applications power/energy consumption via performance monitoring counters have shown that performance monitoring counters relevant to power consumption estimation depend on the application itself. Thus performance counters relevant to power consumption estimation of a CPU intensive application may differ from those relevant to power consumption estimation of a memory intensive application.

As performance monitoring counters relevant to power consumption estimation depends on the computational state of the application, we state that any change in the set of performance counters relevant to power consumption estimation of an application over a time period T reflects a change in the application computational state over the same time period T .

Based on the above statement, we propose Algorithm 1 which takes as input an application footprint as a matrix and outputs the partition of the application into computational phases according to changes in the set of performance monitoring counters relevant to the power consumption estimation. Each row r of the input matrix contains values of hardware monitoring counters recorded over the sample interval timestamped r.

Relevant hardware Counters Definition The steps to find out which performance counters are relevant to power estimation are the following: (1) the most straightforward approach is to only take into account the first k performance counters highly correlated to power consumption, (2) the second approach relies on the power model described by Power ∼ P n i=1 α i * C i or a similar one (linear or not). In this equation α i and C i are model coefficients and hardware counters respectively. We conduct a multi-variable linear regression to obtain coefficients α i and retain counters C j exhibiting a 5% level of statistical significance to power consumption estimation given the power model.

Figures 1, where similar patterns refer to the same computational behavior, shows the output of our algorithm considering a constant number (4 in this case) Data: A: a matrix representing the application footprint, P =Ø Result: P :as e tc o n t a i n i n gs u b s e t sRi representing application phases Initialization: consider a sample interval Sn of upper bound n, n represents the first n rows of the application matrix A such that n>p+ 1, where p is the number of performance counters (including disk read/write and network packets (bytes) sent/received count). Algorithm 1: Algorithm to detect application phases of hardware counters. The system under consideration comprises two computing nodes running the NAS LU (class C problem on sixteen processes) benchmark [START_REF] Bailey | The nas parallel benchmarks[END_REF]. The second approach showed bad results as the power estimation error using the power model is sometimes too high. We can also noticed that four phases was detected on the first computing node (on the x-axis from 0 to 60, form 60 to 90, from 90 to 120, and finally from 120 to 160) and five on the second computing node.

P = P [ R0 while row(A) > n do
Letter Encoding and Representation In this section, we present a formal representation of letters of our system description model. To simplify we consider that a letter has four hardware monitoring counters i.e., the number of hardware monitoring counters representing a letter is fixed to 4. We also limit the overall number of hardware monitoring counters to sixteen. Although it is possible to monitor more than 64 hardware counters on a single node of our cluster, only a few of them are relevant to the system's power consumption estimation [START_REF] Costa | Methodology of measurement for energy consumption of applications[END_REF][START_REF] Lively | Power-aware predictive models of hybrid (MPI/OpenMP) scientific applications on multicore systems[END_REF].

Let's assign each hardware monitoring counter (including disk reads/writes and network (packets) sent/received bytes) to a four-bit aggregation or half byte. Our quadruplet is therefore of the form (X 1 ,X 2 ,X 3 ,X 4 ); where each X i values is a half byte. Now, deleting commas in between the X i gives a sixteen-bit aggregation which converted into decimal is an unsigned integer. The unsigned integer obtained from the above transformation is then the final representation of a letter.

System Model Use-cases

This section proposes two simple use-cases of our system modeling approach. We first show how the system's energy profile can be derived from its model. Next, we present an approach to predict the energy consumption of an application using our system model and partial execution.

Energy Profiling The concept of energy profile is very well defined in fields such as physical chemistry, but in computer science it is not easy to find an unanimous definition of this concept. The following definitions can be considered: For an application, the energy profile (respectively power profile) can be roughly defined as its energy (respectively power) footprint during its execution. This definition assumes that the application under consideration is the only application running on the system. A more complete definition presents an application's energy profile as its part of the energy footprint variation of the overall system during its execution.

In studies such as [START_REF] Costa | Methodology of measurement for energy consumption of applications[END_REF][START_REF] Kadayif | vec: virtual energy counters[END_REF][START_REF] Contreras | Power prediction for intel xscale processors using performance monitoring unit events[END_REF][START_REF] Singh | Real time power estimation and thread scheduling via performance counters[END_REF][START_REF] Bautista | A simple poweraware scheduling for multicore systems when running real-time applications[END_REF][START_REF] Joseph | Run-time power estimation in high performance microprocessors[END_REF][START_REF] Wu | A systematic method for functional unit power estimation in microprocessors[END_REF] efforts have been devoted to model power usage of system components (CPU, memory, disk, network) via hardware performance counters or hardware monitoring events. From those studies, the energy profile of an application can also be defined as a set of measurements (hardware monitoring events collected per-process or system-wide) over a time interval T such that there exists a combination of them estimating the power/energy used by the application or the whole system over T. The last definition describes the energy consumed by the application or the whole system via a set of hardware monitoring counters. This is particularly interesting as hardware monitoring counters in addition to providing insight about the system's (application's) computational state give way to compute its power consumption.

According to the hardware events-oriented definition of the energy profile, our system model implicitly defines its energy profile. For example, let's consider the energy profile in Figure 1 (a), which can be written as a sequence of the form L i ... X i ... L k denoted as its DNA-like structure; where each system phase is replaced by a letter L i or XXX which refers to any system configuration or state we do not have enough information about (XXX may typically represent an idle state of the system). It is obvious that the system's energy profile is easy to obtain considering the application, for each known letter is associated to a specific power consumption.

Cross Platform Energy Consumption Prediction

This work is probably the very first attempt to predict energy consumption of an application on a given platform. The design of an energy prediction model is mainly motivated by the idea that users often have more than one candidate platforms for running their jobs, therefore choosing the less energy consuming platform can be beneficial to both users and platform providers.

Key concepts of our prediction model include DNA-like structure of the application, and relative energy. To simplify, we assume that the application under consideration is the only application running on the system, so the system's DNA-like structure is that of the application.

The model implicitly uses two sets of data, one from a reference platform provided by the DNA-like structure of the application, and one from a target platform which is the platform on which we want to estimate the overall energy consumption of the application. The aforementioned reference platform is the platform on which the pattern (DNA-like structure) matching with the application currently running was found.

As mentioned earlier, an application's run matches with a DNA-like structure if a significant percentage of the DNA-like structure matches with the already executed part of the application. Let E tar be the energy consumed by the already executed part of the application and E ref the energy that the matched part of the DNA-like structure had consumed on the reference platform. Denoted as E rel , the relative energy consumption between the two platforms is given by the following:

E rel = Etar E ref
With the above relative energy, the estimated energy consumption of the application is given by:

E est = R X% 0 P (t) i,tar dt + E rel * R end X% P 0 (t) j,ref dt
Where E est is the estimated energy consumption on the target platform; E rel the relative energy consumption between the target platform and the reference platform. In the above equation, R X% 0 P (t) i,tar dt represents the energy consumed by the application before a match is found with a pattern from the profile database. Either measured or estimated, P (t) i,tar is the instantaneous power usage of the application. P 0 (t) j,ref is the instantaneous power usage of the application on the reference platform and can be obtained from its DNA-like structure.

We define the estimation accuracy as the ratio between the estimated and measured energy on the target platform.

Experimental Results: Model Development and Validation

We design a cluster composed of 2 nodes with 2 Intel Quad-core Xeon CPUs each (16 cores in total), 12 GB of RAM. The nodes are connected by a Gigabit Ethernet switch. The Linux kernel 3.1.1 is installed on each node where perf event is used to read the hardware monitoring counters. MPICH is used as MPI library. MG, LU, IS, CG, EP, SP, and BT from NPB-3.3 are used for the experiments. MG demonstrates the capabilities of a very simple multi-grid solver, MG nodes communicate with their neighbors, and with other "distant" nodes. IS calculates the large-scale integer sorting. The CG kernel communication graph involves lots of neighbor communication. EP is embarrassingly parallel code that implements the random-number generator. Each application has several types of computations, memory access, and communication phases. Class C of these benchmarks are used (they are compiled using the default compiler's options). Each node's power usage is monitored with one sample per second using a power distribution unit.

Idle System State

We conduct experiments to observe the degree to which diverse hardware events affect the system's idle power consumption. Results show that they are almost never the same from a time interval T to another and that the system's idle power cannot be correlated with hardware events. Hence, to characterize the system's idle state, we monitor it again under different workload characteristics. The number of cache misses are chosen as the main system characteristic. As shown in Figure 2, the number of cache misses normalized to the elapsed cycles count (yielding the event rate) clearly discriminates among all workloads (each scatter of points represents one NAS banchmark). Based on this observation, we define a threshold β under which the system is said to be idle. We assign the letter XXX to the system's idle state to reflect the fact that we are unable to estimate its power usage via hardware performance counters.

Computational States

Firstly, we execute each of the above listed benchmarks 30 times and record the number of occurrences of each performance counter in Table 1. These performance counters are recorded every second along with the power consumption of each node of our cluster. Next, we run Algorithm 1 for defining regions for each node in order to create the system description alphabet. Once the alphabet of each node computed, we use the run history to create a transition matrix for each node. The transition matrix typically gives the probability to move from one letter to another.

As evaluation, we first investigate how close to reality is our approach for partitioning an application into different computational behaviors (or simply phases). For this purpose, we run successively two applications opposite from their computational point (i.e. IS and EP). IS is communication intensive whereas EP is mainly computing. Figure 3 shows the effectiveness of our approach. The couple of integers appearing in each region of the figure gives for each region the corresponding letter coded as an unsigned integer and its duration. For example, (17692 21) means the hardware events highlighted in bold in Table 1 are relevant to power consumption estimation over 21 seconds for the second computing node. We observe from the experiments that two phases were detected and identified with different letters for the two nodes nodes, and that their energy consumptions are different. Use Case Evaluation: Energy Profile The goal of our approach is to use the energy profile to predict the energy consumption and optimize the resources used. So, if we are able to predict the next system configuration, it will no longer be necessary to instrument the application source code prior to applying power saving schemes. For example if the predictor tells that the next state is a communication phase with an acceptable error, then power-saving schemes such as DVFS could be triggered. To observe to what degree our system model fits that expectation, we follow this generic methodology:

-Run the application and create its alphabet using Algorithm 1. We assume that all letters have the same duration of fifteen seconds, i.e., each letter covers fifteen seconds of the application's lifetime. -Take the first two letters of the same application and attempt to determine the rest of the sequence using the system transition matrix.

We discuss the results for LU because it runs a long time. The DNA-like structure (or description sequence) for one node running LU benchmark is provided in Figure 4, where durations are omitted (all 15s). We apply our predictor to the second letter of the LU sequence (293,15) to determine its energy profile or the rest of the sequence (recall that an application's energy profile is derived from its DNA-like structure or description sequence). The predictor simply looks at the transition matrix and chooses the next state with the highest probability. Using this approach, we are only able to predict a few parts of the entire application -less than 5 letters in this case. This can be attributed to the simplicity of the predictor. We are currently investigating more complex approaches to enhance our prediction mechanism. Evaluation for Energy Consumption Prediction We evaluate our model for energy consumption prediction considering a very stable application. For simplicity, we only predict the energy consumption of one node. The application iteratively does two things: It first computes the inverse of a 10x10 square matrix and then it copies a large file from a remote host. We choose such an application to ensure that its behavior is stable enough over time. The advantage of having a stable application resides in the fact that we can successfully predict the entire execution of the application. We consider two scenarios. For the first scenario, the target and reference platforms are the same node but running at respectively 1.6GHz and 2.13GHz. For the second scenario, the reference platform is a Dell Power Edge server and the target platform a Sun Fire V20z. For partial execution, 20% of the application is executed. Results are summarized in Table 2. We compute for both scenarios the expected energy consumption based on the equations given in Section 3.2. We can see from those results that the accuracy is very good. Notice that the accuracy is higher because it is computed considering the average energy consumption instead of the peak energy consumption. However it must be noted that the considered application is very simple and stable. 5 Conclusions and Future Work

In this paper we propose to optimize large-scale systems energy consumption by triggering specific actions to reduce energy consumption depending on the behavior of the application being executed. We introduce a system modeling approach and some use cases. as a state graph and present some relevant use cases of the model. Our approach for dividing applications into phases is fast and does not require extensive knowledge of applications running on the system. We show through experiments that our model can effectively be used for predicting the system's energy profile. We also show that energy consumption estimation using our system model and partial execution can successfully predict the entire system power usage. Future work will combine our model with power saving schemes. We will also improve the system model using more sophisticated mechanisms in order to guarantee accurate energy profile prediction. We also plan on using our energy consumption prediction model for predicting the energy consumption of real workloads on multi-nodes systems

Fig. 1 .

 1 Fig.1. Example of phase detection on a two-nodes cluster system running the NAS LU benchmark (from top to bottom, first and second computing node).

Fig. 2 .

 2 Fig. 2. NAS benchmarks characterized by their cache miss rate.

Fig. 3 .

 3 Fig. 3. Dividing NAS benchmarks IS and EP ran successively into two different computational behaviors using their power usage and hardware counters (left: First node; right: Second node).

Fig. 4 .

 4 Fig. 4. DNA-like representation with fixed letter duration for a node running the LU benchmark.

  Shift the upper bound of S to n = upper bound(S)+n Compute the set Ri of relevant counters from Sn if Ri-1 6 = Ri then Find j 2 [upper bound(S) -n, upper bound(S)] such that Rj == Ri-1, where Rj is the set of relevant counters from Sj;

P = P [ Rj Delete the first j rows of A Go to 1 (Initialization) end end

Table 1 .

 1 List of hardware monitoring counters

	PERF COUNT HW CPU CYCLES	PERF COUNT HW INSTRUCTIONS
	PERF COUNT HW CACHE REFERENCES	PERF COUNT HW STALLED CYCLES FRONTEND
	PERF COUNT HW CACHE MISSES	PERF COUNT HW BUS CYCLES
	PERF COUNT HW BRANCH INSTRUCTIONS PERF COUNT HW BRANCH MISSES
	netSENTbyte	netSENTpkt
	netRECVbyte	netRECVpkt
	Wr i t e I / O	Read I/O

Table 2 .

 2 Energy consumption prediction results summary

	Scenario Estimated Energy (in Joules) Accuracy Peak energy consumption
	1	797143.5	1.01 811932
	2	2068515.6	1.02 2088515.6

Acknowledgments This work is supported by the INRIA large scale initiative Hemera focused on "developing large scale parallel and distributed experiments".