[month] [year]

P Arjun – Dual Degree CSE

P Arjun received his MS Dual Degree in Computer Science and Engineering (CSE). His research work was supervised by Dr. Srinathan kannan. Here’s a summary of  Arjun’s thesis FPL: Fast Presburger Arithmetic through Transprecision.

Presburger arithmetic provides the mathematical core for the polyhedral compilation techniques that drive analytical cache models, loop optimization for ML and HPC, formal verification, and even hardware design. Polyhedral compilation is widely regarded as being slow due to the potentially high computational cost of the underlying Presburger libraries. Researchers typically use these libraries as powerful black-box tools, but a lack of internal documentation and decade-old C implementations hold back broader performance optimization efforts. With FPL, we introduce a new library for Presburger arithmetic built from the ground up in modern C++. We carefully document its internal algorithmic foundations, use lightweight C++ data structures to minimize memory management costs, and deploy transprecision computing across the entire library to effectively exploit machine integers and vector instructions. Major parts of our library have already been upstreamed into the LLVM/MLIR open source project, and this functionality is being used by MLIR to perform loop fusion. On a newly-developed comprehensive benchmark suite for Presburger arithmetic, we show a 5.25x speedup in total runtime over the state-of-the-art library isl in its default configuration and 3.14x when over a variant of isl optimized with elementwise transprecision computing. We expect that the availability of a well-documented and fast Presburger library will accelerate the adoption of polyhedral compilation techniques in production compilers.