电路划分(Circuit Paritioning)是指根据约束条件，把电路分成两个或多个互不相交的子集，以改善EDA软件自动化设计效果。电路划分的对象一般是由宏单元或标准单元组成的电路。电路划分的目的是降低超大规模集成电路的设计复杂性，增强划分电路的可读性，使得布图时面积优化和线长优化简洁高效。电路划分通常要求每个子集包含的单元面积大致相等，子集之间内连线数目最小。由于电路划分属于非确定性( Non-Poly, NP)难题，所以如何在较小时间复杂度内找到近似最优解是划分问题的目标。电路划分示意图如图5-19所示。

电路划分的约束条件通常为对电路总面积和子集面积的上下界约束，以及对应的主要目标函数，主要包括:①最小割( Minimal Cut),即被众子集切割的互连总数最小;②最小时延，即子集输入到输出所有路径上的最大时延最小;③最小化最大子集外部度( Maximum Subdomain Degree),即被子集切割的最大互连数必须小于某个上限值。以上目标函数用以保证电路划分不切割延时较大的关键路径，以及子集之间互连数最小并且互连布线密度尽可能均匀。

从电路划分基础上看，电路划分算法可以分为构造性算法和迭代改进算法。构造性算法从空集开始，逐步增加单元建立划分，包括聚类算法、组迁移算法和线网割模型等。迭代改进算法从任意初始划分开始，重复修改划分结果以满足约束条件，包括仿真退火算法、光谱分割算法和遗传算法等。

从算法原理上看，电路划分算法可以分为移动算法、解析几何算法、组合数学算法和集群算法等。移动算法通常采用交换或移动部分单元改善当前解的方法，逐步得到算法最优解。移动算法包括组迁移算法、仿真退火算法和混合遗传算法等。解析几何算法中最有代表性的是特征向量法。组合数学算法考虑模块形状和长度对时延的影响，时延估算较为精确，适合时延驱动的划分。组合数学算法包括网络流法、数学规划法和集合覆盖法。集群算法包括比例分制算法、随机漫步法和多级层次划分算法等。