Toàn Nguyên
email: toan.nguyen@inria.fr

Resilience Issues for Application Workflows on Clouds

Keywords: workflows-fault-tolerance, resilience, simulation, cloud computing, high-performance computing. I

Two areas are currently the focus of active research, namely cloud computing and high-performance computing. Their expected impact on business and scientific computing is such that most application areas are eagerly uptaking or waiting for the associated infrastructures. However, open issues still remain. Resilience and loadbalancing are examples of such areas where innovative solutions are required to face new or increasing challenges, e.g., fault-tolerance. This paper presents existing concepts and open issues related to the design, implementation and deployment of a fault-tolerant application framework on cloud computing platforms. Experiments are sketched including the support for application resilience, i.e., faulttolerance and exception-handling. They also support the transparent execution of distributed codes on remote highperformance clusters.

INTRODUCTION

The future of computing systems in the next decade is sometimes advertised as a combination of virtual labs running large-scale application workflows on clouds that operate exascale computers [START_REF] Kovatch | The Malthusian Catastrophe is Upon Us! Are the Largest HPC Machines Ever Up?[END_REF] [START_REF] Riesen | Simulating Application Resilience at Exascale[END_REF]. Although this vision is attractive, it currently carries some inherent weaknesses. Among them are the complexity of the applications, e.g., multi-scale and multi-disciplines, the technical layers barrier, e.g., the network infrastructures, the multicore HPC clusters and finally the overwhelming technicalities that rely on experts that are not the final users. The consequences are that important challenges still lay ahead of us, among which are error management, fault-tolerance and application resilience.

Error recovery has long been a difficult challenge for both the computer science engineers and the application users. Approaches dealing with errors, failures and faults have mostly been designed by system engineers [START_REF] Ludäscher | Scientific Workflows: Business as usual ?[END_REF]. The characterization of faults and failures is indeed made inside software systems [START_REF]The Apache Foundation[END_REF]. The emergence and widespread use of high-performance multi-core systems is also increasing the concerns for error-prone infrastructures where the mean-time between failures is decreasing [START_REF] Capello | Toward Exascale Resilience[END_REF].

Operating and communication systems have long addressed the failure detection and recovery problems with sophisticated restart and fail-safe protocols, from both the theoretical and implementation perspectives [START_REF] Beckman | Facts and Speculations on Exascale: Revolution or Evolution?[END_REF] [START_REF] Bridges | Cooperative Application/OS DRAM Fault Recovery[END_REF].

However, the advent of high-performance computing systems and distributed computing environments provide opportunities for new challenging applications to be deployed and run in order to solve unprecedented complex problems, e.g., full 3D aircraft flight dynamics simulation [START_REF] Abbas | High Computing Power: A radical Change in Aircraft Design Process[END_REF]. This stimulates the design of large-scale and longrunning multi-discipline and multi-scale applications. They are expected to be standard within the next decade.

This induces expectations from the designers and users of such applications, e.g., better application accuracy, better performance, high-level and user-friendly interfaces, and resilience capabilities.

Consequently, rising concerns appear questioning the characterization, tracing and recovery from errors in such complex applications [START_REF]Proc. 5th Workshop INRIA-Illinois Joint Laboratory on Petascale Computing[END_REF].

Indeed, the number and variety of components invoked during the execution of these applications are increasing:

• Operating system components (system libraries)

• Network components (virtual nodes, servers, backbones, protocols, messaging, duplication, etc.) • Middleware components (resource allocation, authentication, authorization, load-balancing, etc.) • Application components (software libraries for synchronization, results storage and migration, computation, user interfaces, etc.). This results in several layers of software where the early detection of errors and their effective recovery are crucial with respect to resource allocation, usage cost, performance, system survivability, application consistency and user satisfaction [START_REF] Ghanem | Grid-enabled workflows for industrial product design[END_REF] [8]. Therefore, the software stack includes several different logics that must be carefully taken into account, i.e., identified and coordinated, in case of errors [20][44].

This paper explores the design, implementation and use of cloud infrastructures from the application perspective. It proposes specific techniques to handle application errors and recovery. The cloud infrastructure includes heterogeneous hardware and software components. Further, the application codes must interact in a timely, secure and effective manner. Additionally, because the coupling of remote hardware and software components is prone to run-time errors, sophisticated mechanisms are necessary to handle unexpected failures at the infrastructure, system and application levels [START_REF] Sherp | Using UNICORE and WS-BPEL for Scientific Workflow execution in Grid Environments[END_REF] [START_REF] Joseph | A Strategic Agenda for European Leadership in Supercomputing: HPC 2020[END_REF]. Consequently, specific management software is required to handle unexpected application and system behaviors [START_REF] Wang | A highlevel distributed execution framework for scientific workflows[END_REF][11] [START_REF] Ramakrishna | VGrADS: Enabling e-Science workflows on grids and clouds with fault tolerance[END_REF][15] [START_REF] Moody | Modeling and evaluation of a Scalable Multi-level checkpointing System[END_REF].

The paper is focused on reactive approaches to occurring errors. It does not address error prevention and proactive approaches, e.g., preventive data and code migration and duplication [START_REF] Capello | Toward Exascale Resilience[END_REF]. Neither does it address prevention issues based on statistical evaluation and prediction of error occurrences and log analysis.

Indeed, the paper follows the position mentioned in [START_REF] Capello | Toward Exascale Resilience[END_REF]: "This limited comprehension of root causes makes fault effect avoidance (the capability to avoid the effects of faults) difficult. Without a good understanding of root causes, it seems illusory to design and validate fault prediction mechanisms. Without good fault prediction systems, research on proactive actions is almost useless. In addition, even if at some point, we are capable of predicting errors accurately, we still have to find: 1) acceptable solutions to handle false negatives, and 2) how to handle predicted software errors (process or virtual machine migration is not a response for software errors)".

This paper focuses on application resilience, i.e., survivability mechanisms to ensure the consistent termination of the applications, in the case of unexpected faulty behavior. Section II is an overview of related work. Section III is a description of open issues and gives an overview of running testcases. Section IV is a conclusion.

II. RELATED WORK

A. Definitions

Application resilience uses several notions that need to be detailed:

• Errors • Faults • Failures • Exceptions • Recovery • Fault-tolerance • Robustness • Resilience
The generic term error usually encompasses different types of abnormal situations and behaviors. These might originate in system, middleware and application unexpected discrepancies.

In systems such as Apache's ODE [START_REF]The Apache Foundation[END_REF], system failures and application faults address different types of errors.

A failure to resolve a DNS address is different from a process fault, e.g., a bad expression. Indeed, a system failure does not impact the correct logics of the application process at work, and should not be handled by it, but by the system error-handling software instead: "failures are non-terminal error conditions that do not affect the normal flow of the process" [START_REF]The Apache Foundation[END_REF].

However, an activity can be programmed to throw a fault following a system failure, and the user can choose in such a case to implement a specific application behavior, e.g., a number of activity retries or its termination.

Application and system software usually raise exceptions when faults and failures occur. The exception handling software then handles the faults and failures. This is the case for the YAWL workflow management system [START_REF] Adams | Open source software for workflow management: the case of YAWL[END_REF][47] [START_REF] Lachlan | Dimensions of coupling in middleware[END_REF], where specific exlets can be defined by the users [START_REF] Van Der Aalst | Modern Business Process Automation: YAWL and its support environment[END_REF]. They are components dedicated to the management of abnormal application or system behavior (Figure 1). The extensive use of these exlets allows the users to modify the behavior of the applications in realtime, without stopping the running processes. Further, the new behavior is stored as a component workflow which incrementally modifies the application specifications. The latter can therefore be modified dynamically to handle changes in the user requirements. Fault-tolerance is a generic term that has long been used to name the ability of systems and applications to handle errors. Transactional systems for example need to be fault-tolerant [START_REF] Zang | A Distributed Algorithm for Workflow Recovery[END_REF]. Critical business and scientific applications need to be fault-tolerant, i.e., to resume consistently in case of internal or external errors.

Therefore checkpoints need to be designed at specific intervals to backtrack the applications to consistent points in the application execution, and restart be enabled from there. They form the basis for recovery procedures.

Application robustness is the property of software that are able to survive consistently from data and code errors. This area is a major concern for complex numeric software that deal with data uncertainties. This is particularly the case for simulation applications [START_REF] Duvigneau | A three-level parallelization strategy for robust design in aerodynamics[END_REF]. This is also a primary concern for the applications faced to system and hardware errors. In the following, we include both (application external) fault-tolerance and (internal) robustness in the generic term resilience [START_REF] Nguyên | A Distributed Workflow Platform for Simulation[END_REF].

Therefore we do not follow here the definition given in [START_REF] Capello | Toward Exascale Resilience[END_REF]: "By definition a failure is the impact of an error itself caused by a fault."

But, we fully adhere to the following observation: "the response to a failure or an error depends on the context and the specific sensitivity to faults of the usage scenarios, applications and algorithms" [START_REF] Capello | Toward Exascale Resilience[END_REF].

B. Overview

