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.
ISBN: 978-1-4503-6277-1
URI: http://www2.informatik.uni-erlangen.de/publication/download/cc19_parcan_blass.pdf
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
Thorsten Blaß
Lehrstuhl für Informatik 2 (Programmiersysteme)
Michael Philippsen
Lehrstuhl für Informatik 2 (Programmiersysteme)
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