SHF: Small: A Composable, Sound Optimization Framework for Loops and Recursion

在过去的几十年里，研究人员开发了许多通用框架来优化程序，通过使用循环来操作矩阵、网格和其他“规则”结构。这些优化可以提高并行性和性能，因此对于开发高性能软件至关重要。然而，大量的程序不使用循环，而是使用递归公式；现有的通用框架无法访问这些程序，并且迄今为止仅通过特别的、狭隘的技术进行了优化。这意味着适用于一个程序或一个领域的优化策略经常需要重新考虑，并为新的应用程序重新实现。这个项目的新奇之处在于开发新的程序表示、转换策略和分析技术，以构建一个新的通用框架，用于优化使用递归的程序。这个项目的影响将是为使用递归的更广泛的应用程序打开通用优化和转换的功能，这些应用程序出现在从图形到数据挖掘到模拟的各个领域。研究者在这个项目中开发的总体框架利用了几个新的组件。首先，它使用称为多磁带有限自动机的计算结构捕获递归应用程序的计算时间表，这使得框架能够区分来自程序不同部分的计算。其次，它表示该时间表的转换-它可以重构计算以提高局部性或并行性-使用多磁带有限换能器。第三，它使用一种称为见证元组的新颖抽象来捕获计算中的依赖关系——这限制了合法计算计划的空间。最后，该项目开发了新的、可确定的算法来确定一个特定的转换是否安全。然后将工作扩展到确定有前途的转换策略，处理更一般类型的递归程序，并以更有效的方式生成高性能代码。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Over the last several decades, researchers have developed numerous general frameworks to optimize programs that manipulate matrices, grids, and other "regular" structures by using loops. These optimizations can improve parallelism and performance and hence are critical to developing high-performance software. However, a large class of programs does not use loops but instead uses recursive formulations; these programs are inaccessible to existing general frameworks, and heretofore have only been optimized by ad hoc, narrowly-focused techniques. This means that optimization strategies that work for one program, or one domain, often have to be re-thought and re-implemented for new applications. This project's novelties are developing new program representations, transformation strategies, and analysis techniques to build a new, general framework for optimizing programs that use recursion. This project's impacts will be to open up the power of general optimizations and transformations to a broader range of applications that use recursion, which arise in domains ranging from graphics to data mining to simulation.The general framework developed by the investigator in this project leverages several novel components. First, it captures the schedule of computations of recursive applications using computational constructs called multi-tape finite automata, that allow the framework to distinguish between computations that arise from different parts of the program. Second, it represents transformations of that schedule--which can restructure a computation to improve locality or parallelism--using multi-tape finite transducers. Third, it captures dependences in the computation--which restrict the space of legal computation schedules--using a novel abstraction called witness tuples. Finally, the project develops new, decidable algorithms for determining whether a particular transformation is safe. The work is then extended to identify promising transformation strategies, handle more general types of recursive programs, and generate high-performance code in a more effective manner.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.