Principles of speculative run-time parallelization

Devang Patel, Lawrence Rauchwerger

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

Abstract

Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. We advocate a novel framework for the identification of parallel loops. It speculatively executes a loop as a doall and applies a fully parallel data dependence test to check for any unsatisfied data dependencies; if the test fails, then the loop is re-executed serially. We will present the principles of the design and implementation of a compiler that employs both run-time and static techniques to parallelize dynamic applications. Run-time optimizations always represent a tradeoff between a speculated potential benefit and a certain (sure) overhead that must be paid. We will introduce techniques that take advantage of classic compiler methods to reduce the cost of run-time optimization thus tilting the outcome of speculation in favor of significant performance gains. Experimental results from the PERFECT, SPEC and NCSA Benchmark suites show that these techniques yield speedups not obtainable by any other known method.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 11th International Workshop, LCPC 1998, Proceedings
EditorsZhiyuan Li, David Sehr, Siddhartha Chatterjee, Jan F. Prins, Larry Carter, Jeanne Ferrante, Pen-Chung Yew
PublisherSpringer-Verlag
Pages323-336
Number of pages14
ISBN (Print)3540664262, 9783540664260
StatePublished - Jan 1 1999
Externally publishedYes
Event11th International Workshop on Languages and Compilers for Parallel Computing, LCPC 1998 - Chapel Hill, United States
Duration: Aug 7 1998Aug 9 1998

Publication series

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

Other

Other11th International Workshop on Languages and Compilers for Parallel Computing, LCPC 1998
CountryUnited States
CityChapel Hill
Period8/7/988/9/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Principles of speculative run-time parallelization'. Together they form a unique fingerprint.

  • Cite this

    Patel, D., & Rauchwerger, L. (1999). Principles of speculative run-time parallelization. In Z. Li, D. Sehr, S. Chatterjee, J. F. Prins, L. Carter, J. Ferrante, & P-C. Yew (Eds.), Languages and Compilers for Parallel Computing - 11th International Workshop, LCPC 1998, Proceedings (pp. 323-336). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1656). Springer-Verlag.