View in EDS

Exploiting Locality for Irregular Scientific Codes.

Saved in:
Bibliographic Details
Title: Exploiting Locality for Irregular Scientific Codes.
Authors: Hwansoo Han1 hshan@cs.kaist.ac.kr, Chau-Wen Tseng2 tseng@cs.umd.edu
Source: IEEE Transactions on Parallel & Distributed Systems. Jul2006, Vol. 17 Issue 7, p606-618. 13p. 2 Black and White Photographs, 5 Diagrams, 2 Charts, 4 Graphs.
Subjects: Cache memory, Optimizing compilers, Computer storage devices, Compilers (Computer programs), Computer software, Computer networks
Abstract: Irregular scientific codes experience poor cache performance due to their irregular memory access patterns. In this paper, we present two new locality improving techniques for irregular scientific codes. Our techniques exploit geometric structures hidden in data access patterns and computation structures. Our new data reordering (GPART) finds the graph structure within data accesses and applies hierarchical clustering. Quality partitions are constructed quickly by clustering multiple neighbor nodes with priority on nodes with high degree and repeating a few passes. Overhead is kept low by clustering multiple nodes in each pass and considering only edges between partitions. Our new computation reordering (Z-SORT) treats the values of index arrays as coordinates and reorders corresponding computations in Z-curve order. Applied to dense inputs, Z-SORT achieves performance close to data reordering combined with other computation reordering but without the overhead involved in data reordering. Experiments on irregular scientific codes for a variety of meshes show locality optimization techniques are effective for both sequential and parallelized codes, improving performance by 60–87 percent. GPART achieved within 1–2 percent of the performance of more sophisticated partitioning algorithms, but with one third of the overhead. Z-SORT also yields the performance improvement of 64 percent for dense inputs, which is comparable with data reordering combined with computation reordering. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE 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: 21385827
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Exploiting Locality for Irregular Scientific Codes.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Hwansoo+Han%22">Hwansoo Han</searchLink><relatesTo>1</relatesTo><i> hshan@cs.kaist.ac.kr</i><br /><searchLink fieldCode="AR" term="%22Chau-Wen+Tseng%22">Chau-Wen Tseng</searchLink><relatesTo>2</relatesTo><i> tseng@cs.umd.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Parallel+%26+Distributed+Systems%22">IEEE Transactions on Parallel & Distributed Systems</searchLink>. Jul2006, Vol. 17 Issue 7, p606-618. 13p. 2 Black and White Photographs, 5 Diagrams, 2 Charts, 4 Graphs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Cache+memory%22">Cache memory</searchLink><br /><searchLink fieldCode="DE" term="%22Optimizing+compilers%22">Optimizing compilers</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+devices%22">Computer storage devices</searchLink><br /><searchLink fieldCode="DE" term="%22Compilers+%28Computer+programs%29%22">Compilers (Computer programs)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Irregular scientific codes experience poor cache performance due to their irregular memory access patterns. In this paper, we present two new locality improving techniques for irregular scientific codes. Our techniques exploit geometric structures hidden in data access patterns and computation structures. Our new data reordering (GPART) finds the graph structure within data accesses and applies hierarchical clustering. Quality partitions are constructed quickly by clustering multiple neighbor nodes with priority on nodes with high degree and repeating a few passes. Overhead is kept low by clustering multiple nodes in each pass and considering only edges between partitions. Our new computation reordering (Z-SORT) treats the values of index arrays as coordinates and reorders corresponding computations in Z-curve order. Applied to dense inputs, Z-SORT achieves performance close to data reordering combined with other computation reordering but without the overhead involved in data reordering. Experiments on irregular scientific codes for a variety of meshes show locality optimization techniques are effective for both sequential and parallelized codes, improving performance by 60–87 percent. GPART achieved within 1–2 percent of the performance of more sophisticated partitioning algorithms, but with one third of the overhead. Z-SORT also yields the performance improvement of 64 percent for dense inputs, which is comparable with data reordering combined with computation reordering. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE 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=21385827
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TPDS.2006.88
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 13
        StartPage: 606
    Subjects:
      – SubjectFull: Cache memory
        Type: general
      – SubjectFull: Optimizing compilers
        Type: general
      – SubjectFull: Computer storage devices
        Type: general
      – SubjectFull: Compilers (Computer programs)
        Type: general
      – SubjectFull: Computer software
        Type: general
      – SubjectFull: Computer networks
        Type: general
    Titles:
      – TitleFull: Exploiting Locality for Irregular Scientific Codes.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Hwansoo Han
      – PersonEntity:
          Name:
            NameFull: Chau-Wen Tseng
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Text: Jul2006
              Type: published
              Y: 2006
          Identifiers:
            – Type: issn-print
              Value: 10459219
          Numbering:
            – Type: volume
              Value: 17
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: IEEE Transactions on Parallel & Distributed Systems
              Type: main
ResultId 1