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

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

项目编号： No.61472147

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 何琨

作者单位： 华中科技大学

项目金额： 84万元

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

中文关键词： 算法设计与分析；布图规划；计算机辅助设计；糅合策略；NP难度

英文摘要： 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.

英文关键词： Algorithm Design and Analysis;Floorplanning;Computer Aided Design;Merging Strategy;NP Hard