计算机体系结构总结

第一部分 简单机器设计 CH1、CHA、CHC

Intro

1、计算机体系结构

广义定义：计算机体系结构是抽象层的定义，这些抽象层使得我们可以使用可用的制造技术高效的实现信息处理应用系统

PPT定义：计算机体系结构研究如何设计、组织，以及使用可用的生产技术实现信息处理系统，该系统可有效地执行软件应用，满足价格、功耗和性能约束

课本定义：体系结构涵盖了计算机设计的三个方面：指令集体系结构、组成或微体系结构、硬件

2、计算机组成与实现

计算机组成：ISA的逻辑实现

计算机实现：计算机组成的物理实现(硬件)

3、计算机分类

个人移动设备：强调性能和实时性

桌面计算：强调性价比

服务器：强调可用性、可扩展性和吞吐率

仓库级计算机：强调可用性和性价比

超级计算机：强调浮点性能和高速内部互联

嵌入式计算机：强调价格、能耗以及面向特定应用的性能

量化设计与分析基础 CH1

1、集成电路中的能耗和能耗趋势

动态能耗：

每个晶体管逻辑变为0->1->0或1->0->1的能耗(两次转换) 正比于 容性负载 X 电压$^2$

每个晶体管需要的功率 正比于 1/2 X 容性负载 X 电压$^2$ X 开关频率

降低频率可以降低功耗但是不一定会降低能耗；降低电压可以有效降低功耗和能耗

热设计功率TDP：

通常低于峰值消耗但是高于平均消耗，与功耗没有必然关系

减少动态功耗的技术：

①、关闭非活动模块的时钟

②、降低电压和频率

③、针对典型场景进行设计

④、超频

静态功耗：

静态功率 正比于 静态电流 * 电压

给定负载下能耗越小则能效越高

功耗应该被看成是一个约束条件，能耗更适合度量

2、性能

性能的两种含义：执行时间、吞吐率

唯一稳定、可靠的性能度量是实际程序的执行时间，性能等于执行时间的倒数

执行时间的两种含义：响应时间(完成一项任务的延迟，包括磁盘访问等所有相关时间)、CPU时间(仅包括处理器执行计算的时间)

吞吐率指单位时间完成的任务数

缩短任务执行时间可提高吞吐率；硬件并行可提高响应时间和吞吐率

处理器性能公式：

CPI = 程序的CPU时钟周期数/指令数

CPU时间=指令数 X CPI X 时钟周期的时间

影响指令数：ISA和编译器

影响CPI：计算机组成和ISA

影响时钟周期时间：硬件和组成

若不同类型的指令具有不同的CPI，则

$CPI = \sum ^n _{i=1} Feq_i \times CPI_i$ $Feq_i$为第i条指令占总指令数的比例

3、Amdahl定律

总加速比 = $\frac{1}{(1-升级比例) + 升级比例/升级加速比}$

结论：如果仅仅改进一部分计算的性能，则加速比不会超过$\frac{1}{1-升级比例} $

Amdahl定律基于的假设：问题规模是常量；应用于多处理器系统的假设：研究随着处理器数目增加性能的变化

4、性能的评估

MIPS：

每秒百万条指令数

MIPS = 1/(CPI * T * $10^6$ ) T为时钟周期的时间

FLOPS：

基于浮点操作而非指令

Benchmark：

分类：真实程序、修改过的程序、核心程序、小测试程序、合成测试程序

性能的综合评价：

SPEC Ratio = 基准计算机上某程序的执行时间/待测计算机上该程序的执行时间

采用几何平均的方式来综合：$^n \sqrt{\prod ^n _{i=1} SPEC \ ratio_i}$

采用几何平均的好处：几何平均的比值等于比值的几何平均；几何平均的比值等于性能比值的几何平均

指令集体系结构 CHA

1、ISA分类

栈体系结构：操作数隐式存在与栈顶部

累加器体系结构：操作数隐式存在于累加器内

通用寄存器体系结构：只有显式操作数(寄存器或存储器)，同时这个体系结构可以分为寄存器-存储器体系结构(可以用任意指令访问存储器)和载入-存储体系结构(只能用载入和存储指令来访问存储器)

2、存储器寻址

尾端：大尾端(字的地址是字中最大字节的地址)、小尾端(字的地址是字中最小字节的地址)；即小尾端需要将字节倒序存放，大尾端不变

寻址方式：

位移量寻址、立即数寻址和寄存器间接寻址使用最多

位移量的大小应该在12-16bits，立即数的大小应该在8-16bits

3、操作数的类型与大小

操作数的类型一般由操作码来指定

对单字和双字的数据访问最多

4、指令集中的操作

一般计算机都支持算逻运算、数据传送和控制操作，其他类别的操作不同的系统差别很大

CISC的指令集操作功能设计：

面向目标程序优化，缩短程序长度和执行时间；用新的指令代替使用频率高的指令串

面向高级语言和吧编译器优化，缩小高级语言和机器语言的差距

RISC的指令集操作功能设计：

减小CPI，减小指令和寻址方式的种类，采用固定格式，流水线

5、控制流指令

四类：条件分支、跳转、过程调用、过程返回

