\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
-\[
-\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)\]
+\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 $l,m\in\{1,\ldots,L\}$ $A_{lm}$ is a rectangular block of $A$ of size $n_l\times n_m$, $X_l$ and $B_l$ are sub-vectors of $x$ and $b$, respectively, of size $n_l$ each and $\sum_{l} n_l=\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}
-\left\{
-\begin{array}{l}
-A_{ll}X_l = Y_l \mbox{,~such that}\\
-Y_l = B_l - \displaystyle\sum_{\substack{m=1\\ m\neq l}}^{L}A_{lm}X_m
-\end{array}
-\right.
-\label{eq:4.1}
+ \label{eq:4.1}
+ \left\{
+ \begin{array}{l}
+ A_{ll}X_l = Y_l \text{, such that}\\
+ Y_l = B_l - \displaystyle\sum_{\substack{m=1\\ m\neq l}}^{L}A_{lm}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_l$, 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.
\Statex
\Function {InnerSolver}{$x^0$, $k$}
-\State Compute local right-hand side $Y_l$: \[Y_l = B_l - \sum\nolimits^L_{\substack{m=1 \\m\neq l}}A_{lm}X_m^0\]
+\State Compute local right-hand side $Y_l$:
+ \begin{equation*}
+ Y_l = B_l - \sum\nolimits^L_{\substack{m=1\\ m\neq l}}A_{lm}X_m^0
+ \end{equation*}
\State Solving sub-system $A_{ll}X_l^k=Y_l$ with the parallel GMRES method
\State \Return $X_l^k$
\EndFunction
\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 {\it True} if the local convergence is achieved or to {\it 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 {\it 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 $l$ is detected when the following condition is satisfied
-\[(k\leq \MI) \mbox{~or~} (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)\]
+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
+\text\it{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 $l$ is detected when the following
+condition is satisfied
+\begin{equation*}
+ (k\leq \MI) \text{ or } (\|X_l^k - X_l^{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_l^k$ and $X_l^{k+1}$.
\LZK{Description du processus d'adaptation de l'algo multisplitting à SimGrid}
When the \emph{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 (bw) and the network latency (lat).
-\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 \emph{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 (i.e. speed-up less than $1$).
+\begin{itemize}
+\item At the network level, we found that the most critical values are the
+ bandwidth (bw) and the network latency (lat).
+\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
+ \emph{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 (i.e. speed-up less than 1).
\end{itemize}
-A priori, obtaining a speedup less than $1$ would be difficult in a local area
-network configuration where the synchronous mode will take advantage on the rapid
-exchange of information on such high-speed links. Thus, the methodology adopted
-was to launch the application on clustered network. In this last configuration,
-degrading the inter-cluster network performance will \emph{penalize} the synchronous
-mode allowing to get a speedup lower than $1$. This action simulates the case of
-clusters linked with long distance network like Internet.
+A priori, obtaining a speedup less than 1 would be difficult in a local area
+network configuration where the synchronous mode will take advantage on the
+rapid exchange of information on such high-speed links. Thus, the methodology
+adopted was to launch the application on clustered network. In this last
+configuration, degrading the inter-cluster network performance will
+\emph{penalize} the synchronous mode allowing to get a speedup lower than 1.
+This action simulates the case of clusters linked with long distance network
+like Internet.
As a first step, the algorithm was run on a network consisting of two clusters
-containing $50$ hosts each, totaling $100$ hosts. Various combinations of
-the above factors have providing the results shown in
-Table~\ref{tab.cluster.2x50} with a matrix size ranging from $N_x = N_y = N_z =
-62 \text{ to } 171$ elements or from $62^{3} = \np{238328}$ to $171^{3} =
-\np{5211000}$ entries.
+containing 50 hosts each, totaling 100 hosts. Various combinations of the above
+factors have providing the results shown in Table~\ref{tab.cluster.2x50} with a
+matrix size ranging from $N_x = N_y = N_z = \text{62}$ to 171 elements or from
+$\text{62}^\text{3} = \text{\np{238328}}$ to $\text{171}^\text{3} =
+\text{\np{5211000}}$ entries.
% use the same column width for the following three tables
\newlength{\mytablew}\settowidth{\mytablew}{\footnotesize\np{E-11}}
\begin{table}[!t]
\centering
- \caption{$2$ clusters, each with $50$ nodes}
+ \caption{2 clusters, each with 50 nodes}
\label{tab.cluster.2x50}
\begin{mytable}{6}
\end{table}
Then we have changed the network configuration using three clusters containing
-respectively $33$, $33$ and $34$ hosts, or again by on hundred hosts for all the
+respectively 33, 33 and 34 hosts, or again by on hundred hosts for all the
clusters. In the same way as above, a judicious choice of key parameters has
permitted to get the results in Table~\ref{tab.cluster.3x33} which shows the
-speedups less than $1$ with a matrix size from $62$ to $100$ elements.
+speedups less than 1 with a matrix size from 62 to 100 elements.
\begin{table}[!t]
\centering
- \caption{$3$ clusters, each with $33$ nodes}
+ \caption{3 clusters, each with 33 nodes}
\label{tab.cluster.3x33}
\begin{mytable}{6}
of one GFlops, an efficiency of about \np[\%]{40} in asynchronous mode is
obtained for a matrix size of 62 elements. It is noticed that the result remains
stable even if we vary the external precision from \np{E-5} to \np{E-9}. By
-increasing the problem size up to $100$ elements, it was necessary to increase the
+increasing the problem size up to 100 elements, it was necessary to increase the
CPU power of \np[\%]{50} to \np[GFlops]{1.5} for a convergence of the algorithm
with the same order of asynchronous mode efficiency. Maintaining such a system
power but this time, increasing network throughput inter cluster up to
\np[Mbit/s]{50}, the result of efficiency of about \np[\%]{40} is obtained with
-high external precision of \np{E-11} for a matrix size from $110$ to $150$ side
+high external precision of \np{E-11} for a matrix size from 110 to 150 side
elements.
-For the $3$ clusters architecture including a total of 100 hosts,
+For the 3 clusters architecture including a total of 100 hosts,
Table~\ref{tab.cluster.3x33} shows that it was difficult to have a combination
which gives an efficiency of asynchronous below \np[\%]{80}. Indeed, for a
-matrix size of $62$ elements, equality between the performance of the two modes
+matrix size of 62 elements, equality between the performance of the two modes
(synchronous and asynchronous) is achieved with an inter cluster of
\np[Mbit/s]{10} and a latency of \np[ms]{E-1}. To challenge an efficiency by
-\np[\%]{78} with a matrix size of $100$ points, it was necessary to degrade the
+\np[\%]{78} with a matrix size of 100 points, it was necessary to degrade the
inter cluster network bandwidth from 5 to \np[Mbit/s]{2}.
A last attempt was made for a configuration of three clusters but more powerful
