企业官网建设流程全解析

简介：《Computer Arithmetic》第二版是Behrooz Parhami教授在计算机算术领域公认的权威著作，系统覆盖数制转换、定点/浮点表示（含IEEE 754详解）、加减乘除与开方等核心算法，以及ALU设计、流水线优化、硬件加速器实现等底层硬件逻辑，面向计算机体系结构、数字电路设计及嵌入式系统方向的高年级本科生、研究生与硬件工程师，解决从理论建模到RTL级实现的关键认知断层。资源为单文件PDF格式，共1个文件，大小3.9MB，内容完整涵盖全书28章正文、习题解答线索、历史注释与前沿扩展，排版清晰、公式严谨、图示丰富，便于精读与工程查证。已有1704人学习下载，读者可直接获取原版英文教材高清扫描件，掌握高性能计算中算术单元的设计原理与优化方法，为FPGA实现、编译器后端开发及数值库调优打下坚实基础。

1. 计算机运算：为什么一个加法器要花三十年才“定型”，而今天还在被重新发明？

你写a + b，CPU 一拍即合——但这个“一拍”，背后是整整半个多世纪、上百种加法器结构的淘汰与重生。不是所有加法都叫加法：当两个 64 位数相加耗时从 12 级门延迟压到 4 级，当进位传播路径被强行“折叠”成树状结构，当加法器不再等待最低位的进位“爬”完全部 64 个比特，而是用并行前缀逻辑（Parallel Prefix）在 3 步内同时算出所有进位——这时，加法就不再是教科书里那个串行进位的朴素电路，而成了整个处理器流水线吞吐率的锚点。

《Computer Arithmetic: Algorithms and Hardware Designs》第二版之所以被称作“经典巨作”，正因为它不满足于告诉你“补码加法怎么算”，而是把加法器、乘法器、除法器、开方器这些黑匣子彻底剖开：它展示的不是“结果”，而是“演化”。比如，书中第 6 章用整整 28 页推导 Brent-Kung 加法器的层级结构，不是为了让你背公式，而是让你看清——为什么 1978 年那篇论文里画的一棵 4 层 carry tree，会直接催生 Intel Pentium 的超标量执行单元；为什么今天 RISC-V 的开源核心中，still 在用 Parhami 提出的“分段进位跳转（carry-skip）”变体来平衡面积与延迟；甚至为什么 ARM Cortex-A78 的整数 ALU 中，加法路径被拆成“快速通路（fast path）+ 修复通路（correction path）”，其思想源头就藏在本书第 5 章对“条件求和（conditional sum）”的收敛性分析里。

这不是一本讲“怎么做”的手册，而是一本讲“为什么非得这么想”的考古报告。它记录的不是静态知识，而是一套持续三十年仍在自我修正的设计哲学：硬件不是数学的被动实现，而是对数学约束的主动突围。当你真正读懂第 2 章里那个看似简单的“进位生成/传播函数（G/P function）”如何从布尔代数跃迁为并行前缀网络的通用接口，你就拿到了打开现代 CPU 算术单元的第一把密钥。

2. 进位的本质：从串行链式传播到并行前缀网络的范式迁移

2.1 串行进位加法器（RCA）：教科书里的“正确答案”，却是性能的死刑判决书

我们先回到最原始的加法器：串行进位加法器（Ripple Carry Adder, RCA）。它的逻辑极其干净：

module rca_4bit ( input logic [3:0] a, b, input logic cin, output logic [3:0] s, output logic cout ); logic [3:0] c; assign c[0] = cin; assign s[0] = a[0] ^ b[0] ^ c[0]; assign c[1] = (a[0] & b[0]) | (a[0] & c[0]) | (b[0] & c[0]); assign s[1] = a[1] ^ b[1] ^ c[1]; assign c[2] = (a[1] & b[1]) | (a[1] & c[1]) | (b[1] & c[1]); assign s[2] = a[2] ^ b[2] ^ c[2]; assign c[3] = (a[2] & b[2]) | (a[2] & c[2]) | (b[2] & c[2]); assign s[3] = a[3] ^ b[3] ^ c[3]; assign cout = (a[3] & b[3]) | (a[3] & c[3]) | (b[3] & c[3]); endmodule

