HELIX: Automatic parallelization of irregular programs for chip multiprocessing

Simone Campanoni*, Timothy Jones, Glenn Holloway, Vijay Janapa Reddi, Gu Yeon Wei, David Brooks

*Corresponding author for this work

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

65 Scopus citations

Abstract

We describe and evaluate HELIX, a new technique for automatic loop parallelization that assigns successive iterations of a loop to separate threads. We show that the inter-thread communication costs forced by loop-carried data dependences can be mitigated by code optimization, by using an effective heuristic for selecting loops to parallelize, and by using helper threads to prefetch synchronization signals. We have implemented HELIX as part of an optimizing compiler framework that automatically selects and parallelizes loops from general sequential programs. The framework uses an analytical model of loop speedups, combined with profile data, to choose loops to parallelize. On a six-core Intel® Core™ i7-980X, HELIX achieves speedups averaging 2.25×, with a maximum of 4.12× , for thirteen C benchmarks from SPEC CPU2000.

Original languageEnglish (US)
Title of host publicationProceedings - International Symposium on Code Generation and Optimization, CGO 2012
Pages84-93
Number of pages10
DOIs
StatePublished - Jul 9 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

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'HELIX: Automatic parallelization of irregular programs for chip multiprocessing'. Together they form a unique fingerprint.

Cite this