Paper Info
Title
Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs
Abstract
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 Ω(n3/√S) for matrix-multiply on a cache size S by Hong & Kung to 2n3/√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 2n3/√S lower bound allows to demonstrate the optimality of panel-panel tiling for matrix-multiplication. 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.
Year
DOI
Venue
2020
10.1145/3385412.3385989
PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation London UK June, 2020
Keywords
DocType
ISBN
Data access complexity, I/O lower bounds, Static analysis, Affine programs
Conference
978-1-4503-7613-6
Citations 
PageRank 
References 
1
0.35
0
Authors
5
Name
Order
Citations
PageRank
Olivry Auguste110.35
Langou Julien210.35
Louis-noël Pouchet388047.61
P. Sadayappan44821344.32
Fabrice Rastello548238.30