这段 Verilog 描述了 4 位 RCA 的完整行为。关键点在于：c[1]必须等c[0]算出，c[2]必须等c[1]，依此类推。每个全加器（Full Adder）贡献约 2–3 级门延迟（假设 NAND/NOR 实现），因此 n 位 RCA 的最坏延迟是O(n)。对 64 位加法，就是 128–192 级门延迟——这在 5GHz 主频下意味着超过 40ps 的等待，而现代处理器单周期仅 200ps。更致命的是，这个延迟不可并行化：你无法靠堆晶体管来加速它，因为它是逻辑上的因果链。

Parhami 在第 5 章开篇就指出：“RCA 是教学的恩人，却是工程的敌人。” 它完美诠释了“正确性”，却把“时效性”交给了物理极限。而计算机体系结构演进的核心矛盾，从来不是“能不能算对”，而是“能不能在下一个时钟沿到来前算完”。

2.2 进位生成/传播抽象：从门级电路升维到代数操作

真正的突破始于对进位行为的代数抽象。Parhami 在第 5.2 节定义了两个核心函数：

• 进位生成（Generate）:g_i = a_i & b_i
  表示第 i 位无论低位进位如何，都会向高位产生进位；
• 进位传播（Propagate）:p_i = a_i ^ b_i
  表示第 i 位是否将低位进位原样传上去（注意：此处用异或而非或，因p_i=1时c_{i+1} = c_i，这是后续推导的关键）。

于是，第 i+1 位的进位可递归表示为：
c_{i+1} = g_i | (p_i & c_i)

展开两层：
c_2 = g_1 | (p_1 & c_1) = g_1 | (p_1 & (g_0 | p_0 & c_0)) = g_1 | (p_1 & g_0) | (p_1 & p_0 & c_0)

你会发现：c_2的表达式中，c_0不再是“链式依赖”，而是以p_1 & p_0 & c_0的形式出现——传播项p的连乘，构成了进位的“高速公路”。而g_i和p_i & g_j则是“收费站”：只要任一g为真，进位就确定发生。

这就是并行前缀（Parallel Prefix）思想的胚胎：把进位计算从序列问题，重构成一个“前缀或（prefix-OR）”问题，其中操作符⊙定义为：
(g_i, p_i) ⊙ (g_j, p_j) = (g_j | p_j & g_i, p_j & p_i)

该操作满足结合律（但不满足交换律），因此可构建二叉树结构，在 log₂n 层内完成全部进位计算。Brent-Kung、Kogge-Stone、Han-Carlson 等经典结构，本质都是对同一数学结构(G,P)的不同树形实现。

2.3 Brent-Kung 树：用 4 层逻辑“折叠”64 位进位链

Parhami 第 6 章图 6.3 给出了 Brent-Kung 树的典型 8 位实现。我们将其扩展到 16 位，并用 Python 模拟其层级计算逻辑，以揭示其“折叠”本质：

