超大规模集成电路设计中多目标超图优化划分问题研究

随着超大规模集成电路(VLSI)集成度遵循摩尔定律急剧增加，将VLSI设计划分为若干个子电路，采用分而治之的策略可有效地降低VLSI设计复杂度，提高VLSI设计能力和性能，促进我国集成电路产业的迅速发展。本项目从VLSI设计中多约束、多目标电路划分的实际需求出发，建立电路的超图模型，以多目标超图优化划分问题为主要研究目标；探索基于多水平方法的多约束、多目标的超图优化划分方法和理论，研究和解决粗化阶段的结点匹配策略、初始划分阶段的最小粗化超图划分方法、投影优化阶段结点的多目标迁移优化技术等关键科学问题，为得到超图的非劣最优划分集提供科学的理论和实验依据；进而提出VLSI划分系统的创新思路和整套技术路线，将VLSI划分问题转换为多目标超图优化划分问题，最终实现VLSI划分系统。本项目的研究将为VLSI设计提供有效的划分工具，在VLSI布局布线、软硬件协同仿真验证等领域具有广阔的应用前景。

随着超大规模集成电路(VLSI)集成度遵循摩尔定律急剧增加，将VLSI设计划分为若干个子电路，采用分而治之的策略可有效地降低VLSI设计复杂度，提高VLSI设计能力和性能，促进我国集成电路产业的迅速发展。本项目系统地研究了超大规模集成电路设计中多目标超图优化划分问题，提出了基于多水平方法的多约束、多目标的超图优化划分方法，主要研究工作如下：（一）针对赋权超图，提出了核值等概念并给出了形式化描述，分析了超图k水平p-核的构造性属性，实现了时间复杂度为O(n)的结点核值求解算法；（二）在多水平粗化阶段，提出了基于超图压缩存储格式的核排序重边匹配算法，将结点核值全局信息引入到超图的结点匹配过程，发挥结点核值导向性作用；（三）在多水平投影优化阶段，提出了基于离散群智能的结点多目标迁移优化算法，将结点迁移的收益值作为个体的启发式搜索信息，利用个体之间聚集协同表现出的智能行为，有效地搜索Pareto有效解；（四）将基于多水平方法的多目标超图优化划分应用在VLSI设计中，提出了基于多水平方法和赋权超图的大规模集成电路划分方法，实现了VLSI划分原型系统。本项目的研究成果为VLSI设计提供了有效的划分工具，在VLSI布局布线、软硬件协同仿真验证等领域具有广阔的应用前景。