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

项目名称： 针对FPGA协处理器的高速布局布线算法研究

项目编号： No.61202073

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 罗国杰

作者单位： 北京大学

项目金额： 25万元

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

中文关键词： 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 co-processor；physical design；routing；parallelization；acceleration