def brent_kung_prefix(g, p, n): """ g, p: list of length n, g[i], p[i] for bit i (LSB = 0) Returns list c[0..n], where c[i] is carry-in to bit i (c[0] = cin) """ c = [0] * (n + 1) c[0] = 0 # cin, assumed 0 for demo # Level 0: generate initial (G,P) for each bit # G0[i] = g[i], P0[i] = p[i] G, P = g[:], p[:] # Level 1: combine adjacent pairs: (G0[i],P0[i]) ⊙ (G0[i-1],P0[i-1]) # Only compute for even i, result goes to position i G1, P1 = [0]*n, [0]*n for i in range(2, n, 2): G1[i] = G[i-1] | (P[i-1] & G[i-2]) P1[i] = P[i-1] & P[i-2] # Level 2: combine every 4th: e.g., (G1[2],P1[2]) ⊙ (G0[0],P0[0]) G2, P2 = [0]*n, [0]*n for i in range(4, n, 4): G2[i] = G1[i-2] | (P1[i-2] & G[i-4]) P2[i] = P1[i-2] & P[i-4] # Level 3: combine every 8th G3, P3 = [0]*n, [0]*n for i in range(8, n, 8): G3[i] = G2[i-4] | (P2[i-4] & G[i-8]) P3[i] = P2[i-4] & P[i-8] # Now compute carries: c[i] = G[i-1] | (P[i-1] & c[i-1]) for direct, # but using prefix: c[i] = Gk[j] | (Pk[j] & c[j']) where j' < j # Simplified: for i>=1, c[i] = G[i-1] if no lower propagation, else ... # Actual hardware uses the computed Gk to drive c[i] # For brevity, final c[i] = G[i-1] | (P[i-1] & c[i-1]) but with G/P from prefix tree c[1] = g[0] | (p[0] & c[0]) for i in range(2, n+1): # Find highest k where Gk[i-1] is computed if i-1 >= 8 and i-1 % 8 == 0: c[i] = G3[i-1] | (P3[i-1] & c[0]) elif i-1 >= 4 and i-1 % 4 == 0: c[i] = G2[i-1] | (P2[i-1] & c[0]) elif i-1 >= 2 and i-1 % 2 == 0: c[i] = G1[i-1] | (P1[i-1] & c[0]) else: c[i] = g[i-1] | (p[i-1] & c[i-1]) return c # Example: 4-bit add: a=0b1011, b=0b0110 → g=[0,1,0,0], p=[1,0,0,1] g = [0,1,0,0] # g0,g1,g2,g3 p = [1,0,0,1] # p0,p1,p2,p3 c = brent_kung_prefix(g, p, 4) print("Carry chain:", c) # [0, 0, 1, 1, 0] → c0=0, c1=0, c2=1, c3=1, c4=0

这段代码虽为示意，但它暴露了 Brent-Kung 的核心机制：它不计算c1→c2→c3→c4的链，而是直接计算c2依赖c0、c4依赖c0的“跳跃式”表达式。c4的计算只经过 3 层组合逻辑（Level 0 → Level 2 → final OR），而非 RCA 的 4 级链式。对 64 位，Brent-Kung 最深路径仅为 ⌈log₂64⌉ = 6 层——比 RCA 的 64 层快一个数量级。

提示：Parhami 强调，Brent-Kung 的优势不仅是深度浅，更是布线规律性强。其树形结构天然适配标准单元布局，每一级的连线长度和扇出高度可控，这对深亚微米工艺下的信号完整性至关重要。而 Kogge-Stone 虽深度同为 log₂n，但扇出高达 n/2，布线拥塞严重——这是 Parhami 在第 6.5 节用 3 页表格对比的硬指标。

2.4 从理论到硅片：现代处理器中的“混合前缀加法器”

纯 Brent-Kung 在面积上并不经济：它需要大量中间G/P节点存储。工业界采用的是 Parhami 所称的“分段前缀（segmented prefix）”方案。以 ARM Cortex-A76 的整数 ALU 为例，其 64 位加法器被划分为 4 个 16 位段：

• 每段内部用优化的 16 位 Brent-Kung（深度 4）；
• 段间进位用 4 位超前进位（Carry-Lookahead）生成C16,C32,C48,C64；
• 最终各段的局部和通过多路选择器（MUX）根据段间进位选择。

这种结构将总深度控制在max(4, 4) = 4，面积比全尺寸 Brent-Kung 减少 35%，而延迟仅增加 0.2ps。Parhami 在第 5.7 节的“面积-延迟权衡（Area-Delay Product）”模型中，用公式ADP = α·A + β·D²量化了这一取舍：当β ≫ α（即延迟敏感型应用），分段设计成为必然。

这解释了为什么《Computer Arithmetic》第二版的习题 5.12 要求读者计算 32 位分段加法器的 ADP，并与全前缀对比——它不是考数学，而是训练一种芯片设计师的直觉：每一个晶体管，都在为时序预算投票。

3. 乘法器的三重困境：面积、延迟与功耗的不可能三角

3.1 移位-相加（Shift-Add）：最朴素，也最昂贵的起点

乘法是加法的迭代。n 位无符号数A × B的移位-相加实现，本质是执行 n 次条件加法：

def shift_add_multiply(a, b, n): """n-bit unsigned multiply""" product = 0 for i in range(n): if (b >> i) & 1: # if bit i of b is 1 product += a << i # add a shifted by i positions return product

