To limit the impact of datacenters on climate change various sustainable and effective solutions are being developed. The Datazero2 project aims to design datacenters running solely on local renewable energy combined with storage sources. A multi-hour prevision of user demand (workload) or of IT system usage, using time series, are possible ways to plan energy usage, with the aim of reducing energy consumption while maintaining a required quality of service. The seasonal component of time series is a key element, since it indicates one or more periodic phenomena that can be estimated and implemented in forecasting methods. In this paper, we propose a seasonal study of multiple time series from different workloads. Seasonality is studied using periodograms, a highly effective Fast Fourier Transform technique for detecting seasonal patterns. In addition, since the detected seasonal patterns can be irregular (unexpected, delayed and/or extended user demands or IT system usage), we propose a distribution-based clustering using the Kruskal-Wallis test and a seasonal peak appearances analysis. The results show that most of these time series are multi-seasonal (daily and weekly seasonal patterns) but highly irregular, which can reduce the performance of seasonal forecasting methods.

Multi-Agent Systems (MAS) are naturally good candidates for large-scale parallel simulations. However, implementing MAS simulations for distributed memory architectures, such as High Performance Computing clusters, is still complex for non-experts. In this article we present the principle of a Dynamic Distributed Graph structure, that enables the native distribution of MAS simulations. Most of the distribution related issues such as dynamic load-balancing, time synchronization and data migration across processes can be completely automated and abstracted for the user, who can safely design distribution independent MAS models. The major interest of our contribution is the transparent management of concurrent read / write requests across distant processes, a significant feature not provided by surveyed platforms. We also present FPMAS, an open source C++ implementation of a Distributed Multi-Agent System Simulation platform based on the Distributed Graph structure.

Data publishing is a challenging task from the privacy point of view. Different anonymization techniques are proposed in the literature to preserve privacy in accordance with some mathematical constraints. Disassociation is one of the anonymization techniques that relies on the km - anonymity privacy constraint to guarantee a certain level of privacy for set-valued datasets (e.g., search and shopping items). Dis-association separates a set-valued dataset by clustering the dataset into groups of records with common frequent items, and then splitting each cluster into record chunks respecting km - anonymity. In this paper, we define a new ant-based clustering algorithm based on the disassociation technique to keep some of the items associated together throughout the anonymization process. We define these associations as utility rules that should be treated with eagerness while anonymizing the data. We perform a set of experiments to evaluate our algorithm w.r.t. these utility rules.

Summary Computational simulation is becoming increasingly important in numerous research fields. Depending on the modeled system, several methods such as differential equations or Monte‐Carlo simulations may be used to represent the system behavior. The amount of computation and memory needed to run a simulation depends on its size and precision, and large simulations usually lead to long runs, thus requiring to adapt the model to a parallel system. Complex systems are often simulated using multi‐agent systems (MASs). While linear system based models benefit from a large set of tools to take advantage of parallel resources, multi‐agent systems suffer from a lack of platforms that ease the use of such resources. In this paper, we propose the use of Nested Graphs for a new modeling approach that allows the design of large, complex, and multi‐scale multi‐agent models, which can efficiently be distributed on parallel resources. Nested Graphs are formally defined and are illustrated on the well‐known predator‐prey model. We also introduce PDMAS (parallel and distributed multi‐agent system): a platform that implements the Nested Graph modeling approach to ease the distribution of multi‐agent models on High Performance Computing clusters. Performance results are presented to validate the efficiency of the resulting models.

Energy consumption has become a major concern in the recent years and Green computing has arisen as one of the challenges in order to reduce CO2emissions in the computing domain. Many efforts have been made to make hardware less energy consuming, reduce cooling energy of data and computing centers by relocating those facilities to cool regions and other. A novel approach to make the computing domain greener is to add renewable energy sources for the power supply. The challenge of this work is to consider computing facilities which are solely run by renewable energy sources such as solar panels and wind turbines. In this work we tackle the problem of scheduling independent tasks within a predicted power envelope that varies during the time. First we evaluate different instances of the problem from a theoretical point of view. Then we propose several heuristics for the case of multi-core architectures and we assess their performance on synthetic workloads and power envelopes.

