Analyzing and understanding the performance behavior of parallel applications on various compute infrastructures is a long-standing concern in the High Performance Computing community. When the targeted execution environments are not available, simulation is a reasonable approach to obtain objective performance indicators and explore various łwhat-if?ž scenarios. In this work we present a framework for the of-line simulation of MPI applications.

The main originality of our work with regard to the literature is to rely on time-independent execution traces. This allows for an extreme scalability as heterogeneous and distributed resources can be used to acquire a trace. We propose a format where for each event that occurs during the execution of an application we log the volume of instructions for a computation phase or the bytes and the type of a communication.

To acquire time-independent traces of the execution of MPI applications, we have to instrument them to log the required data. There exist many proőling tools which can instrument an application. We propose a scoring system that corresponds to our framework speciőc requirements and evaluate the most well-known and open source proőling tools according to it. Furthermore we introduce an original tool called Minimal Instrumentation that was designed to fulőll the requirements of our framework. We study diferent instrumentation methods and we also investigate several acquisition strategies. We detail the tools that extract the timeindependent traces from the instrumentation traces of some well-known proőling tools. Finally we evaluate the whole acquisition procedure and we present the acquisition of large scale instances.

We describe in detail the procedure to provide a realistic simulated platform őle to our trace replay tool taking under consideration the topology of the real platform and the calibration procedure with regard to the application that is going to be simulated. Moreover we present the implemented trace replay tools that we used during this work. We show that our simulator can predict the performance of some MPI benchmarks with less than 11% relative error between the real execution and simulation for the cases that there is no performance issue. Finally, we identify the reasons of the performance issues and we propose solutions.

Résumé

L'analyse et la compréhension du comportement d'applications parallèles sur des platesformes de calcul variées est un problème récurent de la communauté du calcul scientiőque. Lorsque les environnements d'exécution ne sont pas disponibles, la simulation devient une approche raisonnable pour obtenir des indicateurs de performance objectifs et pour explorer plusieurs scénarios łwhat-if?ž. Dans cette thèse, nous présentons un environnement pour la simulation of-line d'applications écrites avec MPI.

La principale originalité de notre travail par rapport aux travaux précédents réside dans la déőnition de traces indépendantes du temps. Elles permettent d'obtenir une extensibilité maximale puisque des ressources hétérogènes et distribuées peuvent être utilisées pour obtenir une trace. Nous proposons un format dans lequel pour chaque événement qui apparaît durant l'exécution d'une application, nous récupérons les informations sur le volume d'instructions pour une phase de calcul ou le nombre d'octets et le type d'une communication.

Pour obtenir des traces indépendantes du temps lors de l'exécution d'applications MPI, nous devons les instrumenter pour récupérer les données requises. Il existe plusieurs outils d'instrumentation qui peuvent instrumenter une application. Nous proposons un système de notation qui correspond aux besoins de notre environnement et nous évaluons les outils d'instrumentation selon lui. De plus, nous introduisons un outil original appelé Minimal Instrumentation qui a été conçu pour répondre au besoins de notre environnement. Nous étudions plusieurs méthodes d'instrumentation et plusieurs stratégies d'acquisition. Nous détaillons les outils qui extraient les traces indépendantes du temps à partir des traces d'instrumentations de quelques outils de proőling connus. Enőn nous évaluons la procédure d'acquisition complète et présentons l'acquisition d'instances à grande échelle.

Nous décrivons en détail la procédure pour fournir un őchier de plateforme simulée réaliste à notre outil d'exécution de traces qui prend en compte la topologie de la plateforme cible ainsi que la procédure de calibrage par rapport à l'application qui va être simulée. De plus, nous montrons que notre simulateur peut prédire les performances de certains benchmarks MPI avec moins de 11% d'erreur relative entre l'exécution réelle et la simulation pour les cas où il n'y a pas de problème de performance. Enőn, nous identiőons les causes de problèmes de performances et nous proposons des solutions pour y remédier.

Chapter 1

Introduction

Motivation

Computational Science is the third scientiőc way to study problems arising in various domains such as physics, biology, or chemistry. It is complementary to theory and actual experiments and consists in conducting studies in silico. This approach makes an heavy use of resources located in computing centers. The eicient execution of a parallel application on a certain massively parallel hardware architecture demands the user to be familiar not only with domain-speciőc algorithms but also parallel data structures [START_REF] Kurowski | Complex system simulations with qoscosgrid[END_REF][START_REF] Kurowski | Parallel large scale simulations in the pl-grid environment[END_REF]. It is not rare to observe situations where an application can not fully exploit a large number of processors in its execution, thus it does not scale well [START_REF] Umakishore Ramachandran | Issues in understanding the scalability of parallel systems[END_REF].Such cases can be caused by a not optimized application, the computer system or both. However, through performance evaluation a scientist can observe the performance of an application and can identify bottlenecks [START_REF] Liu | Automatic performance debugging of spmd-style parallel programs[END_REF][START_REF] Gschwandtner | Performance analysis and benchmarking of the intel scc[END_REF][START_REF] Pesterev | Locating cache performance bottlenecks using data proőling[END_REF][START_REF] Roth | Deconstructing the overhead in parallel applications[END_REF][START_REF] Su | A generalized, distributed analysis system for optimization of parallel applications[END_REF][START_REF] Hammond | Performance characterization of global address space applications: a case study with nwchem[END_REF]. The techniques which constitute the performance evaluation őeld can be classiőed into two categories: measurement and modeling techniques [START_REF] Jain | The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling[END_REF][START_REF] Brewer | Proteus: A high-performance parallel-architecture simulator[END_REF][START_REF] Ferrari | Measurement and tuning of computer systems[END_REF]. The latter is separated by many scientists into simulation and analytical modeling. A lot of approaches have been presented to evaluate the performance of an application. Some of them correlate the performance of an application with its scientiőc domain [START_REF] Schulz | Interpreting performance data across intuitive domains[END_REF]. More precisely, in this approach the authors take data from three domains, the application's working set, the hardware domain of the compute and network devices and the communication domain. The combination of visualizing and correlating these data, provides useful information about the behavior of the parallel application. On the other hand some researchers identify bottlenecks on a speciőc application which are related to the operating system such as noise, the cluster manager tool and őx them by applying some techniques to decrease the noise [START_REF] Petrini | The case of the missing supercomputer performance: Achieving optimal performance on the 8,192 processors of asci q[END_REF].

As the number of scientiőc domains producing results from in silico studies increases, the computing centers then have to upgrade their infrastructures in a continuous way. The resources impacted by such upgrades are of diferent kinds, e.g., computing, network and storage. Moreover each kind of resource grows more complex with each generation. Processors have more and more cores, low latency and high bandwidth network solutions become mainstream and some disks now have access time close to that of memory.

The complexity of the decision process leading to the evolution of a computing center is then increasing. This process often relies on years of experience of system administrators and users. The former knows how complex systems work while the latter have expertise on the behavior of their applications. Nevertheless this process lacks of objective data about the performance of a given candidate infrastructure. Such information can only be obtained once the resources have been bought and the applications can be tested. Any unforeseen behavior can then lead to large but vain expenses. This procedure could be completed with less risks by using simulation techniques. Simulation may help the dimensioning of compute clusters in large computing centers. Through simulations the scientists can understand the behavior of large-scale computers. Moreover it is possible to simulate an application for a platform that is not available yet to observe the performance and decide what would be the best hardware characteristics for the needs of the computer center.

Many universities do not provide large-scale computer systems to the researchers and students. Clusters are too expensive as also their maintenance. The access to another supercomputers could cost also a signiőcant amount of money. In such cases the option to predict the performance of an application through simulation is really important. A scientist can execute simulations without using any resource and be able to validate or not his assumptions. Some times a multi-parameter application is needed to be executed, thus it would take a lot of time to try diferent parameters for each execution on a supercomputer. The students can study concepts of parallel computing without using a cluster but just their simulator. However, the performance evaluation and prediction are not always easy to be done.

Issues on Performance Prediction and Evaluation of Parallel Applications

The őrst diicult step during the performance evaluation of a parallel application is the choose of the appropriate metrics. The metrics are essential for understanding the performance characteristics of applications on modern multicore microprocessor. They can indicate a relation between the performance bottleneck and the hardware. However, if a user is not familiar it can be a diicult task. A tool which can help the user was released by Texas Advanced Computing Center called PerfExpert [START_REF] Burtscher | Perfexpert: An easy-to-use performance diagnosis tool for hpc applications[END_REF] which basically executes an application four to őve times. During each execution the tool uses diferent metrics and it measures them periodically. As result it proposes which metrics represent any performance issue that occur mainly during the execution of loops in the code. Moreover a tool called AutoScope [START_REF] Sopeju | AutoSCOPE: Automatic Suggestions for Code Optimizations using PerfExpert[END_REF] proposes code optimization techniques based on the results from PerfExpert. However, performance measurement usually is not a harmonic task. Diferent parts of a code can cause non similar behaviors and diferent metrics could represent their performance. Computational science applications are constituted by iterative methods. A common method is to study the performance of each iteration [START_REF] Kotakemori | Performance evaluation of a parallel iterative method library using openmp[END_REF][START_REF] Shende | main. -performance evaluation of adaptive scientiőc applications using {TAU}[END_REF] where in some cases we can observe non similar performance between diferent iterations. The further analysis of the performance of an application should be achieved through extensive study of the measurements. The main issue with a őne grained measurement is the extra overhead caused by the instrumentation tool. When a user wants to correlate performance measurements with execution time, can not be sure what percentage of these measurements are caused by the instrumentation overhead. This makes the study harder and can hide some other phenomena or create artifacts that are not always easy to explain.

The increase of the hardware complexity raised the diiculty to predict the performance of an application. Diferent processors are constituted by diferent cache memory levels and size. The performance of an application can depend on the cache size. Moreover there are many types of networks, Ethernet Gigabit [START_REF]Gigabit ethernet[END_REF], Inőniband [START_REF] Pőster | Aspects of the inőniband architecture[END_REF] etc. Each of them behave diferent and thus some analytical models should be created in order to simulate the applications. In this work we study Ethernet Gigabit networks. The studied parallel applications are based on the Message Passing Interface (MPI) [START_REF] Lusk | A high-performance, portable implementation of the mpi message passing interface standard[END_REF]. The various implementations of the MPI, MPICH [START_REF] Frost | Mpich performance characteristics and considerations[END_REF], and OpenMPI [START_REF] Gabriel | Open MPI: Goals, concept, and design of a next generation MPI implementation[END_REF], can behave a bit diferent but always respecting the MPI standards. For example some collective communications can behave similarly but not exactly the same. Thus the simulation of a parallel application is a diicult task where many aspects of the applications should be taken under consideration to predict correctly the performance.

Contributions

In this work we propose a new execution log format that is independent of time. This format includes volumes of computation (in number of instructions) and communications (in bytes) for each event instead of classical time-stamps. We present in detail an original approach that totally decouples the acquisition of the trace from its replay. Furthermore, several original scenarios are proposed that allow for the acquisition of large execution traces. These scenarios are only possible because of the chosen time-independent trace format and they can not be applied with other frameworks. We implement a new proőling tool based on our framework requirements which instruments exactly the necessary information from an application, it saves the measurement data directly into time-independent traces and it is more eicient than similar tools. We study the state of the art of the most well known and open sources proőling tools and we evaluate them with regard to our framework requirements. Moreover we justify which ones can be used for our work. We use various instrumentation methods and we evaluate them to show the evolution of the instrumentation overhead. As supporters of the open-science approach, we provide a step-by-step deőnition of an appliance to acquire execution traces on the Grid'5000 experimental infrastructure. Moreover we have our őles available in public to be used from other researchers. Some tools were implemented to extract the time-independent traces from well known proőling tools such as TAU, Score-P and gather them into a single node. We evaluate the time-independent trace acquisition framework to present the overhead, the advantages and disadvantages. The trace replay tool is built on top of a fast, scalable and validated simulation kernel. The implemented simulator tool is analyzed in detail and we describe how to use it by covering all the procedure from calibrating the simulator till the execution of a simulation. Finally, we predict through simulation the performance of some non adaptive MPI applications with small relative error between the real execution and simulation. In the cases that there are some performance issues, we investigate and őgure out what causes any performance issue.

Organization of the Document

The remaining of this document is organized as follows. Chapter 2 presents an introduction to some related topics. We present some benchmarks, we analyze some of them and we indicate which ones we use. Afterwards we present some techniques to evaluate the performance of an application such as the interface to access the hardware counters of the processors is introduced as also some instrumentation methods which are used to measure the performance of an application. We analyze the tracing, proőling, and statistical proőling methods and we explain the advantages and disadvantages.

In Chapter 3 we explore the time-independent trace acquisition framework. In the beginning we explain the motivation for this work, we introduce the time-independent trace format and we analyze the advantages. We provide more details about the whole framework and we mention the trace replay concept. There is an extensive analysis of the instrumentation of an application where we evaluate many well known tools with a score system which respects the framework requirements. We present our proőling library which can instrument an application with less instrumentation overhead and memory requirements. The instrumentation methods which we used are presented and compared. Moreover the acquisition of time-independent traces is presented with all the execution modes that can be used and also instructions of how to reproduce the experiments on Grid'5000 platform. We have implemented some tools to extract time-independent traces from well known proőling tools such as TAU and Score-P as also gather them from all the participating nodes into a single node. Finally we evaluate the acquisition procedure to present the overheads of our framework.

Chapter 4 presents the time-independent trace replay. First of all the components of the simulation are introduced with the calibration procedure where is explained to the user how to calibrate the simulator. Afterwards the simulation backends that were used for the implementation of the various versions of our simulator are presented with their diferences. At last we present the simulation accuracy of some MPI applications and we show that our framework predicts their performance.

Finally in Chapter 5 we present the conclusions and future perspectives.

Chapter 2

Background on Performance Evaluation

Chapter 1, analyzing and understanding the performance of a parallel application is a complex task. Some parallel applications may scale well when increasing the number of the processors while others may sufer from scalability issues. In general we could divide applications in two categories, those that fully exploit the performance of a computer system and to the ones that solve a real problem. Performance evaluation is usually performed thanks to various instrumentation methods when an application is executed on a real platform. However, there are two other approaches that provide insight about the behavior of an application: emulation and simulation. The purpose of this chapter is to introduce some basic concepts for the better understanding of the remaining of this document.

This Chapter is organized as follows. Section 2.1 presents some micro-benchmarks and benchmarks. We explain why they are used and how useful where for our case. In Section 2.2 we detail the interface which provides access to the hardware counters of processors to measure speciőc metrics. Moreover we investigate available instrumentation methods for the performance measurement of an application. Finally in Section 2.3 we detail how to assess the performance on applications on resources. Three methods are analyzed with their advantages and drawbacks.

Evaluating the Performance of Resources

Micro-benchmarks

A micro-benchmark is a test program designed to measure the performance of a very small and speciőc piece of code. Micro-benchmarks tend to be synthetic kernels and can measure a speciőc aspect of computer system. Through them we can understand the behavior of major kernel characteristics.

Netgauge [START_REF] Hoeŕer | Netgauge: A network performance measurement framework[END_REF] is a high-precision network parameter measurement tool. It supports microbenchmarking of many diferent network protocols and communication patterns. The main focus lies on accuracy, statistical analysis and easy extensibility. One of the included micro-benchmarks that we used is OS Noise which measures the noise caused by the Operating System.

OS Noise supports three diferent micro-benchmarking methods. Selősh Detour (selősh) is a modiőed version of the selősh detour benchmark proposed in [START_REF] Beckman | Benchmarking the efects of operating system interference on extreme-scale parallel machines[END_REF]. The micro-benchmark runs in a tight loop and measures the time for each iteration. If an iteration takes longer than the minimum times a particular threshold, then the time-stamp (detour) is recorded. The micro-benchmark runs until it records a predeőned number of detours. Fixed Work Quantum (FWQ), performs a őxed amount of work multiple times and records the time it takes for each run. Due to the őxed work approach of FWQ, the data samples can be used to compute useful statistics (mean, standard deviation and kurtosis) of the scaled noise. These statistics then can be used to characterize and categorize the amount of noise in a hardware and software environments.

During the execution of the Fixed Time Quantum (FTQ) micro-benchmark, a very small work quantum is performed until a őxed time quantum has been exceeded and for each iteration it records how many workload iterations were carried out. If there is no noise this number should be equal for every sample. When there is noise this number varies. Because the start and end time of every sample is deőned, the periodicity of noise can be analyzed with this method. Finally the FTQ and FWQ micro-benchmarks are proposed from the list of benchmarks for the sequoia supercomputer [START_REF]Sequoia Benchmarks[END_REF]. In our studies, we used the FTQ micro-benchmark and the noise caused by the Operating System on diferent Grid'5000 clusters was computed to be at most 0.14% of the execution time. It is important to compute the percentage of the noise caused by external factors such as the operating system to know if the measurement data are biased or not. The speciőc amount of noise is not signiőcant on the considered execution platforms. However, this is not a generic statement. If a scientist wants to apply some statistic methods on some performance measurement data, then the OS noise may probably be taken into account.

SKaMPI [START_REF] Reussner | SKaMPI: a Comprehensive Benchmark for Public Benchmarking of MPI[END_REF] is a micro-benchmark for implementations of the MPI standard. Its purpose is the detailed analysis of individual MPI operations. SkaMPI can be conőgured and tuned in many ways: operations, measurement precision, communication modes, packet sizes, number of processors used, etc. Moreover SkaMPI provides measurement mechanisms that combine accuracy, eiciency, and robustness. Each measurement is derived from multiple measurements of single calls to particular communication pattern with regard to the requested accuracy. SkaMPI handles systematic and statistical errors. The systematic error is caused by the measurement overhead of all calls, it is usually small and can be corrected by subtracting the duration of an empty measurement and the warm-up of the cache by a dummy call to the measurement routine before actually starting to measure. The statistical error is checked through the control of the standard error and the average execution time. We used this micro-benchmark to calibrate our simulation as presented in Section 4.3.

Benchmarks

Benchmarks are software packages which can make use of almost all resources in the system. Various kernels, synthetic programs and application level workloads, are called benchmarks. A subset of a benchmark can be a micro-benchmark. One main reason for benchmarking a computer system is to measure the performance and probably compare with other systems. However, we should be familiar to the kind of applications that are going to be executed on those systems to execute benchmarks that are representative of these applications. One of the most well-known benchmarks is High Performance Linpack (HPL) [START_REF] Luszczek | Introduction to the hpc challenge benchmark suite[END_REF] which measures the ŕoating point execution rate for solving a linear system of equations in double precision arithmetic on distributed-memory computers. It is used to rank supercomputers in the Top5000 [START_REF]The Top 500[END_REF] list which is constituted by the 500 fastest supercomputers of the world. However, this benchmark does not measure the system performance for a signiőcant collection of important science and engineering applications. HPL rankings of computer systems are no longer strongly correlated to real application performance, especially for the broad set of HPC applications governed by diferential equations, which tend to have much stronger needs for high bandwidth and low latency networks, and tend to access data using irregular patterns. Thus a new benchmark suite has been proposed, named High Performance Conjugate Gradient (HPCG) [START_REF] Dongarra | Toward a new metric for ranking high performance computing systems[END_REF]. HPCG is composed of computations and data access patterns commonly found in applications.

The NAS Parallel Benchmarks (NPB) [START_REF] Bailey | The nas parallel benchmarks[END_REF] have been developed at NASA Ames Research Center to study the performance of parallel supercomputers. This is a set of eight benchmark problems, each focusing on some important aspect of highly parallel supercomputing for aerophysics applications. The eight problems consist of őve łkernelsž and three łsimulated computational ŕuid dynamics (CFD) applicationsž. The őve kernels are relatively compact problems, each of which emphasizes a particular type of numerical computation. The simulated applications combine several computations in a manner that are similar to the actual order of execution in certain important CFD application codes.

Each benchmark can be executed for 7 diferent classes, denoting diferent problem sizes: S (the smallest), W, A, B, C, D, and E (the largest). For instance, between class A and class C, the problem size is increased by almost 4 times from one class to the next and from class C to class E the corresponding increase is almost 16 times.

The őve kernels are the following:

EP: An łembarrassingly parallelž kernel. It provides an estimate of the upper achievable limits for ŕoating point performance. This kernel is constituted only from computation and there is communication only during the veriőcation of the solution. It generates pairs of Gaussian random deviates according to a speciőc scheme described in [START_REF] Bailey | The nas parallel benchmarks[END_REF] and tabulates the number of pairs in successive square annuli;

MG: A simpliőed łmultigridž kernel. It requires highly structured long distance communication and tests both short and long distance data communication. Moreover it is memory intensive;

CG: A łconjugate gradientž method is used to compute an approximation to the smallest eigenvalue of a large, sparse, symmetric positive deőnite matrix with a random pattern of non zeros thanks to the inverse power method. This kernel is typical of unstructured grid computations in that it tests irregular long distance communication, employing unstructured matrix vector multiplication;

FT: This kernel performs the essence of many łspectralž codes. It is a rigorous test of longdistance communication performance. It solves numerically a certain partial diferential equation (PDE) using forward and inverse FFTs;

IS: A large łinteger sortž. This kernel performs a sorting operation that is important in łparticle methodž codes. It tests both integer computation speed and communication performance. The three simulated CFD applications are the following: BT: Solves a synthetic system of nonlinear PDEs using a block tridiagonal algorithm; LU: Solve a synthetic system of nonlinear PDEs using a symmetric successive over-relaxation algorithm;

SP: Solve a synthetic system of nonlinear PDEs using a scalar pentadiagonal algorithm. Finally there is a benchmark called Data Traic (DT) which is communication intensive. It uses quad-trees (black hole and white hole) and binary shule as task graphs. It captures core functionality of distributed data acquisition and processing systems.

In out studies, we focused on the EP, DT, LU, and CG benchmarks. We used EP benchmark because it is computation intensive, DT is communication intensive, and the last two ones mix computations and communications.

Evaluating the Performance of Applications

Depending on the application there are various approaches to understand its behavior. First of all we should measure some characteristics of the studied application. The simplest performance metric is time. This way we can observe in which parts of the code the most time is spent and focus on them to further analyze the performance of the application. However, when the application is too complex, the time may not provide enough insight on performance. Then we have to instrument the application to measure other metrics and do further analysis which will guide us to the reasons that the application may not scale or sufer from other performance issues. For example we may want to know if some performance issues of the studied application are inŕuenced by the computation, memory usage, communication between the processes or other factors.

Hardware Counters

The Performance Application Programming Interface (PAPI) [START_REF] Browne | A Portable Programming Interface for Performance Evaluation on Modern Processors[END_REF] is a middleware that provides a consistent and eicient programming interface for the performance hardware counters found in major microprocessors. These counters exist as a small set of registers that count events, occurrences of speciőc signals related to the processor's functions. Monitoring these events facilitates the correlation between the structure of source/object code and the eiciency of the mapping of that code to the underlying architecture. PAPI provides a standard set of over 100 events for application performance tuning but not all of them are necessary available on every processor. Each event can be mapped to either single or linear combinations of native counters on each architecture. Hardware performance counters can provide insight into whole program timing, cache behaviors, branch behaviors, memory and resource contention and access patterns, pipeline stalls, ŕoating point eiciency, instructions per cycle, subroutine resolution, process or thread attribution. With the introduction of Component PAPI, or PAPI-C, PAPI has extended its reach beyond the CPU and can now monitor system information on a range of components from CPUs to network interface cards to power monitors and more. Figure 2.1 shows the internal design of PAPI. PAPI provides two interfaces, high level interface for the acquisition of simple measurements and a fully programmable, low level interface directed towards users with more sophisticated needs. The Component Layer deőnes and exports a machine independent interface to machine dependent functions and data structures. These functions are deőned in components, which may use kernel extensions, operating system calls, or assembly language to access the hardware performance counters on a variety of subsystems. PAPI uses the most eicient and ŕexible of the three, depending on what is available. An instrumentation method can read the values of the hardware counters during the execution of an instrumented application.

Tracing

Observing the time-dependent performance behavior of an application requires to trace its execution. Time-stamped event traces capture what performance is being achieved when and where in the program's execution. With the advent of the distributed processing, the tracing of software events became a dominant technique for performance monitoring [START_REF] Abrams | Design of a measurement instrument for distributed systems[END_REF]. Moreover software event tracing is the foundation of many parallel debugging techniques [START_REF] Gait | A debugger for concurrent programs[END_REF][START_REF] Emrath | Event synchronization analysis for debugging parallel programs[END_REF]. Tracing has also been used to study the performance of an application [START_REF] Malony | An Integrated Performance Data Collection, Analysis, and Visualization System[END_REF][START_REF] Moore | Loop-level proőling and analysis of dod applications using tau[END_REF][START_REF] Brian | Integrated runtime measurement summarisation and selective event tracing for scalable parallel execution performance diagnosis[END_REF]. During the tracing of an application all the executed events are logged except if it is declared otherwise. Each event is associated to a timestamp and includes information related to the executed process and optional data depending on the type of the event. Event logging involves several mechanisms. This includes software instrumentation to generate events and run-time system support to store the events in a trace bufer. One issue observed on many clusters is the time synchronization across the participating nodes during an execution. After the execution of a parallel application each process creates a őle that contains all the occurred events. The advantage of tracing is that we know the performance of an application at each moment for all the execution. For example if an application is constituted by iterative methods, we can extract the performance of each single iteration. However, this procedure adds overhead to the execution time and may require large hard disk space. The tracing procedure is explained in 3.1.

Profiling

The most common way to analyze the performance of an application is the proőling of routine execution. Basically, proőling produce statistics for each routine call by the application indicating the number of times this routine is called and the time spent executing its code, including (or not) the time spent in calls to other routines. Figure 2.2 shows the exclusive and inclusive duration of a routine. The exclusive duration is the amount of time spent while within the foo function excluding the time spent in function bar which is called by foo. The inclusive duration is the amount of execution time spent in foo, including the spent in all the busbroutines called by foo.

Accesses to times (or to hardware performance counters) are trivially made by inserting instrumentation probes at the beginning and ending of each routine as it can be seen in Figure 2.3 where a routine named main, calls a function foo with diferent argument values. The advantage of proőles is that they can be calculated at run-time, require only a small amount of storage, and they can provide a generic glimpse of the application's performance. However, we do not know exactly where a performance issue occurs. In the case of an iterative method, if there is a performance issue with some speciőc iterations we can not observe them. Note that proőles can be extracted through tracing by post-processing the produced trace, but the opposite is not possible.

Statistical Profiling

Statistical proőling or sampling probes the target program's counter at regular intervals using operating system interrupts as we can see in Figure 2.4 where again a routine named main calls a routine foo with diferent arguments. Sampling proőles are less accurate and speciőc than full proőling, but allow the target program to run without inducing an instrumentation overhead. Usually this method is used for applications with long execution time where there is no need for detailed performance analysis.

Assessing the Performance of Applications on Resources

A user can not be aware of the performance of an application on speciőc resources if there is no interaction between them. This interaction can be done either by executing the application on the real platform, executing the application on a virtual environment that corresponds to the resources through emulation or simulating the application to predict its performance. These three approaches constitute the main ways to assess the performance of the applications on the resources and are detailed hereafter.

Experiments

Large-scale computer experiments are becoming increasingly important in science. An experiment can be executed on the available resources. Thus this is the most accurate approach for observing the performance of an application on the speciőc resources. Moreover it is possible through the experiment to observe some unexpected phenomena that a user was not aware of. Experiments also are important for validating theories. Experimentation in a real environment is expensive, because it requires a signiőcant number of resources available for a large amount of time. It also costs time, as it depends on the application to be actually deployed and executed under diferent loads, and for heavy loads long delays in execution time can be expected. Moreover the experiments are not repeatable, because a number of variables that are not under control of the tester may afect experimental results, and elimination of these inŕuences requires more experiments, making it even more time and resource expensive.

For all our direct experiments we used the Grid'5000 [START_REF] Cappello | Grid'5000: A large scale and highly reconőgurable grid experimental testbed[END_REF]40] testbed. In 2003, several teams working around parallel and distributed systems designed a platform to support experimentdriven research in parallel and distributed systems. This platform, called Grid'5000 and opened to users since 2005, was solid enough to attract a large number of users. According to [START_REF] Balouek | Adding Virtualization Capabilities to Grid[END_REF], this platform has led to a large number of research results: 575 users per year, more than 700 research papers, 600 diferent experiments, 24 ANR projects and 10 European projects and 50 PhD. Grid'5000 is located mainly in France (see Figure 2.5), with one operational site in Luxembourg and a second site, not ready yet, in Porto Alegre, Brazil. Grid'5000 provides a testbed supporting experiments on various types of distributed systems (high-performance computing, grids, peerto-peer systems, cloud computing, and others), on all layers of the software stack. The core testbed currently comprises 10 sites. Grid'5000 is composed of 24 clusters, 1,169 nodes, and 8,080 CPU cores, with various generations of technology (Intel (56.2%), AMD (43.8%), CPUs from one to 12 cores, Myrinet, Inőniband and 2 GPU clusters). A dedicated 10 Gbps backbone network is provided by RENATER (the French National Research and Education Network).

From the user point of view, Grid'5000 is a set of sites with the same software environment. It provides to the users heterogeneity which can be controlled during the experiments. The main steps identiőed to run an experiment are (1) reserving suitable resources for the experiment and (2) deploying the experiment on the resources. The resource scheduler on each site is fed with the resource properties so that a user can ask for resources describing the required properties (e.g., 16 nodes connected to the same switch with at least 8 cores and 16 GB of memory). Once enough resources are found, they can be reserved either for exclusive access at a given time or for exclusive access when they become available. In the latter case, a script is given at reservation time, as in classical batch scheduling systems. Several tools are provided to facilitate experiments. Most of them were originally developed speciőcally for Grid'5000. Grid'5000 users select and reserve resources with the OAR batch scheduler [START_REF] Capit | A batch scheduler with high level components[END_REF][START_REF]The OAR Project[END_REF]. Users can install their own system image on the nodes (without any virtual-Figure 2.5: Presentation of the sites and the network of the Grid'5000 testbed. ization layer) using Kadeploy [START_REF] Jeanvoine | Kadeploy3: Eicient and Scalable Operating System Provisioning for HPC Clusters[END_REF]. Moreover the users can deploy a preconőgured environment on a node, called production environment.

Emulation

Emulation [START_REF] Saboo | Emulating petaŕops machines and blue gene[END_REF][START_REF] Vahdat | Scalability and accuracy in a large-scale network emulator[END_REF] is an experimental approach allowing to execute real applications in a virtual environment. This allows us to reach the experimental settings wanted for an experiment. Most of the emulation solutions rely on a heavy infrastructure and mandate the use of a cluster and an emulation layer to reproduce the wanted environment. Emulators let unmodiőed applications run in a speciőc environment where relevant system calls are intercepted and mediated. So basically an emulator is used to replace a system and execute an application on the virtual system.

There are many frameworks which propose their own emulator. The Emulab-Planetlab portal [START_REF] Webb | Implementing the emulab-planetlab portal: Experience and lessons learned[END_REF] allows to use the interface of the Emulab [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF] emulator to access the Planetlab [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF] experimental platform, to emulate applications based on this platform. This helps the scientists to emulate applications considering an existing platform. EMUSIM [START_REF] Calheiros | Emusim: an integrated emulation and simulation environment for modeling, evaluation, and validation of performance of cloud computing applications[END_REF] integrates emulation and simulation environments in the domain of cloud computing applications and provides a framework for increased understanding of this type of systems. Furthermore, Netbed [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF] is a platform based on Emulab that combines emulation with simulation to build homogeneous networks using heterogeneous resources. Another emulator is Distem [START_REF]21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP 2013[END_REF] which builds distributed virtual experimental environments. This tool is easily deployed on Grid'5000 platform and it can emulate a platform composed of heterogeneous nodes, connected to a virtual network described using a realistic topology model. An open problem is still the mapping of a virtual platform on a set of physical nodes. In the case that many virtual machines are on the same physical node there are limitations on the inter-node bandwidth and communication time that should be taken into account during the designing of the experiment.

Simulation

Simulation is a popular approach to obtain objective performance indicators on platforms that are not at one's disposal. Simulation has been used extensively in several areas of computer science for decades, e.g., for microprocessor design and network protocol design. Moreover simulation can be used to evaluate a concept in early development stage. Simulations can also be used to study the performance behavior of an application by varying the hardware characteristics of a hypothetical platform. However, an application should be properly modeled, otherwise the simulation will not be accurate. A simulation is reproducible in comparison to real experiments or emulation. Furthermore, access to large-scale platforms is typically costly (possible access charges to the user, electrical power consumption). The use of simulation can not only save time but also money and resources.

The Message Passing Interface (MPI) is the dominant programming model for parallel scientiőc applications. Given the role of the MPI library as the communication substrate for application communication, the library must ensure to provide scalability both in performance and in resource usage. MPI development is active with an important role in the community and the new version MPI-3.0 [START_REF]MPI: A Message-Passing Interface Standard Version 3[END_REF] was released on September 2012 with intention to improve the scalability, performance and some other issues. Many frameworks for simulating the execution of MPI applications on parallel platforms have been proposed over the last decade. They fall into two categories: on-line simulation or łsimulation via direct executionž [START_REF] Dickens | Parallelized Direct Execution Simulation of Message-Passing Parallel Programs[END_REF][START_REF] Bagrodia | Parallel Simulation of Large-Scale Parallel Applications[END_REF][START_REF] Snavely | A Framework for Application Performance Modeling and Prediction[END_REF][START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF][START_REF] Riesen | A Hybrid MPI Simulator[END_REF][START_REF] León | Instruction-Level Simulation of a Cluster at Scale[END_REF][START_REF] Penof | MPI-NetSim: A network simulation module for MPI[END_REF], and off-line simulation or łpost-mortem simulationž [START_REF] Hoeŕer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF][START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Núñez | New Techniques for Simulating High Performance MPI Applications on Large Storage Networks[END_REF][START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF][START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF]. In on-line simulation the actual code, with no or only marginal modiőcation, is executed on a host platform that attempts to mimic the behavior of a target platform, i.e., a platform with diferent hardware characteristics. Although it is powerful, the main drawback of on-line simulation is that the amount of hardware resources required to simulate application execution at a given scale is commensurate to that needed to run the application on a real-world platform at that scale. Even though a few solutions have been proposed to mitigate this drawback and allow execution on a single computer [START_REF] Adve | Compiler-Optimized Simulation of Large-Scale Applications on High Performance Architectures[END_REF][START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF], the simulation time can be prohibitively high when applications are not regular or have data-dependent behavior. Part of the instruction stream is then intercepted and passed to a simulator. LAPSE is a well-known on-line simulator developed in the early 90's [START_REF] Dickens | Parallelized Direct Execution Simulation of Message-Passing Parallel Programs[END_REF] (see therein for references to precursor projects). In LAPSE, the parallel application executes normally but when a communication operation is performed a corresponding communication delay is simulated for the target platform using a simple network model (aine point-to-point communication delay based on link latency and bandwidth). MPI-SIM [START_REF] Bagrodia | Parallel Simulation of Large-Scale Parallel Applications[END_REF] builds on the same general principles, with the addition of I/O subsystem simulation. A diference with LAPSE is that MPI processes run as threads, a feature which is enabled by a source code preprocessor. Another project similar in intent and approach is the simulator described in [START_REF] Riesen | A Hybrid MPI Simulator[END_REF]. The BigSim project [START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF], unlike MPI-SIM, allows the simulation of computational delays on the target platform. This makes it possible to simulate łwhat if?ž scenarios not only for the network but also for the compute nodes of the target platform. These computational delays are based either on user-supplied projections for the execution time of each block of code, on scaling measured execution times by a factor that accounts for the performance diferential between the host and the target platforms, or based on sophisticated execution time prediction techniques such as those developed in [START_REF] Snavely | A Framework for Application Performance Modeling and Prediction[END_REF]. The weakness of this approach is that since the computational application code is not executed, the computed application data is erroneous. Data-dependent behavior is then lost. This is acceptable for many regular parallel applications, but is more questionable for irregular applications (e.g., branch-and-bound or sparse matrices computations). Going further, the work in [START_REF] León | Instruction-Level Simulation of a Cluster at Scale[END_REF] uses a cycle-accurate hardware simulator of the target platform to simulate computation delays, which leads to a high ratio of simulation time to simulated time.

One diiculty faced by all above MPI-speciőc on-line simulators is that the simulation, be-cause done through a direct execution of the MPI application, is inherently distributed. Parallel discrete event simulation raises diicult correctness issues pertaining to process synchronization. For the simulation of parallel applications, techniques have been developed to speed up the simulation while preserving correctness (e.g., the asynchronous conservative simulation algorithms in [START_REF] Prakash | Asynchronous Parallel Simulation of Parallel Programs[END_REF], the optimistic simulation protocol in [START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF]). A solution could be to run the simulation on a single node but it requires large amounts of CPU and RAM resources. For most aforementioned on-line approaches, the resources required to run a simulation of an MPI application are commensurate to those needed to run the application on a real-world platform. In some cases, those needs can even be higher [START_REF] León | Instruction-Level Simulation of a Cluster at Scale[END_REF][START_REF] Penof | MPI-NetSim: A network simulation module for MPI[END_REF]. One way to reduce the CPU needs of the simulation is to avoid executing computational portions of the application and simulate only expected delays on the target platform [START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF]. Reducing the need for RAM resources is more diicult and if the target platform is a large cluster, then the host platform must then be a large cluster. SMPI [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF], which builds on the same simulation kernel as this work, implements all the above techniques to allow for eicient single-node simulation of MPI applications.

An alternate approach is off-line simulation in which a log, or trace, of MPI communication events (time-stamp, source, destination, data size) is őrst obtained by running the application on a real-world platform. A simulator then replays the execution of the application as if it were running on a target platform. This approach has been used extensively, as shown by the number of trace-based simulators described in the literature since 2009 [START_REF] Hoeŕer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF][START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Núñez | New Techniques for Simulating High Performance MPI Applications on Large Storage Networks[END_REF][START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF][START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF]. The typical approach is to decompose the trace in time intervals delimited by the MPI communication operations. The application is thus seen as a succession of computation bursts and communication operations. An of-line simulator then simply computes simulated delays in a way that accounts for the performance diferential between the platform used to obtain the trace and the platform to be simulated. Computation delays are typically computed by scaling the durations of the CPU bursts in the trace [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Núñez | New Techniques for Simulating High Performance MPI Applications on Large Storage Networks[END_REF][START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF]. Network delays are computed based on a simulation model of the network. The main advantage when compared to on-line simulation is that replaying the execution can be performed on a single computer. This is because the replay does not entail executing any application code, but merely simulating computation and communication delays.

One limitation of these of-line simulators is that trace acquisition is not scalable. To simulate the execution of an application on a platform of a given scale, the trace must be acquired on a homogeneous platform of that same scale, so that time-stamps are meaningful. In some cases, extrapolating a smaller trace to larger numbers of compute nodes is feasible [START_REF] Hoeŕer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], but not generally applicable. Furthermore, the use of time-stamps requires that each trace be accompanied with a description of the platform on which it was obtained, so as to allow meaningful scaling of computation delays. In this work we address the trace acquisition scalability limitation by using time-independent traces.

Another limitation is that these simulators typically use simplistic network models, because they are straightforward to implement and scalable. Possible simpliőcations include: not using a network model but simply replay original communication delays [START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF]; ignoring network contention because it is known to be diicult and costly to simulate [START_REF] Hoeŕer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF][START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF][START_REF] Zheng | Simulation-Based Performance Prediction for Large Parallel Machines[END_REF]; using monolithic performance models of collective communications rather than simulating them as sets of pointto-point communications [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF][START_REF] Badia | Dimemas: Predicting MPI applications behavior in Grid environments[END_REF]. Other simulators opt for accurate packet-level simulation, which is not scalable and leads to high simulation times [START_REF] Núñez | New Techniques for Simulating High Performance MPI Applications on Large Storage Networks[END_REF].

One well-known challenge for of-line simulation is the large size of the traces, which limits the scalability of trace acquisition and can prevent running the simulation on a single node. Mechanisms have been proposed to improve scalability, including compact trace representations [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF] and replay of a judiciously selected subset of the traces [START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF].

In this work, we focus on of-line simulation, by which a trace of a previous execution of the application is łreplayedž on a simulated platform.

SimGrid

SimGrid [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF] is a scientiőc instrument to study the behavior of large-scale distributed systems such as Grids, Clouds, HPC or P2P systems. It can be used to evaluate heuristics, prototype applications or even assess legacy MPI applications. SimGrid was conceived as a scientiőc instrument, thus the validity of its analytical models was thoughtfully studied [START_REF] Velho | Accuracy study and improvement of network simulation in the simgrid framework[END_REF], ensuring their realism. Some of the key features of SimGrid are: ś A scalable and extensible simulation engine that implements several validated simulation models, and that makes it possible to simulate arbitrary network topologies, dynamic compute and network resource availabilities, as well as resource failures; ś High-level user interfaces for distributed computing researchers to quickly prototype simulations either in C or in Java; ś APIs for distributed computing developers to develop distributed applications that can seamlessly run in łsimulation modež or in łreal-world modež. SimGrid ofers four user interfaces as it can be seen in Figure 2.6. MSG module provides an API for the easy prototyping of distributed applications by letting users focus solely on algorithmic issues. Simulations are constructed in terms of concurrent processes, which can be created, suspended, resumed and terminated dynamically, and can synchronize by exchanging data. Moreover it proved perfectly usable in other contexts, such as desktop grids [START_REF] Kondo | Simboinc[END_REF]. An important diference between MSG and SMPI, is that all simulated processes are in the same address space. This simpliőes development of the simulation by allowing convenient communications via global data structures. In other words, while MSG can accurately simulate the interactions taking place in a distributed application, including communication and synchronization delays, the simulated application can be implemented with the convenience of a single address space.

SMPI [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF] is a simulator for MPI applications. Its őrst version provided only on-line simulation, i.e., the application is executed but part of the execution takes place within a simulation component. In Chapter 4 we present our of-line simulator based on SMPI backend. SMPI sim-ulations account for network contention in a fast and scalable manner. SMPI also implements an original and validated piece-wise linear model for data transfer times between cluster nodes. Finally SMPI simulations of large-scale applications on large-scale platforms can be executed on a single node thanks to techniques to reduce the simulation's compute time and memory footprint.

SimDag is designed for the investigation of scheduling heuristics for applications as task graphs. SimDag allows to prototype and simulate scheduling heuristics for applications structured as task graphs of (possibly parallel) tasks. With this API one can create tasks, add dependencies between tasks, retrieve information about the platform, schedule tasks for execution on particular resources, and compute the DAG execution time.

SURF considers the platform as a set of resources, with each of the simulated concurrent tasks utilizes some subset of these resources. SURF computes the fraction of power that each resource delivers to each task that uses it by solving a constrained maximization problem: allocate as much power as possible to all tasks in a way that maximizes the minimum power allocation over all tasks, also called Max-Min fairness. SURF provides a fast implementation of Max-Min fairness. Via Max-Min fairness, SURF enables fast and realistic simulation of resource sharing (e.g., TCP ŕows over multi-link LAN and WAN paths, processes on a CPU). Furthermore, it enables trace-based simulation of dynamic resource availability. Finally, simulated platform conőgurations are described in XML using a syntax that provides an uniőed abstract basis for all other components of the SIMGRID project (MSG and SMPI).

XBT is a łtoolboxž module used throughout the software, which is written in ANSI C for performance. It implements classical data containers, logging and exception mechanisms, and support for conőguration and portability. Now that the basic concepts of our work are analyzed, we can continue in the next chapter with the presentation of the time-independent trace acquisition framework.

Chapter 3

Time-Independent Trace Acquisition Framework

All the of-line MPI simulators that were reviewed in 2.3.3, rely on timed traces, i.e., each occuring event is associated to a time-stamp. The duration of each computation or communication operation is then deőned by the interval between two time-stamps. When it simulates an execution on a target platform that is diferent of the one used to get the trace, a simulator then has to apply a correction factor to these intervals. This implies to know precisely what are the respective characteristics of the host and target platforms. In other words, each execution trace must come with an accurate description of how it has been acquired. Finally, determining the right scaling factor can be tedious depending on the degree of similarity of both platforms.

In this chapter we introduce a new of-line simulation framework, that free ourselves of timestamps by relying on time-independent traces. For each event occurring during the execution of the traced application, e.g., a CPU burst or a communication operation, we log the volume of the operation (in number of instructions or bytes) instead of the time when it begins and ends. Indeed this type of information does not vary with the characteristics of the host platform. For instance, the size of the messages sent by an application is not likely to change according to the speciőcs of the network interconnect, while the computation amount performed within a for loop does not increase with the processing speed of a CPU. This claim is not valid for adaptive MPI applications that modify their execution path according to the execution platform. This type of applications, that represents only a small fraction of all MPI applications, is not covered by our work.

Another advantage of this approach is the lack of clock synchronization across all the participating nodes. This can be done because we do not need to extract the durations of the communications that occur during the execution of the parallel application. This is important as there can be many issues about clock synchronization [START_REF] Hoeŕer | Accurately Measuring Overhead, Communication Time and Progression of Blocking and Nonblocking Collective Operations at Massive Scale[END_REF] that are sometimes very diicult to identify.

A time-independent trace can been seen as a list of actions, e.g., computations and communications, performed by each process of an MPI application. An action is described by the id of the process that does this action, a type, e.g., a computation or a communication operation, a volume, of instructions or bytes, and some action speciőc parameters such as the id of the receiving process for a one-way communication.

Furthermore it is mandatory to know the sequence of the events, otherwise it is not pos-sible to create the list of the actions which constitutes the time-independent traces. The only instrumented mode that provides analytic measurement data, is the tracing one. Thus we need a proőling tool that provides tracing functionalities. The left hand side of Figure 3.1 shows a simple computation executed on a ring of four processes. Each process computes one million instructions and sends one million bytes to its neighbor. The right hand side of this őgure displays the corresponding time-independent trace. Note that, depending on the number of processes and the number of actions, it may be preferable to split the time-independent trace to obtain one őle per process. Indeed Figure 3.1 shows a simple example where all the actions can be included in the same őle. However, typical MPI applications are likely to be executed by dozen of processes that perform millions of actions each. Then it is often easier to split (or actually not merge as it will be explained later) the trace to have one őle per process, like in the Figure 3 In this section we mention the main steps of the acquisition process. As it is shown in the Figure 3.3, in the beginning it is mandatory to instrument an application in order to record all the events that will occur during its execution. Afterwards, we execute the instrumented application on a parallel platform. Then from the acquired traces, we extract the time-independent traces, which are gathered into a single node. In order to replay the time-independent traces, the following requirements should apply. For the computation actions, we know the amount of instructions, and the processing speed of the CPU, so we can determine the time to complete the computation. However, some algorithms should be implemented for the communication actions in order to calculate the time needed to transfer the message from the sender to the receiver in the case of a point-to-point communication and similar for other type of communications. As there are no time-stamps in the execution traces, we should take under consideration the latency and the bandwidth of the network. Furthermore it is really important to simulate also the contention that may occur during the exchange of the data between the nodes. Thus, if a simulation model can handle all the mentioned factors, then it can use the time-independent traces in order to predict the performance of the corresponding application.

The remaining of this Chapter is organized as follows. Section 3.1 describes the instrumentation of an application and evaluates some tracing tools. instrumentation methods. In Section 3.2, we evaluate the quality of diferent instrumentation methods in terms of overhead and skew. Section 3.3 details and evaluates the subsequent parts of the proposed trace acquisition framework. This presentation is illustrated by the deployment of our framework on the Grid'5000 platform. Finally, Section 3.4 concludes this chapter. Note that the replay of the time-independent traces will be covered in the next chapter.

Instrumenting an Application

Instrumenting an application to obtain an execution trace consists in adding probes to its code. For instance, such probes can be accesses to hardware counters or logs of the beginning and end of a function. Thanks to them, all the actions, i.e., computations or communications, can be traced in a chronological order. For every function enter/exit events are saved. The information which is logged for each event are the time-stamp, event type and event-related information such as the sender of a message, the receiver, etc. A crucial diference with other instrumentation modes such as proőling and statistical proőling, is that we know the chronologically ordered sequence of the events that occur during the execution.

The left-hand side of Figure 3.4 shows an example of what occurs during tracing. We have two processes, called A and B. The őrst one calls the function foo, sends a message to process B, and then exits. Similarly process B calls the function bar, receives a message from process A and exits. However, it is mandatory to monitor the time through a synchronization mechanism as we need to know when a communication starts and ends.

On the right-hand side of Figure 3.4, we can observe the sequence of events per process where the name of the functions and information on events are locally encoded. In the case of merged traces, we can observe the global sequence of events for both processes thanks to the recorded time-stamps and the synchronization. The uniőcation takes place to globally declare functions and other important information. ś For compute parts, the trace should contain the id of the process that executes the instructions and the corresponding amount; ś For point-to-point communications, it is mandatory to know both the sender and the receiver of the message, the type (MPI_Send, MPI_Recv, etc.) and the message size in bytes; ś For collective communications, it is important to know at least the size of the message and the type of the MPI communication (MPI_Broadcast, etc.). However, there are some MPI calls such as MPI_Allreduce, where the participating processes execute also some computation, summing values or determining a maximum for example. In this case, it is mandatory to log the number of executed instructions in order to simulate the compute part; ś For synchronization calls such as MPI_Barrier, it is mandatory to know the MPI Communicator. Currently our framework does not support all the MPI calls but the most common ones. Table 3.1 lists all the MPI functions for which there is a corresponding action implemented in our framework. For the collective operations, we consider that all the processes are involved as the MPI_Comm_split function is not implemented. When it is not possible to extract from the instrumented execution the information about the root process that initiates a collective operation, we assume that this process is the one of rank 0. Finally the init and finalize actions have to appear in the trace őle associated to each process to respectively create and destroy some internal data structures that will be needed during the replay of the traces.

Evaluation Criteria and Scoring Method

Many proőling tools can provide useful information about the behavior of parallel applications and record the events that occur during their execution. PAPI [START_REF] Browne | A Portable Programming Interface for Performance Evaluation on Modern Processors[END_REF] provides access to the hardware counters of a processor. In our prototype framework we measured the compute parts of an application in numbers of ŕoating point operations (or ŕops). However, using another counter, such as the number of instructions, has no impact on the instrumentation overhead as long as the chosen measure does not combine the values of several counters. To select the tool that corresponds the most to the requirements expressed by our time-independent traces replay framework, we conducted an evaluation based on the following criteria and scoring method:

Profiling Features

Many tools exist to proőle parallel applications, i.e., get an idea of the behavior of the application over its execution time. A classiőcation of these tools can be made following two axes. The őrst distinction depends on the type of output produced by the considered tool. It can be either a profile or a trace. A proőle gives a higher view of the behavior of an application as information is grouped according to a type of operation or to the call tree. A trace gives lower level information as every event is logged without any aggregation. The second way to classify tools depends on the kind of events they can be proőled or traced. Such events are mainly related to communication or computation. A third important parameter for this evaluation is the type of value associated to each logged event, e.g., volumes or timings. Finally, the instrumentation of an application is mandatory to obtain a proőle or a trace. Such a instrumentation can be applied to the entire application or to a speciőc block of code, e.g., , a particular function or a MPI call. In this evaluation we give a higher score to tools ofering an automatic instrumentation feature. Such a feature lighten the burden of getting a proőle from a user point of view.

With regard to the speciőc requirements of our time-independent trace replay framework, we adopt the following scoring scheme for the Profiling feature criterion: ś Tracing → 2 points ś Information on communication → 1 point ś Information on computation → 1 point ś Information on communication volumes (in bytes)

→ 1 point ś Information on computation volumes (in ŕops)

→ 1 point ś Automatic instrumentation of the complete application → 1 point ś Automatic instrumentation of a block of code → 1 point Each tool can then obtain a score ranging from 0 to 8, the higher being the better.

Quality of Output

Proőling tools usually output the results in őles. These őles could be of various formats such as plain text, XML, or binary formats. As mentioned earlier our objective is to convert such output őles into set of actions to be replayed by SimGrid. The readability of the output őles is then a very important requirement. However, tools that produce binary őles often come with an application or an API to extract the required information. Finally we aim at replaying executions that involve large numbers of processes. To ensure a good scalability, it is important that the trace of each process is stored in a separate őle. Indeed a tool enforcing a unique trace őle for the complete execution will have a poor scalability due to merging overhead. Moreover as we intend to read these traces and extract the time-independent ones, if there is at least one trace őle per node, then we can use the same number of nodes with a parallel application to achieve our purpose. This means that even for large trace sizes we would be able to use many processors and hard disks. So the conversion will be much faster than using just one node. Then we propose the following scoring scheme (ranging from 0 to 3) for the Output quality criterion:

ś Capacity to extract the required information

→ 1 point ś Direct extraction → 1 point ś One pass conversion → 1 point

Space and Time Overheads

As already mentioned, őles that contain all the relevant information are created during the tracing or proőling of an application. Proőling provides aggregated data about an application. This means for example that it records the number of times a function is called and its average duration. Conversely tracing records each call independently with the timestamp and some other information which depend on what the user wants to measure. The source of the time overhead for an instrumented application are the measurement of a PAPI counter on the processor, the instrumentation of the MPI communications, and writing traces on disks. In terms of space overhead, proőling obviously leads to smaller traces, as logged events are aggregated.

Then, for Space and Time overhead, we adopt the following scoring scheme: ś Overhead < 50% of the initial execution time → 2 points ś 50% < Overhead < 100% of the initial execution time → 1 point The executed time of the instrumented application includes the time needed to write the produced traces on disk. ś Linear increase of the overhead → 1 point ś Constant overhead → 2 points ś Linear decrease of the overhead → 3 points ś Linear increase of trace size with regard to problem size → 1 point ś Linear increase of trace size with regard to number of processes → 1 point ś Any special technique integrated in the tool to reduce the time overhead → 1 point Each tool can then obtain a score ranging from 0 to 8, the higher being the better.

Software Quality

Sometimes installing a proőling tool is not just a simple procedure such as executing the commands ./configure, make, and make install in a Linux environment. In some cases many ŕags should be added to install a tool, or dependencies on other tools should be taken under consideration. Moreover the tools that are released under open source license are preferred compared to the ones with any non open source license. Every tool should support a variety of hardware e.g., processors and software developed under various programming languages e.g., C/C++/Fortran or implementations of the Message Passing Interface e.g., Mpich, OpenMPI. A well written manual is also always helpful for both installing and using a tool. It also has to be up to date and inform the user about new features. Finally it is desirable that the tool is maintained in order to support all the new versions of MPI and PAPI. As result for the software quality criterion we adopt the following scoring scheme: ś Ease of installation → 1 point ś Software dependencies → 1 point ś License → 1 point ś Hardware compatibility → 1 point ś Support of C/C++/Fortran programming language, 1 point for each → 3 points ś Compatibility with the major MPI implementations, i.e., Mpich or OpenMPI → 1 point ś Documentation → 1 point ś The project is active → 1 point ś There is a support team for this tool → 1 point Each tool can then obtain a score ranging from 0 to 11, the higher being the better.

Evaluation of Tracing and Profiling Tools

Based on the aforementioned evaluation criteria, we studied in [START_REF] Desprez | Evaluation of Proőling Tools for the Acquisition of Time Independent Traces[END_REF] the following tools: PAPI [START_REF] Browne | A Portable Programming Interface for Performance Evaluation on Modern Processors[END_REF] which gives access to the performance counters, PerfBench [START_REF] Perfbench | [END_REF] which can instrument only compute parts, PerfSuite [START_REF] Kufrin | Perfsuite: An Accessible, Open Source Performance Analysis Environment for Linux[END_REF] that provides statistical proőling for the compute parts, MpiP [START_REF] Vetter | Statistical Scalability Analysis of Communication Operations in Distributed Applications[END_REF] which can apply statistical proőling for the MPI communication, MPE [START_REF] Chan | User's Guide for MPE: Extensions for MPI Programs[END_REF][START_REF] Chan | An Eicient Format for Nearly Constant-Time Access to Arbitrary Time Intervals in Large Trace Files[END_REF] that instruments MPI communication operations, IPM [START_REF] Wright | Measuring and understanding variation in benchmark performance[END_REF] which supports proőling for MPI communication and compute parts. The other tools provide both proőling for communication and compute parts: Extrae [START_REF] Extrae | [END_REF], Scalasca [START_REF] Geimer | A Scalable Tool Architecture for Diagnosing Wait States in Massively Parallel Applications[END_REF], TAU [START_REF] Shende | The Tau Parallel Performance System[END_REF], VampirTrace [START_REF] Knüpfer | The Vampir Performance Analysis Tool-Set[END_REF][START_REF] Müller | Developing scalable applications with vampir[END_REF], Score-P [START_REF] Dieter An Mey | Score-PśA uniőed performance measurement system for petascale applications[END_REF], and our contribution, called Minimal Instrumentation. In this section, we only include the evaluations of a selected subset of tools that are representative.

PAPI

The Performance Application Programming Interface (PAPI) is a tool developed at the University of Tennessee, Knoxville [START_REF] Browne | A Portable Programming Interface for Performance Evaluation on Modern Processors[END_REF]. We based our evaluation on the version 3.7.0 while the last one is version 5.1.0. The diferences with the last version are the support of multiple components, or counting domains, the possibility of developing new components and the support of more platforms. These recent additions do not impact our evaluation. PAPI relies on the hardware performance counters that are available on most processors. It provides the connection between software and hardware performance counters.

Properties of a subset of the events are presented in Listing 3.1. First the name of each hardware counter is given along with its internal code. The Avail column declares if the event is available and the Deriv column shows if this PAPI counter uses two or more counters to produce a value or there is a hardware counter that provides this information directly. Finally, the last line presents how many counters are available for the used processor. So by using this metric, it is possible to create traces with the exact amount of executed ŕops.

--------------------------------------------------------------------- Of 103 p o
Profiling features With regard to the profiling features evaluation criterion, PAPI obtains a score of 4 points. Indeed, PAPI ofers tracing facilities (2 points), that allows us to obtain information about the computation (1 point) and especially about volume for each computation event (1 point). However, PAPI does not provide any mechanism to trace communication events and there is no way to trace an application automatically using only PAPI. Nevertheless it is possible to instrument an application manually.

Listing 3.2 presents an example of how to measure the number of ŕops computed by a block of code. In order to trace a block of code, some commands should be inserted at the beginning and the end of it. If we want to measure the amount of executed ŕops for the function ssor(itmax) in the LU benchmark, the commands PAPIF_start and PAPIF_stop should be inserted as shown in Listing 3.2.

Lines 0-1 declare the events array in which are saved the codes of the events to be measured. The variable numevents declares the number of events that PAPI should monitor and the variable check is used for checking the status of the commands. Furthermore the EventSet is the set with all events that are going to be used. The values from the counters are saved in the array Values. Line 2 declares two strings for printing the number of ŕops and the rank of the process. Line 3 declares the number of events that are going to be monitored. Line 4 sets EventSet to PAPI_NULL on the next line, the event PAPI_FP_OPS is saved to the events array. The variable check on the line 6 is always equal to the code of the current PAPI's version. Between the lines 7 and 12 the following commands are executed: the initialization of PAPI, the creation of the null set, the event is added to the null set, the measurement starts, the ssor function is called, and the measurement stops respectively. Finally from lines 13 to 16 the value of the counter is saved to the string ch, the id which is the rank of the process is saved to the string ch2 and Listing 3.2: Example of measuring the ŕops for the ssor iteration. integer e v e n t s ( 1 ) , numevents , check , EventSet integer Values ( 1 ) character ( 1 5 ) ch , ch2 numevents=1 EventSet = PAPI_NULL e v e n t s ( 1 ) = PAPI_FP_OPS check = PAPI_VER_CURRENT c a l l P A P I f _ l i b r a r y _ i n i t ( check ) c a l l PAPIF_create_eventset ( EventSet , check ) c a l l PAPIF_add_event ( EventSet , e v e n t s ( 1 ) , check )

c a l l PAPIF_start ( EventSet , check ) c a l l s s o r ( itmax ) c a l l PAPIF_stop ( EventSet , Values , check ) write ( ch , ' ( i 1 0 ) ' ) Values ( 1 ) write ( ch2 , ' ( i 6 ) ' ) i d write ( * , 1 0 0 ) t r i m ( ch2 ) , ' ␣ compute ␣ ' , t r i m ( ch ) 100 format (A, A9 ,A)
with the last two lines the number of the ŕops and the rank are printed with the format łrank compute valuež which is the format of time-independent traces.

Moreover each process saves its own trace to a separate őle so if the application is executed on N processes, then there are N trace őles.

Quality of output About the quality of output evaluation criterion, PAPI obtains a score of 3 points. PAPI allows for the extraction of information on computations (1 point). By using appropriate commands such as those in Listing 3.2 it is possible to print the number of ŕops according to the time-independent trace format (1 point). As result there is no need for any conversion (1 point).

Example of traces for the LU benchmark Table 3.2 presents the őrst four lines of the traces of the LU benchmark, class C, executed on 4 nodes. The benchmark was traced with PAPI, hence there is no info about the communication. After each MPI call we start measuring the executed ŕops and stop just before the next MPI call, where we save the corresponding action into our traces.

Space and time overhead Thanks to papi_cost, it is possible to compute the minimal, maximal, mean and the standard deviation of the execution time of basic PAPI operations, e.g., start/pairs and reads. The results are presented in Table 3.3. More details are given in [START_REF] Desprez | Evaluation of Proőling Tools for the Acquisition of Time Independent Traces[END_REF].

With regard to the space and time overheads, PAPI obtains the score of 6 points. In Table 3.4, we see that the time overhead is less than 50% for the LU benchmark class C (2 points). While slightly increasing, the time overhead remains in the 5-7% range, then we consider it as constant (2 points).

In Table 3.5 we can observe that when the number of the nodes is doubled then the size of the traces is almost two times bigger. We can thus claim that the increase is linear (1 point). Moreover with 32 nodes, the diference of the trace sizes from class A to C is of 25 MB per class, so the trace size increases linearly with the problem size, except for class D. Compared to the Software quality Considering the software quality, PAPI obtains the score of 11 points. The installation of the PAPI is easy without any problem but there are some restrictions by the software dependencies (1 point). PAPI depends on linux performance counters driver (perfctr) [START_REF] Pettersson | Perfctr: the Linux Performance Monitoring Counters Driver[END_REF] or performance monitoring interface (perfmon2) [START_REF]Perfmon2[END_REF]. For the kernels older than 2.6.30 it is needed to patch the kernel, otherwise there is at least support for perfmon2. In the case that a patch is needed, the conőguration of the kernel has to be changed. The monitoring counters should be enabled through the make oldconfig command and afterwards to build and install the modiőed kernel (1 point). Moreover PAPI is released under the New BSD license template which is a GPL-compatible software license (1 point). PAPI is the standard tool to access the hardware counters of the CPU and it is compatible with the major platforms as shown in Table 3.6 (1 point). Furthermore PAPI supports the C/C++ and Fortran programming languages (3 points). About the documentation, the installation process is well documented on the oicial web page (1 point), the usage of PAPI is well explained through the PAPI references, the Presentations and the Doxygen docs that are available under the Documentation menu of the oicial web page (1 point). Finally the project is active, patches are released often (1 point) and there is a support team answering any question (1 point).

Hardware

Scalasca

Scalasca [START_REF] Geimer | A Scalable Tool Architecture for Diagnosing Wait States in Massively Parallel Applications[END_REF][START_REF]Scalasca[END_REF] is an open-source toolset that can proőle and trace an application. It is developed by the Forschungszentrum Jülich, Jülich Supercomputing Centre and the German Research School for Simulation Sciences, Laboratory for Parallel Programming. We based our evaluation on version 1.3.3 while the latest is version 1.4.3. When the execution of an instrumented application ends, a parallel automatic event trace analysis tool called SCOUT is executed. This tool identiőes and reports any logical clock violations. Since the version 1.3.3, a new environment variable is introduced that disables the execution of this tool as it does not inŕuence the creation of the traces. The Program Database Toolkit (PDToolkit) ( [START_REF]Tau reference guide, chapter tau instrumentaton options[END_REF], [START_REF]Tau user guide, chapter selectively proőling an application[END_REF]) is a framework for analyzing source code written in several programming languages and for making rich program knowledge accessible to developers of static and dynamic analysis tools. This framework is partially supported by Scalasca.

Profiling features Regarding the profiling features, Scalasca obtains a score of 6 points. This tool can trace an application (2 points), but it is not possible to trace the size of the message for a MPI_Recv call. Thus it can not extract from the trace őles all the required data related to communication (0 point). All the required data about computation (1 point), the volumes in bytes (1 point) and the volumes in ŕops (1 point) are respectively recorded into the trace őles. Finally, Scalasca can automatically trace an application (1 point).

Quality of output Scalasca provides the PEARL API [START_REF] Geimer | A parallel trace-data interface for scalable performance analysis[END_REF] to create a C++/MPI tool to extract the required data from the traces (1 point). Thanks to the format of the trace őles, it is possible to convert them in one pass (1 point).

Space and time overhead Considering the space and time overhead, Scalasca obtains a score of 8 points. According to Table 3.8, the time overhead stays under 50% (2 points). Moreover, we see that it linearly decreases as the number of participating processes increases (3 points). As we execute the benchmark with one process per node, there is always one disk per process onto which ŕush the traces. The size of the trace produced by a single process decreases as the total number of processes grows, hence the reduction of the overhead. In terms of space overhead, the evolution of the trace size is correlated to that of the size of the instance (1 point). Class D is much bigger than the other instances (larger matrices and more iterations). This bigger gap is also observed in the size of the traces. From class A to class C, size grows by a factor of 2.3 and 2.6, while from class C to class D, the trace grows by a factor of 4.7. When the number of processes is increased for a given class, we observe a linear increase of the trace size (1 point). However, a large part of the trace size comes from the tracing of a function that does not depend on the number of processes and is not relevant for our studies. Scalasca allows the user to declare that some functions do not have to be traced, which allows for a reduction the space overhead (1 point).

LU benchmark

