VLSI电路划分算法综述

A survey of VLSI circuit partitioning algorithms

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

Circuit partitioning is a very important stage during very large-scale integrated circuits（VLSI） physical design.The quality of circuit partitioning directly affects the sequent floorplanning,placement,routing,etc.The essence of circuit partitioning is to divide the circuit consisting of logic gates or standard cells into subsets.It aims to reduce the VLSI design complexity.The objective of circuit partitioning is to minimize the number of inter-connection of subsets,such that the number of cells in each subsets are roughly equal.It can be modeled as a graph/hypergraph partitioning problem,which is known to be NP-hard.The problem has been great concern in recent years,and a number of algorithms have been proposed.This paper reviews the partitioning algorithms,mainly including： move-based iterative improvement methods,computational intelligence,multilevel methods based on clustering,approximation algorithms,multi-objective optimization methods.Finally,the points are summarized,moreover,some issues for further research are addressed.