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

我们已经进入了一个新时代，电力/能源限制已经成为技术趋势的根本驱动力。将数据从片外主存储器移动到处理器的时间和能量成本都显著高于双精度浮点计算的成本。随着未来技术的发展，这一比例只会变得更糟。因此，对算法固有的数据移动成本进行表征是非常重要的，对于大规模数据分析应用程序尤为关键。然而，与众所周知的算法的计算复杂性不同，数据移动的复杂性只对一小部分算法是已知的，以前用于表征算法的数据移动复杂性的技术要么局限于计算子类，要么需要特别的人工推理。该项目开发了一个可扩展的自动化工具，用于分析任意非结构化计算的数据移动复杂性，表示为计算有向无环图(CDAG)。研究人员探索了几个方向，包括核心外策略、图形的分解/重组、方向分量分析和经验函数拟合，以应对可伸缩性挑战。

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.