Simulation is a prerequisite for product design and for scientific breakthrough in many application areas ranging from pharmacy, biology to climate modeling and aircraft design [START_REF] Joseph | A Strategic Agenda for European Leadership in Supercomputing: HPC 2020[END_REF]. They all require extensive simulation and testing. This requires often large-scale multidiscipline experiments, including the management of petabytes volumes of data and large multi-core supercomputers [START_REF] Crawl | A Provenance-Based Fault Tolerance Mechanism for Scientific Workflows[END_REF].

In such application environments, various teams usually collaborate on several projects or part of projects. Computerized tools are often shared and tightly or loosely coupled [START_REF] Plankensteiner | Fault-tolerant Behavior in State-of-the-Art Grid Workflow Management Systems[END_REF]. Some codes may be remotely located and non-movable. This is supported by distributed code and data management facilities [START_REF]OPALE project[END_REF]. And unfortunately, this is prone to a large variety of unexpected errors and breakdowns [START_REF] Nguyên | A Workflow Platform for Simulation on Grids[END_REF].

Data replication and redundant computations have been proposed to prevent from random hardware and communication failures [START_REF] Plankensteiner | A New Fault-Tolerant Heuristic for Scientific Workflows in Highly Distributed Environments based on Resubmission impact[END_REF], as well as failure prediction [START_REF] Lan | Adaptive Fault Management of Parallel Applications for High-Performance Computing[END_REF], sometimes applied to deadline-dependent scheduling [START_REF] Ramakrishna | VGrADS: Enabling e-Science workflows on grids and clouds with fault tolerance[END_REF].

System level fault-tolerance in specific programming environments is also proposed, e.g., CIFTS [START_REF] Gupta | CIFTS: a Coordinated Infrastructure for Fault-Tolerant Systems[END_REF]. Also, middleware usually support mechanisms to handle faulttolerance in distributed job execution, usually calling upon data replication and redundant code execution [START_REF] Wang | A highlevel distributed execution framework for scientific workflows[END_REF][15][22] [START_REF] Duvigneau | A three-level parallelization strategy for robust design in aerodynamics[END_REF].

Also, erratic application behavior needs to be supported [START_REF] Sindrilaru | Fault-Tolerance and Recovery in Grid Workflow Mangement Systems[END_REF]. This implies evolution of the application process in the event of such occurrences. Little has been done in this area [START_REF] Ostermann | Extending Grids with Cloud Resource Management for Scientific Computing[END_REF] [START_REF] Hwang | Grid Workflow: A Flexible Failure Handling Framework for the Grid[END_REF]. The primary concerns of the application designers and users have so far focused on efficiency and performance [START_REF]The Grid Workflow Forum[END_REF]. Therefore, application unexpected behavior is usually handled by re-designing and re-programming pieces of code and adjusting parameter values and bounds. This usually requires the simulations to be stopped and restarted.

The concerns focus therefore on application resilience, although intra-node fault-tolerance is also a major concern [START_REF] Beckman | Facts and Speculations on Exascale: Revolution or Evolution?[END_REF].

Studies have focused on reducing checkpoint sizes and frequency, as well writing overheads [START_REF] Kovatch | The Malthusian Catastrophe is Upon Us! Are the Largest HPC Machines Ever Up?[END_REF]. Examples are diskless checkpointing [START_REF]Proc. 5th Workshop INRIA-Illinois Joint Laboratory on Petascale Computing[END_REF], compressed checkpoints [START_REF] Capello | Toward Exascale Resilience[END_REF] and incremental checkpointing [START_REF] Riesen | Simulating Application Resilience at Exascale[END_REF].

An extensible approach for petascale and future exascale systems is proposed in [START_REF] Moody | Modeling and evaluation of a Scalable Multi-level checkpointing System[END_REF], based on a multilevel checkpointing scheme called Scalable Checkpoint/Restart (SCR) which proves to be effective. It provides an explicit checkpoint model to compute the optimal number of checkpoint levels and frequency of checkpoints at each level. The model and strategy are used to predict the checkpointing overhead and performance of the systems targeted. They are assessed by experiments on thousands of run hours on several production HPC clusters. This results in a thorough analysis of the impact of checkpoint intervals on overall system efficiency with respect to failure rate, compute intervals and file systems costs.

A dynamic approach is presented in the following sections. It support the evolution of the application behavior using the introduction of new exception handling rules at run-time by the users, based on occurring (and possibly unexpected) events and data values. The running workflows do not need to be suspended in this approach, as new rules can be added at run-time without stopping the executing workflows.

This allows on-the-fly management of unexpected events. This approach also allows a permanent evolution of the applications that supports their continuous adaptation to the occurrence of unforeseen situations [START_REF] Hwang | Grid Workflow: A Flexible Failure Handling Framework for the Grid[END_REF].

As new situations arise and data values appear, new rules can be added to the workflows that will permanently take them into account in the future. These evolutions are dynamically hooked onto the workflows without the need to stop the running applications. The overall application logic remains therefore unchanged. This guarantees a constant adaptation to new situations without the need to redesign the existing workflows. Further, because exception-handling codes are themselves defined by dedicated component workflows, the user interface remains unchanged [START_REF] Dongarra | The International Exascale Software Roadmap[END_REF].

III. OPEN ISSUES

A. Error management

Many open issues are still the subject of active research concerning application resilience. The paradigm ranges from code and data duplication and migration, to the monitoring of application behavior, and this includes also quick correctness checks on partial data values, the design of error-aware algorithms, as well as hybrid checkpointing-message logging features (Figure 2).

The baseline is:

• The early detection of errors,

• Root cause characterization,

• Characterization of transient vs. persistent errors,

• The tracing and provenance of faulty data,

• The identification of the impacted components and their associated corrupted results,

• The ranking of the errors (warnings, fatal, medium) and associated actions (ignore, restart, backtrack),

•

B. Error detection

The early characterization of errors is difficult because of the complex software stack involved in the execution of multi-discipline and multi-scale applications on clouds. The consequence is that errors might be detected long after the root cause that initiated them occurred. Also, the error observed might be a complex consequence of the root cause, possibly in a different software layer.

Similarly, the exact tracing and provenance data may be very hard to sort out, because the occurrence of the original fault may be hidden deep inside the software stack.

Without explicit data dependency information and realtime tracing of the components execution, the impacted components and associated results may be unknown. Hence, there is a need for explicit dependency information [START_REF] Zang | A Distributed Algorithm for Workflow Recovery[END_REF]. The ranking of errors is dependent on the application logic and semantics (e.g., default values usage). It is also dependent on the logics of each software layer composing the software stack. Some errors might be recoverable (Unresolved address, resource unavailable, etc.), some others not (Network partition, etc.). In each case, the actions to recover and resume differ: ignore, retry, reassign, suspend, abort.

In all cases, resilience requires the application to include four components:

• A monitoring component for (early) error detection,

• A (effective) decision system, for provenance and impact assessment, • A (low overhead) checkpointing mechanism, • An effective recovery mechanism. Further, some errors might be undetected and transient. Without explicit data dependency information and real-time tracing of the components execution, the impacted components and associated results may be unknown. Hence there is a need for explicit dependency information between the component executing instances and between the corresponding result data [START_REF] Zang | A Distributed Algorithm for Workflow Recovery[END_REF].

A sub-system dedicated to application resilience includes therefore several components in charge of specific tasks contributing to the management of errors and consistent resuming of the applications (Figure 2). First, it includes an intelligence engine in charge of the application monitoring and of the orchestration of the resilience components. This engine runs as a background process in charge of event listening during the execution of the applications. It is also in charge of triggering the periodic checkpointing mechanism, depending on the policy defined for the applications being monitored. It is also in charge of triggering the messagelogging component for safekeeping the messages exchanged between tasks during their execution. This component is however optional, depending on the algorithms implemented, e.g., checkpointing only or hybrid checkpointmessage logging approaches. Both run as background processes and should execute without user intervention. Should an error occur, an error detection component that is constantly listening to the events published by the application tasks and the operating system raises the appropriate exceptions to the monitoring component. The following components are then triggered in such error cases: an optional provenance component which is in charge of root cause characterization, whenever possible. An impact assessment component is then triggered to evaluate the consequences of the error on the application tasks and data, that may be impacted by the error. Next, a recovery component is triggered in charge of restoring the impacted tasks and the associated data, in order to re-synchronize the tasks and data, and restore the application to a previous consistent state. A resuming component is finally triggered to deploy and rerun the appropriate tasks and data on the computing resources, in order to resume the application execution. In contrast with approaches designed for global faulttolerance systems, e.g., CIFTS [START_REF] Gupta | CIFTS: a Coordinated Infrastructure for Fault-Tolerant Systems[END_REF], this functional architecture describes a sub-system dedicated to application resilience. It can be immersed in, or contribute to, a more global fault-tolerance system that includes also the management of system and communication errors.

C. Experiments

A distributed platform featuring the resilience capabilities described above is developed [START_REF] Nguyên | A Workflow Platform for Simulation on Grids[END_REF], based on the YAWL workflow management system [START_REF] Adams | Open source software for workflow management: the case of YAWL[END_REF] [START_REF] Lachlan | Dimensions of coupling in middleware[END_REF]. Experiments are connecting the platform to the FAMOSA optimization suite [START_REF] Duvigneau | A three-level parallelization strategy for robust design in aerodynamics[END_REF] developed at INRIA by project OPALE [START_REF]OPALE project[END_REF].

