Automatically exploiting cross-invocation parallelism using runtime information

Jialu Huang, Thomas B. Jablin, Stephen R. Beard, Nick P. Johnson, David I. August

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

24 Scopus citations

Abstract

Automatic parallelization is a promising approach to producing scalable multi-threaded programs for multicore architectures. Many existing automatic techniques only parallelize iterations within a loop invocation and synchronize threads at the end of each loop invocation. When parallel code contains many loop invocations, synchronization can easily become a performance bottleneck. Some automatic techniques address this problem by exploiting cross-invocation parallelism. These techniques use static analysis to partition iterations among threads to avoid crossthread dependences. However, this partitioning is not always achievable at compile-time, because program input determines dependence patterns at run-time. By contrast, this paper proposes DOMORE, the first automatic parallelization technique that uses runtime information to exploit additional cross-invocation parallelism. Instead of partitioning iterations statically, DOMORE dynamically detects crossthread dependences and synchronizes only when necessary. DOMORE consists of a compiler and a runtime library. At compile time, DOMORE automatically parallelizes loops and inserts a custom runtime engine into programs. At run-time, the engine observes dependences and synchronizes iterations only when necessary. For six programs, DOMORE achieves a geomean loop speedup of 2.1× over parallel execution without cross-invocation parallelization and of 3.2 × over sequential execution on eight cores.

Original languageEnglish (US)
Title of host publicationProceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013
DOIs
StatePublished - May 6 2013
Event11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013 - Shenzhen, China
Duration: Feb 23 2013Feb 27 2013

Publication series

NameProceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013

Other

Other11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013
CountryChina
CityShenzhen
Period2/23/132/27/13

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Control and Optimization

Fingerprint Dive into the research topics of 'Automatically exploiting cross-invocation parallelism using runtime information'. Together they form a unique fingerprint.

Cite this