SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Fri 22 Oct 2021 11:20 - 11:35 at Zurich C - Algorithms, Libraries and Databases Chair(s): Hans-J. Boehm
Fri 22 Oct 2021 19:20 - 19:35 at Zurich C - Algorithms, Libraries and Databases - mirror Chair(s): Fabian Muehlboeck

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 the perceived internal complexity of these libraries, caused by the use of C as the implementation language and a focus on end-user-facing documentation, holds 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. On a newly-developed comprehensive benchmark suite for Presburger arithmetic, we show a 5.4x speedup in total runtime over the state-of-the-art library isl in its default configuration and 3.6x over a variant of isl optimized with element-wise 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.

Fri 22 Oct

Displayed time zone: Central Time (US & Canada) change

10:50 - 12:10
Algorithms, Libraries and DatabasesOOPSLA at Zurich C +8h
Chair(s): Hans-J. Boehm Google
10:50
15m
Talk
UDF to SQL Translation through Compositional Lazy Inductive SynthesisVirtual
OOPSLA
Guoqiang Zhang North Carolina State University; Facebook, Yuanchao Xu North Carolina State University, Xipeng Shen North Carolina State University; Facebook, Isil Dillig University of Texas at Austin
DOI
11:05
15m
Talk
LXM: Better Splittable Pseudorandom Number Generators (and Almost as Fast)Virtual
OOPSLA
Guy L. Steele Jr. Oracle Labs, Sebastiano Vigna University of Milan
DOI
11:20
15m
Talk
FPL: Fast Presburger Arithmetic through TransprecisionIn-PersonDistinguished Paper
OOPSLA
Arjun Pitchanathan IIIT Hyderabad, Christian Ulmann ETH Zurich, Michel Weber ETH Zurich, Torsten Hoefler ETH Zurich, Tobias Grosser University of Edinburgh
DOI
11:35
15m
Talk
Verifying Concurrent Multicopy Search StructuresIn-Person
OOPSLA
Nisarg Patel New York University, Siddharth Krishna Microsoft Research, Dennis Shasha New York University, Thomas Wies New York University
DOI
11:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA

18:50 - 20:10
Algorithms, Libraries and Databases - mirrorOOPSLA at Zurich C
Chair(s): Fabian Muehlboeck IST Austria
18:50
15m
Talk
UDF to SQL Translation through Compositional Lazy Inductive SynthesisVirtual
OOPSLA
Guoqiang Zhang North Carolina State University; Facebook, Yuanchao Xu North Carolina State University, Xipeng Shen North Carolina State University; Facebook, Isil Dillig University of Texas at Austin
DOI
19:05
15m
Talk
LXM: Better Splittable Pseudorandom Number Generators (and Almost as Fast)Virtual
OOPSLA
Guy L. Steele Jr. Oracle Labs, Sebastiano Vigna University of Milan
DOI
19:20
15m
Talk
FPL: Fast Presburger Arithmetic through TransprecisionIn-PersonDistinguished Paper
OOPSLA
Arjun Pitchanathan IIIT Hyderabad, Christian Ulmann ETH Zurich, Michel Weber ETH Zurich, Torsten Hoefler ETH Zurich, Tobias Grosser University of Edinburgh
DOI
19:35
15m
Talk
Verifying Concurrent Multicopy Search StructuresIn-Person
OOPSLA
Nisarg Patel New York University, Siddharth Krishna Microsoft Research, Dennis Shasha New York University, Thomas Wies New York University
DOI
19:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA