X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rce2015.git/blobdiff_plain/5935936993555893be36577dd27573642cef4d87..ee8c8a98d36d034e0ee2919355fc0372591e6943:/paper.tex?ds=inline diff --git a/paper.tex b/paper.tex index c959ace..f1e391c 100644 --- a/paper.tex +++ b/paper.tex @@ -113,7 +113,7 @@ %% execution time. %% The simulations confirm the real results previously obtained on different real multi-core architectures and also confirm the efficiency of the asynchronous Multisplitting algorithm on distant clusters compared to the synchronous GMRES algorithm. -The behavior of multi-core applications is always a challenge to predict, especially with a new architecture for which no experiment has been performed. With some applications, it is difficult, if not impossible, to build accurate performance models. That is why another solution is to use a simulation tool which allows us to change many parameters of the architecture (network bandwidth, latency, number of processors) and to simulate the execution of such applications. +The behavior of multi-core applications always proves quite challenging to predict, especially with a new architecture for which no experiment has yet been performed. With some applications, it is difficult, if not impossible, to build accurate performance models. That is why another solution is to use a simulation tool which allows us to change many parameters of the architecture (network bandwidth, latency, number of processors) and to simulate the execution of such applications. In this paper we focus on the simulation of iterative algorithms to solve sparse linear systems. We study the behavior of the GMRES algorithm and two different variants of the multisplitting algorithms: using synchronous or asynchronous iterations. For each algorithm we have simulated different architecture parameters to evaluate their influence on the overall execution time. The simulations confirm the real results previously obtained on different real multi-core architectures and also confirm the efficiency of the asynchronous multisplitting algorithm on distant clusters compared to the GMRES algorithm. @@ -133,11 +133,11 @@ complex parallel applications operating on a large amount of data. Unfortunately, users (industrials or scientists), who need such computational resources, may not have an easy access to such efficient architectures. The cost of using the platform and/or the cost of testing and deploying an application -are often very important. So, in this context it is difficult to optimize a +are often very important. So, in this context, it is difficult to optimize a given application for a given architecture. In this way and in order to reduce the access cost to these computing resources it seems very interesting to use a -simulation environment. The advantages are numerous: development life cycle, -code debugging, ability to obtain results quickly\dots{} In counterpart, the simulation results need to be consistent with the real ones. +simulation environment. The advantages are numerous: life cycle development, +code debugging, ability to obtain results quickly\dots{} In return, the simulation results need to be consistent with the real ones. In this paper we focus on a class of highly efficient parallel algorithms called \emph{iterative algorithms}. The parallel scheme of iterative methods is quite @@ -148,7 +148,7 @@ data dependencies to/from its neighbors and to iterate this process until the convergence of the method. Several well-known studies demonstrate the convergence of these algorithms~\cite{BT89,bahi07}. In this processing mode a task cannot begin a new iteration while it has not received data dependencies -from its neighbors. We say that the iteration computation follows a +from its neighbors. The iteration computation is said to follow a \textit{synchronous} scheme. In the asynchronous scheme a task can compute a new iteration without having to wait for the data dependencies coming from its neighbors. Both communications and computations are \textit{asynchronous} @@ -160,14 +160,14 @@ case, it appears that the asynchronous iterative scheme can significantly reduce overall execution times by suppressing idle times due to synchronizations~(see~\cite{bahi07} for more details). -Nevertheless, in both cases (synchronous or asynchronous) it is very time -consuming to find optimal configuration and deployment requirements for a given +Nevertheless, in both cases (synchronous or asynchronous) it is extremely time +consuming to find optimal configurations and deployment requirements for a given application on a given multi-core architecture. Finding good resource allocations policies under varying CPU power, network speeds and loads is very challenging and labor intensive~\cite{Calheiros:2011:CTM:1951445.1951450}. This problematic is even more difficult for the asynchronous scheme where a small parameter variation of the execution platform and of the application data can -lead to very different numbers of iterations to reach the convergence and so to +lead to very different numbers of iterations to reach the convergence and consequently to very different execution times. In this challenging context we think that the use of a simulation tool can greatly leverage the possibility of testing various platform scenarios. @@ -180,7 +180,7 @@ validity of this approach we first compare the simulated execution of the Krylov multisplitting algorithm with the GMRES (Generalized Minimal RESidual) solver~\cite{saad86} in synchronous mode. The simulation results allow us to determine which method to choose for a given multi-core architecture. -Moreover the obtained results on different simulated multi-core architectures +Moreover, the obtained results on different simulated multi-core architectures confirm the real results previously obtained on real physical architectures. More precisely the simulated results are in accordance (i.e. with the same order of magnitude) with the works presented in~\cite{couturier15}, which show that @@ -189,8 +189,8 @@ scale clusters. Simulated results also confirm the efficiency of the asynchronous multisplitting algorithm compared to the synchronous GMRES especially in case of geographically distant clusters. -In this way and with a simple computing architecture (a laptop) SimGrid allows us -to run a test campaign of a real parallel iterative applications on +Thus, with a simple computing architecture (a laptop) SimGrid allows us +to run a test campaign of real parallel iterative applications on different simulated multi-core architectures. To our knowledge, there is no related work on the large-scale multi-core simulation of a real synchronous and asynchronous iterative application. @@ -206,21 +206,21 @@ concluding remarks and perspectives. \section{The asynchronous iteration model and the motivations of our work} \label{sec:asynchro} -Asynchronous iterative methods have been studied for many years theoretically and +Asynchronous iterative methods have been studied for many years both theoretically and practically. Many methods have been considered and convergence results have been proved. These methods can be used to solve, in parallel, fixed point problems (i.e. problems for which the solution is $x^\star =f(x^\star)$). In practice, asynchronous iteration methods can be used to solve, for example, linear and -non-linear systems of equations or optimization problems, interested readers are +non-linear systems of equations or optimization problems. Interested readers are invited to read~\cite{BT89,bahi07}. Before using an asynchronous iterative method, the convergence must be -studied. Otherwise, the application is not ensure to reach the convergence. An +studied. Otherwise, there is no garantee that the application will reach the convergence. An algorithm that supports both the synchronous or the asynchronous iteration model requires very few modifications to be able to be executed in both variants. In -practice, only the communications and convergence detection are different. In -the synchronous mode iterations are synchronized, whereas in the asynchronous -one they are not. It should be noticed that non-blocking communications can be +practice, only the communications management and the convergence detection are different. In +the synchronous mode, iterations are synchronized, whereas, in the asynchronous +one, they are not. It should be noticed that non-blocking communications can be used in both modes. Concerning the convergence detection, synchronous variants can use a global convergence procedure which acts as a global synchronization point. In the asynchronous model, the convergence detection is more tricky as