计组复(yu)习笔记（慕课）

2018-06-17

运算器

0x01 加法器和减法器

4-bit RCA的关键路径（延迟最长的路径）

进位输出信号的分析

$\begin{align*} C_{i+1} &= (A_{i} \cdot B_{i})+(A_{i} \cdot C_{i})+(B_{i}\cdot C_{i}) \\ &= (A_{i} \cdot B_{i})+(A_{i}+B_{i})\cdot C_{i} \end{align*}$
- 生成信号： $\begin{align*} G_{i}=A_{i}\cdot B_{i} \end{align*}$
- 传播信号： $\begin{align*} P_{i}=A_{i} + B_{i} \end{align*}$
- 则有： $\begin{align*} C_{i+1}=G_{i} + P_{i}\cdot C_{i} \end{align*}$
- $\begin{align*} C_{1}=G_{0} + P_{0}\cdot C_{0} \end{align*}$
  $\begin{align*} C_{2} &= G_{1} + P_{1}\cdot C_{1} \\ &= G_{1} + P_{1}\cdot (G_{0} + P_{0}\cdot C_{0}) \\ &= G_{1} + P_{1}\cdot G_{0} + P_{1}\cdot P_{0}\cdot C_{0} \end{align*}$
  $\begin{align*} C_{3} &= G_{2} + P_{2}\cdot C_{2} \\ &= G_{2} + P_{2}\cdot (G_{1} + P_{1}\cdot G_{0} + P_{1}\cdot P_{0}\cdot C_{0}) \\ &= G_{2} + P_{2}\cdot G_{1} + P_{2}\cdot P_{1}\cdot G_{0} + P_{2}\cdot P_{1}\cdot P_{0}\cdot C_{0} \end{align*}$
- 提前计算电路的优点：计算 C_i+1 的延迟时间固定为三级门延迟，与加法器的位数无关
- 缺点：如果进一步拓宽加法器的位数，则电路变得非常复杂
- 32位加法器通常实现方法：采用多个小规模的超前进位加法器拼接而成：例如，用4个8-bit的超前进位加法器连接成32-bit加法器

0x02 乘法器和除法器

乘法器工作流程

原版
优化

乘法器最终结构

test

除法器工作流程

test

除法器最终结构

test

乘法器除法器合并

test

0x03 乘法和除法指令

MIPS 指令

MIPS 乘除法的专用寄存器：Hi，Lo
- 乘法： Hi/Lo联合用于保存64-bit乘积
- 除法： Lo保存商（32-bit）， Hi保存余数（32-bit）
- 读取方法： mfhi/mflo $s1 （move from Hi/Lo）即为 $s1 = Hi/Lo
MIPS 指令：
- 乘法： mult， multu
- 除法： div， divu

x86 指令

x86 乘法指令：
- MUL：（无符号）
  - 格式： MUL SRC
  - 操作：
    - 8位： AX <- AL × SRC
    - 16位： DX:AX <- AX × SRC
    - 32位： EDX:EAX <- EAX × SRC
    - 64位： RDX:RAX <- RAX × SRC
- IMUL：（有符号）
x86 除法指令：
- DIV：（有符号）
  - 格式： DIV SRC
  - 操作：
    - 8位： AL <- AL/SRC 的商； AH <- 余数
    - 16位： AX <- (DX:AX)/SRC 的商； DX <- 余数
    - 32位及64位类似
- IDIV：（有符号）余数符号和除数相同
符号扩展类指令
- CBW 字节扩展为字
  - 格式： CBW
  - 操作：将 AL 的符号位扩展到 AH
- CWD 字扩展为双字
  - 格式： CWD
  - 操作：将 AX 的符号位扩展到 DX
- 注：IA-32新增的相关指令
  CWDE 指令：将 AX 符号扩展到 EAX
  CDQ 指令：将 EAX 符号扩展到 EDX:EAX

控制器

