View in EDS

REORDERING STRATEGY FOR BLOCKING OPTIMIZATION IN SPARSE LINEAR SOLVERS.

Saved in:
Bibliographic Details
Title: REORDERING STRATEGY FOR BLOCKING OPTIMIZATION IN SPARSE LINEAR SOLVERS.
Authors: PICHON, GREGOIRE1 gregoire.pichon@inria.fr, FAVERGE, MATHIEU2 mathieu.faverge@inria.fr, RAMET, PIERRE1 pierre.ramet@inria.fr, ROMAN, JEAN1 jean.roman@inria.fr
Source: SIAM Journal on Matrix Analysis & Applications. 2017, Vol. 38 Issue 1, p226-248. 23p.
Subjects: Linear systems, Iterative methods (Mathematics), Mathematical optimization, Factorization, Algorithms
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 has become more important than ever. In this paper, we present a reordering strategy that increases this block granularity. This strategy relies on 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. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 122891417
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: REORDERING STRATEGY FOR BLOCKING OPTIMIZATION IN SPARSE LINEAR SOLVERS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22PICHON%2C+GREGOIRE%22">PICHON, GREGOIRE</searchLink><relatesTo>1</relatesTo><i> gregoire.pichon@inria.fr</i><br /><searchLink fieldCode="AR" term="%22FAVERGE%2C+MATHIEU%22">FAVERGE, MATHIEU</searchLink><relatesTo>2</relatesTo><i> mathieu.faverge@inria.fr</i><br /><searchLink fieldCode="AR" term="%22RAMET%2C+PIERRE%22">RAMET, PIERRE</searchLink><relatesTo>1</relatesTo><i> pierre.ramet@inria.fr</i><br /><searchLink fieldCode="AR" term="%22ROMAN%2C+JEAN%22">ROMAN, JEAN</searchLink><relatesTo>1</relatesTo><i> jean.roman@inria.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Matrix+Analysis+%26+Applications%22">SIAM Journal on Matrix Analysis & Applications</searchLink>. 2017, Vol. 38 Issue 1, p226-248. 23p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink><br /><searchLink fieldCode="DE" term="%22Iterative+methods+%28Mathematics%29%22">Iterative methods (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Factorization%22">Factorization</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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 has become more important than ever. In this paper, we present a reordering strategy that increases this block granularity. This strategy relies on 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=122891417
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/16M1062454
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 23
        StartPage: 226
    Subjects:
      – SubjectFull: Linear systems
        Type: general
      – SubjectFull: Iterative methods (Mathematics)
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Factorization
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: REORDERING STRATEGY FOR BLOCKING OPTIMIZATION IN SPARSE LINEAR SOLVERS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: PICHON, GREGOIRE
      – PersonEntity:
          Name:
            NameFull: FAVERGE, MATHIEU
      – PersonEntity:
          Name:
            NameFull: RAMET, PIERRE
      – PersonEntity:
          Name:
            NameFull: ROMAN, JEAN
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: 2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 08954798
          Numbering:
            – Type: volume
              Value: 38
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: SIAM Journal on Matrix Analysis & Applications
              Type: main
ResultId 1