SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 13:50 - 14:05 at Zurich F - PLDI 2020 Papers 2 Chair(s): Tyler Sorensen

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.

Thu 21 Oct

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

13:50 - 15:10
PLDI 2020 Papers 2SIGPLAN Papers at Zurich F
Chair(s): Tyler Sorensen University of California at Santa Cruz
13:50
15m
Talk
Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs
SIGPLAN Papers
Auguste Olivry Inria, France, Julien Langou , Louis-Noël Pouchet Colorado State University, USA, Saday Sadayappan University of Utah, USA, Fabrice Rastello Inria, France
14:05
15m
Talk
Responsive Parallelism with Futures and State
SIGPLAN Papers
Stefan K. Muller Illinois Institute of Technology, Kyle Singer Washington University in St. Louis, USA, Noah Goldstein Washington University in St. Louis, USA, Umut A. Acar Carnegie Mellon University, Kunal Agrawal Washington University in St. Louis, USA, I-Ting Angelina Lee Washington University in St. Louis, USA
14:20
15m
Talk
The Essence of Bluespec: A Core Language for Rule-Based Hardware Design
SIGPLAN Papers
Thomas Bourgeat , Clément Pit-Claudel MIT CSAIL, Adam Chlipala Massachusetts Institute of Technology, Arvind Massachusetts Institute of Technology, USA
14:35
15m
Paper
Semantic Code Search via Equational Reasoning
SIGPLAN Papers
Varot Premtoon Massachusetts Institute of Technology, USA, James Koppel Massachusetts Institute of Technology, USA, Armando Solar-Lezama Massachusetts Institute of Technology
Link to publication
14:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers