Chapter 1 概论

2023.5 lbw

加*为很可能出题的重点，以当年考试来看，这个提纲中的内容有些过于详细了

寻址 huffman 编码片选 cache 流水线中断

取指令的公共操作：(PC)->MAR；READ；M(MAR)->MDR->IR；(PC)+1->PC

中断的操作：

0->MAR，将特定地址 0 送至 MAR；如果要把断点存入堆栈，则改为 SP->MAR

(PC)->MDR，将 PC 内容送至 MDR

Write，启动存储器写操作

MDR->M(MAR)，将 MDR 的内容写入 MAR 指示的主存单元

向量地址->PC，把向量地址形成部件的输出送入 PC，为转入中断服务程序做准备

0->EINT，关中断，将中断允许触发器清 0

指令并行度为 $(m,n)$ ， $k$ 段流水线的超标量超流水线处理机执行 $N$ 条指令所用的时间为 $\large T(m,n)=(k+\frac{N-m}{mn})\Delta t$ ，加速比为 $\large S(m,n)=\frac{mn(k+N-1)}{mnk+N-m}$

Chapter 1 概论

重点内容：

存储程序概念、计算机硬件组成

计算机系统的层次结构

计算机系统结构的定义及研究对象

计算机系统结构、组成、实现三者的区别与相互联系

计算机系统设计的主要方法（由中间开始设计）

Amdahl 定律和 CPU 性能公式

解决软件可移植性的三种方法

系统结构中的并行性、并行性开发的途径、并行处理系统的结构和多机系统的耦合度

计算机系统的分类方法（弗林分类法）

翻译、解释、计算机系统结构、透明性、软件兼容、模拟、仿真、并行性、系列机、兼容机、时间重叠、紧耦合系统

*存储程序与计算机组成

计算机由==运算器、存储器、控制器、输入设备和输出设备==五大基本部件组成

==存储程序==的基本含义：将编好的程序和原始数据事先存入存储器中，然后再启动计算机工作

计算机系统=硬件系统+软件系统/固件

多级层次结构

现代计算机系统可以看成按功能划分的多级层次结构，如图：

通常第 1, 2 级是由解释的方法实现的；更高级由翻译的方法实现

虚拟机器是指以软件或以软件为主实现的机器

*计算机系统结构、组成和实现

==计算机系统结构==是程序员（机器语言）所看到的计算机的属性，一般包括：数据表示、寻址方式、寄存器组织、指令系统、存储系统组织、中断机构、管态和用户态的定义和切换、机器级 I/O 结构、信息保护方式和保护机构
==计算机组成==是指计算机系统结构的==逻辑实现==，包括：机器级内部的==数据流==、==控制流==的组成和逻辑设计等
==计算机实现==是指计算机组成的==物理实现==，着眼于器件技术和微组装技术

要注意，计算机的组成与实现属于计算机系统的内特性，这些特性对于程序员是==透明==的，即程序员的视角看似乎不存在

同一系统结构可能有多种组成；一种组成可能有多种不同实现

可能会有要去区分系统结构和计算机组成的题目，例如：

指令系统的确定属于系统结构；而指令的实现属于计算机组成；主存地址寄存器也属于计算机组成

区分的关键在于对于程序员是否可见；如果不可见再看他是不是物理的实现

设计思路

软硬件取舍基本原则

性价比：在现有硬件和器件条件下，系统要有高的性价比
组成合理：组成技术要合理
软硬结合：实现时要注意“软硬结合”

基本设计思路

由上向下：从应用开始逐级往下，适合专用机的设计
由下向上：可设计通用计算机，但容易软硬脱节
==从中间开始==：中间一般是指传统机器级与操作系统级之间

计算机设计量化准则

性能指标

机器字长：参与运算的数的基本位数
数据通路宽度：数据总线一次所能并行传送信息的位数
主存容量：主存储器所能存储的全部信息量
- 对于字节编址的机器，一般直接用字节数表示
- 对于字编址的机器，一般用字数 x 字长表示

定量原理

*Amdahl 定律

==系统中对某一部件采用某种更快的执行方式所能获得的系统性能改进程度==

可改进比例 $\large Fe=\frac{可改进部分占用的时间}{改进前整个任务的占用时间} < 1$
性能提高比 $\large Se=\frac{改进前改进部分的执行时间}{改进后改进部分的执行时间} > 1$
改进前任务执行时间 $T_0$
改进后任务执行时间 $T_n$

加速比S_n=\frac{T_0}{T_n}=\frac{1}{(1-Fe)+\frac{Fe}{Se}}

*CPU 性能公式

设程序执行过程中处理的==指令数==为 $IC$
指令时钟数 $\large CPI=\frac{CPU时钟周期数}{IC}$ ，即多少个时钟周期能执行一个指令
如果计算机系统有 $n$ 种指令，其中第 $i$ 种的时钟数为 $CPI_i$ ，在程序中第 $i$ 中指令出现的次数为 $I_i$ ，则有： $\large CPI=\sum\limits_{i=1}^n(CPI_i\times\frac{I_i}{IC})$
$\large IPC=\frac{1}{CPI}$

CPU执行时间=\frac{CPU时钟周期数}{时钟频率}=\frac{指令数\times CPI}{时钟频率}

计算机系统性能标准

吞吐量：系统在单位时间内处理请求的数量
响应时间：系统对请求作出响应的时间

*运算速度

每秒执行百万指令 $\large MIPS=\frac{指令条数}{执行时间\times10^6}=\frac{主频}{CPI\times10^6}$
每秒百万次浮点运算 $\large MFLOPS=\frac{浮点操作次数}{执行时间\times10^6}$

*等效指令速度

因为不同指令所需的执行时间有较大差异，所以通过统计各类指令在程序中所占比例进行折算

设 $W_i$ 为指令使用频度， $i$ 为指令种类：

等效指令执行时间 $\large T=\sum\limits^n_{i=1}(W_i\times T_i)$
等效指令速度 $\large MIPS=1/\sum\limits^n_{i=1}\frac{W_i}{MIPS_i}$
等效 $\large CPI=\sum\limits^n_{i=1}(CPI_i\times W_i)$

性能比较

平均执行时间 $\large S_m=\frac{1}{n}\sum\limits^n_{i=1}T_i$
加权执行时间 $\large A_m=\sum\limits^n_{i=1}(W_i\times T_i)$
归一化执行时间，一般标识为几何平均速度，其与机器无关，与程序的执行时间无关，可以平滑掉样本之间的倍数差异

性能评价

使用评测程序 (Benchmark)来评价计算机系统性能

系统结构影响因素

*软件可移植性

为了节约时间、经济成本，在新的系统中必须要解决软件的可移植性问题，有以下办法：

采用统一的==高级语言==
采用==系列机==，即同一厂家生产的具有相同的系统结构，不同组成和实现的一系列计算机系统

兼容机是不同厂家生产的具有相同的系统结构的计算机系统

系列机与兼容机的区别在于是否是同一厂家生产

向后兼容最重要
采用==模拟==和==仿真==，在一台现有的计算机上实现另一台计算机的指令系统
- 模拟：指用==软件==的方法在一台现有的计算机 A 上实现另一台计算机 B 的指令系统
- 仿真：指用一台现有计算机 A 上的微程序去解释实现另一台计算机 B 的指令系统
- 模拟和仿真的区别在于模拟使用机器语言解释，仿真使用微程序解释
- 模拟慢，仿真快；模拟在主存中，仿真在控存中；差别大的机器很难用仿真实现

器件

应用

并行性

概念

*并行性含义

并行性包含以下二重含义：

==同时性==：两个或多个事件在同一时刻发生
==并发性==：两个或多个事件在同一时间间隔内发生

并行性等级

从数据处理的并行性来看，由低到高可以分为：

位串字串
位并字串
位片并字串
全并行

从信息加工的角度看，又可分为：

存储器操作并行：如一个存储周期内访问多个字
处理器操作步骤并行：流水线处理机
处理器操作并行：阵列处理机
指令、任务、作业并行：多处理机

*并行开发途径

==时间重叠==：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周期而赢得速度。流水线处理机常使用这种方法
==资源重复==：在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。阵列处理机会通过资源重复，设置大量算数逻辑单元，以实现空间上的并行
==资源共享==：利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高利用率，这样也可以提高整个系统的性能。多处理机主要采用这种方法

耦合度

耦合度：反映多机系统中各机器之间物理连接的紧密程度和交叉作用能力的强弱

可以分为：

最低耦合，各计算机之间无物理连接，如脱机处理系统
松散耦合，多台计算机通过通道或通信线路实现互联，如外设
紧密耦合，多台计算机通过总线或高速开关互联

计算机的分类

Flynn 分类法

按照指令流和数据流的多倍性特征对计算机系统进行分类

单指令流单数据流 SISD：每次只译码一条指令，并操作一个数据

一般的单处理机
单指令流多数据流 SIMD：一条指令操作多数据

阵列机、并行处理机、向量处理机
多指令流单数据流 MISD：多条指令并行处理同一数据

超标量，超长指令字计算机
多指令流多数据流 MIMD：能实现作业、任务、指令各级全面并行的系统

Chapter 2 数据表示和指令系统

数据表示

传统机器数据表示：

传统机器数据表示：

定点数：原码、反码、补码、移码

浮点数：尾数、基数和阶码。IEEE 754 标准

字符：常用 ASCII 码

汉字：输入码，汉字内码，汉字字模码

高级数据表示：自定义的数据表示，向量数据表示、堆栈数据表示

数据校验原理：奇偶校验码

数据表示和数据结构

==数据表示==是指计算机硬件能够直接识别和处理的数据类型和格式，称为操作数的物理属性或操作数的表示。如定点、逻辑、浮点、十进制、字符、字符串、堆栈和向量等。
==数据结构==反映面向应用所要用到的各种数据元素或信息单元之间的结构关系，称为操作数的逻辑属性或操作数类型。如位图、表、树、阵列、队列、链表、栈、向量、字符、字符串、实数、整数、布尔数等。

数据表示和数据结构都是==数据类型==的子集

无符号数

字长 $n+1$ 位，则无符号数的表示范围为 $[0,2^{n+1}-1]$

后面若无特殊说明，则字长默认为 $n+1$ 位

有符号数

原码：最高位为符号位，其余位为绝对值，取值范围为 $[1-2^n,2^n-1]$
反码：正数时与原码一样，负数时为除符号位按位取反
补码：正数时与原码一样，负数时为除符号位取反后再加 1，取值范围 $[-2^n,2^n-1]$

在原码和反码中，真值 0 都有两种不同的表示形式；但在补码中只有一种，这使得补码可以表示的负数比正数多一个

对于一个负数补码数，其值就等于除符号位所表示的值减去 $2^n$ 。如 1011 除符号位表示的值为 3，那么其补码值为 $3-8=-5$

定点数

小数点的位置固定在最高有效数位之前，符号位之后，所以是纯小数。表示范围（机器字长为 $n+1$ ）：

原码/反码定点小数： $[2^{-n}-1,1-2^{-n}]$
补码定点小数： $[-1,1-2^{-n}]$ (补码表示为 100... 时取值为-1)

*浮点数

浮点数表示

用 $V=M\times2^E$ 表示一个浮点数：

尾数 $M$ 为纯小数，可以用原码或补码表示
阶码 $E$ 是给浮点数指定 $2^E$ 权重，可以用补码或移码表示

浮点数的规格化

一个规格化的浮点数，其尾数用补码表示时，其尾数的第一位和第二位必须不同，即为 1.0 xxxx 或 0.1 xxx 形式，这样保证值在 (0.5,1)和 (-1,-0.5)

若阶码和尾数都用设阶码为 $k+1$ 位，尾数为 $n+1$ 位，浮点数典型值如下：

	阶码	尾数	真值
最大正数	011... 1	011... 1	$(1-2^{-n})2^{2^k-1}$
绝对值最大负数	011... 1	100... 0	$-2^{2^k-1}$
最小正数	100... 0	00... 01	$2^{-(n+2^k)}$
规格化的最小正数	100... 0	010... 0	$2^{-2^k-1}$
绝对值最小负数	100... 0	111... 1	$-2^{-n-2^k}$
规格化的绝对值最小负数	100... 0	101... 1	$-(\frac{1}{2}+2^{-n})2^{-2^k}$

阶码的移码表示

移码表示的阶码，最终的阶码值 E 要减去一个 Bias，这个 Bias 的取值在 IEEE 单精度中为 127，双精度为1023

若阶码采用移码表示，则有以下特点：

浮点数的最高位代表浮点数的正负
移码全为 0 时，对应真值最小；移码全为 1 时，对应真值最大
阶码越大，则浮点数越大

IEEE 浮点数

默认采用移码表示，尾数为补码且取值范围为[1.0-2)，由于首位总是 1，所以将其省略。若尾数值为 1.101，则尾数只需表示 0.101 即可

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

1 位	k 位	n 位
$s$	$e_{k-1}...e_1e_0$	$f_{n-1}...f_1f_0$

最高位是一个单独的符号位 $s$ 编码符号
$k$ 位的阶码字段 $exp=e_{k-1}...e_1e_0$ 编码阶码 $E$
$n$ 位小数字段 $frac=f_{n-1}...f_1f_0$ 编码 M

	s	exp	frac
单精度	1	8	23
双精度	1	11	52
扩展精度	1	15	64

IEEE 示例（来源： https://www.geeksforgeeks.org/ieee-standard-754-floating-point-numbers/ ）：

以 85.125 为例：

85 = 1010101
0.125 = 0.001
85.125 = 1010101.001
       = 1.010101001 × 2^6

符号位 sign = 0

1. 单精度：
阶码使用偏置表示，偏置值为 127，因此：
biased exponent = 127 + 6 = 133
133 = 10000101

规格化后的尾数为 010101001
后面补 0，直到小数字段达到 23 位

因此 IEEE 754 单精度表示为：
= 0 10000101 01010100100000000000000
写成十六进制为 42AA4000

2. 双精度：
阶码使用偏置表示，偏置值为 1023，因此：
biased exponent = 1023 + 6 = 1029
1029 = 10000000101

规格化后的尾数为 010101001
后面补 0，直到小数字段达到 52 位

因此 IEEE 754 双精度表示为：
= 0 10000000101 0101010010000000000000000000000000000000000000000000
写成十六进制为 4055480000000000

汉字表示

汉字输入码：包括数字码、拼音码、字形码，用于输入汉字
汉字机内码：通过不同输入码输入的汉字，其在计算机内部的表示是唯一的
汉字字模码：用于汉字在计算机上的显示

汉字机内码=汉字国标码+8080H=区位码+A0A0H

高级数据表示

引入一些高级数据表示，有时有利于机器的计算。有以下几种高级数据表示：

自定义数据表示
向量数据表示
堆栈数据表示

自定义数据表示

在高级语言中，运算符不反映参与计算的数据类型，比如两个 int 类型的变量或者两个 double 类型的变量之间都可以用+进行加法运算；但是机器语言程序中的指令要用==操作码==指明操作数的类型，比如两个整形数的加法和两个浮点数的加法是完全不同的指令

如上所述的情况给高级语言到机器语言的编译带来了非常大的不方便，为了解决这个问题，引入两种解决方法：

1. 带标志符的数据表示

让每个数据都带有类型标志，将数据类型与数据本身直接联系在一起，使机器语言中的操作码与高级语言中的运算符一致。标志符由编译器或其他系统软件建立，对程序员透明

优点：

提高了操作码的通用性，简化了指令系统和程序设计
简化了指令系统和程序设计
便于实现一致性检查，可由硬件直接快速地检测出多种程序错误
能够由硬件自动完成数据类型转换
支持了数据库系统的实现与数据类型无关的要求
为软件调试和开发提供了支持

缺点：

每个数据字因增设标志符，可能会使程序所占用的主存空间增加
采用标志符会降低指令的执行速度，以换取程序的设计时间、编译时间和调试时间缩短
数据和指令的长度可能不一致
硬件复杂度增加

2. 数据描述符

对于向量、数组、记录等多维或结构复杂的数据，由于每个元素具有相同属性，没有必要让每个数据都带标志符，而是将它们的属性组织为==描述符==，与数据分开存放

因为描述符与数据分开，所以在访问数据时要先访问描述符寄存器，也就多一层寻址

优点：

将描述符按树形连接可以描述多维数组
为向量、数组等数据结构的实现提供了一定的支持

向量数据表示

为实现向量、数组数据结构的快速运算，可以增设向量数据表示

比如原来需要用很多加法指令实现的向量加法，在引入向量数据表示后可用一条指令完成：

可以快速形成元素地址，实现数据块的预取

堆栈数据表示

堆栈有两种类型：

寄存器堆栈：用一组专门的寄存器构成，又称为硬堆栈

栈顶固定，各寄存器相互连接，自动推移（联想 80386 汇编中的浮点数寄存器）
存储器堆栈：从主存中划出一段区域来作堆栈，这种堆栈又称为软堆栈

栈底固定，栈顶浮动，所以需要一个专门的硬件寄存器作为栈顶指针

具有堆栈数据表示的机器称为堆栈机器

随堂练习：

确定数据表示

应坚持以下原则：

缩短程序的运行时间
减少 CPU 与主存之间的通信量
通用性和利用率要高

数据校验原理

数据校验码：能够发现错误或能够自动纠正错误的数据编码

编码最小距离：任意两组合法代码之间二进制位数的最少差异

L-1=D+C(D\ge C)

其中 $L$ 是编码最小距离； $D$ 是检错的位数； $C$ 是纠错的位数

奇偶校验

可以检测出一位（或奇数位）错误，奇偶校验码的码距等于 2

奇校验：整个校验码（包含有效信息位和校验位）中 1 的个数为奇数
偶校验：整个校验码中 1 的个数为偶数

交叉奇偶校验

不仅每一个字节有一个奇偶校验位做==横向校验==，而且全部字节的同一位也设置一个奇偶校验位做==纵向校验==

交叉校验可以发现两位同时出错的情况

数据计算

串行、并行加法器、溢出判断与检测、移位操作
乘法电路基本结构：BOOTH 乘法器（1 位）
除法电路基本结构：加减交替除法器（补码）
逻辑运算：与、或、非、异或运算
运算器基本结构

加法运算

全加器

全加器结构如图：

S_i= A_i\oplus B_i\oplus C_{i-1}=P_i\oplus C_{i-1}\\ C_i=A_iB_i+(A_i\oplus B_i)C_{i-1}=G_i+P_iC_{i-1}\\ G_i=A_iB_i\\ P_i=A_i\oplus B_i

其中，进位产生函数用 $G_i$ 表示，进位传递函数用 $P_i$ 表示

串行加法器：只有1 个全加器，数据逐位串行送入加法器进行运算
并行加法器：由多个全加器构成，位数的多少取决于机器的字长

并行加法器

并行加法器又能细分为两种：

n 位行波进位加法器：全加器的简单堆叠
超前进位加法器（BCLA）：每个进位都不需要等待低位，直接计算可以得到

n 位行波进位加法器虽然结构简单，但是有个致命的缺点：随着全加器的堆叠，全加器的==延迟也叠加==了，每个全加器都要等待前一个全加器的计算结果。若生成每一级进位的延迟为 $2ty$ ，那么 $n$ 位的延迟则为 $2nty$

为了解决这一问题，可以使用超前进位加法器，他与前者的区别是他用更复杂的逻辑表达来直接计算结果的每一位。这样确实大大降低了延迟，但是如果加法位数多，那么高位进位的逻辑表达式将相当复杂，这也会使得全加器的设计变得非常棘手。为解决这一问题，引入了==先行进位==方式：

单级先行进位方式：组内并行，组间串行

比如 16 位加法器可以分为 4 组，每组实现 4 位超前进位加法器，之后串行得到 16 位加法器。这样的加法器相对串行加法器仅有 4 倍延迟
多级先行进位方式：组内并行，组间并行

如下面的多级先行进位加法器：第一个周期计算出来所有的 G 和 P 和最低 4 位的加法结果；第二个周期使用 G 和 P 计算出所有的进位 C，包括 $C_4,C_8,C_{{12}}$ ；最后一个周期用所有的进位 C 和输入计算得到最终的结果

定点数运算

有以下规则：

操作数以补码表示
符号位也参与运算
做加法则两数直接相加；做减法则与减数的==机器负数==相加
运算结果用补码表示

机器负数：连同符号位的所有位取反，末尾加 1

溢出判断

设操作数为 $X$ 和 $Y$ ，进位为 $C$ ，计算结果为 $S$

一个符号位判断： $\overline X_s\overline Y_sS_s+X_sY_s\overline S_s$
进位位判断： $C_s\oplus C_1$
==变形补码==判断： $S_{s1}\oplus S_{s2}$

$S_{s1}$ 是原来的符号位， $S_{s2}$ 是计算时扩充的符号位，对于 $X$ 来说 $X_{s1}=X_{s2}$ ，就是把原来的符号位再复制一位。若 $S_{s1}S_{s2}$ 为 00 或 11，则无溢出；01 为正溢，10为负溢

乘法运算

补码一位乘法——Booth 乘法

寄存器占用：

A 寄存器：部分积与最后乘积的高位部分，初值为0
B 寄存器：被乘数 X
C 寄存器：乘数 Y，运算后 C 寄存器中不再需要保留乘数，改为存放乘积的低位部分

乘法步骤：

符号位参与运算
乘数 Y 最低位后面增加一位附加位 $Y_{n+1}$ ，初值为0

由于每求一次部分积要右移一位，所以乘数的最低两位 $Yn$ 、 $Yn+1$ 的值决定了每次应执行的操作:

判断位 $Y_nY_{n+1}$	操作
0 0	原部分积加 0；右移一位
0 1	原部分积加 $X$ ；右移一位
1 0	原部分积加 $-X$ ；右移一位
1 1	原部分积加 0；右移一位

移位按==补码右移==规则进行，共需做 $n+1$ 次累加， $n$ 次移位（把首位移到原来的末位就不再移位了）

除法运算

加减法交替除法：

第一次操作：

$[X]_补$ 与 $[Y]_补$	操作
同号	$[X]_补+[-Y]_补$
异号	$[X]_补+[Y]_补$

$[r_i]_补$ 与 $[Y]_补$	上商	求新余数的操作
同号	1	左移一位；加 $[-Y]_补$
异号	0	左移一位；加 $[Y]_补$

一共左移 $n$ 次，第一次得到的商移位到最左侧即停止，商的末位恒置1

寄存器使用情况：

A 寄存器：存放被除数 X，不断变化最后为余数
B 寄存器：存放除数 Y
C 寄存器：存放商 Q，它的初值为0

浮点运算

以下浮点运算默认语境为阶码和尾数都用补码表示

浮点加减

对阶：先求阶差，然后小阶向大阶看齐，小阶尾数每右移一位，阶码+1
尾数加减：若尾数用双补码表示，计算得到结果可能有 6 种，之后要根据不同的情况进行规格化或溢出判断

00.1 xxx	11.0 xxx	00.0 xxx	11.1 xxx	10. xxxx	01. xxxx
已规格化	已规格化	进行左规	进行左规	进行右规	进行右规

左规：尾数每左移 1 位，阶码-1；一直左规，直至成为规格化数为止
右规：尾数右移 1 位，阶码+1；右规仅进行这一次

之后判断是否溢出：

若阶码为 01. xxx，此时发生上溢，需做溢出中断处理
若阶码为 10. xxx，此时发生下溢，不做溢出处理，认为该数为机器 0

浮点乘法

阶码相加
尾数相乘
尾数结果规格化（可能需要一次左规）

浮点除法

尾数调整：若 $|M_A|\ge|M_B|$ ，则 $M_A$ 需要右移一位，阶码+1
阶码相减
尾数相除

逻辑运算

逻辑非、逻辑乘、逻辑加、按位异或

运算器

运算器的组成为：

实现基本算数、逻辑运算功能的 ALU
提供操作数与暂存结果的寄存器组
判别逻辑和控制电路

指令系统

寻址技术

寻址技术：寻找操作数及其他信息的地址的技术

主要研究三个方面的内容：编址方式、寻址方式和定位方式

编址单位与编址方式

编址有不同的单位：字、字节、位、块等

编址单位

==字编址==：编址单位=访问单位
==字节编址==：为了适应非数值计算而产生，编址单位＜访问单位

字节编址引入了字节顺序问题，对应的解决方案是大端法和==小端法==；小端模式地址转换方便，容易进行高精度的运算

字节编址还引入了对齐问题，一般采取==边界对齐==

编址方式

==分类编址==：将部件适当分类，通用寄存器、主存和 IO 每类各自从“0”开始编址
统一编址：把各种部件统一编成一个从 0 开始的一维线性空间
隐含编址：采用事先约定的编址方式寻址，比如堆栈、专用寄存器和 Cache 常采用这种方法，这样不需要进行地址计算

寻址方式

寻址方式：指令寻找到所需数据的方法

显式寻址：在指令中设置专门的寻址方式字段，用二进制代码来表明寻址方式类型
隐式寻址：由指令的操作码字段说明指令格式并隐含约定寻址方式

立即数寻址、寄存器寻址、主存储器寻址、堆栈寻址。其中主存寻址包括直接、间接或变址寻址。

常见寻址方式中，A 表示指令中的形式地址或立即数字段，EA 表示有效地址，M[A] 表示主存地址 A 中的内容，R[i] 表示第 i 个寄存器的内容。

寻址方式	原理	有效地址/操作数	除取指外访问主存次数	特点
立即寻址	操作数直接放在指令中	操作数 `= A`	0	速度快，但操作数范围受指令中立即数字段限制
寄存器寻址	指令给出寄存器编号，操作数在寄存器中	操作数 `= R[i]`	0	速度快，指令中只需寄存器编号，但可直接指定的操作数个数受寄存器数量限制
直接寻址	指令地址码直接给出操作数所在主存地址	`EA = A`，操作数 `= M[EA]`	1	简单直观，但寻址范围受地址码位数限制
间接寻址	指令地址码指向一个主存单元，该单元内容才是操作数地址	`EA = M[A]`，操作数 `= M[EA]`	2；多级间址需要更多次	可扩大寻址范围，但速度慢、过程复杂
寄存器间接寻址	指令给出寄存器编号，寄存器中存放操作数地址	`EA = R[i]`，操作数 `= M[EA]`	1	比主存间接寻址快，寻址范围由寄存器位数决定
变址寻址	形式地址与变址寄存器内容相加得到有效地址	`EA = A + (Rx)`	1	适合数组、字符串等成批数据访问
基址寻址	基址寄存器内容与位移量相加得到有效地址	`EA = (Rb) + D`	1	适合程序重定位，面向系统
相对寻址	程序计数器 `PC` 内容与位移量相加得到有效地址	`EA = (PC) + D`	1	适合转移指令，程序可浮动存放

间址 vs 变址

间接寻址和变址寻址都是为了解决操作数地址的修改问题，都能做到不改变程序而修改操作地址

	间址寻址	变址寻址
地址位置	主存	基址寄存器
偏移量	无	有
优缺点	容易但慢	麻烦但快
对数组的支持	差	好

定位方式

逻辑地址：程序员编写程序时所使用的地址
物理地址：程序在主存中的实际地址

因为逻辑地址空间和物理空间是不一致的，所以需要进行逻辑地址到实际地址的转换。有三种定位方法：

直接定位：在程序装入主存之前，物理地址就已确定，很少用
静态重定向：程序装入主存的过程中进行地址变换
动态重定向：程序执行的过程中进行地址变换

指令格式及优化

一条指令由==操作码==和==地址码==构成

指令格式的设计有两个主要目标：

节省程序的存储空间
指令格式尽量规整，便于译码

为了达成这两个目标，我们主要研究操作码和地址码的优化表示

操作码

指令操作码可以按编码方式分为两类：

规整型：定长编码
非规整型：变长编码，如==扩展操作码==：操作数地址多的指令操作码短，操作数地址少的操作码长

操作码优化

在足够表达所有指令的前提下，使操作码占用的位数最少

==Huffman 编码==

依托于 Huffman 树，回看数据结构，这里只给出一些数学相关：

信息源熵（最短平均长度）：

H=-\sum\limits^n_{i=1}p_i·\log_2p_i

其中， $p_i$ 为指令 $I_i$ 的使用频度

信息冗余量：

R=1-\frac{H}{实际平均码长}

采用 Huffman 编码的实际平均码长最短，但是具体码值不唯一，操作码长度不规则，并且难以组成定长的指令

在构建 Huffman 树的时候，要注意短码不能是长码的前缀

Huffman 树虽然信息冗余量是所有编码方式中最低的，但是编码不规整，译码不方便

==扩展编码==

有以下特点：

操作码长度不固定，但只有有限的几种长度
使用频度高的指令用短操作码表示，使用频度低的指令用长操作码表示 (哈夫曼压缩思想)

比如 2-4 扩展编码就是将概率高的用 2 位表示，概率低的用 4 位表示

地址码优化

我们希望寻址范围大，但还不想要地址码长度太宽，就要想想办法——==变长地址码==：对于操作码不同长度的指令可以采用多种地址长度

优化总结

选择合适的编码方式缩短操作码的平均码长
采用多种寻址方式来缩短地址码长度
采用多种地址制增强指令功能，缩短程序长度
在同种地址制内采用多种地址形式，让长操作码与短操作码组配
使用多种不同的指令长度

指令系统的发展

CISC&RISC

现有的指令集有两个大类，分别是 CISC 和 RISC

CISC：进一步增强原有指令的功能以及设置更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化
- 指令数量多且指令长度不固定，指令格式和寻址方式多样
- 一些指令涉及存储器读写
- 采用微程序控制
RISC：通过减少指令种类和简化指令功能来降低硬件设计的复杂度，提高指令的执行速度
- 指令数量少且指令长度固定
- 大部分采用 RR 寻址
- 采用组合逻辑控制

RISC 的设计原则

指令系统只使用频度高的指令（加上少量其他有用的指令）；大多数指令在单周期内完成；LOAD/STORE 结构；硬布线控制逻辑，以提高指令执行速度；减少指令和寻址方式的种类；注重编译优化技术

指令系统的设计方向

CISC 设计方向：增强指令功能；设置功能复杂的指令面向目标代码、高级语言和操作系统；用一条指令代替一串指令

RISC 设计方向：只保留功能简单的指令；功能较复杂的指令用子程序来实现；减少 CPI

RISC 的精华就是==减少 CPI==

设计 RISC 的关键技术

==重叠寄存器窗口==：可以减少大量主存访问操作

设置一个数量比较大的寄存器堆，并把它划分给很多个窗口。在每个过程使用的几个窗口中有一个窗口是与前一个过程共用，还有个窗口是与下一个过程共用
==延迟转移==：使指令流水线不断流

在转移指令之后插入一条没有数据相关的有效的指令，而转移指令被延迟执行，这种技术称为延迟转移技术；指令序列的调整由编译器进行
==指令取消==：延迟转移技术在很多情况下找不到可以用于调整的指令，所以有些 RISC 采用指令取消技术，分为三种情况：
- 向后转移（循环程序）
- 向前转移（if-then）
- 隐含转移
==指令流调整==：通过变量重新命名消除数据相关，提高流水线执行效率

Chapter 3 存储器层次结构

存储系统概念和层次化结构

为了解决存储容量、存取速度和价格之间的矛盾，我们一般将不同的存储器按一定体系结构组织起来

按存储器在计算机中的作用，可分为：

高速缓冲存储器 Cache
主存储器
辅助存储器

按存取方式，可分为：

随机存取存储器 RAM：对任意存储单元的读写时间相同
只读存储器 ROM：可以看作 RAM 的一种特殊方式，只能读出不能写入
顺序存取存储器 SAM：只能顺序存取，存取时间与信息在存储体上的物理位置有关
直接存取存储器 DAM：先定位到存储器某个小区域，再在该区域内顺序检索

按存储介质，可分为磁芯存储器、半导体存储器、磁表面存储器（磁盘，磁带）、光存储器（光盘）等；按信息保存性，可分为易失性存储器和非易失性存储器。若读出操作会破坏原存储信息，则称为破坏性读出，读后需要重写。

局部性原理

时间局部性：最近访问的存储单元在不久的将来仍将被访问
空间局部性：下次访问的存储单元很可能在最近访问的存储单元附近

主存储器的组织和控制

主存储器是整个存储系统的核心，它用来存放计算机运行期间所需要的程序和数据，CPU 可直接随机地对它进行访问。主存由存储体、地址译码和驱动电路、I/O 和读写电路等构成：

其中：

存储体是主存储器的核心，存放程序和数据
地址译码和驱动电路负责将地址总线输入的地址码转换成选中信号，并提供读写所需的驱动电流
I/O 和读写电路负责完成数据输入、输出以及读写控制

存储单元与字节顺序

需要区分几个概念：

位：二进制信息的基本单位
记忆单元：存放 1 位二进制信息的物理器件
存储字：作为整体存入或取出的一组二进制位
存储单元/主存单元：CPU 可访问操作的最小主存单位，存放一个存储字或一个存储字节

编址方式不同，存储单元大小也不同：

字节编址：最小寻址单位是 1 字节
字编址：最小寻址单位是 1 个字

字节编址会引入字节顺序问题：

大端方案：高字节存放在低地址处（人阅读顺序）
小端方案：高字节存放在高地址处

例如存放 0x12345678：

大端：
低地址 --------------------> 高地址
0x12 | 0x34 | 0x56 | 0x78

小端：
低地址 --------------------> 高地址
0x78 | 0x56 | 0x34 | 0x12

主存中数据存放方式

在按字节编址的机器中，指令系统常支持不同长度的数据，如字节、半字、单字、双字等。若数据可以从任意地址开始紧挨存放，则最节省空间，但可能跨越存储字边界，导致一次数据读写需要多个存取周期。

常见存放方式有：

紧挨存放：不浪费存储空间，但读写效率低
从存储字起始位置存放：每个数据都从一个存储字边界开始，访问快但空间浪费大
边界对齐：让不同长度数据按自身长度对齐，兼顾空间利用率和访问效率

边界对齐规则：

数据类型	长度	第一个字节地址要求
字节	8 位	任意地址
半字	16 位	地址为 2 的整数倍，即最低 1 位为 `0`
单字	32 位	地址为 4 的整数倍，即最低 2 位为 `00`
双字	64 位	地址为 8 的整数倍，即最低 3 位为 `000`

边界对齐可以保证一个数据尽量不跨越相应的存储字边界，从而在单个存取周期中完成读写。

技术指标

存储容量

存储容量是指主存所能容纳的二进制信息总量

假设某计算机容量为 $64K\times16$ ，表示他有 $64K$ 个字，每个字的字长为 16位

存取速度

存取时间 $T_a$ ：从启动一次存储器到完成该操作所经历的时间
存取周期 $T_m$ ：进行一次完整的读写操作所需的全部时间，即连续两次访问存储器操作之间所需要的最短时间

主存带宽

表示每秒从主存进出信息的最大数量

B_m=主存等效工作频率\times主存位宽\div8 \\ =内存时钟频率\times倍增系数\times主存位数\div8

以 DDR 400 内存为例，它的运行频率为 200 MHz，数据总线位数为 64 bit，由于上升沿和下降沿都传输数据，因此倍增系数为2

此时带宽为： $200×2×64/8＝3.2GB/s$

主存分类

主存储器通常分为 RAM 和 ROM 两大部分：RAM 可读可写，ROM 只能读不能写

RAM

记忆单元是存放 1 位二进制信息的物理器件，地址码相同的多个记忆单元构成一个存储单元。

SRAM：存储电路以==双稳态触发器==为基础，不需要刷新，存取速度较快，功耗和成本较高，常用作 Cache
DRAM：存储电路以==电容==为基础，需要刷新，集成度高、功耗小、成本低，常用作大容量主存

*DRAM 的刷新

DRAM 为了维持 MOS 型动态记忆单元的存储信息，每隔一定时间必须对存储体中的所有记忆单元的栅极电容补充电荷，这个过程就是==刷新==。

刷新和重写（再生）是两个不同概念：

重写是随机发生的，某个存储单元只有在破坏性读出之后才需要重写，一般按存储单元进行。
刷新是定时发生的，即使许多记忆单元长期没有被访问，若不及时补充电荷，信息也会丢失。刷新通常以存储体矩阵中的一行为单位进行。

刷新==按行定时进行==，常见的刷新方式包括：==集中式==、==分散式==和==异步式==。

集中式刷新：在允许的最大刷新间隔内，按照存储芯片容量的大小集中安排若干个刷新周期，刷新时停止读写操作。

刷新时间=存储体矩阵行数\times刷新周期

这里的刷新周期是指刷新一行所需要的时间。由于刷新过程类似一次“假读”过程，所以刷新周期通常等于存取周期。

集中式刷新会形成一段 CPU 不能访存的连续时间，称为==死区==。例如对 $32\times32$ 矩阵的存储芯片刷新，最大刷新间隔为 $2ms$ ，存取周期为 $0.5\mu s$ ，则 $2ms$ 内共有 $4000$ 个存取周期，需要集中安排 $32$ 个刷新周期：

32\times0.5\mu s=16\mu s

因而可用于读/写操作的周期为 $3968$ 个，最后 $32$ 个周期为刷新死区。

分散式刷新：把刷新操作分散到每个存取周期内进行。此时系统的存取周期被分为两部分，前一部分进行读/写操作或保持，后一部分进行刷新操作；一个系统存取周期内刷新存储矩阵中的一行。

分散式刷新没有死区，但是缺点也明显：
- 加长了系统存取周期。例如存储芯片的存取周期为 $0.5\mu s$ ，则系统存取周期变为 $1\mu s$ ，整机速度降低。
- 刷新过于频繁。例如 $32$ 行每 $1\mu s$ 刷新一行，则每 $32\mu s$ 就把全部行刷新一遍，没有充分利用允许的最大刷新间隔 $2ms$ 。
异步式刷新：可以看成集中式和分散式的结合。它充分利用最大刷新间隔时间，把刷新操作平均分配到整个最大刷新间隔时间内进行。

相邻两行的刷新间隔=\frac{最大刷新间隔时间}{行数}

例如对 $32\times32$ 矩阵，在 $2ms$ 内需要把 $32$ 行刷新一遍，则相邻两行刷新间隔为：

\frac{2ms}{32}=62.5\mu s

即每隔 $62.5\mu s$ 安排一个刷新周期，刷新时封锁读/写。异步刷新虽然也有死区，但每次死区只有一个刷新周期，如 $0.5\mu s$ ，比集中刷新方式的连续死区小得多，可以避免 CPU 连续等待过长时间，是比较实用的一种刷新方式。

最大刷新间隔是随内存技术发展变化的数值。教材计算通常默认采用 $2ms$ ；现行可查的 DDR 系列内存最大刷新间隔可达到 $64ms$ 。

MOS 型 DRAM 刷新控制要点：

刷新对 CPU 是透明的。
刷新通常一行一行地进行，每一行中各记忆单元同时被刷新；刷新操作时只需要行地址，不需要列地址。
刷新操作类似于读出操作。
因为所有芯片同时被刷新，所以在考虑刷新问题时，应当从==单个芯片==的存储容量着手，而不是从整个存储器的容量着手。

ROM

ROM 具有非易失性，即使断电 ROM 中存储的信息也不会消失

常见 ROM 类型：

掩膜式 ROM（MROM）：厂家写入，用户不能改写
一次可编程 ROM（PROM）：用户可写入一次，之后不能改写
可擦除可编程 ROM（EPROM）：可擦除并多次改写
闪速存储器（Flash Memory）：非易失，可在线快速擦除和重写

*主存设计

要解决三个问题：芯片的选用、片内地址分配与片选逻辑、信号线的连接

RAM 芯片分析

RAM 芯片主要外引脚包括：

地址线 $A_i$ ：选择片内存储单元
数据线 $D_i$ ：传送读出或写入的数据
片选线 CS：选择该芯片是否参加本次读写
读写控制线 WE/OE：控制读操作或写操作

若芯片容量为 $2^m\times n$ 位，则通常需要 $m$ 根地址线和 $n$ 根数据线。CPU 访问主存时先进行片选，再在被选芯片内部进行字选。

扩展

==位扩展==：在位数方向扩展，即加大字长。连接方式是将各存储芯片的地址线、片选线和读/写线相应地并联起来，而将各芯片的数据线单独列出

如 8 个 $64K\times1$ 的 SRAM 芯片组成 $64K\times8$ 的存储器：
==字扩展==：仅在字数方向扩展，而位数不变。字扩展将芯片的地址线、数据线、读/写线并联，由片选信号来区分各个芯片

如用 4 个 $16K\times8$ 的 SRAM 组成 $64K\times8$ 的存储器：

一般来说为了构成一个容量较大的存储器，位扩展和字扩展方法都会使用到，如 $16K\times4$ 组成 $64K\times8$ 的存储器：

地址译码方式

地址译码电路将地址信号翻译成存储单元选择信号，常见方式有：

单译码方式（字选法）：容量为 $M$ 个字、每字 $b$ 位的存储器可排列成 $M\times b$ 的矩阵，每一行对应一个字，由一条字线选中。结构直观，但字线多，只适合容量不大的存储器。
双译码方式（重合法）：把 $K$ 位地址码分成接近相等的两段，一段作为 $X$ 地址线，另一段作为 $Y$ 地址线，分别译码后在存储体内交叉选中记忆单元。大容量存储器通常采用这种方式。

片选

片选要做的事情就是把地址线送来的地址信号翻译成对应存储芯片的选择信号。

线选法

用除片内寻址外的高位地址线直接分别接至各个存储芯片的片选端，当某地址线信息为 0 时，就选中对应的存储芯片，比如一个由 4 个 $2k\times8$ 芯片构成的 $8k\times8$ 的存储器：

芯片	$A_{14}～A_{11}$	$A_{10}～A_0$	地址范围
0 号	1110	00... 0~11... 1	7000~77 FF H
1 号	1101	00... 0~11... 1	6800~6 FFF H
2 号	1011	00... 0~11... 1	5800~5 FFF H
3 号	0111	00... 0~11... 1	3800~3 FFFH

全译码法

全译码法将片内寻址外的全部高位地址线作为地址译码器的输入，把经译码器译码后的输出作为各芯片的片选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择。如：

芯片	$A_{12}～A_{11}$	$A_{10}～A_0$	地址范围
0 号	00	00... 0~11... 1	0000~07 FF H
1 号	01	00... 0~11... 1	0800~0 FFF H
2 号	10	00... 0~11... 1	1000~17 FF H
3 号	11	00... 0~11... 1	1800~1 FFFH

使用全译码法，每片芯片的地址范围是唯一确定的而且是连续的，便于扩展

部分译码法

部分译码法只用片内寻址外的一部分高位地址线译码产生片选信号，线路比全译码法简单，但可能使某一存储单元对应多个地址，这称为地址重叠。

如何判断地址覆盖？

以上面的全译码法举例：若地址线位数有 20 位，但是只用到了 13 位，那就出现地址覆盖；若地址线位数也恰好是 13 位，那么就没有地址覆盖

主存和 CPU 的连接

主存和 CPU 的硬连接主要通过三组总线：

地址总线 AB：由 CPU 送出地址，经 MAR 指向主存单元
数据总线 DB：在 CPU 和主存之间传送数据，经 MDR 暂存
控制总线 CB：传送读、写、片选、完成信号等控制信息

CPU 中的 MAR 和 MDR 是 CPU 与主存交互的关键接口。

读操作的基本过程：

地址 -> MAR -> AB
Read
Wait for MFC
M(MAR) -> DB -> MDR

写操作的基本过程：

地址 -> MAR -> AB
数据 -> MDR -> DB
Write
Wait for MFC
MDR -> M(MAR)

习题

➢（1）芯片组的容量为1KB，地址范围为000H~~3FFH，地址线数目为10 根（A9~~A0）。 ➢（2）根据图中所示连线，各芯片组的片选端由地址线A15、A14进行译码。芯片组内地址线为A9~~A0；A13~~A10空闲，即为任意态。假设A13~~A10 为全0，则4KB RAM的寻址范围分别如下：第0组：0000H~~03FFH；第1组：4000H~~43FFH；第2组：8000H~~83FFH；第3组：C000H~~C3FFH。这4KB存储器的地址空间是不连续的。 ➢（3）由于A13~~A10没有参与译码，所以有重叠。

Cache

高速计算机的性能通常受到主存带宽和响应时间的限制：

响应时间：一次访存所需要的时间
带宽：单位时间内的访存次数

而因为 cpu 的发展速度远快于 DRAM 的发展速度，带来了“CPU-主存瓶颈”；为解决这一问题，就在 CPU 和主存之间添加 Cache：

Cache 的基本结构

访问主存时，先访问 Cache：

若命中，则直接访问 Cache
若不命中，则访问主存，将字送往 CPU，并把包括该字在内的一整块都装入 Cache

地址的映像与变换

地址映像：把存放在主存中的程序按照某种规则装入到 Cache 中，并建立主存地址与 Cache 地址之间的对应关系
地址变换：当程序已经装入到 Cache 之后，在实际运行过程中，把主存地址变换成 Cache 地址

为了方便地址映像和变化，就把 Cache 和主存都划分为相同大小的块，这样映像问题就变成了对应问题，有多种对应的方法

Cache-主存层次要求速度很高，并且对程序员透明，所以地址映像、地址变换、标记比较、命中判断、替换控制以及 Cache 与主存之间的数据块交换，通常都由==硬件==自动完成。

容易混淆的控制主体：

控制主体	主要负责内容
硬件	Cache-主存之间的地址映像、地址变换、命中判断、替换与数据块交换；主存芯片译码、读写控制等高速底层操作
软件	操作系统管理虚拟存储器中的页面调入、页面置换、文件与外存管理；应用程序通过系统调用间接请求 I/O
微程序	在微程序控制器中解释和实现机器指令，产生微命令序列；属于 CPU 控制器内部实现方法
DMA 控制器	外设与主存之间的数据块直接传送，包括主存地址修改、传送计数、读写控制和传送结束中断请求

因此，题目若问“Cache-主存层次中的地址映像及数据交换由谁完成”，应选==硬件==，不能选软件、微程序或 DMA 控制器。

全相联映像

主存中的任意一块都可以映像到 Cache 中的==任意==一块

实现复杂，很少采用

直接映像

主存中的每一块只能装入到 Cache 内==唯一==一块位置： $Cache块号=主存区内块号~mod~Cache总块数$

使用直接映像，那么整个 Cache 地址和主存地址的低位部分完全相同。比如若 Cache 一共有 16 块，那么 cache 块号与主存块号的低 4 位就会完全一样，这样使得映射非常简单；1 块 Cache 会映射 $主存块数\div Cache块数$ 的主存块

显然，因为多个主存块会映射到一个 Cache 块，那么需要一个区号表来存储该 Cache 块存储的到底是哪个主存块；除此以外还需要一个有效位来标识该块的内容是否有效（决定是否移进或替换）：

组相联映像

主存块到 Cache 组 set 之间采用直接映像方式，即一个主存块只能映像到一个 Cache 组内
对应的组内采用全相联映像方式，即一个主存块可以放入指定 Cache 组内任何 1 个块位置
组内 $N$ 块的组相联映像称为 $N$ 路组相连

$Cache组号 = 主存区内块号~mod~组数$ ，也就是说主存块号的低几位就是 Cache 的组号

到这里，我们解决了一个主存块放在哪个 Cache 组里的问题；但还需要解决如何知道一个主存块在组里哪个位置的问题——使用主存块的 tag 与 cache 中的块一一比较

地址变换时：首先根据组号查到对应 cache 组的目录表，然后在目录表内查区号（tag）

替换算法

替换时机：发生块失效，并且可以装入块的 cache 都已经被装满时

Cache 替换算法全部由硬件实现

堆栈法：块总是从栈顶进入，而栈底则是近期最久未被访问的块，将被替换
比较对法：使用触发器实现，让各个块成对组合，用一个触发器表示一对（两个）块访问的先后顺序；然后把每个对的顺序经门电路计算就可以找到应该被替换的块

显然比较对法更快，但更复杂、硬件成本更高：若有 $p$ 个块则需要 $p$ 个与门， $p(p-1)/2$ 个触发器

Cache 的透明性与性能分析

Cache 存储层次对系统程序员和应用程序员都是透明的

写 cache

Cache 作为主存的副本，有的时候会与主存不一致：

cpu 写了 cache 但没写主存
I/O 写了主存但没写 cache

为了保持 Cache 与主存的一致性，我们有两种更新算法：

==写直达法==WT：cpu 写 cache 时同时写主存
==写回法==WB：cpu 只写 cache，一直到该块被替换时再把修改的内容写回到主存

具体到写 Cache 时，有两种方法：

不按写分配法：在写不命中时，只把要写的字写入主存。在写直达法中采用
按写分配法：在写不命中时，还把一个块从主存读入 cache。在写回法中采用

预取算法

按需取：出现 cache 不命中时，把下一个块取入 cache
恒预取：无论是否命中，都把下一个块取入
不命中预取：出现 cache 不命中时，把本块和下一块一起取到 cache 中

但是采用预取也==不一定能提高命中率==，还要同时考虑块的大小和预取开销

性能影响因素

块的大小与数量
采用组相联时，组内的块数和组数
替换算法
地址流
预取算法

Cache 的命中率随着 Cache 容量提升而提升，但是有提升的瓶颈（或者叫边界值）

虚拟存储器

虚拟存储器由主存储器和联机工作的外存储器（磁盘存储器）共同组成，即虚存=主存+外存

虚存管理

段式管理

将程序按逻辑意义分成==段==，按段进行调入、调出和管理

每个程序段都从 0 开始编址，段可长可小
每个程序段可以映像到主存的任意位置
每道程序都有一张段表，用于指定每段的基地址；段表的地址由基址寄存器指定

Pros&Cons:

模块化性能好，便于共享
实现程序的动态链接和调度比较容易
地址变换花费时间长
对主存的利用率较低

页式管理

将主存空间和程序空间都等分成固定大小的页面，让程序的起点必须处在某页的起始位置。主存上的页称为实页，虚存的页称为虚页，地址映像机构负责转换

页式管理需要一个页表来存储实页与虚页的对应关系，以及是否装入等信息

地址转换较快，主存利用率更高
页表很长，而且不适合模块化的管理

段页式管理

程序按结构分段，每段再划分为若干大小相等的页

每道程序因为有多个段，所以需要一张段表，多张页表。虚地址包含用户号、段号、段内页号、页内地址四部分

页式虚拟存储系统构成

地址变换

实地址 $A$ 由实页号 $p$ 和页内偏移 $d$ 组成
虚地址 $A_v$ 由用户号 $U$ 、虚页号 $P$ 和页内偏移 $D$ 组成

内部地址变换：虚页号转换成实页号，然后与页内偏移拼接得到实地址
外部地址变换：查外页表获取磁盘实地址，查实页表看主存是否有空页，之后把页调入主存，得到实地址

页面替换

发生页面失效时，要将一页调入主存；若主存中所有页面都被占用，则必须淘汰一个页面

页面失效：该页未装入主存，需从外存中调页（页面失效应该当作一种故障来处理）
页面冲突：两个以上的虚页面想要进入主存中的同一个页面位置

页面失效时不一定发生页面冲突，但是页面冲突一定是由页面失效引起

常用的替换算法：

FIFO
LRU（堆栈型算法）

页式虚拟存储器实现时的问题

提高访问速度

两种主要方式：提高命中率或降低访存时间

==目录表==：使用一个小容量高速存储器存放页表
==快慢表==：优先查快表，查不到再去主存中的慢表中查（快表就是上面的目录表思想）
==散列函数==：把相联访问变成按地址访问，来加大快表容量

影响命中率的因素

页面大小：当页面大小为一个值时，命中率最高
主存容量：命中率随主存容量提升而单调上升
调度方式：请求式与预取式。请求式是什么时候用到什么时候调入，这样在一开始会有大量页面失效；预取式就是提前调入再运行，但是也有可能仍然页面失效，做无用功

提高存储系统性能

双端口存储器：有两组独立的读写控制线路
并行主存储器：多体交叉存储器，有三个方案：
1. 单体多字存储器：一次读出多个存储字，适合连续存放的情况
2. 多体单字交叉存储器
3. 多体多字交叉存储器

高位交叉扩大存储器容量；低位交叉提高访存速度

Chapter 4&5 中央处理器 + 流水线

CPU 的功能和组成

CPU 的功能：

控制指令的执行顺序
产生控制信号控制部件工作
控制各步操作的时序
数据处理：算数操作和逻辑运算

CPU 的组成：==数据通路==和==控制器==两部分

数据通路：指令执行过程中，数据所经过的路径，包括路径中的部件。它是指令的==执行部件==，包含寄存器、运算部件
控制器：对指令进行译码，生成指令对应的控制信号，控制数据通路的动作。是指令的==控制部件==，包含译码器、时序控制等

寄存器

CPU 中的寄存器用来暂时保存在运算和控制过程中的中间结果、最终结果以及状态、控制信息

分为通用寄存器和专用寄存器，专用寄存器至少要有：程序计数器==PC==、指令寄存器==IR==、存储器地址寄存器==MAR==、存储器数据寄存器==MDR==、状态标志寄存器==PSWR==

控制器的组成和实现方法

组成

指令部件：取指令并分析指令，包括：PC（程序计数器）, IR（指令寄存器）, ID（指令译码器）, 地址形成部件
时序部件：产生一定的时序信号，包括：脉冲源、启停控制逻辑、节拍信号发生器
==微操作信号发生器==：控制器的核心，把一条指令的取出和执行分解为很多微操作（最基本的不可再分割的操作）微操作信号发生器也称为控制单元（CU）。不同的机器指令具有不同的微操作序列。
中断控制逻辑

中断控制逻辑是用来控制中断处理的硬件逻辑

实现

微操作信号发生器

实现方法分为：组合逻辑型、控制逻辑型、组合存储逻辑结合型

时序系统与控制方式

概念

指令周期和机器周期：指令周期是指取指令、分析指令到执行完该指令所需的全部时间， $指令周期=i\times机器周期$
节拍：有时要把机器周期分为若干个相等的时间段，即为节拍
工作脉冲：在一个节拍内设置若干个工作脉冲，以保证所有触发器稳定且可靠地翻转
多级时序系统：机器周期-->节拍-->工作脉冲多级时序

控制方式

同步控制方式：各指令所需的时序由控制器统一发出，所有微操作都与时钟同步
异步控制方式：各部件自己产生自己的时序信号自我控制
联合控制方式

指令执行

三个核心阶段：==取指令、分析取数、执行==

取指令的公共操作：(PC)->MAR；READ；M(MAR)->MDR->IR；(PC)+1->PC

指令的微操作序列

实际上，要完成读一个主存中的数据的操作，有以下步骤：

将存储地址的寄存器送至 MAR
READ
把读出的内容送至 MDR，然后再送至其他寄存器

*微程序控制原理

