体系结构复习笔记

1. 定律

1.1 摩尔定律

集成电路上可容纳的晶体管数目，大约每隔两年便会增加一倍；

CMOS工艺的瓶颈使得摩尔定律逐渐失效。

1.2 登纳德缩放比例定律

每平方毫米的电路耗能几乎不变；

登纳德缩放比例定律2007年开始逐渐失效，到2012年几乎完全失效；

1.3 阿姆达定律

多核并行计算机的加速受到程序中串行计算部分的限制；

2. DSA 提高性能的四个原因

DSA为特定领域开发了一种更有效的并行形式，例如：单指令多数据并行（SIMD）比多指令多数据并行（MIMD）更有效；
DSA可以更有效地使用内存结构；
DSA在适当的时候使用较低存储的精度；
DSL（Domain-Specific Languages）编写的目标程序，具有更高的并行性，改善内存访问的结构和表示，应用程序更加有效地映射到特定处理器。

3. 体系结构黄金时代来临

主要原因：深度学习新运算架构的流行

4. 并行

4.1 多线程

4.2 多工

4.3 多处理器

困难点：性能编程、负载均衡、优化通信和同步

5. 冗余实现可靠性

Hadoop分布式文件系统（HDFS）将文件分成多个块存在不同的Ｄatanode中，每个Ｄatanode里的文件块都会有副本存在其他的Datanode中。当某个文件块丢失了，可以使用其副本替代，从而不会导致整个文件的损坏。

6. 计算机效能

6.1 响应时间

完成一项任务需要多长时间

6.2 吞吐量

每单位时间完成的总工作量

6.3 相对性能

定义：性能 = 1 / 执行时间

$\begin{array}{c} {performance_x \over performance_y} = {execution\_time_y \over execution\_time_x} \end{array}$

6.4 经过时间

总响应时间，包括所有方面：处理，I / O，操作系统耗时，空闲时间。

6.5 CPU时间

处理给定工作所花费的时间。

$\begin{array}{c} CPU\_time = CPU\_clock\_cycles \times Clock\_cycle\_time = {CPU\_clock\_cycles \over Clock\_rate} \end{array}$

6.6 提高效能

减少时钟周期数
时钟频率提高
硬件设计人员必须经常权衡时钟速率与周期数

6.7 指令数和CPI

$\begin{array}{c} CPI = Cycles\_per\_instruction \\ Clock\_cycles = Instruction\_count \times CPI \\ CPU\_time = Instruction\_count \times CPI \times Clock\_cycle\_time = {Instruction\_count \times CPI \over Clock\_rate} \end{array}$

CPI在给定CPU上的程序之间有所不同
程序的指令计数：由程序，ISA和编译器确定
每条指令的平均周期：由CPU硬件决定（如果不同的指令具有不同的CPI，平均CPI受指令组合影响）

不同的指令类别需要不同的周期数：

$\begin{array}{c} Clock\_cycles = \sum_{i=1}^n(CPI_i \times Instruction\_count_i) \\ CPI = {Clock\_cycles \over Instruction\_count} = \sum_{i=1}^n(CPI_i \times {Instruction\_count_i \over Instrucion\_count}) \end{array}$

6.8 功率

在 CMOS IC 技术中：

$\begin{array}{c} Power = Capacitive\_load \times Voltage^2 \times Frequency \end{array}$

6.9 SPEC CPU 基准测试

$\begin{array}{c} SPEC = \sqrt[n]{\prod_{i=1}^n Execution\_time\_ratio_i} \end{array}$

SPEC 功率基准

性能：ssj_ops / sec
功率：瓦（焦耳/秒）

$\begin{array}{c} Overall\_ssj\_ops\_per\_watt = {\sum_{i=0}^{10} ssj\_ops_i \over \sum_{i=0}^{10} power_i} \end{array}$

6.10 阿姆达尔定律

改善计算机的部份性能，并期望整体性能得到成比例的改善。

$\begin{array}{c} T_{improved} = {T_{affected} \over Improvement\_factor} + T_{unaffected} \end{array}$

6.11 MIPS

MIPS：每秒数百万条指令

$\begin{array}{c} MIPS = {Instruction\_count \over Execution\_time \times 10^6} = {Clock\_rate \over CPI \times 10^6} \end{array}$

7. cache

命中率：命中/访问
未命中：1 - 命中率

未命中时从较低存储级别复制块

7.1 直接映射缓存

（块地址）%（＃缓存中的块）

7.2 缓存命中与否

未命中：停顿CPU流水线，从下一层次结构中获取块
指令缓存未命中：重新启动指令获取
数据缓存未命中：完整的数据访问

7.3 直写(Write Through)

命中：数据写入命中时，同时更新内存和缓存。
未命中：

分配未命中(Allocate on miss)：更新该缓存块。
随便写(Write around)：不要更新该缓存块

7.4 回写(Write-Back)

命中：命中数据时，只需更新缓存中的块。跟踪每个块是否脏(dirty)。
未命中：通常取出整块。