The experiments are deployed on the Grid5000 infrastructure [START_REF]Grid5000 project home[END_REF]. This involves five different locations throughout France (Figure 5), including two locations near Paris for CAD data and mesh generation. In addition, another location near Nantes involves CFD calculations, and another one in Sophia-Antipolis near Nice is dedicated to optimization. The last location in Grenoble is for application deployment, monitoring and result visualization (Figure 5).

The first experiments simulated this deployment scenario by duplicating the application with two identical parallel sequences running on Lyon and Grenoble clusters respectively, then on Sophia-Antipolis and Grenoble respectively.

This allowed for performance assessment of the various clusters implied on Lyon, Sophia-Antipolis and Grenoble.

Because Grid5000 infrastructure does not currently serve Nantes, a further experiment will invoke the clusters in Rennes instead, Lille instead of Paris2, and Orsay instead of Paris1.

An extension will invoke one more cluster in Lyon instead of one of the Sophia-Antipolis instances. A total of six remote HPC clusters will therefore be invoked (Figure 6). The reason for this is that most application codes are proprietary and are located at the various partners offices.

Data transfers between clusters use a 10 Gbps IP network infrastructure dedicated to Grid5000 (Figure 10).

All the locations involve HPC clusters and are invoked from a remote workflow running on a Linux workstation in Grenoble.

The various errors that are taken into account by the resilience algorithm include run-time errors in the solvers, inconsistent CAD and mesh generation files, and execution time-outs [START_REF] Nguyên | Dynamic Resilient Workflows for Collaborative Design[END_REF]. FAMOSA is currently tested for car rear mirrors optimization (Figure 7) and by ONERA (the French National Aerospace Research Office) for aerodynamics optimization.

FAMOSA is an acronym for "Fully Adaptive Multilevel Optimization Shape Algorithms" and includes C++ components for:

• CAD generation,

• Mesh generation,

• Domain partitioning,

• Parallel CFD solvers using MPI, and • Post-processors. The input is a design vector and the output is a set of simulation results. The components also include other software for mesh generation, e.g., Gmsh [START_REF]Gmsh[END_REF], partitioning, Sophia Grenoble e.g., Metis [START_REF] Metis | [END_REF] and solvers, e.g., Num3sis [28]. They are remotely invoked from the YAWL application workflow by shell scripts [START_REF] Nguyên | A Workflow Platform for Simulation on Grids[END_REF].

The FAMOSA components are triggered by remote shell scripts running for each one on the HPC cluster. The shell scripts are called by YAWL custom service invocations from the user workflow running on the workstation [START_REF] Nguyên | A Workflow Platform for Simulation on Grids[END_REF].

Other testcases implemented by academic and industry partners include the optimization of cylinder input pipes and valves for car engines (Figure 4 and8) and vehicle aerodynamics (Figure 9).

IV. CONCLUSION

The requirements for large-scale simulations make it necessary to deploy various software components on heterogeneous distributed computing infrastructures [START_REF] Crawl | A Provenance-Based Fault Tolerance Mechanism for Scientific Workflows[END_REF] [START_REF] Ostermann | Extending Grids with Cloud Resource Management for Scientific Computing[END_REF]. These environments are often remotely located among a number of project partners for administrative and collaborative purposes.

An overview of resilience is given with open issues. A workflow distributed platform and running testcases are briefly described. The underlying interface to the distributed components is a middleware providing resource allocation and job scheduling [START_REF]Grid5000 project home[END_REF]. Besides fault-tolerance provided by the middleware, which handles communication and hardware failures, the users can define and handle application errors at the workflow level. Application errors may result from unforeseen situations, data values and boundary conditions. In such cases, user intervention is required in order to modify parameter values and application behavior. Complex error characterization is then invoked to assess the impact on the executing tasks and the data involved. The approach presented uses dynamic rules and constraint enforcement techniques, combined with asymmetric checkpoints. It is based on the YAWL workflow management system.

Figure 1 .

 1 Figure 1. Error-handler.

Figure 2 .

 2 Figure 2. Architecture of a resilience sub-system.

  The identification of pending components, • The identification and purge of transient messages, • The secured termination of non-faulty components, • The secure storage of partial and consistent results, • The quick recovery of faulty and impacted components, • The re-synchronization of the components and their associated data, • The properly sequenced restart of the components. Each of these items needs appropriate implementation and algorithms in order to orchestrate the various actions required by the recovery of the faulty application components.

Figure 3 .

 3 Figure 3. The YAWL workflow and middleware interface.

Figure 4 .

 4 Figure 4. Cylinder optimized input pipes -courtesy Lab. Roberval, Université de Technologie de Compiègne (France).

Figure 5 .

 5 Figure 5. The workflow experiment schema.

Figure 6 .

 6 Figure 6. The final distributed workflow.

Figure 7 .

 7 Figure 7. Optimized rear mirror (courtesy CD-adapco).

ACKNOWLEDGMENTS

This work is supported by the European Commission FP7 Cooperation Program "Transport (incl. aeronautics)", for the GRAIN Coordination and Support Action ("Greener Aeronautics International Networking"), grant ACS0-GA-2010-266184. It is also supported by the French National Research Agency ANR (Agence Nationale de la Recherche) for the OMD2 project (Optimisation Multi-Discipline Distribuée), grant ANR-08-COSI-007, program COSINUS (Conception et Simulation).

The authors wish to thank Laboratoire Roberval (Université de Technologie de Compiègne, France), and also CD-adapco, for the testcase implementations and the images.


Toàn Nguyên
email: toan.nguyen@inria.fr

Jean-Antoine Désidéri
email: jean-antoine.desideri@inria.fr

Resilience for Collaborative Applications on Clouds Fault-Tolerance for distributed HPC applications

Keywords: High-Performance Computing, Cloud Computing, Distributed Computing, Scientific Applications, Workflows, Resilience

Because e-Science applications are data intensive and require long execution runs, it is important that they feature fault-tolerance mechanisms. Cloud and grid computing infrastructures often support system and network fault-tolerance. They repair and prevent communication and software errors. They allow also checkpointing of applications, duplication of jobs and data to prevent catastrophic hardware failures. However, only preliminary work has been done so far on application resilience, i.e., the ability to resume normal execution following application errors and abnormal executions. This paper is an overview of open issues and solutions for such errors detection and management. It also overviews the implementation of a workflow management system to design, deploy, execute, monitor, restart and resume distributed HPC applications on cloud infrastructures in cases of failures.

Introduction

Scientific applications are required today to design, simulate, optimize and manufacture artifacts, ranging from nanotubes to electronic devices and cruisers to airliners.

In order to design quickly these artifacts, long running simulations are executed. For example, multi-discipline scenarios are implemented, where hydraulic, thermic, fluid and electromagnetic simulation software collaborate for the design of nuclear plants.

Long running executions lasting days and even weeks on large HPC clusters suffer from reliability problems concerning the hardware and software infrastructures [START_REF] Bridges | Cooperative Application/OS DRAM Fault Recovery[END_REF] [START_REF] Capello | Toward Exascale Resilience[END_REF]. Fault-tolerance mechanisms are therefore required. They tend to be multilevel, each aspect corresponding to a different level with its specific sources of errors: network communications, distributed middleware, operating systems, collaborating application codes.

The efforts on application errors tend to be the focus of active research today. This is due in part to optimization concerns, and to another part for fault-tolerance concerns [START_REF]Proc. 5th Workshop INRIA-Illinois Joint Laboratory on Petascale Computing[END_REF].

Optimization concerns target the speed-up of CPU and data intensive demanding applications [START_REF] Simon | Future directions in High-Performance Computing 2009-2018[END_REF]. Parallelization techniques take advantage today of multi-core supercomputers. However the 100K+ multi-core HPC clusters today are error-prone and their mean-time between failures is in the order of minutes [START_REF] Kovatch | The Malthusian Catastrophe is Upon Us! Are the Largest HPC Machines Ever Up?[END_REF]. Therefore, effective and low-overhead fault-tolerance application algorithms and codes are necessary.

Further, applications misbehavior and errors have multiple origins, which are not necessarily programming errors. They might originate in unforeseen data configurations, especially in simulation applications, unexpected data values, unpredictable behaviors in case of multiple errors cumulating abnormalities, etc.

Important efforts are required to handle these complex abnormal application situations [START_REF] Dongarra | The International Exascale Software Roadmap[END_REF] [8][14].

This paper addresses the management of application errors and abnormal behavior. It defines terms (section 2), addresses open issues and solutions for error detection (Section 3) and error management (Section 4). It sketches also implementation issues using a workflow management system (Section 5). Section 6 is a conclusion.

A prototype system based on a distributed workflow platform for the design, deployment, execution and monitoring of HPC applications is briefly described. The platform features resilience capabilities to address the application runtime errors.

Definitions

Because many terms are used in the fault-tolerance area, we give in this section a definition of various terms used in the domain and pave the way for an ontology of the required concepts.

An interesting definition of errors, faults and failures is given in a system such as Apache's ODE [START_REF]The Apache Foundation[END_REF], system failures and application faults address different types of errors.

Errors

The generic term error is used to characterize abnormal behavior, originating from hardware, operating systems and applications that do not follow prescribed protocols and algorithms. Errors can be fatal, transient and warnings, depending on their criticity level. Because sophisticated hardware and software stacks are operating on all production systems, there is a need to classify the corresponding concepts (Figure 1).

2.2

Failures

A failure to resolve a DNS address is different from a process fault, e.g., a bad expression. Indeed, a system failure does not impact the correct logics of the application process at work, and should not be handled by it, but by the system error-handling software instead: "failures are non-terminal error conditions that do not affect the normal flow of the process" [START_REF]The Apache Foundation[END_REF].

Faults

However, an activity can be programmed to throw a fault following a system failure, and the user can choose in such a case to implement a specific application behavior, e.g., a number of activity retries or its termination.

Application and system software usually raise exceptions when faults and failures occur. The exception handling software then handles the faults and failures. This is the case for the YAWL workflow management system [19][20], where specific exlets can be defined by the users [START_REF] Lachlan | Dimensions of coupling in middleware[END_REF]. They are components dedicated to the management of abnormal application or system behavior (Figure 2). The extensive use of these exlets allows the users to modify the behavior of the applications in real-time, without stopping the running processes. Further, the new behavior is stored as a component workflow which incrementally modifies the application specifications. The latter can therefore be modified dynamically to handle changes in the user requirements.

Fault-tolerance

Fault-tolerance is a generic term that has long been used to name the ability of systems and applications to handle errors. Transactional systems for example need to be fault-tolerant [START_REF] Nguyên | A Workflow Platform for Simulation on Grids[END_REF]. Critical business and scientific applications need to be fault-tolerant, i.e., to resume consistently in case of internal or external errors.

2.5

Checkpoints

Therefore checkpoints need to be designed at specific intervals to backtrack the applications to consistent points in the application execution, and restart be enabled from there. They form the basis for recovery procedures.

In the following, we call checkpoint for a particular task the set including task definition, parameter specifications and data associated to the task, either input data or output data and the parameter values.

This checkpoint definition does not include the tasks execution states or contexts, e.g., internal loop counters, current array indices, etc. Therefore, we assume that checkpointed tasks are stored stateless. This means that interrupted tasks, whatever the reasons and errors, cannot be restarted from their exact execution state immediately prior to the errors.

Recovery

We assume therefore that the recovery procedures must restart the failed tasks from previously stored elements in the set of existing tasks checkpoints. A consequence is that failed tasks cannot be restarted on the fly, following for example a transient non fatal error. They must be restarted using previously stored checkpoints.

Resilience

Application resilience is the property of software that are able to survive consistently from data and code errors (Figure 2). This area is a major concern for complex numeric software that deal with data uncertainties. This is particularly the case for simulation applications [START_REF] Bachmann | Advances in Generalization and Decoupling of Software Parts in a Scientific Simulation Workflow System[END_REF]. This is also a primary concern for the applications faced to system and hardware errors. In the following, we include both (application external) fault-tolerance and (internal) robustness in the generic term resilience [START_REF] Nguyên | A Distributed Workflow Platform for Simulation[END_REF].

Therefore we do not follow here the definition given in [START_REF] Capello | Toward Exascale Resilience[END_REF]: "By definition a failure is the impact of an error itself caused by a fault."

But we fully adhere to the following observation: "the response to a failure or an error depends on the context and the specific sensitivity to faults of the usage scenarios, applications and algorithms" [START_REF] Capello | Toward Exascale Resilience[END_REF].

3

Error Detection

Error Characterization

We address in this paper application errors, e.g., out of bounds data values, undefined parameters, execution time-outs, result discrepancies and unexpected values. We do not address communication, hardware and operating systems errors. We suppose that they are handled by the appropriate fault-tolerance sub-systems, which might automatically correct some of them or take appropriate corrective action, e.g., re-routing lost messages. We also suppose that these errors can be signaled to the applicationlevel software by the appropriate raising of exceptions and posting of signals. Thus, the applications can take whatever actions are needed, e.g., re-executing tasks on other resources in case of network partition, out-of-memory execution, etc. This can be defined by the application designers and even by the application users at runtime.

The early characterization of errors is difficult because of the complex software stack involved in the execution of multi-discipline and multi-scale applications on clouds. The consequence is that errors might be detected long after the root cause that initiated them occurred. Also, the error observed might be a complex consequence of the root cause, possibly in a different software layer.

Similarly, the exact tracing and provenance data may be very hard to sort out, because the occurrence of the original fault may be hidden deep inside the software stack.

Without explicit data dependency information and real-time tracing of the components execution, the impacted components and associated results may be unknown. Hence there is a need for explicit dependency information [START_REF] Sindrilaru | Fault-Tolerance and Recovery in Grid Workflow Mangement Systems[END_REF].

Error ranking

The ranking of errors is dependent on the application logic and semantics (e.g., default values usage). It is also dependent on the logics of each software layer composing the software stack. Some errors might be recoverable (unresolved address, resource unavailable…), some others not (network partition…). In each case, the actions to recover and resume differ: ignore, retry, reassign, suspend, abort... In all cases, resilience requires the application to include four components:

• a monitoring component for (early) error detection,

• a (effective) decision system, for provenance and impact assessment,

• a (low overhead) checkpointing mechanism,

• an effective recovery mechanism.

Further, some errors might be undetected and transient. Without explicit data dependency information and real-time tracing of the components execution, the impacted components and associated results may be unknown. Hence there is a need for explicit dependency information between the component executing instances and between the corresponding result data [START_REF] Beckman | Facts and Speculations on Exascale: Revolution or Evolution? Keynote Lecture[END_REF].

Fig. 3. Resilience sub-system.

Resilience Sub-system

A sub-system dedicated to application resilience includes therefore several components in charge of specific tasks contributing to the management of errors and consistent resuming of the applications (Figure 3). First, it includes an intelligence engine in charge of the application monitoring and of the orchestration of the resilience components [START_REF] Gupta | CIFTS: a Coordinated Infrastructure for Fault-Tolerant Systems[END_REF]. This engine runs as a background process in charge of event listening during the execution of the applications. It is also in charge of triggering the periodic checkpointing mechanism, depending on the policy defined for the applications being monitored [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF]. It is also in charge of triggering the message-logging component for safekeeping the messages exchanged between tasks during their execution. This component is however optional, depending on the algorithms implemented, e.g., checkpointing only or hybrid checkpoint-message logging approaches. Both run as background processes and should execute without user intervention. Should an error occur, an error detection component that is constantly listening to the events published by the application tasks and the operating system raises the appropriate exceptions to the monitoring component. The following components are then triggered in such error cases: an optional provenance component which is in charge of root cause characterization, whenever possible. An impact assessment component is then triggered to evaluate the consequences of the error on the application tasks and data, that may be impacted by the error. Next, a recovery component is triggered in charge of restoring the impacted tasks and the associated data, in order to re-synchronize the tasks and data, and restore the application to a previous consistent state. A resuming component is finally triggered to deploy and rerun the appropriate tasks and data on the computing resources, in order to resume the application execution. In contrast with approaches designed for global fault-tolerance systems, e.g., CIFTS [START_REF] Bridges | Cooperative Application/OS DRAM Fault Recovery[END_REF], this functional architecture describes a sub-system dedicated to application resilience. It can be immersed in, or contribute to, a more global fault-tolerance system that includes also the management of system and communication errors.

Error Management

Many open issues are still the subject of active research concerning application resilience. The paradigm ranges from code and data duplication and migration, to the monitoring of application behavior, and this includes also quick correctness checks on partial data values, the design of error-aware algorithms, as well as hybrid checkpointing-message logging features (Figure 3). We focus here only on application errors. We do not address hardware, systems and communication errors. We suppose that these errors are fully treated by the appropriate system components [15] [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF]. We further suppose that they can be signaled to the applications by some exception events. This allows handling the consequences of the errors, e.g., communication failures, by the appropriate application resilience sub-system (Section 3.3).

The baseline is (Figure 4):

Detection

Error Detection. Hardware and system fault-tolerance mechanisms can intercept errors [START_REF] Beckman | Facts and Speculations on Exascale: Revolution or Evolution? Keynote Lecture[END_REF]. Applications errors however must be explicitly taken into account in the code. This impacts severely the programming efforts and needs important design and re-programming efforts for existing codes [START_REF] Kovatch | The Malthusian Catastrophe is Upon Us! Are the Largest HPC Machines Ever Up?[END_REF].

Error Characterization. Similarly, error characterization is heavily dependent on the application logics [START_REF] Riesen | Simulating Application Resilience at Exascale[END_REF]. It allows for error ranking, ranging from warnings to fatal. This is necessary to fine tune the fault-tolerance and resilience capabilities to the application and user requirements.

Root Cause Detection.

Root cause characterization and provenance information is the most difficult part in complex applications and systems. Most of the time, even sophisticated tracing mechanisms will fail to provide an accurate characterization of the multiple root causes that provoke errors and abnormal application behavior [START_REF] Capello | Toward Exascale Resilience[END_REF].

Impact Assessment. The next important step is the assessment of the error impact. This includes the impact on the subsequent tasks, on the data, and the evaluation of error propagations. Further, a domino effect is that the errors can impact the messages exchanged and in transit between tasks as well as the advent of the pending tasks. This is detailed in the following sections (4.2, 4.3).