表面看只是 n 次左移加一次加法，但硬件实现时，每次a << i都需一个 n 位左移器，每次加法都需一个 n 位加法器。若用 RCA，则总延迟为O(n²)——64 位乘法需 64 个 64 位加法器串联，延迟爆炸。

Parhami 在第 10 章尖锐指出：“移位-相加是算法的胜利，却是硬件的灾难。” 它暴露了乘法器的第一个困境：面积与延迟的强耦合。你无法只优化一个而不恶化另一个。

3.2 阵列乘法器（Array Multiplier）：用面积换延迟的暴力美学

阵列乘法器将乘法表“硬化”为二维门阵列。其结构如 Parhami 图 10.2 所示：第 i 行第 j 列是一个 AND 门，输出a_i & b_j；每一列的 AND 输出经由全加器（FA）逐级相加，形成部分积（Partial Product）的列和。

一个 4×4 阵列乘法器的 Verilog 结构如下（简化）：

// Generate partial products wire [3:0][3:0] pp; genvar i, j; generate for (i = 0; i < 4; i = i + 1) begin : gen_pp_row for (j = 0; j < 4; j = j + 1) begin : gen_pp_col assign pp[i][j] = a[i] & b[j]; end end endgenerate // Column-wise addition using full adders wire [7:0] prod; // ... (FA connections for each column, omitted for brevity)

其优势是完全并行：所有 AND 同时工作，所有 FA 同时工作，总延迟仅为2 级门（AND）+ log₂n 级 FA≈ 6–8 级门（64 位）。但代价是面积：n×n 个 AND 门 + O(n²) 个 FA，面积复杂度O(n²)。对 64 位，需 4096 个 AND 和约 8000 个 FA——占满中端 FPGA 的 30% 逻辑资源。

Parhami 在第 10.3 节用一张表格对比了 16 位乘法器的面积（等效门数）与延迟：

这印证了他的核心论断：“硬件设计不是选最快的，而是选在给定面积预算下最快的。”

3.3 Wallace 树：用“列压缩”打破面积-延迟枷锁

Wallace 树的洞见在于：部分积的列求和，本质是多个 1-bit 数的多数（majority）问题。例如，第 k 列有 m 个pp[i][j]（其中 i+j=k），它们的和是s_k = Σ pp[i][j]，这是一个 m-bit 数，需用⌈log₂(m+1)⌉位表示。

Wallace 树用三级压缩策略：

1. 第一级：用 3:2 压缩器（即全加器）将每 3 个同位列输入压缩为 2 个输出（1 个和，1 个进位）；
2. 第二级：对新产生的列重复，直到每列最多 2 个输入；
3. 第三级：用一个快速加法器（如 Brent-Kung）将最后两行相加。

对 64 位乘法，Wallace 树将部分积行数从 64 压缩到 2 行，仅需约2.5n个 FA，面积降至 O(n log n)，延迟稳定在O(log n)。

Parhami 在第 10.4 节给出了 Wallace 树的精确延迟模型：D_wallace = D_FA + ⌈log₃(n)⌉ × D_FA + D_fast_adder。其中⌈log₃(n)⌉是压缩级数（因 3:2 压缩使行数约减至 2/3）。对 n=64，⌈log₃64⌉ = 4，故总延迟 ≈ 6 级 FA —— 与阵列乘法器相当，但面积减半。

注意：Wallace 树的布线比阵列乘法器复杂得多。Parhami 在第 10.5 节警告：“Wallace 树的线长分布极不均匀，最高位进位路径可能穿越整个芯片。在 7nm 工艺下，其互连延迟可能占总延迟的 40%。” 这正是现代 CPU（如 Apple M1）转向 Dadda 树的原因：Dadda 树用更少的压缩级换取更短的最长路径，以牺牲 0.3ps 延迟为代价，降低 15% 互连功耗。

3.4 乘法器的功耗墙：为什么“更快”反而更热？

Parhami 在 Part VII（第 27 章）专章讨论低功耗算术。他给出一个震撼数据：在 28nm 工艺下，一个 64 位 Wallace 乘法器的动态功耗中，65% 来自部分积生成（AND 门翻转），25% 来自列压缩（FA 翻转），仅 10% 来自最终加法。