7.5 多级缓存

L-1主缓存：专注于降低命中时间(hit time)
L-2缓存：专注于降低未命中率以避免主存储器访问

8. DRAM

突发模式(Burst mode)：连续访问连续的字，减少延迟
双倍数据速率（DDR）DRAM：在时钟的上升沿和下降沿都可以传输
四倍数据速率（QDR）DRAM：单独的DDR输入和输出通道

9. Flash

NOR闪存：以字为读写单位
NAND闪存：以块为读写单位

10. RISC-V

10.1 流水线形式

11. 虚拟机

11.1 虚拟机监视器(Virtual Machine Monitor)

将虚拟资源映射到物理资源；VMM处理实际的I / O设备，模拟guest的通用虚拟I / O设备。

11.2 计时器虚拟化

本机：在计时器中断时，操作系统挂起当前进程，处理中断，选择并继续下一个进程
虚拟机监视器：VMM挂起当前的VM，处理中断，选择并恢复下一个VM。如果VM需要计时器中断，VMM模拟虚拟计时器，发生物理计时器中断时为VM模拟中断

11.3 指令集支持

特权指令仅(Privileged Instruction)在系统模式/内核模式/特权超级用户模式下可用。如果在用户模式下执行，则陷阱(Trap)到系统。
所有物理资源只能使用特权指令进行访问：包括页表和其他状态信息，中断控制，I / O寄存器（系统调用例外）

11.4 虚拟内存

将主内存用作辅助（磁盘）存储的“缓存”，由CPU硬件和操作系统（OS）共同管理
CPU和OS将虚拟地址转换为物理地址：

VM“块(Block)”称为页面(Page)
VM转译“未命中(Miss)”称为页面错误(Page Fault)

11.5 Page Fault

在页面错误时，必须从磁盘中获取页面：需要数百万个时钟周期，由操作系统代码处理

11.6 页表（Page Tables）

CPU中的页表寄存器指向物理内存中的页表
页表条目数组，由虚拟页码索引
如果内存中有页面，PTE(Page Table Entry)存储物理页码，加上其他状态位
如果页面不存在，PTE可以参照磁盘上交换空间中的位置

11.7 TLB (translation lookaside buffer)

TLB是地址转译的快取（转换后备缓冲区）
遗失可由硬件或软件处理
TLB没命中

如果页面在内存中：从内存中加载PTE，然后重试。可以在硬件或在软件中处理。

如果页面不在内存中（页面错误）：操作系统处理获取页面并更新页面表，然后重新启动故障指令(Faulting Instruction)

11.8 未命中原因

强制性未命中(Compulsory misses)（冷启动未命中）：首次访问块
容量缺失(Capacity misses)：由于缓存大小有限，稍后再次访问替换的块
冲突未命中(Conflict misses)：在非完全关联的缓存中，由于竞争一组中的条目。不会在总大小相同的完全关联的缓存中发生。

11.9 缓存设计平衡

11.10 一致性协议

监听协议(Snooping protocol)：每个缓存监视总线的读/写
基于目录的协议(Directory-based protocol)：目录中块的缓存和内存记录共享状态

11.11 Coherence vs. Consistency

Coherence模型主要考虑对于同一内存位置的写操作对于所有的处理器的可见性。
存储的Consistency模型的范围则广得多。和Coherence相比，其主要差别有：

1.Consistency不仅针对同一内存区域的访问；
2.Consistency中的内存访问包括读和写两种。

12. 指令集架构(Instruction Set Architecture, ISA)

12.1 x86

为何需要寄存器?：片内RAM的速度较快，不受外部干扰。
为何处理器需要要多样的寻址模式? ：立即数寻址和寄存器寻址在效率上是最快的，但寄存器仅有几个非常宝贵不可能将操作数都存入其中等待使用，立即数的使用场合也非常有限，这样就需要将数据保存在内存中，然后使用直接寻址、寄存器间接寻址、寄存器相对寻址、基址加变址寻址、相对基址加变址寻址这些寻址方式将内存中的数据移入寄存器中。

12.2 MIPS

分支延迟槽 (Branch delay slot)：就是位于分支指令后面的一条指令，不管分支发生与否其总是被执行，而且位于分支延迟槽中的指令先于分支指令提交 (commit)。

引入分支延迟槽的目的主要是为了提高流水线的效率。

12.3 ARM

1、ARM指令都是32位定长的
2、寄存器数量丰富（37个寄存器）
3、普通的Load/Store指令
4、多寄存器的Load/Store指令
5、指令的条件执行
6、单时钟周期中的单条指令完成数据移位操作和ALU操作
7、通过变种和协处理器来扩展ARM处理器的功能
8、扩展了16位的Thumb指令来提高代码密度

特色