Software quality Although some ŕags have to be set to install the tool, the installation was easy ( Profiling features Regarding the profiling features, TAU obtains a score of 8 points. TAU can trace an application (2 points), and logs data related to the computation (1 point) and the communication (1 point) into trace őles. Moreover the volumes of the communication and computation are in bytes (1 point) and ŕops (1 point) respectively. TAU supports the PDToolkit framework so it provides the user with a method to trace all the application (1 point) or only a block of code (1 point).

Quality of output

The binary trace őles produced by TAU contain all the required data for the simulation. It is possible to extract them with the help of the TAU trace format reader library [START_REF]TAU User Guide, chapter Tracing, TAU Trace Format Reader Library[END_REF] (1 point). We used the API to implement a tool that converts TAU traces into time-independent traces in one pass (1 point).

Space and time overhead

The time overhead of TAU is given in Table 3.12. It is under 50% of the execution time of the application (1 point) but does not decrease as the number of processes grows. In terms of space overhead, the size of the traces increases linearly along with both the number of processes (1 point) and the problem size (1 point), as shown by Table 3.13. Finally, TAU provides a way to declare that some functions are not to be traced in order to decrease the time and space overheads (

Score-P

Score-P [START_REF] Dieter An Mey | Score-PśA uniőed performance measurement system for petascale applications[END_REF]95] has been developed by the German BMBF project SILC and the US DOE project PRIMA. It is a highly scalable tool suite for proőling, tracing, and the online analysis of HPC applications. The evaluated version is the 1.0-beta while the latest one is 1.1.1 that corrects some bugs not related with our usage. This tool is the result of the collaboration between the researchers involved in the development of many well known tools such as TAU, Scalasca and VampirTrace.

Profiling features With regard to profiling features criterion, Score-P achieves the score of 7 points. It can trace an application (2 points) and record all the computation (1 point) and communication events (1 point) with their volumes in ŕops by using PAPI (1 point) and bytes (1 point) respectively. It can automatically instrument an application (1 point).

Quality of output

The Score-P tool achieves the score of 2 points for the criterion of quality of output. The format of the generated traces is the Open Trace Format Version 2 (OTF2) [START_REF] Eschweiler | Open trace format 2 -the next generation of scalable trace formats and support libraries[END_REF] which is a highly scalable, memory eicient event trace data format and will become the new standard trace format for TAU, Vampir and Scalasca. It is the common successor format for the Open Trace Format (OTF) and the Epilog trace format [START_REF] Wolf | EPILOG binary trace-data format[END_REF]. When the execution ends, the traces comprise the computation and the communication events with all the necessary data (1 point). From the OTF2 őles it is possible to acquire the time-independent traces by using the OTF2 API and only one pass (1 point). According to Table 3.17 the increase of the number of the processes causes a linear increase of the size of the traces (1 point). Similarly, when the size of the problem increases, then the size of the traces increases also linearly (1 point). With the combination of PDT and the Score-P user API, code regions can be excluded from the instrumentation (1 point). 3.17: Space overhead of Score-P for the LU benchmark.

Space and time overhead

Software quality Score-P achieves the score of 11 points regarding the software quality criterion. There is no issue about the installation (1 point) and no dependency on other libraries (1 point). It is available in Open Source under a BSD license (1 point). The tool is compatible with various hardware and is supported on many platforms (1 point) as it can be seen in Table 3.18.

It is compatible with the C/C++ and Fortran programming languages (3 points) and with the major MPI implementations (1 point). There is a manual which describes many diferent aspects of what this tool can do, how to install it and how to use it (1 point). This is a new project which aims at providing the best characteristics of some well known tools (1 point) and there is a support team for solving any problem (1 point). We aggregate the results of the evaluation in Table 3

Minimal Instrumentation (MinI)

There are two undesirable side efects caused by complex proőling tools. First, they may induce a large time overhead. Second, the measure of hardware counters may be skewed, as the ŕops caused by the tool itself are also measured. Unnecessary instrumentation, in our case instrumentation that generates trace data beyond the information strictly needed for our replay framework, would then unnecessarily increase overhead and skew. In order to control the instrumentation at a lower level, we implemented our own instrumentation method, called MinI. The MPI standard exposes two interfaces for each MPI function, one preőxed with MPI_ and the other preőxed with PMPI_, the former calling the latter directly. This provides developers with the opportunity to insert their own code, e.g. for proőling purposes, in the implementation of all MPI_ functions. This mechanism is used by several of the aforementioned tools, and we ourselves use it to insert code that is executed upon entry and exit for all MPI calls. This code retrieves hardware counters through PAPI, and generates event traces such as those in Figure 3.1. This approach is guaranteed to perform the minimal amount of instrumentation needed for our purpose.

According to both MPICH and OpenMPI implementations, the Fortran PMPI layer calls C PMPI either directly or through C MPI layer. Thus we just have to provide proőling wrappers in C to trace an application. Furthermore, to decrease the I/O overhead, we implement a simple bufering mechanism. We can declare how many events are saved in the memory before ŕushing them to the hard disk. Listing 3.3 presents the instrumentation of the MPI_Send call, with this minimal instrumentation. The general concept is that when there is an MPI_Send call, we create a compute action with the amount of ŕops computed since the last MPI call. Then, PMPI_Send is called, and the corresponding send action is created, saved in the bufer and it starts measuring again the ŕops. We use the PAPI_accum_counters command which measures the corresponding PAPI metric since the beginning of the execution and increases monotonically. i n t MPI_Send ( buf , count , datatype , d e s t , tag , comm ) { . . . i f ( PAPI_accum_counters ( v a l u e s , 1 ) !=PAPI_OK) { p r i n t f ( "PAPI d oe s not s u p p o r t t h i s m e t r i c \n " ) ; } c o u n t e r 2=v a l u e s [ 0 ] ; MPI_Type_get_name ( datatype , t_data ,&np ) ; t h i s _ t y p e=encode_datatype(&t_data ) ; PMPI_Comm_rank( MPI_COMM_WORLD, &l l r a n k ) ; s p r i n t f ( msg,"%d compute %l l d \n " , l l r a n k , c o u n t e r s 2 -c o u n t e r 1 ) ; s t r c a t ( longmsg , msg ) ; r e t u r n V a l=PMPI_Send( buf , count , datatype , d e s t , tag , comm ) ; i f ( t h i s _ t y p e ==0) s p r i n t f ( msg , "%d send %d %d\n " , l l r a n k , d e s t , count ) ; e l s e s p r i n t f ( msg , "%d send %d %d %d\n " , l l r a n k , d e s t , count , t h i s _ t y p e ) ; s t r c a t ( longmsg , msg ) ; i f ( PAPI_accum_counters ( v a l u e s , 1 ) !=PAPI_OK) { p r i n t f ( "PAPI d oe s not s u p p o r t t h i s m e t r i c \n " ) ; } c o u n t e r 1=v a l u e s [ 0 ] ; . . . } Profiling features With regard to the profiling features evaluation criterion, the minimal instrumentation tool, obtains a score of 7 points. This tool can trace an application (2 points) and record the communication (1 point) and computation information (1 point) with the corresponding data in bytes (1 point) and ŕops (1 point). Moreover it can instrument automatically an application (1 point), but all the application has to be traced.

Quality of output

Regarding the quality of output, it achieves a score of 3 points. This tool can record all the required information (1 point), it saves directly the measured data into time-independent traces (1 point), thus there is no need to read the traces at all (1 point).

Space and time overhead About the space and time overheads evaluation criterion, our minimal instrumentation obtains a score of 6 points. The time overhead in Table 3.20 is around 4-5% in all the cases, then smaller than 50% (2 points) and constant (2 points). The trace sizes are given in Table 3

Final Scores and Discussion

The őnal score for all the tools is presented in Table 3 First, we recall the evaluation criteria we used are driven by the requirements of our framework. Then, it is not an exhaustive evaluation of all the features of each tool. About the score, PAPI achieves a high score. However, it only provides information about computation with manual instrumentation. Then, Extrae needs a lot of time to convert the trace őles into Paraver őles and depending on the application, traces can be large. As the conversion to time-independent traces should be done by a serial application, the demanded time could be signiőcant with regard to the execution of an application. Reading the provided OTF őles of VampirTrace instrumentation, requires to merge them, so a global őle system is demanded, or at least to gather all the traces into a single node. This is a procedure that we want to avoid because the global őle system is not supported by default by all our clusters and the gathering of the traces would consume a lot of time. Although Scalasca is an eicient tool, it does not comply with all the necessary requirements expressed by our framework. TAU, is one of the tools that provide all the features and it is eicient enough according to our requirements. However, there are some cases which are going to be described later, where it demands a lot of memory in comparison with other tools. One of the newest tools, named Score-P, seems to be promising. It provides all the required information and with the OTF2 API it is possible to extract time-independent traces without the need for a global őle system. The MinI tool succeeded to most of our tests. It has been developed to fulőll our framework requirements. It provides the time-independent traces directly after the application's execution, just by compiling MPI applications against our tool with less overhead than any other tool. The TAU, Score-P, and MinI can be used for our framework but with some restrictions. For example if we want to create an action corresponding to communication such as MPI_Alltoallv, then we need to know some speciőc information about the MPI call that only MinI provides directly.

While MinI does not achieve the highest score, it is the most eicient with regard to our framework requirements. It leads to smaller time and space overhead than other tools. Furthermore it creates the time-independent traces directly during the execution of the application, thus it needs less space to save trace őles on hard disks. The instrumentation skew is also smaller than other tools, so the traces represent accurately the performance of an application. Another advantage is its lack of dependencies and it is easy to use by linking MinI to the desired application. For our prototype we used the TAU tool, as Score-P was not mature at that time. However, the need for an even more eicient proőling tool, led us to develop MinI.

Evaluation of Instrumentation Methods

In our prototype framework it was necessary to validate our methodology on various benchmarks. The benchmarks are constituted by computation and/or communications parts and declarations of variables and initialization/őnalization phases. To validate our framework, specially as the simulation did not take memory footprint under consideration, we had to acquire the time-independent traces for speciőc parts of applications. The usual approach is called selective instrumentation. There is another reason to apply selective instrumentation. Some applications can be constituted by large number of calls to a function which does only compute and total duration whose is not signiőcant in comparison to application's execution time. Such functions can create both time and space overhead during the instrumentation of an application. We őgured out another method to decrease such time and space overhead. The main idea came out from the structure of the time-independent traces as there is no need to know when a non MPI function is called. From the computation point of view we only need to know the total amount of instructions between two successive MPI calls. We combine TAU with PDToolkit to instrument only MPI calls, leading to a more eicient instrumentation called łTAU-reducedž. However, when we tried to test the scaling capabilities of our framework by using hundreds of nodes, TAU demands a lot of memory. This occurs because TAU provides more complex proőling features than the ones that are required by our framework. To address this issue we developed the minimal instrumentation MinI which instruments only the MPI calls of an application and saves the logged events into time-independent traces directly. This tool is the most eicient with regard to our framework requirements and requires less memory than other tools. In the next section we detail the "Selective" and "Tau-Reduced" instrumentation methods+

Selective Instrumentation

An interesting feature provided by TAU, is selective instrumentation. It can be done in diferent ways. One consists in listing in a separate őle which functions have (or have not) to be traced. All the functions in the call path of the listed functions will also be traced. However, this technique may not be enough to isolate a given call, e.g., if a function is called twice but only one call has to be traced. A solution is then to insert two macros provided by the TAU API, namely TAU_ENABLE_INSTRUMENTATION and TAU_DISABLE_INSTRUMENTATION in the source code.

The following example illustrates the instrumentation of the SSOR(itmax) function call in a LU factorization. One additional call to each of these macros is required to deőne neat disable/enable sections. Such slight modiőcations of the source code can be handled by the pre-processor. Indeed the initial program has to be compiled using one of the scripts provided by TAU, i.e., tau_cc.sh and tau_f77.sh for C and Fortran codes respectively.

TAU-reduced

While selective instrumentation logs only the events of speciőc parts of an application, it still includes time overhead to instrument all the enter/exit events of a function that is called many times. For instance, this overhead may come from the instrumentation of functions that do not include MPI calls and are located within loops. While this information may be useful to users aiming at identifying performance bottlenecks in their application, it is useless to our speciőc usage of the produced traces.

However, the selective instrumentation feature provided by TAU gives us a way to obtain all this required information, and only it. We modiőed our instrumentation method as follows. First we create a őle, named exclude.pdt, in which we indicate to TAU the list of source őles that have to be excluded from the detailed instrumentation. Actually, we exclude all the source őles using the special character '*'.

BEGIN_FILE_EXCLUDE_LIST * END_FILE_EXCLUDE_LIST

Then, we add the following option to the command line to take this exclusion őle into account.

-optTauSelectFile=/path/exclude.pdt Thanks to this straightforward modiőcation, the instrumentation is łreducedž with regard to our speciőc needs. Indeed the performance hardware counter that measures the number of executed instructions will be triggered only when entering and exiting MPI functions. All the information related to MPI calls, i.e., id of the process that calls this function and the function name and calling parameters, are traced exactly as in the previous implementation.

We expect this simple modiőcation to have an impact on both the execution time overhead and the skew of measured numbers of instructions between non-instrumented and instrumented versions of an application. This instrumentation method is called łTAU-reducedž.

Evaluation of the instrumentation methods

We execute four diferent versions of the LU factorization from the NPB suite, all compiled with the highest level of compiler optimization. The őrst version is the original benchmark augmented with two calls to PAPI inserted at the beginning and the end of the LU computation to measure the total number of executed instructions. Since the overhead and skew due to these two calls are negligible, we call this version łoriginalž. The second version is called łTAU-fullž and corresponds to the benchmark instrumented using TAU with default conőguration settings. The third version is called łTAU-reducedž and corresponds to the benchmark instrumented using TAU but enabling instrumentation exclusion to reduce overhead and skew. The fourth version is called łminimalž and corresponds to the benchmark instrumented using the MinI tool. We execute all versions on the same cluster, called graphene, that comprises 144 2.53GHz Quad-Core Intel Xeon x3440 nodes. Each core has a L2 cache of 2 MB. The nodes are spread across four cabinets, and interconnected by a hierarchy of 10 Gigabit Ethernet switches.

We compute the instrumentation overhead as the percentage diference in execution time between an instrumented version and the original version. For each MPI process, we compute the instrumentation skew as the percentage diference in total number of instructions between an instrumented and the original application. For the instrumented application this number is computed as the average of the numbers of instructions for all the CPU bursts.

Figure 3.5 shows the skew for various instances of the LU benchmark. Each data point is obtained as an average over ten executions and aggregates the skews measured on all the processes. As expected, the TAU-full instrumentation method leads the highest skew as it is the most intrusive methods. The induced skew ranges from 3.66% to 21.62%. As the number of instructions is a fundamental component in our replay framework, the higher the skew, the less accurate the simulations will be. In other words, our framework will simulate the instrumented application rather than the original application. The TAU-reduced and Minimal instrumentation methods greatly reduce the skew (on average by a factor of 3.69 and 8.97, respectively). The lowest skew is achieved by the Minimal instrumentation method. It is always under 5% and in most of the cases under 2%. The highest skew caused by the Minimal instrumentation method (4.76%) is obtained for the B-128 instance. In this particular case a relatively small input data is distributed among 128 processes, so that each process holds only less than a hundred kilobytes of data. As a result each process performs a small volume of computation and the instrumentation instructions represents a non-negligible fraction of the executed instructions. Figure 3.6 shows the overhead in terms of execution time induced by the TAU-reduced and Minimal instrumentation methods for various instances of the LU benchmark. The TAU-Full instrumentation method is not displayed here, as its high skew discards it as a valid choice for our of-line simulation framework. As for the skew, we see that the Minimal instrumentation we implemented reduces the overhead (on average by a factor of 1.6) with regard to the TAUreduced method. While this őgure indicates that the overhead can become large (up to 23.5% for the B-128 instance), in general it remains low. Indeed, the overhead induced by the Minimal instrumentation method ranges from 1.55 to 2.01 seconds for class B instances and from 0.8 to 2.6 seconds for class C instances. But as the original execution time of the application greatly decreases as more processes are used, the relative overhead increases. Since large number of processes are generally used to solve only large problem instances, unlike the class B LU benchmark, we conclude that the instrumentation overhead is well within acceptable limits.

Acquisition of Time-Independent Traces

When an application is instrumented then a procedure should be followed for the acquisition of the time-independent traces. As mentioned in Figure 3.3, the instrumented application is executed, afterwards the action lists is extracted from the instrumentation traces if necessary, and őnally the time-independent traces are gathered into a single node.

Execution

There are only two requirements for obtaining a valid time-independent trace in a view to simulate an MPI application with n processes on an arbitrary platform: (i) the instrumented application must be executed with n processes; and (ii) each process must őt in main memory. This is in sharp contrast with time-dependent traces, which must be obtained on homogeneous platforms with as many compute nodes as that in the simulated platform. In particular, our method makes it possible to execute the instrumented application in four ways: Regular mode: execution on a single homogeneous cluster with one MPI process per processor. This is the way in which of-line simulators obtain time-stamped traces. This mode requires as many processors as that in the platform to be simulated, which limits its scalability. All three modes hereafter are only applicable to time-independent traces. Folded mode: execution on a single homogeneous cluster with more than one MPI process per processor. This allows for the acquisition of traces for larger instances of the application than can be executed in regular mode on the same cluster. The folding factor is only limited by the available amount of memory on the processors.

Composite mode: execution on heterogeneous or multiple non-identical clusters. In this mode, the user can aggregate disparate processors together, such as those in multiple homogeneous clusters, so as to augment the scale of the trace without requiring a single (large) homogeneous cluster. The only constraint is to select processors of a same family to prevent inconsistencies in the execution. Composite and folded mode: a combination of folded and composite mode. This mode further increases the scalability of trace acquisition by executing multiple MPI processes per processor in a non-homogeneous platform.

Using the Grid'5000 Platform to Acquire Time-Independent Traces

Building an Appliance Several base system images are made available by the Grid'5000 technical staf. Most of the images are based on the Debian Linux distribution and can be deployed on all Grid'5000 sites. There exist images based on three diferent versions of the Debian distribution, but one of them is aging (Lenny), the Squeeze is the one used for our experiments and the Wheezy image is the latest Debian release at the time of writing.

ś squeeze-x64-base is a minimal environment with no support of NFS and LDAP services.

Only the drivers necessary to the support of the Grid'5000 infrastructure and high-speed network interconnect are installed. ś squeeze-x64-nfs is based on squeeze-x64-base and enables the LDAP and NFS services. ś squeeze-x64-big is based on squeeze-x64-nfs and includes various pre-installed packages such as cmake, gfortran, OpenMPI, taktuk [START_REF] Claudel | Taktuk, adaptive deployment of remote executions[END_REF], as well as several packages for development, system tools, and editors. All these tools provide a stable platform for conőguring the operating system and execute various experiments. In [START_REF] Markomanolis | Time-Independent Trace Acquisition Framework ś A Grid'5000 How-to[END_REF] are presented all the procedures to build an image that could be used to acquire time-independent traces. Initially we describe how to deploy an image on Grid'5000. In the case where the kernel is earlier than version 2.6.31, we provide instructions to patch the kernel to enable access to the hardware counters of the processor. Then we detail all the steps to install the tracing tools, instrument and compile an application. Moreover the tools for trace post-processing should be installed on the deployed image. It is needed to save the image for future deployment and set the appropriate environment variables for TAU. Finally, we give all the commands to execute an instrumented application and acquire the time-independent traces for all the available execution modes.

Trace Extract Tools

One of the tasks that may be needed after the execution of an instrumented application, is the conversion of the instrumented traces into time-independent ones. This is necessary only if the MinI tool is not used, otherwise the time-independent traces are created automatically. We are going to describe the tools that convert instrumentation traces into time-independent ones by presenting how they handle some of the MPI calls.

TAU

When the execution of a program instrumented with TAU completes, many őles are produced. They fall in two categories: trace őles and event őles. The generated trace őles are named:

tautrace.<node>.<context>.<thread>.trc, where <node> is the rank of the MPI process whose execution is logged in the őle. The two other őelds, i.e., <context> and <thread>, are only used for multi-threaded applications. In this case, TAU distinguishes each thread and groups the threads according to the virtual address space they share. A trace file is a binary őle that includes all the events that occur during the execution of the application for a given process. For each event, this őle indicates when this event (e.g., a function call or an instrumented block) starts and őnishes. The time spent and the number of computed instructions between these begin/end tags are also stored. For MPI events all the parameters of the MPI call, including source, destination, and message size, are stored.

To reduce the size of the trace őles, TAU stores a unique id for each distinct traced event instead of its complete signature. The matching between the ids and the functions descriptions can be found in the event files. These őles are named: events.<node>.edf. There is only one event őle per MPI process. Each event őle contains information about each traced function. For any function, an event őle stores its numerical id, the group it belongs to, e.g., MPI for all MPI functions, a tag to distinguish TAU events from those deőned by the user, and the name type which is the actual name of the traced function. Some extra parameters required by TAU can also be stored into an event őle. For instance, the keyword EntryExit is used to declare a function that occurs between two separate events, i.e., entry and exit. Conversely the TriggerValue keyword typically corresponds to a counter that increases monotonically from the beginning of the execution. Such a trigger has to be activated twice to determine the evolution of the counter value during the corresponding period of time.

Figure 3.7 presents some entries of an event őle generated by TAU that corresponds to some MPI functions. An entry corresponding to the access to a hardware counter that measures the number of instructions, some user events related to the size of the messages for some MPI communications as it is mentioned by their names.

4 MPI 0 "MPI_Init() " EntryExit 19 MPI 0 "MPI_Send() " EntryExit 21 MPI 0 "MPI_Irecv() " EntryExit 22 MPI 0 "MPI_Wait() " EntryExit 26 MPI 0 "MPI_Allreduce() " EntryExit 28 MPI 0 "MPI_Barrier() " EntryExit 30 MPI 0 "MPI_Finalize() " EntryExit 1 TAUEVENT 1 "PAPI_TOT_INS" TriggerValue DefUserEvent event id 8 user event name "Message size sent to all nodes", monotonically increasing = 0 DefUserEvent event id 11 user event name "Message size for broadcast", monotonically increasing = 0 DefUserEvent event id 27 user event name "Message size for all-reduce", monotonically increasing = 0 DefUserEvent event id 9 user event name "Message size for all-to-all", monotonically increasing = 0 As the trace őles generated by TAU are binary őles, there is a need for an interface to extract information. Such an API is provided by the TAU Trace Format Reader (TFR) library [START_REF]TAU User Guide, chapter Tracing, TAU Trace Format Reader Library[END_REF]. This tool provides the necessary functions to handle a trace őle, including a function to read events. It also deőnes a set of eleven callback methods, that correspond to the diferent types of events that appear in a TAU trace őle. For instance there are callbacks for entering or exiting a function and triggering a counter. The implementation of these callback methods is let to the charge of the developer.

We thus developed a C/MPI parallel application, that implements the diferent callback methods of the TFR library. This program basically opens, in parallel, all the TAU trace őles and read them line by line. For each event, the corresponding callback function is called. To illustrate how this tool extracts the necessary data to produce a time-independent trace, we detail the case of some calls to MPI functions. Figure 3.8 presents the parameters of the diferent callbacks related to the MPI_Send function call on process 1 in a readable format. Each line starts by the process id, the thread id, the time (in ms) at which the event occurred and the name of the event. The remaining őelds are event dependent. As mentioned earlier, the event that corresponds to a MPI_Send is tagged as EntryExit in the event őle with the event id 19. The őrst occurring callback will then be on the EnterState event (line 1). The matching LeaveState event (line 5) deőnes the scope of events related to the function call. There are more four events, two of them (lines 2 and 6) correspond to the hardware counter measuring the number of instructions, as identiőed in the event őle. These two events are used to respectively end the CPU burst preceding the MPI call and starts the next one. The number of instructions computed within an MPI call, mainly due to bufer allocation costs, are ignored as they are accounted for by the network model. The last two events are related to the sent message. The EventTrigger on line 3 only provides the size of the message (8 bytes), which is not enough to build an entry in the time-independent trace. The SendMessage event (line 4) gives more information, namely the process and thread ids of the receiver, the size of the message, and the MPI tag and communicator for this communication.

Note that for asynchronous and collective communications, the extraction process is more complex. For instance, the mandatory information to write the entry corresponding to a MPI_Irecv, e.g., the receiver id, are given by a RecvMessage event which generally occurs within the MPI_wait function. This implies to implement some lookup techniques to retrieve all the necessary parameters. Figure 3.9 presents the parameters of the diferent callbacks related to the MPI_Irecv and MPI_Wait functions calls on process 1 in a readable format. TFR provides a method to seek the current position during the reading of the traces to a speciőc event. Thus during the call to the MPI_Irecv function, the position of the next event is saved. When the tool reads the call to the MPI_Wait function it creates the corresponding time-independent actions and it moves back to the position of the saved event to continue reading the trace.

Similarly, the callbacks for the MPI_Bcast function are presented in Figure 3.10 with its corresponding time-independent trace. The diference is that the line 3 calls the EventTrigger with id 11 which declares the size of the message for broadcast procedure (4 bytes).

The MPI_Allreduce function is presented in Figure 3.11. On line 3 there is a call to EventTrigger with id 27 which declares the size of the message for all-reduce procedure (40 bytes). Moreover in the time-independent trace we declare the amount of executed instructions to complete the reduction operation (600,124 instructions). The action comm_size declares the total number of processes that participate to this collective communication (4 processes in this case). However, this callback mechanism is not always suicient. For instance, as shown by Figure 3.12, the information extracted from the textttMPI_Alltoallv function only gives the total number of bytes exchanged during the execution of this function and not the size of each exchanged message.

We do not know the values of the displacements of the array that are given as input during the call to the MPI_Alltoallv function. Also the value 4196661 corresponds to the sum of the elements that the process exchanges with other participating processes.

Score-P

Similarly, after the execution of an instrumented program with Score-P, many őles are produced. Initially, there is the anchor őle named <archive_name>.otf2 which contains meta data related to the archive organization, declaring where are stored the other őles. The global deőnition őle <archive_name>.def stores all global and uniőed deőnition records. There are also local deőnition and trace őles, one for each MPI process. The őle <node>.def stores mapping tables used to map identiőers that are not global during the measurement. The <node> is the rank of the MPI process whose execution is logged in the őles. The trace őle <node>.evt is constituted by all the local event records that occur during the execution of the application. There is only one event őle per MPI process. Each event őle contains information about all the traced functions. For any function, an event őle stores its locationID which is the rank of the MPI process that called this function and the time-stamp in ticks. The rest are event dependent, it can be the regionID which is the name of the function, or the metricID which is the id of the used PAPI counter. It is important to mention that the global deőnition őle contains the time resolution used for the measurement of time, thus the time-stamps of the events should be divided by the time resolution in order to extract the time in seconds.

Score-P creates binary őles, so it is mandatory to use the OTF2 reading interface [100] to extract the required information. We developed a C/MPI parallel application with a similar number of callbacks as for TAU. This program opens, in parallel, all the local deőnition and trace őles and read them line by line. However, we had to copy the anchor and the global deőnition őles across all the nodes with the help of the taktuk tool because they only exist on the root node. This happens because Score-P is considering the existence of a global őle system. However, thanks to the structure of the OTF2 őle format we can read the traces in parallel.

We present hereafter some examples of MPI functions to illustrate how our trace_extract_scorep extraction tool works. The following example in Figure 3.13 shows the callbacks related to the MPI_Send function in a readable format. The őrst column declares the name of the event, then are the process id, the time in ticks and the event dependent data. For the METRIC events (lines 1 and 4), are declared the id of the measured hardware counter, and its value. For the ENTER/EXIT events (lines 2 and 5), there are the name of the function with its id. Finally for the event MPI_Send after the time are declared the thread id of the receiver, the MPI communicator, the MPI tag and the size of the message (in bytes).

Figure 3.14 presents the parameters of the diferent callbacks related to the MPI_Irecv and MPI_Wait functions calls on process 1 in a readable format. The data layour is similar. The OTF2 reading interface provides a method to seek to a speciőc event during the reading of the local event trace őle. Thus the procedure is similar to the one described for TAU. On the line 3 the MPI_IRECV_REQUEST event, declares that the MPI_Irecv function was called. Then, the event MPI_IRECV (line 9) marks the end of this MPI function while the MPI_Wait function has already been called.

The MPI_Bcast function is presented in Figure 3.15. The events MPI_COLLECTIVE_BEGIN and MPI_COLLECTIVE_END declare the start and the end of an MPI collective communication MPI_Bcast function. This event provides the MPI communicator, the root node, the sent and the received sizes of the messages (in bytes). The MPI_Allreduce function is presented in Figure 3.16. On line 4, after the name of the MPI function, are declared the MPI communicator and the sum of sent and received bytes. In this example four processes were involved, thus the size of each message for the allreduce action is 40 bytes. Moreover from the METRIC events we calculate how many instructions are computed during the reduction operation.

As for TAU, it is not possible to extract all the necessary data regarding a call to the MPI_Alltoallv function and other similar collective operations because the traces provide only generic values about the size of the messages. For example Figure 3.17 presents callbacks related to the MPI_Alltoallv function. The alltoallv event provides the MPI communicator and the sum of the sent and received size of the messages (in bytes). In this case we do not know exactly the size of the messages that a process sends or receives and the displacements of the array that are given as input in the MPI_Alltoallv function. We should mention that the last two elements of the MPI_COLLECTIVE_END declare the size of the messages (in bytes) that were sent and received respectively.

MinI

An application instrumented with MinI directly produces time-independent traces during its execution, thus there is no need for a separate tool. Nevertheless, we present how MinI handles calls to some MPI functions. This is a more generic approach and for sake of simplicity we do not show the whole code for each MPI call, e.g., all the variables are considered as declared.

One of the main advantages in comparison to the previous tools is that we can extract the data type of each message for all the MPI communications. In order to use this information into the time-independent traces, we use the function encode_data_type which basically maps each MPI data type to an integer (Figure 3.18).

MinI creates the time-independent traces as a wrapper on calls to PMPI. Figure 3.19 shows the corresponding code for the MPI_Send function.

On line 3 the value of the PAPI counter is saved into the values array and we declare that only one counter is used. On line 4 we the save the data type of the sent data in the variable t_data. We obtain the rank of the MPI process through a call to PMPI_Comm_rank (line 6) and produce the compute action that preceeds this send (line 8). From lines 11 to 16, we produce the send action that comprises the rank of the sender, the send keywork, the rank of the receiver, the message syze, and optionally the message type. The type is optional to reduce the size of the produce traces when the same type is used by the whole application, e.g., MPI_DOUBLE_PRECISION. On line 16, PMI_Send is called to actually perform the communication. The last two lines initiate the count of the number of instructions that will be stopped in the next MPI call.

In the calles to MPI_Irecv and MPI_wait, we rely on a temporary bufer to save a local timeindependent trace between these two calls. We obtain the id of the sender from the MPI_Status data structure during the MPI_Wait call. The MPI_Bcast function is given in Figure 3.23. Here we just show another way to reduce trace size thanks to default values. If a collective is rooted in process of rank 0 and the data type is MPI_DOUBLE_PRECISION, we do not include this information in the trace. Otherwise a bcast action will have two more entries.

For the MPI_Allreduce function, presented in Figure 3.24, each process computes the number of instructions it has executed during this call and report it in the produced action. Again, saving the data type is optional.

Similar the MPI_Bcast function, is presented in Figure 3.20. The most details are similar to other MPI functions and are not presented, however we wanted to show that during a collective communication the root node is known. We considered the default value of the root node equal to zero, thus are not declared into the time-independent traces in the case that the values of both root node and the this_type are equal to zero. In this example the message size is 4 bytes, the root node is equal to one and the data type value is equal to two, which means from the function encode_data_type that the message's data type is MPI_CHAR. Similar the MPI_Allreduce function, is presented in Figure 3.21. In this case, we compute the instructions that the call to the MPI_Allreduce function executes and are declared in the corresponding action with the message's data type if is not the default one. The elements of this action depend on the number of participating processes. In this example we execute this collective operation on 4 processes. The őrst element after the name of the action is the length of the send bufer, the next four values correspond to the number of elements respectively sent to the other processes, then the other four values correspond to the displacements according to the MPI standards. Symmetrically we őnd the length of the receive bufer, and the values of the number of elements that the processors can receive and their displacements. The last value which is equal to one, declares that all the previous values are integers.

Once extracted, and whatever the extraction method, time-independent traces can be injected into the simulation framework. However, they őrst have to be gathered on a single node onto which the simulation will take place.

Trace Gathering

One challenge for trace acquisition is the time needed to aggregate (potentially large) trace őles generated on a large number of compute nodes. This corresponds to a standard łgatherž collective communication operation. The Grid'5000 platform provides a tool called kaget to gather remote őles into a single node. This tool is based on taktuk and provides a simple interface without the need for the user to be familiar with the complicated commands of taktuk. We tested this tool to assess its performance and unfortunately the performance was not satisfying. Then, we implemented another tool based on a diferent gathering algorithm called trace_gather. It is based on a K-nomial reduction tree that allows for an eicient gathering of the őles in log (K+1) N steps, where N is the number of őles and K is the arity of the tree. This tool can be eicient by picking an appropriate K value given to the number of trace őles and the number of compute nodes. Figure 3.23 shows how this tool handles the traces produced on 16 nodes.

Analysis of Trace sizes

We used two instrumentation methods with TAU. Table 3.26 shows the TAU trace sizes with both methods. With TAU-reduced the trace sizes are decreased from 35% to 44% in comparison to the selective instrumentation. This leads to smaller time and space overheads. One issue with of-line simulation is the large size of the traces. The time-independent trace format was improved through our diferent versions of our framework. Although we studied various benchmarks we present the time-independent trace sizes only for the LU benchmark. For EP, each process executes a big block of instructions. Then the trace of a given process has only one line. For DT, the number of actions is also relatively small. The processes that execute the most actions are comparators that receive data from four other processes, merge them, and forward the aggregated data. Consequently the total trace size for both benchmarks is at most a few hundreds of kilobytes for class C instances. With LU, computations and communications are interleaved and each process logs a lot of actions. The size of the time-independent traces depends on the number of actions executed by the processes. Table 3.27 shows trace sizes for diferent instances of the LU benchmark as well as the number of actions in each trace for the prototype framework [START_REF] Desprez | Assessing the Performance of MPI Applications Through Time-Independent Trace Replay[END_REF].

The size of time-independent traces grows linearly with the number of processes which is explained by the evolution of the number of traced events. We also see that the size of the time-independent traces grows from a constant factor of 1.6 from class B to class C which is also directly related to the number of actions. Table 3.27 presents the trace sizes for the selective instrumentation method. The ratio of size to the number of actions, that denotes the average number of characters per action, is roughly constant (from 14.72 to 15.29). Moreover the traces are extracted from the main core of the benchmark. It does not include the initialization and őnalization phases. Table 3.28 shows trace sizes obtained with the MinI instrumentation method for the whole benchmark. Then there are more actions for each instance in comparison to Table 3.27. Dividing the trace size by the number of actions also leads to a roughly constant ratio (between 14.45 and 15.94). Note that while the number of the actions are increased from 0.3% up to 0.5%, the trace sizes are globally decreased from 0.2% to 1.7%. However, our trace format is not optimized for space. Authors have proposed compact trace representations [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Noeth | Scalable Compression and Replay of Communication Traces in Massively Parallel Environments[END_REF]. In our case, we could devise a binary trace format that would remove most of the redundant characters. Alternately, we can simply use compression algorithms for our text trace őles, which reduces trace őle size signiőcantly but not as much as if a custom compact trace format were used. When showing the scalability of our trace acquisition procedure in the next section we őrst present results without any compaction/compression, and then some results using compression. Now that the whole acquisition procedure has been presented in detail, we can evaluate it in order to identify any bottleneck.

Evaluation of the Acquisition Procedure

Trace Acquisition Scalability

We have already mentioned the three diferent instrumentation methods, selective instrumentation, TAU-reduced, and Minimal Instrumentation where each one evolves the previous one. We studied our prototype framework (that uses the selective instrumentation) mainly on AMD processors, thus we used the bordereau [103] cluster. The bordereau cluster comprises 93 2.6 GHz Dual-Proc, Dual-Core AMD Opteron 2218 nodes. All these nodes are connected to a single 10 Gigabit switch. One way to demonstrate the scalability of our trace acquisition procedure is to investigate the distribution of elapsed times for each step of the procedure, i.e., execution, instrumentation, extraction, and gathering. Figure 3.24 shows this distribution for the acquisition of time-independent traces for the most demanding NPB benchmark among those we used in our experiments, i.e., LU, for classes B and C and for diferent number of processes. These results were obtained in the Regular acquisition mode, meaning that there was exactly one MPI process on each compute node. We performed trace acquisition 10 times and we show the average value for each step. The acquisition time is strictly related to the production of the time-independent traces i.e., the instrumentation, extraction, and gathering represent at most 53.34% of the total acquisition time. The worst value is obtained for class B with 64 processes where the benchmark execution time is the smallest. However, large number of processes are generally used to solve large problem instances. Then we can conclude that the extra overhead required to get a time-independent trace can be aforded. Moreover such traces need to be acquired only once and can then be used to explore much more łwhat-ifž scenarios that with timed traces.

As the bordereau cluster was aging with many technical issues and we wanted to evaluate also our framework on Intel processors, we used for the next version of our framework the graphene cluster. It has been already mentioned that the nodes of this cluster are spread over four cabinets, thus we expect to have some communication delays in comparison to the bordereau cluster. However, thanks to the TAU-reduced instrumentation method, the trace sizes are smaller than before, so the instrumentation overhead should be smaller with regard to both time and space. In Figure 3.25 the instrumentation, extraction, and gathering represent at most 76.24% of the total acquisition time for class B with 64 processes. 77% of this time overhead is caused by the gathering procedure which depends on the network speed and topology. To compare the őrst two versions of our framework, we executed some experiments on the graphene cluster. Figure 3.26 shows the evolution of the instrumentation overhead. With the őrst implementation of our framework, the overhead goes from 9.8% to 37.9%, which is consistent with the experiments on the bordereau cluster. The proposed modiőcations make the overhead range shrink to [0.7% -27.1%]. More interestingly, we can see a stable growth of this overhead as the number of processes increases.

Moreover the TAU-reduced method instruments only the MPI calls of an application. According to Table 3.26 the trace sizes are smaller, then the extraction of the time-independent traces from these TAU traces takes less time than the prototype implementation of our framework. However, the gathering of the traces takes more time because of the graphene's network topology.

Then we used the MinI tool for acquiring the time-independent traces. It has been already mentioned that an instrumented application with MinI produces directly the time-independent traces, thus there is no extraction step. Considering that it uses only the absolute necessary features to proőle an application, MinI is also more eicient than TAU. Moreover we used a compression option in the gathering tool to decrease the duration of this procedure. The obtained results are presented in Figure 3.27. The main observation on the results in Figure 3.27 is that when more processes are used the acquisition overhead increases while the time to execute the application decreases. The time to gather traces on a single node becomes more and more prevalent, and even dominates the total trace acquisition time as more processes are involved, accounting for up to 62.02% of the acquisition time. This is expected since the size of each independent trace grows as more actions are logged and the depth of the reduction tree also increases. Data compression and/or a more compact trace format would help to reduce that trace gathering time. For instance, the horizontal line displayed in the gathering part of Figure 3.27 indicates the time needed to gather the same traces but with a preliminary gzip compression step. For large numbers of processes, the trace gathering time can then be divided by up to three. Nevertheless, for realistic instances, i.e., for instances in which a small amount of work is not distributed over a large number of processes, the most time-consuming component of the trace acquisition process is the unavoidable application execution. The tracing overhead represents between 1.75% and 10.55% of the trace acquisition time. The higher values, as already explained for the results in Figure 3.6, are due to cases in which each process performs little computation due to distribution of a small dataset across many processes. Thus our őnal framework provides less tracing overhead than TAU and direct compatibility with the appropriate trace format.

The results in Figure 3.27 are for at most 128 processes. To further evaluate the scalability of our trace acquisition procedure, and also to demonstrate how our trace acquisition framework can be used to acquire traces for simulating platforms that are not actually available, we perform two larger-scale experiments. In the őrst experiment, we use folded execution to execute the instrumented LU benchmark on a single node of a cluster called St-Rémi. This node comprises two twelve-core processors that share 48 GiB of memory. Thanks to folding, we can obtain traces for the largest possible number of processes for classes B and C and a large class D instance of the benchmark on that single node. Table 3.29 shows the obtained results in terms of time needed to acquire the trace and memory footprint in GiB. For comparison purposes, we also include results when obtaining traces with the TAU (with selective instrumentation enabled), the Scalasca, and the Score-P proőling tools. We őnd that TAU cannot produce traces (i.e., it fails) for the larger benchmark instance due to large memory footprint. The results for our minimal instrumentation are in line with those achieved by Scalasca, with some improvement over Scalasca in all cases. But it is important to remind that Scalasca does not produce traces with all the information we need for our purpose, so the Scalasca results in the table are optimistic. The memory footprint of Score-P is three to four times larger than that of our minimal instrumentation. For large instances, such as the class D executed with 256 processes, Score-P begins to swap, leading to prohibitively long acquisition times. We conclude that although proőling tools exist, and in fact provide capabilities well beyond what is needed in this work, our minimal instrumentation method is useful to achieve better scalability. In the second experiment, we run a very large-scale application on a heterogeneous platform, i.e., combining the folded and composite modes. More speciőcally, we run class E of the LU benchmark, with 16,384 processes. To run this large instance, we distributed trace acquisition across 778 compute nodes in 18 clusters at 9 geographically distant sites of the Grid'5000 experimental testbed. The set of clusters being heterogeneous, the MPI processes were not uniformly distributed across the clusters. Instead, they were distributed according to the memory capacity of each cluster, attempting to maximize usage of main memory without overcoming its capacity. As a result, we used a diferent folding factor on each cluster. As for the previous experiment, TAU fails to produce a trace due to its large memory footprint. We did not use Scalasca as it does not meet all the requirements for obtaining a useful trace. We stopped the execution with Score-P after more than nine hours, without obtaining the desired trace. Our minimal instrumentation method was successful in acquiring the trace, producing a 1.45 TiB time-independent trace. 53 minutes were needed to execute the instrumented application. 16 minutes were needed to gather and aggregate individual trace őles on a single node using a K-nomial tree. This time includes a gzip compression step. Decompressing the őles on a single node is a more expensive process that added around 40 minutes of computation. For such a large trace, using compression/decompression was worthwhile. Note that systems exist for adaptive compression so as to achieve a good trade-of between compression time and data transfer time [START_REF] Jeannot | Improving Middleware Performance with AdOC: An Adaptive Online Compression Library for Data Transfer[END_REF]. In the end, our approach was suiciently scalable to acquire a trace for a 16,384-process MPI application using 9 diferent clusters over a wide-area network in less than two hours.

Evaluation of the Execution Modes

To acquire trace-independent traces with our őrst prototype framework, we used two clusters of the Grid'5000 experimental testbed: bordereau and gdx. The gdx cluster comprises 186 2.0 GHz Dual-Proc AMD Opteron 246 scattered across 18 cabinets. Two cabinets share a common switch and all these switches are connected to a single second level switch through Ethernet 1 Gigabit links. Consequently a communication between two nodes located in two distant cabinets goes through three diferent switches. These two clusters are interconnected through a dedicated 10 Gigabit network.

Table 3.30 shows the execution time of the LU benchmark (class B) for the Regular (R), Folded (F-x), Composite (C-y), and Composite and Folded (CF-(u, v)) acquisition modes, instrumented with the selective instrumentation. The last row of the table shows the slowdown relative to the regular mode. When processes are folded on a smaller number of nodes, x denotes the folding factor. For instance F-4 means that four processes are executed on a single CPU. In the composite mode, y is the number of sites used for the acquisition. Finally when both modes are combined, CF-(u, v) means that the execution is distributed over u sites and that v processes run on each CPU. In the composite mode, y is the number of sites used for the acquisition. Finally when both modes are combined, CF-(u, v) means that the execution is distributed over u sites and that v processes run on each CPU. Again, we use only one core per node.

We see that the time needed to execute the instrumented application increases linearly with the folding factor (F-*). This was expected as several processes have to compete for a single CPU. However, there is no extra overhead induced by folding. When the execution is scattered across two clusters (C-2), the overhead comes from two factors. First, some communications are made on a wide area network and then take more time to complete. Second, the progression of the execution is limited by the slowest cluster (gdx ). While this overhead remains lower than the number of sites, further experiments showed that it increases with the number of sites and is also greater for smaller problem classes. Indeed, a lower amount of computations leads to a greater impact of wide area communications. Finally with the combination of process folding and scattering (CF-(2,*)), the overhead costs are cumulated. If we divide the ratios to regular mode by the value obtained for C-2, we still observe that the execution time increases with the folding factor in a roughly linear way. For DT we used diferent folding factors to ensure that the load is well balanced among processes. Compared to the other benchmarks, folding has a smaller impact on execution time as this benchmark is dominated by communications, while Scattering is more detrimental for the same reason. Large bufer allocations can prevent folding for big DT instances.

An interesting property of time-independent traces is exempliőed by these experiments. A tracing tool such as TAU will produce traces with some erroneous timestamps for most scenarios, due to external load on the system and or transient operating systems behaviors. An of-line simulator using these traces would then predict an execution time close to that of the corresponding acquisition scenario instead of the targeted Regular mode execution time. Preventing such a behavior would require an accurate description of the acquisition platform along with the trace. With time-independent traces, the simulated time is totally independent of the acquisition scenario. Only slight variations (under 1%) are observed caused by hardware counter accuracy issue, and in fact a dedicated platform is not even required.

Similarly, Table 3.31 shows the execution time of the LU benchmark (class B) instrumented with the MinI tool. The execution times are obtained on the graphene cluster and, when composite execution takes place, also on the paradent cluster that comprises 64 2.5GHz Dual Quad-Core Intel Xeon L5420 nodes. The nodes of these two clusters have very similar peak performance, around 8Gŕop/s per core, as measured with the HPLinpack benchmark, and we use one core per node in this experiment. Table 3.31: Execution time and slowdown relative to the regular acquisition mode for instrumented runs of the LU NAS benchmark (class B) executed with 64 processes, for several acquisition modes. Results obtained on the graphene and paradent. We obtained results and trends similar to those in Table 3.30 with regard to the slowdown factors. However, we observed an impact of the network of the second cluster, paradent on the performance of the diferent acquisition modes. Indeed, while the performance of the folded mode is improved (from 11.21% to 24.72%) thanks to the minimal instrumentation, the composite mode takes more time (around 15%). Moreover, when both modes are combined, the improvement is lower than with the folded mode alone (from 3.24% to 21.4% only). Nervertheless, the beneőts ofered by the minimal instrumentation in terms of overhead and skew do not compromise the use of the folded and composite acquisition modes.

Acquisition mode R F-2 F-4 F-8 F-16 F-32 C-2 CF-(2,2) CF-(2,4) CF-(2,8) CF-(2,

Conclusion

In this chapter we presented in detail the diferent steps of our time-independent trace acquisition framework. We explained what occurs during the instrumentation of an application and introduced the time-independent trace format. We analyzed all the possible actions of a time-independent trace to show the corresponding requirements that a tracing tool should respect to produce such traces. According to these requirements we evaluated many open source proőling tools among the most popular. As none of the studied fulőlled our requirements without inducing important overheads, instrumentation skew, and/or large memory footprint, we also proposed another instrumentation method to decrease the instrumentation overhead and improve the accuracy of the measured values both for time and hardware counters. This original instrumentation method is called MinI. This tool was developed with the necessary options only and provides a direct compatibility with the time-independent traces as this is its default trace output format, leading to minimal instrumentation overhead and skew. Moreover four execution modes were proposed and we showed how we can take advantage of most of them in comparison to other frameworks. We also explained how we can use our framework on the Grid'5000 platform. Furthermore we presented in detail two tools, one for extracting time-independent traces produced by TAU and Score-P and another one for gathering these traces into one single node. We did further analysis of trace sizes for both TAU tool and time-independent trace framework. An evaluation of the full acquisition procedure was conducted to show the improvement of our framework since the prototype version and present in detail the corresponding overheads. Finally we succeed in applying our framework on 778 compute nodes by executing an instrumented application with 16,384 processes and acquire the corresponding time-independent traces to prove its scalability. Now that time-independent traces can be acquired for an application, we can use them to predict the performance of applications. The replay of time-independent traces will be detailed in the next Chapter.

Chapter 4

Time-Independent Trace Replay

In the previous Chapter we described the time-independent trace acquisition framework. We detailed all the procedures required to obtain a time-independent trace from an application. In the current Chapter we present how to replay time-independent traces by using a simulator based on the SimGrid simulation toolkit.

Since release 3.3.3, SimGrid allows users to describe an applicative workload as a timeindependent trace. As shown in the upper part of Figure 4.1, three input őles are needed to replay such traces with SimGrid. Apart from the time-independent trace(s), descriptions of the simulated platform and of the deployment of the application, i.e., how simulated processes are mapped onto simulated processors, are also needed. These input are passed to the trace replay tool which, in turn, is built on top of the simulation kernel in SimGrid. Decoupling the simulation kernel, and then the simulator, from the simulation scenario ofers ŕexibility. A wide range of łwhat if?ž scenarios can be explored without modifying of the simulator and instead simply changing the input őles.

The platform őle on the upper left part of Figure 4.1 declares a cluster of 4 nodes with the cluster tag. This tag is used to quickly declare a bunch of homogeneous machines. The cluster is a meta-tag from SimGrid point of view. It represents an Autonomous System (AS) in which is deőned some optimized routing mechanisms. There are have four nodes in this cluster, named c-[0-3].me, whose processing power is one billion instructions per second. The cluster's network bandwidth is 1Gb/s (or 1.25E8B/s), the latency for both the cluster links and the backbone are 15 microseconds, and the backbone bandwidth is 10Gb/s (or 1.25E9B/s). The time-independent trace in the upper middle part correspond to the example in Figure 3.1, where each process on a ring computes one million instructions and sends one million bytes to its neighbor. The deployment őle on the upper right corner of Figure 4.1 maps the simulated processes on the platform. For example the simulated process of rank 0 is mapped to the node c-0.me. Our replay framework can produce various types of output as indicated in the bottom part of Figure 4.1. First we can obtain a simulated execution time, which serves as a prediction of the execution time of the target application in the particular experimental scenario described by the platform and deployment őles. It is also possible to generate a time-stamped trace that corresponds to this particular scenario by adding timers (measuring simulated time) in the trace replay tool. Finally it is possible to visualize the trace as a Gantt chart, thanks to a built-in tracing mechanism provided by SimGrid that produce traces in the Pajé format [START_REF] Chassin | Pajé, an Extensible and Interactive and Scalable Environment for Visualizing Parallel Program Executions[END_REF].

The remaining of this Chapter is organized as follows. In Section 4.1 we go further than the platform [START_REF] Bobelin | Scalable multi-purpose network representation for large scale distributed system simulation[END_REF]. The SimGrid toolkit handles most of these routing schemes and can determine routes between hosts belonging to diferent ASes by looking for the őrst common ancestor in the hierarchy.

In what follows, we detail the diferent steps that allowed us to propose a highly realistic description of the graphene cluster that was used in many of our experiments. As mentioned in the previous Chapter, graphene comprises 144 2.53GHz Quad-Core Intel Xeon x3440 nodes. Each core has a L2 cache of 2 MB. The nodes are spread across four cabinets, and interconnected by a hierarchy of 10 Gigabit Ethernet switches. The simplest description of this cluster is given by Figure 4.2 <?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd"> <platform version="3"> <AS id="AS_graphene" routing="Full" > <cluster id="AS_sgraphene1" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="0-143" power="1E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> </AS> </platform> The diferent attributes of the <cluster> tag provide the minimal information to describe the cluster's characteristics and performance. The name of the nodes that compose the cluster and formed from the prefix, suffix, and radical attributes. The radical is a classical regular expression that allows users to describe non-contiguous ranges of nodes. In this example, the names are then graphene-[0-143].nancy.grid5000.fr. The power attribute indicates the processing speed of a node in number of instructions processed per second. The four remaining attributes respectively deőne the latency and bandwidth of the network links the connect each node to a backbone (preőxed by bb_). The main problem with this simplistic description is that it does not reŕect the hierarchical organization in cabinets of the cluster.

Figure 4.3 improves this description by distinguishing the four cabinets as four ASes named

AS_graphene [START_REF] Kurowski | Complex system simulations with qoscosgrid[END_REF][START_REF] Kurowski | Parallel large scale simulations in the pl-grid environment[END_REF][START_REF] Umakishore Ramachandran | Issues in understanding the scalability of parallel systems[END_REF][START_REF] Liu | Automatic performance debugging of spmd-style parallel programs[END_REF], each having a diferent range of nodes. These four ASes belong to a single AS, called AS_graphene, that represents the whole cluster. Each cabinet is connected to a central backbone, called switch-graphene, with its own bandwidth and latency. As the main AS follows the Full routind method, we have to declare how cabinets are interconneted, thank to the <ASroute> tags. For sake of simplicity we show only the connection between two pair of cabinets. The <ASroute> tag declares a route between two ASes. In our example, this route is between AS_graphene1 and AS_graphene2. The access point (or gateway) of the source (resp. destination) AS is given in the gw_src (resp. gw_dst) attribute. There is a single link between these two gateways, namely switch-graphene.

As mentioned in Figure 4.1, another input őle is required by our trace reaply tool. It is the deployment őle that maps each simulated process on a node of the platform. A typical example of deployement for the graphene cluster is presented in Figure 4.4. It shows that the the process of rank 0 is mapped onto the graphene-0.nancy.grid5000.fr node. Similar information is given for all the other nodes in the cluster.

<?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd"> <platform version="3"> <AS id="AS_graphene" routing="Full" > <cluster id="AS_sgraphene1" prefix="graphene-" suffix=".nancy.grid5000.fr" radical= "0-38" power="1E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene2" prefix="graphene-" suffix=".nancy.grid5000.fr" radical= "39-73" power="1E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene3" prefix="graphene-" suffix=".nancy.grid5000.fr" radical= "74-103" power="1E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene4" prefix="graphene-" suffix=".nancy.grid5000.fr" radical= "104-143" power="1E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <link id="switch-graphene" bandwidth="1.25E9" latency="5E-4"/> <ASroute src="AS_sgraphene1" dst="AS_sgraphene2" gw_src="graphene-AS_sgraphene1_router.nancy.grid5000.fr" gw_dst="graphene-AS_sgraphene2_router.nancy.grid5000.fr"> <link_ctn id="switch-graphene"/> </ASroute> <ASroute src="AS_sgraphene1" dst="AS_sgraphene3" gw_src="graphene-AS_sgraphene1_router.nancy.grid5000.fr" gw_dst="graphene-AS_sgraphene3_router.nancy.grid5000.fr"> <link_ctn id="switch-graphene"/> </ASroute> ... <?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd"> <platform version="3"> <process host="graphene-0.nancy.grid5000.fr" function="0"/> <process host="graphene-1.nancy.grid5000.fr" function="1"/> ... <process host="graphene-142.nancy.grid5000.fr" function="142"/> <process host="graphene-143.nancy.grid5000.fr" function="143"/> </platform>

</AS> </platform>

Calibration and Instantiation

A necessary step for obtaining accurate performance predictions through simulation is the calibration of the simulation tool. In our context, calibration is used to determine the rate at which a CPU processes instructions, the latency and bandwidth of communication links, and some other factors. These values are then used to instantiate the platform description őle shown in Figure 4.3. Such a calibration strongly depends on both application and execution environment. Indeed diferent types of computation may lead to diferent processing rates on a given CPU. This is mainly due to how eiciently the computation can use the diferent levels of cache. Moreover the performance of a given computation may difer with regard to the processor brand.

Calibration of the CPU processing power To instantiate the power attribute of the <cluster> tag that represents the processing power of each host in the cluster, we proceed as follows. A small instrumented instance of the target application, e.g., a class A instance for NAS parallel benchmarks, is run on a small version of the cluster to describe, e.g., on up to four nodes. This allows us to determine the number of instructions of each event as long as the time spent to computed them. Then we can determine a processing rate of each single action, compute a weighted average on each process, and get an average processing rate for all the process set. To smooth the runtime variations, we repeat this procedure őve times and compute an average over the őve runs. We use this őnal value to instantiate the SimGrid platform őle. It depends on the application, compilation options and target cluster characteristics. This calibration step allows us to acquire time-independent traces on any execution environment, as explained in Chapter 3, and simulate their compute part on a correctly instantiated description of the target cluster. For instance, the description given in Figure 4.5 has been updated with a processing power that correspond to a calibration of LU benchmark on the graphene cluster. The obtained rate is of 3.68E9 instructions per second and is homogeneous across the nodes.

<?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd"> <platform version="3"> <AS id="AS_graphene" routing="Full" > <cluster id="AS_sgraphene1" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="0-38" power= "3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene2" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="39-73" power= "3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene3" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="74-103" power= "3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene4" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="104-143" power= "3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> ... When analyzing the simulation results obtained for the LU benchmark in cite [START_REF] Desprez | Assessing the Performance of MPI Applications Through Time-Independent Trace Replay[END_REF], we observed that the calibration procedure described above prevented us to obtain accurate pre-dictions for some speciőc conditions on speciőc models of processors. More precisely we noted that we were generally overestimating the processing rate, leading to shorter simulated times. For instance, on some simulated clusters, using a calibration based on the execution of a class A instance with 4 processes prevented us to correctly predict the execution time of a class C instance executed with 8 processes. We suspected the large diference of data size managed by each process between the two instances to be the source of this inaccuracy. Then we investigated the use of additional hardware counters, such as the number of L2 cache misses or stalled cycles, to őnd some correlation with the processing rate. Even though we did not őnd anything relevant, having to rely on this counter would have been detrimental to our framework. Indeed, we explained in Section 3.3 that one of the acquisition mode allowed by time-independent traces consists in executing several MPI processes on a single core. In this case, the processes compete for the cache and the values of the hardware counters cannot be used anymore. Then we have to propose another method that does not compromise the beneőt of the time-independent traces.

</AS> </platform>

The rationale of the calibration method was to limit the number of resources and the time needed to do the calibration as much as possible. Experiments shown that while using only as few resources as four cores does not raise any issue, limiting the calibration to a small problem size hide some important phenomena. As already mentioned, in the particular case of the LU factorization, as soon as the share of the matrix owned by each process exceeds the capacity of the L2 cache, the performance drops, with a direct impact on the instruction rate. To circumvent this issue, we propose to complete our calibration procedure, when it is needed, with runs on larger problem sizes but on the same number of resources. In practical terms, we run the class B and C instances in addition to the class A instance, still on four nodes. Then we determine three diferent instruction rates, one per studied class. Depending on whether the current instance handles data that őt in the L2 cache or not, we use the rate coming from the calibration based on class A or the one that corresponds to the instance class.

Note that the use of this cache-aware calibration is mandatory only for the cases where the L2 cache of a processor is small (1MB per core only). On the graphene cluster that has a L2 cache of 2MB per core, all the instances do őt in cache. Calibrating the simulator with a run of the class A instance with four processes is then enough.

Communication Calibration For network resources, SimGrid uses an analytical network contention model. This model was developed for arbitrary network topologies with end-points that use standard network protocols, such as TCP/IP, and are connected via multi-hop paths. Instead of being packet-based, the model is ŕow-based, meaning that at each instant the bandwidth allocated to an active ŕow (i.e., a data transfer occurring between two end-points) is computed analytically given the topology of the network and all currently active ŕows. This generic model is well suited for networks ranging from local-area to wide-area networks. In [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF], a simulator called SMPI, was added to the SimGrid toolkit for the on-line simulation of MPI applications on a single node. In order to specialize the generic network model for cluster interconnects, a model has been added to the SimGrid simulation kernel that takes into account the speciőcs of MPI implementations that use TCP on cluster interconnects. In [START_REF] Bedaride | Improving Simulations of MPI Applications Using A Hybrid Network Model with Topology and Contention Support[END_REF] we propose a hybrid network model where more parameters are used to take under consideration the congestion which can occur during the execution of a parallel application. For the declared bandwidth in the <cluster> tags, the nominate value of the link is used. The measurements presented in Figure 4.6 were obtained according to the following protocol. To avoid any measurement bias, the message size is exponentially sampled from 1 byte to 100MiB. We ran two "ping" and one "ping-pong" experiments. The ping experiments aim at measuring the time spent in the MPI_Send (respectively MPI_Recv) function by ensuring that the receiver (respectively sender) is always ready to communicate. The ping-pong experiment allows us to measure the transmission delay. We ran our analysis on the whole set of raw measurements rather than on averaged values for each message size to prevent behavior smoothing and variability information loss. The rationale is to study the asynchronous part of MPI (from the application point of view) without any a priori assumptions of where switching may occur. We distinguish three modes of operation in Figure 4.7: asynchronous, detached, and synchronous. The variable k is the message size (in bytes), S a , and S d are the size thresholds of the asynchronous communication and detached communication respectively. In Figure 4.7, P s and P r represent the processes of the send and receiver respectively and the variable T i declares the durations of the corresponding task. More information about this hybrid network model can be found in [START_REF] Bedaride | Improving Simulations of MPI Applications Using A Hybrid Network Model with Topology and Contention Support[END_REF]. ś Small (when k ≤ 1, 420): this mode corresponds to messages that őt in a TCP packet and are sent asynchronously by the kernel. As it induces memory copies, the duration signiőcantly depends on the message size; ś Medium (when 1, 420 < k ≤ 32, 768 or 32, 768 < k ≤ 65, 536 = S a ): these messages are still sent asynchronously but incur a slight overhead compared to small messages, hence a discontinuity at k = 1420. The distinction at k = 32, 768 does not really correspond to any particular threshold on the sender side but is visible on the receiver side where a small gap is noticed. Accounting for it is harmless and allows for a better linear őtting accounting for MPI/TCP peculiarities; ś Detached (when 65, 536 < k ≤ 327, 680 = S d ): this mode corresponds to messages that do not block the sender but require the receiver to post the reception before the communication actually takes place; ś Large (when k > 327, 680): for such messages, both sender and receiver synchronize using a rendez-vous protocol before sending data. Except for the waiting time, the durations on the sender side and on the receiver side are very close. All the parameters and values for the instantiation of this hybrid for the described cluster can be declared thanks to a conőguration header in the XML őle, as shown in Figure 4.8.

Small

<?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd"> <platform version="3"> <config id="General"> <prop id="workstation/model" value="compound"/> <prop id="network/model" value="SMPI"/> <prop id="smpi/async_small_thres" value="65536"/> <prop id="smpi/send_is_detached_thres" value="327680"/> <prop id= "smpi/os" value="0:8.93009e-06:7.654382e-10; 1420:1.396843e-05:2.974094e-10; 32768:1.540828e-05:2.441040e-10; 65536:0.000238:0; 327680:0:0"/> <prop id= "smpi/or" value="0:8.140255e-06:8.395881e-10; 1420:1.269952e-05:9.092182e-10; 32768:3.095706e-05:6.956453e-10; 65536:0:0; 327680:0:0"/> <prop id="smpi/bw_factor" value="0:0.400977; 1420:0.913556; 32768:1.078319; 65536:0.956084; 327680:0.929868"/> <prop id= "smpi/lat_factor" value="0:1.35489; 1420:3.437250; 32768:5.721647;65536:11.988532; 327680:9.650420"/> </config> <AS id="AS_graphene" routing="Full" > <cluster id="AS_sgraphene1" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="0-38" power="3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> <cluster id="AS_sgraphene2" prefix="graphene-" suffix=".nancy.grid5000.fr" radical="39-73" power="3.68E9" bw="1.25E8" lat="15E-6" bb_bw="1.25E9" bb_lat="15E-6"/> ... First, we have to declare that the default network model is not the one to used by creating a compound (combination of CPU and network models) using the SMPI hybrid network model (lines 5 and 6). Then we declare the message size at which the protocol change from eager to rendez-vous (async_small_thres at 65,536 bytes) and from rendez-vous to detached (send_is_detached_thres at 327,680 bytes) (lines 7 and 8). From line 10 to line 17, we declare the values for the sender and receiver overheads (smpi/os and smpi/or. The values of these parameters are given by triplets x : y : z. For messages whose size is greater than x, the simulation kernel applies a delay of z + x × y. This delay, that depends on the message size, basically corresponds to copying the message in memory. Finally, correction factors for the latency and bandwidth are declared from lines 19 to 23. This allows the model to mimic the behavior shown by Figure 4.6. They are declared as couples x : y. For messages whose size is greater than x, the factor y is applied to the nominal bandwidth (resp. latency).

</AS> </platform>

All the presented values were obtained on the graphene cluster. The łpingž measurements are used to instantiate the values of o s , O S , o r , and O r for small to detached messages which are the sender overhead, the overhead per byte at the sender side, the receiver overhead and the overhead per byte at the receiver side respectively. By subtracting 2(o r + k.O r ) from the round trip time measured by the łping-pongž experiment, and thanks to a piece-wise linear regression, we can deduce the values of latency and bandwidth correction factors.

The last phenomenon to reŕect in our description to become completely realistic is the impact of network contention on a point-to-point communication between two processors in a same cabinet and between two processors in two diferent cabinets. To quantify this impact, we artiőcially create contention and measure the bandwidth as perceived by the sender and the receiver. We place ourselves in the large message mode where the highest bandwidth usage is observed and transfer 4 MiB messages.

In a őrst experiment we increase the number of concurrent pings from 1 to 19, i.e., half the size of the cabinet. As the network switch is well dimensioned, this experiment fails to create contention: We observe no bandwidth degradation on either the sender side or the receiver side. Our second experiment uses concurrent MPI_Sendrecv transfers instead of pings. We increase the number of concurrent transfers from 1 to 19 and measure the bandwidth on the sender (B s ) and receiver (B r ) side. A multi-port model, as assumed by delay models, would estimate that B s + B r = 2 × B since communications do not interfere with each other. However, both fail to model what actually happens, as we observe that B s + B r ≈ 1.5 × B on this cluster.

We model this bandwidth sharing efect by enriching the simulated cluster description, as seen in Figure 4.9. Each processor is provided with three links: an uplink and a downlink, so that send and receive operations share the available bandwidth separately in each direction; and a speciőc link, whose bandwidth is 1.5 × B, shared by all the ŕows to and from this processor. The consequence is that there is no more backbone (and thus no more bb_lat and bb_bw attributes in the <cluster> tag. Experiments shown it was more realistic to connect the nodes directly to the router of the cluster and model communications as follows. The sharing_policy of the links that connect the nodes to the router is declared to FULLDUPLEX. This means that two links (named UP and DOWN) are created during the parsing of the XML őle to model pertubation coming from ACK returning packets [START_REF] Velho | On the Validity of Flow-level TCP Network Models for Grid and Cloud Simulations[END_REF]. Then the limiter_link attribute creates a pseudoshared link to limit the bandwidth that can achieved with the fullduplex links. This link has no latency and a bandwidth of 1.875E8 B/s (that is 1.5 × 1.25E8B/s) and it will create contention when messages are sent from both directions with a new peak bandwidth value. When the messages are sent only to one direction the initial bandwidth value is respected. Finally, the loopback_lat and loopback_bw atributes respectively declare the values of the latency and the bandwidth of the link used when a process sends a message to another process mapped on the same node.

Preliminary experiments on other clusters show that this contention parameter seems constant for a given platform, with a value somewhere between 1 and 2. Determining this parameter requires benchmarking each cluster as described in this section. The set of experiments is available on this web page [111].

This modiőcation is not enough to model contention at the level of the whole graphene cluster. As said eralier, this cluster is made of four cabinets interconnected through 10Gb links.

Experiments show that these links become limiting when shared between several concurrent pairwise communications between cabinets. This efect is captured by describing the interconnection of two cabinets as three distinct links (uplink, downlink, and limiting link). In Figure 4.9, this correspond to lines 49 to 76. The links named explicit-limiter [START_REF] Kurowski | Complex system simulations with qoscosgrid[END_REF][START_REF] Kurowski | Parallel large scale simulations in the pl-grid environment[END_REF] induce the same behavior as the limiter_link attribute of the <cluster> tag. The bandwidth of the limiting links is set to 13 Gb/s as measured. But experiments shown that application are never able to use more than 93% of the nominal bandwidth across cabinets. Then we applied this correction directly in the XML őle (lines 49, 51, 54, and 56). Finally note that the routes between two cabinets are not symmetrical anymore (see lines 63 and 72) to take the uplink, downlink, and limiting links into account.

If we refer to Figure 4.1, we now have all the necessary inputs to replay a time-independent trace: a realistic and carefully instantiated description of the target cluster (Figure 4.9), a deployment őle (Figure 4.4, and time-independent trace acquired according to the framework described in Chapter 3. In the next Section, we introduce the simulation backends used in the diferent implementations of our time-independent replay tool.

Simulated Trace Replay

Our simulation framework is tightly connected to the SimGrid project [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF] that provides core functionalities for the simulation of distributed applications in heterogeneous distributed environments. SimGrid relies on a scalable and extensible simulation engine and ofers several user APIs. The MSG API allows users to describe an application as a set of concurrent processes and provides a simple mailbox-based communication protocol. While initially aimed at studying scheduling algorithms, the MSG API proved to be perfectly usable in other contexts and became the most widely used API of SimGrid. Then, to replay time-independent traces, we őrst wrote a simulator, on top of the simulation kernel using the MSG API.

This simulator had to include a function that corresponds to the expected behavior of a given action. This has to be done for each action that may appear in a trace. We present hereafter the implementation of some typical and representative actions.

Figure 4.10 shows the necessary code for the compute action. The format of this action is <id> compute <volume of instructions>, and is passed to this function as an array of strings (action), one for each őeld of the entry. Once the amount of instructions to compute has been extracted (line 2), it is possible to create the corresponding SimGrid task (line 3). The task is executed (line 6) and destroyed (line 7) as soon as the computation of amount instructions has been simulated. The duration of the action is logged on line 8. 4.11 shows the implementation of the send action whose format is <id> send <dst_id> <volume>. Line 3 retrieves the message size while line 6 creates the name of the mailbox in which the message will be sent. This name combines the rank of the sender and that of the receiver. Line 8 creates a MSG communication task and sends it in the mailbox. Finally line 11 calls a function that check is some asynchronous communications are completed and can be cleaned. 4.12 shows the MSG commands for the Isend action whose format is very similar to that of its synchronous equivalent <id> Isend <dst_id> <volume>. For sake of simplicity, we only comment the additional code needed to handle asynchronous communications. Each simulated process has access to a shared data structure, called globals, that comprises diferent counters and two dynamic arrays, isends and irecvs that respectively contain the pending asynchronous sends and receives. The MSG_task_isend function returns a handler (lines 9-10) that is pushed at the ends of the isends dynamic array (line 11). The Irecv action ( <id> Irecv <src_id> <volume>) depicted in Figure 4.13 is a bit more complex. The basic principle of this action is to retrieve the MSG communication task sent by the sender. To do this, we build the name of the mailbox for this communication from the ranks of the sender and receiver (line 7). Then we use another dynamic array of the global data structure to store the MSG task. First we add an empty task at the end of the dynamic array (line 10), and then we use give a pointer on it as parameter of the MSG_task_irecv function (lines 11-14). Finally, line 15 stores the handle on the asynchronous communication in the irecvs dynamic array. In time-independent traces, as in MPI applications, Irecv actions are usually followed by wait actions that act as synchronization barriers for asynchronous communications. Figure 4.14 presents the code for the wait action (<id> wait). After having checked that this wait was precedeed by an Irecv (lines 8-10), this function gets the last element from the globals->irecv dynamic array (line 12) and waits for its completion (line 13). Lines 14-16 clean up things, one the asynchronous communication has completed and released the MSG_comm_wait function. We complete this presentation of the implementation of some actions using the MSG API with a collective communication operation, namely the bcast action (<id> bcast <volume>).

Once all the actions are implemented, the trace replay tool has to register all of them thanks to the MSG_action_register function. These calls made in the main function of the simulator link the action keywords (as deőned in Table 3.1) to the functions presented above. For instance the main function of the simulator includes the following calls:

xbt_replay_action_register("compute", action_compute); xbt_replay_action_register("send", action_send); xbt_replay_action_register("Isend", action_Isend); xbt_replay_action_register("Irecv", action_Isend); xbt_replay_action_register("wait", action_wait); xbt_replay_action_register("bcast", action_bcast);

The last step consists in calling function MSG_action_trace_run that takes either a trace őle name or NULL as input. When no őle name is given, it means that there is one trace őle per process, whose name is given in the platform őle, as shown below.

<process host="graphene-1.nancy.grid5000.fr" function="1"/> <argument value="SG_process1.trace"/> </process> This őrst implementation of the trace replay tool based on the MSG API forced us to mimic the behavior of MPI primitives, e.g., collectives operations or protocols depending on the message size, with crude simpliőcations. Moreover it decouples this efort on the of-line simulation of MPI applications to that on on-line simulation also taking place within the SimGrid project with SMPI. Consequently we completely rewritten our tool between the publications of [START_REF] Desprez | Assessing the Performance of MPI Applications Through Time-Independent Trace Replay[END_REF] and [START_REF] Desprez | Improving the accuracy and eiciency of time-independent trace replay[END_REF] to change the simulation backend and rely on SMPI instead of MSG.

As explained in Chapter 2, SMPI is another user API of SimGrid dedicated to the on-line simulation of MPI applications [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF]. It is, as the present of-line approach, built on top of the simulation kernel of the SimGrid toolkit and thus also beneőts of its fast, scalable, and validated network models. A salient property of SMPI is its capacity to simulate MPI applications on a single node. SMPI implements about 80% of the MPI 2.0 standard, including most of the network communication related functions. To leverage the accurate network models underlying SMPI, remove unwanted simplifactions, and factor the eforts on the simulation of MPI applications, we have reimplemented the trace replay mechanism directly within SMPI. This rewriting leads to many beneőcial changes. First, it simpliőes the way actions, i.e., events stored in the trace are passed to the simulation kernel.

To illustrate this, we show the implementations of some actions that correspond to speciőc MPI calls. Figure 4.16 presents the new version of the compute action. Lines 2 and 4 log the duration of this action. This action is actually a simple wrapper on the smpi_execute_flops function that belongs to the internal API of SMPI. It simulates the execution of a certain amount of ŕops (the default unit in SimGrid), or any other work unit provided that the processing power of processors is declared in a coherent unit. The send action shown in Figure 4.17 has a slightly diferent format compared to the MSG version: <id> send <dst_id> <volume> [<datatype_id>]. Indeed, instrumentation tools such as TAU, Score-P, and Scalasca express the message size in bytes which is the default data type used by our replay tool. However, the MinI can also log the data type of the message bufer. Then we added a correspondance table that maps each MPI data type to an integer. If this integer is given in the last őeld of the action then the correct data type is used (lines 6-9). This is done whenever the data type can be extracted. Again, the new version is just a wrapper on the appropriate SMPI internal function (line 11). that builds a MPI_Request which is stored at the right position, i.e., given by the receiver's rank, in the global array (line 14). This request will be handled by the wait action. As mentioned earlier, the wait action retrieves the last posted irecv request (line 9) and then waits for its completion (line 11). A check is done to ensure that there were an asynchronous receive to wait for (lines 6-7). We end this presentation of the SMPI versions of actions with the bcast action whose format is <id> bcast <volume> [<root>] [<datatype_id>]. This action has two optional parameters to explicitely declare which process initiates the broadcast and the type of data to communicate. This removes one of the unrealistic assumption made in the MSG version, i.e., having the collective operations always rooted on process of rank 0. The other issue related to the underlying algorithm is directly solved by SMPI. Indeed, calling the smpi_mpi_bcast function allows the trace replay tool to beneőt of the adaptive selection of algorithms for collective operation implemented by SMPI. Depending on the message size, the number of processes, and the MPI implementation (OpenMPI, MPICH, or StarMPI), the best algorithm will be automatically selected in a seamless way. This presentation showed that SMPI already implements a lot of functionalities in comparison to MSG. It is a better choice to use SMPI as it prevents the development of simplistic equivalents of MPI routines. It is also less error prone and diicult than relying on a programming interface that has not been designed to simulate parallel MPI applications. Using MSG means to rethink complex mechanisms such as bufering or RDMA in terms of processors putting tasks in mailboxes. On the contrary, the new implementation allows us to beneőt of all the complex optimizations already ofered and validated by SMPI in a seamless way.

The second main change implied by this rewriting is the user view of the replay framework. In the former version everything was exposed to the user. Everything is now embedded and replaying a Time-Independent Trace with SimGrid simply amounts to run the following program. This code, that initializes some data structures, loads a trace, and destroys the data structures, is considered as a regular SMPI program. Then it is compiled with the smpicc wrapper and launched thanks to the smpirun command (see [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF] for details), as follow smpirun -np 8 -hostfile hostfile \ -platform platform.xml \ ./smpi_replay trace_description where np and hostfile are classical parameters of mpirun. Our replay tool needs a single extra parameter, i.e., a őle that lists the names of the trace őles to associate to each process. If this őle contains a single entry, all the processes will look for the actions they have to perform into the same trace. Otherwise, each process parses actions for its own trace őle.

In the next section, we evaluate the accuracy of the simulation results achieved by the trace replay tool we just detailed. We present results obtained with the őrst prototype written with MSG as well as with the new SMPI version. Then we show how the accuracy was greatly improved thanks to a better calibration procedure and an adapted simulation backend.

Accuracy of Simulation Results

Our őrst prototype framework [START_REF] Desprez | Assessing the Performance of MPI Applications Through Time-Independent Trace Replay[END_REF] was implemented with MSG API and time-independent traces were acquired with the selective instrumentation method described in 3.2.1. Moreover the calibration of the processing rate was not aware of the processor's cache. For the computation calibration of our prototype framework we used the already mentioned approach in Section 4.1 without the cache-aware method. The instantiation of the network parameters of the platform őle was done in two steps. To set the bandwidth, we used the nominal value of the links, e.g., 1 Gib for GigaEthernet links. For the latency of a communication link, we relied on the Pingpong_Send_Recv experiment of the SKaMPI [START_REF] Reussner | SKaMPI: a Comprehensive Benchmark for Public Benchmarking of MPI[END_REF] benchmark suite. Only two nodes of the target platform were then needed here to calibrate the network. We took the value obtained for a 1-byte message and divided it by six. This factor of six comes from two sources. We have to divide the ping-pong time by two to obtain the latency of a one-way message. Then we divide it by three to take the topology of a the network interconnect into account. Indeed, two nodes in a compute cluster are generally connected through two links and one switch. In case of hierarchical network, we account for this hierarchy in the determination of the latency. Finally we were studying AMD processors then we conducted our experiments on the bordereau cluster.

The second step consists in instantiating the piece-wise linear model ofered by SimGrid that is dedicated to MPI communications on compute clusters. SimGrid provides a Python script that takes as input the latency and bandwidth determined as above, the output of the SKaMPI run, and the number of links connecting the two nodes used for the ping-pong. This script determines latency and bandwidth correction factors that lead to a best-őt of the experimental data for each segment of this piece-wise linear model. For DT, the class refers not only to the data size but also the number of communicating processes: classes A, B, and C involve 21, 43, and 85 processes respectively. Moreover three diferent communication graphs can be used for this benchmark. We chose the Black Hole (BH) communication graph that collects data from multiple sources in a single sink. We see that the simulated execution time is very accurate with low relative errors for EP (up to 1.71% for class B on 64 processes) and DT (up to -8.99%) that are dominated either by computation or communication. For LU, which is composed of millions of interleaved computation and communication actions, the obtained results are more ambivalent. Here the trace replay is able to predict the correct evolution trend, but the local relative error may be quite high (up to 47.1% for Class B on 64 processes) and more importantly is not constant. This prevents our tool to provide predictions within a őxed interval of conődence. We can see that for 8 and 16 processes mainly for class C, the absolute diference of the execution and simulated time represents a signiőcant amount of time. 4.24 from a diferent perspective. It shows the evolution of the relative error between the time to compute a LU factorization and its simulated counterpart when the number of involved processes vary. We see that the inaccuracy of the simulated version is not stable, but increases rather linearly with the number of processes. Moreover, our tool underestimates the execution time for small number of processes, i.e., when each process owns a larger share of data, and then overestimates the execution as the number of processes grows.

This inaccuracy may have diferent origins related either to computations or communications. For instance it may come from the discrepancy of the measured number of instructions. Indeed this discrepancy directly impacts the calibration of the replay tool that determines the rate at which each machine can process instructions. Among other potential sources, we assume that every part of the application can be processed at the same rate while it may not be the case for some applications, due to cache ainity for instance. However, the general trend shown by Figure 4.25 seems to indicate that the main source of inaccuracy comes from a bad estimation of communication times. To conőrm this impression, we made simulations in which each compute action was replaced by a delay that corresponds exactly to the time spent for this compute part during the trace acquisition. The obtained results, in which computations are thus perfectly simulated, show a similar trend. The most probable source might then be that the LU factorization, as implemented in the NAS Parallel Benchmark suite, implies a lot of small messages (less than 64 KiB). Then most of the point-to-point communications use the eager mode of MPI in which the sender copies the data directly into the memory of the receiver without having to wait for it to post the corresponding receive. This particular communication protocol was implemented in a too simple way, based on asynchronous communications in the őrst implementation of our framework. As the number of small messages increases with the number of involved processes, small inaccuracies tend to accumulate and lead to a large overall relative error.

In the second version of our framework [START_REF] Desprez | Improving the accuracy and eiciency of time-independent trace replay[END_REF] we combined the compiler optimization ŕag, the TAU-reduced instrumentation detailed in Section 3.2.2, and the cache-aware calibration method to improve the quality of the simulation of the compute part of the application. For the communication part, we beneőt of the quality of the underlying SMPI layer that provides better estimations for the point-to-point communication of small messages and a tuned piecewise linear network model. Moreover the tag called async_small_thres is used as described in Section 4.1.

Figure 4.26 shows the impact of the whole set of modiőcations on the accuracy of the simulated executions of the LU factorization. These results, obtained on the bordereau cluster, have to be compared to those presented by The őrst outcome is a drastic reduction of the inaccuracy. With our initial implementation, the relative error linearly increased from -2.7% to 38.9% for class B and from -15.8% to 32.5% for class C. Now, the error varies between -9.5% and 11.5% for class B and between -6.1% and 8.1% for class C. Moreover, the linear increase of the error along with the number of processes, that indicated a bad simulation of the communication part, disappeared. We even note an opposite trend for class B. This can be explained by the fact that this conőguration of SMPI does not capture the time to copy data in memory in the MPI_Send function. This leads to a slight underestimation of the simulation time that increases as more small messages are exchanged for large numbers of processes.

As the bordereau cluster is now aging and prone to failures and suspect behaviors. Then we completed our study with results obtained on the more recent graphene cluster. Figure 4.27 shows the relative error achieved under the same experimental conditions as for Figure 4.26. As on the bordereau cluster, the error is in a narrow interval ranging from ś11.4% and -2%. Results for class B are even more stable. Again the underestimation of the simulated time should be compensated by taking memory copy into account. These results are not perfect yet, as some ŕuctuations or linear trends are still there, but there are a great improvement towards an accurate and trustworthy performance prediction tool. The reduction of around 10% of the overall inaccuracy allowed by the proposed modiőcations may sound common in the domain of trace-based simulation. But in our case, recall that we deal with time-independent traces that are based only on volumes and totally oblivious to both acquisition and replay platforms. For such traces a good accuracy is then harder to achieve. These results show that the more ŕexible approach ofered by time-independent traces becomes a sound alternative for prediction only thanks to these modiőcations. Some issues still have to be addressed, but most of them have been identiőed. Finally the factorization of the code, and thus of the eforts with those made on the SMPI project will help to improve the quality of our Time-Independent Trace replay tool.

For the last version of our framework we used all the features presented in Figure 4.9 related to communications. We took under consideration the cost to copy data in memory and the network congestion that may occur during the execution. Moreover the time-independent traces that are now used are acquired by instrumenting the whole benchmarks and not by applying selective instrumentation. Thus the traces include initialization and őnalization phases. show the actual and simulated execution times for various classes of the EP, DT, LU, and CG benchmarks on the graphene cluster. The presented execution times are average values over ten łcleanž runs, i.e., the standard deviation is negligible. The graphene is a cluster shared by multiple users and accessed through a resource management system. Then some experiments may be impacted by other jobs as network resources are shared.

To obtain these ten undisturbed runs, we usually had to execute three to four extra runs. Results for the EP and DT benchmarks show that the simulated execution times track the actual execution times closely, with maximum absolute relative error of 1.35% and 6.33% (corresponding to an absolute error of 2.2 ms only), respectively. As already mentioned, these two benchmarks are dominated either by computation or communication and are then simpler to simulate.

For the LU and CG benchmarks, the simulation is less accurate with maximum absolute and clock skew that requires a synchronization for the real trace. Real executions are also subject to system noise that does not occur in simulation causing some small discrepancies related to the computation time. This then prevents the observation of a perfect match. However, Figure 4.33 clearly shows that despite the small time scale, the simulation correctly renders the general communication pattern of this benchmark. One approach to identify which aspect of the simulation, computation or communication, is not accurately predicted is to fake a perfect simulation of the computation times. To do this, when we acquire the time-independent traces in regular mode, we save the duration of each compute action in addition of the volume of computed instructions. Then we replace the number of instructions with the duration times the processing rate. Thus the simulated times of the compute actions correspond exactly to the measured ones. The maximum absolute relative error is 2.82%. This indicates that the network model predicts the communication with good accuracy while the calibration of the computation part could be improved. This is the cost of using a single processing rate for the whole application while it depends on many factors such as cache misses, stalled cycles on any resource, etc. One approach would be to use a probabilistic model based on the measurements of the instance used for the calibration procedure but we are still looking for an appropriate solution.

The measured times of the compute actions include a small instrumentation overhead, then the relative error for the łperfectž simulation can be positive wihtout any issue with the communication model. However, the predictions for class B with 32 processes and class C with 128 processes are less accurate. A further analysis show that these instances handle two speciőc message sizes. For class B, 32 processes there are message of 204,000 and 212,160 bytes and for class C and 128 processes there are message sizes of 129,600 and 142,560 bytes. Thus we should focus in a future work to study exactly the simulation prediction on a range of message sizes from 129,000 to 215,000 bytes.

Another issue is that calibration for hierarchical networks is a complex procedure. The instances with 64 processes use two cabinets with 8% of the communication occuring between cabinets. With 128 processes it represents 22% of the communications. However, our network calibration mainly performs the ping-pong tests within a single cabinet. Moreover 99% of the exchanged messages are small, i.e., less than 65,536, and fall in the asynchronous category. Small variations in the calibration may then have a great impact of the simulation accuracy. However, the communication predictions remains pretty accurate for most of the instances.

Figure 4.35 shows the relative error between the real execution and the simulated times for the CG benchmark. We see a large error (close to 30%) with 128 processes while it remains under 9% for the other instances. Then we have to determine if the source of this gap comes from a bad estimation by the model or a problem during the actual execution. Our main suspect was the actual execution. First experiments showed a relative error for class C with 128 processes of 56%. Then we observed the communication pattern of the CG benchmark to understand better what was happening. We extracted the communication pattern for a small part of CG benchmark which is given in Figure 4.36. This sample last from time 0.178 to time 0.187. The red links correspond message sizes of 75,000 bytes and the blue ones of messages of 8 bytes. Thanks to the knowlegde of this particular communication pattern we adapted the mapping of processes to minimize communication across cabinets. The new mapping is the presented in Table 4 To őnd the source of the unexpected inaccuracy for instances with 128 processes, we analyzed the Gantt chart of the execution of a class B instance (Figure4.37). The execution time is 14.4 seconds while the simulated time is only of 9.9 seconds. We see two outstanding zones of MPI_Send and MPI_Wait. Such operations typically take few microseconds to less than a millisecond. Here they take 0.2 seconds. Our guess is that, due to a high congestion, the switch drops packets and slows down one (or several) process to the point where it stops sending until a timeout of .2 seconds is reached. Because of the communication pattern, blocking one process impacts all the other processes. This phenomenon occurs 24 times leading to a delay of 4.86 seconds. Without this bad behavior, the real execution would take 9.55 seconds, which is extremely close to the corresponding simulated time. The same phenomenon was observed for class C. This behavior of the interconnection network can be considered as a bug that needs to be őxed in a production environment.

So we are able to predict the performance of MPI applications and indicate the reasons when there are some performance issues. Our next step is to study how much time do we need to simulate these applications.

Simulation Time

The time to replay a time-independent trace is directly related to the number of actions. As mentioned in Section 3.3.5, the traces for the EP and DT are relatively small, up to a few hundreds of kilobytes, and are composed of a small number of actions, up to a few thousands for DT. Consequently EP and DT traces for 128 processes can be replayed in less than 0.2 seconds. The large number of actions in the LU traces (see Tables 3.27 and 3.28) implies a larger simulation time. Figure 4.38 presents the evolution of the simulation time as the number of processes increases for classes B and C instances of the LU benchmark. These timings were obtained on one node of the bordereau cluster with our prototype simulator. We should mention that this cluster is constituted by one cabinet, thus the format of the platform őle is similar to that detailed in We see that the simulation time grows linearly with the number of processes. Moreover it conőrms the relation between simulation time and number of actions. The average time to process with one million of actions is around 10 seconds.

The second version of our simulator was based on the SMPI layer which allowed us to save some internal context switches. These improvements lead to faster simulations. Figure 4.39 shows the simulation times. These timings were obtained on a laptop with a 2.5GHz Intel i5-3210M processor, 8 GiB of RAM and a Samsung SSD 830 hard disk. In this case we include results with 128 nodes because the time-independent were acquired from graphene cluster. This cluster is constituted by four cabinets and the format of the platform őle is similar to the one given in Figure 4.3. This has to ne noted as more complicated network topologies and other related features increase the simulation. Similarly, the simulation time grows linearly with the number of processes for the class B and up to 64 processes for class C instances. The simulation time is more important for the C-128 instance, whose trace size is more than 1 GiB. The average time to process one million of actions is around 8 seconds for instances with up to 64 processes. For 128 processes, the processing time is a slightly higher, around 11 seconds per million of actions. These data obtained for small and medium size instances allow us to estimate the simulation time from the size of the timeindependent trace. For instance, replaying the 1.45 TiB trace of a class E instance of the LU benchmark executed with 16,384 processes would take around 8 days on a single laptop (provided it has a large storage space). Indeed, such a huge trace contains roughly 70 billions of actions. This simulation time may seem prohibitive but, as mentioned earlier, neither the trace format nor the trace loading mechanism have been optimized for performance. Moreover, current eforts in the SimGrid project aim at enabling the distribution of a simulation of several compute nodes. Our time-independent replay framework would be a good candidate to beneőt of this capacity. Traces could be distributed on several disks to allow for concurrent accesses and the time to process the traces should be greatly reduced.

Finally, when we represent the real platform as accurate as it can be, such as in Figure 4.9 then the simulation time increases due to the simulation of őner details. This is the cost that we have to pay to get even better simulation accuracy. Figure 4.40 presents the corresponding simulation times.

Again the simulation time grows linearly with the number of processes for the class B and up to 64 processes for class C instances. The average time to proceed with one million of actions is 8.6 seconds for instances with up to 64 processes. With 128 processes, the processing time is higher, around 13 seconds per million of actions. It should be noted that the timeindependent traces for this case are 0.5% larger than the previous ones as we did not apply selective instrumentation, thus the traces correspond to the whole benchmark. The timings were also obtained on a laptop with a 2.5GHz Intel i5-3210M processor, 8 GiB of RAM and a Samsung SSD 830 hard disk.

Conclusion

In this chapter we presented all the aspects of our trace replay framework and its issues. We explained how to declare to our simulator a platform őle that represents the network topology of a cluster. The calibration procedure was detailed and analyzed step-by-step to be easy for a reader to understand and follow the same procedure. We also explained how to take into account the cache memory of a processor with regard to application and the problem size. The implemented simulators were analyzed in details and some examples were given to illustrate their capabilities. Moreover we mentioned some cases for which well-known proőling tools can not really provide enough data according to our requirements in comparison to the Minimal Instrumentation tool presented in the previous Chapter. We showed that our trace replay tool is able to predict the performance of MPI applications such as the EP, DT, LU, and CG benchmarks. The various implemented simulators were analyzed to show the improvement that occurred thanks to the applied modiőcations. We observed some performance issues and we identiőed the reasons that cause them. For the LU benchmark we know that we should integrate another model for the computation part to increase further the performance prediction accuracy. Moreover for the CG benchmark we őgured out an improved mapping approach to increase the performance and we identiőed hardware issues related to high congestion and drop packets from the side of switch. The performance prediction for most instances of the studied benchmarks is accurate and we know which parts should be improved. Finally, we presented the simulation time which is the time needed to execute a simulation. We discussed also that although the simulation time was improved because of some modiőcations, in the case that we want to declare a more analytical platform őle to improve the accuracy then we pay this cost by increasing the simulation time.

Chapter 5

Conclusions and Perspectives

Massive parallel computer systems are necessary in many scientiőc őelds. A lot of computational science applications are executed on clusters or supercomputers to provide results on many diferent topics such as weather modeling, life sciences, etc. Moreover, researchers are investigating various related őelds where the behavior of parallel computer systems is studied and new programming models to take into account the next generations of supercomputers are developed. The diiculty of achieving a good scale during the execution of some parallel applications while we increase the number of the processors is known and depends on many factors. Performance evaluation can provide an insight about the performance of an application and indicate possible bottlenecks. However, supercomputers are not available to all the researchers.

The work presented in this Thesis focuses on the performance evaluation and prediction of parallel applications. Simulation is a popular approach to obtain objective performance indicators platforms that are not at one's disposal. As presented in Chapter 1, there are numerous issues that increase the diiculty of our task. Our purpose was to acquire time-independent traces for an application and predict its performance through simulation. The prediction of the performance with good accuracy was really challenging and we had to address many issues.

In order to clarify the context of the current work, in Chapter 2 we presented some necessary concepts for our framework. Two micro-benchmarks were introduced, the OS Noise and SkaMPI. We used the őrst one to measure the noise caused by the Operating System on Grid'5000 platform. The second one was used to measure the latency of the network and some other data for the calibration of the communication. Moreover we mentioned the various benchmarks that constitute the NAS Parallel Benchmarks suite as our main work is based on the benchmarks EP, DT, LU and CG that belong to this suite. Three instrumentation methods, tracing, proőling and statistical proőling were introduced with the PAPI interface for handling the values of the hardware counters on the processors. We described also the advantages and disadvantages of the instrumentation methods. Similarly we analyzed the three methods for assessing the performance of applications on the resources, experiments, emulation, and simulation. Our simulator is built on top of the SimGrid simulation toolkit, thus we introduced further the SimGrid layers.

Although all the available of-line simulators which simulate MPI applications use timestamp traces, we developed a diferent approach. In Chapter 3 we detailed the time-independent trace acquisition framework. We proposed a new execution log format that is time independent. Thus, the acquisition procedure of this trace is totally decoupled from its replay. Heterogeneous and distributed platforms with processors that belong to the same processor family, e.g., i386 or amd64, can then be used to get traces without impacting the quality of the simulation which is not possible with other tool. We deőned the requirements for our framework and we evaluated accordingly most of the well-known and open-source proőling tools. Our requirements were decomposed to a score system to allow the evaluation of the tools and their easy comparison. Moreover we have developed our own proőling tool which is more eicient than similar tools for our framework. This tool is memory eicient, instruments only the necessary data and it provides some internal information from the MPI proőling layer that can not be extracted automatically from other tools. For the scientists that want to use some of the well-known proőling tools such as TAU and Score-P, we have developed the corresponding tools to extract the time-independent traces, however all the necessary information for some MPI collective communications are not provided by all the tools. We identiőed issues with instrumentation time overhead and a discrepancy of the measured number of instructions. We proposed a diferent instrumentation method to decrease these issues and we compared with the initial one. The issue with the extra measured amount of instructions was important because the computation workload was close to the one of the instrumented application but we improved it. One more important contribution of our framework is the option to use various execution modes. In this way we can use even diferent hardware or a smaller platform to acquire the time-independent traces and predict the performance of an application for a diferent platform. All the experiments were carried out on Grid'5000 experimental testbed. We support open-science, thus we have documented all of our work to be able for other scientists to build an appliance to acquire time-independent traces on Grid'5000 experimental infrastructure. The acquisition framework was evaluated with the various instrumentation methods and diferent clusters to show that the overhead is acceptable considering that the time-independent traces can be used for many diferent simulations. Finally we tested our framework for large-scale experiments and our tools behave pretty eicient. We succeed in applying our framework on 778 compute nodes in 18 clusters at 9 geographically distant sites of the Grid'5000 experimental testbed.

When the time-independent traces are acquired, the next step is to replay them with our of-line simulator to predict the performance of the corresponding application. For this task we developed a simulator based on the SimGrid simulation toolkit. Chapter 4 presents the time-independent trace replay framework. First of all we had to declare the topology of the cluster under some speciőcations to be handled correctly from the simulator. The calibration of the simulator is an important procedure. We presented one procedure for the computation calibration based on weighted average of the computed instructions and another one for the communication calibration which is based on a more complicated procedure with a piece-wise linear model. We have described the implementation of a proposed network model that improves on this situation within SMPI, and shown that SMPI-based simulations do a better job of tracking real-world behavior than those implemented using competing simulation toolkits. Afterwards we presented the incremental procedure of developing our of-line simulator with different simulation back-ends and we showed the improvements that occurred. We also identiőed the reasons that the performance of some benchmarks such as LU and CG were not the expected ones. We used a calibration method which is cache-aware and őgured out some switch issues. We have demonstrated that accurate modeling and performance prediction for a wide range of parallel applications requires proper consideration of many aspects of underlying communication architecture, including the breakdown of collective communication into their component point-to-point messages, the interconnect topology, and contention between competing messages that are sent simultaneously over the same link. Our priority in this work was the validation of the model at a small scale and for TCP over Ethernet networks. Such a tool would prove very useful for eforts such as the European Mont-Blanc project [113,[START_REF] Rajovic | The low-power architecture approach towards exascale computing[END_REF], which aims to prototype exascale platforms using low-power embedded processors interconnected by Ethernet.

Figure 2 . 1 :

 21 Figure 2.1: Internal deisgn of PAPI architecture.

Figure 2 . 2 :

 22 Figure 2.2: Exclusive and inclusive duration of a routine during proőling.

Figure 2 . 3 :

 23 Figure 2.3: Instrumentation during proőling.

Figure 2 . 4 :

 24 Figure 2.4: Adding probes at regular intervals for statistical proőling.

Figure 2 . 6 :

 26 Figure 2.6: SimGrid components.

Figure 3 . 1 :

 31 Figure 3.1: MPI code sample of some computation on a ring of processes (left) and its equivalent time-independent trace (right).

Figure 3 . 2 :

 32 Figure 3.2: Example of a split time-independent trace corresponding to a larger application execution with 128 processes.

Figure 3 . 3 :

 33 Figure 3.3: Overview of the Time Independent Trace Replay Framework.

Figure 3 . 4 :

 34 Figure 3.4: Example of tracing for two processes A and B that both call a function and exchange a message.

Listing 3 . 1 :

 31 Subset of the counters accessed by PAPI on a AMD processor. The f o l l o w i n g c o r r e s p o n d t o f i e l d s i n t h e PAPI_event_info_t s t r u c t u r e . Name Code A v a i l Deriv D e s c r i p t i o n ( Note ) PAPI_L1_DCM 0 x80000000 Yes No L e v e l 1 data c a c h e m i s s e s PAPI_L1_ICM 0 x80000001 Yes No L e v e l 1 i n s t r u c t i o n c a c h e m i s s e s PAPI_L2_DCM 0 x80000002 Yes No L e v e l 2 data c a c h e m i s s e s PAPI_L2_ICM 0 x80000003 Yes No L e v e l 2 i n s t r u c t i o n c a c h e m i s s e s . . . PAPI_TOT_IIS 0 x80000031 No No I n s t r u c t i o n s i s s u e d PAPI_TOT_INS 0 x80000032 Yes No I n s t r u c t i o n s completed PAPI_INT_INS 0 x80000033 No No I n t e g e r f l o p s PAPI_FP_INS 0 x80000034 Yes No F l o a t i n g p o i n t f l o p s PAPI_TOT_CYC 0 x8000003b Yes No T o t a l c y c l e s

  s s i b l e e v e n t s , 36 a r e a v a i l a b l e , o f which 8 a r e d e r i v e d .

Listing 3 . 3 :

 33 Handling MPI_Send function with MinI.

Figure 3 . 5 :

 35 Figure 3.5: Instrumentation skew for the three instrumented LU benchmarks.

Figure 3 . 6 :

 36 Figure 3.6: Instrumentation overhead for the reduced and minimal instrumented LU benchmarks.

Figure 3 . 7 :

 37 Figure 3.7: TAU -Entries example from an event őle.

Figure 3 . 8 :

 38 Figure 3.8: TAU -List of callbacks related to a call to the MPI_Send function and the corresponding time-independent trace.

Figure 3 . 9 :Figure 3 . 10 :

 39310 Figure 3.9: TAU -List of callbacks related to calls to the MPI_Irecv and MPI_Wait functions and the corresponding time-independent trace.

Figure 3 . 11 :

 311 Figure 3.11: TAU -List of callbacks related to a call to the MPI_Allreduce function and the corresponding time-independent trace.

Figure 3 . 12 :

 312 Figure 3.12: TAU -List of callbacks related to a call to the MPI_Alltoallv function.

Figure 3 . 13 :

 313 Figure 3.13: Score-P -List of callbacks related to a call to the MPI_Send function and the corresponding time-independent trace.

Figure 3 . 14 :

 314 Figure 3.14: Score-P -List of callbacks related to a call to the MPI_Irecv and MPI_Wait functions and the corresponding time-independent trace.

Figure 3 . 15 :

 315 Figure 3.15: Score-P -List of callbacks related to a call to the MPI_Bcast function and the corresponding time-independent trace.

Figure 3 . 16 : 5 Figure 3 . 17 :

 3165317 Figure 3.16: Score-P -List of callbacks related to a call to the MPI_Allreduce function and the corresponding time-independent trace.

Figure 3 . 18 : 1 int 2 PAPI_accum_counters

 31812 Figure 3.18: MinI ś Encoding MPI data types to an integer.

Figure 3 . 19 :

 319 Figure 3.19: MinI ś Example of code for the MPI_Send function and the corresponding timeindependent trace.

1 int 4 else 5 sprintf 6 } 1 bcast 4 1 2 Figure 3 . 20 :

 145612320 Figure 3.20: MinI ś Example of code for the MPI_Bcast function and the corresponding timeindependent trace.

1 int 2 PAPI_accum_counters

 12 MPI_Allreduce(sendbuf, recvbuf, count, datatype, op, comm){ , "%d comm_size %d\n",llrank,global); if(!this_type) sprintf(msg, "%d allReduce %d %lld %d\n", llrank,count,values[0]-ins1); else sprintf(msg, "%d allReduce %d %lld\n", llrank,count,values[0]-ins1,this_type);

Figure 3 . 21 :

 321 Figure 3.21: MinI ś Example of code for the MPI_Allreduce function and the corresponding time-independent trace.

Figure 3 . 22 :

 322 Figure 3.22: MinI ś Action corresponding to a call to MPI_Alltoallv in a time-independent trace.

Figure 3 . 23 :

 323 Figure 3.23: Example of the gathering algorithm for 16 nodes and arity of tree equal to four.

Figure 3 . 24 :

 324 Figure 3.24: Distribution of the acquisition time for diferent instances of the LU benchmark in the regular acquisition mode, on bordereau cluster with selective instrumentation.

Figure 3 . 25 :

 325 Figure 3.25: Distribution of the acquisition time for diferent instances of the LU benchmark in the regular acquisition mode on graphene cluster with TAU-reduced instrumentation.

Figure 3 . 26 :

 326 Figure 3.26: Evolution of the instrumentation overhead induced by the selective instrumentation and the TAU-reduced when the number of processes varies. Results obtained on graphene.

Figure 3 . 27 :

 327 Figure 3.27: Distribution of the acquisition time for diferent instances of the LU benchmark in the regular acquisition mode on graphene cluster with minimal instrumentation.

Figure 4 . 2 :

 42 Figure 4.2: Simplest platform őle describing the graphene cluster.

Figure 4 . 3 :

 43 Figure 4.3: Example -Platform őle for graphene cluster with network topology.

Figure 4 . 4 :

 44 Figure 4.4: Deployment őle for graphene cluster.

Figure 4 . 5 :

 45 Figure 4.5: Updating the processing power after the calibration of the LU benchmark.

Figure 4 . 6 :

 46 Figure 4.6: MPI_Send and MPI_Recv duration as a function of message size.

Figure 4 . 7 :

 47 Figure 4.7: The "hybrid" network model of SMPI in a nutshell.

Figure 4 . 8 :

 48 Figure 4.8: Conőguring the hybrid network model.

Figure 4 . 10 :

 410 Figure 4.10: MSG code for the compute action.

Figure

  Figure 4.11 shows the implementation of the send action whose format is <id> send <dst_id> <volume>. Line 3 retrieves the message size while line 6 creates the name of the mailbox in which the message will be sent. This name combines the rank of the sender and that of the receiver. Line 8 creates a MSG communication task and sends it in the mailbox. Finally line 11 calls a function that check is some asynchronous communications are completed and can be cleaned.

Figure 4 . 11 :

 411 Figure 4.11: MSG code for the send action.

Figure

  Figure 4.12 shows the MSG commands for the Isend action whose format is very similar to that of its synchronous equivalent <id> Isend <dst_id> <volume>. For sake of simplicity, we only comment the additional code needed to handle asynchronous communications. Each simulated process has access to a shared data structure, called globals, that comprises diferent counters and two dynamic arrays, isends and irecvs that respectively contain the pending asynchronous sends and receives. The MSG_task_isend function returns a handler (lines 9-10) that is pushed at the ends of the isends dynamic array (line 11).

Figure 4 . 12 :

 412 Figure 4.12: MSG code for the Isend action.

Figure 4 . 13 :

 413 Figure 4.13: MSG code for the Irecv action.

Figure 4 . 14 :

 414 Figure 4.14: MSG code for the wait action.

Figure 4 . 16 :

 416 Figure 4.16: SMPI version of the compute action.

Figure 4 . 17 :

 417 Figure 4.17: SMPI version of the send action.

Figure 4 . 18 :

 418 Figure 4.18: SMPI version of the Isend action.

Figure 4 . 19 :

 419 Figure 4.19: SMPI version of the Irecv action.

Figure 4 . 20 :

 420 Figure 4.20: SMPI version of the wait action.

Figure 4 . 21 :

 421 Figure 4.21: SMPI version of the bcast action.

  int main(int argc, char *argv[]){ smpi_replay_init(&argc, &argv); smpi_action_trace_run(NULL); smpi_replay_finalize(); return 0; }

Figure 4 . 22 :

 422 Figure 4.22: Comparison of simulated and actual execution time for the EP benchmark on the bordereau cluster.

Figure 4 . 23 :

 423 Figure 4.23: Comparison of simulated and actual execution time for the DT benchmark on the bordereau cluster.

Figure 4 . 24 :

 424 Figure 4.24: Comparison of simulated and actual execution time for the LU benchmark on the bordereau cluster.

Figures 4. 22

 22 Figures 4.22, 4.23, and 4.24 show the accuracy of the time-independent trace replay by comparing the actual execution time respectively of the EP, DT and LU benchmarks on the bordereau cluster for various classes with the simulated time obtained with SimGrid. EP (Embarrassingly Parallel) consists of only computations, DT (Data Traic) consists of only communications, while LU (LU Factorization) mixes computation and communication. For DT, the class refers not only to the data size but also the number of communicating processes: classes A, B, and C involve 21, 43, and 85 processes respectively. Moreover three diferent communication graphs

  Figures 4.22, 4.23, and 4.24 show the accuracy of the time-independent trace replay by comparing the actual execution time respectively of the EP, DT and LU benchmarks on the bordereau cluster for various classes with the simulated time obtained with SimGrid. EP (Embarrassingly Parallel) consists of only computations, DT (Data Traic) consists of only communications, while LU (LU Factorization) mixes computation and communication. For DT, the class refers not only to the data size but also the number of communicating processes: classes A, B, and C involve 21, 43, and 85 processes respectively. Moreover three diferent communication graphs

Figure 4 . 25 :

 425 Figure 4.25: Evolution with regard to the number of processes of the relative error between execution and simulated times for the execution of the LU factorization on the bordereau cluster.

Figure 4 .

 4 Figure 4.25 shows the results of Figure4.24 from a diferent perspective. It shows the evolution of the relative error between the time to compute a LU factorization and its simulated counterpart when the number of involved processes vary. We see that the inaccuracy of the simulated version is not stable, but increases rather linearly with the number of processes. Moreover, our tool underestimates the execution time for small number of processes, i.e., when each process owns a larger share of data, and then overestimates the execution as the number of processes grows.This inaccuracy may have diferent origins related either to computations or communications. For instance it may come from the discrepancy of the measured number of instructions. Indeed this discrepancy directly impacts the calibration of the replay tool that determines the rate at which each machine can process instructions. Among other potential sources, we assume that every part of the application can be processed at the same rate while it may not be the case for some applications, due to cache ainity for instance. However, the general trend shown by Figure4.25 seems to indicate that the main source of inaccuracy comes from a bad estimation of communication times. To conőrm this impression, we made simulations in which each compute action was replaced by a delay that corresponds exactly to the time spent for this compute part during the trace acquisition. The obtained results, in which computations are thus perfectly simulated, show a similar trend. The most probable source might then be

Figure 4

 4

Figure 4 . 26 :

 426 Figure 4.26: Evolution w.r.t. the number of processes of the relative error between execution and simulated times for the execution of the LU factorization with the new replay framework. Results obtained on the bordereau cluster.

Figure 4 . 27 :

 427 Figure 4.27: Evolution w.r.t. the number of processes of the relative error between execution and simulated times for the execution of the LU factorization with the new replay framework. Results obtained on the graphene cluster.

Figures 4. 28

 28

  ,4.29,4.30 and 4.31

Figure 4 . 28 :

 428 Figure 4.28: Comparison of simulated and actual execution time for the EP benchmark on the graphene cluster.

Figure 4 . 29 :

 429 Figure 4.29: Comparison of simulated and actual execution time for the DT benchmark on the graphene cluster.

Figure 4 .

 4 [START_REF] Gait | A debugger for concurrent programs[END_REF] presents the results of such a łperfectž simulation.

Figure 4 . 34 :

 434 Figure 4.34: Evolution w.r.t. the number of processes of the relative error between execution and perfect simulation for the execution of the LU benchmark.

Figure 4 . 35 :

 435 Figure 4.35: Evolution w.r.t. the number of processes of the relative error between execution and simulated times for the execution of the CG benchmark.

Figure 4 . 36 :

 436 Figure 4.36: Communication pattern of a class C instance of CG for 128 processes.

Figure 4 . 37 :

 437 Figure 4.37: Two seconds Gantt-chart of the real execution of a class B instance of CG for 128 processes.

Figure 4

 4

Figure 4 . 38 :

 438 Figure 4.38: Evolution of the trace replay time with the number of processes executing a LU benchmark with the prototype simulator.

Figure 4 . 39 :

 439 Figure 4.39: Evolution of the trace replay time with the number of processes executing a LU benchmark with the simulator based on the SMPI layer.

Figure 4 .

 4 Figure 4.40: Evolution of the trace replay time with the number of processes executing a LU benchmark with our SMPI simulator and calibrating all the network parameters.

  .2.

	0 init	1 init		127 init
	0 compute 1e6	1 recv 0		127 recv 2
	0 send 1 1e6 0 recv 3	1 compute 1e6 1 send 2 1e6	...	127 compute 1e6 127 send 0 1e6
	...	...		...
	0 finalize	1 finalize		127 finalize

Table 3 .

 3 1: Time-independent counterparts of the actions performed by each process involved in an MPI application.

	MPI actions	Trace entry
	CPU burst	<id> compute <volume>
	MPI_Send	<id> send <dst_id> <volume>
	MPI_Isend	<id> Isend <dst_id> <volume>
	MPI_Recv	<id> recv <src_id>
	MPI_Irecv	<id> Irecv <src_id> <volume>
	MPI_Broadcast	<id> bcast <volume>
	MPI_Reduce	<id> reduce <vcomm> <vcomp>
	MPI_Reduce_scatter <id> reduceScatter <recv_counts>
		<vcomp>
	MPI_Allreduce	<id> allReduce <vcomm> <vcomp>
	MPI_Alltoall	<id> allToAll <send_volume> <receive_volume>
	MPI_Alltoallv	<id> allToAllv <send_buffer> <send_counts>
		<send_displs> <receive_buffer> <recv_counts>
		<recv_displs>
	MPI_Gather	<id> gather <send_buffer> <recv_buffer>
	MPI_Allgatherv	<id> allGatherV <send_count> <recv_counts>
		<recv_disps>
	MPI_Barrier	<id> barrier
	MPI_Wait	<id> wait
	MPI_Waitall	<id> waitAll
	MPI_Init	<id> init
	MPI_Finalize	<id> finalize

Table 3 .

 3 2: The őrst lines of the time-independent traces of LU benchmark, class C, 4 nodes.

	0 compute 10632621	1 compute 10633358
	0 compute 244390418	1 compute 244372181
	0 compute 11612863	1 compute 9328093
	0 compute 6492893	1 compute 2284893
	2 compute 10633400	3 compute 10632459
	2 compute 244372720	3 compute 244394098
	2 compute 9328049	3 compute 9327954
	2 compute 2284855	3 compute 6492794
		Min cycles Max cycles Mean cycles std. deviation
	Papi_start/stop	9	26381	12	26.73
	Papi_read	111	28568	114	81.9
	Addition	235	9537		254	10

Table 3 .

 3

	Nodes	Execution time	Execution time	Time Overhead
		w/o tracing (in sec.) w tracing (in sec.)	(in %)
	4	685.18	696	1.58
	8	345.2	362.5	5.01
	16	184	195.4	6.2
	32	100.1	106.6	6.5
	64	53.08	56.8	7

3: Overhead in cycles of basic PAPI operations as measured with papi_cost

Table 3 .

 3

	LU, class C Nodes Size (in MB) 4 11 8 23 16 46 32 94 64 193	LU, 32 nodes Class Size (in MB) A 36 B 59 C 94 D 299

4: Time overhead of PAPI for the LU benchmark, Class C. other classes, Class D works on larger matrices (14 times bigger than class C) and needs more iterations (300 vs. 250). The observed can then easily be justiőed and we give 1 point on this criterion.

Table 3 .

 3

5: Space overhead of PAPI for the LU benchmark.

Table 3 .

 3 6: Principal Hardware/OS combinations supported by PAPI.

		Operating	Requirements
		System
	AMD Athlon/Opteron,	Linux 2.2,	Mikael Pettersson's PerfCtr
	Intel thru Pentium III,	2.4,2.6	kernel patch for Linux
	Pentium M, Core2 Series		(included)
	AMD Opteron,	Linux 2.6	Stephane Eranian's
	Intel Pentium M,		Perfmon2 kernel patch
	Core2 Series		from sourceforge
	Intel Pentium IV, D	Linux 2.2,2.4,2.6 Mikael Pettersson's PerfCtr
			2.6.x kernel patch
			for Linux (included)
	Intel Itanium II,	Linux 2.4, 2.6	none
	Montecito, Montvale

Table 3 .

 3 [START_REF] Roth | Deconstructing the overhead in parallel applications[END_REF] summarizes the results of the evaluation of PAPI.

	Proőling features Quality of output Overheads Quality of Software Total
	4	3	6	11	24

Table 3 .

 3

7: Summary of the evaluation of PAPI.

Table 3 .

 3

	, class C

8: Time overhead of Scalasca for the LU benchmark, Class C.

Table 3 .

 3 1 point). It depends on libbfd and libiberty libraries but both libraries are part of 9: Space overhead of Scalasca for the LU benchmark. standard distributions (1 point). Furthermore Scalasca is released under the New BSD license which is a GPL-compatible free software license and has been vetted as open source by the Open Source Initiative (1 point). According to Table3.10 Scalasca is compatibile with a lot of hardware (1 point). Scalasca can trace applications which are implemented in C/C++ and Fortran (3 points) and is compatible with MPICH and OpenMPI (1 point). The documentation is well written and covers a lot of topics about the installation and usage of the tool (1 point). Finally the project is active (1 point) and there is a team providing support to the users (1 point).

	LU, class C Nodes Size (in MB) 4 2,100 8 2,200 16 2,500 32 2,900 64 3,900		LU, 32 nodes Class Size (in MB ) A 476 B 1,100 C 2,900 D 36,000
	Hardware	Operating	Requirements
		System
	AMD Athlon/Opteron,
	Intel thru Pentium III,	x86-Linux
	Pentium M, Core2 Series
	AMD Opteron,
	Intel Pentium M,	x86_64-Linux PAPI, PDToolkit,
	Core2 Series		libbfd,libiberty,Qt4
	Intel Pentium IV, D
	Intel Itanium II,	IA_64-Linux
	Montecito, Montvale

Table 3 .

 3 10: Principal Hardware/OS combinations supported by Scalasca.

Table 3 .

 3 [START_REF] Brewer | Proteus: A high-performance parallel-architecture simulator[END_REF] shows the overall results of the evaluation of Scalasca.

	Proőling features Quality of output Overheads Software Quality Total
	6	2	8	11	27

Table 3 .

 3 11: Summary of the evaluation of Scalasca.TAU TAU[START_REF] Shende | The Tau Parallel Performance System[END_REF][START_REF]Tuning and Analysis Utilities[END_REF] is an advanced proőling and tracing toolkit for the performance analysis of parallel programs. It is developed by the Department of Computer and Information Science, University of Oregon, the Forschungszentrum Jülich, Jülich Supercomputing Centre, ZAM and the Advanced Computing Laboratory, Los Alamos National Laboratory. The evaluation is based on TAU version 2.21 while the last one is version 2.22.2 which suppors new technologies and processors and a new implementation of the MPI wrapper. According to our experiments these changes do not inŕuence the current results.

Table 3 .

 3 1 point). 12: Time overhead of TAU for the LU benchmark, Class C.

			LU benchmark, class C
	Nodes	Execution time	Execution time	Time Overhead
		w/o tracing (in sec.) w tracing (in sec.)	(in %)
	4	685.18	983	43.46
	8	345.2	493.5	42.96
	16	184	239.3	30.05
	32	100.1	128.8	28.67
	64	53.08	71.1	33.94
	LU, class C Nodes Size (in MB) 4 5,100 8 5,400 16 6,000 32 7,300 64 9,900	LU, 32 nodes Class Size (in MB) A 1,300 B 2,700 C 7,300 D 87,200

Table 3 .

 3 13: Space overhead of TAU for the LU benchmark.

Software quality

The installation of TAU is easy. It can be conőgured thanks to compilation ŕags (1 point). It has a software dependency on the PDToolkit which can be respected (1 point). TAU is free under BSD style license which is GPL-compatible (1 point). According to

Table 3 .

 3 14 it supports various hardware conőgurations (1 point). Moreover all the programming languages C/C++ and Fortran (3 points) and the major MPI implementations such as MPICH and OpenMPI (1 point) are supported. The oicial web site gives access to manuals about usage and installation of this tool (1 point). Finally the project is active (1 point) and there is a team for answering any question (1 point).

	Hardware	Operating	Requirements
		System
	AMD Athlon/Opteron,
	Intel thru Pentium III,	x86-Linux
	Pentium M, Core2 Series
	AMD Opteron,
	Intel Pentium M,	x86_64-Linux PAPI, PDToolkit (optional)
	Core2 Series
	Intel Pentium IV, D
	Intel Itanium II,	IA_64-Linux
	Montecito, Montvale

Table 3 .

 3 14: Principal Hardware/OS combinations supported by TAU.The overall results of the evaluation are presented in Table3.15.

	Proőling features Quality of output Overheads Software Quality Total
	8	2	5	11	26

Table 3 .

 3

15: Summary of the evaluation of TAU.

Table 3 .

 3 [START_REF] Sopeju | AutoSCOPE: Automatic Suggestions for Code Optimizations using PerfExpert[END_REF] shows that the time overhead is less than 50% (2 points). Moreover the overhead decreases linearly as the number of the processes increases (3 points).

	Nodes	Execution time	Execution time	Time Overhead (in %)
		w/o tracing (in sec.) w tracing (in sec.)	(in %)
	4	685.16	915.919	33.67
	8	345.2	443.59	28.5
	16	184	220.78	19.99
	32	100.1	109.95	9.84
	64	53.08	58.16	9.57

Table 3 .

 3

[START_REF] Sopeju | AutoSCOPE: Automatic Suggestions for Code Optimizations using PerfExpert[END_REF]

: Time overhead of Score-P for the LU benchmark, Class C.

Table 3 .

 3 .19. 18: Principal Hardware/OS combinations supported by Score-P.

	Hardware		Operating	Requirements
			System
	AMD Athlon/Opteron,
	Intel thru Pentium III,	x86-Linux
	Pentium M, Core2 Series
	AMD Opteron,
	Intel Pentium M,	x86_64-Linux PAPI, PDToolkit
	Core2 Series
	Intel Pentium IV, D
	Intel Itanium II,	IA_64-Linux
	Montecito, Montvale
	Proőling features Quality of output Overheads Software Quality Total
	7	2	8	11	28

Table 3 .

 3

19: Summary of the evaluation of Score-P.

Table 3 .

 3 .21. When the number of processes is doubled, the size of the traces is 20: Time overhead of MinI for the LU benchmark, Class C. increased linearly (1 point). With regard to the problem size, by changing only the class of the problem, the size of the traces is increased linearly (1 point).

	Nodes	Execution time	Execution time	Time Overhead (in %)
		w/o tracing (in sec.) w tracing (in sec.)	(in %)
	4	685.18	695.8	1.55
	8	345.2	360	4.29
	16	184	191.63	4.15
	32	100.1	105.2	5.09
	64	53.08	55.8	5.12
	LU, class C Nodes Size (in MB) 4 20 8 49 16 120 32 257 64 549	LU, 32 nodes Class Size (in MB) A 99 B 161 C 257 D 804

Table 3 .

 3

	Hardware	Operating	Requirements
		System
	AMD Athlon/Opteron,
	Intel thru Pentium III,	x86-Linux
	Pentium M, Core2 Series
	AMD Opteron,
	Intel Pentium M,	x86_64-Linux	PAPI
	Core2 Series
	Intel Pentium IV, D
	Intel Itanium II,	IA_64-Linux
	Montecito, Montvale

21: Space overhead of MinI for the LU benchmark.

Software quality MinI achieves a score of 10 points regarding the software quality criterion. There is no need to install the tool, just to compile it (1 point). There is no dependency except on PAPI (1 point). MinI is released under the LGPL license (1 point). Table

3

.

[START_REF] Frost | Mpich performance characteristics and considerations[END_REF]

shows that MinI has no hardware compatibility issues (1 point). It supports C/C++ and Fortran programming languages (3 points). The MinI tool is developed according to the MPI standards, thus it supports both MPICH and OpenMPI (1 point). There are instructions on how to compile and use it (1 point). Moreover this project is active (1 point) there is a support team for answering any question (1 point).

Table 3 .

 3 22: Principal Hardware/OS combinations supported by MinI.Finally we aggregate the results of the evaluation in the Table3.23.

	Proőling features Quality of output Overheads Software Quality Total
	7	3	6	10	26

Table 3 .

 3 23: Summary of the evaluation of MinI.

Table 3 .

 3 .24.

	Tool	Proőling Quality of	Space and	Quality of Total
		features	output	Time Overheads Software
	PerfBench	2	0	0	5	7
	PerfSuite	2	0	0	10	12
	MpiP	2	0	0	11	13
	IPM	3	0	0	11	14
	MPE	4	1	2	10	17
	PAPI	4	3	6	11	24
	Extrae	7	2	5	11	25
	VampirTrace	7	2	5	11	25
	MinI	7	3	6	10	26
	TAU	8	2	5	11	26
	Scalasca	6	2	8	11	27
	Score-P	7	2	8	11	28

24: Summary of the evaluation of the studied instrumentation tool.

Table 3 .

 3 25: Comparing the gathering tools kaget and trace_gather for the LU benchmark, 64 nodes, and classes B and C.

				Gathering time for LU (in sec)
			B-64			C-64
		Kaget Trace_gather	Kaget T race_gather	Kaget Trace_gather	Kaget T race_gather
	min 12.33	4.93	2.5	19.27	10.06	1.92
	max 13.98	5.7	2.45	23.98	10.4	2.31
	avg 13.07	5.32	2.46	21.6	10.26	2.11
	std	0.51	0.25	2.04	1.51	0.12	12.58

Table 3 .

 3 26: TAU trace sizes and number of actions for diferent instances of the LU benchmark.

			TAU trace size (in MB)
	#Processes	Selective Instrumentation	TAU-reduced
		Class B Class C Class B Class C
	8	334	531	188	298
	16	741	1,200	450	714
	32	1,600	2,500	973	1,600
	64	3,200	5,100	2,100	3,300
	128	6,600	11,000	4,300	6,800

Table 3 .

 3 27: Sizes of time-independent traces and number of actions for diferent instances of the LU benchmark for the prototype framework.

	#Processes	Trace size (in MiB) #Actions (in millions) Class B Class C Class B Class C
	8	29.9	48.4	2.03	3.23
	16	72.6	117	4.87	7.75
	32	161.3	256.8	10.55	16.79
	64	344.9	552.5	22.73	36.17

Table 3 .

 3 28: Sizes of time-independent traces and number of actions for diferent instances of the LU benchmark produced with the MinI tool.

	#Processes	Trace size (in MB) #Actions (in millions) Class B Class C Class B Class C
	8	29.6	48	2.04	3.24
	16	72	116.8	4.89	7.78
	32	159	255	10.6	16.87
	64	339	550	22.83	36.33
	128	711	1,200	47.3	75.25

Table 3 .

 3 29: Executing the instrumented LU benchmark using folding on a single node.

		Time in minutes / Memory footprint in GiB
	Instance	TAU	Minimal	Scalasca	Score-P
		Reduced Instrumentation
	B -256 2.8 / 21.4	1.9 / 1.65	2.1 / 2.8	1.8 / 5.2
	C -1024	N/A	12.9 / 7.95	16.3 / 12.9	27.3 / 29.3
	D -256	N/A	47.4 / 15.4	55.2 / 16.9 > 420 / N/A

Table 3 .

 3 30: Evolution of the execution time of instrumented class B instance of EP, DT and LU executed by 64 processes (43 for DT) with regard to the acquisition mode. Results obtained on the bordereau and gdx clusters using one core per node.

		Acquisition mode	R	F-2	F-4	F-8	F-16	F-32	C-2	CF-(2,2) CF-(2,4) CF-(2,8) CF-(2,16)
		Number of nodes	64	32	16	8	4	2	(32,32)	(16,16)	(8,8)	(4,4)	(2,2)
	LU	Execution Time (in sec.) 20.73 52.96 88.66 179.07 347.27 689.18 Ratio to regular mode 1 2.55 4.28 8.64 16.75 33.25	37.54 1.81	79.19 3.82	134.05 6.47	277.25 13.37	505.64 24.39
	EP	Execution Time (in sec.) 1.99 Ratio to regular mode 1	4.06 2.04	8.33 4.18	16.29 8.18	36.42 18.3	69.05 34.7	2.67 1.34	5.38 2.7	10.77 5.41	21.52 10.81	43.09 21.65
		Acquisition mode	R	F-2.625 F-5.25 F-10.5 F-21	C-2	CF-(2,2.625) CF-(2,5.25) CF-(2,10.5) SF-(2,21)
		Number of nodes	43	16	8	4	2	(22,21)	(8,8)		(4,4)	(2,2)	(1,1)
	DT	Execution Time (in sec.) 4.56 Ratio to regular mode 1	12.62 2.76	18.67 4.09	32.2 7.06	58.8 12.89	10.66 2.33	31.277 6.86	41.06 9	47.49 10.4	66.93 14.67

Table 4 .

 4 .1. It improved the execution time of the benchmark and also reduced the relative error from 56% to 30%. 1: Speciőc process mapping on nodes of the graphene cluster for the CG benchmark.

	Cabinet id	Nodes
	0	1-28, 33-34, 65-66, 97-98
	1	35-62
	2	67-92
	3	29-32,93-96,99-128

Contents

power="1E9" bw="1.25E8" lat="15E-6" <cluster id="cluster" prefix="c-" suffix=".me" radical="0-3" </platform> <platform version="3"> <?xml version='1.0'?> bb_bw="1.25E9" bblat="15e-6"/> <!DOCTYPE platform SYSTEM "simgrid.dtd"> <!DOCTYPE platform SYSTEM "simgrid.dtd"> <platform version="3"> <?xml version='1.0'?> <process host="c-0.me" function="0"/> <process host="c-1.me" function="1"/> <process host="c-2.me" function="2"/> <process host="c-3.me" function="3"/> </platform>

Realistic Platform Descriptions

Reflecting Hierarchical Topologies Before illustrating on an example how to describe compute clusters in order to replay timeindependent, we recall the motivations that led to the proposition of a scalable multi-purpose representation of network topologies in the SimGrid toolkit [106]. The key concept is to provide users with the ability to adapt the representation to their needs. Most current distributed systems mainly rely on three types of possible interconnected and mixed networks:

ś System and local area networks (SAN and LAN) are organized in a very hierarchical way or with large switches; ś National Research and Education Networks (NRENs) interconnect systems through their gateways on a higher level of networks, called backbone which are scattered at national scale; ś Privately and idenpendently managed networks. Such networks are interconnected in a hierarchical way ans large scale distributed systems can thus be seen as a hierarchical aggregation of networks. Each network is independent of the others and can have a diferent structure, hence the name of Autonomous Systems (AS). Each AS can be connected with lower or higher level ASes. For each AS there is at least one gateway to compute the route between two ASes even if the one is on higher level. There are various graph representations for the network topology and routing such as Flat, Dijkstra [START_REF] De Munck | Improving the scalability of simgrid using dynamic routing[END_REF], Floyd [START_REF] De Munck | Improving the scalability of simgrid using dynamic routing[END_REF] etc., but one main problem is that they do not exploit the hierarchy and the regularity of the Such functions are more complex, as shown in Figure 4.15. Moreover, the MSG API forces us to make some unrealistic assumptions. For instance, a ŕat tree rooted in process of rank 0 is used to implement the broadcast operation, while actual MPI implementations adapt the difusion algorithm to the message size and number of participating processes, and can be initiated by any process. This implementation őrst checks that the size of the MPI communicator has been declared (thanks to a comm_size action in the trace) on lines 13-14. Then each process builds a speciőc mailbox name to receive data from the root process (lines 18 and 26 or 36). The behavior is diferent for the process of rank 0 that sends asynchronously a message to every other processes and then waits for their reception (lines [START_REF] Pőster | Aspects of the inőniband architecture[END_REF][START_REF] Lusk | A high-performance, portable implementation of the mpi message passing interface standard[END_REF][START_REF] Frost | Mpich performance characteristics and considerations[END_REF][START_REF] Gabriel | Open MPI: Goals, concept, and design of a next generation MPI implementation[END_REF][START_REF] Hoeŕer | Netgauge: A network performance measurement framework[END_REF][START_REF] Beckman | Benchmarking the efects of operating system interference on extreme-scale parallel machines[END_REF][START_REF]Sequoia Benchmarks[END_REF][START_REF] Reussner | SKaMPI: a Comprehensive Benchmark for Public Benchmarking of MPI[END_REF][START_REF] Luszczek | Introduction to the hpc challenge benchmark suite[END_REF][START_REF]The Top 500[END_REF][START_REF] Dongarra | Toward a new metric for ranking high performance computing systems[END_REF][START_REF] Bailey | The nas parallel benchmarks[END_REF][START_REF] Browne | A Portable Programming Interface for Performance Evaluation on Modern Processors[END_REF][START_REF] Abrams | Design of a measurement instrument for distributed systems[END_REF][START_REF] Gait | A debugger for concurrent programs[END_REF]. The other processes just synchronously receive the sent message (line 37). relative error of 10.17% and 29.95% respectively.Figure 4.32 is similar to Figures 4.26 and 4.27 but with a well calibrated network model. We see another improvement in terms of accuracy with regard to the version and even more stable predictions. However, the simulated execution time is still underestimated. A next step, detailed in the next section is to attempt to identify (and remedy) the sources of the inaccuracies observed for the LU and CG benchmarks.

Sources of Inaccuracy

To better understand the sources of inaccuracy in the presented simulation results, we further analyze those obtained for the LU benchmark. The LU iterative benchmark alternates computations and communications at a high rate. Similar or close completion times as shown by Figure 4.30 may hide a bad, but lucky, estimation of each component of the execution time. To be sure that estimation errors on computation times are not compensated by errors on the communication times, we propose to compare (a part of) the Gantt charts of the actual and simulated executions. Such a comparison is given by Figure 4.33 that shows a period of 0.2 seconds of the execution of the LU benchmark with 32 processes. The upper part of this őgure displays the actual execution while the lower corresponds to the simulation of the same phase with the simulation.

Perspectives

The work of this Thesis can be the base for the next version of our framework. A new computation model could be introduced to predict more accurate the performance as the power rate of a real execution usually is not stable. Our framework can support more MPI calls as both the simulator and our proőling tool can be easily extended and are available to the potential users. Moreover the simulation of a real application is one of our priorities. A next step will be to analyze its adequacy for simulating larger platforms when we can get access to such large machines for experimental purposes. The study should then extend to other kinds of interconnects (such as Inőniband) and more complicated topologies. One signiőcant advantage is that the our time-independent traces used for the current work can be simulated with Inőniband network model. In general some techniques should be investigated to decrease the trace sizes and simulation time as we intend to simulate large scale instances of applications and we should avoid a huge simulation time specially compared to the real execution. In this case the parallel simulation which is under investigation could help to speed up our framework. While experimental data have been collected by hand for the present analysis, the need to collect more traces to test against various platforms is a strong incentive to automate this task. Thus, one future work will be to build a systematic validation/invalidation framework based on automatic collection of traces.

A challenge would be to investigate our framework model with regard to multicore processors and take into account the shared cache memory and all the related issues.

The proposed time-independent replay framework is freely distributed as part the SimGrid project under the LGPL license. It can be downloaded from http://simgrid.gforge.inria. fr/download.html. Moreover, the process to acquire a time-independent is fully described in [START_REF] Markomanolis | Time-Independent Trace Acquisition Framework ś A Grid'5000 How-to[END_REF].