取指令
- 程序计数器（PC）的内容是指令的地址，用 PC 的内容作为地址，访问指令存储器获得指令编码
更新 PC
- 顺序执行时： PC <- PC + 4
- 发生分支时： PC <- 分支目标的地址
取指部件 IFU
加法和减法指令
- R[rd] = R[rs] op R[rt]
- addu rd, rs, rt
逻辑运算指令
- R[rt] = R[rs] op ZeroExt[imm16]
- ori rt, rs, imm16
运算部件
访存指令（Load）
- R[rt] = Mem[R[rs]+SignExt[imm16]]
- lw rt, imm16(rs)
访存指令（Store）
- Mem[R[rs]+SignExt[imm16]] = R[rt]
- sw rt, imm16(rs)
运算+访存
整体
控制信号的逻辑表达式

流水线

执行指令的主要步骤（MIPS）
超标量流水线：具有两条或两条以上并行工作的流水线结构称为超标量流水线
- 单周期->标量流水线：时间并行性
- 标量->超标量流水线：空间并行性
流水线冒险
- 结构冒险
  - 示例：
  - 解决方法1：流水线停顿（stall），产生空泡（bubble）
  - 解决方法2：指令和数据放在不同的存储器
  - 示例：
  - 解决方法：前半周期写，后半周期读，设置独立的读写接口
- 数据冒险
  - 示例：
  - 解决方法1：流水线停顿（stall），产生空泡（bubble）
  - 解决方法2：数据前递（Forwarding）（前递也叫旁路（Bypass））
    - 无法解决的情况：
    - 解决方法：停顿 + 前递
- 控制冒险
  - 示例：
  - 无条件直接转移 j Target ：流水线不停顿，信息在取指阶段可以获得
  - 无条件间接转移 jr rs：停顿一个周期，译码阶段获得信息
  - 条件转移 beq rs， rt， imm16：使译码阶段能判断两数相等则只需停顿一个周期

高速缓存 Cache

Cache 的写策略
- 写穿透/直写：数据同时写入 Cache 和主存
- 写返回：数据只写入 Cache，仅当该数据块被替换时数据写回主存
Cache 失效时的写策略
- 写不分配：直接将数据写入主存
- 写分配：将该数据所在的块读入 Cache 后，再将数据写入 Cache
Cache 失效的原因：
- 义务失效也称冷启失效：第一次访问某一数据块（无法有效避免）
- 容量失效： Cache 无法保存程序访问所需的数据块（可通过增加 Cache 容量缓解）
- 冲突失效：多个存储器位置映射到同一 Cache 位置
Cache 的映射策略
- 直接映射：表项只保存一行数据（即只有一个标签，若有相同标号的表项则直接替换）
- 二路组相联：可以保存在一个表项保存两个不同标签，第三个标签来再替换
- 全相联：和表中所有比较标签
常见的 Cache 替换算法
- 随机
- 轮换：按预先设定的顺序换
- 最近最少使用（LU）：选择距离现在最长时间未被访问的 Cache 块替换

中断和异常

8086 ：最低 1KB （00000H ~ 003FFH）保留中断向量表
中断处理过程
- 关中断： CPU 关闭中断响应，即不再接受其他外部中断请求
- 保存断点：将发生中断处的指令地址压栈。
- 识别中断源： CPU 识别中断的来源，确定中断类型号，从而找到相应的中断服务程序的入口地址
- 保护现场：将发生中断处的有关寄存器（中断服务程序中要用的寄存器）以及标志寄存器压栈
  - 标志寄存器 FLAGS 中第九位 IF 中断标志
  - IF = 1 允许可屏蔽中断请求
  - STI/CLI 指令将 IF 置 1/0
  - 对非屏蔽中断和内部中断 IF 不起作用
- 执行中断服务程序：转到中断服务程序入口开始执行，可在适当时候重新开放中断，以响应较高优先级的外部中断
- 恢复现场并返回：把压栈的信息弹回原寄存器并执行中断返回指令
  - IRET 中断返回指令
  - 操作：从栈顶弹出三个字，分别送到 IP， CS 和 FLAGS
  - 说明：放在中断服务程序的末尾，按中断调用时的逆序恢复现场，返回到程序发生中断处继续执行
内部中断
- 类型0：除法错中断
  - 除法后，商超过了目标寄存器所能表示的范围（如把 0 作除数），则 CPU 立即产生一个类型0中断
- 类型4：溢出中断
  - 执行 INTO 指令时，若溢出标志位 OF 为1，则将引起类型4内部中断（若 OF = 0 则 INTO 等价于空指令）
  - 通常安排在算术运算指令后，以便发生溢出时能及时处理
  - INTO 等价于 INT 4
- 类型1：单步中断
  - 当标志寄存器的 TF 位置为1， CPU 便处于单步工作状态
  - 在单步工作状态， CPU 每执行完一条指令，就会自动产生一个类型1的中断，进入类型1的中断服务程序
  - 类型1中断服务程序：一般用于显示 CPU 内部各寄存器的内容和一些其他信息以便调试
- 类型3：断点中断
  - 也是一种调试手段，常和单步中断配合使用
  - 一般先通过断点将程序的某一错误定位在一小段，再单步调试
  - 在所有 INT n 形式的指令中，只有断点中断指令 INT 3 是一条单字节长的指令，其他都是两字节
  - 设置断点：用断点中断指令 INT 3 代替用户程序原有指令，保存用户程序原有指令
  - 恢复执行：断点中断服务程序返回前，恢复用户程序的原有指令，并将 IP 减1，返回后从断点处继续执行
- 内部中断的特点：
  - 类型号由 CPU 内部产生，外部中断需要从外设中读取中断类型号
  - 屏蔽方式：除单步中断外，所有内部中断都不能用软件方式屏蔽；单步中断可以设置 TF 的值来允许和禁止
  - 优先级：除单步中断外所有内部中断优先级高于外部中断
INT 指令说明
- 格式： INT n （0 ~ 255）
- 操作：
  - FLAGS 压栈
  - 清除 IF 和 TF
  - CS IP 压栈
  - 查找中断向量表
  - 入口地址装入 CS IP

BIOS 中断

ROM BIOS
- 装于从地址 0FE00H 开始的 8KB ROM 中
- 提供了系统加电自检，引导装入，主要 I/O 设备的处理程序及接口控制等
BIOS 各功能模块的入口地址都在中断向量表中，通过 INT n 调用，如有需要用寄存器传参

示例：

MOV AH, 1  # 设置功能号， 对于 1AH， AH = 1 为写时钟 0 为读时钟
MOC CX, 0  # 设置入口参数， CH:CL = 时：分
MOV DX, 0  # DH:DL = 秒： 1/100秒
INT, 1AH   # 调用 1AH 号中断

DOS中断
- 格式 INT 21H
- 功能：包含最常用的程序功能，分别实现文件管理，存储管理等功能
- 共用 21H 号中断入口，通过传参数的方式设置功能号，以选择执行不同的功能模块
- DOS 中断功能比 BIOS 中断更齐全，完整，进一步屏蔽了设备的物理特性及接口特性
- 示例：在屏幕上输出字符 ‘$’
  1
  2
  3
  MOV AH 06 #设置功能号， DOS 6号为屏幕输入输出
  MOV DL '$' #设置入口参数， DL 中放待输出的字符 (DL = FF 时为输入 AL = 输入字符）
  INT 21H

输入输出设备

I/O 控制方式
- 程序控制方式：在程序控制下进行数据传送
  - 无条件传送方式：假设外设已经准备好， CPU 直接使用指令和外设传递数据，不查询外设工作状态
    - 优点：控制程序简单
    - 缺点：只适合简单外设
  - 程序查询传送方式： CPU 通过执行一段程序，不断查询外设的工作状态，确定外设已经准备好后，才进行数据传送
    - 优点：比无条件传送准确可靠
    - 缺点：查询外设状态占用了大量的时间
    - 数据输入输出过程参见 计组复习笔记第九讲 0x02 数据输出过程
  - 共同的优缺点：
    - 优点：对外设要求低，流程清晰
    - 缺点：由 CPU 进行数据传送，占用了运算资源
