Automated Lower Bounds on the I/O Complexity of Computation Graphs
share
We consider the problem of finding lower bounds on the I/O complexity of arbitrary computations. Executions of complex computations can be formalized as an evaluation order over the underlying computation graph. In this paper, we present two novel methods to find I/O lower bounds for an arbitrary computation graph. In the first, we bound the I/O using the eigenvalues of the graph Laplacian. This spectral bound is not only efficiently computable, but also can be computed in closed form for graphs with known spectra. In our second method, we leverage a novel Integer Linear Program that directly solves for the optimal evaluation order; we solve this ILP on constant sized sub-graphs of the original computation graph to find I/O lower bounds. We apply our spectral method to compute closed-form analytical bounds on two computation graphs (hypercube and Fast Fourier Transform). We further empirically validate our methods on four computation graphs, and find that our methods provide tighter bounds than current empirical methods and behave similarly to previously published I/O bounds.
READ FULL TEXT