View in EDS PDF Full Text

A Library for Pattern-based Sparse Matrix Vector Multiply.

Saved in:
Bibliographic Details
Title: A Library for Pattern-based Sparse Matrix Vector Multiply.
Authors: Belgin, Mehmet1 mehmetb@cs.vt.edu, Back, Godmar1 gback@cs.vt.edu, Ribbens, Calvin J.1 ribbens@cs.vt.edu
Source: International Journal of Parallel Programming. Feb2011, Vol. 39 Issue 1, p62-87. 26p. 7 Diagrams, 8 Charts, 5 Graphs.
Subjects: Sparse matrix software, Kernel functions, Bandwidths, Data transmission systems, Central processing units, Computer storage devices
Abstract: Pattern-based Representation (PBR) is a novel approach to improving the performance of Sparse Matrix-Vector Multiply (SMVM) numerical kernels. Motivated by our observation that many matrices can be divided into blocks that share a small number of distinct patterns, we generate custom multiplication kernels for frequently recurring block patterns. The resulting reduction in index overhead significantly reduces memory bandwidth requirements and improves performance. Unlike existing methods, PBR requires neither detection of dense blocks nor zero filling, making it particularly advantageous for matrices that lack dense nonzero concentrations. SMVM kernels for PBR can benefit from explicit prefetching and vectorization, and are amenable to parallelization. The analysis and format conversion to PBR is implemented as a library, making it suitable for applications that generate matrices dynamically at runtime. We present sequential and parallel performance results for PBR on two current multicore architectures, which show that PBR outperforms available alternatives for the matrices to which it is applicable, and that the analysis and conversion overhead is amortized in realistic application scenarios. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Parallel Programming is the property of Springer Nature 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 Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 57366652
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A Library for Pattern-based Sparse Matrix Vector Multiply.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Belgin%2C+Mehmet%22">Belgin, Mehmet</searchLink><relatesTo>1</relatesTo><i> mehmetb@cs.vt.edu</i><br /><searchLink fieldCode="AR" term="%22Back%2C+Godmar%22">Back, Godmar</searchLink><relatesTo>1</relatesTo><i> gback@cs.vt.edu</i><br /><searchLink fieldCode="AR" term="%22Ribbens%2C+Calvin+J%2E%22">Ribbens, Calvin J.</searchLink><relatesTo>1</relatesTo><i> ribbens@cs.vt.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Parallel+Programming%22">International Journal of Parallel Programming</searchLink>. Feb2011, Vol. 39 Issue 1, p62-87. 26p. 7 Diagrams, 8 Charts, 5 Graphs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Sparse+matrix+software%22">Sparse matrix software</searchLink><br /><searchLink fieldCode="DE" term="%22Kernel+functions%22">Kernel functions</searchLink><br /><searchLink fieldCode="DE" term="%22Bandwidths%22">Bandwidths</searchLink><br /><searchLink fieldCode="DE" term="%22Data+transmission+systems%22">Data transmission systems</searchLink><br /><searchLink fieldCode="DE" term="%22Central+processing+units%22">Central processing units</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+devices%22">Computer storage devices</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Pattern-based Representation (PBR) is a novel approach to improving the performance of Sparse Matrix-Vector Multiply (SMVM) numerical kernels. Motivated by our observation that many matrices can be divided into blocks that share a small number of distinct patterns, we generate custom multiplication kernels for frequently recurring block patterns. The resulting reduction in index overhead significantly reduces memory bandwidth requirements and improves performance. Unlike existing methods, PBR requires neither detection of dense blocks nor zero filling, making it particularly advantageous for matrices that lack dense nonzero concentrations. SMVM kernels for PBR can benefit from explicit prefetching and vectorization, and are amenable to parallelization. The analysis and format conversion to PBR is implemented as a library, making it suitable for applications that generate matrices dynamically at runtime. We present sequential and parallel performance results for PBR on two current multicore architectures, which show that PBR outperforms available alternatives for the matrices to which it is applicable, and that the analysis and conversion overhead is amortized in realistic application scenarios. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal of Parallel Programming is the property of Springer Nature 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=57366652
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10766-010-0145-2
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 26
        StartPage: 62
    Subjects:
      – SubjectFull: Sparse matrix software
        Type: general
      – SubjectFull: Kernel functions
        Type: general
      – SubjectFull: Bandwidths
        Type: general
      – SubjectFull: Data transmission systems
        Type: general
      – SubjectFull: Central processing units
        Type: general
      – SubjectFull: Computer storage devices
        Type: general
    Titles:
      – TitleFull: A Library for Pattern-based Sparse Matrix Vector Multiply.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Belgin, Mehmet
      – PersonEntity:
          Name:
            NameFull: Back, Godmar
      – PersonEntity:
          Name:
            NameFull: Ribbens, Calvin J.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: Feb2011
              Type: published
              Y: 2011
          Identifiers:
            – Type: issn-print
              Value: 08857458
          Numbering:
            – Type: volume
              Value: 39
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: International Journal of Parallel Programming
              Type: main
ResultId 1