View in EDS PDF Full Text

TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.

Saved in:
Bibliographic Details
Title: TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.
Authors: ZEFREH, EBRAHIM ZAREI1, LOTFI, SHAHRIAR, KARIMPOUR, JABER, KHANLI, LEYLI MOHAMMAD2
Source: Scalable Computing: Practice & Experience. Dec2016, Vol. 17 Issue 4, p331-349. 19p. 8 Charts, 6 Graphs.
Subjects: Loop tiling (Computer science), Heterogeneous computing
Abstract: Nested loops are one of the most time-consuming parts and the largest sources of parallelism in many scientific applications. In this paper, we address the problem of 3-dimensional tiling and scheduling of three-level perfectly nested loops with dependencies on heterogeneous systems. To exploit the parallelism, we tile and schedule nested loops with dependencies by awareness of computational power of the processing nodes and execute them in pipeline mode. The tile size plays an important role to improve the parallel execution time of nested loops. We develop and evaluate a theoretical model to estimate the parallel execution time of tilled nested loops. Also, we propose a tiling genetic algorithm that used the proposed model to find the near- optimal tile size, minimizing the parallel execution time of dependence nested loops. We demonstrate the accuracy of theoretical model and effectiveness of the proposed tiling genetic algorithm by several experiments on heterogeneous systems. The 3D tiling reduces the parallel execution time by a factor of 1.2× to 2× over the 2D tiling, while parallelizing 3D heat equation as a benchmark. [ABSTRACT FROM AUTHOR]
Copyright of Scalable Computing: Practice & Experience is the property of Scalable Computing: Practice & Experience 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: 118867786
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22ZEFREH%2C+EBRAHIM+ZAREI%22">ZEFREH, EBRAHIM ZAREI</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22LOTFI%2C+SHAHRIAR%22">LOTFI, SHAHRIAR</searchLink><br /><searchLink fieldCode="AR" term="%22KARIMPOUR%2C+JABER%22">KARIMPOUR, JABER</searchLink><br /><searchLink fieldCode="AR" term="%22KHANLI%2C+LEYLI+MOHAMMAD%22">KHANLI, LEYLI MOHAMMAD</searchLink><relatesTo>2</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Scalable+Computing%3A+Practice+%26+Experience%22">Scalable Computing: Practice & Experience</searchLink>. Dec2016, Vol. 17 Issue 4, p331-349. 19p. 8 Charts, 6 Graphs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Loop+tiling+%28Computer+science%29%22">Loop tiling (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Heterogeneous+computing%22">Heterogeneous computing</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Nested loops are one of the most time-consuming parts and the largest sources of parallelism in many scientific applications. In this paper, we address the problem of 3-dimensional tiling and scheduling of three-level perfectly nested loops with dependencies on heterogeneous systems. To exploit the parallelism, we tile and schedule nested loops with dependencies by awareness of computational power of the processing nodes and execute them in pipeline mode. The tile size plays an important role to improve the parallel execution time of nested loops. We develop and evaluate a theoretical model to estimate the parallel execution time of tilled nested loops. Also, we propose a tiling genetic algorithm that used the proposed model to find the near- optimal tile size, minimizing the parallel execution time of dependence nested loops. We demonstrate the accuracy of theoretical model and effectiveness of the proposed tiling genetic algorithm by several experiments on heterogeneous systems. The 3D tiling reduces the parallel execution time by a factor of 1.2× to 2× over the 2D tiling, while parallelizing 3D heat equation as a benchmark. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Scalable Computing: Practice & Experience is the property of Scalable Computing: Practice & Experience 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=118867786
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.12694/scpe.v17i4.1205
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 19
        StartPage: 331
    Subjects:
      – SubjectFull: Loop tiling (Computer science)
        Type: general
      – SubjectFull: Heterogeneous computing
        Type: general
    Titles:
      – TitleFull: TILING AND SCHEDULING OF THREE-LEVEL PERFECTLY NESTED LOOPS WITH DEPENDENCIES ON HETEROGENEOUS SYSTEMS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: ZEFREH, EBRAHIM ZAREI
      – PersonEntity:
          Name:
            NameFull: LOTFI, SHAHRIAR
      – PersonEntity:
          Name:
            NameFull: KARIMPOUR, JABER
      – PersonEntity:
          Name:
            NameFull: KHANLI, LEYLI MOHAMMAD
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 12
              Text: Dec2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 18951767
          Numbering:
            – Type: volume
              Value: 17
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Scalable Computing: Practice & Experience
              Type: main
ResultId 1