第三讲 算术逻辑单元（Arithmetic Logic Unit

内容要点：逻辑运算，二进制加减法运算，ALU的实现

算术运算和逻辑运算

• 加法指令的编码示例1：add $8,$9,$10 #$8=$9+$10

  • int f,g,h;
    ...
    //f->$8, g->$9, h->$10
    f = g + h;
    

    查指令编码表得：opcode=0，funct=，shamt=0（非移位指令）

    根据指令操作数得：rd=8（目的操作数），rs=9（第一个源操作数），rt=10（第二个源操作数）

    R	opcode	rs	rt	rd	shamt	funct
    	31 26	25 21	20 16	15 11	10 6	5 0
    	00000	01001	01010	01000	00000	100000

• 加法指令的编码示例1：addi $21,$22,-50 #$21=$22+(-50)

  • 查指令编码表得：opcode=

  • 分析指令得：rs=22（源操作数寄存器编号）， rt=21（目的操作数寄存器编号），immediate=-50（立即数）

  I	opcode	rs	rt	Immediate
  	31 26	25 21	20 16	15 0
  	001000	10110	10101	1111 1111 1100 1110

• 算术运算指令（MIPS Core Instruction Set）

  • R型
    • add rd, rs, rt #R[rd] = R[rs] + R[rt] ^[1]
    • addu rd, rs, rt #R[rd] = R[rs] + R[rt]
    • sub rd, rs, rt #R[rd] = R[rs] - R[rt] ^[1]
    • subu rd, rs, rt #R[rd] = R[rs] - R[rt]
  • I型
    • addi rt, rs, imm #R[rt] = R[rs] + SignExtImm ^[1][2]
    • addiu rt, rs, imm #R[rt] = R[rs] + SignExtImm ^[2]

• 逻辑运算指令（MIPS Core Instruction Set）

  • R型
    • and rd, rs, rt #R[rd] = R[rs] & R[rt]
    • or rd, rs, rt #R[rd] = R[rs] |R[rt]
    • nor rd, rs, rt #R[rd] = ~(R[rs] | R[rt])
  • I型
    • andi rt, rs, imm #R[rt] = R[rs] & ZeroExtImm ^[3]
    • ori rt, rs, imm #R[rt] = R[rs] | ZeroExtImm ^[3]

• 算术逻辑运算的需求

  • 算术运算
    • 两个32-bit数的加法，结果为一个32-bit数
    • 两个32-bit数的减法，结果为一个32-bit数
    • 检查加减法的结果是否溢出
  • 逻辑运算
    • 两个32-bit数的“与”操作，结果为一个32-bit数
    • 两个32-bit数的“或”操作，结果为一个32-bit数
    • 两个32-bit数的“或非”操作，结果为一个32-bit数

门电路的基本原理

• 晶体管
  • 现代集成电路中通常使用MOS晶体管（Metal-Oxide-Semiconductor）
    • N型MOS管（Gate连接高电频时导通）
    • P型MOS管（Gate连接低电频时导通）
• 非门（NOT gate）
• 与门（AND gate）
• 或门（OR gate）
• 异或门（XOR gate）
  • 两个值不相同，异或结果为真；反之为假
  • A^B = (!A·B) + (A·!B)

• 寄存器的基本原理
  • D触发器（D flip-flop，DFF）
    • 具有存储信息能力的基本单元
    • 由若干逻辑门构成，有多种实现方法
    • 主要有一个数据输入，一个数据输出和一个时钟输入
    • 在时钟clock的上升沿（0->1），采样输入D的值，传送到输出Q，其余时间输出Q的值不变
      • 照相机➕显示器 -> D触发器
      • 每10s按一次快门 -> clock频率为0.1Hz
      • 按快门后1s，显示器上显示照片 -> CLK-to-Q时间为1s
      • 按快门前后，待拍摄的画面不能有变化，否则画面会糊 -> Setup/Hold时间
  • 寄存器的构成：32个D触发器 -> 32-bit register -> CPU中的一个通用寄存器/PC/IR -> 相连得复杂的CPU

算术逻辑运算的实现（Arithmetic-Logical-Unit，ALU）

• MUX 多选器

• 加法和减法的实现
  • 半加器（Half Adder）
    • 输入端口A、B
    • 输出端口S（和 & XOR Gate）、C（进位 & AND Gate）
  • 全加器（Full Adder）
    • 由两个半加器组成
    • 输入端口A、B、C（进位输入）
    • 输出端口S（和）、C（进位输出）
  • 4-bit加法器
    • 两个4-bit二进制数相加
    • 由四个全加器构成
  • 检查加法运算结果是否溢出
    • “溢出”（overflow）：运算结果超出了正常的表示范围
    • ”溢出“仅针对有符号数运算（有符号数是指最高位1是否代表负数）
      • 两个正数相加，结果为负数
      • 两个负数相加，结果为正数
    • 检查方法：”最高位的进位输入“ 不等于 ”最高位的进位输出“
    • 注意区分”进位“和”溢出“
      • 有”溢出“时，不一定有进位：0011 + 0101 = 01000
      • 有”进位“时，不一定有溢出：1110 + 1100 = 11010
  • ”溢出“的处理方法
    • MIPS
      • 将操作数看做有符号数，发生”溢出“时产生异常
      • 将操作数看做无符号数，不处理”溢出“
    • X86
      • 利用程序状态字寄存器中的OF位，发生”溢出“，设置OF=1
      • 利用程序状态字寄存器中的OF位，发生”溢出“，设置OF=1
  • 减法运算
    • 减法运算均可转换为加法运算
    • 补码表示的二进制数的相反数：按位取反，末尾加一
    • A - B = A + (-B) = A + (~B + 1)

加法器的优化

1. 行波进位加法器（Ripple-Carry Adder，RCA）
   • 结构特点：低位全加器的C连接到高一位全加器C
   • 优点：电路布局简单，设计方便
   • 缺点：高位的运算必须等待低位的运算完成，延迟时间长
   • 4-bit RCA的关键路径（延迟最长的路径/关注Gate最多的路径）
     • T为门延迟
     • 总延迟时间：(T+T)*4 + T = 9T

• 进位输出信号的分析
  • C = (A·B) + （A·C）+ （B·C）= (A·B) + (A+B)C
  • 设：
    • 生成（Generate）信号：G = A·B
    • 传播（Propagate）信号：P = A + B
  • 则：C = G + P·C
  • 计算C 时，无需等待C，直接将从C开始的式子不断带入，这样就可以实现提前计算”进位输出信号“
• 提前计算C的电路实现
  • 优点：计算C的延迟时间固定为三级门延迟，与加法器的位数无关
  • 缺点：如果进一步拓宽加法器的位数，则电路变得非常复杂

2. 超前进位加法器（Carry-Lookahead Adder, CLA）

• 4-bit CLA: 计算C需要3级门延迟 + 最后一级全加器还需要1级门延迟 -> 总延迟时间为4级门延迟

  • 参考值：4-bit RCA的总延迟时间为9级门延迟

• 32-bit加法器的实现

  • 如果采用RCA
    • 总延迟时间为65级门延迟：(T+T)*32 + T = 65T
  • 如果采用CLA
    • 理想的总延迟时间为4级门延迟
    • 实际上电路过于复杂，难以实现
    • 通常的实现方法：
      • 采用多个小规模的CLA拼接而成
      • 如，用4个8-bit的CLA连接成32-bit加法器

1. May cause overflow exception ↩ ↩ ↩

2. SignExtImm = {16{imm[15]}, imm} ↩ ↩

3. ZeroExtImm = {16{1'b0}, imm} ↩ ↩