paper.tex

   1 \documentclass[times]{cpeauth}
   2
   3 \usepackage{moreverb}
   4
   5 %\usepackage[dvips,colorlinks,bookmarksopen,bookmarksnumbered,citecolor=red,urlcolor=red]{hyperref}
   6
   7 %\newcommand\BibTeX{{\rmfamily B\kern-.05em \textsc{i\kern-.025em b}\kern-.08em
   8 %T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
   9
  10 \def\volumeyear{2015}
  11
  12 \usepackage{graphicx}
  13 \usepackage{wrapfig}
  14 \usepackage{grffile}
  15
  16 \usepackage[T1]{fontenc}
  17 \usepackage[utf8]{inputenc}
  18 \usepackage{amsfonts,amssymb}
  19 \usepackage{amsmath}
  20 \usepackage{algorithm}
  21 \usepackage{algpseudocode}
  22 %\usepackage{amsthm}
  23 \usepackage{graphicx}
  24 \usepackage[american]{babel}
  25 % Extension pour les liens intra-documents (tagged PDF)
  26 % et l'affichage correct des URL (commande \url{http://example.com})
  27 %\usepackage{hyperref}
  28
  29 \usepackage{url}
  30 \DeclareUrlCommand\email{\urlstyle{same}}
  31
  32 \usepackage[autolanguage,np]{numprint}
  33 \AtBeginDocument{%
  34   \renewcommand*\npunitcommand[1]{\text{#1}}
  35   \npthousandthpartsep{}}
  36
  37 \usepackage{xspace}
  38 \usepackage[textsize=footnotesize]{todonotes}
  39
  40 \newcommand{\AG}[2][inline]{%
  41   \todo[color=green!50,#1]{\sffamily\textbf{AG:} #2}\xspace}
  42 \newcommand{\RC}[2][inline]{%
  43   \todo[color=red!10,#1]{\sffamily\textbf{RC:} #2}\xspace}
  44 \newcommand{\LZK}[2][inline]{%
  45   \todo[color=blue!10,#1]{\sffamily\textbf{LZK:} #2}\xspace}
  46 \newcommand{\RCE}[2][inline]{%
  47   \todo[color=yellow!10,#1]{\sffamily\textbf{RCE:} #2}\xspace}
  48
  49 \algnewcommand\algorithmicinput{\textbf{Input:}}
  50 \algnewcommand\Input{\item[\algorithmicinput]}
  51
  52 \algnewcommand\algorithmicoutput{\textbf{Output:}}
  53 \algnewcommand\Output{\item[\algorithmicoutput]}
  54
  55 \newcommand{\TOLG}{\mathit{tol_{gmres}}}
  56 \newcommand{\MIG}{\mathit{maxit_{gmres}}}
  57 \newcommand{\TOLM}{\mathit{tol_{multi}}}
  58 \newcommand{\MIM}{\mathit{maxit_{multi}}}
  59 \newcommand{\TOLC}{\mathit{tol_{cgls}}}
  60 \newcommand{\MIC}{\mathit{maxit_{cgls}}}
  61
  62 \usepackage{array}
  63 \usepackage{color, colortbl}
  64 \newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
  65 \newcolumntype{Z}[1]{>{\raggedleft}m{#1}}
  66
  67 \newcolumntype{g}{>{\columncolor{Gray}}c}
  68 \definecolor{Gray}{gray}{0.9}
  69
  70
  71
  72 \begin{document}
  73 \RCE{Titre a confirmer.}
  74 \title{Comparative performance analysis of simulated grid-enabled numerical iterative algorithms}
  75 %\itshape{\journalnamelc}\footnotemark[2]}
  76
  77 \author{    Charles Emile Ramamonjisoa and
  78     David Laiymani and
  79     Arnaud Giersch and
  80     Lilia Ziane Khodja and
  81     Raphaël Couturier
  82 }
  83
  84 \address{
  85         \centering
  86     Femto-ST Institute - DISC Department\\
  87     Université de Franche-Comté\\
  88     Belfort\\
  89     Email: \email{{raphael.couturier,arnaud.giersch,david.laiymani,charles.ramamonjisoa}@univ-fcomte.fr}
  90 }
  91
  92 %% Lilia Ziane Khodja: Department of Aerospace \& Mechanical Engineering\\ Non Linear Computational Mechanics\\ University of Liege\\ Liege, Belgium. Email: l.zianekhodja@ulg.ac.be
  93
  94 \begin{abstract}
  95   The behavior of multicore 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. We have decided to use SimGrid as it enables to benchmark MPI applications.
  96
  97 In this paper, we focus our attention on two parallel iterative algorithms based
  98 on the  Multisplitting algorithm  and we  compare them  to the  GMRES algorithm.
  99 These algorithms  are used to  solve libear  systems. Two different  variantsof the Multisplitting are
 100 studied: one  using synchronoous  iterations and  another one  with asynchronous
 101 iterations. For each algorithm we have  tested different parameters to see their
 102 influence.  We strongly  recommend people  interested  by investing  into a  new
 103 expensive  hardware  architecture  to   benchmark  their  applications  using  a
 104 simulation tool before.
 105
 106
 107
 108
 109 \end{abstract}
 110
 111 \keywords{Algorithm; distributed; iterative; asynchronous; simulation; simgrid; performance}
 112
 113 \maketitle
 114
 115 \section{Introduction}
 116
 117 \section{The asynchronous iteration model}
 118
 119 \section{SimGrid}
 120
 121 %%%%%%%%%%%%%%%%%%%%%%%%%
 122 %%%%%%%%%%%%%%%%%%%%%%%%%
 123
 124 \section{Two-stage multisplitting methods}
 125 \label{sec:04}
 126 \subsection{Synchronous and asynchronous two-stage methods for sparse linear systems}
 127 \label{sec:04.01}
 128 In this paper we focus on two-stage multisplitting methods in their both versions synchronous and asynchronous~\cite{Frommer92,Szyld92,Bru95}. These iterative methods are based on multisplitting methods~\cite{O'leary85,White86,Alefeld97} and use two nested iterations: the outer iteration and the inner iteration. Let us consider the following sparse linear system of $n$ equations in $\mathbb{R}$
 129 \begin{equation}
 130 Ax=b,
 131 \label{eq:01}
 132 \end{equation}
 133 where $A$ is a sparse square and nonsingular matrix, $b$ is the right-hand side and $x$ is the solution of the system. Our work in this paper is restricted to the block Jacobi splitting method. This approach of multisplitting consists in partitioning the matrix $A$ into $L$ horizontal band matrices of order $\frac{n}{L}\times n$ without overlapping (i.e. sub-vectors $\{x_\ell\}_{1\leq\ell\leq L}$ are disjoint). The two-stage multisplitting methods solve the linear system~(\ref{eq:01}) iteratively as follows
 134 \begin{equation}
 135 x_\ell^{k+1} = A_{\ell\ell}^{-1}(b_\ell - \displaystyle\sum^{L}_{\substack{m=1\\m\neq\ell}}{A_{\ell m}x^k_m}),\mbox{~for~}\ell=1,\ldots,L\mbox{~and~}k=1,2,3,\ldots
 136 \label{eq:02}
 137 \end{equation}
 138 where $x_\ell$ are sub-vectors of the solution $x$, $b_\ell$ are the sub-vectors of the right-hand side $b$, and $A_{\ell\ell}$ and $A_{\ell m}$ are diagonal and off-diagonal blocks of matrix $A$ respectively. The iterations of these methods can naturally be computed in parallel such that each processor or cluster of processors is responsible for solving one splitting as a linear sub-system
 139 \begin{equation}
 140 A_{\ell\ell} x_\ell = c_\ell,\mbox{~for~}\ell=1,\ldots,L,
 141 \label{eq:03}
 142 \end{equation}
 143 where right-hand sides $c_\ell=b_\ell-\sum_{m\neq\ell}A_{\ell m}x_m$ are computed using the shared vectors $x_m$. In this paper, we use the well-known iterative method GMRES ({\it Generalized Minimal RESidual})~\cite{saad86} as an inner iteration to approximate the solutions of the different splittings arising from the block Jacobi multisplitting of matrix $A$. The algorithm in Figure~\ref{alg:01} shows the main key points of our block Jacobi two-stage method executed by a cluster of processors. In line~\ref{solve}, the linear sub-system~(\ref{eq:03}) is solved in parallel using GMRES method where $\MIG$ and $\TOLG$ are the maximum number of inner iterations and the tolerance threshold for GMRES respectively. The convergence of the two-stage multisplitting methods, based on synchronous or asynchronous iterations, is studied by many authors for example~\cite{Bru95,bahi07}.
 144
 145 \begin{figure}[t]
 146 %\begin{algorithm}[t]
 147 %\caption{Block Jacobi two-stage multisplitting method}
 148 \begin{algorithmic}[1]
 149   \Input $A_\ell$ (sparse matrix), $b_\ell$ (right-hand side)
 150   \Output $x_\ell$ (solution vector)\vspace{0.2cm}
 151   \State Set the initial guess $x^0$
 152   \For {$k=1,2,3,\ldots$ until convergence}
 153     \State $c_\ell=b_\ell-\sum_{m\neq\ell}A_{\ell m}x_m^{k-1}$
 154     \State $x^k_\ell=Solve_{gmres}(A_{\ell\ell},c_\ell,x^{k-1}_\ell,\MIG,\TOLG)$\label{solve}
 155     \State Send $x_\ell^k$ to neighboring clusters\label{send}
 156     \State Receive $\{x_m^k\}_{m\neq\ell}$ from neighboring clusters\label{recv}
 157   \EndFor
 158 \end{algorithmic}
 159 \caption{Block Jacobi two-stage multisplitting method}
 160 \label{alg:01}
 161 %\end{algorithm}
 162 \end{figure}
 163
 164 In this paper, we propose two algorithms of two-stage multisplitting methods. The first algorithm is based on asynchronous model which allows the communications to be overlapped by computations and reduces the idle times resulting from the synchronizations. So in the asynchronous mode, our two-stage algorithm uses asynchronous outer iterations and asynchronous communications between clusters. The communications (i.e. lines~\ref{send} and~\ref{recv} in Figure~\ref{alg:01}) are performed by message passing using MPI non-blocking communication routines. The convergence of the asynchronous iterations is detected when all clusters have locally converged
 165 \begin{equation}
 166 k\geq\MIM\mbox{~or~}\|x_\ell^{k+1}-x_\ell^k\|_{\infty }\leq\TOLM,
 167 \label{eq:04}
 168 \end{equation}
 169 where $\MIM$ is the maximum number of outer iterations and $\TOLM$ is the tolerance threshold for the two-stage algorithm.
 170
 171 The second two-stage algorithm is based on synchronous outer iterations. We propose to use the Krylov iteration based on residual minimization to improve the slow convergence of the multisplitting methods. In this case, a $n\times s$ matrix $S$ is set using solutions issued from the inner iteration
 172 \begin{equation}
 173 S=[x^1,x^2,\ldots,x^s],~s\ll n.
 174 \label{eq:05}
 175 \end{equation}
 176 At each $s$ outer iterations, the algorithm computes a new approximation $\tilde{x}=S\alpha$ which minimizes the residual
 177 \begin{equation}
 178 \min_{\alpha\in\mathbb{R}^s}{\|b-AS\alpha\|_2}.
 179 \label{eq:06}
 180 \end{equation}
 181 The algorithm in Figure~\ref{alg:02} includes the procedure of the residual minimization and the outer iteration is restarted with a new approximation $\tilde{x}$ at every $s$ iterations. The least-squares problem~(\ref{eq:06}) is solved in parallel by all clusters using CGLS method~\cite{Hestenes52} such that $\MIC$ is the maximum number of iterations and $\TOLC$ is the tolerance threshold for this method (line~\ref{cgls} in Figure~\ref{alg:02}).
 182
 183 \begin{figure}[t]
 184 %\begin{algorithm}[t]
 185 %\caption{Krylov two-stage method using block Jacobi multisplitting}
 186 \begin{algorithmic}[1]
 187   \Input $A_\ell$ (sparse matrix), $b_\ell$ (right-hand side)
 188   \Output $x_\ell$ (solution vector)\vspace{0.2cm}
 189   \State Set the initial guess $x^0$
 190   \For {$k=1,2,3,\ldots$ until convergence}
 191     \State $c_\ell=b_\ell-\sum_{m\neq\ell}A_{\ell m}x_m^{k-1}$
 192     \State $x^k_\ell=Solve_{gmres}(A_{\ell\ell},c_\ell,x^{k-1}_\ell,\MIG,\TOLG)$
 193     \State $S_{\ell,k\mod s}=x_\ell^k$
 194     \If{$k\mod s = 0$}
 195        \State $\alpha = Solve_{cgls}(AS,b,\MIC,\TOLC)$\label{cgls}
 196        \State $\tilde{x_\ell}=S_\ell\alpha$
 197        \State Send $\tilde{x_\ell}$ to neighboring clusters
 198        \Else
 199          \State Send $x_\ell^k$ to neighboring clusters
 200     \EndIf
 201     \State Receive $\{x_m^k\}_{m\neq\ell}$ from neighboring clusters
 202   \EndFor
 203 \end{algorithmic}
 204 \caption{Krylov two-stage method using block Jacobi multisplitting}
 205 \label{alg:02}
 206 %\end{algorithm}
 207 \end{figure}
 208
 209 \subsection{Simulation of two-stage methods using SimGrid framework}
 210 \label{sec:04.02}
 211
 212 One of our objectives when simulating the application in SIMGRID is, as in real life, to get accurate results (solutions of the problem) but also ensure the test reproducibility under the same conditions. According our experience, very few modifications are required to adapt a MPI program to run in SIMGRID simulator using SMPI (Simulator MPI).The first modification is to include SMPI libraries and related header files (smpi.h). The second and important modification is to eliminate all global variables in moving them to local subroutine or using a Simgrid selector called "runtime automatic switching" (smpi/privatize\_global\_variables). Indeed, global variables can generate side effects on runtime between the threads running in the same process, generated by the Simgrid to simulate the grid environment.The last modification on the MPI program pointed out for some cases, the review of the sequence of the MPI\_Isend, MPI\_Irecv and MPI\_Waitall instructions which might cause an infinite loop.
 213
 214
 215 \paragraph{SIMGRID Simulator parameters}
 216
 217 \begin{itemize}
 218         \item hostfile: Hosts description file.
 219         \item plarform: File describing the platform architecture : clusters (CPU power,
 220 \dots{}), intra cluster network description, inter cluster network (bandwidth bw,
 221 latency lat, \dots{}).
 222         \item archi   : Grid computational description (Number of clusters, Number of
 223 nodes/processors for each cluster).
 224 \end{itemize}
 225
 226
 227 In addition, the following arguments are given to the programs at runtime:
 228
 229 \begin{itemize}
 230         \item Maximum number of inner and outer iterations;
 231         \item Inner and outer precisions;
 232         \item Matrix size (N$_{x}$, N$_{y}$ and N$_{z}$);
 233         \item Matrix diagonal value = 6.0;
 234         \item Execution Mode: synchronous or asynchronous.
 235 \end{itemize}
 236
 237 At last, note that the two solver algorithms have been executed with the Simgrid selector -cfg=smpi/running\_power which determine the computational power (here 19GFlops) of the simulator host machine.
 238
 239 %%%%%%%%%%%%%%%%%%%%%%%%%
 240 %%%%%%%%%%%%%%%%%%%%%%%%%
 241
 242 \section{Experimental Results}
 243
 244
 245 \subsection{Setup study and Methodology}
 246
 247 To conduct our study, we have put in place the following methodology
 248 which can be reused for any grid-enabled applications.
 249
 250 \textbf{Step 1} : Choose with the end users the class of algorithms or
 251 the application to be tested. Numerical parallel iterative algorithms
 252 have been chosen for the study in this paper. \\
 253
 254 \textbf{Step 2} : Collect the software materials needed for the
 255 experimentation. In our case, we have two variants algorithms for the
 256 resolution of three 3D-Poisson problem: (1) using the classical GMRES (Algo-1)(2) and the multisplitting method (Algo-2). In addition, SIMGRID simulator has been chosen to simulate the behaviors of the
 257 distributed applications. SIMGRID is running on the Mesocentre datacenter in Franche-Comte University but also in a virtual machine on a laptop. \\
 258
 259 \textbf{Step 3} : Fix the criteria which will be used for the future
 260 results comparison and analysis. In the scope of this study, we retain
 261 in one hand the algorithm execution mode (synchronous and asynchronous)
 262 and in the other hand the execution time and the number of iterations of
 263 the application before obtaining the convergence. \\
 264
 265 \textbf{Step 4 }: Setup up the different grid testbeds environment
 266 which will be simulated in the simulator tool to run the program. The
 267 following architecture has been configured in Simgrid : 2x16 - that is a
 268 grid containing 2 clusters with 16 hosts (processors/cores) each -, 4x8,
 269 4x16, 8x8 and 2x50. The network has been designed to operate with a
 270 bandwidth equals to 10Gbits (resp. 1Gbits/s) and a latency of 8E-6
 271 microseconds (resp. 5E-5) for the intra-clusters links (resp.
 272 inter-clusters backbone links). \\
 273
 274 \textbf{Step 5}: Conduct an extensive and comprehensive testings
 275 within these configurations in varying the key parameters, especially
 276 the CPU power capacity, the network parameters and also the size of the
 277 input matrix. Note that some parameters should be fixed to be invariant to allow the
 278 comparison like some program input arguments. \\
 279
 280 \textbf{Step 6} : Collect and analyze the output results.
 281
 282 \subsection{Factors impacting distributed applications performance in
 283 a grid environment}
 284
 285 From our previous experience on running distributed application in a
 286 computational grid, many factors are identified to have an impact on the
 287 program behavior and performance on this specific environment. Mainly,
 288 first of all, the architecture of the grid itself can obviously
 289 influence the performance results of the program. The performance gain
 290 might be important theoretically when the number of clusters and/or the
 291 number of nodes (processors/cores) in each individual cluster increase.
 292
 293 Another important factor impacting the overall performance of the
 294 application is the network configuration. Two main network parameters
 295 can modify drastically the program output results : (i) the network
 296 bandwidth (bw=bits/s) also known as "the data-carrying capacity"
 297 of the network is defined as the maximum of data that can pass
 298 from one point to another in a unit of time. (ii) the network latency
 299 (lat : microsecond) defined as the delay from the start time to send the
 300 data from a source and the final time the destination have finished to
 301 receive it. Upon the network characteristics, another impacting factor
 302 is the application dependent volume of data exchanged between the nodes
 303 in the cluster and between distant clusters. Large volume of data can be
 304 transferred in transit between the clusters and nodes during the code
 305 execution.
 306
 307  In a grid environment, it is common to distinguish in one hand, the
 308 "\,intra-network" which refers to the links between nodes within a
 309 cluster and in the other hand, the "\,inter-network" which is the
 310 backbone link between clusters. By design, these two networks perform
 311 with different speed. The intra-network generally works like a high
 312 speed local network with a high bandwith and very low latency. In
 313 opposite, the inter-network connects clusters sometime via heterogeneous
 314 networks components thru internet with a lower speed. The network
 315 between distant clusters might be a bottleneck for the global
 316 performance of the application.
 317
 318 \subsection{Comparing GMRES and Multisplitting algorithms in
 319 synchronous mode}
 320
 321 In the scope of this paper, our first objective is to demonstrate the
 322 Algo-2 (Multisplitting method) shows a better performance in grid
 323 architecture compared with Algo-1 (Classical GMRES) both running in
 324 \textbf{\textit{synchronous mode}}. Better algorithm performance
 325 should means a less number of iterations output and a less execution time
 326 before reaching the convergence. For a systematic study, the experiments
 327 should figure out that, for various grid parameters values, the
 328 simulator will confirm the targeted outcomes, particularly for poor and
 329 slow networks, focusing on the impact on the communication performance
 330 on the chosen class of algorithm.
 331
 332 The following paragraphs present the test conditions, the output results
 333 and our comments.\\
 334
 335
 336 \textit{3.a Executing the algorithms on various computational grid
 337 architecture scaling up the input matrix size}
 338 \\
 339
 340 % environment
 341 \begin{footnotesize}
 342 \begin{tabular}{r c }
 343  \hline
 344  Grid & 2x16, 4x8, 4x16 and 8x8\\ %\hline
 345  Network & N2 : bw=1Gbits/s - lat=\np{5E-5} \\ %\hline
 346  Input matrix size & N$_{x}$ x N$_{y}$ x N$_{z}$ =150 x 150 x 150\\ %\hline
 347  - &  N$_{x}$ x N$_{y}$ x N$_{z}$  =170 x 170 x 170    \\ \hline
 348  \end{tabular}
 349 Table 1 : Clusters x Nodes with N$_{x}$=150 or N$_{x}$=170 \\
 350
 351 \end{footnotesize}
 352
 353
 354
 355 %\RCE{J'ai voulu mettre les tableaux des données mais je pense que c'est inutile et ça va surcharger}
 356
 357
 358 The results in figure 3 show the non-variation of the number of
 359 iterations of classical GMRES for a given input matrix size; it is not
 360 the case for the multisplitting method.
 361
 362 %\begin{wrapfigure}{l}{100mm}
 363 \begin{figure} [ht!]
 364 \centering
 365 \includegraphics[width=100mm]{cluster_x_nodes_nx_150_and_nx_170.pdf}
 366 \caption{Cluster x Nodes NX=150 and NX=170}
 367 %\label{overflow}}
 368 \end{figure}
 369 %\end{wrapfigure}
 370
 371 Unless the 8x8 cluster, the time
 372 execution difference between the two algorithms is important when
 373 comparing between different grid architectures, even with the same number of
 374 processors (like 2x16 and 4x8 = 32 processors for example). The
 375 experiment concludes the low sensitivity of the multisplitting method
 376 (compared with the classical GMRES) when scaling up to higher input
 377 matrix size.
 378
 379 \textit{\\3.b Running on various computational grid architecture\\}
 380
 381 % environment
 382 \begin{footnotesize}
 383 \begin{tabular}{r c }
 384  \hline
 385  Grid & 2x16, 4x8\\ %\hline
 386  Network & N1 : bw=10Gbs-lat=8E-06 \\ %\hline
 387  - & N2 : bw=1Gbs-lat=5E-05 \\
 388  Input matrix size & N$_{x}$ =150 x 150 x 150\\ \hline \\
 389  \end{tabular}
 390 Table 2 : Clusters x Nodes - Networks N1 x N2 \\
 391
 392  \end{footnotesize}
 393
 394
 395
 396 %\begin{wrapfigure}{l}{100mm}
 397 \begin{figure} [ht!]
 398 \centering
 399 \includegraphics[width=100mm]{cluster_x_nodes_n1_x_n2.pdf}
 400 \caption{Cluster x Nodes N1 x N2}
 401 %\label{overflow}}
 402 \end{figure}
 403 %\end{wrapfigure}
 404
 405 The experiments compare the behavior of the algorithms running first on
 406 speed inter- cluster network (N1) and a less performant network (N2).
 407 The figure 2 shows that end users will gain to reduce the execution time
 408 for both algorithms in using a grid architecture like 4x16 or 8x8: the
 409 performance was increased in a factor of 2. The results depict also that
 410 when the network speed drops down, the difference between the execution
 411 times can reach more than 25\%.
 412
 413 \textit{\\3.c Network latency impacts on performance\\}
 414
 415 % environment
 416 \begin{footnotesize}
 417 \begin{tabular}{r c }
 418  \hline
 419  Grid & 2x16\\ %\hline
 420  Network & N1 : bw=1Gbs \\ %\hline
 421  Input matrix size & N$_{x}$ =150 x 150 x 150\\ \hline\\
 422  \end{tabular}
 423
 424 Table 3 : Network latency impact \\
 425
 426 \end{footnotesize}
 427
 428
 429
 430 \begin{figure} [ht!]
 431 \centering
 432 \includegraphics[width=100mm]{network_latency_impact_on_execution_time.pdf}
 433 \caption{Network latency impact on execution time}
 434 %\label{overflow}}
 435 \end{figure}
 436
 437
 438 According the results in table and figure 3, degradation of the network
 439 latency from 8.10$^{-6}$ to 6.10$^{-5}$ implies an absolute time
 440 increase more than 75\% (resp. 82\%) of the execution for the classical
 441 GMRES (resp. multisplitting) algorithm. In addition, it appears that the
 442 multisplitting method tolerates more the network latency variation with
 443 a less rate increase. Consequently, in the worst case (lat=6.10$^{-5
 444 }$), the execution time for GMRES is almost the double of the time for
 445 the multisplitting, even though, the performance was on the same order
 446 of magnitude with a latency of 8.10$^{-6}$.
 447
 448 \textit{\\3.d Network bandwidth impacts on performance\\}
 449
 450 % environment
 451 \begin{footnotesize}
 452 \begin{tabular}{r c }
 453  \hline
 454  Grid & 2x16\\ %\hline
 455  Network & N1 : bw=1Gbs - lat=5E-05 \\ %\hline
 456  Input matrix size & N$_{x}$ =150 x 150 x 150\\ \hline
 457  \end{tabular}
 458
 459 Table 4 : Network bandwidth impact \\
 460
 461 \end{footnotesize}
 462
 463
 464 \begin{figure} [ht!]
 465 \centering
 466 \includegraphics[width=100mm]{network_bandwith_impact_on_execution_time.pdf}
 467 \caption{Network bandwith impact on execution time}
 468 %\label{overflow}
 469 \end{figure}
 470
 471
 472
 473 The results of increasing the network bandwidth depict the improvement
 474 of the performance by reducing the execution time for both of the two
 475 algorithms. However, and again in this case, the multisplitting method
 476 presents a better performance in the considered bandwidth interval with
 477 a gain of 40\% which is only around 24\% for classical GMRES.
 478
 479 \textit{\\3.e Input matrix size impacts on performance\\}
 480
 481 % environment
 482 \begin{footnotesize}
 483 \begin{tabular}{r c }
 484  \hline
 485  Grid & 4x8\\ %\hline
 486  Network & N2 : bw=1Gbs - lat=5E-05 \\ %\hline
 487  Input matrix size & N$_{x}$ = From 40 to 200\\ \hline
 488  \end{tabular}
 489 Table 5 : Input matrix size impact\\
 490
 491 \end{footnotesize}
 492
 493
 494 \begin{figure} [ht!]
 495 \centering
 496 \includegraphics[width=100mm]{pb_size_impact_on_execution_time.pdf}
 497 \caption{Pb size impact on execution time}
 498 %\label{overflow}}
 499 \end{figure}
 500
 501 In this experimentation, the input matrix size has been set from
 502 Nx=Ny=Nz=40 to 200 side elements that is from 40$^{3}$ = 64.000 to
 503 200$^{3}$ = 8.000.000 points. Obviously, as shown in the figure 5,
 504 the execution time for the algorithms convergence increases with the
 505 input matrix size. But the interesting result here direct on (i) the
 506 drastic increase (300 times) of the number of iterations needed before
 507 the convergence for the classical GMRES algorithm when the matrix size
 508 go beyond Nx=150; (ii) the classical GMRES execution time also almost
 509 the double from Nx=140 compared with the convergence time of the
 510 multisplitting method. These findings may help a lot end users to setup
 511 the best and the optimal targeted environment for the application
 512 deployment when focusing on the problem size scale up. Note that the
 513 same test has been done with the grid 2x16 getting the same conclusion.
 514
 515 \textit{\\3.f CPU Power impact on performance\\}
 516
 517 % environment
 518 \begin{footnotesize}
 519 \begin{tabular}{r c }
 520  \hline
 521  Grid & 2x16\\ %\hline
 522  Network & N2 : bw=1Gbs - lat=5E-05 \\ %\hline
 523  Input matrix size & N$_{x}$ = 150 x 150 x 150\\ \hline
 524  \end{tabular}
 525 Table 6 : CPU Power impact \\
 526
 527 \end{footnotesize}
 528
 529
 530 \begin{figure} [ht!]
 531 \centering
 532 \includegraphics[width=100mm]{cpu_power_impact_on_execution_time.pdf}
 533 \caption{CPU Power impact on execution time}
 534 %\label{overflow}}
 535 \end{figure}
 536
 537 Using the SIMGRID simulator flexibility, we have tried to determine the
 538 impact on the algorithms performance in varying the CPU power of the
 539 clusters nodes from 1 to 19 GFlops. The outputs depicted in the figure 6
 540 confirm the performance gain, around 95\% for both of the two methods,
 541 after adding more powerful CPU. Note that the execution time axis in the
 542 figure is in logarithmic scale.
 543
 544 \subsection{Comparing GMRES in native synchronous mode and
 545 Multisplitting algorithms in asynchronous mode}
 546
 547 The previous paragraphs put in evidence the interests to simulate the
 548 behavior of the application before any deployment in a real environment.
 549 We have focused the study on analyzing the performance in varying the
 550 key factors impacting the results. In the same line, the study compares
 551 the performance of the two proposed methods in \textbf{synchronous mode
 552 }. In this section, with the same previous methodology, the goal is to
 553 demonstrate the efficiency of the multisplitting method in \textbf{
 554 asynchronous mode} compare with the classical GMRES staying in the
 555 synchronous mode.
 556
 557 Note that the interest of using the asynchronous mode for data exchange
 558 is mainly, in opposite of the synchronous mode, the non-wait aspects of
 559 the current computation after a communication operation like sending
 560 some data between nodes. Each processor can continue their local
 561 calculation without waiting for the end of the communication. Thus, the
 562 asynchronous may theoretically reduce the overall execution time and can
 563 improve the algorithm performance.
 564
 565 As stated supra, SIMGRID simulator tool has been used to prove the
 566 efficiency of the multisplitting in asynchronous mode and to find the
 567 best combination of the grid resources (CPU, Network, input matrix size,
 568 \ldots ) to get the highest "\,relative gain" in comparison with the
 569 classical GMRES time.
 570
 571
 572 The test conditions are summarized in the table below : \\
 573
 574 % environment
 575 \begin{footnotesize}
 576 \begin{tabular}{r c }
 577  \hline
 578  Grid & 2x50 totaling 100 processors\\ %\hline
 579  Processors & 1 GFlops to 1.5 GFlops\\
 580    Intra-Network & bw=1.25 Gbits - lat=5E-05 \\ %\hline
 581    Inter-Network & bw=5 Mbits - lat=2E-02\\
 582  Input matrix size & N$_{x}$ = From 62 to 150\\ %\hline
 583  Residual error precision: 10$^{-5}$ to 10$^{-9}$\\ \hline \\
 584  \end{tabular}
 585 \end{footnotesize}
 586
 587 Again, comprehensive and extensive tests have been conducted varying the
 588 CPU power and the network parameters (bandwidth and latency) in the
 589 simulator tool with different problem size. The relative gains greater
 590 than 1 between the two algorithms have been captured after each step of
 591 the test. Table I below has recorded the best grid configurations
 592 allowing a multiplitting method time more than 2.5 times lower than
 593 classical GMRES execution and convergence time. The finding thru this
 594 experimentation is the tolerance of the multisplitting method under a
 595 low speed network that we encounter usually with distant clusters thru the
 596 internet.
 597
 598 % use the same column width for the following three tables
 599 \newlength{\mytablew}\settowidth{\mytablew}{\footnotesize\np{E-11}}
 600 \newenvironment{mytable}[1]{% #1: number of columns for data
 601   \renewcommand{\arraystretch}{1.3}%
 602   \begin{tabular}{|>{\bfseries}r%
 603                   |*{#1}{>{\centering\arraybackslash}p{\mytablew}|}}}{%
 604     \end{tabular}}
 605
 606 \begin{table}[!t]
 607   \centering
 608   \caption{Relative gain of the multisplitting algorithm compared with
 609 the classical GMRES}
 610   \label{"Table 7"}
 611
 612   \begin{mytable}{6}
 613     \hline
 614     bandwidth (Mbit/s)
 615     & 5         & 5         & 5         & 5         & 5 \\
 616     \hline
 617     latency (ms)
 618     & 20      & 20      & 20      & 20      & 20 \\
 619     \hline
 620     power (GFlops)
 621     & 1         & 1         & 1         & 1.5       & 1.5 \\
 622     \hline
 623     size (N)
 624     & 62        & 62        & 62        & 100       & 100 \\
 625     \hline
 626     Precision
 627     & \np{E-5}  & \np{E-8}  & \np{E-9}  & \np{E-11} & \np{E-11} \\
 628     \hline
 629     Relative gain
 630     & 2.52     & 2.55     & 2.52     & 2.57     & 2.54 \\
 631     \hline
 632   \end{mytable}
 633
 634   \smallskip
 635
 636   \begin{mytable}{6}
 637     \hline
 638     bandwidth (Mbit/s)
 639     & 50        & 50        & 50        & 50        & 50 \\
 640     \hline
 641     latency (ms)
 642     & 20      & 20      & 20      & 20      & 20 \\
 643     \hline
 644     power (GFlops)
 645     & 1.5         & 1.5         & 1         & 1.5       & 1.5 \\
 646     \hline
 647     size (N)
 648     & 110       & 120       & 130       & 140       & 150 \\
 649     \hline
 650     Precision
 651     & \np{E-11} & \np{E-11} & \np{E-11} & \np{E-11} & \np{E-11}\\
 652     \hline
 653     Relative gain
 654     & 2.53     & 2.51     & 2.58     & 2.55     & 2.54 \\
 655     \hline
 656   \end{mytable}
 657 \end{table}
 658
 659 \section{Conclusion}
 660 CONCLUSION
 661
 662
 663 \section*{Acknowledgment}
 664
 665
 666 The authors would like to thank\dots{}
 667
 668
 669 \bibliographystyle{wileyj}
 670 \bibliography{biblio}
 671
 672 \end{document}
 673
 674 %%% Local Variables:
 675 %%% mode: latex
 676 %%% TeX-master: t
 677 %%% fill-column: 80
 678 %%% ispell-local-dictionary: "american"
 679 %%% End: