基于糅合策略的超大规模集成电路布图规划问题的算法研究

Floorplanning is a multi-objective strong NP hard problem with complicated constraints. As an essential step in the physical design phase of the very large scale integration (VLSI), it not only directly determines the area and the overall structure of the integrated circuit chip, but also will it has a decisive impact on the follow-up steps of placement and routing. Up to now, however, its mathematical model is not sufficiently clear and unified, the related fundamental research is not very strong, and the VLSI industry needs more universal and scalable algorithms. Taking into account of the actual requirements of the modern industrial VLSI design, this project will focus on the mathematical model, computability, complete algorithms and non-complete algorithms for the floorplanning problem. First, we will design an enumeration algorithm basing on the corner-occupying method for floorplanning with hard modules, propose an complete layout algorithm and give a strict proof on the sufficient condition of feasible layouts for floorplanning with soft modules. Then, we will figure out a local search method to optimize the wirelength by combining the merging strategy for floorplanning with soft modules. Next, we plan to design a heuristic approach for solving the floorplanning with hard modules basing on some strategies for the clustering problem and the rectangle packing area minimization problem. Finally, on the basis of module merging method, we will borrow the idea of "relaxation" and "rounding" for integer programming and explore an approximation algorithm for floorplanning with hard modules. It is expected that the project will provide theoretical and technical support to promote the development of modern VLSI industry.

布图规划问题是一个具有复杂约束条件的、多目标的强NP难度问题。作为超大规模集成电路物理设计阶段的一个核心步骤，它不仅直接确定了集成芯片的面积及整体结构，而且对后续的布局、布线设计会产生决定性影响。拟针对目前其模型不够清晰统一、基础性理论研究不够充分、缺少通用的可扩展性算法等现状，结合现代工业中集成电路设计的实际需要，深入开展布图规划问题的数学模型、可计算性、完备算法和非完备算法的研究。拟基于占角策略设计求解硬模块布图规划问题的枚举算法；基于糅合策略研究软模块布图规划问题的完备放置算法，证明可合法布图的严格充分条件；基于模块糅合设计考虑连线优化的软模块搜索算法；利用求解聚类问题和矩形Packing面积最小化问题的相关策略设计求解硬模块问题的启发式算法；以模块糅合为基础，借鉴整数规划中松弛、还原的思想探索硬模块问题的近似求解算法。本项目将为促进超大规模集成电路相关产业的发展提供理论和技术支持。

布图规划问题是一个具有复杂约束条件的、多目标的强NP难度问题。作为超大规模集成电路物理设计阶段的一个核心步骤，它不仅直接确定了集成芯片的面积及整体结构，而且对后续的布局、布线设计会产生决定性影响。此项目为Floorplanning问题定义了清晰的数学模型，并设计了高效率的求解算法，将矩形Packing问题的占角动作拟人算法和圆形Packing问题的拟物势能下降算法成功迁移和运用到Floorplanning问题的求解中。设计了提高电路板面积利用率的动态归约（DRA）算法；对于二维软矩形Packing问题和固定边界的软模块布图规划问题，分别设计了迭代糅合Packing算法（IMP）和基于迭代糅合的层次划分算法（IMP-HP）；对于固定边界的混合模块布图规划问题，设计了基于拟牛顿法的布图规划算法（QNF）。在包括IEEE Transactions on SMC: Systems、 Computers & Operations Research、European Journal of Operational Research、IJCAI、AAAI、ECAI等国内外核心期刊、会议发表论文19、17篇，其中SCIE/SSCI收录26篇，EI收录29篇。本项目的研究成果将为促进超大规模集成电路相关产业的发展提供理论和技术支持。