Unconventional parallelization of nondeterministic applications

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

2 Citations (Scopus)

Abstract

The demand for thread-level-parallelism (TLP) on commodity processors is endless as it is essential for gaining performance and saving energy. However, TLP in today's programs is limited by dependences that must be satisfied at run time. We have found that for nondeterministic programs, some of these actual dependences can be satisfied with alternative data that can be generated in parallel, thus boosting the program's TLP. Satisfying these dependences with alternative data nonetheless produces final outputs that match those of the original nondeterministic program. To demonstrate the practicality of our technique, we describe the design, implementation, and evaluation of our compilers, autotuner, profiler, and runtime, which are enabled by our proposed C++ programming language extensions. The resulting system boosts the performance of six well-known nondeterministic and multi-threaded benchmarks by 158.2% (geometric mean) on a 28-core Intel-based platform.

Original languageEnglish (US)
Title of host publicationASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems
PublisherAssociation for Computing Machinery
Pages432-447
Number of pages16
ISBN (Electronic)9781450349116
DOIs
StatePublished - Mar 19 2018
Event23rd International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2018 - Williamsburg, United States
Duration: Mar 24 2018Mar 28 2018

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

Other

Other23rd International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2018
CountryUnited States
CityWilliamsburg
Period3/24/183/28/18

Fingerprint

Computer programming languages
Energy conservation

Keywords

  • Dependences
  • Parallelization
  • Speculation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this

Deiana, E. A., St Amour, V., Dinda, P. A., Hardavellas, N., & Campanoni, S. (2018). Unconventional parallelization of nondeterministic applications. In ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 432-447). (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS). Association for Computing Machinery. https://doi.org/10.1145/3173162.3173181
Deiana, Enrico A. ; St Amour, Vincent ; Dinda, Peter A ; Hardavellas, Nikos ; Campanoni, Simone. / Unconventional parallelization of nondeterministic applications. ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems. Association for Computing Machinery, 2018. pp. 432-447 (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS).
@inproceedings{25f688ea7cde43f2a84c5edfd751fc6b,
title = "Unconventional parallelization of nondeterministic applications",
abstract = "The demand for thread-level-parallelism (TLP) on commodity processors is endless as it is essential for gaining performance and saving energy. However, TLP in today's programs is limited by dependences that must be satisfied at run time. We have found that for nondeterministic programs, some of these actual dependences can be satisfied with alternative data that can be generated in parallel, thus boosting the program's TLP. Satisfying these dependences with alternative data nonetheless produces final outputs that match those of the original nondeterministic program. To demonstrate the practicality of our technique, we describe the design, implementation, and evaluation of our compilers, autotuner, profiler, and runtime, which are enabled by our proposed C++ programming language extensions. The resulting system boosts the performance of six well-known nondeterministic and multi-threaded benchmarks by 158.2{\%} (geometric mean) on a 28-core Intel-based platform.",
keywords = "Dependences, Parallelization, Speculation",
author = "Deiana, {Enrico A.} and {St Amour}, Vincent and Dinda, {Peter A} and Nikos Hardavellas and Simone Campanoni",
year = "2018",
month = "3",
day = "19",
doi = "10.1145/3173162.3173181",
language = "English (US)",
series = "International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS",
publisher = "Association for Computing Machinery",
pages = "432--447",
booktitle = "ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems",

}

Deiana, EA, St Amour, V, Dinda, PA, Hardavellas, N & Campanoni, S 2018, Unconventional parallelization of nondeterministic applications. in ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems. International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS, Association for Computing Machinery, pp. 432-447, 23rd International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2018, Williamsburg, United States, 3/24/18. https://doi.org/10.1145/3173162.3173181

Unconventional parallelization of nondeterministic applications. / Deiana, Enrico A.; St Amour, Vincent; Dinda, Peter A; Hardavellas, Nikos; Campanoni, Simone.

ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems. Association for Computing Machinery, 2018. p. 432-447 (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS).

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

TY - GEN

T1 - Unconventional parallelization of nondeterministic applications

AU - Deiana, Enrico A.

AU - St Amour, Vincent

AU - Dinda, Peter A

AU - Hardavellas, Nikos

AU - Campanoni, Simone

PY - 2018/3/19

Y1 - 2018/3/19

N2 - The demand for thread-level-parallelism (TLP) on commodity processors is endless as it is essential for gaining performance and saving energy. However, TLP in today's programs is limited by dependences that must be satisfied at run time. We have found that for nondeterministic programs, some of these actual dependences can be satisfied with alternative data that can be generated in parallel, thus boosting the program's TLP. Satisfying these dependences with alternative data nonetheless produces final outputs that match those of the original nondeterministic program. To demonstrate the practicality of our technique, we describe the design, implementation, and evaluation of our compilers, autotuner, profiler, and runtime, which are enabled by our proposed C++ programming language extensions. The resulting system boosts the performance of six well-known nondeterministic and multi-threaded benchmarks by 158.2% (geometric mean) on a 28-core Intel-based platform.

AB - The demand for thread-level-parallelism (TLP) on commodity processors is endless as it is essential for gaining performance and saving energy. However, TLP in today's programs is limited by dependences that must be satisfied at run time. We have found that for nondeterministic programs, some of these actual dependences can be satisfied with alternative data that can be generated in parallel, thus boosting the program's TLP. Satisfying these dependences with alternative data nonetheless produces final outputs that match those of the original nondeterministic program. To demonstrate the practicality of our technique, we describe the design, implementation, and evaluation of our compilers, autotuner, profiler, and runtime, which are enabled by our proposed C++ programming language extensions. The resulting system boosts the performance of six well-known nondeterministic and multi-threaded benchmarks by 158.2% (geometric mean) on a 28-core Intel-based platform.

KW - Dependences

KW - Parallelization

KW - Speculation

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

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

U2 - 10.1145/3173162.3173181

DO - 10.1145/3173162.3173181

M3 - Conference contribution

AN - SCOPUS:85045390947

T3 - International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

SP - 432

EP - 447

BT - ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems

PB - Association for Computing Machinery

ER -

Deiana EA, St Amour V, Dinda PA, Hardavellas N, Campanoni S. Unconventional parallelization of nondeterministic applications. In ASPLOS 2018 - 23rd International Conference on Architectural Support for Programming Languages and Operating Systems. Association for Computing Machinery. 2018. p. 432-447. (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS). https://doi.org/10.1145/3173162.3173181