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

Access status

Open

Documents

http://dl.acm.org/citation.cfm?id=3049862
Original languageEnglish
Title of host publicationCGO 2017 Proceedings of the 2017 International Symposium on Code Generation and Optimization
PublisherIEEE
Pages269-280
Number of pages12
ISBN (Print)978-1-5090-4931-8
StatePublished - Feb 2017

Abstract

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.

Download statistics

No data available

ID: 31487987