面向层次式FPGA的多目标布局和布线问题研究

With the rapid increase of Very-Large-Scale Integration to follow Moore's Law, FPGA's large-scale expansion and complicated structure bring new challenges for its physical design. Compared with the traditional flat FPGA, hierarchical FPGA can effectively reduce the routing area and time delay in the case of the same completion rate. We focus on the multi-constraint and multi-objective placement and routing for hierarchical FPGA. Firstly, we build the weighted hypergraph, hierarchical routing resource graph and wire length estimation model. Secondly, we explore the method and theory of multi-constraint and multi-objective placement and routing based on the multi-level optimization method. Furthermore, we study the global matching strategy of logic-unit in the coarsening phase, the placement and global routing algorithm of the coarsest netlist in the initial placement and routing phase, the multi-objective refinement technology of the coupled-cluster in the uncoarsening and refinement phase, and other key scientific problems. We also provide the scientific theory and experimental basis for the Pareto optimal solutions. Finally, we propose the innovative approach and technical route of the FPGA placer and router based on the multi-level optimization method. The placement and routing tool of hierarchical FPGA is the main goal of the research proposal which will effectively improve the design capabilities and performance of FPGA and have a positive significance in the improvement of FPGA core technology.

随着VLSI 集成度遵循摩尔定律急剧增加，FPGA 规模膨胀化和结构复杂化给其物理设计带来了新的挑战。和传统的平面均匀分布模式的FPGA 相比，层次式FPGA 在相同布通率的情况下可有效地减少布线面积和信号时延。本项目以层次式FPGA 的多目标布局和布线为主要研究目标，建立赋权超图、多层次布线资源图和线长估算模型等数学模型；探索基于多层次优化方法的多约束、多目标的布局布线方法和理论，研究和解决结群阶段的逻辑单元全局匹配、初始布局布线阶段的布局和全局布线、投影优化阶段的结群单元多目标迁移优化等关键科学问题，为得到近似非劣最优的布局布线提供有效的理论和实验依据；进而提出基于多层次优化方法的FPGA 布局布线系统的创新思路和整套技术路线，为层次式FPGA 提供高效的布局布线工具。本项目的研究将有效地增强FPGA 设计能力和性能，对我国FPGA 核心技术研究水平的提高有着积极意义。

随着VLSI 集成度遵循摩尔定律急剧增加，FPGA 规模膨胀化和结构复杂化给其物理设计带来了新的挑战。和传统的平面均匀分布模式的FPGA 相比，层次式FPGA 在相同布通率的情况下可有效地减少布线面积和信号时延。研究适用于层次式FPGA的资源模型和与之配套的高效快速布局布线算法，可有效地提高FPGA设计能力和性能，促进我国FPGA产业的迅速发展。.本项目系统地研究了层次式FPGA 的多目标布局和布线问题，建立了赋权超图、多层次布线资源图和线长估算模型等数学模型，提出了基于多层次优化方法的多约束、多目标的布局布线方法，主要研究工作如下：（一）针对赋权超图，提出了核值等相关概念并给出了形式化描述，分析了超图k水平p-核的构造性属性，进而提出了基于结点属性函数快速求解赋权超图结点核值的算法框架，实现了时间复杂度为O(n)的求解结点核值算法；（二）在多层次优化方法的粗化阶段，提出了基于超图压缩存储格式的核排序重边匹配算法，将结点核值全局信息引入到超图的结点匹配过程，改进了以往仅利用边的权值、结点的度等局部信息进行结点选择的匹配策略，充分发挥了结点核值的导向性作用；（三）在多层次优化方法的投影优化阶段，提出了基于离散粒子群的结点多目标迁移优化算法，将结点迁移的收益值作为个体的启发式搜索信息，利用个体之间聚集协同表现出的智能行为，有效地搜索多约束条件下、多目标组合的Pareto有效解，使非劣迁移优化解向着Pareto-最优面逼近，增强了迁移优化算法的多目标搜索能力；（四）将基于多层次优化方法的多目标布局布线算法应用在层次式FPGA中，进行了层次式FPGA结构描述文件到布线资源图的转换、基于BLIF语言的电路网表文件到赋权超图的转换，提出了基于多层次方法和赋权超图的层次式FPGA布局布线方法，实现了面向层次式FPGA的布局布线原型系统。.本项目的研究成果为层次式FPGA提供了高效的布局布线工具，有效地缩短了设计周期、降低了设计成本，对我国FPGA核心技术研究水平的提高有着积极意义。