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.

Fri 19 Jun
Times are displayed in time zone: (GMT-07:00) Pacific Time (US & Canada) change

pldi-2020-papers
16:00 - 17:00: PLDI Research Papers - Static Analysis at PLDI Research Papers live stream
Chair(s): Julian DolbyIBM Research, USA

YouTube lightning session video

pldi-2020-papers16:00 - 16:20
Talk
Auguste OlivryInria, France, Julien LangouUniversity of Colorado at Denver, USA, Louis-Noël PouchetColorado State University, USA, P. SadayappanUniversity of Utah, USA, Fabrice RastelloInria, France
pldi-2020-papers16:20 - 16:40
Talk
Yuanbo LiGeorgia Institute of Technology, USA, Qirun ZhangGeorgia Institute of Technology, USA, Thomas RepsUniversity of Wisconsin-Madison, USA
pldi-2020-papers16:40 - 17:00
Talk
Anastasios AntoniadisUniversity of Athens, Greece, Nikos FilippakisCERN, Switzerland, Paddy KrishnanOracle Labs, Australia, Raghavendra RameshConsenSys, Australia, Nicholas AllenOracle Labs, Australia, Yannis SmaragdakisUniversity of Athens, Greece
Pre-print