GPU-Accelerated Fixpoint Algorithms for Faster Compiler Analyses (Best Paper Award)

Blaß T, Philippsen M (2019)


Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2019

Publisher: ACM

City/Town: New York, NY, USA

Pages Range: 122-134

Conference Proceedings Title: Proceedings of the 28th International Conference on Compiler Construction

Event location: Washington, D.C. US

ISBN: 978-1-4503-6277-1

URI: http://www2.informatik.uni-erlangen.de/publication/download/cc19_parcan_blass.pdf

DOI: 10.1145/3302516.3307352

Abstract

Inter-procedural data-flow analyses are slow. We parallelize these predicate propagation fixpoint algorithms efficiently on a GPU.

Our approach is (mostly) synchronization free even though the processed graphs in general are cyclic and have nodes with fan-in and fan-out degrees above 1. We detect and fix any data races that occur while propagating predicates in a SIMD fashion. Additionally, we solve the parallel termination problem by means of heuristics.

The GPU-codes of five data-flow analyses are up to 89.8 times faster than their sequential LLVM variants. Offloading the analyses to the GPU saves up to 26.5% of the total compilation time.

Authors with CRIS profile

Related research project(s)

How to cite

APA:

Blaß, T., & Philippsen, M. (2019). GPU-Accelerated Fixpoint Algorithms for Faster Compiler Analyses (Best Paper Award). In ACM (Eds.), Proceedings of the 28th International Conference on Compiler Construction (pp. 122-134). Washington, D.C., US: New York, NY, USA: ACM.

MLA:

Blaß, Thorsten, and Michael Philippsen. "GPU-Accelerated Fixpoint Algorithms for Faster Compiler Analyses (Best Paper Award)." Proceedings of the 28th International Conference on Compiler Construction, Washington, D.C. Ed. ACM, New York, NY, USA: ACM, 2019. 122-134.

BibTeX: Download