Summary Bias in the performance evaluation of scheduling heuristics has been shown to undermine the scope of existing studies. Improving the assessment step leads to stronger scientific claims when validating new optimization strategies. This article considers the problem of allocating independent tasks to unrelated machines such as to minimize the maximum completion time. Testing heuristics for this problem requires the generation of cost matrices that specify the execution time of each task on each machine. Numerous studies showed that the task and machine heterogeneities belong to the properties impacting heuristics performance the most. This study focuses on orthogonal properties, the average correlations between each pair of rows and each pair of columns, which measure the proximity with uniform instances. Cost matrices generated with 2 distinct novel generation methods show the effect of these correlations on the performance of several heuristics from the literature. In particular, EFT performance depends on whether the tasks are more correlated than the machines and HLPT performs the best when both correlations are close to one.

Assessing the performance of scheduling heuristics through simulation requires one to generate synthetic instances of tasks and machines with well-identified properties. Carefully controlling these properties is mandatory to avoid any bias. We consider the scheduling problem consisting of allocating independent sequential tasks on unrelated machines while minimizing the maximum execution time. In this problem, the instance is a cost matrix that specifies the execution cost of any task on any machine. This article proposes two measures for quantifying the heterogeneity properties of a cost matrix. An analysis of two classical methods used in the literature reveals a bias in previous studies. We propose new methods to generate instances with given heterogeneity properties and we show that heterogeneity has a significant impact on twelve heuristics.

Simulation has become an indispensable tool for researchers to explore systems without having recourse to real experiments. In this context multi-agent systems are often used to model and simulate complex systems. Depending on the characteristics of the modelled system, methods used to represent the system may vary. Whatever the modelling techniques used, increasing the size and the precision of a model increases the amount of computation needed, requiring the use of parallel systems when it becomes too large. Usually, to efficiently run on parallel resources, the model must be adapted to be distributed. In this paper, we propose a new modelling approach, based on nested graphs, that allows the design of large, complex and multi-scale multi-agent models which can be efficiently distributed on parallel resources. A PDMAS (Parallel and Distributed Multi-Agent Platform) that supports this approach and efficiently run parallel multi-agent models is introduced.

Summary In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the ℓp‐quasi‐norm for p∈(0,1). Minimization of the ℓp‐quasi‐norm is implemented via a successive linear programming approximation heuristic. We propose several new algorithms based on this approach, and we assess their efficiency through simulations. The experiments show that the scheme outperforms the classic Largest Task First list based algorithm for scheduling small to medium instances but needs improvements to compete on larger numbers of jobs. Copyright © 2014 John Wiley & Sons, Ltd.

Multi-Agent Systems (MAS) can be used to model systems where the global behavior cannot be uniformly represented by standard techniques such as partial differential equations or linear systems because the system elements have their own independent behavior. This is, for instance, the case in complex systems such as daily mobility in a city for example. Depending on the system size the computing power needs for the MAS may be as big as for more traditional linear numerical systems and may need to be parallelized to fully represent real systems. Graphical Processing Units (GPU) have already proven to be an efficient support to execute large linear programs. In this paper we present the use of GPU for the execution of Sworm, a multi-scale MAS system. We show that GPU computing can be efficient in that less regular case and when the agent behavior is simple. We advocate for a wider use of the GPU in Agent Based Models in particular for multi-scale systems with work distribution between the CPU and GPU.

In this paper we study the problem of batch scheduling within a homogeneous cluster. In this context, the problem is that the more processors the job requires the more difficult it is to find an idle slot to run it on. As a consequence the resources are often inefficiently used as some of them remain unallocated in the final schedule. To address this issue we propose a technique called job folding that uses virtualization to reduce the number of processors allocated to a parallel job and thus allows to execute it earlier. Our goal is to optimize the resource use. In this paper we propose several heuristics based on job folding and we compare their performance with classical on-line scheduling algorithms as FCFS or backfilling. The contributions of the paper are both on the design of the job folding algorithms and on their performance analysis.

In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks onto a set of machines. The originality of our approach is the failure model for such applications in which tasks are subject to failures rather than machines. If there is exactly one task per machine in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same machine. Several polynomial time heuristics are presented for the most realistic specialized setting, in which tasks of a same type can be mapped onto the same machine. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed.

Search algorithms are a key issue to share resources in large distributed systems as peer networks. Several distributed interconnection structures and algorithms have already been studied in this context. With expanding ring algorithms, the efficiency of searches depends on the topology used to send query requests and the dynamics of the structure. In this paper, we present an interconnection structure that limits the number of messages needed for search queries. This structure, called distributed spanning tree (DST), defines each node as the root of a spanning tree. So, it behaves as a tree for the number of messages but it balances the load generated by the requests among computers, and thus, it avoids to overload the root node. This structure is scalable because it needs only a logarithmic memory space per computer to be maintained. A formal and practical description of the structure is presented and we describe traversal algorithms. Simulations show that DST based searches behave better than randomly generated graphs and trees as it generates less messages to query all computers while avoiding the tree bottlenecks.

Random graph and tree are two topologies used to build overlay networks. These overlay networks may be used by large scale discovery mechanisms to run search algorithms. The distributed spanning tree (DST) is another topology that may be used as overlay. In a DST, every computer is a leaf. DST's non-leaf nodes are sets of computers instead of computers. Thus, it allows the use of tree traversal algorithms while avoiding the usual tree's bottlenecks. As a result, the DST allows more efficient executions of search algorithms in term of number of sent messages and in term of load balancing. In this paper, we describe the results of several simulations of flooding algorithm executions. These simulations are run on the three previous topologies and for different numbers of nodes. These simulations indicate that the DST structure is more efficient than graph topology which, in turn, is more efficient than tree topology in term of traversal speed and in term of supported load for every simulated scale. We study as well the behaviour of the DST when nodes are added or deleted to show that the structure is adapted to dynamic environments.

In this paper we consider the scheduling of a batch of the same job on a heterogeneous execution platform. A job is represented by a directed acyclic graph without forks (intree) but with typed tasks. The execution resources are distributed and each resource can carry out a set of task types. The objective function is to minimize the makespan of the batch execution. Three algorithms are studied in this context: an online algorithm, a genetic algorithm and a steady-state algorithm. The contribution of this paper is on the experimental analysis of these algorithms and on their adaptation to the context. We show that their performances depend on the size of the batch and on the characteristics of the execution platform.

Abstract Network‐enabled server (NES) environments are valuable candidates to provide simple computing Grid access. These environments allow transparent access to a set of computational servers via Remote Procedure Call mechanisms. In this context, a challenge is to increase performances by decreasing data traffic. This paper presents DTM (Data Tree Manager), a data management service for NES environments. Based on the notions of data persistency and data replication, DTM proposes a set of efficient policies which minimize computation times by decreasing data transfers between the clients and the platform. From the end‐user point of view, DTM is accessible through a simple and transparent API. We describe DTM and its implementation in the DIET (Distributed Interactive Engineering Toolbox) platform. We also present a set of experimental results which show the feasibility and the efficiency of our approach. Copyright © 2007 John Wiley & Sons, Ltd.

The Internet development and the availability of reliable networks led to the emergence of grid architectures. The aim of these architectures is to take benefit of widely distributed resources to improve execution possibilities. Depending on their properties, these architectures are usually classified into desktop grids, resources grids and application based grids. Application based grids provide an easy access to applications deployed on the grid on the ASP (application service provider) mode. When these grids grow of orders of magnitude, application lookup will become a costly activity of the grid. In this article, we study how a lookup algorithm scales when the size of the grid grows up. We exhibit a "lookup throughput" which characterizes the grid interconnections graph and the lookup algorithm

Mobility study is composed of many research areas like urban mobility. In the literature, urban mobilities are represented by analytical techniques like stochastic laws or they are defined by simulation tools like multi-agents systems (MAS). The goal of our work is to define citizen behaviour in order to observe population dynamics by a simulation. This strategy is facilitated by a meta-model and a toolkit which are used with a particular method. The latter begins by a conceptual representation of each mobile and finishes by a mobility simulator. This paper aims at describing the mobility simulation toolkit. Thanks to this framework, mobility simulator development is simplified. It allows us to create distributed applications which are based on MAS.

Peer-to-peer and grid applications currently have few structures that allow efficient discovery mechanisms in large scale system. The trees can be an appropriate structure for this task. However, the tree's bottlenecks are a significant drawback in large scale architectures and connected graphs are used most of the time. In this paper, we propose an appropriate architecture named distributed spanning tree (DST) to allow discovery in large scale environment. This structure is organized into a hierarchy of groups. The nodes are put together in groups and groups are gathered in groups of higher level, recursively. This organization, built on top of routing tables allows the instantaneous creation of spanning trees rooted by any nodes and keeps the load balanced between the nodes. The first studies about the distributed spanning tree suggest that it has all the advantages of a tree without its drawbacks. This can be explained by the following complexity order: each node stores only O(log(n)) information; a parallel traversal needs n - 1 messages and takes O(log(n)) units of time; adding or removing a node needs O(n) messages in the worst case but only needs in average O(log(n)) messages. Load balancing and fault tolerance are ensured by the architecture of the distributed spanning tree itself.