寻址方式：PC相对寻址、寄存器间接寻址

过程调用：调用者保存(通常使用)、被调用者保存

6、指令集编码

三类编码方法：变长编码、定长编码(将操作和寻址方式合并到操作码中)、混合编码

代码规模重要，则选择变长编码；性能重要，则选择定长编码

7、MIPS指令集体系结构

32个64位通用寄存器、32个64位浮点寄存器、一些特殊寄存器

立即数字段和偏移量字段都是16位

所有指令都是32位，操作码占6位

3种指令格式：I型、R型、J型

4类操作：载入/存储、ALU运算、分支与跳转、浮点运算

跳转指令确定目标地址：将26位偏移量左移2位后替换PC后28位、寄存器存储目标地址

2种跳转类型：跳转、跳转并链接(还会把顺序下一条指令的地址放入R31)

8、RISC-V指令集体系结构

设计理念：通用

32个32位整型寄存器、32个64位浮点寄存器、FP状态寄存器、PC

变长指令格式(三种长度)

9、微程序控制

微控制器：

地址线：$\mu PC$位数+操作码位数+2

数据线：$\mu PC$位数+18

水平型微指令：每条微指令有多个微操作并行，微指令较宽

垂直型微指令：每条微指令代表一个数据通路操作，微指令较窄

流水线 CHC

1、流水线定义

流水线是一种多条指令重叠执行的实现技术

影响流水线性能的因素：

①、最慢的一段

②、流水段所需时间不均衡

③、流水线存在装入时间和排空时间

2、流水线相关

结构相关：

流水线中一条指令可能需要另一条指令的资源

解决方法：

①、将新指令延迟

②、增加新的资源

数据相关：

一条指令可能依赖于先前指令的结果

三种类型：RAW、WAR(反相关)、WAW(输出相关)

解决办法：

①、Interlock机制(流水线停顿)：在issue段保持相关指令，直到相关解除

②、转发机制：通过旁路传递数据

③、投机：猜测一个值继续，猜错了再更正

控制相关：

解决办法：

①、Flush流水线

②、预测未选中

③、预测选中

④、延迟分支

仅仅考虑控制相关时，流水线加速比 = 流水线深度/(1 + 分支频率 * 分支代价)

分支预测：

静态分支预测：利用先前运行过程收集的数据

动态分支预测：BTB、BHT

3、异常处理

异常：有程序执行过程中引起的异常内部事件

陷阱：因异常情况而被迫将控制权转移给监控程序

中断：运行程序之外的外部事件导致的控制权转移

精确异常：如果流水线可以使得引起异常的指令之前的指令都执行完，处理异常完毕后异常指令可以重复执行，则称流水线支持精确异常

流水线中的异常处理：

在流水线中将异常标志保留到提交阶段；针对某一给定的指令，早期流水段中的异常覆盖该指令的后续异常

异常预测：

①、简单的认为异常不会发生

②、检查预测机制：在提交阶段检查是否存在异常

③、恢复执行机制：仅在提交阶段改变机器状态，在发生异常的时候直接丢弃执行结果

4、流水线性能

吞吐率：

$TP = \frac{n}{T_k}$ $n$为任务数，$T_k$为完成n个任务需要的时间

对于各段执行时间都相等的流水线：(假设每段执行时间为$\Delta t$)

$TP = \frac{n}{(k+n-1)\Delta t}$

$TP _{max} = \frac{1}{\Delta t}$

对于各段执行时间不相等的流水线：

$TP = \frac{n}{\sum ^k _{i=1} \Delta t_i + (n-1)max{\Delta t_1, …, \Delta t_k}}$

$TP_{max} = \frac{1}{max{\Delta t_1, …, \Delta t_k}}$

解决瓶颈段的方法：细分瓶颈段、重复设置瓶颈段

加速比：

对于各段执行时间都相等的流水线：

$S = \frac{nk}{n+k-1}$

$S _{max} = k$

对于各段执行时间不相等的流水线：

$S = \frac{n\sum ^k _{i=1} \Delta t_i}{\sum ^k _{i=1} \Delta t_i + (n-1)max{\Delta t_1, …, \Delta t_k}}$

存在流水线停顿的加速比 = 1/(1 + 每条指令的停顿周期) * 非流水化时钟周期/流水化时钟周期

效率：

流水线中设备实际使用时间与流水线运行时间的比值

对于各段执行时间都相等的流水线：

$E = e_1 = … = e_k = \frac{n}{n+k-1} = TP \times \Delta t = S/S_{max}$

对于各段执行时间不相等的流水线：

$E = \frac{n\sum ^k _{i=1} \Delta t_i}{k[\sum ^k _{i=1} \Delta t_i + (n-1) max{\Delta t_1,…,\Delta_k}]}$

5、扩展MIPS流水线，以处理多周期操作

为了实现浮点操作，需要作出以下改变：

EX段操作可能会重复多次、可能存在多个浮点功能单元

延迟：生成结果的指令与使用结果的指令之间必须间隔的周期数

起始间隔/重复间隔：两个给定类型的操作之间必须间隔的周期数

浮点流水线产生的新问题：

①、除法单元未被完全流水化，存在结构冒险