Impacted Tasks and Data

Impacted Tasks. The application definition provides a detailed dependency relationship between tasks and data. It should therefore be straitghtforward to characterize the impacted tasks and data. However, the latency between error occurrence and their actual detection makes it difficult to precisely point out the exact time and location when an error occurred, particularly in distributed systems. Therefore, impacted tasks and data can bearly be defined without an undefined uncertainty. This paves the way for drastic backtracking policies and restarts. However, optimized checkpointing schemes, e.g., asymmetric [START_REF] Nguyên | A Distributed Workflow Platform for Simulation[END_REF], multi-level [START_REF] Moody | Design, Modeling and evaluation of a Scalable Multi-level checkpointing System[END_REF] and encoded checkpoints [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF], alleviate somehow crude backtracking and checkpointing approaches by reducing their overhead, in both CPU and storage terms.

Corrupted Data. Similarly, corrupted data can originate from application errors and from error propagation (Figure 6):

Application errors. Computation errors on correct data will produce erroneous results, e.g., specification, algorithmic, programming erros. They can be spotted and corrected with unpredictable delays. Performance and overhead issues are Performance and overhead issues are not necessarily fundamental here because CPU and data demanding tasks might have to be backtracked and re-executed, incurring potentially very long delays.

Error propagation. Correct computations performed on previously polluted data may generate random errors on data processed subsequently. Errors cannot in this case be pointed out immediately, if at all. Restarting the application componenents from ancestor tasks might be a necessary option here. The exact and most accurate restart location may in some cases be difficult to characterize. Policy requirements and implementations are in this case the last resort.

Impact

Transient Messages. Transient messages are potentially emitted before a component failure. Identifying such data might be very difficult in distributed computing and collaborative codes. Indeed, failed tasks might have sent unknown numbers of mes-sages and data to a potentially unknown number of descendant tasks, depending on the point of failure. Time-outs might here be necessary to consider transient messages to reach their destinations. Purging all these messages is necessary to backtrack to a previous consistent checkpoint.

Pending Tasks. Pending tasks are in contrast easily characterized since they are waiting for incoming data or events raised by ancestor tasks. Pause and resuming of such tasks is an option, without systematically calling for their cold restart from a previous checkpoint. Opportunistic checkpoints might here be interesting to store already produced data and application state. This is related to asymmetric checkpoints [START_REF] Nguyên | A Distributed Workflow Platform for Simulation[END_REF], where the users define points of interest in the application runs where checkpoints and snapshots must be stored in order to prevent potential catastrophic failures later. So, CPU, storage and communication demanding tasks will in such cases be saved without the need to restart them later in case of application errors. Fig. 6. Error impact.

Recovery

Termination of Non-faulty Tasks. As mentionned above, recovery of non-faulty tasks is straightforward if they are not directly linked to faulty tasks, or if they are explicitly waiting for incoming data or events. If they are directly linked to failed tasks, i.e., processing data produced by failed tasks, restarting them with the failed tasks may be necessary. Indeed, without a sophisticated control of the data exchanged between tasks, it may be impossible to characterize the subsets of data already processed correctly by subsequent tasks. This is also the case when using data pipelining between tasks. In this case, restarting the tasks from the beginning is necessary. Further, resuming the subsequent tasks also requires the ancestor failed tasks to restart at their adequate execution locations when failed. This is most of the time impossible in current systems. It requires repetitive incremental and partial checkpoints of state dta and produced results, which can have an important overhead (Figure 7).

Secured Storage of Non-faulty Data. The secured storage of non-faulty data is essential for the optimization of the recovery process. Although, if it does not succeed, backtracking to a preceding checkpoint in the execution run is an option.

Restart Selection. There might be several options available for a single coordinated restart or local partial restarts (Figure 8). Depending on the situation, ranging from warnings to erros and fatal ones, the distributed configuration of the applications might render a global coordinated restart unrealistic. Several partial local restarts might be preferable, and in all cases, less expensive in terms of CPU and resource consumptions (Section "Coordinated Restart", below). Checkpoint Selection. An adequate checkpoint selection mechanism must be devised, which supports local restart in parallel and/or partial restarts from distributed and coordinated checkpoints. Here again, the versatility of the checkpointing mechanism, i.e., the support for multi-level checkpoints, is of first importance for reducing the restart overhead (Figure 9). But the cost is of course, the checkpointing overhead, both in terms of CPU and storage capacity, incurred. Encoding mechanisms, "shadowed" and "cloned" virtual disk images have been proposed to answer these concerns [START_REF] Nicolae | BlobCR: Efficient Checkpoint-Retart for HPC Applications on IaaS Clouds using Virtual Disk Image Snapshots[END_REF].

Coordinated Restart. Coordinated local restarts is a middle term option, between global cold restarts and multiple local restarts. As mentioned previously (Section 4.3), a global coordinated cold restart is unrealistic in distributed systems because it requires stopping all tasks and restarting the whole application, which might require large computing resources and days of CPU time. Coordination is fundamental here and related to distributed computations. It follows that coordinated restarts must be implemented by a specific mechanism that selects timestamped data and checkpoints.Italso requires the careful selection of those checkpoints strictly needed for the restart. The latter will execute local restarts with the appropriate checkpoints selected.

Implementation

Overview

Several proposals have emerged recently dedicated to resilience and fault management in HPC systems [START_REF] Riesen | Simulating Application Resilience at Exascale[END_REF][15] [START_REF]Proc. 5th Workshop INRIA-Illinois Joint Laboratory on Petascale Computing[END_REF].

The main components of such sub-systems are dedicated to the management of error, ranging from early error detections to error assessment, impact characterization, healing procedures concerning infected codes and data, choice of appropriate steps backwards and effective low overhead restart procedures.

General approaches which encompass all these aspects are proposed for Linux systems, e.g., CIFTS [START_REF] Gupta | CIFTS: a Coordinated Infrastructure for Fault-Tolerant Systems[END_REF]. More dedicated proposals focus on multi-level checkpointing and restart procedures to cope with memory hierarchy (RAM, SSD, HDD), hybrid CPU-GPU hardware, multi-core hardware topology and data encoding to optimize the overhead of checkpointing strategies, e.g., FTI [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF]. The goal is to design and implement low overhead, high frequency and compact checkpointing schemes.

Also, new approaches take benefit of virtualization technologies to optimize checkpointing mechanisms using virtual disks images on cloud computing infrastructures [START_REF] Nicolae | BlobCR: Efficient Checkpoint-Retart for HPC Applications on IaaS Clouds using Virtual Disk Image Snapshots[END_REF].

Two complementary aspects are considered:

• the detection and management of faults inherent to the hardware and software systems used • the detection and management of faults emanating from the application code itself Both aspects are different and imply different system components to react. However, unforeseen or incorrectly handled application errors may have undesirable effects on the execution of system components. The system and hardware fault management components might then have drastic procedure to confine the errors, which can lead to the application aborting. This is the case for out of bound parameter and data values, incorrect service invocations, if not correctly taken care of in the application codes.

This raises an important issue in algorithms design. Parallelization of numeric codes on HPC platforms is today taken into account in an expanding move towards petascale and future exascale computers. But so far, only limited algorithmic approaches take into account fault-tolerance from the start.

Resilience Sub-system

Generic system components have been designed and tested for fault-tolerance. They include fault-tolerance backpanes [START_REF] Gupta | CIFTS: a Coordinated Infrastructure for Fault-Tolerant Systems[END_REF] and fault-tolerance interfaces [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF]. Both target general procedures to cope with systematic monitoring of hardware, system and applications behaviors. Performance consideration limit the design options of such systems where incremental and multi-level checkpoints become the norm, in order to alleviate the overhead incurred by checkpoints storage and CPU usage. These can indeed exceed 25% of the total wall time requirements for scientific applications [START_REF] Bautista-Gomez | FTI: high-performance Fault Tolerance Interface for hybrid systems[END_REF].

Other proposals take advantage of virtual machines technologies to optimize checkpoints storage using incremental ("shadowed" and "cloned") virtual disks images on virtual machines snapshots [START_REF] Nicolae | BlobCR: Efficient Checkpoint-Retart for HPC Applications on IaaS Clouds using Virtual Disk Image Snapshots[END_REF].

Conclusion

The advent of petascale computers has raised concerns about system faulttolerance and application resilience. Because exascale computers are now emerging, these concerns become even more stringent.

Sophisticated and optimized functionalities are therefore required in the upcoming hardware, systems and application codes to support effectively error management.

Large-scale applications also require distributed and heterogeneous environments to run collaborative multidiscipline projects. Workflow management systems are good candidate to deploy and control these applications because they require highlevel and non-expert level dynamic features, e.g., interactive control and visualization.

They also require dynamic reconfiguration capabilities, e.g., in case of task redeployment because of hardware and software failures. Overall, they require resilience support because of potential software errors and erratic and unexpected behavior, e.g., because of wrong simulation parameters.

This paper defines concepts, details current problems and addresses solutions to application resilience. This approach is currently implemented and tested on simulation testcases using a distributed platform that operates a workflow management system interfaced with a cloud infrastructure. An automotive testcase is presented addressing a vehicle rear-mirror drag optimization.

