%% Lilia Ziane Khodja: Department of Aerospace \& Mechanical Engineering\\ Non Linear Computational Mechanics\\ University of Liege\\ Liege, Belgium. Email: l.zianekhodja@ulg.ac.be
-\begin{abstract} The behavior of multicore applications is always a challenge
+\begin{abstract} 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
In this paper, we focus our attention on two parallel iterative algorithms based
on the Multisplitting algorithm and we compare them to the GMRES algorithm.
-These algorithms are used to solve libear systems. Two different variantsof
+These algorithms are used to solve libear systems. Two different variants of
the Multisplitting are studied: one using synchronoous iterations and another
one with asynchronous iterations. For each algorithm we have tested different
parameters to see their influence. We strongly recommend people interested
\maketitle
-\section{Introduction} The use of multi-core architectures for solving large
-scientific problems seems to become imperative in a lot of cases.
+\section{Introduction} The use of multi-core architectures to solve large
+scientific problems seems to become imperative in many situations.
Whatever the scale of these architectures (distributed clusters, computational
grids, embedded multi-core,~\ldots) they are generally well adapted to execute
complex parallel applications operating on a large amount of data.
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,~\ldots at the condition that
-the simulation results are in education with the real ones.
+code debugging, ability to obtain results quickly,~\ldots. In counterpart, 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
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
communication and computations are asynchronous inducing that there is no more
-idle times, due to synchronizations, between two iterations~\cite{bcvc06:ij}.
+idle time, due to synchronizations, between two iterations~\cite{bcvc06:ij}.
This model presents some advantages and drawbacks that we detail in
section~\ref{sec:asynchro} but even if the number of iterations required to
converge is generally greater than for the synchronous case, it appears that
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
-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 variations
-of the parameters of the execution platform can lead to very different number of
-iterations required to converge and so to very different execution times. In
-this challenging context we think that the use of a simulation tool can greatly
+Nevertheless, in both cases (synchronous or asynchronous) it is very time
+consuming to find optimal configuration 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 can lead to very different numbers
+of iterations to reach the converge and so 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.
The main contribution of this paper is to show that the use of a simulation tool
solver~\cite{saad86} in synchronous mode. The obtained results on different
simulated multi-core architectures confirm the real results previously obtained
on non simulated architectures. We also confirm the efficiency of the
-asynchronous multisplitting algorithm comparing to the synchronous GMRES. In
+asynchronous multisplitting algorithm compared to the synchronous GMRES. 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
different simulated multi-core architectures. To our knowledge, there is no
\section{The asynchronous iteration model}
\label{sec:asynchro}
+Asynchronous iterative methods have been studied for many years theorecally 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 iterations methods can be used to solve, for example, linear and
+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
+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, the 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 dectection is more tricky as it must not synchronize all the processors. Interested readers can consult~\cite{myBCCV05c,bahi07,ccl09:ij}.
+
\section{SimGrid}
\label{sec:simgrid}