②、指令运行的时间不同，可能存在同一时钟周期发生多次寄存器写入事件

③、由于指令不会按序到达WB段，故可能发生WAW相关

④、指令的完成顺序可能不同于发射顺序

⑤、操作的延迟较长，RAW导致的停顿变多

结构相关解决办法：

在ID段跟踪寄存器写端口的使用，以便能够暂停指令发射；当指令进入MEM或WB段时，暂停冲突的指令，让具有较高延迟的指令先写(因为具有较高延迟的指令更容易导致频繁的RAW相关)

WAW数据相关解决办法：

延迟后续指令的发射，直到前面的指令到达MEM段；废除前面指令的结果

如果在ID段做相关检测，则必须检测完下列相关后才可发射指令：

结构相关、RAW数据相关、WAW数据相关

精确异常处理办法：

①、忽略问题，允许非精确异常

②、缓存操作结果，直到早期发射的指令全部执行完

③、运行非精确异常，但保留足够的信息以便软件能够生成精确的异常序列

④、确保发射指令之前的所有指令都已经完成且没有异常才发射指令

6、MIPS R4000流水线

八级流水线

分解存储器访问的流水段

转发数明显增加

在有转发的情况下，载入延迟增加到2个时钟周期

基本分支延迟为3个时钟周期，在预测分支未发生的情况下，预测正确的分支延迟为1个时钟周期，预测错误的分支延迟为3个时钟周期

影响性能的因素：载入停顿、分支停顿、浮点RAW停顿、浮点结构停顿

降低浮点运算的延迟是第一目标

第二部分 存储系统设计 CH2、CHB

1、存储器层次结构

处理器与DRAM的性能差异逐渐增大，需要利用Cache来缓解

多级层次结构：可以使得存储系统接近第一级存储器的访问速度，但是容量和价格接近最后一级存储器

存储器层次工作原理：时间局部性和空间局部性

寄存器与内存间通过编译器进行调度，Cache与内存间通过硬件进行调度，内存和磁盘间通过硬件和操作系统进行调度

2、Cache性能

CPU执行时间 = (CPU时钟周期数 + 存储器停顿周期数) * 时钟周期时间

存储器停顿周期数 = 指令数 * 存储器访问操作比例 * 缺失率 * 缺失代价 = 存储器访问数 * 缺失率 * 缺失代价 = 缺失数 * 缺失代价

缺失数 = 缺失率 * 存储器访问数

平均访存时间 = 命中时间 + 缺失率 * 缺失代价 = L1命中时间 + L1缺失率 *(L2 命中时间 + L2缺失率 * L2缺失代价)

如果允许乱序执行，则缺失代价需要减去重叠缺失延迟

3、Cache基本概念

映象规则：

直接映射：每个块只能出现在缓存中的一个位置 选择块：块地址 MOD 缓存中的块数

全相联：每个块可以放在缓存中的任意位置

组相连：每个块映射到缓存中的某个组内，可以放在组内的任何位置 选择组：块地址 MOD 缓存中的组数

n路组相联表示一个组中有n个缓存块

相联度越高，则Cache空间利用率越高，失效率越低；但Cache的实现会很复杂

查找方法：

缓存地址由块地址和块偏移组成，块偏移指示数据在块中的位置。块地址由标志和索引组成，索引用来表示组的位置，全相连映象时没有索引

查找时并行比较标志即可

容量为$2^N$字节的Cache，块标志位有32-N比特

替换算法：

直接映射不需要替换算法，全相联和组相联需要

随机替换、LRU、FIFO

LRU的效果在缓存较小时好于其他算法

写策略：

写直达：同时写入缓存和低一级存储器 容易实现、一致性保证但速度慢

写回：仅被写入缓存 速度快、对同一块的多次写入只需要向低一级存储器写一次但是一致性得不到保证

写入缺失时的处理策略：

写分配：先把缺失的块调入缓存再执行写入操作

写不分配：直接写入下一级存储器，不调入缓存

一般情况下写回法用写分配策略；写直达法用写不分配策略

4、基本Cache优化方法

Cache缺失类别：

强制缺失、容量缺失、冲突缺失

2：1Cache经验规则：

大小为N的直接映射Cache的失效率约等于大小为N/2的两路组相连Cache的失效率

优化方法：

减小失效率：

①、增大块大小

较大的块可以降低强制缺失(因为空间局部性)；但是较大的块会增加缺失代价，同时可能增加容量缺失和冲突缺失

所以在增加块大小时，失效率先下降再上升；同时缓存容量越大，获得最低失效率的块大小越大

②、增加缓存容量

可以降低容量缺失；但是会延长命中时间，增加成本和功耗

③、提高相联度

可能会延长命中时间，提高缺失代价

8路组相联的缺失率效果与全相联已经基本一致

④、使用Victim Cache

Victim Cache是一个全相联Cache，位于Cache和内存之间，直接映射Cache丢失的块先放入Victim Cache中，当缺失时先去Victim Cache中看是否有，没有再去内存中获取

减小直接映射Cache的冲突失效

减小缺失代价：

⑤、采用多级Cache

局部失效率：该缓存缺失数除以对该缓存访问数