The platform provides functionalities for application specification, deployment, execution and monitoring. It features resilience capabilities to handle runtime errors. It implements the cloud computing "Platform as a Service" paradigm while using a workflow system interface.

Fig. 1 .

 1 Fig. 1. Resilience domains and concepts.

Fig. 2 .

 2 Fig. 2. Error management.

Fig. 4 .

 4 Fig. 4. Error detection and assessment.

•

  the early detection of errors • root cause characterization • characterization of transient vs. persistent errors • the tracing and provenance of faulty data • the identification of the impacted components and their associated corrupted results • the ranking of the errors (warnings, fatal, medium) and associated actions (ignore, restart, backtrack) • the identification of pending components • the identification and purge of transient messages • the secured termination of non-faulty components • the secure storage of partial and consistent results • the quick recovery of faulty and impacted components • the re-synchronization of the components and their associated data • the properly sequenced restart of the components Each of these items needs appropriate implementation and algorithms in order to orchestrate the various actions required by the recovery of the faulty application components.

Fig. 5 .

 5 Fig. 5. Error handler.

Fig. 7 .

 7 Fig. 7. Error recovery.

Fig. 8 .

 8 Fig. 8. Restart.

Fig. 9 .

 9 Fig. 9. Checkpoints.

Acknowledgments

This work is supported by the European Commission FP7 Cooperation Program "Transport (incl. aeronautics)", for the GRAIN Coordination and Support Action ("Greener Aeronautics International Networking"), grant ACS0-GA-2010-266184.

It is also supported by the French National Research Agency ANR (Agence Nationale de la Recherche) for the OMD2 project (Optimisation Multi-Discipline Distribuée), grant ANR-08-COSI-007, program COSINUS (Conception et Simulation).


Pierre Comon
email: pcomon@unice.fr

Giorgio Ottaviani
email: ottavian@math.unifi.it

On the typical rank of real binary forms

Keywords: tensor rank, binary form, symmetric tensor, polynomial, genericity AMS Subject Classification: 15A69, 15A72, 14L99

We determine the rank of a general real binary form of degree d = 4 or d = 5. In the case d = 5, the possible values of the rank of such general forms are 3, 4, 5. This is the first reported case, to our knowledge, where more than two typical ranks have been found. We prove that a real binary form of degree d with d real roots has rank d.

Introduction

Motivation. The decomposition of tensors into a minimal sum of rank-1 terms, sometimes referred to as the Canonical Polyadic decomposition (CP), has raised a great interest in several quite different branches of engineering [START_REF] Sidiropoulos | Parallel factor analysis in sensor array processing[END_REF][START_REF] Kroonenberg | Applied Multiway Data Analysis[END_REF][START_REF] Smilde | Multi-Way Analysis[END_REF][START_REF] Bader | Algorithm 862: Matlab tensor classes for fast algorithm prototyping[END_REF][START_REF] Morup | Parallel factor analysis as an exploratory tool for wavelet transformed event-related EEG[END_REF][START_REF] Carroll | Analysis of individual differences in multidimensional scaling via n-way generalization of Eckart-Young decomposition[END_REF][START_REF] Comon | Tensor decompositions, state of the art and applications[END_REF] as well as in mathematics [START_REF] Hackbusch | Hierarchical Kronecker tensor-product approximation[END_REF][START_REF] Iarrobino | Power sums, Gorenstein algebras and determinantal loci[END_REF][START_REF] Ürgisser | Algebraic Complexity Theory[END_REF][START_REF] Lickteig | Typical tensorial rank[END_REF][START_REF] Landsberg | On the ranks and border ranks of symmetric tensors[END_REF][START_REF] Bernardi | Computing symmetric rank for symmetric tensors[END_REF][START_REF] Buczynski | Ranks of tensors and a generalization of secant varieties[END_REF]. More precisely, the symmetric case of the CP decomposition is dealt with in [START_REF] Iarrobino | Power sums, Gorenstein algebras and determinantal loci[END_REF][START_REF] Landsberg | On the ranks and border ranks of symmetric tensors[END_REF][START_REF] Bernardi | Computing symmetric rank for symmetric tensors[END_REF], and the general case in [START_REF] Lickteig | Typical tensorial rank[END_REF][START_REF] Buczynski | Ranks of tensors and a generalization of secant varieties[END_REF], while [START_REF] Ürgisser | Algebraic Complexity Theory[END_REF] is a general thorough reference focused on complexity. If we take the example of tensors of order 4 to fix the ideas, the CP decomposition of a tensor T is defined as:

T ijkℓ = r p=1 α i (p) β j (p) γ k (p) δ ℓ (p)
The minimal value of r such that the equality holds is called the rank of tensor T .

In applications, these tensors are often corrupted by measurement or estimation noises, which can be modeled as additive random variables with continuous probability distribution. The consequence is that tensors to be decomposed are generic.

A key question is then to know what is the rank of such tensors as a function of order and dimensions, and when they admit a finite number of CP decompositions. For real or complex symmetric tensors decomposed in the complex field, this question has been answered, and enters the framework of the Waring problem [START_REF] Iarrobino | Power sums, Gorenstein algebras and determinantal loci[END_REF][START_REF] Ciliberto | Geometric aspects of polynomial interpolation in more variables and of Waring's problem[END_REF]. The Theorem of Alexander and Hirschowitz (see [START_REF] Alexander | Polynomial interpolation in several variables[END_REF] and also [START_REF] Brambilla | On the Alexander-Hirschowitz theorem[END_REF]) answers that the generic rank is always the expected one, with a finite list of exceptions. However, it has not yet received any response either for non symmetric tensors, or for decompositions in the real field. ten Berge showed that real third order generic tensors can assume two typical ranks, r and r +1 [START_REF] Berge | The typical rank of tall three-way arrays[END_REF]. But he could not find generic tensors assuming more than two typical ranks. Regarding general complex tensors, some partial results are contained in [START_REF] Abo | Induction for secant varieties of Segre varieties[END_REF], while [START_REF] Catalisano | Secant varieties of P 1 × . . . × P 1 (n-times) are not defective for n ≥ 5[END_REF] provides a complete answer for tensors of format 2 × . . . × 2. We point out also the recent preprint [START_REF] Reznick | Laws of inertia in higher degree binary forms[END_REF], where the related concept of signature is studied.

Contribution. In order to exhibit more than two typical ranks, it seems necessary to consider tensors of order higher than 3. The simplest case we can think of is that of real symmetric tensors of dimension 2 and order 4 or 5. Yet, such tensors are bijectively associated with homogeneous polynomials in two variables [START_REF] Ehrenborg | Apolarity and canonical forms for homogeneous polynomials[END_REF], namely binary quartics and quintics, respectively.

The previous definition translates to binary forms as follows. The rank of a binary form f (x, y) = d i=0 d i a i x d-i y i of degree d defined over the field K is the minimum integer r such that there is a decomposition f = r j=1 c j (l j ) d where l j are linear forms and c j ∈ K. Note that the rank is called "length" in [START_REF] Reznick | Sums of even powers of real linear forms[END_REF]. If K is the real field, coefficients c j can be imposed to belong to {-1, 1}. If K is the complex field, one can impose c j = 1 for all coefficients. In the complex field, the rank of a general binary form f of odd degree d = 2n + 1 is n + 1. The Sylvester Theorem asserts that the decomposition of such general form f as a sum of n + 1 powers of linear forms is unique (up to a multiplicative factor for each c j ) , and gives also a way to determine it. The rank of a general binary form f of even degree d = 2n is n + 1, but in this case such decompositions form an infinite set, which can be identified with the projective line.

It is interesting that no semicontinuity holds for the rank. Indeed there are forms such that their rank is bigger than the general value and other such that the rank is lower than the general value. Indeed it is well known (see for example Comas and Seiguer [START_REF] Comas | On the rank of a binary form[END_REF]) that on the complex numbers the rank can attain all the values between 1 and d.

Define (ii) S R 5,r has non empty interior only for r = 3, 4, 5. More precisely, assume that f has distinct roots, then • (ii1) if f has five real roots then the rank of f is 5.

S K d,r = {f ∈ Sym d (K 2 )|rank f = r},
• (ii2) if f has one or three real roots then the rank of f is 3 or 4, according to the sign of an invariant of degree 12 defined in section 4, where we provide an algorithm.

Very probably, S R d,r has a non empty interior if and only if ⌊ d 2 ⌋ + 1 ≤ r ≤ d. We leave this as a conjecture to the readers (proved here for d ≤ 5), as the intriguing problem of the relations between S R d,r and the loci where the number of real roots is fixed. We prove also in Prop. 3.1 that if a form of degree d has the maximal number d of real roots, then its rank attains the maximum possible value which is again d.

There is always an open subset where the general rank is the same as the complex one. In other words, for given order and dimension, the smallest typical rank in the real field coincides with the generic rank in the complex field (see [START_REF] Comon | Generic and typical ranks of multi-way arrays[END_REF], [START_REF] Friedland | On the generic rank of 3-tensors[END_REF]).

Preliminaries: quadratic and cubic forms

An elementary example illustrating the difference between real and complex rank is given by the equality

