Automatic speculative DOALL for clusters

Hanjun Kim, Nick P. Johnson, Jae W. Lee, Scott A. Mahlke, David I. August

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

32 Scopus citations

Abstract

Automatic parallelization for clusters is a promising alternative to time-consuming, error-prone manual parallelization. However, automatic parallelization is frequently limited by the imprecision of static analysis. Moreover, due to the inherent fragility of static analysis, small changes to the source code can significantly undermine performance. By replacing static analysis with speculation and profiling, automatic parallelization becomes more robust and applicable. A naïve automatic speculative parallelization does not scale for distributed memory clusters, due to the high bandwidth required to validate speculation. This work is the frit automatic speculative DOALL (Spec-DOALL) parallelization system for clusters. We have implemented a prototype automatic parallelization system, called Cluster Spec-DOALL, which consists of a Spec-DOALL parallelizing compiler and a speculative runtime for clusters. Since the compiler optimizes communication patterns, and the runtime is optimized for the cases in which speculation succeeds, Cluster Spec-DOALL minimizes the communication and validation overheads of the speculative runtime. Across 8 benchmarks, Cluster Spec-DOALL achieves a geomean speedup of 43.8× on a 120- core cluster, whereas DOALL without speculation achieves only 4.5× speedup. This demonstrates that speculation makes scalable fully-automatic parallelization for clusters possible.

Original languageEnglish (US)
Title of host publicationProceedings - International Symposium on Code Generation and Optimization, CGO 2012
Pages94-103
Number of pages10
DOIs
StatePublished - 2012
Event10th International Symposium on Code Generation and Optimization, CGO 2012 - San Jose, CA, United States
Duration: Mar 31 2012Apr 4 2012

Publication series

NameProceedings - International Symposium on Code Generation and Optimization, CGO 2012

Other

Other10th International Symposium on Code Generation and Optimization, CGO 2012
Country/TerritoryUnited States
CitySan Jose, CA
Period3/31/124/4/12

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Automatic speculative DOALL for clusters'. Together they form a unique fingerprint.

Cite this