加法运算与ALU
加法运算与ALU
复习定位
CPU的运算器(ALU)不是魔法——它是一个组合逻辑电路。加法运算用全加器和进位电路实现。补码使加减法可用同一个加法器——不必为减法设计单独电路。标志寄存器(ZF/CF/OF/SF)是ALU运算后再组合状态指示的一组字段位——条件跳转指令(jz/jb/jo/js)实际检查的就是这些标志位。逆向分析时看到test edi, edi; jz——实际就是ALU做了按位与运算——ZF被置位时则jz跳转。
全加器的级联——行波进位加法器
一位全加器接收三个输入——A、B、进位输入Ci——产生两个输出：和S、进位输出Co。真值表确定了$S = A⊕B⊕Ci$、$Co = (A∧B) ∨ (A∧Ci) ∨ (B∧Ci)$——输入三位组合后唯一确定输出。n位行波进位加法器由n个全加器级联而成——第i位的进位输出Co连接到第i+1位的进位输入Ci。优点是电路非常规整——所有加法器单元完全相同——容易通过EDA工具自动布局。致命缺点是延迟随位数线性增长——32位加法需要等从第0位的C0经过32级全加器到达第31位——进位必须从最低位一直传播到最高位。在最坏情况下(C0=1且所有Ai和Bi都有效)进位传播需要经过32×2门级延迟——已达数百皮秒——限制了CPU频率。
超前进位加法器(CLA)
核心思想：每一级的进位可以直接由输入计算——不需要等低位的进位结果。定义两个辅助量：$G_i = A_i ∧ B_i$(进位生成——不管进位输入Ci是否为1——Ai和Bi本身都是1时必然产生进位)和$P_i = A_i ⊕ B_i$(进位传播——如果Ai或Bi中一个为1、进位输入Ci为1则产生进位)。进位输出$C_{i+1} = G_i ∨ (P_i ∧ C_i)$。展开递归：$C_1 = G_0 ∨ (P_0 ∧ C_0); C_2 = G_1 ∨ (P_1 ∧ G_0) ∨ (P_1 ∧ P_0 ∧ C_0)$……每一级的进位表达式被展开为两级与或式——不必等待低级的进位输出。因此CLA的延迟约4门级——远小于行波进位加法器的32×2=64门级。代价是用更多逻辑门实现——n位CLA需约O(n²)的门级数——n很大时面积巨大。因此实际设计中采用多级CLA组合——16位级联用超前进位、4位一组CLA、组间并行进位——平衡延迟与面积。
ALU的内部组织
一个典型的ALU包含加法器(Adder)——用于加减和比较。逻辑运算单元——用于AND/OR/XOR/NOT。移位器(Shifter)——用于算术移位/逻辑移位/循环移位。多路选择器——根据操作码选择将哪个结果写入输出。输入可能通过前级从寄存器文件取出操作数。ALU的核心特性是组合逻辑——输出只取决于当前输入组合——ALU没有内部状态(flag寄存器虽然看起来像状态但只是一个依赖ALU结果的组合输入、由后面一级寄存器在下一个时钟沿锁存)。
加减法的统一——补码实现
减法$a-b$在ALU中间变为$a + (b的补码)$。补码$=取反+1$——ALU加一个减法标示Sub——Sub=1时，将b的所有位取反(XOR Sub)并将进位输入C0设为1(取反+1完成补码转换)——Sub=0时正常加法。几乎相同的逻辑门数量——简单的加法器也可以完成减法——不需要在ALU后方放置独立的减法器。这在任何ISA级反汇编中的减法指令都是在二进制层面通过补码加法完成的。
标志位的产生
ZF(零标志)：ALU结果的所有位均为0——通过一个多输入NOR门对所有结果位取非(全是0→ZF=1)。SF(符号标志)：结果最高位——有符号数解释下的符号位。CF(进位/借位标志)：无符号加法结果超出位的进位输出——也是无符号减法向高位借位的检测条件。OF(溢出标志)：$C_{n-1}异或C_n$——即最高有效位的进位输入与进位输出不一致。因为$C_n$+进位的极性反映了符号位是否被错误地改变了。PF(奇偶标志)：结果的低8位中1的个数为偶数则置1,奇数则0——主要用于RS-232通信的老式数据校验——现在很少使用。
cmp a,b的实际逻辑是ALU做a−b的补码加法——结果丢弃只更新标志位。jz label检查ZF——ZF=1说明a−b=0即a等于b。jb label检查CF——CF=1说明a无符号小于b(减法产生了借位)。jg label在x86上通过检查ZF=0且OF=SF来综合判断有符号的a>b。
ALU的算术与逻辑分类
ALU能执行的运算被控制器通过操作码选择。典型的ALU功能列表：
算术运算：加法(ADD,ADDC含进位)、减法(SUB,SUBB含借位)、加1(INC)、减1(DEC)、取负(NEG——补码)、比较(CMP——减法不写结果只设标志)。
逻辑运算：与(AND)、或(OR)、异或(XOR)、取反(NOT)。AND常用于消去特定位(掩码)、OR常用于置位特定位、XOR常用于翻转特定位——而且XOR same_reg,same_reg在x86上因编码短于一条显式的"寄存器归零"被编译器高频用于寄存器清0。
移位运算：算术左移(SAL)——整体左移低位补0——相当于乘2(但有符号溢出时OF置位且符号可能变化)。算术右移(SAR)——有符号右移高位补符号位——相当于除2但有向负取整现象——负奇数右移1位时结果会比除以2向下取绝对值的小一个单位。逻辑右移(SHR)——无符号右移高位补0。循环移位(ROL/ROR)——移出的位补到另一端的空位上——常见于密码学中位混淆。
不同运算通过ALU内部的多路选择器从不同功能单元的输出选通到ALU输出。
标志寄存器的完整结构
x86-64的RFLAGS寄存器不是单纯由ALU产生的——但条件跳转最常检查的位正是ALU输出的组合。
| 标志 | 含义 | 置位条件 | 条件跳转 |
|---|---|---|---|
| CF | 进位 | 加法最高位进位或减法借位 | jb/ja(无符号) |
| PF | 奇偶 | 低8位1的个数偶数 | jp/jnp |
| ZF | 零 | 运算结果全0 | je/jz/ne/jnz |
| SF | 符号 | 结果最高位 | js/jns |
| OF | 溢出 | 有符号运算溢出 | jo/jno |
test rax, rax; jz label组合：test=AND运算不写目标只设标志。rax=0→全0→ZF=1→jz跳转。这是x86判断寄存器为0的标准模式——test不改变rax的值。
乘法运算的硬件实现
乘法在硬件中通常不使用加法器的级联加法实现——而是用一个移位器+加法器的组合完成。最简单的硬件乘法器模拟竖式算法：乘数逐位扫描——如果该位为1则将被乘数左移对应位数后累加。32位乘法需要最多32个时钟周期加32个加法运算。现代CPU用Booth编码将乘数的连续1序列合并为更少的加减法操作——减少了部分积的数量——再使用Wallace树(进位保留加法器阵列)将多个部分积并行合并为两个结果(和与进位)——最后用一个常规加法器相加。单次32位乘法可以做到约3~5个时钟周期。
Booth编码的原理：乘数的连续1序列0111(7)可表示为1000-0001(8-1)——即一次加一次减替代三次加法。编码后乘数每3位一组只需产生一次加减。这种优化对被乘数的符号位可能延长造成的不对称在负数乘法中被完美解决。
除法运算的硬件实现
硬件除法远比加法复杂。非恢复余数算法使用被除数高位试减除数——减得动则商1并撤除数左移恢复余数，减不动则商0且不恢复余数只左移继续试减。每次试减需要一次减法。32位除法最多需要32个时钟周期。现代CPU用SRT除法(Sweeney, Robertson, Tocher)——每周期产生多位商来代替一次性试减——并用冗余商表示(允许商位取值-1,0,1而非仅0,1)克服了高基数试减的逻辑残差判断的不确定性——代价是结尾必须进行一次常规加法的最终调整。典型32位除法约需10~16周期。
x86-64的div/idiv指令非常慢——相对其他运算慢数十倍。编译器尽量把除以常数优化为乘法和移位：x/10被优化为x * 171 / 2^11(预先计算的乘法逆元+右移)。涉及变量的除法应尽量减少——性能密集代码中用位运算和查表绕过除法。
ALU的时序与时钟
ALU是组合逻辑——输出在输入稳定后一段传播延迟后稳定。CPU时钟周期长度必须≥最慢功能单元(加法器/移位器等)的延迟加上前后寄存器建立/保持时间——因此ALU延迟直接影响CPU最高频率。超前进位加法器将加法延迟从64门路降低到约4门路——使极高时钟周期成为可能。
如果ALU的延迟不满足时钟周期——可以用流水线寄存器将ALU拆分为多级——加法器插入流水线寄存器取中间进位状态——在下一时钟周期完成余下的求和。代价是一条加法指令需要一个时钟步骤的额外延迟来处理——流水线的分级增加了总的取指到写回的延迟(Latency)但提升了总吞吐(Throughput)——CPU可以在相加上一批数据的同时开始下一批数据准备。
复习检查
行波进位加法器中32位加法在最坏条件下需要经历多少门级延迟——如果每门150ps——32位加法耗时多少？
超前进位加法器理论上可以将延迟降到几门级——为什么级联加法的逻辑表达式中"展开"到两级与非式过后仍然有额外的扇入扇出延迟？
将减法统一为补码加法——ALU中通过增加一个Sub(减法标识)信号来实现——具体是如何控制输入进位的？
cmp a,b执行后CPU的哪些标志位会被更新？jz检查的是标志位中的哪一个位？该位在cmp之后的逻辑填充关系是什么？OF的计算可通过最高有效位的进位输入异或进位输出来判定——在什么减法场景下OF触发而CF不触发？