跳到正文
半导体开放世界

并行前缀加法器

Parallel-Prefix Adders

利用有序组摘要的结合律并行形成全部进位前缀，并按层数、扇出和布线共同选择拓扑。

进阶出处 2 本教材
报告问题

速览

约 1 分钟

把连续位组压缩成G、P摘要，再用不同的有序树共享中间结果；少层数并不是无代价的最快保证。

系统理解

约 2 分钟

前缀加法器保留从高到低的位组顺序，只用结合律改变括号和共享方式。Kogge–Stone、Brent–Kung、Sklansky与稀疏结构形成不同层数、扇出和互连分布。理论合并深度和点操作位置计数需要与实际库映射、输入到达和物理寄生区分。

在进位传播契约之后学习全部前缀的共享计算，再与综合、全局布线和详细布线的物理约束衔接。

关键参数

关键参数
参数单位含义
组合顺序与区间—高位在左、低位在右的相邻连续区间
基数与合并层数—区分每层合并组数、最大深度及前后处理
扇出和连线—可能抵消减少逻辑层数所得收益

常见误区

  • 点操作可交换高低位次序。
  • 对数级进位意味着延迟与位宽完全无关。
  • Kogge–Stone在任何工艺和位宽下一定最快。

工程深入

12 条结论 · 1 道例题

组摘要与前缀代数

定义

一个位组可用输入进位到输出进位的函数摘要

连续位组可由一对G、P描述：G表示无外来进位也产生输出进位，P表示该组可传递外来进位。在本页异或传播约定下，这个摘要保留了组合相邻位组所需的进位信息，而不保存每个内部和位。12

成立条件 位组连续且高低位次序明确。；组摘要用于进位功能，不替代内部和位的求和运算。

公式

相邻摘要按高位在左低位在右合并

设H是高位组、L是紧邻的低位组，高组自身产生进位，或者高组传播低组产生的进位时，合并组才产生进位；只有两组都传播时，合并组才传播。合并次序必须与算术位权相符。12

(GH,PH)∘(GL,PL)=(GH∨(PH∧GL),  PH∧PL)(G_H,P_H)\circ(G_L,P_L)=\bigl(G_H\lor(P_H\land G_L),\;P_H\land P_L\bigr)
(GH,PH) ∘ (GL,PL) = (GH ∨ (PH ∧ GL), PH ∧ PL)
GH、PH
高位组的产生、传播摘要，单位 1
GL、PL
相邻低位组的产生、传播摘要，单位 1
∘
高位在左、低位在右的组摘要组合运算，单位 1

成立条件 Gi=Ai∧Bi、Pi=Ai⊕Bi。；∨、∧为布尔操作；H和L为连续不重叠的高低位组。

边界

结合律允许改括号但不允许颠倒位组

组摘要组合等价于有序进位函数的复合，因此可改变括号形成不同树，却不能交换高位组和低位组。例如高组取消、低组产生时整体取消，颠倒两组则整体产生；这不是同一个算术电路。12

成立条件 按本页从高到低书写的算子约定。；保留每个操作数的位区间，不能仅凭树外观重排叶节点。

机制

全部前缀计算不同于只归约最高位组

普通归约树只需得到整个字的一个摘要，而加法器还要得到各个低位起始的前缀，供中间各和位使用。并行前缀网络共享这些重叠区间的组合结果，不能只把最高位树复制成一个无中间输出的树。12

成立条件 最终外部Cin仍需按接口合入前缀。；本页0起始位号与部分教材把Cin计为第0列的画法不同，按功能对应。

层级与资源

边界

对数合并深度只描述树内组合级数

基2树每经过一轮可把已覆盖区间扩大，平衡的前缀路径可用对数轮次覆盖整字。但总加法延迟还包括位传播产生、最终求和及连线负载，不能把log2N直接写成真实门数或实际时间。12

成立条件 基2组合的理想层级讨论，非所有前缀拓扑都具有同样最大深度。；没有假定所有组门都等延迟或无布线。

公式

稠密Kogge–Stone的合并位置可逐层计数

在每层跨距按1、2、4逐倍增加、为每个有效终点设置一个合并位置的标准稠密基2网络中，可以将每层有效位置数求和。该计数不含首级PG、末级求和、缓冲与物理复制，也不把灰色单元简化自动算作新增收益。12

M=∑k=0L−1(N−2k)=NL−N+1,L=log⁡2NM=\sum_{k=0}^{L-1}(N-2^k)=NL-N+1,\qquad L=\log_2 N
M = Σ(k=0…L−1)(N − 2ᵏ) = NL − N + 1；L = log₂N
N
按该标准拓扑组织的数据位宽，单位 1
L
基2合并轮数，单位 1
M
组摘要合并位置数量，单位 1

成立条件 N=2的整数幂，L=log2N。；计数对象是标准稠密拓扑的组摘要合并位置，不是晶体管数或最终版图单元数。

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

按标准稠密基2Kogge–Stone拓扑计数16位网络的组摘要合并位置。

已知

  1. N=16，L=log₂16=4。
  2. 不含PG预处理、求和、Cin处理、缓冲及技术映射变化。

步骤

  1. N−1=15，N−2=14，N−4=12，N−8=8，按四层跨距分别数有效合并位置。
  2. M=15+14+12+8=49，逐层累加。
  3. NL−N+1=16×4−16+1=49，用等比数列化简式交叉核对。
结果 该理想稠密网络含49个组摘要合并位置。

少量合并层数可以伴随较多并行硬件，层数和资源不是同一个指标。

不能外推到 不是综合后单元数、晶体管数、面积或延迟实测。

拓扑取舍

机制

Brent–Kung以额外层次减少树内分发压力

Brent–Kung先形成分级的大区间摘要，再补齐中间前缀；在标准基2结构中，它以比最小深度树更多的级数，换取受控扇出及较少的全宽横向连接需求。1

成立条件 讨论标准拓扑，不给未经实现的固定面积比例。；缓冲、尺寸与布局会改变最终门数和时序。

机制

Sklansky减少层数但使部分摘要驱动较多终点

Sklansky按分而治之方式快速形成大组前缀，某些组结果必须同时分发到更多列。这些高扇出点可能需要增强驱动或缓冲，因此同样的理想合并层数不表示与其他树拥有相同物理延迟。1

成立条件 以标准基2树的分发结构作比较。；不能把某一级扇出数当成全网络每个单元的共同负载。

机制

稀疏前缀把部分组内求和留给局部候选

稀疏树只在部分位组边界计算全局进位，同时在局部组预计算候选和，再由边界进位选择。它把全局摘要网络与局部选择结合，减少全局进位端点的同时保留额外的局部硬件和等待关系。1

成立条件 必须给出组宽和选择方式，不能仅删去前缀端点而不补内部结果。；组内预计算与边界进位的到达仍需平衡。

边界

提高组合基数会同时加重单级逻辑

一层合并更多相邻组可减少总层数，但单个组门的扇入、堆叠或内部逻辑更加复杂。高阶结构是否更快取决于电路系列、输入负载和实际表征，不能只按较少层数判断。12

成立条件 高阶表示每次组合的相邻组数，不是数据位宽。；不将特定多米诺实现的收益推广至所有静态标准单元库。

实现与检查

机制

只需最终产生时可以不继续计算组传播

在网络的某个终点，如果后续只使用组产生来得到进位而不再需要组合更高区间，该位置可以省去组传播输出。是否可省取决于后续使用关系，不能在仍需继续合并的中间位置随意丢掉传播信息。1

成立条件 对应常见灰色单元只计算G、黑色单元计算G和P的表示。；单元极性和库映射由实现决定，本条只限定必要输出。

关联

低逻辑深度仍需面对真实扇出和横向互连

前缀网络增加并行组合以缩短依赖深度，代价可表现为更多节点、长连线或局部高负载。应在相同接口和工艺条件下比较放置布线后的寄生与时序，而不是以树名或理论层数给出全局最快排名。12

成立条件 候选之间保持位宽、Cin要求和输入输出时序边界一致。；不将教材中特定时代的版图或功耗数值当成当前设计指标。

出处

2 本教材 · 20 处引用
  1. 1

    CMOS超大规模集成电路设计（第4版）

    查看这个来源 →
  2. 2

    数字集成电路：电路、系统与设计（第2版）

    Jan M. Rabaey, Anantha Chandrakasan, Borivoje Nikolić

    查看这个来源 →