IOOpt: automatic derivation of I/O complexity bounds for affine programs
Auguste Olivry, Guillaume Iooss, Nicolas Tollenaere, Atanas Rountev, Ponnuswamy Sadayappan, Fabrice Rastello · 2021
Evaluating the complexity of an algorithm is an important step when developing applications, as it impacts both its time and energy performance. Computational complexity, which is the number of dynamic operations regardless of the execution order, is easy to characterize for affine programs. Data movement (or, I/O) complexity is more complex to evaluate as it refers, when considering all possible valid schedules, to the minimum required number of I/O between a slow (e.g. main memory) and a fast (e.g. local scratchpad) storage location.