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

EAGER：实现大规模分析应用程序数据移动复杂性的自动表征

• 批准号: 1645599
• 负责人: Ponnuswamy Sadayappan
• 金额: $ 30万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-15 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1645599&HistoricalAwards=false
• 关键词: EAGER; Towards; Automated; Characterization; Data

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.

我们进入了一个新时代，在该时代，力量/能源限制已成为技术趋势的基本驱动力。 将数据从芯片主存储器转移到处理器的时间和能量的成本明显高于双重精确浮点计算的成本。 借助未来的技术，该比率只会变得更糟。 因此，算法固有的数据运动成本的表征非常重要，对于大型数据分析应用尤其重要。 但是，与算法的熟悉计算复杂性不同，数据运动复杂性仅因少数算法而闻名。该项目开发了一种可扩展的自动化工具，用于分析以计算有向无环图表示的任意非结构化计算的数据运动复杂性（CDAGS）。研究人员探索了几个方向，包括核心策略，图形的分解/重构，方向成分分析和经验函数拟合，以应对可伸缩性挑战。

项目成果

Automated derivation of parametric data movement lower bounds for affine programs

自动推导仿射程序的参数数据移动下限

• DOI: 10.1145/3385412.3385989
• 发表时间: 2020
• 期刊: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation
• 作者: Olivry, Auguste;Langou, Julien;Pouchet, Louis-Noël;Sadayappan, P.;Rastello, Fabrice
• 通讯作者: Rastello, Fabrice

Adaptive sparse tiling for sparse matrix multiplication

• DOI: 10.1145/3293883.3295712
• 发表时间: 2019-02
• 期刊: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
• 作者: Changwan Hong;Aravind Sukumaran-Rajam;Israt Nisa;Kunal Singh;P. Sadayappan

Characterization of Data Movement Requirements for Sparse Matrix Computations on GPUs

GPU 上稀疏矩阵计算的数据移动要求的表征

• DOI: 10.1109/hipc.2017.00040
• 发表时间: 2017
• 期刊: 24th IEEE International conference on High Performance Computing (HIPC
• 作者: Kurt, Sireyya Emre;Thumma, Vineeth;Hong, Changwan;Sukumaran-Rajam, Aravind;Sadayappan, P.
• 通讯作者: Sadayappan, P.

ColdRoute: effective routing of cold questions in stack exchange sites

• DOI: 10.1007/s10618-018-0577-7
• 发表时间: 2018-06
• 期刊: Data Mining and Knowledge Discovery
• 影响因子: 4.8
• 作者: Jiankai Sun-;Abhinav Vishnu;Aniket Chakrabarti;Charles Siegel;S. Parthasarathy

ATP: Directed Graph Embedding with Asymmetric Transitivity Preservation

• DOI: 10.1609/aaai.v33i01.3301265
• 发表时间: 2018-11
• 作者: Jiankai Sun-;Bortik Bandyopadhyay;Armin Bashizade;Jiongqian Liang;P. Sadayappan;S. Parthasarathy