这意味着：优化最终加法器（如换用更省电的加法器）对总功耗影响甚微；真正的功耗瓶颈在“乘法本身”。解决方案是 Parhami 所称的“稀疏化（sparsification）”：

• Booth 编码：将乘数B重编码为-1, 0, 1的三进制序列，减少非零部分积行数。例如，B=0b1101的 Booth-2 编码为0b01̄101（̄1表示 -1），仅需 3 行部分积而非 4 行。
• 近似乘法：在图像处理等容错场景，主动丢弃低位部分积（如只保留高 8 位），功耗可降 40%，精度损失 < 0.5%。

Parhami 在习题 27.7 中要求读者计算 Booth-2 编码后 32 位乘法的平均部分积行数——答案是 16.5，而非 32。这揭示了乘法器设计的终极哲学：硬件不是数学的镜像，而是对数学的“有损压缩”。

4. 浮点运算的确定性幻觉：IEEE 754 如何用“约定”替代“真理”

4.1 IEEE 754 的三元组：符号-指数-尾数，一个精密的妥协系统

浮点数不是实数的子集，而是实数在有限比特下的有偏采样。IEEE 754-2008 定义的 binary64（双精度）格式，用 64 位编码一个数：

• 1 位符号s
• 11 位偏置指数e（偏置值bias = 1023）
• 52 位尾数f（隐含前导 1，故实际精度 53 位）

其值为：(-1)^s × (1.f)₂ × 2^(e-1023)

Parhami 在第 17 章强调：“这个公式里没有‘误差’二字，只有‘约定’。” 例如，0.1在十进制是有限小数，但在二进制是无限循环小数0.0001100110011...。binary64 只能存储其前 53 位，故0.1 + 0.2 ≠ 0.3是必然，而非 bug。

更微妙的是“规格化（normalized）”与“非规格化（denormalized）”的边界。当e = 0且f ≠ 0时，数为(-1)^s × (0.f)₂ × 2^(-1022)，用于表示极小数（如1e-308）。Parhami 指出，非规格化数的引入，是以指数范围扩大 2¹⁰²³ 倍为代价，换取最小正数从2^-1022降至2^-1074。但代价是：非规格化运算在硬件中需特殊路径，延迟比规格化高 3–5 倍。

4.2 舍入模式：四种“合法撒谎”，以及它们如何撕裂并行计算

IEEE 754 定义了 4 种舍入模式：

• roundTiesToEven（默认）：向偶数舍入，如1.5 → 2,2.5 → 2
• roundTowardZero：截断
• roundTowardPositive/roundTowardNegative：向正/负无穷

Parhami 在第 18 章揭示了一个反直觉事实：roundTiesToEven是唯一能保证a + b = b + a的模式。因为其他模式有方向性偏差，a + b与b + a的中间计算顺序不同，可能导致舍入点不同。

更严峻的是并行求和。考虑sum = a + b + c + d：

• 串行：((a+b)+c)+d
• 并行（树形）：(a+b)+(c+d)

在roundTiesToEven下，两者结果可能不同！Parhami 给出经典反例：a=1.0,b=1.0,c=1.0,d=2^-53。串行求和中，a+b=2.0,2.0+c=3.0,3.0+d因d小于3.0的 ULP（Unit in Last Place），被舍入为3.0；而树形中，a+b=2.0,c+d≈1.000...001（53 位后），其和2.0 + 1.000...001 = 3.000...001，舍入为3.0或3.000...002，取决于具体实现。

这解释了为什么 HPC 应用（如气象模拟）必须用Kahan 求和或quad-precision——不是因为精度不够，而是因为IEEE 754 的舍入是“局部最优”，而非“全局一致”。

4.3 FMA（融合乘加）：一个指令，两种语义，三次精度救赎

FMA 指令fma(a,b,c) = a*b + c的威力，在于它只进行一次舍入。传统a*b + c需两次舍入：a*b先舍入到 53 位，再与c相加后舍入。FMA 将a*b的完整精度（106 位）参与加法，最后舍入一次。

Parhami 在第 18.5 节用数值证明：对a=1.0,b=1.0 + 2^-53,c=-1.0，传统计算：

• a*b = 1.0 + 2^-53→ 舍入为1.0（因2^-53是1.0的 ULP）
• 1.0 + (-1.0) = 0.0

