VLSI电路划分算法综述

电路划分作为VLSI物理设计中的一个关键阶段,其划分的结果直接影响后续的布图规划、布局、布线等过程.电路划分把由逻辑门或标准单元组成的电路分成多个子集,以降低VLSI设计的复杂性,其通常要求每个子集所包含的元件数目平衡,目标一般是这些子集之间的线网连接数达到最小.电路划分本质上属于图/超图划分,是NP-hard问题.根据近年来划分算法的研究进展,对划分算法进行了研究与综述,主要包括:基于移动的迭代改进方法、计算智能、基于聚类的多级方法、近似算法、多目标优化方法等.最后对全文进行总结,并展望了进一步的研究方向.