X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/blobdiff_plain/e2f7ea69b2321fbf77291f35360751e460a99f44..65f8be28e79668334c6fcbc3a2af46a7c8a2eab0:/BookGPU/Chapters/chapter12/ch12.tex

diff --git a/BookGPU/Chapters/chapter12/ch12.tex b/BookGPU/Chapters/chapter12/ch12.tex
index 3843597..5c0a5b2 100755
--- a/BookGPU/Chapters/chapter12/ch12.tex
+++ b/BookGPU/Chapters/chapter12/ch12.tex
@@ -47,7 +47,7 @@ CPU cluster and on a GPU cluster of solving large sparse linear systems.
 %%--------------------------%%
 \section{Krylov iterative methods}
 \label{ch12:sec:02}
-Let us consider the following system of $n$ linear equations\index{Sparse~linear~system}
+Let us consider the following system of $n$ linear equations\index{sparse linear system}
 in $\mathbb{R}$: 
 \begin{equation}
 Ax=b,
@@ -57,7 +57,7 @@ where $A\in\mathbb{R}^{n\times n}$ is a sparse nonsingular square matrix, $x\in\
 is the solution vector, $b\in\mathbb{R}^{n}$ is the right-hand side, and $n\in\mathbb{N}$ is a
 large integer number. 
 
-The iterative methods\index{Iterative~method} for solving the large sparse linear system~(\ref{ch12:eq:01})
+The iterative methods\index{iterative method} for solving the large sparse linear system~(\ref{ch12:eq:01})
 proceed by successive iterations of a same block of elementary operations, during which an
 infinite number of approximate solutions $\{x_k\}_{k\geq 0}$ is computed. Indeed, from an
 initial guess $x_0$, an iterative method determines at each iteration $k>0$ an approximate
@@ -68,20 +68,20 @@ x^{*}=\lim\limits_{k\to\infty}x_{k}=A^{-1}b.
 \end{equation}
 The number of iterations necessary to reach the exact solution $x^{*}$ is not known beforehand
 and can be infinite. In practice, an iterative method often finds an approximate solution $\tilde{x}$
-after a fixed number of iterations and/or when a given convergence criterion\index{Convergence}
+after a fixed number of iterations and/or when a given convergence criterion\index{convergence}
 is satisfied as follows:   
 \begin{equation}
 \|b-A\tilde{x}\| < \varepsilon,
 \label{ch12:eq:03}
 \end{equation}
-where $\varepsilon<1$ is the required convergence tolerance threshold\index{Convergence!Tolerance~threshold}. 
+where $\varepsilon<1$ is the required convergence tolerance threshold\index{convergence!tolerance threshold}. 
 
 Some of the most iterative methods that have proven their efficiency for solving large sparse
-linear systems are those called \textit{Krylov subspace methods}~\cite{ch12:ref1}\index{Iterative~method!Krylov~subspace}.
+linear systems are those called \textit{Krylov subspace methods}~\cite{ch12:ref1}\index{iterative method!Krylov subspace}.
 In the present chapter, we describe two Krylov methods which are widely used: the CG method (conjugate
 gradient method) and the GMRES method (generalized minimal residual method). In practice, the
 Krylov subspace methods are usually used with preconditioners that allow the improvement of their
-convergence. So, in what follows, the CG and GMRES methods are used to solve the left-preconditioned\index{Sparse~linear~system!Preconditioned}
+convergence. So, in what follows, the CG and GMRES methods are used to solve the left-preconditioned\index{sparse linear system!preconditioned}
 sparse linear system:
 \begin{equation}
 M^{-1}Ax=M^{-1}b,
@@ -99,14 +99,14 @@ It is one of the well-known iterative methods to solve large sparse linear syste
 can be adapted to solve nonlinear equations and optimization problems. However, it can only be applied
 to problems with positive definite symmetric matrices.
 
-The main idea of the CG method\index{Iterative~method!CG} is the computation of a sequence of approximate
-solutions $\{x_k\}_{k\geq 0}$ in a Krylov subspace\index{Iterative~method!Krylov~subspace} of order $k$ as
+The main idea of the CG method\index{iterative method!CG} is the computation of a sequence of approximate
+solutions $\{x_k\}_{k\geq 0}$ in a Krylov subspace\index{iterative method!Krylov~subspace} of order $k$ as
 follows: 
 \begin{equation}
 x_k \in x_0 + \mathcal{K}_k(A,r_0),
 \label{ch12:eq:04}
 \end{equation}
-such that the Galerkin condition\index{Galerkin~condition} must be satisfied:
+such that the Galerkin condition\index{Galerkin condition} must be satisfied:
 \begin{equation}
 r_k \bot \mathcal{K}_k(A,r_0),
 \label{ch12:eq:05}
@@ -181,15 +181,15 @@ the recurrences~(\ref{ch12:eq:08}) and~(\ref{ch12:eq:09}) allow the deduction th
 \end{algorithm}
 
 Algorithm~\ref{ch12:alg:01} shows the main key points of the preconditioned CG method. It allows
-the solving the left-preconditioned\index{Sparse~linear~system!Preconditioned} sparse linear system~(\ref{ch12:eq:11}).
+the solving the left-preconditioned\index{sparse linear system!preconditioned} sparse linear system~(\ref{ch12:eq:11}).
 In this algorithm, $\varepsilon$ is the convergence tolerance threshold, $maxiter$ is the maximum
 number of iterations, and $(\cdot,\cdot)$ defines the dot product between two vectors in $\mathbb{R}^{n}$.
 At every iteration, a direction vector $p_k$ is determined, so that it is orthogonal to the preconditioned
 residual $z_k$ and to the direction vectors $\{p_i\}_{i<k}$ previously determined (from line~$8$ to
 line~$13$). Then, at lines~$16$ and~$17$, the iterate $x_k$ and the residual $r_k$ are computed using
 formulas~(\ref{ch12:eq:07}) and~(\ref{ch12:eq:08}), respectively. The CG method converges after, at
-most, $n$ iterations. In practice, the CG algorithm stops when the tolerance threshold\index{Convergence!Tolerance~threshold}
-$\varepsilon$ and/or the maximum number of iterations\index{Convergence!Maximum~number~of~iterations}
+most, $n$ iterations. In practice, the CG algorithm stops when the tolerance threshold\index{convergence!tolerance threshold}
+$\varepsilon$ and/or the maximum number of iterations\index{convergence!maximum number of iterations}
 $maxiter$ is reached.
 
 
@@ -198,27 +198,27 @@ $maxiter$ is reached.
 \subsection{GMRES method} 
 \label{ch12:sec:02.02}
 The iterative GMRES method was developed by Saad and Schultz in 1986~\cite{ch12:ref3} as a generalization
-of the minimum residual method MINRES~\cite{ch12:ref4}\index{Iterative~method!MINRES}. Indeed, GMRES can
+of the minimum residual method MINRES~\cite{ch12:ref4}\index{iterative method!MINRES}. Indeed, GMRES can
 be applied for solving symmetric or nonsymmetric linear systems. 
 
-The main principle of the GMRES method\index{Iterative~method!GMRES} is to find an approximation minimizing
+The main principle of the GMRES method\index{iterative method!GMRES} is to find an approximation minimizing
 at best the residual norm. In fact, GMRES computes a sequence of approximate solutions $\{x_k\}_{k>0}$ in
-a Krylov subspace\index{Iterative~method!Krylov~subspace} $\mathcal{K}_k$ as follows:
+a Krylov subspace\index{iterative method!Krylov subspace} $\mathcal{K}_k$ as follows:
 \begin{equation}
 \begin{array}{ll}
 x_k \in x_0 + \mathcal{K}_k(A, v_1),& v_1=\frac{r_0}{\|r_0\|_2},
 \end{array}
 \label{ch12:eq:12}
 \end{equation} 
-so that the Petrov-Galerkin condition\index{Petrov-Galerkin~condition} is satisfied:
+so that the Petrov-Galerkin condition\index{Petrov-Galerkin condition} is satisfied:
 \begin{equation}
 \begin{array}{ll}
 r_k \bot A \mathcal{K}_k(A, v_1).
 \end{array}
 \label{ch12:eq:13}
 \end{equation}
-GMRES uses the Arnoldi process~\cite{ch12:ref5}\index{Iterative~method!Arnoldi~process} to construct an
-orthonormal basis $V_k$ for the Krylov subspace $\mathcal{K}_k$ and an upper Hessenberg matrix\index{Hessenberg~matrix}
+GMRES uses the Arnoldi iterations~\cite{ch12:ref5}\index{iterative method!Arnoldi iterations} to construct an
+orthonormal basis $V_k$ for the Krylov subspace $\mathcal{K}_k$ and an upper Hessenberg matrix\index{Hessenberg matrix}
 $\bar{H}_k$ of order $(k+1)\times k$:
 \begin{equation}
 \begin{array}{ll}
@@ -311,16 +311,16 @@ $V$ to $m$ orthogonal vectors.
 \end{algorithm}
 
 Algorithm~\ref{ch12:alg:02} shows the key points of the GMRES method with restarts.
-It solves the left-preconditioned\index{Sparse~linear~system!Preconditioned} sparse linear
+It solves the left-preconditioned\index{sparse linear system!preconditioned} sparse linear
 system~(\ref{ch12:eq:11}), such that $M$ is the preconditioning matrix. At each iteration
-$k$, GMRES uses the Arnoldi process\index{Iterative~method!Arnoldi~process} (defined from
+$k$, GMRES uses the Arnoldi iterations\index{iterative method!Arnoldi iterations} (defined from
 line~$7$ to line~$17$) to construct a basis $V_m$ of $m$ orthogonal vectors and an upper
-Hessenberg matrix\index{Hessenberg~matrix} $\bar{H}_m$ of size $(m+1)\times m$. Then, it
+Hessenberg matrix\index{Hessenberg matrix} $\bar{H}_m$ of size $(m+1)\times m$. Then, it
 solves the linear least-squares problem of size $m$ to find the vector $y\in\mathbb{R}^{m}$
 which minimizes at best the residual norm (line~$18$). Finally, it computes an approximate
 solution $x_m$ in the Krylov subspace spanned by $V_m$ (line~$19$). The GMRES algorithm is
 stopped when the residual norm is sufficiently small ($\|r_m\|_2<\varepsilon$) and/or the
-maximum number of iterations\index{Convergence!Maximum~number~of~iterations} ($maxiter$)
+maximum number of iterations\index{convergence!maximum number of iterations} ($maxiter$)
 is reached.
 
 
@@ -329,11 +329,11 @@ is reached.
 %%--------------------------%%
 \section{Parallel implementation on a GPU cluster}
 \label{ch12:sec:03}
-In this section, we present the parallel algorithms of both iterative CG\index{Iterative~method!CG}
-and GMRES\index{Iterative~method!GMRES} methods for GPU clusters. The implementation is performed on
+In this section, we present the parallel algorithms of both iterative CG\index{iterative method!CG}
+and GMRES\index{iterative method!GMRES} methods for GPU clusters. The implementation is performed on
 a GPU cluster composed of different computing nodes, such that each node is a CPU core managed by one
 MPI (message passing interface) process and equipped with a GPU card. The parallelization of these algorithms is carried out by
-using the MPI communication routines between the GPU computing nodes\index{Computing~node} and the
+using the MPI communication routines between the GPU computing nodes\index{computing node} and the
 CUDA (compute unified device architecture) programming environment inside each node. In what follows, the algorithms of the iterative methods
 are called iterative solvers.
 
@@ -400,15 +400,15 @@ solve the least-squares problem, and a kernel to update the elements of the solu
 vector $x$.
 
 The least-squares problem in the GMRES method is solved by performing a QR factorization
-on the Hessenberg matrix\index{Hessenberg~matrix} $\bar{H}_m$ with plane rotations and,
+on the Hessenberg matrix\index{Hessenberg matrix} $\bar{H}_m$ with plane rotations and,
 then, solving the triangular system by backward substitutions to compute $y$. Consequently,
 solving the least-squares problem on the GPU is not efficient. Indeed, the triangular
 solves are not easy to parallelize and inefficient on GPUs. However, the least-squares
 problem to solve in the GMRES method with restarts has, generally, a very small size $m$.
 Therefore, we develop an inexpensive kernel which must be executed by a single CUDA thread. 
 
-The most important operation in CG\index{Iterative~method!CG} and GMRES\index{Iterative~method!GMRES}
-methods is the SpMV multiplication (sparse matrix-vector multiplication)\index{SpMV~multiplication},
+The most important operation in CG\index{iterative method!CG} and GMRES\index{iterative method!GMRES}
+methods is the SpMV multiplication (sparse matrix-vector multiplication)\index{SpMV multiplication},
 because it is often an expensive operation in terms of execution time and memory space.
 Moreover, it requires taking care of the storage format of the sparse matrix in the
 memory. Indeed, the naive storage, row-by-row or column-by-column, of a sparse matrix
@@ -416,12 +416,12 @@ can cause a significant waste of memory space and execution time. In addition, t
 nature of the matrix often leads to irregular memory accesses to read the matrix nonzero
 values. So, the computation of the SpMV multiplication on GPUs can involve noncoalesced
 accesses to the global memory, which slows down its performances even more. One of the
-most efficient compressed storage formats\index{Compressed~storage~format} of sparse
-matrices on GPUs is the HYB (hybrid)\index{Compressed~storage~format!HYB} format~\cite{ch12:ref7}.
+most efficient compressed storage formats\index{compressed storage format} of sparse
+matrices on GPUs is the HYB (hybrid)\index{compressed storage format!HYB} format~\cite{ch12:ref7}.
 It is a combination of ELLpack (ELL) and Coordinate (COO) formats. Indeed, it stores
-a typical number of nonzero values per row in ELL\index{Compressed~storage~format!ELL}
+a typical number of nonzero values per row in ELL\index{compressed storage format!ELL}
 format and the remaining entries of exceptional rows in COO format. It combines the efficiency
-of ELL due to the regularity of its memory accesses and the flexibility of COO\index{Compressed~storage~format!COO}
+of ELL due to the regularity of its memory accesses and the flexibility of COO\index{compressed storage format!COO}
 which is insensitive to the matrix structure. Consequently, we use the HYB kernel~\cite{ch12:ref8}
 developed by NVIDIA to implement the SpMV multiplication of CG and GMRES methods on GPUs.
 Moreover, to avoid the noncoalesced accesses to the high-latency global memory, we fill
@@ -434,10 +434,10 @@ the elements of the iterate vector $x$ in the cached texture memory.
 \label{ch12:sec:03.03}
 All the computing nodes of the GPU cluster execute in parallel the same iterative solver
 (Algorithm~\ref{ch12:alg:01} or Algorithm~\ref{ch12:alg:02}) adapted to GPUs, but on their
-own portions of the sparse linear system\index{Sparse~linear~system}: $M^{-1}_iA_ix_i=M^{-1}_ib_i$,
+own portions of the sparse linear system\index{sparse linear system}: $M^{-1}_iA_ix_i=M^{-1}_ib_i$,
 $0\leq i<p$. However, in order to solve the complete sparse linear system~(\ref{ch12:eq:11}),
 synchronizations must be performed between the local computations of the computing nodes over
-the cluster. In what follows, two computing nodes sharing data are called neighboring nodes\index{Neighboring~node}.
+the cluster. In what follows, two computing nodes sharing data are called neighboring nodes\index{neighboring node}.
 
 As already mentioned, the most important operation of CG and GMRES methods is the SpMV multiplication.
 In the parallel implementation of the iterative methods, each computing node $i$ performs the
@@ -452,13 +452,13 @@ In the same way, the vector used to construct the orthonormal basis of the Krylo
 $p$ and $v$ in CG and GMRES methods, respectively) is composed of a local subvector and a shared
 subvector. 
 
