×

EigenCFA

swMATH ID: 14136
Software Authors: Prabhu, Tarun; Ramalingam, Shreyas; Might, Matthew; Hall, Mary
Description: EigenCFA, accelerating flow analysis with GPUs. We describe, implement and benchmark EigenCFA, an algorithm for accelerating higher-order control-flow analysis (specifically, 0CFA) with a GPU. Ultimately, our program transformations, reductions and optimizations achieve a factor of 72 speedup over an optimized CPU implementation.{par}We began our investigation with the view that GPUs accelerate high-arithmetic, data-parallel computations with a poor tolerance for branching. Taking that perspective to its limit, we reduced Shivers’s abstract-interpretive 0CFA to an algorithm synthesized from linear-algebra operations. Central to this reduction were “abstract” Church encodings, and encodings of the syntax tree and abstract domains as vectors and matrices.{par}A straightforward (dense-matrix) implementation of EigenCFA performed slower than a fast CPU implementation. Ultimately, sparse-matrix data structures and operations turned out to be the critical accelerants. Because control-flow graphs are sparse in practice (up to 96
Homepage: http://dl.acm.org/citation.cfm?doid=1926385.1926445
Keywords: abstract interpretation; CPS; EigenCFA; flow analysis; GPU; lambda calculus; matrix; program analysis
Related Software: PETSc; CUDA; THORS; TRecS; ARMC; SPIN
Referenced in: 3 Publications

Referenced in 0 Serials

Referenced in 1 Field

3 Computer science (68-XX)

Referencing Publications by Year