A large amount of resources is spent writing, porting, and optimizing scientific and industrial High Performance Computing applications, which makes autotuning techniques fundamental to lower the cost of leveraging the improvements on execution time and power consumption provided by the latest software and hardware platforms. Despite the need for economy, most autotuning techniques still require large budgets of costly experimental measurements to provide good results, while rarely providing exploitable knowledge after optimization. The contribution of this paper is a user-transparent autotuning technique based on Design of Experiments that operates under tight budget constraints by significantly reducing the measurements needed to find good optimizations. Our approach enables users to make informed decisions on which optimizations to pursue and when to stop. We present an experimental evaluation of our approach and show it is capable of leveraging user decisions to find the best global configuration of a GPU Laplacian kernel using half of the measurement budget used by other common autotuning techniques. We show that our approach is also capable of finding speedups of up to 50x, compared to gcc's -O3, for some kernels from the SPAPT benchmark suite, using up to 10x fewer measurements than random sampling.

Broadly used and applied in many domains, Hidden Markov Models are a well established formalism, both in computer science and statistics.Among other reasons, they owe their popularity to a fast fitting method, i.e., the Baum-Welch algorithm, allowing to adjust models to a variety of input data.Using expectation and maximization phases, BW assures an increase to the model likelihood at every iteration.Yet, to initialize the sequence of expectationmaximization (EM) steps, it is a standard procedure to start the BW algorithm from randomly generated values.We propose a, simple and fast, deterministic pre-fitting approach which derives the BW's initial values directly from the input data.

We propose a simple, fast, deterministic pre-fitting approach which derives the Baum–Welch algorithm initial values directly from the input data. Such pre-fitting has the purpose of improving the fitting time for a given Hidden Markov Model (HMM) while maintaining the original Baum–Welch algorithm as the fitting one. The fitting time is improved by avoiding the Baum–Welch algorithm sensitiveness through the generation of parameters closer to the global maximum likelihood. Furthermore, by keeping the original Baum–Welch algorithm as the fitting one, we guarantee that all related methods will continue to work properly. On the other hand, the pre-fitting generates the HMM parameters directly derived from time-series data, without any data transformation, using an [Formula: see text] operation.

Fog computing provides computing, storage and communication resources at the edge of the network, near the physical world. Subsequently, end devices nearing the physical world can have interesting properties such as short delays, responsiveness, optimized communications and privacy. However, these end devices have low stability and are prone to failures. There is consequently a need for failure management protocols for IoT applications in the Fog. The design of such solutions is complex due to the specificities of the environment, i.e., (i) dynamic infrastructure where entities join and leave without synchronization, (ii) high heterogeneity in terms of functions, communication models, network, processing and storage capabilities, and, (iii) cyber-physical interactions which introduce non-deterministic and physical world's space and time dependent events. This paper presents a fault tolerance approach taking into account these three characteristics of the Fog-IoT environment. Fault tolerance is achieved by saving the state of the application in an uncoordinated way. When a failure is detected, notifications are propagated to limit the impact of failures and dynamically reconfigure the application. Data stored during the state saving process are used for recovery, taking into account consistency with respect to the physical world. The approach was validated through practical experiments on a smart home platform.

The use of stochastic formalisms, such as Stochastic Automata Networks (SAN), can be very useful for statistical prediction and behavior analysis.Once well fitted, such formalisms can generate probabilities about a target reality.These probabilities can be seen as a statistical approach of knowledge discovery.However, the building process of models for real world problems is time consuming even for experienced modelers.Furthermore, it is often necessary to be a domain specialist to create a model.This work illustrates a new method to automatically learn simple SAN models directly from a data source.This method is encapsulated in a tool called SAN GEnerator (SANGE).This new model fitting method is powerful and relatively easy to use; therefore this can grant access to a much broader community to such powerful modeling formalisms.

Analysts commonly use execution traces collected at runtime to understand the behavior of an application running on distributed and parallel systems. These traces are inspected post mortem using various visualization techniques that, however, do not scale properly for a large number of events. This issue, mainly due to human perception limitations, is also the result of bounded screen resolutions preventing the proper drawing of many graphical objects. This paper proposes a new visualization technique overcoming such limitations by providing a concise overview of the trace behavior as the result of a spatiotemporal data aggregation process. The experimental results show that this approach can help the quick and accurate detection of anomalies in traces containing up to two hundred million events.

Given a set of individuals, a collection of subsets, and a cost associated to each subset, the Set Partitioning Problem (SPP) consists in selecting some of these subsets to build a partition of the individuals that minimizes the total cost. This combinatorial optimization problem has been used to model dozens of problems arising in specific domains of Artificial Intelligence and Operational Research, such as coalition structures generation, community detection, multilevel data analysis, workload balancing, image processing, and database optimization. All these applications are actually interested in special versions of the SPP where assumptions regarding the admissible subsets constraint the search space and allow tractable optimization algorithms. However, there is a major lack of unity regarding the identification, the formalization, and the resolution of these strongly-related problems. This paper hence proposes a generic framework to design dynamic programming algorithms that fit with the particular algebraic structure of special versions of the SPP. We show how this framework can be applied to two well-known versions, thus opening a unified approach to solve new ones that might arise in the future.

Performance analysis through visualization techniques usually suffers semantic limitations due to the size of parallel applications. Most performance visualization tools rely on data aggregation to work at scale, without any attempt to evaluate the loss of information caused by such aggregations. This paper proposes a technique to evaluate the quality of aggregated representations - using measures from information theory - and to optimize such measures in order to build consistent multiresolution representations of large execution traces.

Software applications providers have always been required to perform load testing prior to launching new applications. This crucial test phase is expensive in human and hardware terms, and the solutions generally used would benefit from further development. In particular, designing an appropriate load profile to stress an application is difficult and must be done carefully to avoid skewed testing. In addition, static testing platforms are exceedingly complex to set up. New opportunities to ease load testing solutions are becoming available thanks to cloud computing. This paper describes a Benchmark-as-a-Service platform based on: (i) intelligent generation of traffic to the benched application without inducing thrashing (avoiding predefined load profiles), (ii) a virtualized and self-scalable load injection system. The platform developed was experimented using two use cases based on the reference JEE benchmark RUBiS. This involved detecting bottleneck tiers, and tuning servers to improve performance. This platform was found to reduce the cost of testing by 50 percent compared to more commonly used solutions.

The performance of parallel and distributed applications is highly dependent on the characteristics of the execution environment. In such environments, the network topology and characteristics tell how fast data can be transmitted and placed in the resources. These are key phenomena to understand the behavior of such applications and possibly improve it. Unfortunately few visualization available to the analyst are capable of accounting for such phenomena. In this paper, we propose an interactive topology-based visualization technique based on data aggregation that enables to correlate network characteristics, such as bandwidth and topology, with application performance traces. We show that such kind of visualization enables to explore and understand non trivial behavior that are impossible to grasp with classical visualization techniques. We also show that the combination of multi-scale aggregation and dynamic graph layout allows our visualization technique to scale seamlessly to large distributed systems. These results are validated through a detailed analysis of a high performance computing scenario and of a grid computing scenario.

SUMMARY Understanding the behavior of large scale distributed systems is generally extremely difficult as it requires to observe a very large number of components over very large time. Most analysis tools for distributed systems gather basic information such as individual processor or network utilization. Although scalable because of the data reduction techniques applied before the analysis, these tools are often insufficient to detect or fully understand anomalies in the dynamic behavior of resource utilization and their influence on the applications performance. In this paper, we propose a methodology for detecting resource usage anomalies in large scale distributed systems. The methodology relies on four functionalities: characterized trace collection, multi‐scale data aggregation, specifically tailored user interaction techniques, and visualization techniques. We show the efficiency of this approach through the analysis of simulations of the volunteer computing Berkeley Open Infrastructure for Network Computing architecture. Three scenarios are analyzed in this paper: analysis of the resource sharing mechanism, resource usage considering response time instead of throughput, and the evaluation of input file size on Berkeley Open Infrastructure for Network Computing architecture. The results show that our methodology enables to easily identify resource usage anomalies, such as unfair resource sharing, contention, moving network bottlenecks, and harmful short‐term resource sharing. Copyright © 2011 John Wiley & Sons, Ltd.

International audience

In the age of cloud, Grid, P2P, and volunteer distributed computing, large-scale systems with tens of thousands of unreliable hosts are increasingly common. Invariably, these systems are composed of heterogeneous hosts whose individual availability often exhibit different statistical properties (for example stationary versus non-stationary behavior) and fit different models (for example Exponential, Weibull, or Pareto probability distributions). In this paper, we describe an effective method for discovering subsets of hosts whose availability have similar statistical properties and can be modelled with similar probability distributions. We apply this method with about 230,000 host availability traces obtained from a real large-scale Internet-distributed system, namely SETI@home. We find that about 34% of hosts exhibit availability that is a truly random process, and that these hosts can often be modelled accurately with a few distinct distributions from different families. We believe that this characterization is fundamental in the design of stochastic scheduling algorithms across large-scale systems where host availability is uncertain.

Using MPI as communication interface, one or several applications may introduce complex communication behaviors over the network cluster. This effect is increased when nodes of the cluster are multi-processors, and where communications can income or outgo from the same node with a common interval time. Our goal is to understand those behaviors to build a class of predictive models of bandwidth sharing, knowing, on the one hand the flow control mechanisms and, on the other hand, a set of experimental results. This paper present experiences that show how is shared the bandwidth on gigabit Ethernet, Myrinet 2000 and Infiniband network before to introduce the models for Gigabit Ethernet and Myrinet 2000 networks.

Nowadays, peer to peer systems are largely studied. But in order to evaluate them in a realistic way, a better knowledge of their environments is needed. In this article we focus on the computers availability in these systems. We characterize this availability behind ADSL lines and we link it with the availability of peer to peer systems participants. We emphasise on the methodology as generalized in other systems such as grids or ad-hoc systems. We finally show how users of ADSL lines are related to peer to peer users and we give some examples of the possible practical use of theses results. The results are based on trace datasets obtained over the first five month of 2003 with around 5000 hosts.

Stochastic bounds are obtained on execution times of parallel programs when the number of processors is unlimited. A parallel program is considered to consist of interdependent tasks with synchronization constraints. These constraints are described by an acyclic directed graph called a task graph. The execution times of tasks are considered to be independently identically distributed (i.i.d.) random variables. The performance measure of interest is the overall execution of the considered parallel program (task graph). Stochastic bound methods are applied to obtain lower and upper bounds on this measure. Another upper bound is obtained for parallel programs having 'new better than used in expectation' (NBUE) random variables as task execution times. NBUE random variables are replaced with exponential random variables of the same mean to derive this upper bound.>