CAREER: A Unified Compiler for Sparse Array Operations and Relational Algebra

社会越来越依赖于可扩展的数据分析来解决社会和工业问题。然而，正在分析的数据和正在使用的计算机都变得如此多样化和不规则，以至于交付高效的软件变得更加困难。为了推动数据分析和硬件开发的创新，需要利用数据的结构和稀疏性以及新硬件的功能的计算机系统。然而，利用当前方法的这些属性和功能会使软件变得更加复杂。该项目的新颖之处在于开发了一个软件系统，该系统可以自动地将不同的和不规则的数据源结合起来，并针对不同的硬件。该项目的影响是在大量不规则数据分析计算（包括稀疏张量代数、稀疏数组操作和关系代数）中提高10 -100倍的性能。通过利用新兴的专用硬件，甚至可以实现更大的性能改进。该项目为稀疏张量代数、稀疏数组操作（如稀疏NumPy）和关系代数探索新的编程语言结构和新的统一编译器系统。统一的编译器结合了三种独立的语言，分别描述应用程序逻辑（例如，稀疏数组操作之后的关系查询），数据表示（例如，以压缩形式存储的关系尝试和稀疏数组）和计算组织（例如，针对配备专用张量处理硬件的GPU）。为了实现这些目标，该项目将为稀疏数组操作和关系代数开发统一的编译器理论，为关系开发新的数据表示，并开发将这些应用程序编译为专用加速器的技术。这个项目的成功将带来新的灵活的数据分析系统，它可以跨数据结构和硬件移植，并且比目前的通用方法快几个数量级，同时又不会失去通用性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Society is increasingly dependent on scalable data analytics to solve societal and industrial problems. However the data being analyzed and the computers being used are both becoming so diverse and irregular that it is much harder to deliver efficient software. To drive innovation in both data analytics and hardware development, computer systems are needed that take advantage of the structure and sparsity of the data and the capabilities of new hardware. However, taking advantage of these properties and capabilities with current approaches makes the software a lot more complicated. The project's novelties are the development of a software system that automatically specializes itself to combine diverse and irregular data sources and to target diverse hardware. The project's impacts are a 10x-100x performance improvement across a large class of irregular data analytics computations, including sparse tensor algebra, sparse array operations, and relational algebra. Even greater performance improvements will be possible by taking advantage of emerging specialized hardware. The project explores new programming language constructs and a new unified compiler system for sparse tensor algebra, sparse array operations (e.g., sparse NumPy), and relational algebra. The unified compiler combines three separate languages that describe respectively the application logic (e.g., a relational query followed by sparse array operations), the data representations (e.g., relational tries and sparse arrays stored in compressed form), and the organization of the computation (e.g., to target a GPU equipped with specialized tensor processing hardware). To achieve these goals, the project will develop a unified compiler theory for sparse array operations and relational algebra, develop new data representations for relations, and develop techniques to compile these applications to specialized accelerators. Success of this project will lead to new flexible data analytics systems that port across both data structures and hardware and that are orders of magnitude faster than current general approaches without loss of generality.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.