Skip to main content

Automatic speculative DOALL for clusters

Author(s): Kim, Hanjun; Johnson, Nick P; Lee, Jae W; Mahlke, Scott A; August, David I

To refer to this page use:
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 first 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.8x on a 120-core cluster, whereas DOALL without speculation achieves only 4.5x speedup. This demonstrates that speculation makes scalable fully-automatic parallelization for clusters possible.
Publication Date: Mar-2012
Citation: Kim, Hanjun, Nick P. Johnson, Jae W. Lee, Scott A. Mahlke, and David I. August. "Automatic speculative DOALL for clusters." Proceedings of the Tenth International Symposium on Code Generation and Optimization (2012): pp. 94-103. doi:10.1145/2259016.2259029
DOI: 10.1145/2259016.2259029
ISSN: 2164-2397
Pages: 94 - 103
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Tenth International Symposium on Code Generation and Optimization
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.