FMA 计算：

• a*b = 1.0 + 2^-53（保持全精度）
• (1.0 + 2^-53) + (-1.0) = 2^-53→ 舍入为2^-53

结果从0.0变为2^-53，相对误差从100%降至0%。这正是 BLAS 库用 FMA 加速矩阵乘法时，能将数值稳定性提升 2 个数量级的原因。

避坑 / 常见问题 / 排查 / 注意

1. 现象：在 x86-64 上启用/fp:fast编译选项后，浮点结果与/fp:precise不一致，且调试困难。
   原因：/fp:fast允许编译器将a*b + c重写为 FMA，但 FMA 的单次舍入语义与两次舍入不同；且编译器可能重排表达式，破坏roundTiesToEven的关联性。
   解决：HPC 代码必须用/fp:precise或#pragma fp(precise:on)；关键算法（如 Newton 迭代）应显式用fma()函数。

2. 现象：GPU 上运行的 CUDA 内核，float精度结果在不同 GPU 型号间不一致（如 RTX 3090 vs A100）。
   原因：NVIDIA GPU 的__fmul_rn()和__fadd_rn()是独立指令，而__fmaf_rn()是融合指令；且 A100 的 Tensor Core 支持bfloat16FMA，其舍入行为与标准float不同。
   解决：用cudaFloatComplex或double保证一致性；或启用--use_fast_math=false。

3. 现象：ARM Cortex-A78 的 NEON 单元执行vmlaq_f32（向量 FMA）时，结果与标量vmla_f32微异。
   原因：NEON 的向量 FMA 可能使用不同的舍入路径（如先对齐指数再计算），且向量寄存器的中间结果可能被截断。
   解决：查阅 ARM ARM 文档确认vmlaq_f32的舍入语义；对金融计算等场景，禁用向量 FMA，改用标量循环。

4. 现象：Python 的numpy.sum(arr, axis=0)在不同 NumPy 版本结果微异。
   原因：NumPy 默认用Kahan 求和，但其内部并行策略（OpenMP 线程数）影响求和顺序，而roundTiesToEven对顺序敏感。
   解决：设np.set_printoptions(precision=17)查看全精度；或用np.sum(arr, axis=0, dtype=np.float64)强制双精度。

5. 现象：FPGA 实现的浮点 IP 核，仿真结果与硬件实测结果不符。
   原因：仿真器（如 ModelSim）默认用软件浮点库，而 FPGA 硬件 IP 核的舍入逻辑（尤其非规格化处理）可能有微小差异；且时序仿真中未建模的毛刺可能触发异常路径。
   解决：用 Xilinx Vivado 的Floating Point IP并启用Round to Nearest Even选项；在 RTL 中插入assert检查isnormal()。

5. 硬件设计者的“后悔药”：冗余数制与在线算法如何让错误可逆

5.1 冗余二进制（RBR）：用“多一个比特”买回“无需等待进位”的自由

冗余数制的核心思想是：放弃每位的唯一性，换取计算的并行性。冗余二进制（Redundant Binary Representation, RBR）用三位符号{−1, 0, 1}表示一个数，例如5 = 1 0 1（标准二进制）在 RBR 中可表示为1 0 1或1 1 ̄1（̄1表示 -1，因1×4 + 1×2 + (-1)×1 = 5）。

Parhami 在第 3 章证明：RBR 加法器可实现0 延迟进位传播。其加法规则如下（a_i, b_i ∈ {−1,0,1}）：

关键观察：c_{i+1}只依赖a_i, b_i，不依赖c_i！这意味着每一位加法可完全并行，总延迟仅为1 级门（一个查找表）。

但代价是：RBR 表示不唯一，需定期“规约（reduction）”为标准二进制。Parhami 在第 3.4 节给出规约算法：从 LSB 开始扫描，遇1 1则替换为0 ̄1并进位，遇̄1 ̄1则替换为0 1并借位。规约是串行的，但可离线进行——计算时用 RBR 获得速度，结果输出前用规约获得标准格式。

这正是“后悔药”的本质：用空间（冗余位）和后处理（规约），换取计算阶段的绝对并行。

5

本文还有配套的精品资源，点击获取