O'Boyle, Michael

Franke, Bjoern

Lopez, Adam

Ginsbach, Philip Andreas

2020-04-29T14:08:33Z

2020-04-29T14:08:33Z

2020-06-25

The scaling limitations of multi-core processor development have led to a diversification of the processor cores used within individual computers. Heterogeneous computing has become widespread, involving the cooperation of several structurally different processor cores. Central processor (CPU) cores are most frequently complemented with graphics processors (GPUs), which despite their name are suitable for many highly parallel computations besides computer graphics. Furthermore, deep learning accelerators are rapidly gaining relevance. Many applications could profit from heterogeneous computing but are held back by the surrounding software ecosystems. Heterogeneous systems are a challenge for compilers in particular, which usually target only the increasingly marginalised homogeneous CPU cores. Therefore, heterogeneous acceleration is primarily accessible via libraries and domain-specific languages (DSLs), requiring application rewrites and resulting in vendor lock-in. This thesis presents a compiler method for automatically targeting heterogeneous hardware from existing sequential C/C++ source code. A new constraint programming method enables the declarative specification and automatic detection of computational idioms within compiler intermediate representation code. Examples of computational idioms are stencils, reductions, and linear algebra. Computational idioms denote algorithmic structures that commonly occur in performance-critical loops. Consequently, well-designed accelerator DSLs and libraries support computational idioms with their programming models and function interfaces. The detection of computational idioms in their middle end enables compilers to incorporate DSL and library backends for code generation. These backends leverage domain knowledge for the efficient utilisation of heterogeneous hardware. The constraint programming methodology is first derived on an abstract model and then implemented as an extension to LLVM. Two constraint programming languages are designed to target this implementation: the Compiler Analysis Description Language (CAnDL), and the extended Idiom Detection Language (IDL). These languages are evaluated on a range of different compiler problems, culminating in a complete heterogeneous acceleration pipeline integrated with the Clang C/C++ compiler. This pipeline was evaluated on the established benchmark collections NPB and Parboil. The approach was applicable to 10 of the benchmark programs, resulting in significant speedups from 1.26× on “histo” to 275× on “sgemm” when starting from sequential baseline versions. In summary, this thesis shows that the automatic recognition of computational idioms during compilation enables the heterogeneous acceleration of sequential C/C++ programs. Moreover, the declarative specification of computational idioms is derived in novel declarative programming languages, and it is demonstrated that constraint programming on Single Static Assignment intermediate code is a suitable method for their automatic detection.

https://hdl.handle.net/1842/37008

http://dx.doi.org/10.7488/era/309

en

The University of Edinburgh

Philip Ginsbach, Lewis Crawford, and Michael F. P. O’Boyle. CAnDL: A Domain Specific Language for Compiler Analysis. In Proceedings of the 27th International Conference on Compiler Construction, CC ’18, pages 151–162, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5644-2. doi: 10.1145/3178372.3179515. URL http: //doi.acm.org/10.1145/3178372.3179515.

Philip Ginsbach and Michael F. P. O’Boyle. Discovery and Exploitation of General Reductions: A Constraint Based Approach. In Proceedings of the 2017 International Symposium on Code Generation and Optimization, CGO ’17, pages 269–280, Piscataway, NJ, USA, 2017. IEEE Press. ISBN 978-1-5090-4931-8. URL http: //dl.acm.org/citation.cfm?id=3049832.3049862.

Bruce Collie, Philip Ginsbach, and Michael F. P. O’Boyle. Type-Directed Program Synthesis and Constraint Generation for Library Portability. In 28th International Conference on Parallel Architectures and Compilation Techniques, PACT 2019, Seattle, WA,USA,September23-26,2019,pages55–67,2019. doi: 10.1109/PACT.2019.00013. URL https://doi.org/10.1109/PACT.2019.00013.

Philip Ginsbach, Toomas Remmelg, Michel Steuwer, Bruno Bodin, Christophe Dubach, and Michael F. P. O’Boyle. Automatic Matching of Legacy Code to Heterogeneous APIs: An Idiomatic Approach. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems,ASPLOS’18,pages139–153,NewYork,NY,USA,2018.ACM. ISBN978-14503-4911-6. doi: 10.1145/3173162.3173182. URL http://doi.acm.org/10.1145/ 3173162.3173182.

heterogeneous computing

domain-specific languages

automatical targeting

C/C++

computational idioms

automatic detection

CAnDL

IDL

automatic recognition

From constraint programming to heterogeneous parallelism

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy