Navigation and service

IAS Seminar: Parallel preconditioners for multi-core CPU and GPU platforms

21 Jun 2011 11:15
Dimitar Lukarski, Karlsruhe Institute of Technology (KIT)
In this talk we consider parallel preconditioners in block form based on additive matrix splittings like e.g. Gauß-Seidel and SOR, and multiplicative decompositions like incomplete LU (ILU). In both scenarios, typically a large amount of forward and backward sweeps in triangular solvers needs to be performed. In order to harness parallelism within each block of the decomposition we use multi-coloring matrix reordering schemes. For splitting-based methods (Gauß-Seidel, SOR) and ILU(0) without fill-ins the original matrix pattern is preserved and therefore the matrix can be reorganized such that diagonal blocks are diagonal itself. Furthermore, we allow fill-ins in the ILU(p) method for achieving higher level of coupling with increased efficiency. Here, we consider two algorithms for parallelism. The level-scheduling method is used as a postprocessing method following the factorization. However, it produces very small blocks for many problem classes, i.e. the degree of parallelism is low. As a second approach, we propose a new method for anticipating the fill-in pattern of ILU(p) schemes which we call the power(q)-pattern method. This method computes the multi-coloring permutation pi for the matrix |A|p+1 whose occupancy pattern is a superset of our modified ILU(p) applied to pi(A). As a result, this decomposition has no fill-ins into its diagonal blocks. This leads to an inherently parallel execution of triangular ILU(p) sweeps. In addition, we describe the integration of the preconditioners in the HiFlow3 open-source finite element package that provides a portable software solution across diverse hardware platforms. On this basis, we conduct performance analysis across a variety of test problems on multi-core CPUs and GPU that proves efficiency, scalability and flexibility of our approach.
Tuesday, 21 June 2011, 11:15
Jülich Supercomputing Centre, Besprechungsraum 1, building 16.3, room 107
Announcement as PDF
 Parallel preconditioners for multi-core CPU and GPU platforms (PDF, 80 kB)

Anyone interested is cordially invited to participate.