【EDA】EDA中聚类（Clustering）和划分（Partitioning）
在VLSI物理设计自动化中，聚类（Clustering）和划分（Partitioning）是两个不同的关键步骤，主要区别如下：
1. 目标与核心任务
聚类（Clustering）
-
目标：将电路中的门（Gates）分组为簇（Clusters），形成更小的簇级网络，减少后续设计步骤（如划分、布局）的复杂度。
- 核心目标：最小化簇间连接（Inter-Cluster Connections），例如减少跨簇的边数或最大化簇内连接。
- 典型约束：簇的大小限制（如最大簇内节点数）、簇的外部连接数限制，不要求簇间面积平衡。
-
输出：生成簇级网络，可能包含节点复制（Duplication）以优化延迟或连接。例如，Rajaraman和Wong算法通过延迟优化聚类，FlowMap算法处理LUT映射时的引脚约束。
划分（Partitioning）
-
目标：将电路划分为K个大小相近的分区（Partitions），最小化跨分区的连接（割集，Cutsize），或优化其他指标（如延迟、功耗）。
- 传统目标：最小化割集大小（即跨分区的边数或权重和）。
- 约束：分区大小平衡（如每个分区面积相差不超过一定比例），有时需考虑时序关键路径或功耗约束。
-
输出：平衡的K-way分区，例如二分（Bipartitioning）或K-way划分，直接为后续布局或布线提供结构化的子电路。
2. 算法与方法
聚类算法
- 延迟导向：如Rajaraman和Wong算法，最小化簇级网络的最长路径延迟；FlowMap算法针对FPGA的LUT映射，约束每个簇的输入引脚数（Pin Constraint）。
- 割集导向：如多水平粗化（Multi-Level Coarsening），通过合并节点逐步减少网络规模，目标是最小化跨簇连接。
- 核心思想：通过分组简化网络，不指定簇的数量，依赖启发式或优化算法（如标签传播、网络流）生成簇。
划分算法
- 基于移动（Move-Based）：如Kernighan-Lin（KL）算法通过交换节点对优化割集，Fiduccia-Mattheyses（FM）算法通过移动单个节点并使用桶结构高效计算增益。
- 谱方法（Spectral）：如EIG算法利用图的拉普拉斯矩阵特征向量最小化Ratio Cut，平衡割集和分区大小。
- 网络流：如FBB算法通过最大流计算寻找平衡割，处理复杂约束。
- 核心思想：直接对电路进行分区分割，确保分区大小平衡，目标函数聚焦割集或其他性能指标。
3. 关键区别对比
| 特征 | 聚类（Clustering） | 划分（Partitioning） |
|---|---|---|
| 目标 | 简化网络，减少簇间连接，不要求分区平衡 | 划分为K个平衡分区，最小化割集或优化其他指标（如延迟、功耗） |
| 约束 | 簇大小、外部连接数，无面积平衡要求 | 分区大小平衡（如面积、节点数相近） |
| 输出 | 簇级网络（可能含节点复制），簇数不固定 | K个平衡分区，分区数K预先指定（如二分、4-way等） |
| 典型算法 | Rajaraman-Wong（延迟优化）、FlowMap（LUT映射）、多水平粗化（割集优化） | KL、FM（移动优化）、EIG（谱方法）、FBB（网络流） |
| 应用场景 | 作为布局、划分的预处理步骤，减少问题规模 | 直接为布局、布线提供分区，确保资源分配均衡 |
| 节点处理 | 允许节点复制（Duplication）以优化连接或延迟 | 节点属于唯一分区，不复制 |
| 面积/大小要求 | 无严格平衡要求 | 必须满足面积平衡（如每个分区大小相差≤α%） |
4. 总结
- 聚类是预处理步骤，通过分组简化电路结构，目标是减少跨簇连接或优化延迟，不要求分区平衡；
- 划分是分区分割步骤，目标是将电路分为平衡的K个分区，最小化割集或其他性能指标，是后续布局和布线的基础。
两者相辅相成：聚类常用于划分前的粗化（Coarsening）阶段，减少划分的计算复杂度；而划分则是将电路结构化，为后续物理设计步骤提供明确的分区边界。
参考资料：Sung Kyu Lim - Practical problems in VLSI physical design automation-Springer (2008)