+SimGrid~\cite{SimGrid,casanova+legrand+quinson.2008.simgrid} is a simulation
+framework to study the behavior of large-scale distributed systems. As its name
+says, it emanates from the grid computing community, but is nowadays used to
+study grids, clouds, HPC or peer-to-peer systems. The early versions of SimGrid
+date from 1999, but it's still actively developed and distributed as an open
+source software. Today, it's one of the major generic tools in the field of
+simulation for large-scale distributed systems.
+
+SimGrid provides several programming interfaces: MSG to simulate Concurrent
+Sequential Processes, SimDAG to simulate DAGs of (parallel) tasks, and SMPI to
+run real applications written in MPI~\cite{MPI}. Apart from the native C
+interface, SimGrid provides bindings for the C++, Java, Lua and Ruby programming
+languages. SMPI is the interface that has been used for the work exposed in
+this paper. The SMPI interface implements about \np[\%]{80} of the MPI 2.0
+standard~\cite{bedaride:hal-00919507}, and supports applications written in C or
+Fortran, with little or no modifications.
+
+Within SimGrid, the execution of a distributed application is simulated on a
+single machine. The application code is really executed, but some operations
+like the communications are intercepted, and their running time is computed
+according to the characteristics of the simulated execution platform. The
+description of this target platform is given as an input for the execution, by
+the mean of an XML file. It describes the properties of the platform, such as
+the computing nodes with their computing power, the interconnection links with
+their bandwidth and latency, and the routing strategy. The simulated running
+time of the application is computed according to these properties.
+
+To compute the durations of the operations in the simulated world, and to take
+into account resource sharing (e.g. bandwidth sharing between competing
+communications), SimGrid uses a fluid model. This allows to run relatively fast
+simulations, while still keeping accurate
+results~\cite{bedaride:hal-00919507,tomacs13}. Moreover, depending on the
+simulated application, SimGrid/SMPI allows to skip long lasting computations and
+to only take their duration into account. When the real computations cannot be
+skipped, but the results have no importance for the simulation results, there is
+also the possibility to share dynamically allocated data structures between
+several simulated processes, and thus to reduce the whole memory consumption.
+These two techniques can help to run simulations at a very large scale.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Simulation of the multisplitting method}
+%Décrire le problème (algo) traité ainsi que le processus d'adaptation à SimGrid.
+Let $Ax=b$ be a large sparse system of $n$ linear equations in $\mathbb{R}$, where $A$ is a sparse square and nonsingular matrix, $x$ is the solution vector and $b$ is the right-hand side vector. We use a multisplitting method based on the block Jacobi splitting to solve this linear system on a large scale platform composed of $L$ clusters of processors~\cite{o1985multi}. In this case, we apply a row-by-row splitting without overlapping
+\begin{equation*}
+ \left(\begin{array}{ccc}
+ A_{11} & \cdots & A_{1L} \\
+ \vdots & \ddots & \vdots\\
+ A_{L1} & \cdots & A_{LL}
+ \end{array} \right)
+ \times
+ \left(\begin{array}{c}
+ X_1 \\
+ \vdots\\
+ X_L
+ \end{array} \right)
+ =
+ \left(\begin{array}{c}
+ B_1 \\
+ \vdots\\
+ B_L
+ \end{array} \right)
+\end{equation*}
+in such a way that successive rows of matrix $A$ and both vectors $x$ and $b$
+are assigned to one cluster, where for all $\ell,m\in\{1,\ldots,L\}$, $A_{\ell
+ m}$ is a rectangular block of $A$ of size $n_\ell\times n_m$, $X_\ell$ and
+$B_\ell$ are sub-vectors of $x$ and $b$, respectively, of size $n_\ell$ each,
+and $\sum_{\ell} n_\ell=\sum_{m} n_m=n$.
+
+The multisplitting method proceeds by iteration to solve in parallel the linear system on $L$ clusters of processors, in such a way each sub-system
+\begin{equation}
+ \label{eq:4.1}
+ \left\{
+ \begin{array}{l}
+ A_{\ell\ell}X_\ell = Y_\ell \text{, such that}\\
+ Y_\ell = B_\ell - \displaystyle\sum_{\substack{m=1\\ m\neq \ell}}^{L}A_{\ell m}X_m
+ \end{array}
+ \right.
+\end{equation}
+is solved independently by a cluster and communications are required to update
+the right-hand side sub-vector $Y_\ell$, such that the sub-vectors $X_m$
+represent the data dependencies between the clusters. As each sub-system
+(\ref{eq:4.1}) is solved in parallel by a cluster of processors, our
+multisplitting method uses an iterative method as an inner solver which is
+easier to parallelize and more scalable than a direct method. In this work, we
+use the parallel algorithm of GMRES method~\cite{ref1} which is one of the most
+used iterative method by many researchers.
+
+\begin{figure}[!t]
+ %%% IEEE instructions forbid to use an algorithm environment here, use figure
+ %%% instead
+\begin{algorithmic}[1]
+\Input $A_\ell$ (sparse sub-matrix), $B_\ell$ (right-hand side sub-vector)
+\Output $X_\ell$ (solution sub-vector)\medskip
+
+\State Load $A_\ell$, $B_\ell$
+\State Set the initial guess $x^0$
+\For {$k=0,1,2,\ldots$ until the global convergence}
+\State Restart outer iteration with $x^0=x^k$
+\State Inner iteration: \Call{InnerSolver}{$x^0$, $k+1$}
+\State\label{algo:01:send} Send shared elements of $X_\ell^{k+1}$ to neighboring clusters
+\State\label{algo:01:recv} Receive shared elements in $\{X_m^{k+1}\}_{m\neq \ell}$
+\EndFor
+
+\Statex
+
+\Function {InnerSolver}{$x^0$, $k$}
+\State Compute local right-hand side $Y_\ell$:
+ \begin{equation*}
+ Y_\ell = B_\ell - \sum\nolimits^L_{\substack{m=1\\ m\neq \ell}}A_{\ell m}X_m^0
+ \end{equation*}
+\State Solving sub-system $A_{\ell\ell}X_\ell^k=Y_\ell$ with the parallel GMRES method
+\State \Return $X_\ell^k$
+\EndFunction
+\end{algorithmic}
+\caption{A multisplitting solver with GMRES method}
+\label{algo:01}
+\end{figure}
+
+Algorithm on Figure~\ref{algo:01} shows the main key points of the
+multisplitting method to solve a large sparse linear system. This algorithm is
+based on an outer-inner iteration method where the parallel synchronous GMRES
+method is used to solve the inner iteration. It is executed in parallel by each
+cluster of processors. For all $\ell,m\in\{1,\ldots,L\}$, the matrices and
+vectors with the subscript $\ell$ represent the local data for cluster $\ell$,
+while $\{A_{\ell m}\}_{m\neq \ell}$ are off-diagonal matrices of sparse matrix
+$A$ and $\{X_m\}_{m\neq \ell}$ contain vector elements of solution $x$ shared
+with neighboring clusters. At every outer iteration $k$, asynchronous
+communications are performed between processors of the local cluster and those
+of distant clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in
+Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are
+exchanged by message passing using MPI non-blocking communication routines.
+
+\begin{figure}[!t]
+\centering
+ \includegraphics[width=60mm,keepaspectratio]{clustering}
+\caption{Example of three clusters of processors interconnected by a virtual unidirectional ring network.}
+\label{fig:4.1}
+\end{figure}
+
+The global convergence of the asynchronous multisplitting solver is detected
+when the clusters of processors have all converged locally. We implemented the
+global convergence detection process as follows. On each cluster a master
+processor is designated (for example the processor with rank 1) and masters of
+all clusters are interconnected by a virtual unidirectional ring network (see
+Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around
+the virtual ring from a master processor to another until the global convergence
+is achieved. So starting from the cluster with rank 1, each master processor $i$
+sets the token to \textit{True} if the local convergence is achieved or to
+\textit{False} otherwise, and sends it to master processor $i+1$. Finally, the
+global convergence is detected when the master of cluster 1 receives from the
+master of cluster $L$ a token set to \textit{True}. In this case, the master of
+cluster 1 broadcasts a stop message to masters of other clusters. In this work,
+the local convergence on each cluster $\ell$ is detected when the following
+condition is satisfied
+\begin{equation*}
+ (k\leq \MI) \text{ or } (\|X_\ell^k - X_\ell^{k+1}\|_{\infty}\leq\epsilon)
+\end{equation*}
+where $\MI$ is the maximum number of outer iterations and $\epsilon$ is the
+tolerance threshold of the error computed between two successive local solution
+$X_\ell^k$ and $X_\ell^{k+1}$.
+
+
+
+In this paper, we solve the 3D Poisson problem whose the mathematical model is
+\begin{equation}
+\left\{
+\begin{array}{l}
+\nabla^2 u = f \text{~in~} \Omega \\
+u =0 \text{~on~} \Gamma =\partial\Omega
+\end{array}
+\right.
+\label{eq:02}
+\end{equation}
+where $\nabla^2$ is the Laplace operator, $f$ and $u$ are real-valued functions, and $\Omega=[0,1]^3$. The spatial discretization with a finite difference scheme reduces problem~(\ref{eq:02}) to a system of sparse linear equations. The general iteration scheme of our multisplitting method in a 3D domain using a seven point stencil could be written as
+\begin{equation}
+\begin{array}{ll}
+u^{k+1}(x,y,z)= & u^k(x,y,z) - \frac{1}{6}\times\\
+ & (u^k(x-1,y,z) + u^k(x+1,y,z) + \\
+ & u^k(x,y-1,z) + u^k(x,y+1,z) + \\
+ & u^k(x,y,z-1) + u^k(x,y,z+1)),
+\end{array}
+\label{eq:03}
+\end{equation}
+where the iteration matrix $A$ of size $N_x\times N_y\times N_z$ of the discretized linear system is sparse, symmetric and positive definite.
+
+The parallel solving of the 3D Poisson problem with our multisplitting method requires a data partitioning of the problem between clusters and between processors within a cluster. We have chosen the 3D partitioning instead of the row-by-row partitioning in order to reduce the data exchanges at sub-domain boundaries. Figure~\ref{fig:4.2} shows an example of the data partitioning of the 3D Poisson problem between two clusters of processors, where each sub-problem is assigned to a processor. In this context, a processor has at most six neighbors within a cluster or in distant clusters with which it shares data at sub-domain boundaries.
+
+\begin{figure}[!t]
+\centering
+ \includegraphics[width=80mm,keepaspectratio]{partition}
+\caption{Example of the 3D data partitioning between two clusters of processors.}
+\label{fig:4.2}
+\end{figure}
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+We did not encounter major blocking problems when adapting the multisplitting algorithm previously described to a simulation environment like SimGrid unless some code
+debugging. Indeed, apart from the review of the program sequence for asynchronous exchanges between processors within a cluster or between clusters, the algorithm was executed successfully with SMPI and provided identical outputs as those obtained with direct execution under MPI. In synchronous
+mode, the execution of the program raised no particular issue but in asynchronous mode, the review of the sequence of MPI\_Isend, MPI\_Irecv and MPI\_Waitall instructions
+and with the addition of the primitive MPI\_Test was needed to avoid a memory fault due to an infinite loop resulting from the non-convergence of the algorithm.
+\CER{On voulait en fait montrer la simplicité de l'adaptation de l'algo a SimGrid. Les problèmes rencontrés décrits dans ce paragraphe concerne surtout le mode async}\LZK{OK. J'aurais préféré avoir un peu plus de détails sur l'adaptation de la version async}
+Note here that the use of SMPI functions optimizer for memory footprint and CPU usage is not recommended knowing that one wants to get real results by simulation.
+As mentioned, upon this adaptation, the algorithm is executed as in the real life in the simulated environment after the following minor changes. First, all declared
+global variables have been moved to local variables for each subroutine. In fact, global variables generate side effects arising from the concurrent access of
+shared memory used by threads simulating each computing unit in the SimGrid architecture. Second, the alignment of certain types of variables such as ``long int'' had
+also to be reviewed.
+\AG{À propos de ces problèmes d'alignement, en dire plus si ça a un intérêt, ou l'enlever.}
+ Finally, some compilation errors on MPI\_Waitall and MPI\_Finalize primitives have been fixed with the latest version of SimGrid.
+In total, the initial MPI program running on the simulation environment SMPI gave after a very simple adaptation the same results as those obtained in a real
+environment. We have successfully executed the code in synchronous mode using parallel GMRES algorithm compared with our multisplitting algorithm in asynchronous mode after few modifications.
+
+
+
+\section{Simulation results}
+
+When the \textit{real} application runs in the simulation environment and produces the expected results, varying the input
+parameters and the program arguments allows us to compare outputs from the code execution. We have noticed from this
+study that the results depend on the following parameters:
+\begin{itemize}
+\item At the network level, we found that the most critical values are the
+ bandwidth and the network latency.
+\item Hosts power (GFlops) can also influence on the results.
+\item Finally, when submitting job batches for execution, the arguments values
+ passed to the program like the maximum number of iterations or the external
+ precision are critical. They allow to ensure not only the convergence of the
+ algorithm but also to get the main objective of the experimentation of the
+ simulation in having an execution time in asynchronous less than in
+ synchronous mode. The ratio between the execution time of asynchronous
+ compared to the synchronous mode is defined as the \emph{relative gain}. So,
+ our objective running the algorithm in SimGrid is to obtain a relative gain
+ greater than 1.
+ \AG{$t_\text{async} / t_\text{sync} > 1$, l'objectif est donc que ça dure plus
+ longtemps (que ça aille moins vite) en asynchrone qu'en synchrone ?
+ Ce n'est pas plutôt l'inverse ?}
+\end{itemize}
