skip to main content
10.1145/1996130.1996172acmconferencesArticle/Chapter ViewAbstractPublication PageshpdcConference Proceedingsconference-collections
poster

Exclusive squashing for thread-level speculation

Published: 08 June 2011 Publication History

Abstract

Speculative parallelization is a runtime technique that optimistically executes sequential code in parallel, checking that no dependence violations appear. In this paper, we address the problem of minimizing the number of threads that should be restarted when a data dependence violation is found. We present a new mechanism that keeps track of inter-thread dependencies in order to selectively stop and restart offending threads, and all threads that have consumed data from them. Results show a reduction of 38.5% to 81.8% in the number of restarted threads for real application loops and up to a 10% speedup, depending on the amount of local computation.

References

[1]
Cintra, M., and Llanos, D. R. Toward efficient and robust software speculative parallelization on multiprocessors. In PPoPP 2003 (San Diego, CA, USA, 2003), ACM, pp. 13--24.
[2]
Dang, F., Yu, H., and Rauchwerger, L. The R-LRPD test: speculative parallelization of partially parallel loops. In IPDPS '02 (2002).
[3]
Gupta, M., and Nim, R. Techniques for speculative run-time parallelization of loops. In ACM/IEEE Conf. on Supercomputing (San Jose, CA, 1998), pp. 1--12.
[4]
Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., and Chew, L. P. Optimistic parallelism requires abstractions. In ACM PLDI '07 (San Diego, CA, USA, 2007), ACM, pp. 211--222.
[5]
Rauchwerger, L., and Padua, D. The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization. In ACM PLDI '95 (La Jolla, CA, USA, 1995), pp. 218--232.

Cited By

View all
  • (2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
  • (2015)Simultaneous Inspection: Hiding the Overhead of Inspector-Executor Style Dynamic ParallelizationLanguages and Compilers for Parallel Computing10.1007/978-3-319-17473-0_7(101-115)Online publication date: 1-May-2015

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HPDC '11: Proceedings of the 20th international symposium on High performance distributed computing
June 2011
296 pages
ISBN:9781450305525
DOI:10.1145/1996130

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. loop-based parallelization
  2. speculative parallelization

Qualifiers

  • Poster

Conference

HPDC '11
Sponsor:

Acceptance Rates

Overall Acceptance Rate 166 of 966 submissions, 17%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
  • (2015)Simultaneous Inspection: Hiding the Overhead of Inspector-Executor Style Dynamic ParallelizationLanguages and Compilers for Parallel Computing10.1007/978-3-319-17473-0_7(101-115)Online publication date: 1-May-2015

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media