SHF: Small: Graph-X: Exploiting Hidden Parallelism of Irregular and Non-Stencil Computation in High-Level Synthesis

现代现场可编程门阵列(FGA)在许多重要的人工智能驱动或大数据应用中实现了计算性能和能效的飞跃。然而，手工编程非常困难，容易出错，而且很难优化。该项目旨在开发一种新颖的“自动化”方法，以极大地提高现场可编程门阵列开发人员的生产率和他们设计的计算性能。该项目如果成功，不仅可以实现以前无法实现的高性能的现场可编程门阵列计算，而且可以显著提高现场可编程门阵列开发人员的整体工作效率。鉴于现代现场可编程门阵列技术在高科技未来的重要性与日俱增，解决这一根本问题对美国计算机产业未来的竞争力至关重要。该项目寻求解决的主要技术方面是如何以最佳方式综合不规则但重要的计算模式，因为所有最重要的现场可编程门阵列设计通常都表现出更通用和更复杂的存储器访问模式。为此，本项目提出了几种新颖的基于图的优化技术，这些技术不仅可以极大地有利于FPGA技术，而且可以很容易地扩展到其他计算领域，如CPU编译器或基于GPU的计算。特别是，该项目使用图形来捕获内存访问，并提出了三个研究主题：(I)GraphMorph解决了调度和绑定问题，(Ii)GraphFold最大化了冲突解决方案，以及(Iii)GraphProjection针对高维内存空间。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern Field Programmable Gate Arrays (FPGAs) hold great promise in leapfrogging our computing performance and energy efficiency in many important AI-driven or big data applications. However, manual FPGA programming is extremely difficult, error-prone, and hard to optimize. This project aims at developing a novel and "automatic" methodology to greatly improve the FPGA developer's productivity and the computing performance of their designs. This project, if successful, can not only achieve the high-performance of FPGA computing previously infeasible, but also significantly boost the FPGA developers' total productivity. Given the growing importance of modern FPGA technologies in our high-tech future, solving this fundamental problem is crucial to the future competitiveness of US computer industry.The major technical aspect that this project seeks to address is how to optimally synthesize irregular yet important computation patterns because all of the most important FPGA designs typically exhibit much more general and sophisticated memory access patterns. To this end, this project has proposed several novel and fundamental graph-based optimization techniques that can not only greatly benefit FPGA technology, but also be readily extended to other computing domains, such as CPU compiler or GPU-based computing. In particular, the project uses graphs to capture memory accesses, and presents three research thrusts: (i) GraphMorph solves the problem of scheduling and binding, (ii) GraphFold maximizes conflict resolution, and (iii) GraphProjection targets high-dimensional memory spaces.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.