用程序设计的思想来组织操作控制逻辑，将控制信号编码形成==控制字==（微指令），再把这些微指令按时间先后排列起来，存储在一个只读存储器中

微命令和微操作：一条机器指令可以分为一个微操作序列；微命令是控制计算机各部件完成某个基本微操作的命令。微命令是微操作的控制信号，微操作是微命令的操作过程
微指令和微地址：微指令是指控制存储器中一个单元的内容；存放控制字的控制存储器的单元地址就是微地址
微周期：读取并执行一条微命令所需要的时间
微程序：与机器周期对应，是一系列微指令的有序集合

*微指令编码法

一条微指令至少包含两大信息：

微指令编码法指的就是微操作码的编码方法：

直接控制法：也称不译码法，微操作码中的的每位直接控制对应微命令是否有效
最短编码法：对所有微命令统一编码，每条微指令只定义一个微命令
==字段编码法==：将控制字段分为几个小段，段内采用最短编码法，段间采用直接控制法
- 字段直接编码法：各字段独立定义本字段的微命令，与其他字段无关
- 字段间接编码法：一个字段和其他字段联合定义
字段编码法的==设计原则==：
1. 互斥的微命令分在同一段内，兼容性的微命令分在不同段内
2. 每个小段还要留出一个状态，表示本字段不发出任何微命令

微程序控制器

基本组成

控制存储器 CM（核心部件）：用来存放微程序
微地址寄存器 uIR：用来存放从 CM 中取出的微指令
微地址形成部件：产生初始微地址和后继微地址
微地址寄存器 uMAR：接受微地址，为在 CM 读取指令做准备

工作过程

微程序控制器的工作过程就是一条条机器指令的执行过程：

执行取指令公操作
由操作码产生入口地址，并送入 uMAR
从 CM 中逐条取出对应的微指令并执行

微程序地址

初始微地址：由机器指令的==操作码==字段指出各段微程序的入口地址（初始微地址）

由机器指令的操作码转换成初始微地址的方法有三种：一级功能转换；二级功能转换；PLA 功能转换
后继微地址：增量方式（顺序-转移）和断定方式（给定+测试）

微程序设计方法

水平型微指令：一次能定义并执行多个微命令，并行性高，灵活性强
垂直型微指令：一次只能执行一个微命令，编程简单，微指令字较短

流水线

基本概念

流水线技术

流水线技术：将指令的执行过程分解为==多个子过程==，并让每个子过程分别由专用的部件完成，这些功能部件可以同时工作，从而实现多条指令的并行执行，减少多条指令或一段程序的完成时间

空间并行性：设置多个独立的操作部件，多操作部件处理机、超标量
时间并行性：流水线，流水线/超流水线处理机

流水线是基于==时间重叠==的并行处理技术，不能加快一条指令的执行，但是能加快多条指令的执行

只有==连续==提供==同类==任务才能充分发挥流水线效率
流水线中的每一段都需要设置一个==流水寄存器==
各段的时间应尽可能相等
流水线有装入时间和排空时间

流水线分类

部件级/处理机级/处理机间级（流水线级别）；单功能/多功能（流水线面向功能）；静态/动态（是否允许联结多种功能）；线性/非线性（是否有反馈信号），非线性流水线需要用流水线连接图和流水线预约表共同表示

*流水线性能

提升性能的方法：

细分瓶颈过程
重复设置瓶颈功能段，让他们并行交叉工作

性能指标

吞吐率：流水线单位时间里能流出的任务数或结果数
加速比：流水线速度与等效的非流水线速度之比， $\large S_p=\frac{T_{非流水}}{T_{流水}}$
效率：又称设备时间利用率，是流水线中的设备实际使用时间占整个运行时间之比

*流水线调度

==资源冲突==：几个任务争用一个功能段的现象

线性流水线因为没有反馈，所以不会发生冲突，只需间隔固定的时间输入任务即可

但是非线性流水线段间有反馈回路，一个任务在流水执行的全过程中，可能会多次通过同一段，或越过某些段。如果每拍都向流水线中输入数据，就会发生资源冲突

那么此时就引入了调度问题——间隔几拍向流水线中输入数据才能既不冲突，又能获得比较高的吞吐率？

二维预约表

假设有一个由 $K$ 段组成的单功能非线性流水线，每个任务通过流水线需要 $N$ 拍。若一个任务在第 $n$ 拍时需要用到第 $k$ 段，那么就在表中的 $(n,k)$ 处置✅。例如一个 5 段9拍的二维预约表：

	1	2	3	4	5	6	7	8	9
S 1	✅								✅
S 2		✅	✅					✅
S 3				✅
S 4					✅	✅
S 5							✅	✅

调度方法

根据预约表可以得出一个任务使用各功能段所需间隔的拍数，构建延迟==禁止向量 F==

将流水线中所有各功能段对一个任务流过时会产生争用的节拍间隔数汇集在一起，比如上面的预约表的禁止向量 $F=\{1,5,6,8\}$ ，这些间隔节拍禁止使用
将禁止向量 (或禁止表)转换成 m 位的、用二进位表示的==初始冲突向量 C==

例子的冲突向量 $C=10110001$
计算流水线的新的冲突向量

对于每个冲突向量，对其不断右移，每移出一个 0 之后就和初始冲突向量作一次按位或，直至求到这种运算的==闭包==
构造用冲突向量表示的流水线状态图

对于 3 中得到的所有冲突向量，每个向量都是一个状态，状态转移条件即为前状态右移几位之后作按位或能得到后状态。如：
确定调度方案

从状态图中的初始状态出发，找到一个间隔拍数呈周期性重复的方案，并按此方案进行调度，就不会发生功能段冲突。如上图的调度方案有：(2,7); (2,2,7); (3,4,7)等等。需要从诸多调度方案中挑选出平均延迟最小的，吞吐量最大的

有些方案可能最大吞吐量是一样的，但是在效率或者真实的吞吐量方面上有细微差别，选择方案时要综合考虑

流水线相关处理

相关：相邻或临近的两条指令因存在某种关联，它使得指令序列中下一条指令无法按照设计的时钟周期开始执行

局部性相关（数据相关）

原因：当机器执行多条指令时，这些指令对==同一存储单元==“先写后读”导致（联想 csapp 数据相关）

解决方法：推后读（将读的操作延迟）；设置相关专用通路（同 csapp 中解决方法）

全局性相关（控制相关）

原因：由分支转移指令引起的相关（联想 csapp 控制相关）

解决方法：尝试判断正确的转移分支

猜测法，保证猜错时可恢复分支点原先的现场
加快和提前形成条件码
延迟转移
加快短循环程序的处理

局部性相关	全局性相关
指令相关、主存数相关、寄存器组相关等
只影响数条指令，不影响指缓中预取的指令	影响后续指令、指缓中预取的指令
同步流动由 WR 引起；异步流动由 WW、RW 引起	一般由转移或中断引起
	使流水线断流，使吞吐率和效率下降

流水线的中断处理

中断会使流水线断流，它不经常发生，不可预测，一旦进入中断可能持续很长时间

流水机器中断的处理主要是==断点现场的保护与恢复==

不精确断点法：允许已经在流水线中的指令执行完毕再进入中断，中断处理简单但是调试困难
==精确断点法==：不论指令 i 在流水线哪一段发生中断，只保存第 i 条指令的现场

向量流水处理与向量机

向量的特点：元素之间无相关，一般对元素执行相同类型的操作

向量的处理方式

要根据向量运算的特点和向量处理机的类型选择处理方式

水平处理：标量机的处理法，向量机不用这个
垂直处理：以向量为单位计算，只要能提供连续输入就能获得高吞吐率，缺点是对存储器要求较高，可以通过采用多体交叉存储或设置向量寄存器组来解决这一问题
分组处理：用于寄存器--寄存器结构的向量处理机中，当向量长度大于向量寄存器长度 n 时，进行分组处理；组内纵向处理，组间横向处理

向量流水处理机

向量流水处理机=向量数据表示+流水线处理

$V_i$ 冲突：除相关情况外，并行工作的指令中使用了相同的向量 $V_i$
功能部件冲突：同一个功能部件被一条以上的要求并行工作的向量指令所使用

超标量与超流水

超标量

本质是在不同的流水线执行不相关指令的能力

度为 $m$ 的超标量处理机采用 $m$ 流水线，在每个 $\Delta t$ 时间内同时解释完 $m$ 条指令。以增加硬件资源为代价获取处理机性能，利用的是空间并行性

单发射处理机：每个周期只操作一条指令
多发射处理机：每个周期同时操作多条指令

一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机，必须有两条或两条以上能够同时工作的指令流水线

指令集并行度为 $(m,1)$ ， $k$ 段流水线的超标量处理机上，执行 $N$ 条指令所用的时间为 $T(m,1)=(k+\frac{N-m}{m})\Delta t$ ；相比单流水线标量处理机的加速比为 $S(m,1)=\frac{m(k+N-1)}{mk+N-m}$

超流水

一个周期内能分时发射多条指令的处理机称为超流水线处理机，通过硬件部件充分重叠工作来提高处理机性能，利用的是时间并行性。

每隔 $1/n$ 个时钟周期发射一条指令，流水线周期为 $1/n$ 个时钟周期

指令并行度为 $(1,n)$ ， $k$ 段流水线的超流水线处理执行 N 条指令所用的时间为 $T(1,n)=(k+\frac{N-1}{n})\Delta t$ ，加速比为 $S(1,n)=\frac{n(k+N-1)}{nk+N-1}$

超标量超流水

指令并行度为 $(m,n)$ ， $k$ 段流水线的超标量超流水线处理机执行 $N$ 条指令所用的时间为== $\large T(m,n)=(k+\frac{N-m}{mn})\Delta t$ ，加速比为 $\large S(m,n)=\frac{mn(k+N-1)}{mnk+N-m}$ ==

性能比较

超流水线的启动延迟比超标量处理机大
条件转移造成的损失，超流水线要比超标量大
因为超标量重复设置了多个指令执行部件，所以超标量执行指令时出现的冲突会更少

一般来说，并行度 m 和 n 都不要超过4

Chapter 6 总线与输入输出系统

概述

组成

处理机和主存储器之外的部分输入输出系统包括：输入输出设备、设备控制器及与输入输出操作相关的软硬件

功能

是对指定的外设进行输入、输出操作，同时也完成许多其他的管理和控制

特点与组织

异步性 IO 设备不使用统一的中央时钟，各个设备按照自己的时钟工作，但又要在某些时刻接受处理机的控制。
- 自治控制（输入输出系统独立于处理机之外）
实时性（处理机必须及时处理设备）
- 层次结构（离处理机由近到远：I/O 处理机、标准接口、设备控制器）
与设备无关性（独立于设备的标准接口）计算机系统的使用者，在需要更换外围设备时，各种不同型号，不同生产厂家的设备都可以直接通过标准接口与计算机系统连接。
- 分类处理（面向字符设备、面向数据块设备）

发展阶段与形式

程序控制输入输出：CPU直接进行I/O操作，包括全软件的、程序查询状态驱动的、中断驱动等
直接存储器访问DMA：DMA开始和结束时需要处理及参与，传送过程中不用
I/O处理机：专门处理机完成外设I/O操作，实现CPU、I/O设备操作并行

磁盘阵列

RAID

将一组磁盘驱动器用某种逻辑方式联系起来，形成一个磁盘驱动器优点：成本低、功耗小、速率高；提供容错能力 RAID 的分级：

SSD

SSD 由两部分组成：控制单元，负责读取、写入资料；存储单元：负责存储资料（Flash 芯片）简单的说就是存储芯片通过阵列制成的硬盘（基本都是 RAID 0 模式，这也是 SSD 高速的原因）

优点：读写速度快；低功耗；无噪音；防震抗摔；工作温度范围大；轻便
缺点：容量上限低；售价高；寿命限制

总线

在大多数小型和微型计算机系统中，计算机的各子系统之间通过总线（Bus）实现连接

总线特点

总线是一组能为多个部件==分时共享==的公共信息传送线路共享是指总线上可以挂接多个部件，各个部件之间相互交换的信息都可以通过这组公共线路传送；分时是指同一时刻总线上只能传送一个部件发送的信息。

优点：成本低、简单；缺点：总线的带宽形成了信息交换的瓶颈，从而限制了系统中总的 I/O 吞吐量。

总线事务

通常把在总线上一对设备之间的一次信息交换过程称为一个==总线事务== ，把发出总线事务请求的部件称为==主设备==，与主设备进行信息交换的对象称为==从设备==

例如 CPU 要求读取存储器中某单元的数据，则 CPU 是主设备，而存储器是从设备。

总线事务类型通常根据它的操作性质来定义，典型的总线事务类型有“存储器读”、“存储器写”、“I/O 读”、“I/O 写”、“中断响应”等总线事务包括两个阶段：地址阶段，数据阶段

总线使用权

因为总线是共享的，所以必须有一个总线控制机构，实现对总线使用的分配与管理

主设备请求并获得总线使用权后，立即开始向从设备进行一次信息传送

通常，将完成一次总线操作的时间称为==总线周期==；总线使用权的转让总发生在总线进行一次数据传送的结束时刻

总线数据宽度

数据宽度是 I/O 设备取得 I/O 总线后所传送数据的总量。它不同与前述的数据通路宽度。数据通路宽度是数据总线的物理宽度，也就是数据总线的线数。而两次分配总线期间所传送的数据宽度可能要经过多个时钟周期分次传送才能完成。对于不同速度的设备，有不同的数据宽度，比如单字宽度、变长块宽度、定长块宽度

单字（单字节）宽度：适合于低速设备，因为这些设备在每次传送一个字（字节）后的访问等待时间很长，这段时间内让总线释放出来为别的设备服务，可以大大提高总线利用率和系统效率
定长块宽度：适合于高速设备，可以充分利用总线带宽，定长块也不用指明传送信息的长度，简化了控制。但由于块的大小固定，当它要比实际传送的信息块小很多时，仍要多次分配总线。
变长块宽度：适合于高优先级的中高速设备，灵活性好，按照设备特点动态改变传送块的大小，使之与部件的物理或逻辑信息块的大小一致。
单字+定长块宽度：速度低但优先级高的设备

总线线数

总线需要有很多物理线路，总线的线数越多，成本越高、干扰越大、可靠性越低，占用空间越大，传送速度和流量越高。此外，总线的长度越长，成本越高，干扰越大，波形畸变越严重，可靠性越低。因此，在满足性能要求的情况下，应尽量减少总线的线数，数据总线的宽度有一位、一个字节或一个全字等等。

*总线性能指标

总线宽度

总线宽度指的是总线的线数，它决定了总线所占的物理空间和成本对总线宽度最直接的影响是地址线和数据线的数量。主存空间和 I/O 空间的扩充使地址线数量的增加，并行传输要求有足够的数据线。

例 1：使用 ISA 总线（20 位地址线）允许寻址的主存空间有多大？使用 PCI 总线（32 位地址线）允许寻址的主存空间又有多大？如果该计算机采用字节编址，则允许寻址的主存空间又有多大？解： ISA 总线的主存空间= $2^{20}$ 个主存单元=1 M 个主存单元。PCI 总线的主存空间=232 个主存单元=4 G 个主存单元。如果采用字节编址所以是 1 M × 1B = 1 MB

地址总线：传地址，决定的是最大可寻址空间
数据总线：传数据，数据总线宽度
控制总线：传读/写、中断、时钟等控制信号

总线线数 = 地址线 + 数据线 + 控制线等总和

总线带宽

总线的最大数据传输速率，即每秒传输的字节数

总线带宽=数据总线宽度\times总线时钟频率

总线负载

总线负载是指连接在总线上的最大设备数量。大多数总线的负载能力是有限的。

总线复用

总线分时复用是指在不同时段利用总线上同一个信号线传送不同信号，例如地址总线和数据总线共用一组信号线。采用这种方式的目的是减少总线数量，提高总线的利用率。

总线猝发传输

猝发式数据传输是一种总线传输方式，即在一个总线周期中可以传输存储地址连续的多个数据

总线控制

为了保证同一时刻只有一个申请者使用总线，总线控制机构需要按照一定的优先次序来决定哪个部件首先使用总线。只有获得使用权的部件才能开始数据传输

集中仲裁

为了保证同一时刻只有一个申请者使用总线，总线控制机构中设置有总线判优和仲裁控制逻辑，即按照一定的优先次序来决定哪个部件首先使用总线，只有获得总线使用权的部件，才能开始数据传送。总线控制逻辑集中在一处（如在 CPU 中）的，称为集中式控制

链式查询：总线控制器使用三根控制线与所有部件和设备相连，包括==总线请求 BR==、==忙 BS==、==批准 BG==。这样做无法更改查询优先级
计数器定时查询：有公共的 BR 线和 BS 线，还需要一些线来控制优先次序。对于 $n$ 个部件，需要 $2+\lceil log_2n\rceil$ 根线
独立请求：每一个部件都有一对 BR 和 BG。对于 $n$ 个部件，需要 $2n+1$ 根线

分布仲裁

总线的控制逻辑分散在连接于总线上的各个部件或设备中

自举分布式：优先级固定，需要控制权的设备在各自的请求线上送出请求信号。如果检测到没有优先级更高的设备正在请求使用总线，则使用总线并通过总线忙信号阻止其他设备使用总线
冲突检测分布式：如果发现冲突则等待一段随机的时间再重新使用，（有点像计网的随机访问 ALOHA）
并行竞争分布式：总线上的每个设备都有一个唯一的仲裁号，需要使用总线的主控设备把自己的仲裁号发送到仲裁线上，这个仲裁号将用在并行竞争算法中。每个设备根据仲裁算法决定在一定时间段后占用总线还是撤销仲裁号

输入输出系统控制

概述

主机和外设之间的信息传送控制方式，按照发展的先后次序和主机与外设并行工作的程度，可以分为四种：

程序查询方式：程序查询方式是一种程序直接控制方式，这是主机与外设间进行信息交换的最简单方式，完全通过 CPU 直接控制
程序中断方式：外设在做好输入输出准备时，向主机发中断请求，主机接到请求后就暂时中止原来执行的程序，转去执行中断服务程序对外部请求进行处理，在中断处理完毕后返回原来的程序继续执行。
直接存储器存取方式 DMA：DMA 是在主存和外部设备之间开辟的直接数据通路，可以在没有 cpu 介入完成数据在主存与外设之间的交换
I/O 通道控制方式：通道是一个具有特殊功能的处理器，它能独立执行通道程序，产生相应的控制信号，实现对外设的统一管理和外设与主存之间的数据传送。是从属于 CPU 的一个专用处理器，要在 CPU 的 I/O 指令指挥下才能启动、停止或改变工作状态。

控制方式	优点	缺点	适用场景
程序查询	控制简单	外设、主机之间不能同时工作，系统效率低	外设不多，实时要求低；cpu 操作任务单一，不繁忙的系统
程序中断	允许主机和外设同时并行工作，允许一台主机管理多台外设	一次程序中断需要许多辅助操作，CPU 占用高；高速外设可能会丢失信息	适用于中、低速外设
直接存储器存取	能保证 CPU 的高效率和外设的高速	只能进行简单的数据传送操作，在数据块传送的起始和结束时还需 CPU 及中断系统进行预处理和后处理	适用于高速外设
I/O 通道控制	不论交换信息多少，只打扰 CPU 两次（启动和停止时）

程序查询方式（轮询方式）

由 CPU 执行一段输入、输出程序来实现主存与外设之间的数据传送方式，叫做程序直接控制方式。根据外设的不同性质，这种传送方式又可分为无条件传送和程序查询方式两种。

在无条件传送方式中，I/O 接口总是准备好接收主机的输出数据，或总是准备好向主机输入的数据，因而 CPU 无需查询外设的工作状态，而默认外设始终处于准备就绪状态。

许多外设的工作状态是很难事先预知的，为了保证数据传送的正确进行，CPU 在程序中查询外设的工作状态，如果外设尚未准备就绪，CPU 就等待，只有外设已作好准备，CPU 才能执行 I/O 指令，这就是程序查询方式

工作流程

使用查询方式，至少要 5 个指令才能完成一次数据传送，包括下面的 12356

预置传送参数在传送数据之前，由 CPU 执行一段程序，预置传送参数。传送参数包括存取数据的主存缓冲区首地址和传送数据的个数。
向 I/O 接口发命令字来启动外设当 CPU 选中某台外设时，执行输出指令向 I/O 接口发出命令字，启动外设，为接收数据或发送数据的操作做准备。
从 I/O 接口取回状态字

CPU执行输入指令，从I/O接口中取回状态字并进行测试，判断数据传送是否可以进行。
查询外设标志

CPU不断查询状态标志，如果外设没有准备就绪，CPU就踏步进行等待，一直到这个外设准备就绪，并发出“准备就绪”信号为止。
传送数据

只有外设准备好，才能实现主机与外设间的一次数据传送。
- 输入时，CPU执行输入指令，从I/O接口的数据缓冲寄存器中接收数据；
- 输出时，CPU执行输出指令，将数据写入I/O接口的数据缓冲寄存器。
修改传送参数

每进行一次数据传送，需要修改传送参数，其中包括主存缓冲区地址加1，传送个数减1。
判断传送是否结束

如果传送个数不为0，则转第3步，继续传送，直到传送结束为止。

*中断系统与程序中断方式

中断系统是计算机实现中断功能的软、硬件总称。

中断系统在 cpu 中会配置==中断机构==，外设接口配置==中断控制器==，软件上设计==中断服务程序==

中断源和中断请求

==中断源==是指中断的来源，即任何引起计算机中断的事件

一般计算机都有多个中断源。由于每个中断源向CPU发出中断请求的时间是随机的，为了记录中断事件并区分不同的中断源，可采用具有存储功能的触发器来记录中断源，称为中断请求触发器。当某一个中断源有中断请求时，其相应的中断请求触发器置成“1”状态，此时，该中断源向CPU发出中断请求信号。

多个中断请求触发器构成一个中断请求寄存器，其中每一位对应一个中断源，中断请求寄存器的内容称为中断字或中断码，中断字中为“1”的位就表示对应的中断源有中断请求

中断请求信号的传送

独立请求线：每个中断源单独设置请求线，独立发送中断请求信号送往 CPU，这种方式的特点是 CPU 在接到中断请求的同时也就知道了中断源是谁，其中断服务程序的入口地址在哪里。
公共请求线：有一根公共请求线，这种方式的特点是在负载允许的情况下，中断源的数目可随意扩充，但 CPU 在接到中断请求后，必须通过软件或硬件的方法来识别中断源，然后再找出中断服务程序的入口地址。
二维结构：将中断请求线连成二维结构，同一优先级的中断源采用一根公共请求线，这种方式综合了前两种方式的优点，在中断源较多的系统中常采用这种方式。

中断优先级

当多个中断源同时发出中断请求时，CPU 在任何瞬间只能接受一个中断源的请求。所以就需要中断优先级来排序

确定中断优先级的原则：对那些提出中断请求后需要立刻处理，否则就会造成严重后果的中断源规定最高的优先级；而对那些可以延迟响应和处理的中断源规定较低的优先级。如故障中断一般优先级较高，接着才是 I/O 设备中断。而在 I/O 设备中又可以根据各个设备的速度来决定优先级。

软件判优法
- 软件判优是与识别中断源结合在一起的，当查询到中断请求信号的发出者，也就是找到了中断源，程序立即可以转入对应的中断服务程序中去。
硬件判优电路
- 采用硬件实现中断优先级判定可节省 CPU 时间，而且速度快，但是成本较高

CPU 响应中断的条件

cpu 接收到中断请求信号
cpu 允许中断 CPU 内部有一个中断允许触发器，只有当其被置位时，CPU 才可能响应中断源的中断请求（中断开放）。如其被复位，CPU处于不可中断状态，即使中断源有中断请求，CPU 也不响应（中断关闭）。
一条指令执行完毕

中断隐指令

CPU 响应中断之后，经过某些操作，转去执行中断服务程序。这些操作是由硬件直接实现的，我们把它称为==中断隐指令==。中断隐指令并不是指令系统中的一条真正的指令，它没有操作码，所以中断隐指令是一种不允许、也不可能为用户使用的特殊指令。它包括以下操作：

保存断点
暂不允许中断为了在用软件保护中断现场（即 CPU 的主要寄存器状态）时，不被新的中断所打断，从而保证被中断的程序在中断服务程序执行完毕之后能接着正确地执行下去。
引出中断服务程序

中断周期

0->MAR，将特定地址 0 送至 MAR；如果要把断点存入堆栈，则改为 SP->MAR
(PC)->MDR，将 PC 内容送至 MDR
Write，启动存储器写操作
MDR->M(MAR)，将 MDR 的内容写入 MAR 指示的主存单元
向量地址->PC，把向量地址形成部件的输出送入 PC，为转入中断服务程序做准备
0->EINT，关中断，将中断允许触发器清 0

进入中断服务程序

CPU 决定响应中断之后，向中断源发出中断响应信号；中断源接到中断响应信号后就通过自己的向量地址发生器向 CPU 发送向量地址，这个向量地址有两种情况：

向量地址是中断服务程序的入口地址，直接进入中断服务程序
向量地址是中断向量表的指针，需要从中断向量表的响应单元中取出中断服务程序的入口地址

中断现场的保护和恢复

使用堆栈保存通用寄存器等硬件的信息

中断嵌套

中断嵌套的层次可以有多层，越在里层的中断越急迫，优先级越高，因此优先得到 CPU 的服务。需要 CPU 能保护多个断点，并且进入中断服务程序后仍然保持开中断

开/关中断

由中断允许触发器控制，置 1 则开中断，置 0 则关中断

==开中断的情况==：

中断服务程序执行完毕，恢复中断现场之后
多重中断的情况下，保护中断现场之后

==关中断的情况==：

响应某一级中断请求，不再允许被其他中断请求打断时
在中断服务程序的保护和恢复现场之前

中断屏蔽

用程序的方式有选择地封锁部分中断，可以使用掩码按位与来实现

不同的优先级的中断源可以有不同的屏蔽字，以防止被优先级低的中断打断

如一个中断系统有 16 个中断源，每一个中断源按其优先级别赋予一个屏蔽字。“0”表示开放，“1”表示屏蔽。第 1 级中断源的优先级别最高，它禁止本级和更低级的中断请求；第 16 级中断源的优先级别最低，它仅禁止本级的中断请求，而对其他高级的中断请求全部开放

中断源的优先级 屏蔽字（16位）
1
2
3
……
15
16

对应的屏蔽字：

111…111
011…111
001…111
……
000…011
000…001

*中断升级

中断升级是将级别较低的中断源变成较高级别，改变中断的==处理次序== 中断响应次序是由硬件排队电路决定的，无法改变。但是，中断处理次序是可以由屏蔽码来改变的，故把屏蔽码看成软排队器。中断处理次序可以不同于中断响应次序。

升级的方法很简单，就是改写中断源的屏蔽字

中断全过程

中断请求
中断判优
中断响应
中断处理：执行中断服务程序，分为保护现场、处理中断和恢复中断
中断返回

随堂练习

DMA

程序查询还是中断需要 CPU 执行程序来完成，而直接存储器访问 DMA 方式是在外设和主存储器之间开辟一条==直接数据通道==，不需要 CPU 程序也能传送数据

特点

主存既可以被 CPU 访问，又可以被外设访问
主存地址、传送数据计数由硬件实现
传送速度快，和 CPU 并行工作
DMA 开始前和结束后需要通过程序和中断方式进行预处理和后处理

与中断的区别

中断需要保护和恢复现场；DMA 除预处理和后处理以外，不需要 CPU
中断只能发生在每条指令执行完毕时；DMA 可以发生在每个机器周期结束时
DMA 的数据传送速率更高
DMA 的请求优先级高于中断请求
中断可以处理异常事件；DMA 局限于传送信息块

DMA 控制器功能

在传送数据期间，代替 CPU 工作，可以向 CPU 发出总线请求、自动修改计数值、发出读写等控制信号、执行数据传送操作、报告 DMA 操作结束等

DMA 控制器基本组成

主存地址计数器：存放主存中要交换数据的地址
传送长度计数器：记录传送数据块的长度，为 0 时表示数据传输完毕
数据缓冲寄存器：外设的数据先送入缓冲，再送入主存
DMA 请求触发器
控制/状态逻辑
中断机构：向 CPU 提出中断请求，用于后处理

DMA 传送方法

CPU 停止访问主存法
存储器分时法：把原来的一个存取周期分为两个时间片，一片给 CPU，一片给 DMA，令二者交替访问。如果要维持 CPU 访存速度不变，就需要主存工作速度提高一倍 DMA 时间片可能成为空操作，导致不必要的浪费
周期挪用法：前两种方法的折中方法一旦外设有 DMA 请求并获得 CPU 批准后，CPU 让出一个周期的总线控制权，由 DMA 控制器控制系统总线，进行数据传输，然后再把控制权交回 CPU；重复上述过程直至数据块传输完毕

DMA 传送过程

DMA 预处理 这是在 DMA 传送之前做的一些必要的准备工作，是由 CPU 来完成的。CPU 首先执行几条 I/O 指令，用于测试外设的状态、向 DMA 控制器的有关寄存器置初值、设置传送方向、启动该外部设备等。
数据传送 DMA 的数据传送可以是以单字节（或字）为基本单位，也可以以数据块为基本单位。对于以数据块为单位的传送，DMA 占用总线后的数据输入和输出操作都是通过循环来实现的。
DMA 后处理 当长度计数器计为 0 时，DMA 操作结束，DMA 控制器向 CPU 发中断请求，CPU 停止原来程序的执行，转去执行中断服务程序做 DMA 结束处理工作。

I/O 通道控制方式

通道是 DMA 方式的进一步发展，二者区别主要在于：通道是一个具有特殊功能的处理器，可以同时控制多台不同类的设备；通道由更强的独立处理数据输入/输出的功能

通道的功能

接受 CPU 的I/O指令，按要求与指定的外设进行联系
从主存中取通道指令，向外设发送命令
实施主存和外设间的数据传送
向 CPU 报告外设和自身的中断请求
将外设的状态信息送至主存的指定单元供 CPU 使用

Chapter 7 多处理机与多计算机

多处理机概念

定义

多处理：在多个处理机上运行同一道程序或作业的不同任务。可以串行，也可以并行

多处理机：由两台及以上处理机组成的计算机系统，实现作业任务指令数据等各个级别的并行，属于 MIMD

主要技术问题

结构灵活性与通用型
进程通信方法：共享内存、互连网络、消息传递机制
运行模型：数据并行+处理并行
并行性表达
并行算法

多处理机结构

从存储器的分布和使用上看，多处理机系统分类两种结构：

共享存储器结构：还可以细分为 UMA 结构和 NUMA 结构
分布式存储器结构

共享存储器结构

各处理机通过互联网络共享存储器和 I/O 设备，并通过共享存储器相互联系。不过这也引入了 Cache 的一致性问题

UMA 结构

均衡存储器访问结构。各处理机对存储器的访问时间、访问功能相同。这种结构的处理机称为对称多处理机 SMP

互联网络一般是总线，也可以是交叉开关或多级交换网络

NUMA 结构

非均衡存储器访问结构。各处理机拥有自己的本地存储器，可以独立工作，也可以借助互联网络、通过消息传递机制相互通信

ccNUMA

高速缓存一致性非均匀存储访问，在 NUMA 多处理机中，若各处理机 Cache 内容一致，则将其称为 ccNUMA

使用基于==目录==的高速缓存一致性协议

COMA

仅用高速缓存存储器结构，是 NUMA 的特例，将 NUMA 中的分布存储器换成了 Cache

各处理机节点上没有主存，没有存储层次结构，仅有 Cache

分布式存储器结构

NORMA，非远程存储访问：各处理机拥有私有的本地存储器，在本地操作系统控制下独立工作；各处理机借助互联网络，通过消息传递机制相互通信，实现数据共享

大规模并行处理机 MPP 和机群等采用这种结构

大规模并行处理机 MPP

以定制的高带宽、低延迟的高速互联网络互联

是一种异步的 MIMD 机器

机群 COW/NOW

通过一组松散耦合的计算机软件/硬件连接起来，高度紧密地协作完成计算工作的计算机系统

是非均匀存储访问的 MIMD 型的分布式存储并行计算机

多核处理器

多核处理器是多处理机的一种特殊形式，即一个芯片上的 SMP

硬件多线程

为每个线程提供单独的通用寄存器组和程序计数器等，线程切换时，处理器只需要激活选中的寄存器，达到快速切换线程的目的，这种方式叫做硬件多线程

线程切换

细粒度多线程：处理器每个时钟周期轮流发射不同线程的指令
粗粒度多线程：仅在一个线程出现较大开销的阻塞时，才切换线程
同时多线程：多个线程的指令被同时发射

结构设计

同构/异构
核的数量
Cache 的设置与访问
核间通信技术

多处理机的多 Cache 一致性

如果一道程序的任何运行结果都与按假定序列执行的结果一样，则称多处理机存储器是一致性的

所有存储器访问的执行都必须保持所有各个程序的次序 8