POSTER

The Liberation Day of Nondeterministic Programs

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

1 Citation (Scopus)

Abstract

The demand for thread-level parallelism (TLP) is endless, especially on commodity processors, as TLP is essential for gaining performance. However, the TLP of 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, therefore boosting the program's TLP. We show how these dependences (which we call 'state dependences' because they are related to the program's state) can be exploited using algorithm-specific knowledge. To demonstrate the practicality of our technique, we implemented a system called April25th that incorporates the concept of 'state dependences'. This system boosts the performance of five nondeterministic, multi-threaded PARSEC benchmarks by 100.5%.

Original languageEnglish (US)
Title of host publicationProceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages136-137
Number of pages2
Volume2017-September
ISBN (Electronic)9781467395243
DOIs
StatePublished - Oct 31 2017
Event26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017 - Portland, United States
Duration: Sep 9 2017Sep 13 2017

Other

Other26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017
CountryUnited States
CityPortland
Period9/9/179/13/17

Fingerprint

Thread
Parallelism
Boosting
Benchmark
Alternatives
Demonstrate

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Cite this

Deiana, E. A., St-Amour, V., Dinda, P., Hardavellas, N., & Campanoni, S. (2017). POSTER: The Liberation Day of Nondeterministic Programs. In Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017 (Vol. 2017-September, pp. 136-137). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/PACT.2017.26
Deiana, Enrico Armenio ; St-Amour, Vincent ; Dinda, Peter ; Hardavellas, Nikos ; Campanoni, Simone. / POSTER : The Liberation Day of Nondeterministic Programs. Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017. Vol. 2017-September Institute of Electrical and Electronics Engineers Inc., 2017. pp. 136-137
@inproceedings{8912c0a16bd2492cab82eb72081bd9cf,
title = "POSTER: The Liberation Day of Nondeterministic Programs",
abstract = "The demand for thread-level parallelism (TLP) is endless, especially on commodity processors, as TLP is essential for gaining performance. However, the TLP of 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, therefore boosting the program's TLP. We show how these dependences (which we call 'state dependences' because they are related to the program's state) can be exploited using algorithm-specific knowledge. To demonstrate the practicality of our technique, we implemented a system called April25th that incorporates the concept of 'state dependences'. This system boosts the performance of five nondeterministic, multi-threaded PARSEC benchmarks by 100.5{\%}.",
author = "Deiana, {Enrico Armenio} and Vincent St-Amour and Peter Dinda and Nikos Hardavellas and Simone Campanoni",
year = "2017",
month = "10",
day = "31",
doi = "10.1109/PACT.2017.26",
language = "English (US)",
volume = "2017-September",
pages = "136--137",
booktitle = "Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

Deiana, EA, St-Amour, V, Dinda, P, Hardavellas, N & Campanoni, S 2017, POSTER: The Liberation Day of Nondeterministic Programs. in Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017. vol. 2017-September, Institute of Electrical and Electronics Engineers Inc., pp. 136-137, 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017, Portland, United States, 9/9/17. https://doi.org/10.1109/PACT.2017.26

POSTER : The Liberation Day of Nondeterministic Programs. / Deiana, Enrico Armenio; St-Amour, Vincent; Dinda, Peter; Hardavellas, Nikos; Campanoni, Simone.

Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017. Vol. 2017-September Institute of Electrical and Electronics Engineers Inc., 2017. p. 136-137.

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

TY - GEN

T1 - POSTER

T2 - The Liberation Day of Nondeterministic Programs

AU - Deiana, Enrico Armenio

AU - St-Amour, Vincent

AU - Dinda, Peter

AU - Hardavellas, Nikos

AU - Campanoni, Simone

PY - 2017/10/31

Y1 - 2017/10/31

N2 - The demand for thread-level parallelism (TLP) is endless, especially on commodity processors, as TLP is essential for gaining performance. However, the TLP of 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, therefore boosting the program's TLP. We show how these dependences (which we call 'state dependences' because they are related to the program's state) can be exploited using algorithm-specific knowledge. To demonstrate the practicality of our technique, we implemented a system called April25th that incorporates the concept of 'state dependences'. This system boosts the performance of five nondeterministic, multi-threaded PARSEC benchmarks by 100.5%.

AB - The demand for thread-level parallelism (TLP) is endless, especially on commodity processors, as TLP is essential for gaining performance. However, the TLP of 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, therefore boosting the program's TLP. We show how these dependences (which we call 'state dependences' because they are related to the program's state) can be exploited using algorithm-specific knowledge. To demonstrate the practicality of our technique, we implemented a system called April25th that incorporates the concept of 'state dependences'. This system boosts the performance of five nondeterministic, multi-threaded PARSEC benchmarks by 100.5%.

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

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

U2 - 10.1109/PACT.2017.26

DO - 10.1109/PACT.2017.26

M3 - Conference contribution

VL - 2017-September

SP - 136

EP - 137

BT - Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Deiana EA, St-Amour V, Dinda P, Hardavellas N, Campanoni S. POSTER: The Liberation Day of Nondeterministic Programs. In Proceedings - 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017. Vol. 2017-September. Institute of Electrical and Electronics Engineers Inc. 2017. p. 136-137 https://doi.org/10.1109/PACT.2017.26