1、一些特定的指令周期数可变。
例如多寄存器装载或存储的Load/Store指令
2、内嵌的桶形移位寄存器产生了更复杂的指令。
在一个寄存器被一条指令使用之前，桶形移位寄存器可以处理这个寄存器中的数据。可提高代码密度。
3、Thumb16位指令集
ARM处理器有两种工作状态。ARM状态下指令长度为32位，Thumb状态下指令长度为16位。
4、条件执行
当某个特定条件满足时指令才会被执行。这个特性可以减少分支指令的数目，可以提高代码密度。
5、增强指令
数字信号处理器（DSP）指令被加入到标准的ARM指令中，如支持快速的16*16乘法操作。

12.4 RISC-V

基准指令：
40 余个基准指令，已固化不变
标准扩展指令：
一套标准的可选扩展指令，可能会缓慢演化
特定指令：
用户专为特定片上系统设计的独特指令，无需考虑复用性；各家可对其实现进行专利保护。

1. 基本指令格式

4种核心指令格式（R/I/S/U）,都是固定32位长度的指令。基于立即数的处理，还有SB/UI这两种指令格式的变种。

2. RISC-V指令集架构特点

一、模块化：支持模块化可配置的子集。
二、可扩展性：支持可扩展定制指令。
三、改进之前指令集架构：
（1）仅支持小端格式。
（2）放弃“一次读多个寄存器指令”和一次性写多个寄存器指令。
（3）去除存储器访问指令的地址自增和地址自减模式。
（4）规整的指令编码格式。
（5）简化的分支跳转指令和静态预测机制。
（6）不使用分支延迟槽。
（7）不使用指令分支延迟码。
（8）运算指令的结果不产生异常。
（9）16位的压缩指令有其对应的32位指令。
（10）支持多线程存储器模型。
（11）支持原子指令。

3. 多线程存储器模型-FENCE栅栏操作

FENCE就是一个栅栏操作，其前后指令之间不能被乱序，可用于线程间的同步。

FENCE.I用于同步指令和序列流，用于线程内的同步。

Fences用于在设备 I/O 和内存访问上强制执行顺序

4. 设计原理

简洁有利于规律性，规律性使实施更简单，简单性以更低的成本实现更高的性能

越小越快

好的设计需要好的折衷

5. RISC-V寄存器

13. 并行设计

13.1 并行编程

难点
分区(Partitioning)
协调(Coordination)
通讯开销(Communications overhead)
阿姆达尔定律
顺序部分可能会限制加速(Speedup)

$\begin{array}{c} Speedup = {1 \over (1-F_{parallelizable}) + F_{parallelizable}/n} \end{array}$

其中， $n$ 为处理器个数， $F_{parallelizable}$ 为可并行代码比例。

13.2 指令和数据流

13.3 多线程

在线程中，通过调度(scheduling) 和寄存器重命(register renaming)名来处理依赖项。

14. 链接器

14.1 目的

Modularity
Efficiency

14.2 功能

符号解析（Symbol resolution）
重定位（Relocation）

14.3 三种目标文件

可重定位目标文件（.o）
可执行目标文件（.out）
共享目标文件（.so）

14.4 ELF文件（Executable and Linkable Format）

是上述三种目标文件的统一格式。

14.3 符号解析

全局链接器符号：当前模块中定义的非静态的C函数和全局变量
外部符号：其他模块中定义的非静态的C函数和全局变量
局部符号：带static属性的C函数和全局变量

【注】C语言中可以利用static属性来隐藏变量和函数。

任何带static属性的全局变量和函数都是私有的。

任何不带static属性的全局变量和函数都是公有的。

伪节

三个特殊伪节，他们在节头部表中没有条目。
ABS：代表不应该被重定向的符号
UNDEF：代表未定义的符号，即在本模块引用在其他模块定义的符号
COMMON：表示还未被分配位置的为初始化的数据目标
【注】只有可重定位目标文件才有这些伪节，可执行目标文件没有。

COMMON vs .bss vs .data

COMMON：未初始化的全局变量
.bss：未初始化的静态变量，以及初始化为0的全局变量和静态变量
.data：已初始化的全局变量和静态变量

强符号和弱符号

函数和已初始化的全局变量是强符号，为初始化的全局变量是弱符号

不允许有多个同名的强符号

如果一个强符号和多个弱符号同名，则选择强符号

如果有多个弱符号同名，则从中任选一个

内存分配顺序

对于局部变量而言，内存分配的顺序和代码的顺序是一样的。由于是在栈分配的，因此先定义的变量的地址要高于后定义的变量的地址

对于已经初始化的全局变量，静态局部变量，是确定的。编译器会分配相应的空间，因此它们的内存分配顺序是按照定义的顺序。对于同一源文件中未初始化的全局变量，从实验来看，它们是按照字母顺序分配内存的，不论定义顺序。对于不同源文件间全局变量，是按照链接器处理的顺序。

静态库解析

在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件和存档文件。

在扫描过程中，链接器维护一个可重定位目标文件集合E、一个未解析（即已引用但尚未定义）的符号集合U、一个已定义的符号集合D

缺点：

存储时磁盘空间存在大量冗余

运行时内存空间存在大量冗余

库更新导致所有程序需要显示重新链接
![注]静态库文件是.a文件，一种归档文件。