Edinburgh Research Explorer

Discovery and exploitation of general reductions: a constraint based approach

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

Related Edinburgh Organisations

Open Access permissions


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
StatePublished - 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
CountryUnited States
CityAustin, Texas


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.


International Symposium on Code Generation and Optimization (CGO) 2017


Austin, Texas, United States

Event: Conference

Download statistics

No data available

ID: 31487987