Iteration disambiguation for parallelism identification in time-sliced applications

Shane Ryoo, Christopher I. Rodrigues, Wen Mei W. Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Media and scientific simulation applications have a large amount of parallelism that can be exploited in contemporary multi-core microprocessors. However, traditional pointer and array analysis techniques often fall short in automatically identifying this parallelism. This is due to the allocation and referencing patterns of time-slicing algorithms, where information flows from one time slice to the next. In these, an object is allocated within a loop and written to, with source data obtained from objects created in previous iterations of the loop. The objects are typically allocated at the same static call site through the same call chain in the call graph, making them indistinguishable by traditional heap-sensitive analysis techniques that use call chains to distinguish heap objects. As a result, the compiler cannot separate the source and destination objects within each time slice of the algorithm. In this work we discuss an analysis that quickly identifies these objects through a partially flow-sensitive technique called iteration disambiguation. This is done through a relatively simple aging mechanism. We show that this analysis can distinguish objects allocated in different time slices across a wide range of benchmark applications within tens of seconds even for complete media applications. We will also discuss the obstacles to automatically identifying the remaining parallelism in studied applications and propose methods to address them.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers
Pages110-124
Number of pages15
DOIs
StatePublished - Oct 27 2008
Event20th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2007 - Urbana, IL, United States
Duration: Oct 11 2007Oct 13 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5234 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2007
CountryUnited States
CityUrbana, IL
Period10/11/0710/13/07

Fingerprint

Parallelism
Iteration
Slice
Heap
Microprocessor chips
Aging of materials
Slicing
Microprocessor
Information Flow
Object
Compiler
Benchmark
Graph in graph theory
Range of data
Simulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Ryoo, S., Rodrigues, C. I., & Hwu, W. M. W. (2008). Iteration disambiguation for parallelism identification in time-sliced applications. In Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers (pp. 110-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5234 LNCS). https://doi.org/10.1007/978-3-540-85261-2_8

Iteration disambiguation for parallelism identification in time-sliced applications. / Ryoo, Shane; Rodrigues, Christopher I.; Hwu, Wen Mei W.

Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers. 2008. p. 110-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5234 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ryoo, S, Rodrigues, CI & Hwu, WMW 2008, Iteration disambiguation for parallelism identification in time-sliced applications. in Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5234 LNCS, pp. 110-124, 20th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2007, Urbana, IL, United States, 10/11/07. https://doi.org/10.1007/978-3-540-85261-2_8
Ryoo S, Rodrigues CI, Hwu WMW. Iteration disambiguation for parallelism identification in time-sliced applications. In Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers. 2008. p. 110-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-85261-2_8
Ryoo, Shane ; Rodrigues, Christopher I. ; Hwu, Wen Mei W. / Iteration disambiguation for parallelism identification in time-sliced applications. Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers. 2008. pp. 110-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{bbdbea9d69524b3eb436e4115cc405d6,
title = "Iteration disambiguation for parallelism identification in time-sliced applications",
abstract = "Media and scientific simulation applications have a large amount of parallelism that can be exploited in contemporary multi-core microprocessors. However, traditional pointer and array analysis techniques often fall short in automatically identifying this parallelism. This is due to the allocation and referencing patterns of time-slicing algorithms, where information flows from one time slice to the next. In these, an object is allocated within a loop and written to, with source data obtained from objects created in previous iterations of the loop. The objects are typically allocated at the same static call site through the same call chain in the call graph, making them indistinguishable by traditional heap-sensitive analysis techniques that use call chains to distinguish heap objects. As a result, the compiler cannot separate the source and destination objects within each time slice of the algorithm. In this work we discuss an analysis that quickly identifies these objects through a partially flow-sensitive technique called iteration disambiguation. This is done through a relatively simple aging mechanism. We show that this analysis can distinguish objects allocated in different time slices across a wide range of benchmark applications within tens of seconds even for complete media applications. We will also discuss the obstacles to automatically identifying the remaining parallelism in studied applications and propose methods to address them.",
author = "Shane Ryoo and Rodrigues, {Christopher I.} and Hwu, {Wen Mei W.}",
year = "2008",
month = "10",
day = "27",
doi = "10.1007/978-3-540-85261-2_8",
language = "English (US)",
isbn = "3540852603",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "110--124",
booktitle = "Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers",

}

TY - GEN

T1 - Iteration disambiguation for parallelism identification in time-sliced applications

AU - Ryoo, Shane

AU - Rodrigues, Christopher I.

AU - Hwu, Wen Mei W.

PY - 2008/10/27

Y1 - 2008/10/27

N2 - Media and scientific simulation applications have a large amount of parallelism that can be exploited in contemporary multi-core microprocessors. However, traditional pointer and array analysis techniques often fall short in automatically identifying this parallelism. This is due to the allocation and referencing patterns of time-slicing algorithms, where information flows from one time slice to the next. In these, an object is allocated within a loop and written to, with source data obtained from objects created in previous iterations of the loop. The objects are typically allocated at the same static call site through the same call chain in the call graph, making them indistinguishable by traditional heap-sensitive analysis techniques that use call chains to distinguish heap objects. As a result, the compiler cannot separate the source and destination objects within each time slice of the algorithm. In this work we discuss an analysis that quickly identifies these objects through a partially flow-sensitive technique called iteration disambiguation. This is done through a relatively simple aging mechanism. We show that this analysis can distinguish objects allocated in different time slices across a wide range of benchmark applications within tens of seconds even for complete media applications. We will also discuss the obstacles to automatically identifying the remaining parallelism in studied applications and propose methods to address them.

AB - Media and scientific simulation applications have a large amount of parallelism that can be exploited in contemporary multi-core microprocessors. However, traditional pointer and array analysis techniques often fall short in automatically identifying this parallelism. This is due to the allocation and referencing patterns of time-slicing algorithms, where information flows from one time slice to the next. In these, an object is allocated within a loop and written to, with source data obtained from objects created in previous iterations of the loop. The objects are typically allocated at the same static call site through the same call chain in the call graph, making them indistinguishable by traditional heap-sensitive analysis techniques that use call chains to distinguish heap objects. As a result, the compiler cannot separate the source and destination objects within each time slice of the algorithm. In this work we discuss an analysis that quickly identifies these objects through a partially flow-sensitive technique called iteration disambiguation. This is done through a relatively simple aging mechanism. We show that this analysis can distinguish objects allocated in different time slices across a wide range of benchmark applications within tens of seconds even for complete media applications. We will also discuss the obstacles to automatically identifying the remaining parallelism in studied applications and propose methods to address them.

UR - http://www.scopus.com/inward/record.url?scp=54249158455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=54249158455&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-85261-2_8

DO - 10.1007/978-3-540-85261-2_8

M3 - Conference contribution

AN - SCOPUS:54249158455

SN - 3540852603

SN - 9783540852605

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 110

EP - 124

BT - Languages and Compilers for Parallel Computing - 20th International Workshop, LCPC 2007, Revised Selected Papers

ER -