EAGER: Towards Automated Characterization of the Data-Movement Complexity of Large Scale Analytics Applications

Ohio State University, The, Columbus OH

Investigators

Abstract

We have entered a new era where power/energy limitations have become fundamental drivers of technological trends. The cost in both time and energy for moving data from off-chip main memory to the processor is significantly higher than the cost of a double-precision floating-point computation. With future technologies, this ratio will only get worse. Therefore the characterization of the inherent data movement costs of algorithms is very important, and is particularly critical for large scale data-analytic applications. However, unlike the well-understood computational complexity of algorithms, the data movement complexity is known only for a small number of algorithms. Prior techniques for characterizing the data movement complexity of algorithms has either been restricted to subclasses of computations, or has required ad hoc manual reasoning. This project develops a scalable automated tool for analyzing the data movement complexity of arbitrary unstructured computations, expressed as computational directed acyclic graphs (CDAGs). The researchers explore several directions including out-of-core strategies, decomposition/recomposition of graphs, directional component analysis, and empirical function fitting, to address scalability challenges.