Write a Blog >>
POPL 2021
Sun 17 - Fri 22 January 2021 Online
Fri 22 Jan 2021 16:15 - 16:25 at POPL-A - Probabilistic Programming

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 sums, 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 dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program.

In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program’s dependences.

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. 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 speedups in wall-clock time that range from $1.1\text{x}$ to over $10^6\text{x}$.

Fri 22 Jan
Times are displayed in time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

15:45 - 16:45
Probabilistic ProgrammingPOPL at POPL-A
15:45
10m
Talk
λS: Computable Semantics for Differentiable Programming with Higher-Order Functions and Datatypes
POPL
Benjamin ShermanMassachusetts Institute of Technology, USA, Jesse MichelMassachusetts Institute of Technology, Michael CarbinMassachusetts Institute of Technology
Link to publication DOI
15:55
10m
Talk
Deciding Accuracy of Differential Privacy Schemes
POPL
Gilles BartheMPI-SP, Germany / IMDEA Software Institute, Spain, Rohit ChadhaUniversity of Missouri, Paul KrogmeierUniversity of Illinois at Urbana-Champaign, A. Prasad SistlaUniversity of Illinois at Chicago, Mahesh ViswanathanUniversity of Illinois at Urbana-Champaign
Link to publication DOI
16:05
10m
Talk
Probabilistic Programming Semantics for Name Generation
POPL
Marcin SabokMcGill University, Sam StatonUniversity of Oxford, Dario SteinUniversity of Oxford, Michael WolmanMcGill University
Link to publication DOI Pre-print
16:15
10m
Talk
Simplifying Multiple-Statement Reductions with the Polyhedral Model
POPL
Cambridge YangMIT CSAIL, Eric AtkinsonMIT CSAIL, Michael CarbinMassachusetts Institute of Technology
Link to publication DOI
16:25
10m
Talk
A Pre-Expectation Calculus for Probabilistic SensitivityDistinguished Paper
POPL
Alejandro AguirreIMDEA Software Institute and T.U. of Madrid (UPM), Gilles BartheMPI-SP, Germany / IMDEA Software Institute, Spain, Justin HsuUniversity of Wisconsin-Madison, USA, Benjamin Lucien KaminskiRWTH Aachen University, Germany, Joost-Pieter KatoenRWTH Aachen University, Christoph MathejaETH Zurich
Link to publication DOI
16:35
10m
Talk
Paradoxes of probabilistic programming
POPL
Jules JacobsRadboud University Nijmegen
Link to publication DOI Pre-print