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

在过去的几十年里，研究人员已经开发了许多通用的框架来优化程序，通过使用循环来操纵矩阵，网格和其他“规则”结构。这些优化可以提高并行性和性能，因此对于开发高性能软件至关重要。然而，一个大类的程序不使用循环，而是使用递归公式，这些程序是无法访问现有的一般框架，迄今为止，只有通过特设的，狭隘的技术进行优化。这意味着，对于一个程序或一个领域有效的优化策略，通常必须重新考虑并重新实现新的应用程序。这个项目的新颖之处在于开发新的程序表示、转换策略和分析技术，以构建一个新的通用框架来优化使用递归的程序。这个项目的影响将是开放的通用优化和转换的能力，以更广泛的应用程序，使用递归，出现在从图形到数据挖掘到仿真的领域。首先，它捕获递归应用程序的计算时间表，使用称为多带有限自动机的计算结构，允许框架区分来自程序不同部分的计算。其次，它表示该调度的转换-可以使用多带有限转换器重构计算以提高局部性或并行性。第三，它使用一种称为见证元组的新颖抽象来捕获计算中的依赖性--这限制了法律的计算调度的空间。最后，该项目开发了新的，可判定的算法，用于确定特定的转换是否安全。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.