  Determining I/O lower bounds is a crucial step in obtaining
communication-efficient parallel algorithms, both across the memory hierarchy
and between processors. Current approaches either study specific algorithms
individually, disallow programmatic motifs such as recomputation, or produce
asymptotic bounds that exclude important constants. We propose a novel approach
for obtaining precise I/O lower bounds on a general class of programs, which we
call Simple Overlap Access Programs (SOAP). SOAP analysis covers a wide variety
of algorithms, from ubiquitous computational kernels to full scientific
computing applications. Using the red-blue pebble game and combinatorial
methods, we are able to bound the I/O of the SOAP-induced Computational
Directed Acyclic Graph (CDAG), taking into account multiple statements,
input/output reuse, and optimal tiling. To deal with programs that are outside
of our representation (e.g., non-injective access functions), we describe
methods to approximate them with SOAP. To demonstrate our method, we analyze 38
different applications, including kernels from the Polybench benchmark suite,
deep learning operators, and -- for the first time -- applications in
unstructured physics simulations, numerical weather prediction stencil
compositions, and full deep neural networks. We derive tight I/O bounds for
several linear algebra kernels, such as Cholesky decomposition, improving the
existing reported bounds by a factor of two. For stencil applications, we
improve the existing bounds by a factor of up to 14. We implement our method as
an open-source tool, which can derive lower bounds directly from provided C
code.
