COA Review (3) | ZY in NJU

13 总线

总线是连接两个或多个设备的通信通路

类型

芯片内部总线：连接芯片内部的各个部分
- 例：CPU中连接寄存器、ALU等部分
系统总线：连接CPU、存储器、IO控制器和其他功能设备
通信总线：连接主机和I/O设备，或连接不同的计算机系统

Intel架构中的“系统总线”

intel架构中的系统总线指的是：IO连接桥和CPU之间连接的总线，与上面所说的系统总线有略微不同（特指的系统总线

数据线、地址线和控制线

数据线：在系统组件之间传输数据
- 数据线的数量决定了一次可以传输的数据大小（数据的位数，一根一位）
地址线：在数据线和I/O端口上指定数据的来源和去向
- 地址线的数量决定了寻址空间的大小（地址的位数，一根一位）
特例：可以将64位地址分成两次32位地址传输（先行地址后列地址
控制线：控制对数据线和地址线的存取和使用
- 时钟（clock）：用于总线同步操作
- 总线请求（bus request）：表示模块需要获得对总线的控制
- 总线允许（bus grant）：发出请求的设备已经被允许控制总线
- 中断请求（interrupt request）：表示某个中断正在悬而未决
- 中断响应（interrupt ACK）：未决的中断请求被响应
- 存储器读（Memory Read）：使所寻址单元的数据放到总线上
- 存储器写（Memory Write）：引起总线上的数据写入被寻址的单元
- I/O读（I/O Read）：使被寻址的I/O端口的数据放到总线上
- I/O写（I/O Write）：引起总线上的数据输出到被寻址的I/O端口

总线上数据传输的特点

总线可以被多个设备监听，但同一时刻只能由一个设备发送数据

如果同一时刻多个设备同时发送数据，会造成数据之间的混淆
使用总线进行数据传输
- 如果连在总线上的某个设备希望向另一个设备发送数据，需要：
  1. 获得总线的使用权
  2. 通过总线传输数据
- 如果连在总线上的某个设备希望向另一个组件请求数据，需要：
  1. 获得总线的使用权
  2. 通过总线向另一个设备发送请求，等待另一个设备发送数据
某个设备已经在使用总线时，其他设备不能获得总线的使用权（无论优先级

设计要素

用途：专用总线，复用总线
仲裁（arbitration）：集中式，分布式
时序：同步时序/异步时序/半同步时序/分离事务
总线带宽（bandwidth）和数据传输率（data transfer rate）
总线层次结构：单总线，双总线，多总线

用途

专用（dedicated）总线：始终只负责一项功能，或始终分配给特定的计算机组件。
- 优点：高吞吐量，减少总线冲突
- 缺点：增加了系统的规模和成本
复用（multiplexed）总线：将同一线路用于多种用途
- 优点：使用的布线数量少，节省空间和成本
- 缺点：每个模块需要更复杂的控制电路，且共享可能会降低性能

仲裁

总线仲裁：当多个设备需要与总线通信时，通过某种策略选择一个设备

平衡因素：

优先级：优先级高的设备优先被服务
公平性：优先级最低的设备不能一直被延迟

仲裁方案

集中式（centralized）：由**仲裁器（arbiter）或总线控制器（bus controller）**负责分配总线使用权
- 链式查询/菊花链（daisy chain）
  
  所有的设备都是串行连接的，并将允许信号从优先级最高的设备下发到优先级最低的设备（从高到低
  
  总线仲裁器收到请求后，在总线不忙的情况下，发起允许信号
  
  如果某个设备收到了允许信号并且发起了总线请求，该设备将总线设置为繁忙状态，允许信号将不再被进一步传递。（繁忙线是双向的，可以由设备发起也可以发送到设备，此时其他优先级更低的设备会知道总线繁忙
  
  优点：确定优先级很简单（优先级高在前面，优先级低在后面），可以很灵活地添加设备
  
  缺点：不能保证公平性，对电路故障敏感（串连），限制总线的速度
  
  流程：
  1. 首先设备检查繁忙线是否被设成忙，如果没有被设成忙则发起请求信号，
  2. 总线仲裁器收到请求信号后，检测繁忙线是否被设为忙，如果不忙的话则发起允许信号。
  3. 允许信号从优先级高的设备一直往优先级低的设备传递（通过允许线串连起来），遇到发出请求信号的设备就停止，该设备将繁忙线设成忙，同时开始使用总线
    
    计数器查询（query by a counter）
  将总线允许线替换为设备ID线（ $\log_2n$ 根 – $n$ 个设备，并非图上所绘制出来的一根）
  
  如果总线空闲，总线仲裁器通过设备ID线发送计数
  
  如果当前发送请求的设备ID等于裁决器当前的计数，裁决器将停止计数，设备将总线设置为忙
  
  与链式的区别：报数顺序并不固定，可以更改，即同一个设备的设备ID在每次请求时可能不同，这样就可以灵活的确定设备的优先级
  
  优点：通过使用不同的初始计数，可以灵活地确定设备优先级
  - 强调优先级：从1开始
  - 强调公平性：从下一个设备的ID开始
  对电路故障不敏感。
  
  缺点：需要添加设备ID线，需要解码和比较设备ID信号，限制总线的速度
  - 独立请求（independently request）
  每个设备都有自己的总线请求线和总线允许线
  
  当一个设备请求总线时，它通过总线请求线将请求信号发送给总线仲裁器
  
  总线仲裁器决定哪个设备可以使用总线
  - 决定策略：固定优先级，公平链式，LRU，FIFO，…
  优点：快速响应，可编程的优先级
  
  缺点：复杂的控制逻辑，更多的控制电路
分布式（distributed）：每个设备都包含访问控制逻辑，各设备共同作用分享总线
- 自举式
  
  固定优先级
  
  每个设备在其总线请求线上发送请求，最低优先级的设备没有请求线
  
  每个设备自行判断自己是否在请求总线的设备中优先级最高
  
  过程：优先级高的设备会发送信号，比该设备优先级低的设备会监听该信号，如果优先级高的设备要使用总线，就会发送信号，优先级低的设备就不能使用总线（监听到了优先级高的设备要使用总线的信号
- 冲突检测
  当一个设备想要使用总线时，它会检查宗贤是否繁忙。如果总线空闲，设备使用总线
  
  冲突：如果两个设备发现总线空闲，它们可能同时使用总线
  - 在传输数据时，设备会监听总线，检查是否存在冲突
  - 如果发生冲突，所有使用总线的设备将停止数据传输，并分别在随机间隔时间后再次请求总线。

时序

确定每个总线事务的开始和结束时间

总线事务：地址 + 数据 + … + 数据

类型：

同步时序：事件的发生由时钟决定
异步时序：一个事件的发生取决于前一个事件的发生
半同步：同步时序和异步时序相结合
分离事务：设备准备数据期间释放总线

同步时序

优点：更容易实现和测试

缺点：所有设备共享同一个时钟，总线长度收到时钟偏差的限制

异步时序

握手策略：ready线和ACK线进行三次握手变成全互锁

非互锁：No interlock

半互锁：Semi-interlock

全互锁：interlock

以全互锁的三次握手为例来讲解一下，非互锁就是取了全互锁的第一次握手，半互锁是取了全互锁的第一次和第二次握手。

Ready信号：提供东西给总线时需要告诉总线该东西准备就绪（上升沿表示），下降沿表示撤掉准备就绪的信号，目的是为了下一次的准备就绪

ACK信号：总线告诉设备自己已经获得了数据（上升沿表示已经取到了数据）

第一次握手：Ready信号在上升沿处，代表设备已经准备好了数据，总线可以获得数据，于是Ready线和ACK线握手，告诉ACK线该设备已经准备好数据，Ack线可以获得该数据了

第二次握手：Ack线取得数据之后，代表总线已经获得了该数据，此时Ready线上的Ready信号可以撤去，因此发生第二次握手，Ack线告诉Ready线自己已经取好了数据，不需要知道设备准备就绪了

第三次握手：Ready线撤下信号之后，代表进入到下一个取数据的周期中，因此发生第三次握手，告诉Ack信号应该撤下代表“已经取好数据”的信号，因为此时进入下一个周期，信号应该是还没有取好的。

优点：可以灵活地协调速度不同的设备
缺点：对噪声敏感

半同步时序

为了减少噪声的影响，在异步计时中使用时钟。

准备和响应信号在时钟上升沿有效

结合同步和异步定时的优点。

分离事务

将一个总线事件分离为两个过程

优点：增加总线利用率

缺点：增加每个总线事件的持续时间和系统复杂度

总线带宽和数据传输数率

总线带宽（bus bandwidth）：总线最大数据传输速率

不要考虑总线仲裁，地址传输等因素
数据传输速率

考虑地址传输，握手等因素
总线宽度：组成总线的线数（与总线带宽不同）

数据总线越宽，一次传输的数据位数就越多

地址总线越多，一次传输的地址位数就越多

例1

假设同步总线的时钟周期为50ns，每次传输需要一个时钟周期，异步总线每次握手需要40ns。两个总线都是32位宽，内存的数据准备时间为200ns。当从存储器读出一个32位的字时，计算两个总线的数据传输率

同步总线
- 发送指令和地址到内存：50ns
- 内存准备数据：200ns
- 将数据传输到CPU：50ns
- 数据传输率 = $\frac{32\ bit}{(50 + 200 + 50) \ ns} = 106.7\ Mbps$
异步总线
- 步骤1：40ns
- 步骤2、3、4、数据准备： $\max(40ns \times 3, 200ns) = 200ns$
- 步骤5、6、7： $40ns \times 3 = 120ns$
- 数据传输率 $ = \frac{32\ bit}{(40 + 200 + 120)\ ns} = 88.9\ Mbps$

例2

假设系统具有以下特征：

它支持访问大小为4到16个字（每个字32bit）的块

同步总线具有64位宽和200MHz时钟频率，需要1个时钟周期来传输地址或64位数据

在两个总线事务之间有2个空闲时钟周期

内存访问准备前4个字需要200ns，后面每4个字准备需要20ns

当前面的数据在总线上传输时，内存可以同时读取后面的数据

如果读取256个字，分别计算每次传输4个字和16个字时的数据传输速率，传输时间和每秒总线事务数

每次传输4个字
- 总线事务：地址 + 4个字
  - 地址传输：1个时间周期
  - 数据准备：200ns（40个时间周期）
  - 数据传输：2个时间周期
  - 空闲：2个时钟周期
- 总共： $\frac{256}{4} \times (1 + 40 + 2 + 2) = 2880$ 个时间周期
- 传输时间（时钟周期 $5ns$ ）： $2880 \times 5ns = 14400ns$
- 每秒总线事务： $\frac{1s}{14400 ns} \times 64 = 4.44M$
- 数据传输速率 $= \frac{256 \times 32bit}{14400ns} = 568.9Mbps$
每次传输16个字
- 总线事务：地址 + 16个字
  - 地址传输：1个时间周期
  - 数据准备（前四个字）： $200ns$ （40个时间周期）
  - 数据传输：同步总线一次传输两个字，在传输两个字的同时准备数据的下4个字，传输需要2个时钟周期，读取下4个字需要 $20ns$ ，即4个时钟周期
  - 空闲：2个时钟周期
- 总共： $\frac{256}{16} \times (1 + 40 + 3 \times \max(2, 4) + 2 + 2) = 912$ 个时钟周期（其中倒数第二个2是最后一次数据传输，此时没有数据需要准备了，所以直接传输）
- 传输时间： $912 \times 5ns = 4560ns$
- 每秒总线事务数 = $\frac{1s}{4560ns} \times 16 = 3.51M$
- 数据传输速率 = $\frac{256 \times 32bit}{4560} = 1796.5 Mbps$

提高总线的数据传输率

提高时钟频率
增加数据总线宽度
- 每次传输更多的数据（成本：更多的总线线路
块传输
- 传输一次地址就传输一块数据（成本，高复杂性
分离总线事务
- 减少总线空闲时间（成本：复杂性高，增加每个事务的持续时间
分离地址线和数据线
- 同时传输地址和数据（成本：更多的总线线路

总线层次结构

单总线结构

CPU、存储器和I/O模块都连接到一条系统总线
优点：简单、易于扩展
缺点：
- 连接的设备越多，总线长度越大，传输延迟也就越大
- 聚集的传输请求接近总线容量后，总线成为瓶颈

双总线结构I

在CPU和存储中间增加一个存储器总线
优点：增加CPU和存储器之间的传输效率，同时降低系统总线的负担

双总线结构II

将系统总线分为存储器总线、I/O总线 和 IOP（input/output processor）
优点：降低I/O对总线的负担

多总线结构I

在双总线结构II 的基础上增加一个本地总线（local bus）来连接CPU和cache
优点：分离了 CPU 和 I/O 的交互

多总线结构II

将系统总线分为存储器总线、I/O总线和DMA总线
优点：增加I/O效率

多总线结构III

增加一个高速I/O

14 指令系统

指令集：CPU能执行的各种不同指令的集合
程序由存储在内存中的一组指令组成
计算机的基本功能是执行程序
CPU通过执行指定的指令来完成实际工作

指令时计算机处理的最基本单位

操作码（指令执行的内容）+操作数（要操作的对象）

多周期实现方案

可以将一条指令的执行分解为一系列步骤
- 取指令，译码/取寄存器，执行/有效地址/完成分支，访问内存，存储结果

指令的要素

操作码：指定将要完成的操作
源操作数引用：操作会涉及一个或多个源操作数，这是操作所需的输入
结果操作数引用：操作可能会产生一个结果
下一指令引用：告诉处理器这条指令处理完去哪里去取下一条指令

指令表示

在计算机内部，指令由一个位串（01串）来表示

指令格式：对应于指令的各要素，这个位串划分成几个字段

大多数指令集使用不止一种指令格式

机器指令符号表示法

操作码被缩写成助记符来表示

ADD：加，SUB：减，MUL：乘，DIV：除，LOAD：从存储器装入，STOR：保存到存储器
操作数也可以用符号表示

用寄存器编号或内存地址替换操作数

操作码

不同计算机上操作码的数目变动是很大的

所有计算机上都会存在相同的常用操作类型

数据传输
算术运算
逻辑运算
转换
输入/输出
系统控制
控制转移

数据传送

指明源和目标操作数的位置
指明将要传送数据的长度
指明每个操作数的寻址方式

算术运算

一条算术指令的执行会涉及数据传送操作，来为算术和逻辑单元准备输入，并传送逻辑单元的输出。

逻辑运算

位操作：操作一个字或其他可寻址单元中的个别位
移位和旋转

算术右移补充符号位，逻辑右移补充0

逻辑左移和算术左移都是补充0

输入/输出

各种输入/输出方法仅有少数输入/输出指令实现，具体操作由参数、代码或命令字指定

控制转移

分支指令（亦称为跳转指令）
跳步指令
过程调用指令

分支/跳转指令

把将要执行的下一条指令的地址作为它的操作数之一

跳步指令

包含一个隐藏地址，该隐含地址等于下一指令地址加上该指令的长度之和

下一指令地址：取指周期过后PC已经加一，指向了下一条指令的地址

过程调用指令

问题：存取函数跳转之后的返回的地址

涉及由目前位置转移到过程的调用指令和由过程返回到调用发生位置的返回指令

方法一：用寄存器：只能用于没有嵌套的函数调用

$RN(register) \longleftarrow PC + \Delta \\ PC \longleftarrow X(\text{函数调用的首地址})$
方法二：返回地址存于过程开始处（可以解决嵌套调用的问题，但递归时会修改掉返回地址，出现错误

$X \longleftarrow PC + \Delta \\ PC \longleftarrow X + 1$
方法三：使用栈：每次调用函数就将返回地址压入栈中

操作数

常见类型：地址、数值、字符、逻辑数据

地址

一个指令需要有4个地址引用：2个源操作数，1个目的操作数，以及下一指令地址

下一指令地址是隐含的

地址数量

每条指令中的地址数目越少
1. 指令的长度越短，不需要复杂的CPU
2. 使程序总的指令条数更多，导致执行时间更长，程序也更长更复杂
对于多地址指令，普遍具有多个通用寄存器可用，允许某些运算只使用寄存器即可完成，从而使执行加快。

数值

计算机存储的数值是受限的
- 集齐可表示数值的幅值是有限的
- 浮点数情况下数值精度是有限的
数值数据的类型
- 二进制整数或定点数
- 二进制浮点数
- 十进制数

字符

ASCII：每个字符被表示成唯一的7位二进制串

UNICODE：16/32位

逻辑数据

将一个 $n$ 位单元看成是由 $n$ 个 $1$ 位项组成，每项有值0或1

存储一个布尔或者二进制数据项序列，序列中的每个值只能取1（真）或0（假）
有利于实现对数据项的具体位进行操纵

大端序和小端序

大端：高位数据存在低地址

小端：高位数据存在高地址

对一个字节（同一个地址里的数据），都是高位在前低位在后，即大端序

在两种策略中每个数据项有同样的地址
在任何一个给定的多字节值中，小端的字节排序是大端的反序，反之亦然
端序不影响结构中数据项的次序

操作数引用

操作数的实际值
操作数的地址
- 寄存器
- 主存 / 虚拟内存

寻址方式

规定：

$A$ ：指令中地址字段的内容

$R$ ：指向寄存器的指令地址字段内容

$EA$ ：被访问位置的实际（有效）地址

$(X)$ ：存储器位置 $X$ 或寄存器 $X$ 的内容

立即寻址

方式：操作数实际出现在指令中
用法：定义和使用常数或设置变量的初始值
算法：操作数 = $A$
优点：除了取指令之外，获得操作数不要求另外的存储器访问
缺点：数的大小受限于地址字段的长度

直接寻址

方式：地址字段含有操作数的有效地址
用法：早期计算机常用，在当代计算机体系结构中不多见
算法： $EA = A$
优点：只要求1次存储器访问，且无需为生成地址而专门计算
缺点：有限的地址空间

间接寻址

方式：地址字段指示一个存储器字地址，而此地址保存有操作数的全长度地址
算法： $EA = (A)$
优点：扩大了地址空间
缺点：取操作数需要2次访问存储器
解释：地址引用的数量限制可能是有益的

寄存器寻址

方式：地址字段指示的是寄存器
算法： $EA = R$
优点：指令中仅需要一个较小的地址字段，且不需要存储器访问
缺点：地址空间十分有限
解释：寄存器寻址只有在被有效使用的时候才有意义

寄存器间接寻址

方式：地址字段指示寄存器
算法： $EA = (R)$
优点：扩大了地址空间，比间接寻址少1次存储器访问
缺点：相对于寄存器寻址，需要多1次存储器访问

偏移寻址

方式：结合直接寻址和寄存器间接寻址能力
算法： $EA = (R)+A$
类型：
- 相对寻址
- 基址寄存器寻址
- 变址
解释：偏移寻址要求指令有两个地址字段，至少其中一个是显式的

相对寻址

方式：隐含引用的寄存器是程序计数器（Program Counter, PC）
- 此指令后续的下一条指令的地址加上地址字段的值产生有效地址
  
  取指周期之后PC就加一了，已经指向了下一条指令的地址
用法：大多数存储器访问都相对靠近正在执行的指令，相对寻址可节省指令中的地址位数
算法： $EA = (PC) + A$
优点：利用程序局部性原理，节省指令中地址的位数

基址寄存器寻址

方式：被引用的寄存器含有一个存储器地址，地址字段含有一个相对于那个地址的偏移量（通常是无符号整数表示）
- 寄存器引用可以是显式的，也可以是隐式的
算法： $EA = (R) + A$
用法：虚拟内存空间中的程序重定位

变址寻址

方式：指令地址字段引用一个主存地址，被引用的寄存器含有对于该地址的一个正的偏移量
算法： $EA = A + (R)$
用法：为完成重复操作提供一种高效机制
扩展：结合间接寻址和变址寻址
- 前变址： $EA = (A + (R))$
- 后变址： $EA = (A) + (R)$

栈寻址

方式：栈指针保存在寄存器中，对寄存器中栈位置的访问实际上是一种寄存器间接寻址方式
解释：与栈相关的是一个指针，它的值是栈顶地址，或者当栈顶的两个元素已在CPU寄存器内，此时栈顶指针指向栈顶的第三个元素

栈

栈（stack）是有序元素组，一次仅能存取它的一个元素

栈顶（top）：存取元素的点
- LIFO
栈底（base）：栈中最后一个元素

栈的操作：push，pop，一元操作（对栈顶元素操作完成后以结果替代栈顶元素），二元操作（取栈顶的两个元素进行操作，结果放到栈顶）

栈的实现

栈基（base）：保存为栈保留的内存块底部位置的地址
栈限（limit）：保存为栈保留的内存块另一端的地址
栈指针（pointer）：保存栈顶的地址
向上/向下增长：向着地址增大/减小的方向增长

栈的应用：表达式求值

指令格式

指令格式通过它的各个构成部分来定义指令的位安排
一个指令格式必须包含一个操作码，以及隐式或显式的、零个或多个操作数
指令格式必须显式或隐式地为每个操作数指定其寻址方式
大多数指令集使用不止一种指令格式

指令格式的设计原则

指令尽量短
- 指令占用存储空间小
有足够的操作码位数
- 要为操作类型不断增加预留
操作码的编码必须有唯一的解释
- 操作码译码时要么是唯一的合法编码，要么是不合法的
指令长度是字节的整数倍
- 与内存按照字节寻址相对应，便于指令的读取和地址计算
合理选择地址字段的个数
- 涉及到指令长度和规整性，是空间和时间开销权衡的结果
指令尽量规整
- 简化硬件实现

指令长度

最明显的权衡考虑是在强有力的指令清单和节省空间之间进行

编程人员希望更多的操作码、更多的操作数、更多的寻址方式和更大的地址范围

指令长度变短可以节省存储空间和减少数据传送时间

指令长度应该是字符长度或定点数长度的整数倍

指令长度应该等于存储器的传送长度（即数据总线宽度），或者这两者的其中之一是另一个的整数倍

位的分配

操作码数目和寻址能力之间存在着权衡考虑

变长的操作码（指令长度固定

使用一个最小操作码长度，但是对于某些操作码，可通过使用指令附加位的方法来指定附加的操作

使用寻址位的考虑因素

寻址方式的种数
操作数的数量
寄存器与存储器比较：能用于操作数引用的寄存器越多，指令需要的位数越少
寄存器组的数目：对于固定数目的寄存器，功能上的分开将使指令只需较少的位数
地址范围
寻址粒度：使用较大的字时，需要的地址位更少

变长指令

提供不同长度的各种指令格式

优点：

易于提供大的操作码清单，而操作码具有不同的长度
寻址方式能更灵活，指令格式能将各种寄存器和存储器引用加上寻址方式予以组合

缺点：

增加CPU复杂程度

取至少等于最长指令长度的几个字节或几个字

指令集设计

设计的基本问题

操作指令表：应该提供多少和什么样的操作，操作有多复杂
数据类型：对哪几种数据类型完成操作
指令格式：指令的位长度、地址数目、各个字段的大小等
寄存器：能被指令访问的寄存器数目以及它们的用途
寻址：寻址方式的种类以及有效地址的计算
下一条指令地址的确定：通常通过PC寄存器来实现