针对FPGA协处理器的高速布局布线算法研究

FPGA co-processors support reconfigurable computing, which enables low-energy and high-performance computation for specific applications. However, the compilation time for FPGAs (including high-level synthesis, logic synthesis, placement and routing) is significantly longer than the compilation time of a functionally-equivalent program for CPUs. The long compilation time reduces productivity and prohibits the adoption of FPGA co-processors and reconfigurable computing by software engineers. Since the placement and routing time consumes almost 3/4 of the total runtime, in order to accelerate the compilation time, we are going to develop ultra-fast placement and routing tools that are 10X to 100X faster than existing tools. To get start, we will examine the optimality of existing placers and develop our own high-quality placer compatible with modern heterogeneous FPGA architectures. This placer and an existing negotiation-based router will be accelerated through algorithm enhancements (e.g., analytical method, multilevel method) and parallelism. In addition, an open-source FPGA physical design flow will be developed for further study of reconfigurable computing.

FPGA协处理器能支持可重构计算，在特定应用中实现高性能低能耗的计算。然而，FPGA程序的编译时间（高层次综合、逻辑综合、布局布线）远远大于同等功能的CPU程序的编译时间。漫长的编译时间降低开发效率，阻碍了软件工程师应用FPGA协处理器与可重构计算。在FPGA编译过程里，布局布线占了大概四分之三的时间；为了缩短编译时间，我们打算开发高速的布局布线器，实现比现有布局布线器快10倍至100倍的效果。首先，我们会对现有布局器做最优化研究，并开发一个高质量的支持现代异构FPGA体系结构的布局器。之后，我们将采用算法加速（采用解析式算法和高层次方法）和并行加速的手段，来使我们的布局器以及一个基于协商的布线器达到最大的加速效果。另外，我们将开发一套开放源代码的FPGA物理综合流程，以推动可重构计算的研究。

FPGA协处理器能支持可重构计算，在特定应用中能实现高性能低能耗的计算。然而，FPGA程序的编译时间远远大于同等功能的CPU程序的编译时间。漫长的编译时间降低开发效率，阻碍了软件工程师应用FPGA协处理器与可重构计算。在FPGA编译过程里，布局布线占了大概四分之三的时间；为了缩短编译时间，我们打算开发高速的布局布线器，实现比现有布局布线器快10倍至100倍的效果。.项目成功实现了：1）现有FPGA布局器的最优化研究。我们通过构造具有已知最优布局线长的异质FPGA网表，从而定量评估DSP、BRAM等异质模块对于布局线长的影响。 2）布局布线算法的高速并行方法的设计。我们提出基于网表位置信息最优化递归划分的粗粒度并行的FPGA布线方法，实现了7倍的加速效果，是目前学术界发表的加速比最大的FPGA并行布线方法。另外，我们提出基于通用图形处理器细粒度并行的FPGA布线方法，实现了6倍的加速效果；预计该技术使用多块通用图形处理器能实现15倍的加速效果，或者叠加上述的粗粒度并行布线方法实现42倍的加速效果。对于布局问题，我们提出布局后的触发器聚集算法，利用算法优化和多线程技术将核心计算加速了25倍，快速有效地降低了30%的时钟功耗。3）支持异质FPGA物理设计自动化的并行算法开发平台。我们利用现有FPGA开发工具的TCL语言界面，搭建了支持大规模集群的分布式布局算法开发平台；该平台支持新兴的分布式计算框架Spark编程，并能演示一个分布式详细布局算法的例子。4）FPGA应用的加速。针对基于Mumford-Shah模型的图像同时重建及分割算法，我们提出了使用异步并行更新技术的FPGA加速设计；相比通用图形处理器，速度和能效分别提高了1.2倍和58倍。本项目已发表国内外会议论文7篇和专利申请1项。