debut de correct d'anglishe

[rce2015.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index c959ace6e1ec0cc7af9d51f075487662df9a9502..f1e391c17ab1a70fd390a3e91985c3cb771742c6 100644 (file)
--- 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.
 
 %% 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.
 
 
 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
 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
 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
 
 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
 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}
 \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).
 
 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
 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.
 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.
 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
 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.
 
 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.
 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}
 
 \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
 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
 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
 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
 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