Wed 15 Jun 2022 11:20 - 11:40 at Macaw - Program Analysis Chair(s): Qirun Zhang

A Reduction – an accumulation over a set of values, using an associative and commutative operator – is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics.

Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sum, in which each component of the reduction’s output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once.

These techniques, however, do not support reductions that – when phrased in the language of the polyhedral model – span multiple statements. In such cases, existing approaches can generate incorrect code that violates the data dependencies of the original, unoptimized program.

In this work, we identify and formalize the multiple-/statement reduction problem as a bilinear optimization problem. We present a heuristic optimization algorithm for these reductions, and we demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. Specifically, the complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of $10^4$ to $10^6$ for typical real application inputs. We also confirm the significance of the improvement by showing that the speedups in wall-clock time range from $1.1\text{x}$ to over $10^7\text{x}$.

Wed 15 Jun

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

10:40 - 12:00
Program AnalysisSIGPLAN Track at Macaw
Chair(s): Qirun Zhang Georgia Institute of Technology, USA
10:40
20m
Talk
(OOPSLA 2020) Perfectly Parallel Fairness Certification of Neural Networks
SIGPLAN Track
Caterina Urban INRIA & École Normale Supérieure | Université PSL, Maria Christakis MPI-SWS, Valentin Wüstholz ConsenSys, Fuyuan Zhang MPI-SWS
11:00
20m
Talk
(PLDI 2020) OOElala : Order-Of-Evaluation based Alias Analysis for compiler optimization
SIGPLAN Track
Ankush Phulia IIT Delhi, India, Vaibhav Bhagee IIT Delhi, India, Sorav Bansal IIT Delhi and CompilerAI Labs
11:20
20m
Talk
(POPL 2021) Simplifying Dependent Reductions with the Polyhedral Model
SIGPLAN Track
Cambridge Yang MIT CSAIL, Eric Atkinson MIT CSAIL, Michael Carbin Massachusetts Institute of Technology
11:40
20m
Talk
(POPL 2021) The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis
SIGPLAN Track
Andreas Pavlogiannis Aarhus University, Anders Alnor Mathiasen Aarhus University