跳到正文
半导体开放世界

网表划分

Netlist Partitioning

在容量与平衡约束下，把元胞分组并减少跨组连接代价。

进阶出处 2 份资料
报告问题

速览

约 1 分钟

先把元胞和线网表示为图或超图，再在容量约束下比较分组。少割边、面积平衡和关键连接是不同约束；选定目标后才能解释交换或移动的好坏。

系统理解

约 2 分钟

划分把复杂设计分成可处理的子问题。元胞是要分配的对象，多端线网是共同连接；跨块后产生接口开销。KL通过成对交换试探改善，FM通过单元移动处理更一般的面积与超图目标，多级框架则把聚合和逐级细化结合。它们依赖明确的代价与可行性规则，不能把一次局部停止当成全局最优证明。

在逻辑综合之后深化网表分组，再连接芯片规划；复用既有P&R总览。

关键参数

关键参数
参数单位含义
块容量μm²或规定资源单位每块允许的面积或其他资源上界
割代价—选定图/超图模型下的跨块连接代价
移动增益—一次试探造成的割代价减少量

常见误区

  • 节点个数相等就一定面积平衡。
  • 多端网任意拆边后，割边数仍等于割网数。
  • 贪心每步都改善才可能得到更好的划分。

工程深入

12 条结论 · 1 道例题

网表对象与割的定义

定义

划分结果是节点集合的互不重叠分组

网表划分为每个元胞选择一个所属块，并用块间连接代价评价分组；它确定逻辑归属，而不是直接给元胞安排版图坐标。12

成立条件 本页讨论固定网表的互斥划分，不包含允许逻辑复制的扩展问题。

机制

多端线网宜用超边保留整体连接

一个线网可同时连接多个元胞；以超边表示它们能直接判断该线网是否跨块。把多端网拆成若干两点边会引入权重选择，不能把图边割数直接当作原网表割网数。12

成立条件 两点线网可直接用普通图边表示。；比较算法结果前必须固定线网模型和割代价定义。

公式

加权割代价只累计跨块连接

普通加权图的割代价等于所有跨块边的权重之和；同块内部边不计入该次割。权重可以表达连接重要性，但不能未经说明同时当作面积或时延。12

Ccut=∑e 跨块w(e)C_{\mathrm{cut}}=\sum_{e\,\text{跨块}}w(e)
Ccut = Σ(e跨块) w(e)
Ccut
加权割代价，单位 1
w(e)
边e的指定权重，单位 1

成立条件 无向图，每条边在求和中只计一次。；边权非负；超图采用割网目标时应改用相应的线网指示函数。

面积约束与可行性

边界

面积平衡不等于元胞个数相等

元胞大小不同时，划分约束应累计元胞面积或其他资源权重；两块元胞数量相等，仍可能严重超出其中一块的容量。12

成立条件 权重按同一资源口径相加。；面积上界和允许不平衡范围由问题输入给定，不是所有芯片共用常数。

关联

无平衡约束的最小割不是平衡划分的答案

只追求少割边可能把绝大部分逻辑放在同一块中；受容量或平衡限制的划分必须先保持可行，再比较割代价。12

成立条件 不把源汇最小割的最优性直接外推为带面积平衡约束问题的全局最优性。

移动增益与迭代改进

机制

KL用跨块成对交换保持等大小分组

基本KL算法从两个等节点数的块中各选一个未锁定节点交换，在一轮内锁定已尝试的节点，避免立即撤销同一节点的试探。12

成立条件 限定基本等节点权重的二分形式；任意面积权重需要额外处理。

公式

KL交换增益需要扣除两端共有边

以外部边权减内部边权得到单节点移动增益后，交换a、b的增益为两者之和再减2c(a,b)，因为二者之间的边在交换前后仍跨块，不能被重复算作改善。12

D(a)=E(a)−I(a),g(a,b)=D(a)+D(b)−2c(a,b)D(a)=E(a)-I(a),\qquad g(a,b)=D(a)+D(b)-2c(a,b)
D(a)=E(a)−I(a)，g(a,b)=D(a)+D(b)−2c(a,b)
D(a)
节点a移到另一块时的割代价减少量，单位 1
E(a)
a连接另一块的边权和，单位 1
I(a)
a连接本块的边权和，单位 1
c(a,b)
节点a、b之间的边权，单位 1

成立条件 a、b位于不同块；无向非负边权图。；c(a,b)=0表示二者之间没有边；增益正值表示割代价降低。

例题：动手算一次教学假设，可复算

教学加权图中，某次交换前D(a)=5、D(b)=3，a与b之间边权为2，当前割代价12。交换增益和新割代价是多少？

已知

  1. 所有数值为教学假设、无量纲。
  2. a、b位于不同块，交换后仍满足容量约束。

步骤

  1. g=5+3−2×2=4，校正a、b共有边在单节点增益中的重复贡献。
  2. Cnew=12−4=8，正增益从旧割代价中扣除。
结果 交换增益4，新割代价8。

减少的是本次指定图模型的割代价。

不能外推到 不表示该交换满足实际芯片时序，也不证明全局最优。

机制

一轮试探后保留累计增益最大的前缀

KL可以在试探序列中暂时接受负增益移动，结束后只确认累计增益最大的正前缀；若没有正的累计改善，则不把整轮试探作为最终结果。12

成立条件 每步增益均相对于此前试探状态更新。；不能把各步独立增益在未更新的旧状态下直接相加。

机制

FM以单元移动支持面积不同的元胞

FM一次把一个元胞移到另一块，在满足平衡约束的候选中比较增益；它按超图割网变化更新关键线网，并在一轮结束后保留最好前缀。1

成立条件 限定采用超图割网目标和明确面积平衡约束的FM过程。

大规模网表与工程边界

机制

多级框架先聚合再逐级展开细化

多级划分先把联系紧密的元胞聚合成较小网表，在粗层求初始划分，再把解投影回更细层并增量改进；展开后的解仍需满足原网表约束。1

成立条件 聚合时保留成员资源权重和外部连接。；不使用教材中历史规模阈值作为当前工具的通用性能界限。

边界

迭代改进停止不代表证明全局最优

启发式划分只能说明在当前起点、移动集合和终止规则下找到了一个结果；一次KL或FM没有正改善，不排除其他初始划分或其他移动能得到更好解。12

成立条件 评价时同时报告可行性、割代价、初始条件与运行代价。

关联

多FPGA划分还受引脚和跨器件时延限制

把逻辑映射到多个FPGA时，逻辑容量并不是唯一限制；跨器件连接还消耗I/O资源并引入时延，单纯降低割网数量不能替代引脚和性能检查。1

成立条件 只讨论系统划分约束，不把旧器件的容量、价格或速度外推到当前产品。

出处

2 份资料 · 21 处引用
  1. 1

    超大规模集成电路物理设计：从图分割到时序收敛

    Andrew B. Kahng 等 著；于永斌, 张徐亮, 徐宁等 译

    查看这个来源 →
  2. 2

    EECS 357: Circuit Partitioning

    Hai Zhou

    查看这个来源 →