Reordering strategy for blocking optimization in sparse linear solvers - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2016

Reordering strategy for blocking optimization in sparse linear solvers

Stratégie de renumérotation pour optimiser la granularité des calculs dans la résolution des systèmes linéaires creux

(1) , (1, 2) , (1) , (1)
1
2

Abstract

Solving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For this reason, optimizing their performance on modern architectures is critical. The preprocessing steps of sparse direct solvers, ordering and block-symbolic factorization, are two major steps that lead to a reduced amount of computation and memory and to a better task granularity to reach a good level of performance when using BLAS kernels. With the advent of GPUs, the granularity of the block computation became more important than ever. In this paper, we present a reordering strategy that increases this block granularity. This strategy relies on the block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. We integrate this algorithm in the PaStiX solver and show an important reduction of the number of off-diagonal blocks on a large spectrum of matrices. This improvement leads to an increase in efficiency of up to 20% on GPUs.
De nombreuses applications scientifiques recquièrent La résolution de large systèmes linéaires creux qui est généralement l'étape la plus comnsommatrice de ressources, que ce soit en temps de calculs ou mémoire. Il est donc primordial d'optimiser les bibliothèques de résolution de ces problèmes sur les architectures modernes. Nous présentons dans ce documents une technique de renumérotation des inconnues qui permet d'élargir la granularité des calculs afin de mieux exploiter les accélérateurs, comme les GPUs, dans ces bibliothèques. Cet algorithme s'appuie sur les renumérotations calculées par des outils comme Metis ou Scotch sans changer le nombre d'opérations de la factorisation numérique. Nous présentons les résultats de l'intégration de cette stratégie dans la bibliothèque architectures hétérogènes.
Fichier principal
Vignette du fichier
RR-8860-v1.pdf (1.02 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01276746 , version 1 (19-02-2016)
hal-01276746 , version 2 (13-10-2016)

Identifiers

  • HAL Id : hal-01276746 , version 2

Cite

Grégoire Pichon, Mathieu Faverge, Pierre Ramet, Jean Roman. Reordering strategy for blocking optimization in sparse linear solvers. [Research Report] RR-8860, Inria Bordeaux Sud-Ouest; LaBRI - Laboratoire Bordelais de Recherche en Informatique; Bordeaux INP; Université de Bordeaux. 2016, pp.26. ⟨hal-01276746v2⟩
402 View
567 Download

Share

Gmail Facebook Twitter LinkedIn More