Speculative parallelization of partially parallel loops

Francis H. Dang, 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 have previously proposed a framework for their identification. We speculatively executed a loop as a doall, and applied a fully parallel data dependence test to determine if it had any cross–processor dependences; if the test failed, then the loop was re–executed serially. While this method exploits doall parallelism well, it can cause slowdowns for loops with even one cross-processor flow dependence because we have to re-execute sequentially. Moreover, the existing, partial parallelism of loops is not exploited. In this paper we propose a generalization of our speculative doall parallelization technique, named Recursive LRPD test, that can extract and exploit the maximum available parallelism of any loop and that limits potential slowdowns to the overhead of the run-time dependence test itself, i.e., removes the time lost due to incorrect parallel execution. The asymptotic time-complexity is, for fully serial loops, equal to the sequential execution time. We present the base algorithm and an analysis of the different heuristics for its practical application. Some preliminary experimental results on loops from Track will show the performance of this new technique.

Original languageEnglish (US)
Title of host publicationLanguages, Compilers, and Run-Time Systems for Scalable Computers - 5th International Workshop, LCR 2000, Selected Papers
EditorsSandhya Dwarkadas
PublisherSpringer-Verlag Berlin Heidelberg
Pages285-299
Number of pages15
ISBN (Print)3540411852, 9783540411857
DOIs
StatePublished - Jan 1 2000
Event5th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 2000 - Rochester, United States
Duration: May 25 2000May 27 2000

Publication series

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

Conference

Conference5th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 2000
CountryUnited States
CityRochester
Period5/25/005/27/00

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Speculative parallelization of partially parallel loops'. Together they form a unique fingerprint.

  • Cite this

    Dang, F. H., & Rauchwerger, L. (2000). Speculative parallelization of partially parallel loops. In S. Dwarkadas (Ed.), Languages, Compilers, and Run-Time Systems for Scalable Computers - 5th International Workshop, LCR 2000, Selected Papers (pp. 285-299). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1915). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/3-540-40889-4_22