-Therefore, before computing the SpMV multiplication\index{SpMV~multiplication}, the neighboring
-nodes\index{Neighboring~node} over the GPU cluster must exchange between them the shared vector
+Therefore, before computing the SpMV multiplication\index{SpMV multiplication}, the neighboring
+nodes\index{neighboring node} over the GPU cluster must exchange between them the shared vector
 elements necessary to compute this multiplication. First, each computing node determines, in its
 local subvector, the vector elements needed by other nodes. Then, the neighboring nodes exchange
 between them these shared vector elements. The data exchanges are implemented by using the MPI
-point-to-point communication routines: blocking\index{MPI~subroutines!Blocking} sends with \verb+MPI_Send()+
-and nonblocking\index{MPI~subroutines!Nonblocking} receives with \verb+MPI_Irecv()+. Figure~\ref{ch12:fig:02}
+point-to-point communication routines: blocking\index{MPI!blocking} sends with \verb+MPI_Send()+
+and nonblocking\index{MPI!nonblocking} receives with \verb+MPI_Irecv()+. Figure~\ref{ch12:fig:02}
 shows an example of data exchanges between \textit{Node 1} and its neighbors \textit{Node 0}, \textit{Node 2},
 and \textit{Node 3}. In this example, the iterate matrix $A$ split between these four computing
 nodes is that presented in Figure~\ref{ch12:fig:01}.
