IOOpt: automatic derivation of I/O complexity bounds for affine programs
Auguste Olivry, Guillaume Iooss, Nicolas Tollenaere, Atanas Rountev, P. Sadayappan, Fabrice Rastello
Abstract
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.
Topics & Concepts
Computer scienceComputational complexity theoryAffine transformationParallel computingTheoretical computer scienceAlgorithmDistributed computingMathematicsPure mathematicsParallel Computing and Optimization TechniquesAdvanced Data Storage TechnologiesDistributed and Parallel Computing Systems