2x 3 -6xy 2 = (x + √ -1y) 3 + (x - √ -1y) 3 = (2 2/3 x) 3 -(x + y) 3 -(x -y) 3
In this case the complex rank is 2 and the real rank is 3. Let's begin with a known general statement.

x + t 1 y) d = d i=0 d i t d-i 0 t i 1 x d-i y i we get that the curve C d can be parametrized by a i = t d-i 0 t i 1 . Pick d -1 general points on C d corresponding to l d i = (l i,0 x + l i,1 y) d for i = 1, . . . , d -1.
The linear span of f and these points is a hyperplane, whose equation

d i a i c i = 0 restricts to C d to the binary form d i c i t d-i 0 t i 1 of degree d with the d -1 real roots (t 0 , t 1 ) = (l i,0 , l i,1 ) (because d i c i l d-i i,0 l i i,1 = 0) hence also the last root is real, corresponding to a last linear form l d d .
This means that f is a projective linear combination of the the powers

l d i for i = 1, . . . , d, or equivalently, f has rank ≤ d.
Because of the bijection mentioned earlier, f ∈ Sym 2 (K 2 ) corresponds to a symmetric 2 × 2 matrix, and its rank is the same as the rank of the associated matrix. Hence f has rank 2 if and only if f has distinct roots, both for

K = R or K = C. So S R
2,r has non empty interior only if r = 2. For any field of characteristic zero, the dual ring of differential operators

D = K[∂ x , ∂ y ] acts on the polynomial ring R = K[x, y] = ⊕ d≥0 Sym d (K 2 ) = ⊕ d≥0 R d
with the usual rules of differentiations. This action preserves the degrees, in the sense that we have the pairing

R d ⊗ D k → R d-k
which means that the homogeneous differential operators of degree k takes homogeneous polynomials of degree d to homogeneous polynomials of degree dk.

If l = ax + by ∈ R 1 , we denote by l ⊥ = b∂ x -a∂ y ∈ D 1 its orthogonal (apolar) operator, such that l ⊥ (l) = 0. The main remark, which goes back to the XIXth century, is that the form f = r j=1 c j (l j ) d is killed by the operator r j=1 l ⊥ j . The space of operators of degree k which kill a given form f of degree d is the kernel of the linear map A f : D k → R d-k ; see [START_REF] Ehrenborg | Apolarity and canonical forms for homogeneous polynomials[END_REF] for instance.

In the basis {∂ k-i x ∂ i y } i=0,...k and { d-k j x d-k-j y j } j=0,...,d-k the matrix of A f is (up to scalar multiples) the well known Hankel matrix (called catalecticant by Sylvester) of size (d

-k + 1) × (k + 1)      a 0 a 1 a 2 . . . a k a 1 a 2 a 3 . . . . . . . . . a d-k . . . a d     
For general forms f , the map A f has maximal rank. We may assume 2k ≤ d, so that its kernel has dimension d -2k. This holds on any field K.

In particular the general form of degree d = 2n + 1 is killed by a unique operator of degree n. This gives a proof of Sylvester Theorem over C. The kernel of the Hankel matrix of size n × (n + 1) is an operator g of degree n, and decomposing it over C as g = n j=1 l ⊥ j gives the decomposition of f as sum of n d-th powers of the l j . If f is real, the kernel g is real, but the decomposition is possible only if all the roots of g (thought as a polynomial) are real.

Comon and Mourrain explored further this situation [START_REF] Comon | Decomposition of quantics in sums of powers of linear forms[END_REF]. If it is not possible to find a kernel of degree n such that all its roots are real, we consider operators of degree (n + 1) and we look for such an operator in the kernel such that all the roots are real. If this is not possible we go further, and so on.

We use this technique by reproving the classically known criterion to determine the rank in the case d = 3. For f ∈ Sym 3 (R 2 ), consider the discriminant

∆(f ) = 4 a 0 a 1 a 1 a 2 • a 1 a 2 a 2 a 3 - a 0 a 2 a 1 a 3 2 Proposition 2.2 S R 3
,r has non empty interior only for r = 2, 3. Precisely, let f be a polynomial of third degree without multiple roots. Then (i) f has rank two if and only if ∆(f ) < 0, or equivalently, if and only if f has one real root (ii) f has rank three if and only if ∆(f ) > 0, or equivalently, if and only if f has three real roots.

Proof:

The differential operators of degree two which annihilate f consist of the kernel of the matrix

a 0 a 1 a 2 a 1 a 2 a 3
The discriminant of the quadratic generator of the kernel coincides with -∆(f ); thus the operators have two real roots if ∆(f ) < 0 and this means that the rank-2 complex decomposition is actually real. Note also that a cubic of real rank two can have only one real root. Indeed the equation l 3 1 + l 3 2 = 0 reduces to the three linear equations l 1e nπi 3 l 2 = 0 for n = 0, 1, 2. This proves (i). If ∆(f ) > 0, the quadratic generator has no real root and (ii) follows from Prop. 2.1.

Remark

The complete description of rank of tensors of dimension 2 and order 3 can be found in [START_REF] Gelfand | Discriminants, Resultants, and Multidimensional Discriminants[END_REF](ch. 14, ex. 4.5) in the complex case and in [START_REF] De | Tensor rank and the ill-posedness of the best low-rank approximation problem[END_REF] in the real case.

3. Forms with all real roots, with an application to quartics Proposition 3.1 Let be a real binary form of degree d with d real distinct roots. Then the (real) rank of f is equal to d.

Proof:

The proof is by induction on d. By the previous section, let d ≥ 3. Assume the rank is ≤ d -1. Then we get f = d-1 i=1 l d i and since there are infinitely many such decompositions we may assume that l d-1 does not divide f . Consider the rational function

F = f l d-1
Under a linear (real) change of projective coordinates φ(x, y) = (x ′ , y ′ ) with • (x 2 + y 2 )(x 2 + ay 2 ) (a > 0 no real root, a < 0 two real roots) • (x 2y 2 )(x 2 + ay 2 ) (a < 0 four real roots) Case d = 5:

y ′ = l d-1 we get G(x ′ , y ′ ) = F (φ -1 (x ′ , y ′ )) = f (φ -1 (x ′ ,y ′ ))
• x(x 2 + y 2 )(x 2 + 2axy + by 2 ) (b -a 2 > 0 one real root, b -a 2 < 0 three real roots)
• x(x 2y 2 )(x 2 + 2axy + by 2 ) (ba 2 < 0 five real roots)

Proof: We prove just the first case for d = 4, the other ones being analogous. When there are two pairs of conjugate roots, they lie in the complex plane on a circle with real center, then a convenient circle inversion makes the four roots on a vertical line. A translation and a homothety centered at zero conclude the argument.

When there is one pair of conjugate roots, assume that they are ± √ -1. Then consider the tranformations x → x+c -cx+1 , which preserve ± √ -1 and it is easy to show that a convenient choice of c makes the sum of the other two roots equal to zero. For d = 3, after a Möbius transformation, we may assume that f = x 3 + 3xy 2 . Then f x = 3(x 2 + y 2 ) has no real roots.

For d = 4 we may assume by the Lemma 3.3 that f = (x 2 + y 2 )(x 2 + ay 2 ). For a > -1 we consider f x = x • (4x 2 + 2(a + 1)y 2 ) which has only one real root. For a < -1 we consider f y = y • (4ay 2 + 2(a + 1)x 2 ) which has only one real root. For a = -1 then f xf y has only one real root.

For d = 5 we may assume by the Lemma 3.3 that f = x(x 2 +y 2 )(x 2 +2axy +by 2 ). The discriminant of f x is (up to a positive scalar multiple) D(a, b)

:= -540a 2 - 1584a 4 + 830b 3 -180b 4 -180b 2 -8192a 6 + 405b 5 + 405b -7476a 2 b 2 + 1548a 2 b + 14784a 4 b -396a 2 b 3 + 576a 4 b 2 -432b 4
x + bf y has rank ≤ d -2, otherwise, if the rank is d -1, it follows that af x + bf y has d -1 real roots. So we get af x + bf y = d-2 i=1 l d-1 i . Choose c, d such that ad -bc = 0. Let F (t) = f (at + c, bt + d). We get that F ′ (t) = d-2 i=1 n i (t) d-1
for some degree one polynomials n i and by integration there is a constant K and degree one polynomials

m i such that F (t) (bt+d) d = d-2 i=1 mi(t) d (bt+d) d + K (bt+d) d . With the substitution t = dx-yc
-bx+ay we get that the rank of f is ≤ d -1, which is against the assumption.

Remark We do not know if the part (ii) of the Prop. 3.4 holds for d ≥ 6. If this is true, also the Cor. 3.5 can be extended. Now we can give our promised application to quartics. Proof of the Main Theorem in the case d = 4. Prop. 3.1 and Cor. 3.5 show that the rank 4 is attained if and only if f has four real roots. By the results quoted at the end of the introduction, the smallest typical rank in the real field coincides with the generic rank in the complex field , which in this case is 3. By the Prop. 2.1 no other typical ranks are possible.

We end this section with a last general result about forms such that their complex rank is smaller than the general one. Proposition 3.6 Let f be a real binary form of degree d and complex rank k. Assume that 2 ≤ k < ⌊ d 2 ⌋ + 1. Then there are only two possibilities: (i) The real rank is equal to the complex rank (ii) The real rank of f is ≥ dk + 2 (when k = 2 the equality holds).

