Elements: Transformation-Based High-Performance Computing in Dynamic Languages

技术计算的一个关键能力是通过各种不同的过程来处理大型的规则形状的数组。该设施是天气预报、人工智能和图像处理等领域的基础。 相应地，现代计算硬件已经发展出用于以高效率执行这样的计算的先进能力。不幸的是，迄今为止，使期望的过程适应给定的硬件的过程是昂贵的、费力的并且容易出错。一个天真的认识和一个谨慎的认识之间的性能差异是50倍，这是规则，而不是例外。Loopy，这个项目的主题，通过使用人工引导的自动程序重写来解决这个问题。Loopy已经在许多应用中展示了应用影响力，从自然和工程现象的模拟到神经科学，它帮助用户以更少的努力实现更高的性能。目前的建议涉及几个重要的改进，将有助于使Loopy更有效，更容易应用，通过扩大类的程序，Loopy可以转换，提高Loopy代表片上通信的手段，并允许它实现重要的基本操作，经常造成有效的实施困难。这项工作的一个重要组成部分是通过实现交互式用户界面，使Loopy本身易于用户社区使用，这样只需点击鼠标就可以应用程序转换，而不是编写计算机代码。提出的进展将通过一个样本工作量来展示，该样本工作量是当今技术计算中面临的许多计算和软件挑战的象征。多维数组（有时称为“张量”）是许多科学计算的基础数据结构，其应用范围从天气预测到深度学习，再到图像处理和计算神经科学。 即使是最简单的数组运算之一，矩阵-矩阵乘法的有效执行，也对现代计算机提出了相当大的技术挑战。通过基于多面体的程序转换工具，拟议的软件将提供数学意图和程序优化的技术挑战之间的分离，允许每个任务由领域专家执行。在拟议的项目中，PI将开发更有效的片上通信，前缀和代码生成，程序转换中的重用和抽象，增加转换发现和性能分析的易用性，以及在用户程序中表达数组计算的方法。PI将通过具有广泛适用性的具有挑战性的应用程序来验证所提出的技术。所提出的研究的智力价值在于（1）映射和扩展景观的转换为基础的编程从一次性的脚本，可重用的转换组件，（2）开发一个统一的，循环/阵列轴为基础的方法来表达片上通信，同时减少冗余的Loopy？的程序表示和转换，（3）探索高性能语言的设计空间，在执行布局和数据布局之间建立密切联系，（4）开发交互式程序转换和性能分析工具，沿着发现高性能计算中劳动力培训的潜在含义，（5）证明所有已开发的组成部分可以以实际和一致的方式一起应用。通过研究生和本科生的教学以及对该项目支持的学生和博士后的指导，PI为扩大人才库做出了贡献。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

A key capability in technical computing is the processing of large, regularly-shaped arrays of numbers by a wide variety of different processes. This facility is foundational in, for example, weather prediction, artificial intelligence, and image processing. Correspondingly, modern computing hardware has evolved advanced capabilities for carrying out such computations with high efficiency. Unfortunately, the process of adapting a desired process to a given piece of hardware thus far is costly, laborious, and error-prone. Differences of a factor of 50 in performance between a naive realization and a careful one is the rule, rather than the exception. Loopy, the subject of this project, attacks this problem by using human-guided, automated program rewriting. Loopy has demonstrated application impact in a number of applications ranging from the simulation of natural and engineering phenomena to neuroscience, where it has helped its users achieve higher performance with less effort. The present proposal concerns several important improvements that will contribute to making Loopy more effective and easier to apply, through enlarging the class of programs that Loopy can transform, improving the means by which Loopy represents on-chip communication, and permitting it to realize important basic operations that routinely pose difficulty in efficient implementation. An important component of the effort is making Loopy itself easy to use for its user community, through the realization of an interactive user interface, so that program transformations can be applied with the click of a mouse, rather than by writing computer code. The proposed advances will be demonstrated through a sample workload that is emblematic of many of the computational and software challenges faced in technical computing today.Multidimensional arrays (sometimes called 'tensors') are a foundational data structure for much of scientific computing, with applications ranging from weather prediction to deep learning, to image processing and computational neuroscience. Even the efficient execution of one of the simplest operations on arrays, matrix-matrix multiplication, poses considerable technical challenges on modern computers. Through a polyhedrally-based program transformation tool, the proposed software will provide separation between mathematical intent and the technical challenges of program optimization, allowing each task to be performed by a domain expert. In the proposed project, the PI will develop means for more efficient on-chip communication, code generation for prefix sums, reuse and abstraction in program transformation, increasing the ease of use in transformation discovery and performance analysis, and for expressing array computations in user programs. The PI will validate the proposed techniques through a challenging application with broad applicability. The intellectual merit of the proposed research lies in (1) mapping out and extending the landscape of transformation-based programming from one-off scripts to reusable transform components, (2) the development of a unifying, loop/array-axis-based approach to expressing on-chip communication while reducing redundancy in Loopy?s program representation and transformation, (3) exploring the design space of high-performance languages that establish a close link between execution placement and data placement, (4) the development of an interactive program transform and performance analysis tool, along with the discovery of potential implications for workforce training in high-performance computing, (5) a demonstration that all the developed components can be applied together in a practical and coherent manner. Through graduate and undergraduate teaching as well as mentoring of the students and postdocs supported by this project, the PI contributes to enlarging the talent pool.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.