全局失效率：该缓存缺失数除以总存储器访问次数

每条指令的平均存储器停顿时间 = 每条指令的L1缺失数 * L2命中时间 + 每条指令的L2缺失数 * L2缺失代价

多级Cache能够减小失效开销，缩短AMAT

一级Cache保持较小容量以减小命中时间和能耗(一级Cache的重点是减小命中时间)，二级Cache保持较大容量以降低全局失效率(二级Cache的重点是减小失效率)

多级包容：

在L1中出现的缓存块一定在L2中出现

如果L1缺失L2命中，则将L2中的块拷贝到L1中

如果L1L2都缺失，则从更低一级的存储器中拷贝到L1和L2中

对L1的写操作将会把数据同时写到L1和L2(写直达)；写回策略用于L2和低级存储器之间

若L2中的块被替换出去，则L1中的块也要被替换出去

多级不包容：

L1中的块绝对不会出现在L2中

如果L1缺失L2命中，则将L2中的块与L1中的块互换

如果L1和L2都缺失，则从更低一级的存储器将块仅仅拷贝给L1

L1与L2、L2与更低一级的存储器之间的写策略均为写回

⑥、读操作优先于写操作

对写直达法更有效，写回法用Victim Cache

发生读取缺失时先检查写入缓冲区中的内容，如果没有冲突且存储器可用，则继续读取缺失的处理

减小命中时间：

⑦、避免在索引缓存期间进行地址转换，以缩短命中时间

使用虚拟地址与物理地址相同的一部分来索引缓存，同时将虚拟地址转化为物理地址

5、高级Cache优化方法

缩短命中时间：

①、小而简单的一级Cache

最近一级Cache开始使用较高的相联度

②、路预测

缓存中保存了一些预测位用以预测下一次缓存访问的组中的路或块

但是预测错误会导致更长的命中时间

增加Cache带宽：

③、Cache访问流水化

Cache的访问由多个时钟周期构成

④、无阻塞Cache

Hit under a miss：允许数据缓存在一次缺失期间继续提供hit信号

Hit under multiple Misses：允许数据缓存在多次缺失期间继续提供hit信号

MSHR包含正在等待处理的失效，相同的块可以包含多个Load/Store失效，也可以包含多个未解决的块地址

失效可以分成：第一次发起存储请求的失效、后续失效、MSHR资源耗尽时的失效

具体操作流程：

当Cache失效时，检查MSHR中是否有匹配的块地址：

如果有，则为该地址分配新的表项

如果没有，则分配新的MSHR和表项

如果MSHR资源耗尽，则停顿

当从低级存储器传输块时:

Load：将数据装到指定寄存器

Store：将数据写入指定位置

处理完所有Load/Store失效后，释放表项

⑤、多组缓存

可以给缓存增加访问端口

也可以将多个缓存组织成缓存组

减小失效开销:

⑥、关键字优先和提前重启动

关键字优先：首先请求CPU需要的字，然后再调入块中的其他字

提前重启动：请求顺序不变，但是只要被请求的字一到达就马上发给CPU

通常在块大小比较大的时候，这些技术才有效

⑦、合并写缓冲区

Cache向写缓冲区内写入数据时，先检查缓冲区内是否已经存在被修改的块，若存在，则检查其地址，如果匹配，则将这次的写与该块合并

可以缓解由与写缓冲区满而导致的停顿

I/O地址不能进行写合并

降低失效率：

⑧、编译器优化

减小指令失效：

重新组织指令顺序而不影响程序正确性

减小数据失效：

优化改善数据时间局部性(分块)和空间局部性(循环交换)

通过并行降低失效代价和失效率：

⑨、硬件预取

CPU在执行这一块代码时，提前预取下一块代码

或者是当缺失发生时，处理器同时提取两个缓存块，目标缓存块放在缓存中，另一个放在指令流缓冲区中

⑩、编译器控制预取

寄存器预取：将数据值加载到寄存器中

缓存预取：将数据加载到缓存中

故障性预取：若预取时发生异常则抛出异常

非故障性预取：若预取时发生异常则转换为空操作

循环是预取优化的主要目标：

失效代价较小时，将循环体展开一两次

失效代价较大时，将循环体展开多次以便为较远的数据预取

6、存储器技术与优化

DRAM：破坏性读；每bit一个晶体管；地址线复用

SRAM：每bit六个晶体管

DRAM优化：

①、添加定时信号，允许重复访问行缓冲区，从而节省行访问时间

②、向DRAM接口添加一个时钟信号，使重复传输不需要承担这一开销(SDRAM 同步DRAM)

③、拓宽DRAM宽度(数据总线)

④、在时钟上升沿和下降沿均传输数据(DDR)

降低SDRAM功耗：

①、降低工作电压

②、省电模式

三种存储器组织形式：

Simple：CPU、Cache、Bus、Memory都具有相同的数据宽度

Wide：CPU数据宽度为1个字，其他三个数据宽度为N个字

Interleaved：Memory数据宽度为N个字，其他三个数据宽度为1个字

提高主存性能的方法：增大存储器宽度(并行访问存储器)

多体交叉存储器：

存储体数目 >= 访问体中一个字所需要的时钟周期数

高位交叉编址：取线性地址高位为体号，低位为体内地址

低位交叉编址：取线性地址低位为体号，高位为体内地址

7、虚拟存储器

允许应用程序的大小超过主存容量

虚拟存储管理是在主存-磁盘这个层面上的

Cache与虚拟存储器的区别：

Cache是为了提高访存速度；虚拟存储器为了提高存储容量

Cache失效由硬件处理；虚拟存储器失效由OS处理

Cache的地址空间与CPU无关；虚拟存储器的地址空间由CPU地址确定

Cache的下一级存储器是主存；虚拟存储器的下一级存储器是磁盘

两种虚拟存储器：

页虚拟存储器：采用固定大小的块，地址为页编号+页内偏移量

段虚拟存储器：采用大小可变的块，两个字来表示地址，一个字表示段号，一个字表示段内偏移量

映象规则：

全相联映射

查找算法：

查找段表或页表，得到段基址或页基址，再与偏移量相加得到物理地址

替换规则：

LRU

写策略:

写回法

页大小选择:

选择较大的页大小：

优点：减小页表大小，降低TLB缺失率，提高传输效率

缺点：碎片多，进程启动时间长，缺失代价增大

TLB：

虚拟存储器每次访存需要访问两次物理存储器：第一次访问页表获取物理地址，第二次获取数据

TLB存放经常使用的页表项，是整个页表部分内容的副本

TLB每一个表项存储虚拟地址、物理地址、保护字段、有效位、使用位、重写位

TLB必须在片内，以提高访问速度，相联度较高

第三部分 指令级并行 CH3

1、指令集并行的挑战

真数据相关：

前面指令的结果会被后面指令用到；

前面指令结果被中间指令用到，中间指令结果被后面指令用到，则后面指令与前面指令也是真数据相关

名称相关：

两条指令使用相同的寄存器或存储器位置但是没有数据流动时

包括反相关(WAR)、输出相关(WAW)

可以通过重命名解决，不是真正的相关

流水线CPI = 理想CPI + 结构相关停顿 + WAR停顿 + RAW停顿 + WAW停顿 + 控制相关停顿 + 存储器停顿

WAR冒险只在乱序执行中出现

2、软件方案：循环间展开

首先要确定迭代间不相关

删除不必要的循环终点测试和分支，调整循环终止测试代码

注意调整偏移量

注意Load/Store指令，需要保证不同迭代间没有引用同一存储器地址

展开时使用不同的寄存器，去除名称相关

3、硬件方案

基本思想：允许乱序执行，停顿后的指令继续向前流动

ID段被分成两个阶段：发射、读操作数

EX阶段需要用多个功能单元

发射是按指令顺序的，但是执行完毕的指令不是按顺序的

顺序发射有利于数据流分析

记分牌：

四个阶段：

发射 — 当指令没有结构相关和WAW相关时，发射指令

读取操作数 — 当没有RAW相关时(即现在寄存器的数据已经是最新的)，读取操作数

执行 — 功能单元接收到数据后开始执行

写结果 — 当没有WAR相关时，写结果

记分牌结构：

指令状态：指出指令进行到哪一阶段

功能单元状态：

9个字段：忙、Op(此单元内正在进行的操作)、Fi(目标寄存器)、Fj,Fk(源寄存器号)、Qj,Qk(产生源操作数的功能单元)、Rj,Rk(指示源操作数已就绪但尚未读取的标志)

寄存器结果状态：指出哪些活动指令以该寄存器为目标寄存器

缺点：没有转发、指令窗口较小、功能部件数目较少、WAR和WAW都是通过停顿解决

Tomasulo算法：

每个功能单元(载入存储功能单元除外，他们的是载入缓冲区和存储缓冲区) 都有保留站，寄存器重命名功能由保留站提供，保留站在一个操作数可用的时候回马上提取并保存，操作数由保留站提供给功能单元

优势：冒险检测逻辑的分布；消除了WAW和WAR停顿

保留站的结构：

Op(对源操作数执行的操作)、Qj,Qk(产生源操作数的保留站编号，该值为0时表示操作数已经准备好；缓冲存储区中的Qk表示产生地址偏移量的保留站)、Vj,Vk(源操作数的值)、Busy、A(用于保存载入存储指令的存储器地址信息)

寄存器堆中有一个字段Qi表示以此寄存器为目的寄存器的操作所在的保留站编号

三个阶段：

发射：当有匹配的空保留站时，将指令发送到该保留站；同时将对应的已经准备好的寄存器中的值也传输到保留站，若有操作数为准备好，则跟踪生成这些操作数的功能单元。如果没有匹配的空保留站，则停顿。消除了结构相关和WAR、WAW相关。

执行：当所有操作数可用时，开始执行计算。避免RAW相关

写结果：当计算完成后，将结果写入对应的寄存器和需要该结果的保留站

缺点：受限于CDB

支持推断执行的Tomasulo算法：

重排序缓冲区ROB：保存已经完成执行但是没有提交的结果；包含四个字段：指令类型、目的字段、值字段、就绪字段

四个阶段：

