Discovery and exploitation of general reductions: a constraint based approach

Philip Ginsbach, Michael O'Boyle

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


Discovering and exploiting scalar reductions in programs has been studied for many years. The discovery of more complex reduction operations has, however, received less attention. Such reductions contain compile-time unknown parameters, indirect memory accesses and dynamic control flow, which are challenging for existing approaches. In this paper we develop a new compiler based approach that automatically detects a wide class of reductions. This approach is based on a constraint formulation of the reduction idiom and has been implemented as an LLVM pass. We use a custom constraint solver to identify program subsets that adhere to the constraint specification. Once discovered, we automatically generate parallel code to exploit the reduction. This approach is robust and was evaluated on C versions of three well known benchmark suites: NAS, Parboil and Rodinia. We detected 84 scalar reductions and 6 histograms, outperforming existing approaches. We show that exploiting histograms gives significant performance improvement.
Original languageEnglish
Title of host publicationCGO 2017 Proceedings of the 2017 International Symposium on Code Generation and Optimization
Place of PublicationAustin, Texas, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Print)978-1-5090-4931-8
Publication statusPublished - 28 Feb 2017
EventInternational Symposium on Code Generation and Optimization (CGO) 2017 - Austin, Texas, United States
Duration: 4 Feb 20178 Feb 2017


ConferenceInternational Symposium on Code Generation and Optimization (CGO) 2017
Country/TerritoryUnited States
CityAustin, Texas


Dive into the research topics of 'Discovery and exploitation of general reductions: a constraint based approach'. Together they form a unique fingerprint.

Cite this