体系结构复习笔记

2022-03-01 15:34:29 浏览数 (1)

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没命中
  1. 如果页面在内存中：从内存中加载PTE，然后重试。可以在硬件或在软件中处理。
  2. 如果页面不在内存中（页面错误）：操作系统处理获取页面并更新页面表，然后重新启动故障指令(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属性来隐藏变量和函数。

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

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

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

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

  1. 不允许有多个同名的强符号
  2. 如果一个强符号和多个弱符号同名，则选择强符号
  3. 如果有多个弱符号同名，则从中任选一个

内存分配顺序

  1. 对于局部变量而言， 内存分配的顺序和代码的顺序是一样的。 由于是在栈分配的， 因此先定义的变量的地址要高于后定义的变量的地址
  2. 对于已经初始化的全局变量， 静态局部变量， 是确定的。 编译器会分配相应的空间， 因此它们的内存分配顺序是按照定义的顺序。对于同一源文件中未初始化的全局变量， 从实验来看， 它们是按照字母顺序分配内存的， 不论定义顺序。对于不同源文件间全局变量， 是按照链接器处理的顺序。
静态库解析

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

  1. 在扫描过程中，链接器维护一个可重定位目标文件集合E、一个未解析（即已引用但尚未定义）的符号集合U、一个已定义的符号集合D
  2. 缺点：
  • 存储时磁盘空间存在大量冗余
  • 运行时内存空间存在大量冗余
  • 库更新导致所有程序需要显示重新链接 ![注]静态库文件是.a文件，一种归档文件。
动态库解析
  1. 链接：加载时或运行时
  2. 库打桩机制：
  • 编译时：显示函数包装
  • 链接时：链接符号时替换
  • 加载/运行时：通过dlsym实现定制版函数

14.4 重定位

15. 虚拟内存

15.1 动态内存分配

  • 分配器类型：
  1. 显示分配器：malloc和free
  2. 隐式分配器：垃圾回收器（不需要显示free）
  • 分配器
  1. 限制
  • 处理任意请求序列
  • 立即响应请求
  • 只使用堆
  • 对齐块（对齐要求）
  • 不修改已分配的块
  1. 目标
  • 最大化吞吐率：吞吐率定义为单位时间内完成的请求数（请求为malloc或free）
  • 最大化内存利用率：
  • 碎片
  1. 内部碎片：由于malloc需要考虑块对齐，所以实际分配空间 >= 请求分配空间，以及块头部信息也属于内部碎片。由之前的请求造成，容易测量。
  2. 外部碎片：不同malloc块间无法利用的小碎片空间。由未来的请求造成，不容易测量。

15.2 链表

  • 隐式空闲链表 根据每个块的长度链接在一起。
  1. 首次适配
  2. 下一次适配
  3. 最佳适配
  • 显示空闲链表 通过指针链接所有块。
  1. LIFO
  2. Address-ordered
  • 分离的空闲链表
  1. 优点：
  • 高吞吐率：对于2的幂次来划分大小类分配和释放只需要常量时间
  • 更好的内存利用率（首次适配接近最佳适配）

15.3 垃圾回收

  • 支持垃圾回收：Python、Ruby、Java、Perl、ML、Lisp、Mathematica
  • C和C 的GC必须是保守的，其根本原因在于：C语言不会用类型信息来标记内存位置。
  • Mark&Sweep垃圾收集器

使用深度优先遍历内存有向图。

  1. 标记阶段：为每个根节点调用mark函数，标记出所有的可达块。
  2. 清除阶段：在堆中每个块上反复循环，释放它所遇到的所有未标记的已分配块。

15.4 C语言与内存有关的错误

  • 间接引用坏指针：scanf
  • 读未初始化的内存：malloc不会将申请的堆空间清零（calloc会）
  • 允许栈缓冲溢出：gets和fgets
  • 假设指针和它们指向的对象是相同大小的
  • 造成错位错误：访问超出申请空间，覆盖其后的内存位置。
  • 引用指针，而不是它所指向的对象：C语言运算符优先级和结合性
  • 误解指针运算：指针运算单位为其指向的对象的大小
  • 引用不存在的变量：局部变量在函数结束后会被释放
  • 引用空闲堆块中的数据：堆指针被释放后又引用
  • 内存泄露：申请使用完后没有释放
  • 多次释放同一个块
  • 只释放了数据结构空间，没有释放其内部的指针指向的空间

16. IO

16.1 Unix IO

  • 文件类型：
  1. 普通文件
  2. 目录
  3. 套接字 …
  • 内核为每个进程维护一个当前工作目录

16.2 RIO

解决不足值出现的问题。

16.3 共享文件

  • 描述符表
  • 文件表
  • v-node表

17. 程序优化

17.1 提高并行性

  • 循环展开 多累计变量
  • 循环展开 重新结合变换

17.2 限制因素

  • 寄存器溢出
  • 分支预测与预测错误处罚

解决：条件数据传送（不是所有操作都可行）

17.3 加载和存储

  • 加载操作延迟和数据相关性能下降
单片机 缓存 arm c++

0 人点赞