hpcc.tex

   1 \documentclass[conference]{IEEEtran}
   2
   3 \usepackage[T1]{fontenc}
   4 \usepackage[utf8]{inputenc}
   5 \usepackage{amsfonts,amssymb}
   6 \usepackage{amsmath}
   7 %\usepackage{algorithm}
   8 \usepackage{algpseudocode}
   9 %\usepackage{amsthm}
  10 \usepackage{graphicx}
  11 \usepackage[american]{babel}
  12 % Extension pour les liens intra-documents (tagged PDF)
  13 % et l'affichage correct des URL (commande \url{http://example.com})
  14 %\usepackage{hyperref}
  15
  16 \usepackage{url}
  17 \DeclareUrlCommand\email{\urlstyle{same}}
  18
  19 \usepackage[autolanguage,np]{numprint}
  20 \AtBeginDocument{%
  21   \renewcommand*\npunitcommand[1]{\text{#1}}
  22   \npthousandthpartsep{}}
  23
  24 \usepackage{xspace}
  25 \usepackage[textsize=footnotesize]{todonotes}
  26 \newcommand{\AG}[2][inline]{%
  27   \todo[color=green!50,#1]{\sffamily\textbf{AG:} #2}\xspace}
  28 \newcommand{\DL}[2][inline]{%
  29   \todo[color=yellow!50,#1]{\sffamily\textbf{DL:} #2}\xspace}
  30 \newcommand{\LZK}[2][inline]{%
  31   \todo[color=blue!10,#1]{\sffamily\textbf{LZK:} #2}\xspace}
  32 \newcommand{\RC}[2][inline]{%
  33   \todo[color=red!10,#1]{\sffamily\textbf{RC:} #2}\xspace}
  34
  35 \algnewcommand\algorithmicinput{\textbf{Input:}}
  36 \algnewcommand\Input{\item[\algorithmicinput]}
  37
  38 \algnewcommand\algorithmicoutput{\textbf{Output:}}
  39 \algnewcommand\Output{\item[\algorithmicoutput]}
  40
  41 \newcommand{\MI}{\mathit{MaxIter}}
  42
  43 \begin{document}
  44
  45 \title{Simulation of Asynchronous Iterative Numerical Algorithms Using SimGrid}
  46
  47 \author{%
  48   \IEEEauthorblockN{%
  49     Charles Emile Ramamonjisoa\IEEEauthorrefmark{1},
  50     David Laiymani\IEEEauthorrefmark{1},
  51     Arnaud Giersch\IEEEauthorrefmark{1},
  52     Lilia Ziane Khodja\IEEEauthorrefmark{2} and
  53     Raphaël Couturier\IEEEauthorrefmark{1}
  54   }
  55   \IEEEauthorblockA{\IEEEauthorrefmark{1}%
  56     Femto-ST Institute -- DISC Department\\
  57     Université de Franche-Comté,
  58     IUT de Belfort-Montbéliard\\
  59     19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France\\
  60     Email: \email{{charles.ramamonjisoa,david.laiymani,arnaud.giersch,raphael.couturier}@univ-fcomte.fr}
  61   }
  62   \IEEEauthorblockA{\IEEEauthorrefmark{2}%
  63     Inria Bordeaux Sud-Ouest\\
  64     200 avenue de la Vieille Tour, 33405 Talence cedex, France \\
  65     Email: \email{lilia.ziane@inria.fr}
  66   }
  67 }
  68
  69 \maketitle
  70
  71 \RC{Ordre des auteurs pas définitif.}
  72 \begin{abstract}
  73 In recent years, the scalability of large-scale implementation in a
  74 distributed environment of algorithms becoming more and more complex has
  75 always been hampered by the limits of physical computing resources
  76 capacity. One solution is to run the program in a virtual environment
  77 simulating a real interconnected computers architecture. The results are
  78 convincing and useful solutions are obtained with far fewer resources
  79 than in a real platform. However, challenges remain for the convergence
  80 and efficiency of a class of algorithms that concern us here, namely
  81 numerical parallel iterative algorithms executed in asynchronous mode,
  82 especially in a large scale level. Actually, such algorithm requires a
  83 balance and a compromise between computation and communication time
  84 during the execution. Two important factors determine the success of the
  85 experimentation: the convergence of the iterative algorithm on a large
  86 scale and the execution time reduction in asynchronous mode. Once again,
  87 from the current work, a simulated environment like SimGrid provides
  88 accurate results which are difficult or even impossible to obtain in a
  89 physical platform by exploiting the flexibility of the simulator on the
  90 computing units clusters and the network structure design. Our
  91 experimental outputs showed a saving of up to \np[\%]{40} for the algorithm
  92 execution time in asynchronous mode compared to the synchronous one with
  93 a residual precision up to \np{E-11}. Such successful results open
  94 perspectives on experimentations for running the algorithm on a
  95 simulated large scale growing environment and with larger problem size.
  96
  97 % no keywords for IEEE conferences
  98 % Keywords: Algorithm distributed iterative asynchronous simulation SimGrid
  99 \end{abstract}
 100
 101 \section{Introduction}
 102
 103 Parallel computing and high performance computing (HPC) are becoming  more and more imperative for solving various
 104 problems raised by  researchers on various scientific disciplines but also by industrial in  the field. Indeed, the
 105 increasing complexity of these requested  applications combined with a continuous increase of their sizes lead to  write
 106 distributed and parallel algorithms requiring significant hardware  resources (grid computing, clusters, broadband
 107 network, etc.) but also a non-negligible CPU execution time. We consider in this paper a class of highly efficient
 108 parallel algorithms called \emph{numerical iterative algorithms} executed in a distributed environment. As their name
 109 suggests, these algorithms solve a given problem by successive iterations ($X_{n +1} = f(X_{n})$) from an initial value
 110 $X_{0}$ to find an approximate value $X^*$ of the solution with a very low residual error. Several well-known methods
 111 demonstrate the convergence of these algorithms~\cite{BT89,Bahi07}.
 112
 113 Parallelization of such algorithms generally involve the division of the problem into several \emph{blocks} that will
 114 be solved in parallel on multiple processing units. The latter will communicate each intermediate results before a new
 115 iteration starts and until the approximate solution is reached. These parallel  computations can be performed either in
 116 \emph{synchronous} mode where a new iteration begins only when all nodes communications are completed,
 117 or in \emph{asynchronous} mode where processors can continue independently with few or no synchronization points. For
 118 instance in the \textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)} model~\cite{bcvc06:ij}, local
 119 computations do not need to wait for required data. Processors can then perform their iterations with the data present
 120 at that time. Even if the number of iterations required before the convergence is generally greater than for the
 121 synchronous case, AIAC algorithms can significantly reduce overall execution times by suppressing idle times due to
 122 synchronizations especially in a grid computing context (see~\cite{Bahi07} for more details).
 123
 124 Parallel numerical applications (synchronous or asynchronous) may have different
 125 configuration and deployment requirements.  Quantifying their resource
 126 allocation policies and application scheduling algorithms in grid computing
 127 environments under varying load, CPU power and network speeds is very costly,
 128 very labor intensive and very time
 129 consuming~\cite{Calheiros:2011:CTM:1951445.1951450}.  The case of AIAC
 130 algorithms is even more problematic since they are very sensible to the
 131 execution environment context. For instance, variations in the network bandwidth
 132 (intra and inter-clusters), in the number and the power of nodes, in the number
 133 of clusters\dots{} can lead to very different number of iterations and so to
 134 very different execution times. Then, it appears that the use of simulation
 135 tools to explore various platform scenarios and to run large numbers of
 136 experiments quickly can be very promising. In this way, the use of a simulation
 137 environment to execute parallel iterative algorithms found some interests in
 138 reducing the highly cost of access to computing resources: (1) for the
 139 applications development life cycle and in code debugging (2) and in production
 140 to get results in a reasonable execution time with a simulated infrastructure
 141 not accessible with physical resources. Indeed, the launch of distributed
 142 iterative asynchronous algorithms to solve a given problem on a large-scale
 143 simulated environment challenges to find optimal configurations giving the best
 144 results with a lowest residual error and in the best of execution time.
 145
 146 To our knowledge, there is no existing work on the large-scale simulation of a
 147 real AIAC application. The aim of this paper is twofold. First we give a first
 148 approach of the simulation of AIAC algorithms using a simulation tool (i.e. the
 149 SimGrid toolkit~\cite{SimGrid}). Second, we confirm the effectiveness of
 150 asynchronous mode algorithms by comparing their performance with the synchronous
 151 mode. More precisely, we had implemented a program for solving large
 152 non-symmetric linear system of equations by numerical method GMRES (Generalized
 153 Minimal Residual) []\AG[]{[]?}. We show, that with minor modifications of the
 154 initial MPI code, the SimGrid toolkit allows us to perform a test campaign of a
 155 real AIAC application on different computing architectures. The simulated
 156 results we obtained are in line with real results exposed in ??\AG[]{??}.
 157 SimGrid had allowed us to launch the application from a modest computing
 158 infrastructure by simulating different distributed architectures composed by
 159 clusters nodes interconnected by variable speed networks.  With selected
 160 parameters on the network platforms (bandwidth, latency of inter cluster
 161 network) and on the clusters architecture (number, capacity calculation power)
 162 in the simulated environment, the experimental results have demonstrated not
 163 only the algorithm convergence within a reasonable time compared with the
 164 physical environment performance, but also a time saving of up to \np[\%]{40} in
 165 asynchronous mode.
 166
 167 This article is structured as follows: after this introduction, the next  section will give a brief description of
 168 iterative asynchronous model.  Then, the simulation framework SimGrid is presented with the settings to create various
 169 distributed architectures. The algorithm of  the multisplitting method used by GMRES written with MPI primitives and
 170 its adaptation to SimGrid with SMPI (Simulated MPI) is detailed in the next section. At last, the experiments results
 171 carried out will be presented before some concluding remarks and future works.
 172
 173 \section{Motivations and scientific context}
 174
 175 As exposed in the introduction, parallel iterative methods are now widely used in many scientific domains. They can be
 176 classified in three main classes depending on how iterations and communications are managed (for more details readers
 177 can refer to~\cite{bcvc06:ij}). In the \textit{Synchronous Iterations~-- Synchronous Communications (SISC)} model data
 178 are exchanged at the end of each iteration. All the processors must begin the same iteration at the same time and
 179 important idle times on processors are generated. The \textit{Synchronous Iterations~-- Asynchronous Communications
 180 (SIAC)} model can be compared to the previous one except that data required on another processor are sent asynchronously
 181 i.e.  without stopping current computations. This technique allows to partially overlap communications by computations
 182 but unfortunately, the overlapping is only partial and important idle times remain.  It is clear that, in a grid
 183 computing context, where the number of computational nodes is large, heterogeneous and widely distributed, the idle
 184 times generated by synchronizations are very penalizing. One way to overcome this problem is to use the
 185 \textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)} model. Here, local computations do not need to
 186 wait for required data. Processors can then perform their iterations with the data present at that time. Figure~\ref{fig:aiac}
 187 illustrates this model where the gray blocks represent the computation phases, the white spaces the idle
 188 times and the arrows the communications. With this algorithmic model, the number of iterations required before the
 189 convergence is generally greater than for the two former classes. But, and as detailed in~\cite{bcvc06:ij}, AIAC
 190 algorithms can significantly reduce overall execution times by suppressing idle times due to synchronizations especially
 191 in a grid computing context.
 192
 193 \begin{figure}[!t]
 194   \centering
 195     \includegraphics[width=8cm]{AIAC.pdf}
 196   \caption{The Asynchronous Iterations~-- Asynchronous Communications model}
 197   \label{fig:aiac}
 198 \end{figure}
 199
 200
 201 It is very challenging to develop efficient applications for large scale,
 202 heterogeneous and distributed platforms such as computing grids. Researchers and
 203 engineers have to develop techniques for maximizing application performance of
 204 these multi-cluster platforms, by redesigning the applications and/or by using
 205 novel algorithms that can account for the composite and heterogeneous nature of
 206 the platform. Unfortunately, the deployment of such applications on these very
 207 large scale systems is very costly, labor intensive and time consuming. In this
 208 context, it appears that the use of simulation tools to explore various platform
 209 scenarios at will and to run enormous numbers of experiments quickly can be very
 210 promising. Several works\dots{}
 211
 212 \AG{Several works\dots{} what?\\
 213   Le paragraphe suivant se trouve déjà dans l'intro ?}
 214 In the context of AIAC algorithms, the use of simulation tools is even more
 215 relevant. Indeed, this class of applications is very sensible to the execution
 216 environment context. For instance, variations in the network bandwidth (intra
 217 and inter-clusters), in the number and the power of nodes, in the number of
 218 clusters\dots{} can lead to very different number of iterations and so to very
 219 different execution times.
 220
 221
 222
 223
 224 \section{SimGrid}
 225
 226 SimGrid~\cite{SimGrid,casanova+legrand+quinson.2008.simgrid} is a simulation
 227 framework to study the behavior of large-scale distributed systems.  As its name
 228 says, it emanates from the grid computing community, but is nowadays used to
 229 study grids, clouds, HPC or peer-to-peer systems.  The early versions of SimGrid
 230 date from 1999, but it's still actively developed and distributed as an open
 231 source software.  Today, it's one of the major generic tools in the field of
 232 simulation for large-scale distributed systems.
 233
 234 SimGrid provides several programming interfaces: MSG to simulate Concurrent
 235 Sequential Processes, SimDAG to simulate DAGs of (parallel) tasks, and SMPI to
 236 run real applications written in MPI~\cite{MPI}.  Apart from the native C
 237 interface, SimGrid provides bindings for the C++, Java, Lua and Ruby programming
 238 languages.  SMPI is the interface that has been used for the work exposed in
 239 this paper.  The SMPI interface implements about \np[\%]{80} of the MPI 2.0
 240 standard~\cite{bedaride:hal-00919507}, and supports applications written in C or
 241 Fortran, with little or no modifications.
 242
 243 With SimGrid, the execution of a distributed application is simulated on a
 244 single machine.  The application code is really executed, but some operations
 245 like the communications are intercepted to be simulated according to the
 246 characteristics of the simulated execution platform.  The description of this
 247 target platform is given as an input for the execution, by the mean of an XML
 248 file.  It describes the properties of the platform, such as the computing node
 249 with their computing power, the interconnection links with their bandwidth and
 250 latency, and the routing strategy.  The simulated running time of the
 251 application is computed according to these properties.
 252
 253 \AG{Faut-il ajouter quelque-chose ?}
 254
 255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 256 \section{Simulation of the multisplitting method}
 257 %Décrire le problème (algo) traité ainsi que le processus d'adaptation à SimGrid.
 258 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
 259 \begin{equation*}
 260   \left(\begin{array}{ccc}
 261       A_{11} & \cdots & A_{1L} \\
 262       \vdots & \ddots & \vdots\\
 263       A_{L1} & \cdots & A_{LL}
 264     \end{array} \right)
 265   \times
 266   \left(\begin{array}{c}
 267       X_1 \\
 268       \vdots\\
 269       X_L
 270     \end{array} \right)
 271   =
 272   \left(\begin{array}{c}
 273       B_1 \\
 274       \vdots\\
 275       B_L
 276     \end{array} \right)
 277 \end{equation*}
 278 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$.
 279
 280 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
 281 \begin{equation}
 282   \label{eq:4.1}
 283   \left\{
 284     \begin{array}{l}
 285       A_{ll}X_l = Y_l \text{, such that}\\
 286       Y_l = B_l - \displaystyle\sum_{\substack{m=1\\ m\neq l}}^{L}A_{lm}X_m
 287     \end{array}
 288   \right.
 289 \end{equation}
 290 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.
 291
 292 \begin{figure}[!t]
 293   %%% IEEE instructions forbid to use an algorithm environment here, use figure
 294   %%% instead
 295 \begin{algorithmic}[1]
 296 \Input $A_l$ (sparse sub-matrix), $B_l$ (right-hand side sub-vector)
 297 \Output $X_l$ (solution sub-vector)\vspace{0.2cm}
 298 \State Load $A_l$, $B_l$
 299 \State Set the initial guess $x^0$
 300 \For {$k=0,1,2,\ldots$ until the global convergence}
 301 \State Restart outer iteration with $x^0=x^k$
 302 \State Inner iteration: \Call{InnerSolver}{$x^0$, $k+1$}
 303 \State\label{algo:01:send} Send shared elements of $X_l^{k+1}$ to neighboring clusters
 304 \State\label{algo:01:recv} Receive shared elements in $\{X_m^{k+1}\}_{m\neq l}$
 305 \EndFor
 306
 307 \Statex
 308
 309 \Function {InnerSolver}{$x^0$, $k$}
 310 \State Compute local right-hand side $Y_l$:
 311        \begin{equation*}
 312          Y_l = B_l - \sum\nolimits^L_{\substack{m=1\\ m\neq l}}A_{lm}X_m^0
 313        \end{equation*}
 314 \State Solving sub-system $A_{ll}X_l^k=Y_l$ with the parallel GMRES method
 315 \State \Return $X_l^k$
 316 \EndFunction
 317 \end{algorithmic}
 318 \caption{A multisplitting solver with GMRES method}
 319 \label{algo:01}
 320 \end{figure}
 321
 322 Algorithm on Figure~\ref{algo:01} shows the main key points of the
 323 multisplitting method to solve a large sparse linear system. This algorithm is
 324 based on an outer-inner iteration method where the parallel synchronous GMRES
 325 method is used to solve the inner iteration. It is executed in parallel by each
 326 cluster of processors. For all $l,m\in\{1,\ldots,L\}$, the matrices and vectors
 327 with the subscript $l$ represent the local data for cluster $l$, while
 328 $\{A_{lm}\}_{m\neq l}$ are off-diagonal matrices of sparse matrix $A$ and
 329 $\{X_m\}_{m\neq l}$ contain vector elements of solution $x$ shared with
 330 neighboring clusters. At every outer iteration $k$, asynchronous communications
 331 are performed between processors of the local cluster and those of distant
 332 clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in
 333 Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are
 334 exchanged by message passing using MPI non-blocking communication routines.
 335
 336 \begin{figure}[!t]
 337 \centering
 338   \includegraphics[width=60mm,keepaspectratio]{clustering}
 339 \caption{Example of three clusters of processors interconnected by a virtual unidirectional ring network.}
 340 \label{fig:4.1}
 341 \end{figure}
 342
 343 The global convergence of the asynchronous multisplitting solver is detected
 344 when the clusters of processors have all converged locally. We implemented the
 345 global convergence detection process as follows. On each cluster a master
 346 processor is designated (for example the processor with rank 1) and masters of
 347 all clusters are interconnected by a virtual unidirectional ring network (see
 348 Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around
 349 the virtual ring from a master processor to another until the global convergence
 350 is achieved. So starting from the cluster with rank 1, each master processor $i$
 351 sets the token to \textit{True} if the local convergence is achieved or to
 352 \text\it{False} otherwise, and sends it to master processor $i+1$. Finally, the
 353 global convergence is detected when the master of cluster 1 receives from the
 354 master of cluster $L$ a token set to \textit{True}. In this case, the master of
 355 cluster 1 broadcasts a stop message to masters of other clusters. In this work,
 356 the local convergence on each cluster $l$ is detected when the following
 357 condition is satisfied
 358 \begin{equation*}
 359   (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)
 360 \end{equation*}
 361 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}$.
 362
 363 \LZK{Description du processus d'adaptation de l'algo multisplitting à SimGrid}
 364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 365 We did not encounter major blocking problems when adapting the multisplitting
 366 algorithm previously described to a simulation environment like SimGrid unless
 367 some code debugging. Indeed, apart from the review of the program sequence for
 368 asynchronous exchanges between the six neighbors of each point in a submatrix
 369 within a cluster or between clusters, the algorithm was executed successfully
 370 with SMPI and provided identical outputs as those obtained with direct execution
 371 under MPI. In synchronous mode, the execution of the program raised no
 372 particular issue but in asynchronous mode, the review of the sequence of
 373 MPI\_Isend, MPI\_Irecv and MPI\_Waitall instructions and with the addition of
 374 the primitive MPI\_Test was needed to avoid a memory fault due to an infinite
 375 loop resulting from the non-convergence of the algorithm. Note here that the use
 376 of SMPI functions optimizer for memory footprint and CPU usage is not
 377 recommended knowing that one wants to get real results by simulation.  As
 378 mentioned, upon this adaptation, the algorithm is executed as in the real life
 379 in the simulated environment after the following minor changes. First, all
 380 declared global variables have been moved to local variables for each
 381 subroutine. In fact, global variables generate side effects arising from the
 382 concurrent access of shared memory used by threads simulating each computing
 383 units in the SimGrid architecture. Second, the alignment of certain types of
 384 variables such as ``long int'' had also to be reviewed. Finally, some
 385 compilation errors on MPI\_Waitall and MPI\_Finalize primitives have been fixed
 386 with the latest version of SimGrid.  In total, the initial MPI program running
 387 on the simulation environment SMPI gave after a very simple adaptation the same
 388 results as those obtained in a real environment. We have tested in synchronous
 389 mode with a simulated platform starting from a modest 2 or 3 clusters grid to a
 390 larger configuration like simulating Grid5000 with more than 1500 hosts with
 391 5000 cores~\cite{bolze2006grid}. Once the code debugging and adaptation were
 392 complete, the next section shows our methodology and experimental results.
 393
 394
 395 \section{Experimental results}
 396
 397 When the \emph{real} application runs in the simulation environment and produces the expected results, varying the input
 398 parameters and the program arguments allows us to compare outputs from the code execution. We have noticed from this
 399 study that the results depend on the following parameters:
 400 \begin{itemize}
 401 \item At the network level, we found that the most critical values are the
 402   bandwidth (bw) and the network latency (lat).
 403 \item Hosts power (GFlops) can also influence on the results.
 404 \item Finally, when submitting job batches for execution, the arguments values
 405   passed to the program like the maximum number of iterations or the
 406   \emph{external} precision are critical. They allow to ensure not only the
 407   convergence of the algorithm but also to get the main objective of the
 408   experimentation of the simulation in having an execution time in asynchronous
 409   less than in synchronous mode (i.e. speed-up less than 1).
 410 \end{itemize}
 411
 412 A priori, obtaining a speedup less than 1 would be difficult in a local area
 413 network configuration where the synchronous mode will take advantage on the
 414 rapid exchange of information on such high-speed links. Thus, the methodology
 415 adopted was to launch the application on clustered network. In this last
 416 configuration, degrading the inter-cluster network performance will
 417 \emph{penalize} the synchronous mode allowing to get a speedup lower than 1.
 418 This action simulates the case of clusters linked with long distance network
 419 like Internet.
 420
 421 As a first step, the algorithm was run on a network consisting of two clusters
 422 containing 50 hosts each, totaling 100 hosts. Various combinations of the above
 423 factors have providing the results shown in Table~\ref{tab.cluster.2x50} with a
 424 matrix size ranging from $N_x = N_y = N_z = \text{62}$ to 171 elements or from
 425 $\text{62}^\text{3} = \text{\np{238328}}$ to $\text{171}^\text{3} =
 426 \text{\np{5211000}}$ entries.
 427
 428 % use the same column width for the following three tables
 429 \newlength{\mytablew}\settowidth{\mytablew}{\footnotesize\np{E-11}}
 430 \newenvironment{mytable}[1]{% #1: number of columns for data
 431   \renewcommand{\arraystretch}{1.3}%
 432   \begin{tabular}{|>{\bfseries}r%
 433                   |*{#1}{>{\centering\arraybackslash}p{\mytablew}|}}}{%
 434     \end{tabular}}
 435
 436 \begin{table}[!t]
 437   \centering
 438   \caption{2 clusters, each with 50 nodes}
 439   \label{tab.cluster.2x50}
 440
 441   \begin{mytable}{6}
 442     \hline
 443     bw
 444     & 5         & 5         & 5         & 5         & 5         & 50 \\
 445     \hline
 446     lat
 447     & 0.02      & 0.02      & 0.02      & 0.02      & 0.02      & 0.02 \\
 448     \hline
 449     power
 450     & 1         & 1         & 1         & 1.5       & 1.5       & 1.5 \\
 451     \hline
 452     size
 453     & 62        & 62        & 62        & 100       & 100       & 110 \\
 454     \hline
 455     Prec/Eprec
 456     & \np{E-5}  & \np{E-8}  & \np{E-9}  & \np{E-11} & \np{E-11} & \np{E-11} \\
 457     \hline
 458     speedup
 459     & 0.396     & 0.392     & 0.396     & 0.391     & 0.393     & 0.395 \\
 460     \hline
 461   \end{mytable}
 462
 463   \smallskip
 464
 465   \begin{mytable}{6}
 466     \hline
 467     bw
 468     & 50        & 50        & 50        & 50        & 10        & 10 \\
 469     \hline
 470     lat
 471     & 0.02      & 0.02      & 0.02      & 0.02      & 0.03      & 0.01 \\
 472     \hline
 473     power
 474     & 1.5       & 1.5       & 1.5       & 1.5       & 1         & 1.5 \\
 475     \hline
 476     size
 477     & 120       & 130       & 140       & 150       & 171       & 171 \\
 478     \hline
 479     Prec/Eprec
 480     & \np{E-11} & \np{E-11} & \np{E-11} & \np{E-11} & \np{E-5}  & \np{E-5} \\
 481     \hline
 482     speedup
 483     & 0.398     & 0.388     & 0.393     & 0.394     & 0.63      & 0.778 \\
 484     \hline
 485   \end{mytable}
 486 \end{table}
 487
 488 Then we have changed the network configuration using three clusters containing
 489 respectively 33, 33 and 34 hosts, or again by on hundred hosts for all the
 490 clusters. In the same way as above, a judicious choice of key parameters has
 491 permitted to get the results in Table~\ref{tab.cluster.3x33} which shows the
 492 speedups less than 1 with a matrix size from 62 to 100 elements.
 493
 494 \begin{table}[!t]
 495   \centering
 496   \caption{3 clusters, each with 33 nodes}
 497   \label{tab.cluster.3x33}
 498
 499   \begin{mytable}{6}
 500     \hline
 501     bw
 502     & 10       & 5        & 4        & 3        & 2        & 6 \\
 503     \hline
 504     lat
 505     & 0.01     & 0.02     & 0.02     & 0.02     & 0.02     & 0.02 \\
 506     \hline
 507     power
 508     & 1        & 1        & 1        & 1        & 1        & 1 \\
 509     \hline
 510     size
 511     & 62       & 100      & 100      & 100      & 100      & 171 \\
 512     \hline
 513     Prec/Eprec
 514     & \np{E-5} & \np{E-5} & \np{E-5} & \np{E-5} & \np{E-5} & \np{E-5} \\
 515     \hline
 516     speedup
 517     & 0.997    & 0.99     & 0.93     & 0.84     & 0.78     & 0.99 \\
 518     \hline
 519   \end{mytable}
 520 \end{table}
 521
 522 In a final step, results of an execution attempt to scale up the three clustered
 523 configuration but increasing by two hundreds hosts has been recorded in
 524 Table~\ref{tab.cluster.3x67}.
 525
 526 \begin{table}[!t]
 527   \centering
 528   \caption{3 clusters, each with 66 nodes}
 529   \label{tab.cluster.3x67}
 530
 531   \begin{mytable}{1}
 532     \hline
 533     bw         & 1 \\
 534     \hline
 535     lat        & 0.02 \\
 536     \hline
 537     power      & 1 \\
 538     \hline
 539     size       & 62 \\
 540     \hline
 541     Prec/Eprec & \np{E-5} \\
 542     \hline
 543     speedup    & 0.9 \\
 544     \hline
 545   \end{mytable}
 546 \end{table}
 547
 548 Note that the program was run with the following parameters:
 549
 550 \paragraph*{SMPI parameters}
 551
 552 \begin{itemize}
 553         \item HOSTFILE: Hosts file description.
 554         \item PLATFORM: file description of the platform architecture : clusters (CPU power,
 555 \dots{}), intra cluster network description, inter cluster network (bandwidth bw,
 556 lat latency, \dots{}).
 557 \end{itemize}
 558
 559
 560 \paragraph*{Arguments of the program}
 561
 562 \begin{itemize}
 563         \item Description of the cluster architecture;
 564         \item Maximum number of internal and external iterations;
 565         \item Internal and external precisions;
 566         \item Matrix size $N_x$, $N_y$ and $N_z$;
 567         \item Matrix diagonal value: \np{6.0};
 568         \item Execution Mode: synchronous or asynchronous.
 569 \end{itemize}
 570
 571 \paragraph*{Interpretations and comments}
 572
 573 After analyzing the outputs, generally, for the configuration with two or three
 574 clusters including one hundred hosts (Tables~\ref{tab.cluster.2x50}
 575 and~\ref{tab.cluster.3x33}), some combinations of the used parameters affecting
 576 the results have given a speedup less than 1, showing the effectiveness of the
 577 asynchronous performance compared to the synchronous mode.
 578
 579 In the case of a two clusters configuration, Table~\ref{tab.cluster.2x50} shows
 580 that with a deterioration of inter cluster network set with \np[Mbit/s]{5} of
 581 bandwidth, a latency in order of a hundredth of a millisecond and a system power
 582 of one GFlops, an efficiency of about \np[\%]{40} in asynchronous mode is
 583 obtained for a matrix size of 62 elements. It is noticed that the result remains
 584 stable even if we vary the external precision from \np{E-5} to \np{E-9}. By
 585 increasing the problem size up to 100 elements, it was necessary to increase the
 586 CPU power of \np[\%]{50} to \np[GFlops]{1.5} for a convergence of the algorithm
 587 with the same order of asynchronous mode efficiency.  Maintaining such a system
 588 power but this time, increasing network throughput inter cluster up to
 589 \np[Mbit/s]{50}, the result of efficiency of about \np[\%]{40} is obtained with
 590 high external precision of \np{E-11} for a matrix size from 110 to 150 side
 591 elements.
 592
 593 For the 3 clusters architecture including a total of 100 hosts,
 594 Table~\ref{tab.cluster.3x33} shows that it was difficult to have a combination
 595 which gives an efficiency of asynchronous below \np[\%]{80}. Indeed, for a
 596 matrix size of 62 elements, equality between the performance of the two modes
 597 (synchronous and asynchronous) is achieved with an inter cluster of
 598 \np[Mbit/s]{10} and a latency of \np[ms]{E-1}. To challenge an efficiency by
 599 \np[\%]{78} with a matrix size of 100 points, it was necessary to degrade the
 600 inter cluster network bandwidth from 5 to \np[Mbit/s]{2}.
 601
 602 A last attempt was made for a configuration of three clusters but more powerful
 603 with 200 nodes in total. The convergence with a speedup of \np[\%]{90} was
 604 obtained with a bandwidth of \np[Mbit/s]{1} as shown in
 605 Table~\ref{tab.cluster.3x67}.
 606
 607 \section{Conclusion}
 608 The experimental results on executing a parallel iterative algorithm in
 609 asynchronous mode on an environment simulating a large scale of virtual
 610 computers organized with interconnected clusters have been presented.
 611 Our work has demonstrated that using such a simulation tool allow us to
 612 reach the following three objectives:
 613
 614 \begin{enumerate}
 615 \item To have a flexible configurable execution platform resolving the
 616 hard exercise to access to very limited but so solicited physical
 617 resources;
 618 \item to ensure the algorithm convergence with a reasonable time and
 619 iteration number ;
 620 \item and finally and more importantly, to find the correct combination
 621 of the cluster and network specifications permitting to save time in
 622 executing the algorithm in asynchronous mode.
 623 \end{enumerate}
 624 Our results have shown that in certain conditions, asynchronous mode is
 625 speeder up to \np[\%]{40} than executing the algorithm in synchronous mode
 626 which is not negligible for solving complex practical problems with more
 627 and more increasing size.
 628
 629  Several studies have already addressed the performance execution time of
 630 this class of algorithm. The work presented in this paper has
 631 demonstrated an original solution to optimize the use of a simulation
 632 tool to run efficiently an iterative parallel algorithm in asynchronous
 633 mode in a grid architecture.
 634
 635 \section*{Acknowledgment}
 636
 637 This work is partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01).
 638 \todo[inline]{The authors would like to thank\dots{}}
 639
 640
 641 % trigger a \newpage just before the given reference
 642 % number - used to balance the columns on the last page
 643 % adjust value as needed - may need to be readjusted if
 644 % the document is modified later
 645 \bibliographystyle{IEEEtran}
 646 \bibliography{IEEEabrv,hpccBib}
 647
 648 \end{document}
 649
 650 %%% Local Variables:
 651 %%% mode: latex
 652 %%% TeX-master: t
 653 %%% fill-column: 80
 654 %%% ispell-local-dictionary: "american"
 655 %%% End:
 656
 657 % LocalWords:  Ramamonjisoa Laiymani Arnaud Giersch Ziane Khodja Raphaël Femto
 658 % LocalWords:  Université Franche Comté IUT Montbéliard Maréchal Juin Inria Sud
 659 % LocalWords:  Ouest Vieille Talence cedex scalability experimentations HPC MPI
 660 % LocalWords:  Parallelization AIAC GMRES multi SMPI SISC SIAC SimDAG DAGs Lua
 661 % LocalWords:  Fortran GFlops priori Mbit de du fcomte multisplitting scalable
 662 % LocalWords:  SimGrid Belfort parallelize Labex ANR LABX IEEEabrv hpccBib