- 中断控制方式：
  - 数据输入过程：
    1. CPU 执行指令，将控制字写入控制寄存器，设置工作模式
    2. 外设将数据发到并行数据输入信号，并将输入准备好信号置为有效
    3. 接口发现输入准备好信号有效后，从并行数据输入 信号接收数据，放入输入缓冲寄存器，并将 输入回答 信号置为有效，阻止外设输入新数据（和程序查询一样，但不用反复读取 状态寄存器 确认是否有输入）
    4. 接口通过中断控制逻辑向 CPU 发出终端请求信号，并将状态寄存器 中的 输入缓冲满 置为有效
    5. CPU 收到中断请求后，进入中断服务程序，执行指令从 状态寄存器 中读出状态字，发现 输入缓冲满 ，因此执行指令，从 输入缓冲寄存器 中读出数据
    6. 接口将 输入回答 信号置为无效，等待外设输入新的数据
  - 数据输出过程：
    1. CPU 执行指令，将控制字写入控制寄存器，设置工作模式
    2. CPU 执行指令，将数据写到接口的输出缓冲寄存器
    3. 接口将数据发到并行数据输出信号，并将输出准备好信号置为有效（也可由 CPU 将该字设置为有效）
    4. 外设发现输出准备好信号有效后，从并行数据输出 信号接收数据，并将输出回答信号置为有效（与程序控制同）
    5. 接口发现 输出回答 信号有效后，通过 中断控制逻辑 向 CPU 发出中断请求信号，并将 状态寄存器 中的状态位 输出缓冲空 置为有效
    6. CPU 收到中断请求后，进入中断服务程序，执行指令从 状态寄存器 中读出状态字，发现 输出缓冲空 ，因此开始下一个输出过程，继续输出新数据
  - 优点： CPU 和外设可以并行工作，提高工作效率；外围设备具有申请服务的主动权
  - 缺点：
    - 外设和存储器之间的数据交换仍由 CPU 承担，使用数据传送指令，占用了 CPU 资源
    - 数据要经过 CPU 中的通用寄存器中转，过程冗长
    - 注： 程序查询方式 也有这些缺点
    - 进入中断和退出中断服务需要额外的指令
- 直接存储器访问式（DMA）
  - 数据传送过程不需要 CPU 干预（不需要执行程序指令）
  - 由专门硬件电路（DMA控制器，简称DMAC）控制，进行外设和存储器间直接数据传送
  - DMAC 基本工作步骤：
  - 部分接口带有独立的 DMAC 如显卡，网卡等
    1. CPU 设置 DMAC 内部配置寄存器，一般包括
      - 源地址的初始值及传送时的地址增减方式
      - 目的地址的初始值及传送时的地址增减方式
      - 待传送的数据长度
      - 示例：外设到内存
        
        源地址设置为某 I/O 端口，传送时不变
        
        目的地址设置为存储器的某个地址，传送时递增
        
        待传送数据的长度根据需要设置，亦可不设置
    2. DMAC 处于空闲等待状态
    3. I/O 接口向 DMAC 发出 DMA 传送申请
    4. DMAC 相应 I/O 接口的申请
    5. DMAC 向 I/O 接口发起总线读传输
    6. DMAC 向存储器发起总线写传输
    7. 重复 5~6 直到本次 DMA 传送完成
    8. 返回 2 ，等待下一次 DMA 传送申请
    9. 注： DMA 传输完成后， DMAC 会通过中断信号通知 CPU

外部中断的处理过程
- 外部中断也叫，由 CPU 外部的中断请求信号启动的中断
- x86 CPU 外部中断提供两个引脚
  - NMI: 非屏蔽中断
  - INTR：可屏蔽中断
可编程中断控制器 PIC （典型 Intel 8259A ）(APIC：高级PIC）
- 早期 PC 中的中断控制器
- 现代 PC 中的中断控制器
  - 注： CPU 可以发出中断请求给另一个 CPU 来完成交互
中断嵌套
- 当 CPU 正在执行中断服务程序时，发生优先级更高的中断请求
- CPU 相应优先级更高的中断请求，而将正在处理的中断请求暂时挂起
- CPU 完成优先级更高的中断服务后，返回此前优先级较低的中断服务程序继续执行

未来机械研究所

计组复(yu)习笔记（慕课）

运算器

0x01 加法器和减法器

0x02 乘法器和除法器

乘法器工作流程

乘法器最终结构

除法器工作流程

除法器最终结构

乘法器除法器合并

0x03 乘法和除法指令

MIPS 指令

x86 指令

控制器

流水线

高速缓存 Cache

中断和异常

输入输出设备