Abstract:

Multigrid methods are efficient and fast solvers for problems typically modeled by partial differential equations of elliptic type. For problems with complex geometries and local singularities stencil-type discrete operators on equidistant Cartesian grids need to be replaced by more flexible concepts for unstructured meshes in order to properly resolve all problem-inherent specifics and for maintaining a moderate number of unknowns. However, flexibility in the meshes goes along with severe drawbacks with respect to parallel execution – especially with respect to the definition of adequate smoothers. This point becomes in particular pronounced in the framework of fine-grained parallelism on GPUs with hundreds of execution units. We use the approach of matrix-based multigrid that has high flexibility and adapts well to the exigences of modern computing platforms.

In this work we investigate multi-colored Gauss-Seidel type smoothers, the power(q)-pattern enhanced multi-colored ILU(p) smoothers with fill-ins, and factorized sparse approximate inverse (FSAI) smoothers. These approaches provide efficient smoothers with a high degree of parallelism. In combination with matrix-based multigrid methods on unstructured meshes our smoothers provide powerful solvers that are applicable across a wide range of parallel computing platforms and almost arbitrary geometries. We describe the configuration of our smoothers in the context of the portable lmpLAtoolbox and the HiFlow3 parallel finite element package. In our approach, a single source code can be used across diverse platforms including multicore CPUs and GPUs. Highly optimized implementations are hidden behind a unified user interface. Efficiency and scalability of our multigrid solvers are demonstrated by means of a comprehensive performance analysis on multicore CPUs and GPUs.

V. Heuveline, D. Lukarski, N. Trost and J.-P. Weiss. Parallel Smoothers for Matrix-based Multigrid Methods on Unstructured Meshes Using Multicore CPUs and GPUs. EMCL Preprint Series No. 9. 2011.

Abstract:

A novel algorithm for solving in parallel a sparse triangular linear system on a graphical processing unit is proposed. It implements the solution of the triangular system in two phases. First, the analysis phase builds a dependency graph based on the matrix sparsity pattern and groups the independent rows into levels. Second, the solve phase obtains the full solution by iterating sequentially across the constructed levels. The solution elements corresponding to each single level are obtained at once in parallel. The numerical experiments are also presented and it is shown that the incomplete-LU and Cholesky preconditioned iterative methods, using the parallel sparse triangular solve algorithm, can achieve on average more than 2x speedup on graphical processing units (GPUs) over their CPU implementation.

(Maxim Naumov: “Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU”, NVIDIA Technical Report, June 2011. [WWW])

ofgpu is a free GPL library from Symscape that provides GPU linear solvers for OpenFOAM®. The experimental library targets NVIDIA CUDA devices on Windows, Linux, and (untested) Mac OS X. It uses the Cusp library’s Krylov solvers to produce equivalent GPU (CUDA-based) versions of the standard OpenFOAM linear solvers:

• PCG – Preconditioned conjugate gradient solver for symmetric matrices (e.g., p)
• PBiCG – Preconditioned biconjugate gradient solver for asymmetric matrices (e.g., Ux, k)

ofgpu also has support for the OpenFOAM preconditioners:

• no
• diagonal

For more details see “GPU Linear Solver Library for OpenFOAM”. OpenFOAM is a registered trademark of OpenCFD and is unaffiliated with Symscape.

Abstract:

The paper discusses a fast implementation of the conjugate gradient iterative method with E-field multilevel preconditioner applied to solving real symmetric and sparse systems obtained with vector finite element method. In order to accelerate computations, a graphics processing unit (GPU) was used and significant speed-up (2.61 fold) was achieved comparing to a central processing unit (CPU) based approach. These results indicate that performance of electromagnetic simulations can be significantly improved thereby enabling full wave optimization of microwave components in more manageable time.

(A. Dziekonski, A. Lamecki and M. Mrozowski: “GPU Acceleration of Multilevel Solvers for Analysis of Microwave Components With Finite Element Method”, IEEE Microwave and Wireless Components Letters 21(1) pp.1-3, Jan. 2011. [DOI])

MAGMA 1.0 RC1 is now available, including the MAGMA sources. MAGMA 1.0 RC1 is intended for a single CUDA enabled NVIDIA GPU. It extends version 0.2 by adding support for Fermi GPUs (see the sample performances for LU, QR, and Cholesky).

Included are routines for the following algorithms:

• LU, QR, and Cholesky factorizations in both real and complex arithmetic (single and double);
• Linear solvers based on LU, QR, and Cholesky in both real and complex arithmetic (single and double);
• Mixed-precision iterative refinement solvers based on LU, QR, and Cholesky in both real and complex arithmetic;
• MAGMA BLAS in real arithmetic (single and double), including gemm, gemv, symv, and trsm.

See the MAGMA homepage for a download link.

OpenNL (Open Numerical Library) is a library for solving sparse linear systems on CPUs and GPUs. Features include various preconditioned Krylov subspace solvers for several data structures. The library is explicitly designed for easy interfacing with existing codes and their storage schemes.

Highlights of version 3.2.1 include:

• Support for double precision on the GPU
• Support for the Fermi architecture

OpenCurrent version 1.1.0 has been released. OpenCurrent is a library for solving certains types of PDEs over 3D cartesian grids. It supports single and double precision, and includes solvers for Poisson equations, diffusion, and incompressible Navier-Stokes.

New features:

• Multi-GPU communication library
• Multi-GPU versions of Multigrid solver, Incompressible Navier-Stokes solver, and more
• NetCDF support now optional
• Support for Fermi/CUDA 3.0
• Numerous bug fixes and enhancements

Get it here: http://code.google.com/p/opencurrent/downloads/list

The Vienna Computing Library (ViennaCL) is a scientific computing library written in C++ and based on OpenCL. It allows simple, high-level access to the vast computing resources available on parallel architectures such as GPUs and is primarily focused on common linear algebra operations (BLAS level 1 and 2) and the solution of large systems of equations by means of iterative methods. The following iterative solvers are implemented:

• Conjugate Gradient (CG)
• Stabilized BiConjugate Gradient (BiCGStab)
• Generalized Minimum Residual (GMRES)

Read the rest of this entry »

OpenNL (Open Numerical Library) is a library for solving sparse linear systems, especially designed for the Computer Graphics community. The goal of OpenNL is to be as small as possible, while offering the subset of functionalities required by this application field. The Makefiles of OpenNL can generate a single .c and .h file that make it very easy to integrate into other projects. The distribution includes an implementation of a Least Squares Conformal Maps parameterization method.  The new version 3.0 of OpenNL includes support for CUDA (with Concurrent Number Cruncher and CUSP ELL formats).

This survey paper by D. Göddeke and R. Strzodka compares native double precision solvers for linear systems of equations as they typically arise in finite element discretizations with emulated- and mixed-precision schemes. Such schemes are particularly suitable for coupled hardware configurations such as GPUs and FPGAs, which serve as co-processors to the general purpose CPU. The results demonstrate that

1. accuracy is preserved even for very ill-conditioned systems,
2. significant speedups can be achieved (time aspect, GPUs) and
3. area requirements are reduced (space aspect, FPGA).

(link/preprint)