发射：当有匹配的空保留站且ROB中有空项时，才发射指令；同时将已经准备好的数据从寄存器或ROB中传输到保留站；为指令执行结果分配的ROB项目编号也发给保留站

执行：当操作数都就绪后，开始执行；如果没有就绪就监视CDB

写结果：将结果发送给等待结果的保留站，同时发送给存储结果的ROB

提交：当一条指令到达ROB头部并且值可用时，如果该指令不是分支预测错误指令，则处理器将对应的值写入对应的寄存器或存储器(存储指令)，删除表项；如果是分支预测错误指令，则刷新ROB，重新从正确分支的指令处开始执行

该算法可以实现精确中断，当产生中断的指令到达ROB头部时，刷新ROB即可

存储器引用的数据相关：

主要避免RAW真相关，假相关通过重命名已经解决

对于任何一条载入指令，只要它访问以前的存储指令存储数据的地址，那么当这条存储指令没有写入数据之前，载入指令不能执行存储器访问

当不知道前面存储指令的地址时，有两种方法处理数据相关

非推测：停顿后面的载入指令，直到我们可以确定两者的目的地址不相等

Total ordering：完全按照指令顺序来

Partial ordering：载入指令前面的存储指令已经完成地址计算，可能会乱序执行载入指令

Load ordering，store ordering：载入指令可能在存储指令之前执行

推测：推测两条指令相关还是不相关，推测错误通过ROB刷新

store ordering：假设载入指令和前面未计算出地址的存储指令不相关

4、相关预测器

(m,n)相关预测器：

根据最近m次分支的执行情况选择预测器，每个预测器有n个预测位

可以由分支的低位地址和m个全局位组合形成索引从而选择正确的预测器

(m,n)局部预测器：

根据该分支的最近m次执行情况来预测该分支

竞赛预测器：

结合相关预测器和局部预测器

5、多发射技术

超标量技术：

每个时钟周期发射的指令数不定

在同一时刻发射的指令数越多，译码和发射就越困难

代码量较小

静态超标量技术：有相关就会停止发射

使用Tomasulo算法的动态超标量技术：

每个时钟周期发送两条不同类型的指令：一条整形指令，一条浮点指令

存储器引用问题：

载入操作前检测存储操作队列中的存储地址，防止RAW相关

存储操作前检测载入队列中的地址，防止WAR相关

载入指令按序进行，防止WAW相关

超长指令字技术VLIW：

每个时钟周期发射的指令数固定

由编译器调度使得多个单操作合并为一个超长指令

代码量较大

多发射技术的限制：

调度延时、需要大量的硬件资源来支持并行(功能部件数、指令访问带宽、寄存器文件端口数、存储器端口数及带宽)

6、多线程技术

使多个线程以重叠方式共享单个处理器的功能单元

在流水线中交叉执行来自不同线程的指令

粗粒度多线程：仅在发生成本较高的停顿时才切换线程

细粒度多线程：每个时钟周期都切换线程

同时多线程：通过寄存器重命名和动态调度执行多个线程的多个指令，在同一个时钟周期内运行多个线程的指令

第四部分 数据级并行 CH4

1、动机

ILP的缺陷：

程序内在并行性不高、时钟频率的提高可能导致CPI增加、有时候很难指令预取、Cache有时候命中率较低

SIMD的优势：

允许程序员继续以串行方式思考、SIMD比MIMD更节能

2、向量体系结构

基本思想：两个向量的对应分量进行运算，产生一个结果向量

基本特性：

一条指令包含多个操作、每一个结果独立于前面的结果、以已知方式访问存储器，降低延时，不需要数据Cache、减少控制相关

基本结构：

存储器-存储器型向量计算机的缺陷：需要较高的存储器带宽、重叠执行难、启动时间长

向量处理机的基本组成：

向量寄存器、向量功能单元、向量载入/存储单元、标量寄存器

向量执行时间：

convey：书上的定义：护航指令组，不能包含任何结构相关，数据相关的指令可以通过链接技术放在一个convey中；PPT定义：可以在同一时钟周期开始执行的指令集合，不能还有任何相关

chime：执行一个convey需要的大概时间

向量启动时间：功能部件延时(一个操作通过功能部件的时间) + 截止时间(运行下一条向量指令的间隔时间)

车道：

每个车道包含向量寄存器组的一部分和来自向量功能单元的一条流水线

每个向量功能单元使用多条流水线

向量长度：

VLR寄存器控制向量操作的向量长度，但是其值不能超过最大向量长度

在不知道程序会不会超过最大向量长度MVL时，使用条带挖掘，第一次循环做最小片，之后的循环按最大片做

向量处理器性能参数：

$R_{\infty}$：向量长度为无限长时的流水线最大性能，常用MFLOPS作为单位

$R_{n}$：表示向量长度为n时的流水线性能

$N_{1/2}$：达到$R_{\infty}$一半所需要的向量长度，用于评价启动时间

$N_v$：向量流水线性能优于标量串行方式的向量长度临界值

存储器组：

向量处理器使用存储器组以便在同一个时钟周期访问多个存储器，使得存储器速率与处理器速率能够匹配

非单位步幅的存储器元素载入可能会引起组冲突而导致停顿，引起组冲突的条件：

组数 / (步幅与组数的最小公倍数) < 组繁忙时间

链接:

对于两条存在数据相关的指令，当前一条指令的第一个元素计算完毕后就可以启动后一条指令，而不是等到前一条指令执行完毕后才启动后一条指令

条件执行：

向量遮罩寄存器：向量操作仅对在向量遮罩寄存器中对应为1的向量元素执行

缺陷:

对于向量遮罩寄存器中为0的向量元素，也会浪费一定的执行时间

有些向量处理器中的向量遮罩寄存器仅控制对目标寄存器的写，所有执行操作仍然后进行，所以可能会有除0的异常

集中-分散：

专门针对稀疏矩阵进行处理

集中操作：使用索引向量，将稀疏矩阵中的非0元素取出放到一个密集向量中运算

分散操作：密集向量运算完成后，再通过相同的索引向量分散到整个稀疏矩阵

缺陷：存储器访问速度远低于非索引载入访问

3、阵列处理器

SIMD

用单一的控制部件控制每个处理器对不同的数据做相同的操作，用的还是标量指令

VLIW是将多个独立的操作放到一起执行，而阵列处理器则是将单个操作作用到不同数据上

4、SIMD指令集的多媒体扩展

在已有的ISA中添加一些向量长度很短的向量指令，将已有的64bit寄存器拆成2个32bit或4个16bit的寄存器，以便于进行向量操作

具有受限的指令集和受限的向量长度

5、GPU

编程模型：

SPMD：Single Program Multiple Data 可以在SIMD机器上执行

每个线程执行相同的代码，处理不同的数据

一组执行相同指令的线程被动态组织成Warp

GPU组成：

GPU由多个并行核组成，每个核是一个SIMD处理器

CPU将整个Grid发送到GPU，Grid中的每个线程块分配给一个并行核(多个线程块也可在一个核上运行)

执行模型：

SIMT：Single Instruction Multiple Thread

优点：每个线程可以在任何标量流水线上运行；线程组织成Warp形成SIMD处理模式

通过Warp交叉执行的细粒度多线程技术来隐藏存储器访问和功能部件的延迟

与传统向量机的对比：

不需要启动时间、每个线程可以单独对待，使用独立的流水线，ISA不需要更改

分支处理：

一个Warp中的线程可能会执行分支指令，所以线程会有不同的执行路径，即分支发散

分支同步堆栈：保存分支的路径地址、保存该路径的屏蔽字

指令标记：管理何时分支、何时汇聚

CUDA线程的控制流由PTX分支指令、由程序员指定的每个线程车道的1比特谓词寄存器控制

当各个线程选择的方向不一致时，创建一个屏蔽向量来指示各个线程的转移方向，继续执行分支失败的路径，将分支成功的路径压入堆栈，等待后续执行

合并：

分支发散之后，动态合并执行相同指令的Warp

存储器访问：

专用存储器/本地存储器：每个核中的每个SIMD车道获得其专用存储器，线程级

本地存储器/共享存储器：每个核上的SIMD车道共享，线程块级

GPU存储器/全局存储器：整个GPU共享，外部主机可读取和写入，Grid级

##第五部分 线程级并行 CH5

1、MIMD成为通用多处理机体系结构的选择的原因

灵活性、可以充分利用商品化微处理器在性价比方面的优势

2、不同通信机制的优点

共享存储器：易于编程、简化编译器、通信开销低、Cache减小通信延迟和访问冲突

消息传递：硬件简单、通信显式

3、并行处理的挑战

①、程序中有限的可用并行

②、通信成本较高

4、存储器访问的序问题

存储同一性(consistency)：不同处理器发出的所有存储器操作的序问题

存储一致性(coherence)：不同处理器访问相同存储单元时的访问序问题

5、集中式共享存储体系结构的Cache一致性问题

一致性问题产生的原因：I/O(memory 与disk)，不同处理器的Cache(cache与cache)

存储器是一致的：对任何一个数据项进行读取时都会返回最新的写入值；所有处理器都看到了写入的结果，写入才算完成；允许无序读，但必须是串行写

Cache提供两种功能以保证一致性：迁移(降低延迟、降低存储器带宽需求)、复制(降低延迟、降低争用)

缓存一致性协议：

目录式：共享数据块的状态及相关信息被保存在目录中

监听式：每个Cache保存自己的共享块的状态和信息

基于监听的两种一致性协议：

写作废(更常用)：在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权

写更新：当一个处理器写某数据项时，通过广播使其它Cache中所有对应的该数据项拷贝进行更新

写作废协议在写入时的性能较高，写更新协议在读取时的性能较高

MSI写作废协议：

三个状态：Modified、Shared、Invalidate

处理器读操作：如果miss，则产生总线读缺失；如果hit，则不产生总线事务

处理器写操作：块状态为非M时，产生总线排他读信号(导致其他Cache中对应块作废)；块状态为M时，如果hit，不产生总线事务；如果miss，产生总线排他读信号，还要将块写回存储器

当一个Cache观察到针对自己的块的总线读信号时：如果该块状态为M，则更新存储器和其他Cache，终止存储器访问，自己向请求该块的Cache提供该块，该块状态变为S