Proof:

Assume that (i) does not hold. This means that the contraction

D k → R d-k
has rank k and that the one dimensional kernel is generated by one operator with at least two complex conjugate roots. It follows that also the transpose operator

D d-k → R k
has rank k, and the operators in the kernel are given exactly by the previous operator times every operator degree d -2k. In particular no operator in the kernel has all real roots. This argument works also for the next contraction

D d-k+1 → R k-1
which has again rank k. At the next step it is possible to find an operator in the kernel with all real roots. This concludes the proof. When k = 2 the equality holds by Prop. 2.1.

Quintics

It is relatively easy to check if a real quintic form has rank three. Indeed we have to compute the kernel [β 0 , β 1 , β 2 , β 3 ] of the matrix

  α 0 α 1 α 2 α 3 α 1 α 2 α 3 α 4 α 2 α 3 α 4 α 5  
The coefficients β i are given by the 3 × 3 minors of the above matrix. Now in order to check if β = 3 i=0 x 3-i y i β i has three real roots we consider the invariant of degree 12

I 12 (α 0 , . . . , α 5 ) := ∆(β)
where ∆ is the discriminant considered before. A nickname for I 12 could be the "apple invariant", as we will se in the next pictures. We have that the general f has rank three if and only if β has three real roots and by Prop. For quintics with less than 5 real roots, it is enough to consider the canonical form f = x(x 2 + y 2 )(x 2 + 2axy + by 2 ) of Lemma 3.3, and compute for this form the sign of the invariant I 12 . Now f has rank three if and only if I 12 > 0, and rank four if and only if I 12 < 0.

This sign can be checked explicitly from the expression (up to a positive scalar multiple)

I 12 (a, b) = 2b 3 -142b 4 -64a 6 + 3752b 5 -83a 2 b 2 + 144a 4 b + 3960a 2 b 3 - 11840a 4 b 2 -62900b 4 a 2 -311952b 5 a 4 -593208b 7 a 2 + 375552b 3 a 6 + 287488ba 8 + 348552b 5 a 2 + 243056a 4 b 3 + 12096a 6 b -243410b 6 a 2 -673952a 4 b 4 -392736a 6 b 2 + 99840a 8 b 2 + 700160a 6 b 4 + 700160a 4 b 6 + 92940a 2 b 8 + 7680a 8 b 4 + 19712a 10 b 2 - 336640a 8 b 3 -6560a 6 b 6 -287040a 6 b 5 -115712a 10 b+480a 4 b 8 -44400a 4 b 7 -4680a 2 b 9 + 77a 2 b 10 -4096a 8 -43192b 9 + 170652b 7 -43192b 6 + 170652b 8 -78848a 10 + 3752b 10 + 2b 12 -142b 11 + 8192a 12 .
Yet, two regions of the affine space separated by a variety have a non empty interior. This completes the proof.

The region where I 12 > 0 intersects in a set of positive measure the two regions where f has one or three real roots, separated by the curve ba 2 = 0. The same holds true for the region where I 12 < 0. As an illustration, these regions are depicted in Figures 1 and2. For real quintics in the canonical form f = x(x 2 + y 2 )(x 2 + 2axy + by 2 ) the ones with rank four consist of the shaded area in the (a, b)-plane in Figure 1, that is, the area where I 12 < 0. I 12 contains only even powers of a, hence the pictures are symmetric with respect the b-axis. It follows that the "apple" is all over the parabola (depicted in dashed line in the figures).

The figure 2 shows the quintics with one real root (over the parabola) which have rank four; we get a bounded region.

We get that most of quintics with one real root have rank three, but both rank three and four have nonempty interior, although the rank four part is bounded. In the same way most of quintics with three real roots (under the parabola) have rank three, but both ranks three and four have nonempty interior, and even both regions are unbounded.

We conclude this paper with an algorithm which summarizes our results on real quintics. realrank-v23

Linear and Multilinear Algebra 665

Proposition 2 . 1

 21 Any binary real form of degree d has real rank ≤ d. Proof: The points of the projective space P d = P(S d R 2 ) correspond to forms f = d i=0 d i a i x d-i y i , which have coordinates (a 0 , . . . , a d ) . The rational normal curve C d , corresponds to polynomials which are d-th powers of linear forms. From the expansion (t 0

  y ′dThen the polynomial G(x ′ , 1) = d-2 i=1 n i (x ′ ) d + 1 has d distinct real roots since f had, (where deg n i = 1) and its derivatived dx ′ G(x ′ , 1) = d-2 i=1 dn i (x ′ ) d-1 d dx ′ (n i (x ′ )) has d -1 distinct real roots. Now d dx ′ G(x ′ , 1) has rank ≤ d -2, indeed d dx ′ n i (x ′ )are constants. This contradicts the inductive assumption. Hence the assumption was false and the rank of f must exceed d -1. The rank of f must eventually be equal to d from Proposition 2.1. Lemma 3.2 It is easy to check that under a general Möbius transformation x → ax+b cx+d with adbc = 0 both the number of real roots and the rank of a binary form are invariant. Lemma 3.3 The following are canonical forms under the action of the Möbius transformation group for general forms. Case d = 4:

Proposition 3 . 4

 34 Let f be a real binary form of degree d with distinct roots. (i) If f has d real roots then for every (a, b) = (0, 0) the binary form af x + bf y has d -1 real roots. (ii) Conversely, if for every (a, b) = (0, 0) the binary form af x + bf y has d -1 real roots and 3 ≤ d ≤ 5, then f has d real roots. Proof: (i) Consider that for any substitution x = at+c, y = bt+d with ad-bc = 0 we have that F (t) = f (at + c, bt + d) has d real roots, then d dt f (at + c, bt + d) = af x + bf y has d -1 real roots corresponding to the d -1 extremal points of F . (ii) Assume that f has ≤ d -1 (hence ≤ d -2) real roots, and let us show that there exist (a, b) such that af x + bf y has ≤ d -2 (hence ≤ d -3) real roots.

a 2 .

 2 It can be shown that f x has zero real roots if D(a, b) > 0 and two real roots if D(a, b) < 0. This concludes the proof. Corollary 3.5 Let f be a real binary form of degree d with distinct roots. If f has rank d and 3 ≤ d ≤ 5 then it has d real roots. Proof: The proof is by induction on d. For d = 3 it follows from the Prop. 2.2. Let 4 ≤ d ≤ 5. If f has ≤ d-2 real roots then by Prop. 3.4(ii), there exists (a, b) = (0, 0) such that the binary form af x + bf y has ≤ d -3 real roots. Otherwise, if for every (a, b) = (0, 0) the form af x + bf y has d -1 real roots, it follows from Prop. 3.4(ii) that f has d real roots. Then by the inductive assumption af

Figure 1 .

 1 Figure 1. In the shaded area, I 12 < 0, and the quintics considered have rank 4. In the area where I 12 > 0, they have rank 3.

Figure 2 . 5 ( 1 ) 1 α 2 α 3 α 2 α 3 α 4 α 3 α 4 α 5 x 3 - α 0 α 2 α 3 α 1 α 3 α 4 α 2 α 4 α 5 x 2 + α 0 α 1 α 3 α 1 α 2 α 4 α 2 α 3 α 5 x - α 0 α 1 α 2 α 1 α 2 α 3 α 2 α 3 α 4 a)

 25113524 Figure 2. In the shaded area, the quintics considered have rank four and have only one real root; the parabola ba 2 = 0 is represented in dashed line.

latter values of r are called generic ranks in C. On the real numbers

  we are intested in the pairs (d, r) such that S R d,r has non empty interior. If for a given value of d there exist several values of r, the latter are called typical ranks. In other words, if r i are typical, none of the sets S R d,ri is dense, but ∪ i S R d,ri is. For d = 2, 3 the situation is well known and we recall it in the next section. Our main results are the following, for d = 4, 5.

	realrank-v23
	Linear and Multilinear Algebra	659
	the set of binary forms of rank
	exactly r. On complex numbers, S C d,r has a non empty interior only for the pairs
	(d, r) where r = ⌊ d 2 ⌋ + 1. That is, for every d, there is a unique r such that S C d,r is dense. The Main Theorem
	(i) S R 4,r has non empty interior only for r = 3, 4. More precisely, assume that f has distinct roots, then
	• (i1) if f has four real roots then the rank of f is 4. • (i2) if f has zero or two real roots then the rank of f is 3.

  2.2 (ii) this happens if and only if I 12 > 0. Proof of the Main Theorem in the case d 5 By Prop. 3.1 and Cor. 3.5 we get that, for d = 5, a form f with distinct roots has rank 5 if and only if it has 5 real roots. Hence, we have just to prove that both rank three and four have nonempty interior in the other cases.

Taylor & Francis and I.T. Consultant

Acknowledgment This work was begun at the workshop on Geometry and representation theory of tensors for computer science, statistics and other areas, held in July 2008 at the AIM, California, and presented at the Workshop on Tensors and Interpolation held in Nice in June 2009. We thank the AIM and J. Landsberg for useful talks. The work has been also supported in part by contract ANR-06-Blan-0074 "Decotes".