Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions

Abstract

Data dependence analysis is a must-do operation for parallelisation since it reveals the safe parallelisable regions of serial codes. Generally, it relies on dynamic analysis, which incurs substantial execution time and memory space overheads. As a result, there have been many efforts in the literature to strike a balance between accuracy and runtime overhead. The approaches generally rely on random instruction sampling, parallelising analysis, as well as filtering statically determined dependencies and independencies. This paper considers an alternate approach of conducting static analysis at runtime, exploiting available states just before executing loops, potentially improving precision. In particular, the paper adopts abstract interpretation using interval, congruent, and bisector domains for detecting memory data dependencies in binary programs at runtime. Abstract interpretation has the advantage of being associated with the execution semantics, making it more natural to model binary instruction execution. The profiler is implemented on top of the Pin framework and evaluated using the Polyhedral, NPB, and SPEC 2006 benchmarks suites. Results show a mean accuracy of 90.4% with an average $16.3 \times$ speedup in time in comparison with related work, making it a promising approach.

Keywords

• Abstract interpretation
• data dependence profiling
• dynamic binary analysis
• interval domain
• congruent domain
• bisector domain