Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020
Fri 19 Jun 2020 16:00 - 16:20 at PLDI Research Papers live stream - Static Analysis Chair(s): Julian Dolby

Researchers and practitioners have for long worked on improving the computational complexity of algorithms, focusing on reducing the number of operations needed to perform a computation. However the hardware trend nowadays clearly shows a higher performance and energy cost for data movements than computations: quality algorithms have to minimize data movements as much as possible.

The theoretical operational complexity of an algorithm is a function of the total number of operations that must be executed, regardless of the order in which they will actually be executed. But theoretical data movement (or, I/O) complexity is fundamentally different: one must consider all possible legal schedules of the operations to determine the minimal number of data movements achievable, a major theoretical challenge. I/O complexity has been studied via complex manual proofs, e.g., refined from $\Omega(n^3/\sqrt{S})$ for matrix-multiply on a cache size $S$ by Hong & Kung to $2n^3/\sqrt{S}$ by Smith et al. While asymptotic complexity may be sufficient to compare I/O potential between broadly different algorithms, the accuracy of the reasoning depends on the tightness of these I/O lower bounds. Precisely, exposing constants is essential to enable precise comparison between different algorithms: for example the $2n^3/\sqrt{S}$ lower bound allows to demonstrate the optimality of panel-panel tiling for matrix-multiplication.

\emph{We present the first static analysis to automatically derive non-asymptotic parametric expressions of data movement lower bounds with scaling constants, for arbitrary affine computations}. Our approach is fully automatic, assisting algorithm designers to reason about I/O complexity and make educated decisions about algorithmic alternatives.

Conference Day
Fri 19 Jun

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

16:00 - 17:00
Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs
PLDI Research Papers
Auguste OlivryInria, France, Julien LangouUniversity of Colorado at Denver, USA, Louis-Noël PouchetColorado State University, USA, Saday SadayappanUniversity of Utah, USA, Fabrice RastelloInria, France
Fast Graph Simplification for Interleaved Dyck-Reachability
PLDI Research Papers
Yuanbo LiGeorgia Institute of Technology, USA, Qirun ZhangGeorgia Institute of Technology, USA, Thomas RepsUniversity of Wisconsin-Madison, USA
Static Analysis of Java Enterprise Applications: Frameworks and Caches, the Elephants in the Room
PLDI Research Papers
Anastasios AntoniadisUniversity of Athens, Greece, Nikos FilippakisCERN, Switzerland, Paddy KrishnanOracle Labs, Australia, Raghavendra RameshConsenSys, Australia, Nicholas AllenOracle Labs, Australia, Yannis SmaragdakisUniversity of Athens, Greece