SHF: Medium: Collaborative Research: An Inspector/Executor Compilation Framework for Irregular Applications

计算科学和工程提供对物理现象和设计空间的廉价探索，并帮助指导实验和提供理论建议。诸如分子动力学模拟、n体模拟、有限元分析和大型图形分析等不规则应用构成了科学计算应用的关键和重要部分。不规则应用程序的特征是具有在编译应用程序时无法确定的间接内存访问，例如A[B[I]]，因此严重限制了大量关于并行化编译器技术的工作的适用性。因此，对于推动科学前沿如此重要的不规则应用程序，在为不断变化的并行体系结构开发高性能实现方面，给计算和领域科学家带来了非常大的负担。该项目的智力优势是为不规则应用程序开发了一个编译器和运行时框架，特别适合于稀疏矩阵和图形计算，这些计算是计算科学和数据科学中关键问题的基础。其更广泛的影响是为领域科学家提供了一个强大的工具，用于优化和移植对性能至关重要的不规则计算到当前和未来的多核处理器和多核加速器。PIS还将继续在外联和多样性方面作出努力，以增加STEM职业的参与度，特别是在妇女和代表性不足的少数群体中。本项目的方法是扩展成熟的检查员/执行者范例，在运行时确定计算依赖结构(基于存储器访问模式)，并将运行时信息传递给编译时生成的执行者。具体地说，检查器可以在运行时在计算的早期检查存储器访问模式，并且执行器利用该信息来执行数据和计算重新排序和调度，以影响存储器层次结构和并行性优化。该项目正在开发一个带有新抽象的编译器和运行时框架，用于表达和操作检查器；然后，这些检查器可以彼此几乎无缝地集成在一起，并与现有的编译器优化(例如，循环平铺)集成在一起，以优化执行器。该项目还扩展了以前的工作，这些工作支持非仿射输入代码并混合了编译时和运行时优化。由此产生的系统提高了专家程序员的生产力，在各种非常规应用程序上实现了高性能和可移植性。

Computational science and engineering provides inexpensive exploration of physical phenomena and design spaces and helps direct experimentation and advise theory. Irregular applications such as molecular dynamics simulations, n-body simulations, finite element analysis, and big graph analytics constitute a critical and significant portion of scientific computing applications. An irregular application is characterized by having indirect memory accesses such as A[B[i]] that cannot be determined when the application is being compiled, therefore severely limiting the applicability of the large body of work on parallelizing compiler technology. Consequently, irregular applications, which are so important in pushing forward the frontiers of science, place a very large burden on computational and domain scientists in developing high-performance implementations for the ever-changing landscape of parallel architectures. The intellectual merit of this project is to develop a compiler and runtime framework for irregular applications, particularly well suited for sparse matrix and graph computations that underlie critical problems in computational science and data science. The broader impact is to provide domain scientists a powerful tool for optimizing and porting performance-critical, irregular computations to current and future multi-core processors and many-core accelerators. The PIs will also continue efforts in outreach and diversity to increase the participation in STEM careers, particularly among women and underrepresented minorities.The approach in this project is to extend the well-established inspector/executor paradigm where the computational dependence structure (based on the memory access pattern) is determined at runtime, and runtime information is passed to a compile-time generated executor. Specifically, an inspector can examine the memory access patterns early in the computation at runtime, and an executor leverages this information to perform data and computation reordering and scheduling to affect memory hierarchy and parallelism optimizations. The project is developing a compiler and runtime framework with new abstractions for expressing and manipulating inspectors; these inspectors may then be integrated nearly seamlessly with each other and with existing compiler optimizations (e.g., loop tiling) to optimize executors. The project is also extending prior work that supports non-affine input code and mixes compile-time and runtime optimization. The resulting system increases the productivity of expert programmers in achieving both high performance and portability on a wide variety of irregular applications.