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

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