当一个Cache观察到针对自己的块的总线排他读信号时：作废该块，如果该块状态为M，终止存储器访问，自己向请求该块的Cache提供该块，同时该块作废

写传播：对任意一个S块或I块的写，其他Cache都可见

写串行：所有总线上的写操作被总线串行化，并不是所有写操作都会出现在总线上(对M块的写hit不会)

缺点：读进并修改一个块，会产生两个总线事务，读(I -> S)，写(S -> M)

MESI写作废协议：

四个状态：Modified、Shared、Invalidate、Exclusive(表示这个块时独占的且是干净的)

处理器读操作：如果miss，产生总线读缺失，如果其他Cache有同样的块，则块状态为S，否则为E；如果hit，不产生任何总线事务

处理器写操作：如果hit，块状态为I，产生总线排他读信号，块状态为S，产生总线升级信号，块状态为E或M，不产生总线事务；如果miss，产生总线排他读信号，如果块状态为M，还要将块写回存储器

当一个Cache观察到针对自己的块的总线读信号时：如果块状态为E，则变为S；如果该块状态为M，则更新存储器和其他Cache，终止存储器访问，自己向请求该块的Cache提供该块，该块状态变为S

当一个Cache观察到针对自己的块的总线排他读信号时：作废该块，如果该块状态为M，终止存储器访问，自己向请求该块的Cache提供该块，同时该块作废

当一个Cache观察到针对自己的块的总线升级信号时：仅作废块

MOESI写作废协议：

第五个状态：Owned，该状态表示该Cache拥有该块的最新值，存储器中的值不是最新的

同时S态的块内容也不一定与存储器一致，可能是与O态的块内容一致

监听协议的缺点：

总线的可扩放性收到限制、在非总线的网络上监听困难

6、集中式共享存储体系结构的Cache性能

由单处理器Cache性能加上Coherence miss

Coherence Miss：由共享块的写操作引起

真miss：因为对一个变量的写导致某一块作废之后，另一处理器读取同一变量

假miss：因为对一个变量的写导致某一块作废之后，另一处理器读取不同变量(块大小为1个字时这种失效不会发生)

7、分布式共享存储结构的Cache一致性问题

目录协议

目录在共享Cache中，共享Cache包括了所有私有Cache的内容

每个块含有k个presence bits(指示含有该块的CPU)和一个状态位

对于私有Cache，有三种状态：S、M、I

对于共享Cache，有四种状态：Modified(只有一个私有Cache是这个块的拥有者)、Owned(共享Cache是Modified块的拥有者)、Shared、Uncached

CPU发出读缺失信号：块状态为M，目录去对应的私有Cache中取回块放入共享Cache中，私有Cache中的块状态变为S，共享Cache中的块状态变为O，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为S；块状态为S或O，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为S；块状态为U，从存储器中取出该块，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为S；

CPU发出写缺失信号：块状态为M，目录去对应的私有Cache中取回块放入共享Cache中，私有Cache中的块状态变为I，共享Cache中的块状态变为M，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为M；块状态为S或O，目录根据presence bit给所有拥有该块副本的私有Cache发送作废信号后对presence bit复位，共享Cache中的块状态变为M，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为M；块状态为U，从存储器中取出该块，目录将该块发送给请求的CPU，并将对应的presence bit置位，CPU的私有Cache将该块状态设为M；

8、存储同一性

定义：共享地址空间的存储同一性模型是在多个处理器对不同存储单元并发读写操作时，每个进程看到的这些操作被完成的序的一种约定

顺序同一性：不论指令流如何交叠执行，全局次序必须保持所有进程的程序次序

单个处理器存储器操作的序：

硬件执行load和store操作以程序序顺序执行

优点：在执行时机器的状态是确定的；程序的不同次运行机器状态是一致的，有利于程序调试

缺点：降低性能，增加复杂性，降低可扩放性

数据流处理器的存储器操作的序：

数据准备好就进行存储器操作

优点：并行度高

缺点：不同次程序运行的机器状态不一定一致，增加了调试的困难

多处理器的存储器操作的序：

顺序同一性：多个进程之间的存储器操作可以交叉，但是每个进程的存储器操作按照程序序

如果程序的一次执行产生的结果与前面定义的任意一种可能的总体序产生的结果一致，那么程序的这次执行就称为是顺序同一的

顺序同一性的充分条件：每个进程按照程序序发出粗存储器操作；发出写操作后，进程要等待写的完成才能发出它的下一个操作；发出读操作后，进程不仅要等待读的完成，还要等待读的数据的写操作完成才能发出下一个操作

顺序同一性模型SC：R->W、R->R、W->R、W->W

TSO：放松W->R

PSO：放松W->W

RMO：全放松

存储器栅栏指令：

实现弱同一性或放松的存储器模型的处理器（允许针对不同地址的loads 和stores操作乱序）需要提供存储器栅栏指令来强制对某些存储器操作串行化

存储器栅栏是一种代价比较大的操作，仅仅在需要时，对存储器操作串行化

原子指令用来实现信号量的P(V)和S(V)操作