A compiler approach to map algebra: automatic parallelization, locality optimization, and GPU acceleration of raster spatial analysis.
Saved in:
| Title: | A compiler approach to map algebra: automatic parallelization, locality optimization, and GPU acceleration of raster spatial analysis. |
|---|---|
| Authors: | Carabaño, Jesús1 jcaraban@abo.fi, Westerholm, Jan1 jawester@abo.fi, Sarjakoski, Tapani2 tapani.sarjakoski@nls.fi |
| Source: | GeoInformatica. Apr2018, Vol. 22 Issue 2, p211-235. 25p. |
| Subjects: | Compilers (Computer programs), Bit-mapped graphics, Graphics processing units, Computer architecture, Spatial analysis (Statistics), Automation, Mathematical optimization |
| Abstract: | Computer architectures have evolved into parallel and heterogeneous systems with multi-core CPUs, many-core GPUs, and vector instructions. Meanwhile, advances in data collection technologies have led to a rapid increase in the spatial and temporal resolution of geographic data. Efficiently dealing with large volumes of geographic data demands, now more than ever, an effective use of modern parallel computers. However, parallel programming is distinctly more challenging than writing sequential scripts. Moreover, parallelism is not the only issue; data locality is critical, too. This work addresses the issues of data escalation and parallel transition using a compiler approach to map algebra. More specifically, we design and implement a framework that uses compiler techniques to automatically speed up raster spatial analysis. In this way, users simply write sequential map algebra scripts in Python, which are translated into a graph where optimizations are applied. Then the scripts are parallelized, reordered for locality, and executed on OpenCL devices such as multi-core CPUs and GPUs. The novelty of our approach resides in the efficient organization of the execution, which we achieve via compilation. Unlike interpreters, our framework reorders the raster operations to maximize data reuse and minimize memory movements. The reordering occurs at two hierarchical levels and is controlled by a scheduler and a fusion technique. This strategy targets data locality, which, as we show, is key to the performance of raster spatial analysis. The experiments report speed-ups of one to two orders of magnitude compared to traditional interpreters. [ABSTRACT FROM AUTHOR] |
| Copyright of GeoInformatica 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 |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 129133086 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A compiler approach to map algebra: automatic parallelization, locality optimization, and GPU acceleration of raster spatial analysis. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Carabaño%2C+Jesús%22">Carabaño, Jesús</searchLink><relatesTo>1</relatesTo><i> jcaraban@abo.fi</i><br /><searchLink fieldCode="AR" term="%22Westerholm%2C+Jan%22">Westerholm, Jan</searchLink><relatesTo>1</relatesTo><i> jawester@abo.fi</i><br /><searchLink fieldCode="AR" term="%22Sarjakoski%2C+Tapani%22">Sarjakoski, Tapani</searchLink><relatesTo>2</relatesTo><i> tapani.sarjakoski@nls.fi</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22GeoInformatica%22">GeoInformatica</searchLink>. Apr2018, Vol. 22 Issue 2, p211-235. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Compilers+%28Computer+programs%29%22">Compilers (Computer programs)</searchLink><br /><searchLink fieldCode="DE" term="%22Bit-mapped+graphics%22">Bit-mapped graphics</searchLink><br /><searchLink fieldCode="DE" term="%22Graphics+processing+units%22">Graphics processing units</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+architecture%22">Computer architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Spatial+analysis+%28Statistics%29%22">Spatial analysis (Statistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Automation%22">Automation</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Computer architectures have evolved into parallel and heterogeneous systems with multi-core CPUs, many-core GPUs, and vector instructions. Meanwhile, advances in data collection technologies have led to a rapid increase in the spatial and temporal resolution of geographic data. Efficiently dealing with large volumes of geographic data demands, now more than ever, an effective use of modern parallel computers. However, parallel programming is distinctly more challenging than writing sequential scripts. Moreover, parallelism is not the only issue; data locality is critical, too. This work addresses the issues of data escalation and parallel transition using a compiler approach to map algebra. More specifically, we design and implement a framework that uses compiler techniques to automatically speed up raster spatial analysis. In this way, users simply write sequential map algebra scripts in Python, which are translated into a graph where optimizations are applied. Then the scripts are parallelized, reordered for locality, and executed on OpenCL devices such as multi-core CPUs and GPUs. The novelty of our approach resides in the efficient organization of the execution, which we achieve via compilation. Unlike interpreters, our framework reorders the raster operations to maximize data reuse and minimize memory movements. The reordering occurs at two hierarchical levels and is controlled by a scheduler and a fusion technique. This strategy targets data locality, which, as we show, is key to the performance of raster spatial analysis. The experiments report speed-ups of one to two orders of magnitude compared to traditional interpreters. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of GeoInformatica 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=129133086 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10707-017-0312-3 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 211 Subjects: – SubjectFull: Compilers (Computer programs) Type: general – SubjectFull: Bit-mapped graphics Type: general – SubjectFull: Graphics processing units Type: general – SubjectFull: Computer architecture Type: general – SubjectFull: Spatial analysis (Statistics) Type: general – SubjectFull: Automation Type: general – SubjectFull: Mathematical optimization Type: general Titles: – TitleFull: A compiler approach to map algebra: automatic parallelization, locality optimization, and GPU acceleration of raster spatial analysis. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Carabaño, Jesús – PersonEntity: Name: NameFull: Westerholm, Jan – PersonEntity: Name: NameFull: Sarjakoski, Tapani IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: Apr2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 13846175 Numbering: – Type: volume Value: 22 – Type: issue Value: 2 Titles: – TitleFull: GeoInformatica Type: main |
| ResultId | 1 |
