A Compile/Run-time Environment for the Automatic Transformation of Linked List Data Structures.
Saved in:
| Title: | A Compile/Run-time Environment for the Automatic Transformation of Linked List Data Structures. |
|---|---|
| Authors: | Spek, H.1 hvdspek@liacs.nl, Groot, S.1, Bakker, E.1, Wijshoff, H.1 |
| Source: | International Journal of Parallel Programming. Dec2008, Vol. 36 Issue 6, p592-623. 32p. 6 Diagrams, 4 Charts, 6 Graphs. |
| Subjects: | Compilers (Computer programs), Optimizing compilers, Data structures, Electronic data processing, Computer software, Programming software, Systems software, Data |
| Abstract: | Irregular access patterns are a major problem for today’s optimizing compilers. In this paper, a novel approach will be presented that enables transformations that were designed for regular loop structures to be applied to linked list data structures. This is achieved by linearizing access to a linked list, after which further data restructuring can be performed. Two subsequent optimization paths will be considered: annihilation and sublimation, which are driven by the occurring regular and irregular access patterns in the applications. These intermediate codes are amenable to traditional compiler optimizations targeting regular loops. In the case of sublimation, a run-time step is involved which takes the access pattern into account and thus generates a data instance specific optimized code. Both approaches are applied to a sparse matrix multiplication algorithm and an iterative solver: preconditioned conjugate gradient. The resulting transformed code is evaluated using the major compilers for the x86 platform, GCC and the Intel C compiler. [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: 34748718 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A Compile/Run-time Environment for the Automatic Transformation of Linked List Data Structures. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Spek%2C+H%2E%22">Spek, H.</searchLink><relatesTo>1</relatesTo><i> hvdspek@liacs.nl</i><br /><searchLink fieldCode="AR" term="%22Groot%2C+S%2E%22">Groot, S.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Bakker%2C+E%2E%22">Bakker, E.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Wijshoff%2C+H%2E%22">Wijshoff, H.</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Parallel+Programming%22">International Journal of Parallel Programming</searchLink>. Dec2008, Vol. 36 Issue 6, p592-623. 32p. 6 Diagrams, 4 Charts, 6 Graphs. – 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="%22Optimizing+compilers%22">Optimizing compilers</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+data+processing%22">Electronic data processing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Programming+software%22">Programming software</searchLink><br /><searchLink fieldCode="DE" term="%22Systems+software%22">Systems software</searchLink><br /><searchLink fieldCode="DE" term="%22Data%22">Data</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Irregular access patterns are a major problem for today’s optimizing compilers. In this paper, a novel approach will be presented that enables transformations that were designed for regular loop structures to be applied to linked list data structures. This is achieved by linearizing access to a linked list, after which further data restructuring can be performed. Two subsequent optimization paths will be considered: annihilation and sublimation, which are driven by the occurring regular and irregular access patterns in the applications. These intermediate codes are amenable to traditional compiler optimizations targeting regular loops. In the case of sublimation, a run-time step is involved which takes the access pattern into account and thus generates a data instance specific optimized code. Both approaches are applied to a sparse matrix multiplication algorithm and an iterative solver: preconditioned conjugate gradient. The resulting transformed code is evaluated using the major compilers for the x86 platform, GCC and the Intel C compiler. [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=34748718 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10766-008-0085-2 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 32 StartPage: 592 Subjects: – SubjectFull: Compilers (Computer programs) Type: general – SubjectFull: Optimizing compilers Type: general – SubjectFull: Data structures Type: general – SubjectFull: Electronic data processing Type: general – SubjectFull: Computer software Type: general – SubjectFull: Programming software Type: general – SubjectFull: Systems software Type: general – SubjectFull: Data Type: general Titles: – TitleFull: A Compile/Run-time Environment for the Automatic Transformation of Linked List Data Structures. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Spek, H. – PersonEntity: Name: NameFull: Groot, S. – PersonEntity: Name: NameFull: Bakker, E. – PersonEntity: Name: NameFull: Wijshoff, H. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2008 Type: published Y: 2008 Identifiers: – Type: issn-print Value: 08857458 Numbering: – Type: volume Value: 36 – Type: issue Value: 6 Titles: – TitleFull: International Journal of Parallel Programming Type: main |
| ResultId | 1 |
