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 &#38; 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

 16:00 - 17:00: PLDI Research Papers - Static Analysis at PLDI Research Papers live stream Chair(s): Julian DolbyIBM Research, USAYouTube lightning session video 16:00 - 16:20Talk Automated Derivation of Parametric Data Movement Lower Bounds for Affine ProgramsAuguste OlivryInria, France, Julien LangouUniversity of Colorado at Denver, USA, Louis-Noël PouchetColorado State University, USA, P. SadayappanUniversity of Utah, USA, Fabrice RastelloInria, France 16:20 - 16:40Talk Fast Graph Simplification for Interleaved Dyck-ReachabilityYuanbo LiGeorgia Institute of Technology, USA, Qirun ZhangGeorgia Institute of Technology, USA, Thomas RepsUniversity of Wisconsin-Madison, USA 16:40 - 17:00Talk Static Analysis of Java Enterprise Applications: Frameworks and Caches, the Elephants in the RoomAnastasios 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