@@ -484,14 +484,14 @@ storage formats. Figure~\ref{ch12:fig:03} shows a reordering of a sparse submatr
 \label{ch12:fig:03}
 \end{figure}
 
-A GPU cluster\index{GPU~cluster} is a parallel platform with a distributed memory. So, the synchronizations
+A GPU cluster\index{GPU!cluster}\index{multi-GPU} is a parallel platform with a distributed memory. So, the synchronizations
 and communication data between GPU nodes are carried out by passing messages. However, a GPU cannot exchange data
 with other GPUs in a direct way. Then, CPUs via MPI processes are in charge of the synchronizations within the GPU
 cluster. Consequently, the vector elements to be exchanged must be copied from the GPU memory to the CPU memory
 and vice versa before and after the synchronization operation between CPUs. We have used the CUBLAS\index{CUBLAS}
 communication subroutines to perform the data transfers between a CPU core and its GPU: \verb+cublasGetVector()+
 and \verb+cublasSetVector()+. Finally, in addition to the data exchanges, GPU nodes perform reduction operations
-to compute in parallel the dot products and Euclidean norms. This is implemented by using the MPI global communication\index{MPI~subroutines!Global}
+to compute in parallel the dot products and Euclidean norms. This is implemented by using the MPI global communication\index{MPI!global}
 \verb+MPI_Allreduce()+.
 
 
@@ -507,7 +507,7 @@ by a $20$GB/s InfiniBand network. Each machine is a Quad-Core Xeon E5530 CPU run
 providing $12$GB of RAM with a memory bandwidth of $25.6$GB/s. In addition, two Tesla C1060 GPUs are
 connected to each machine via a PCI-Express 16x Gen 2.0 interface with a throughput of $8$GB/s. A
 Tesla C1060 GPU contains $240$ cores running at $1.3$GHz and providing a global memory of $4$GB with
-a memory bandwidth of $102$GB/s. Figure~\ref{ch12:fig:04} shows the general scheme of the GPU cluster\index{GPU~cluster}
+a memory bandwidth of $102$GB/s. Figure~\ref{ch12:fig:04} shows the general scheme of the GPU cluster\index{GPU!cluster}
 that we used in the experimental tests.
 
 Linux cluster version 2.6.39 OS is installed on CPUs. C programming language is used to code
@@ -526,7 +526,7 @@ is managed by one MPI process and is composed of one CPU core and one GPU card.
 All tests are made on double-precision floating point operations. The parameters of both linear
 solvers are initialized as follows: the residual tolerance threshold $\varepsilon=10^{-12}$, the
 maximum number of iterations $maxiter=500$, the right-hand side $b$ is filled with $1.0$, and the
-initial guess $x_0$ is filled with $0.0$. In addition, we limited the Arnoldi process\index{Iterative~method!Arnoldi~process}
+initial guess $x_0$ is filled with $0.0$. In addition, we limited the Arnoldi iterations\index{iterative method!Arnoldi iterations}
 used in the GMRES method to $16$ iterations ($m=16$). For the sake of simplicity, we have chosen
 the preconditioner $M$ as the main diagonal of the sparse matrix $A$. Indeed, it allows us to easily
 compute the required inverse matrix $M^{-1}$, and it provides a relatively good preconditioning for
@@ -548,8 +548,10 @@ which are the number of rows, the total number of nonzero values, and the maxima
 the present chapter, the bandwidth of a sparse matrix is defined as the number of matrix columns separating
 the first and the last nonzero value on a matrix row.
 
+
 \begin{table}
 \centering
+\begin{small}
 \begin{tabular}{|c|c|c|c|c|}
 \hline
 {\bf Matrix Type}             & {\bf Matrix Name} & {\bf \# Rows} & {\bf \# Nonzeros} & {\bf Bandwidth} \\ \hline \hline
@@ -578,10 +580,12 @@ the first and the last nonzero value on a matrix row.
 
                               & torso3            & $259,156$     & $4,429,042$  & $216,854$  \\ \hline
 \end{tabular}
+\end{small}
 \caption{Main characteristics of sparse matrices chosen from the University of Florida collection.}
 \label{ch12:tab:01}
 \end{table}
 
+
 \begin{table}[!h]
 \begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|} 
@@ -607,6 +611,7 @@ thermal2          & $1.172s$           & $0.622s$            & $1.88$        & $
 
 \begin{table}[!h]
 \begin{center}
+\begin{small}
 \begin{tabular}{|c|c|c|c|c|c|c|} 
 \hline
 {\bf Matrix}     & $\mathbf{Time_{cpu}}$ & $\mathbf{Time_{gpu}}$ & $\mathbf{\tau}$  & $\mathbf{\#~Iter.}$ & $\mathbf{Prec.}$     & $\mathbf{\Delta}$   \\ \hline \hline
@@ -635,6 +640,7 @@ poli\_large       & $0.097s$           & $0.095s$            & $1.02$        & $
 
 torso3            & $4.242s$           & $2.030s$            & $2.09$        & $175$          & $2.69e$-$10$     & $1.78e$-$14$ \\ \hline
 \end{tabular}
+\end{small}
 \caption{Performances of the parallel GMRES method on a cluster 24 CPU cores vs. on cluster of 12 GPUs.}
 \label{ch12:tab:03}
 \end{center}
@@ -649,7 +655,7 @@ of the CG method to solve the nonsymmetric systems. In both tables, the second a
 columns give, respectively, the execution times in seconds obtained on $24$ CPU cores
 ($Time_{cpu}$) and that obtained on $12$ GPUs ($Time_{gpu}$). Moreover, we take into account
 the relative gains $\tau$ of a solver implemented on the GPU cluster compared to the same
-solver implemented on the CPU cluster. The relative gains\index{Relative~gain}, presented
+solver implemented on the CPU cluster. The relative gains\index{relative gain}, presented
 in the fourth column, are computed as a ratio of the CPU execution time over the GPU
 execution time:
 \begin{equation}
@@ -739,10 +745,10 @@ GPUs. Obviously, we can notice from these tables that solving large sparse linea
 a GPU cluster is more efficient than on a CPU cluster (see relative gains $\tau$). We can also
 notice that the execution times of the CG method, whether in a CPU cluster or in a GPU cluster,
 are better than those of the GMRES method for solving large symmetric linear systems. In fact, the
-CG method is characterized by a better convergence\index{Convergence} rate and a shorter execution
+CG method is characterized by a better convergence\index{convergence} rate and a shorter execution
 time of an iteration than those of the GMRES method. Moreover, an iteration of the parallel GMRES
 method requires more data exchanges between computing nodes compared to the parallel CG method.
-
+\clearpage
 \begin{table}[!h]
 \begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|} 
@@ -769,6 +775,7 @@ on a cluster of 12 GPUs.}
 
 \begin{table}[!h]
 \begin{center}
+\begin{small}
 \begin{tabular}{|c|c|c|c|c|c|c|} 
 \hline
 {\bf Matrix}      & $\mathbf{Time_{cpu}}$ & $\mathbf{Time_{gpu}}$ & $\mathbf{\tau}$ & $\mathbf{\#~Iter.}$ & $\mathbf{Prec.}$ & $\mathbf{\Delta}$   \\ \hline \hline
@@ -797,6 +804,7 @@ poli\_large       & $8.515s$             & $1.053s$              & $8.09$
 
 torso3            & $31.463s$            & $3.681s$              & $8.55$          & $175$               & $2.69e$-$10$     & $2.66e$-$14$ \\ \hline
 \end{tabular}
+\end{small}
 \caption{Performances of the parallel GMRES method for solving linear systems associated to sparse banded matrices on a cluster of 24 CPU cores vs. 
 on a cluster of 12 GPUs.}
 \label{ch12:tab:06}