超大规模集成电路多目标划分的算法研究

项目名称： 超大规模集成电路多目标划分的算法研究

项目编号： No.61070020

项目类型： 面上项目

立项/批准年度： 2011

项目学科： 建筑科学

项目作者： 朱文兴

作者单位： 福州大学

项目金额： 10万元

中文摘要： 超大规模集成电路划分是VLSI物理设计过程中的一个关键阶段，该问题本质上是大规模的NP困难多目标组合优化问题，但目前还缺乏该多目标问题的有效的解决方案。本项目研究在最小割集、最小化最大子集外部度、最小时延等多个目标下超大规模集成电路k划分的方法。利用超图的数学模型，根据问题的超大规模特点，构造基于全局信息的高效的多级划分框架；在框架的最底层级，超图的规模较小，针对问题的最小割集、最小化最大子集外部度、最小时延等多目标函数的特点，研究相应的k路划分近似算法，保证最底层级电路划分的质量；对于框架的中间级的稍大规模的超图，研究适合这些目标的集成电路划分问题的离散局部搜索算法，以及改进局部最优解的离散动态凸化算法来提高划分质量；而对框架的高层级，超图的规模很大，则改进已有的FM算法来提高划分效果。本项目的研究成果不仅对超大规模集成电路划分有意义，而且对解决与电路划分类似的问题有借鉴作用。

中文关键词： 超大规模集成电路划分；多目标；多级划分；近似算法；局部搜索算法

英文摘要： Very lagre scale circuit partitioning problem is a fundamental problem in computer-aided design of very large-scale integrated circuits (VLSI CAD). This problem is indeed an NP-hard multiobjective combinatorial optimization problem, and has no effective solution methods at present. In this project, we consider the multiobjective problem under the cutsize, minimum maximal subset degree, and minimum delay objectives, and design effective multilevel partitioning schemes using the global net information of the circuit. At the coarsest level, the size of the hypergraph is smaller. We will design approximation algorithm for the problems with the cutsize, minimum maximal subset degree, and minimum delay objectives; for a lager hypergraph, we will design a discrete dynamic convexized method for patitioing of the hypergraph; for the finest hypergraph, we will use the FM algorithm to improve the solution by the discrete dynamic convexized method. The output of this project will be meaningful for the VLSI circuit partitioing problem, and will be beneficial for the solution of similar scientific problems.

英文关键词： VLSI circuit partition; multiobjective; multilevel partition; approximation algorithm; local search method.