体系结构技术发展

流量强调的是在一定时间内完成的工作量，又称之为带宽；响应时间强调的是在一个请求提出之后得到回复的时间间隔，又称之为延迟。二者的核心内容是时间。

两个不同的计算机，X比Y快n倍，表示一个程序在X上的执行时间比在Y的执行时间快n倍。

墙钟时间，wall time不一定是单调递增的。因为wall-time是指现实中的实际时间，如果系统要与网络中某个节点时间同步、或者由系统管理员觉得这个wall-time与现实时间不一致，有可能任意的改变这个wall-time。
response time响应时间
elapsed time

benchmark用来评估计算机性能，有五种：真实程序、核心程序（应用内挖出来的典型应用）、简单程序（素数筛选等）、synthetic benchmark（组合程序）、benchmark suites（测试组件）。

最著名的测试组件：SPEC（system performance and evaluation cooperative），是一个benchmark suite，侧重于CPU内部的性能，是研究计算机的人员所侧重的，用来测试Unix工作站。

CPU performance：大部分计算机在一个特定时钟周期下工作，Clock time（CPU时钟）越高越快。

一个程序的CPU时间表示为占用的时钟周期乘以时钟周期数，或者占用的CPU时钟周期/CPU时钟工作频率，得到一共用了多少拍。

Instruction Count（IC）是指令数，与机器的指令系统和编译系统有关。
Cycles Per Instruction（CPI）用（CPU时钟周期数）除以指令数，是每条指令占用的节拍数，与硬件组织有关。IPC是二者倒过来。

所以，CPU时间 = IC * CPI * Clock cycle time，或者CPU time = IC * CPI / clock_rate。

3个基本原则：

大概率事件优先，让最常见的事执行的最快。
Amdahl定律，可以找到系统的瓶颈在什么地方，且系统的性能是由系统最差的部分决定，一个系统是均衡优化的系统。
程序局部性原理，时间局部性（将来用的东西最大概率是我现在用的）、空间局部性（这次访问的下次可能再访问，出现内存中的热点部分）。

指令系统和基本流水线

计算机指令系统：

所有机器的指令系统相似，但都不一样；
桌面计算、服务器和嵌入式系统的指令系统有差别
- 桌面系统要求同时有整数和浮点数，对容量的消耗不敏感
- 服务器中，浮点数运算不如整数运算和字符串处理重要
- 嵌入式系统对容量和大小更敏感

指令集分类是根据CPU访问存储器的方式分类的

堆栈型，少见，最大的好处是程序员事先组织好数据，之后不需要管；
累加器型，部件少；
寄存器型，有寄存器-存储器、寄存器-寄存器型
存储器型。

指令的四个方面：

存储器地址
操作类型
操作数类型
指令编码

访问内存时，首先要告诉，访问哪个地址，访问地址有多长。注意字节对准，对一个地址的访问需要成块成块的访问。

大端小端：如果数据超过一个字节，则数据的第一个字节放在哪个位置？第一个字节放的是高八位，则是大端。

寻址模式：可以减少指令数，但是增加了复杂性。越丰富的寻址方式给程序设计人员带来更大的便利，过于复杂的寻址方式降低了利用率。

现在所使用的数据有8位的、16位的、32位的、64位的。

常用的指令系统：

逻辑运算指令，ADD，AND，OR
数据传输，LOADS、STORES
控制类指令，指令执行方向的改变所需的指令，jump、call、trap
系统类指令，实模式切换到保护模式等一些系统调用；进程切换时需要cache的清空指令
浮点类指令
字符串类指令
图形类指令，即数字图像处理类指令。MX、MXR等

指令功能设计中，有一类指令是改变控制流的：

条件分支，有条件转移
跳转，无条件转移
子程序调用
子程序返回

这一类指令会影响到系统的性能，导致机器在运行中频繁执行切换，可以：

直接形成条件码，设置特殊标志位
条件特别多，做一个条件寄存器
比较完直接拿结果

操作数问题：最常见的操作数有如下几种:

字符型
整数型，半字、字。
浮点型，32位短浮点和64位长浮点，尽量使用64位的，因为浮点数的误差和累计误差很大
十进制数，不紧缩的可以看成串，紧缩的是按照BCD码调整的，直接进行运算，一个字节放两位十进制数

指令编码：经典的RISC机器都是固定四字节的指令长度，80x86指令长度从8位到48位，译码的时间过长，需要使常用的指令较短。

编译器大概有如下的过程：

前端的语言处理
高级优化，与机器关联，考虑如何优化
全局优化，考虑寄存器分配和全局变量的存储
代码生成，依据机器进行生成代码

一个地址会有很多中表示方法，这叫做“别名”，给编译优化带来了很大的问题。

MIPS实现：

MIPS整数部分的子集，还包括存取字，整数ALU，基本浮点功能部件
过程
- Instruction Fetch：取出指令放到指令寄存器中，生成下一条指令的地址，当前指令地址+4，
- Instruction Decode：译码，读取寄存器
- execution/effective address：处理地址。
  - 访存指令，ALU得到地址，将结果放到寄存器中
  - register-register运算类指令， ALU执行操作码指定的运算，将两个寄存器中的值进行运算
  - register-immediate运算类指令，
  - 分支指令，
- memory access：访存，访存阶段如果是运算类指令，则绕过访存直接进入寄存器，如果是分支类指令则有其他操作。
- write back：写回，结果写入寄存器中，不管是从memory sytem或者ALU中来的。目标寄存器在两个位置之一（rd或rt），取决于操作码
- 这是一个五拍的工作过程
流水线MIPS是再流水阶段增加流水线寄存器（锁存器），寄存器名字与它们连接的状态有关：
- IF/ID — ID/EX — EX/MEM — MEM/WB
- 共有四个。

提高并行化有三种出路：资源的大量使用、时间重叠、资源的共享。流水线以时间重叠实现并行。

流水线的操作步骤

取指令：
- 把存储器中的当前需要执行的指令，取出来放到IF/ID寄存器中
- 如果操作码是分支类指令，并且分支条件为true，把后边流水线计算的结果放到寄存器中，这个地方可能出现等待；否则就PC+4
译码段：
- 两个源操作数寄存器送到ID/EX
- 指令和下一个PC从IF/ID传到ID/EX
- 立即数进行扩展，因为立即数都是8/16位的，需要扩展后参加运算
执行段：
访存段：
- 对load/store指令，把锁存器的指令传过来
- 存储器的输出接过来
写回段：
- 写回到rd或者rt，因为其中一个是register-register指令，一个是register-immediate，所涉及的寄存器不同。

指令流出：指令从译码段进入执行段，并不是所有指令都可以流出，有的译码之后不能执行。

数据冒险：在一个指令执行的时候，所需要的数据（状态）对前边指令产生依赖关系，只有在流水线上才发生如此的依赖关系。

四种可能的组合
- read after write
- write after read
- write after write
- read after read(不是冒险)

空转（Stall）：机器并没有停但是没有干什么，出现冒险时控制器插入stall，避免某些指令的提前，可以通过比较流水线寄存器来检测冒险。

定向（旁路，bypass）：为了尽早获得数据，减少因为数据冒险而导致的空转，越早拿到数据，空转的周期越少。

流水线的分支会产生问题，已经有一组指令进来了，但是可能会进入另一个分支，在译码阶段就知道了，将需要进行计算的分支条件进行提前判断。

例外/异常（Exception）：

IO设备请求
调用操作系统服务，通过和异常类似的方法处理操作系统的使用
断点
整数上下溢出
浮点计算异常
缺页
寄存器访问未对准
使用了非法指令
硬件故障

有一些例外是同步的，有一些是异步的（网络请求，IO请求）；
可屏蔽的中断和不可屏蔽的中断；
指令间的和指令内部的；

机器能够在碰到例外后进入一种有序的状态，作为体系结构设计的时候，当发生例外并被处理之后，可以实现状态“可预测”，有很多种策略：

强迫指令流中止，但是如果流水线长且可以乱序执行时难以实现；
不允许产生例外的指令把结果放入寄存器；
例外处理程序将PC保存下来。

精确异常：明确地确定哪一条指令导致了例外，这种情况下称为精确的异常处理。机器内部导致的例外可以精确定位，外部请求导致的例外不用定位。例外和指令处理的各个步骤均相关：

IF：取指令时的缺页中断，内存访问的不对齐，存储器保护错误
ID：译出来的指令不知道是什么
EX：计算意外
MEM：页失效，不对准等

流水线中的多周期：有些指令耗时长，有些耗时短，如果指令执行时间差距不大倒还好，可以均切分。指令过长导致流水线出现：指令在执行中间出现机器调度不确定性；导致浮点部件在结构上出现冒险，搞不清楚指令到底执行完了没有，或者在等待结果的时候不知道能不能等到。

如果不能把所有部件设计成等长，则设计成不等长，在MIPS中，把执行段设计为4个部件：整数部件、浮点加、乘、除四个部件，其他不变。

流水线的延迟和执行下一条指令要等多久，这两个时间是流水线的重要属性。

流水线中结构不足所导致的风险，和流水线密度所导致的风险（每一拍所产生的结果与前后都有依赖，具有反馈性，需要保证旁路通道多）

指令结束的次序与指令输入的顺序不一定一样，先写后读的风险大得多。

动态调度和静态调度：静态调度又称为编译器调度，在程序执行之前对程序的指令进行排序；动态调度是开始执行发现执行顺序不好，则重新进行排序，通过硬件办法重新排序减少机器空转，优点是对于程序静态分析时看不出来的情况可以进行调度，编译器也可以简化，且硬件的事可以交给硬件自己去做，但是硬件成本大大增加，复杂性增加。

为实现动态调度，流水线必须具备以下功能：

允许按序取多条指令和发射多条指令——取指(IF)流水级允许按顺序取多条指令进入单口暂存器(single-entry latch)或队列(queue), 指令然后从latch或queue取出，进入ID节拍。
能检查并消除hazards——将ID流水级分为独立的两级：Issue级和Read operand级：
- Issue级功能——指令译码，检查是否存在结构冲突(即在这一流水级解决结构冲突问题)；
- Read operands级功能——等到无数据冲突(RAW)后，读出操作数，即在这一流水级解决数据冲突问题。

记分牌算法。需要足够资源和没有数据相关，记分牌是枢纽，所有的指令都要经过它留下执行的记录和依赖条件，如果记分牌决定指令不能立即执行，会将指令进行重排并决定何时可以执行。

记分牌是一集中控制部件，其功能是控制数据寄存器与处理部件之间的数据传送。在记分牌中保存有与各个处理部件相联系的寄存器中的数据装载情况。当一个处理部件所要求的数据都已就绪（装载完毕），记分牌允许处理部件开始执行。当执行完成后，处理部件通知记分牌释放相关资源。记分牌中记录了数据寄存器和多个处理部件状态的变化情况，通过它来检测和消除或减少数据相关性，加快程序执行速度。

如果在MIPS上做记分牌，要在指令的译码阶段检查结构和数据冒险。可以解决：写后读相关，解决乱序结束。把指令译码阶段分成两个部分，指令的结构冒险和数据冒险给它分开，所以要拆成两步。

第一步：指令流出，条件是它所使用的功能部件是空闲的且所要写的目标寄存器没有被别人写，检查了结构冒险和数据冒险中的写后写冒险，因为前边可能有超长的指令还没完成。
第二步：读操作数，指令流出之后，所要的数据还没来，这条指令读操作数就读不出来，就要等结果。
第三步：运算，直到运算完成。
第四步：写回，检查读后写冒险，等别人把数据读走之后再写。

记分牌并没有发挥定向通道的优势，必须读写分开。

总结一下：
动态调度技术需要将ID译码段分成两个阶段：1是发射，2是读取操作数。发射阶段对指令进行译码，检查结构冒险（例如有四个运算器：整数运算、加法器、乘法器、除法器，检查该指令需要使用的运算器是否正在被占用）读取操作数阶段检查数据冒险（读之前检查寄存器的值是否已经写回，或者是否会覆盖了之前的值）。数据冒险的解决方法（读写冒险(RAW)：将指令和操作数保存起来，然后只能在读操作数阶段进行读取；写写冒险(WAW)：检测是否有其它指令会写回到相同的寄存器（检测到冒险），有则等待，直到其它的完成）

发射阶段：假如检测到没有结构冒险和数据冒险，那么记分板将会将指令发射到相关的运算器，假如结构冒险或者写写冒险发生了，那么该指令将会等待，直到冒险消失为止。我要使用的功能部件忙标志位为否且指令所要写的状态是空。填写三个寄存器（目标寄存器，第一、二操作数寄存器，填写的是寄存器编号）

读取操作数：没有数据相关了以后（之前的指令不会写回源寄存器或者正在写寄存器的情况时，读写冒险），读取操作数。读取操作数后将交给运算器，之后开始运算。发送到运算器的顺序可能是乱序的。

之后就是执行段以及写回段了。没啥好说的。执行段在完成计算以后会通知记分板。记分板直到计算已经完成了，那么它进行读写冒险检验（即写之前是否已经读取了寄存器的值，例如 ADD F10,F0,F8 SUB F8,F8,F14，这里SUB指令写回时要检查ADD指令的F8是否已经读取了，仅此而已）假如检测到冒险，则等待，不然就可以写寄存器了。

记分牌的构成：

指令状态，
功能部件状态，很多个域
- Busy 标识该器件是否正被使用
- OP 该器件正在执行的运算例如 + - * / 等等
- FI 目标寄存器
- Fj，Fk：源操作寄存器
- Qj，Qk：如果这两个数据没有谁将生成这个数据（源操作寄存器正在被什么单元所处理），如果是NO的话说明已经拿到数据了或者数据尚未准备好
- Rj, Rk 表示Fj Fk是否准备好的标志位
寄存器状态，标识哪一个存储器将会被写回

这是一种以记分牌电路为核心的设计方法。

指令级并行（ILP）

指令之间有一种特征，可能会并行地执行而不影响结果，正是要挖掘这个特点使指令并行地执行。一种是动态办法（依赖硬件定位并行性），一种是静态办法（依赖软件）。

流水线CPI = 理想流水CPI + structural stalls + data hazard stalls + control stalls

先进的流水线：不区分动态静态和软硬件，所有的技术都与编译器结合。

ILP的概念：

基本块：一个没有分支的指令块
串行代码：只有少量的并行性。
操作系统代码的基本块较长

跨越多个基本块的指令级并行主要是在循环级探讨并行性，这是最常用的提高并行性的方法。需要将循环级并行转成指令级并行。最常用的方法是循环展开，可以通过编译器或者硬件实现。循环的每一次迭代执行可以与其他迭代重叠，需要确保循环中涉及的数据不会干扰。

向量处理器作为专用部件应用在图形处理器中。

数据相关和数据冒险：相关导致冒险，冒险导致空转，空转导致流水线效率下降。数据相关可能会产生冒险，尽可能减少机器的空转。

名相关：分为两条指令都写相同寄存器和读后写两种，读后写可以通过名字的改变消除。

区分数据相关和名相关：是否在指令之间发生了数据传输，数据相关发生了，名相关没发生。克服名相关可以寄存器重命名。

控制依赖的调度有两个基本原则：与分支指令控制相关的指令不能调度到分支指令之前去，与分支指令无关的指令不能调度到分支之后。

数据流前后的依赖关系需要数据依赖和控制依赖的协调，且数据流依赖设计链式依赖。

Tomasulo算法

核心思想：硬件的动态指针技术。动态解决RAW，允许指令乱序流出。

两点显著不同：冒险检测机制不像记分牌一样集中在电路上，而是分布在算法中的。不检查WAR和WAW，因为已经被算法消除了。

重要概念：保留站（一种虚拟功能部件）。就是一个缓冲，每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。里边保存了指令和操作数，以及等待执行的所有条件。

在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。

也发挥了寄存器重命名的功能，原来访问寄存器a，缓冲以后，不再访问寄存器a，而是去访问缓冲。

记录和检测指令间的相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；通过寄存器换名来消除WAR冲突和WAW冲突。

过程：

从指令队列的头部取一条指令。
- 如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r。
- 如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r。
- 一旦被记录的保留站完成计算，它将直接把数据送给保留站r。
- 如果没有空闲的保留站，指令就不能流出。
操作数来了之后运算。两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。
得到结果后放到共用区域（common data bus），共用区域链接所有可能需要数据的部件，cdb发出广播，所有需要这个结果的部件将同时拿到这个结果，这样可以大大减少连线量。在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。每个保留站都有一个标识字段，唯一地标识了该保留站。
拿到结果之后结果再消失，数据放到了公共区域，那么要写的目标寄存器也要到公共寄存器去拿，减少了仲裁机构调派部件拿数据的过程。
所有保留站有各种标志，用来进行各种数据状态的检查。

执行步骤：

首先把浮点指令送到指令队列
没有结构风险的时候就把指令流出
根据需要送到确定的运算部件或访存部件
load或store把指令送到访存的缓冲中去
如果访存操作数没有被取到，就把产生这个数的浮点功能部件的编号取过来，实现了寄存器到保留站的重命名过程，把寄存器重命名到保留站，消除了同名。
结果有效时，写到cdb中。

每个保留站有以下6个字段：

Op：要对源操作数进行的操作。
Qj，Qk：将产生源操作数的保留站号。
- 等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。
Vj，Vk：源操作数的值。
- 对于每一个操作数来说，V或Q字段只有一个有效。
- 对于load来说，Vk字段用于保存偏移量。
Busy：为“yes”表示本保留站或缓冲单元“忙”。
A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。
Qi：寄存器状态表。
- 每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。
- 为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪；非全0的时候时保留站的编号。

分支预测

当指令流出速度快时，流水线中的指令是多指令流出，如果遇到分支则会出现问题。前边讲过静态的分支预测，假设分支总是成功/不成功等条件，很好的帮助程序提高性能。动态分支预测使用硬件对程序进行预测，依赖于程序的动态特征和执行过程。在分支预测时，假设分支指令是成功或不成功。

分支预测的精确程度、预测正确和不正确的开销比较都会影响分支预测是否成功。最简单的分支预测方法是看上次的分支结果。

一种办法是BPB（Branch Prediction Buffer），记录分支历史的进入分支数，用于下一次分支特征的预测。记录一个分支指令成功或不成功，放入缓冲中，下一次指令再来的时候查这个缓冲，有多大程序就有多大缓冲，因为程序中哪个是分支不知道。通过指令地址进行记录的同等检索，下次再进入的时候再检查是成功还是不成功。BPB的buffer还是个小的寄存器，用指令的地址进行同等检索，所记录的是分支指令发生还是不发生。

绝大部分指令不是分支指令，如何把分支预测缓冲做的小，比如做到一半那么大。采用地址折半，上半截主存和下半截主存映射到同一块地址，并且实际预测正确率不降低。减到一半还嫌多，那就先做一个512个入口的缓冲，使用指令地址的低位来访问缓冲，效果也不错。这样就是取模了，可能会冲突，如果问题严重的话就加大分支预测缓冲，分支预测错了则将那一位反转。根据被预测指令是否成功画出状态转移图：

上图只有一位，比较浅薄。可以让历史更深一点，再加一个位，构成两位的分支预测。一个预测必须失败两次后才能改变。对4k的缓冲，最高命中率达到82-99%，这么高的命中是因为可能有的程序有很多循环。

浮点指令猜错的概率要比整数指令猜错的概率小，因为浮点计算主要面向科学计算，循环多，所以猜错概率小。

预测器的位数在2位和n位的时候差别不大，所以很多系统只使用2位的分支预测。做4k个入口和更多的入口效果差不多，所以只有4k个入口就够了。

相关分支预测，现在的分支预测是不是成功要根据上一个分支预测是不是成功，实际上是做两级，即做两个1位分支预测器，如果上一次预测成功则使用一个预测器，如果上一次预测不成功则使用另一个预测器，使得本条分支预测的结果基于上一次分支预测。

多指令流出：每个中期发出4-8条指令，必须要使得指令流得到更大的带宽，有三种方法：

分支目标缓冲（BTB），另外一种动态分支预测方法，在取指令阶段对btb进行搜索，如果不在表中就看是不是分支指令，而且是不是成功的分支指令，如果是，但是表中没有，则放进去，如果表中有了就直接拿出来执行；如果不在btb中且不是成功分支（不是分支或不是成功的分支），这种情况下IF没有困难，都是PC+1，。通过查表提前知道对应的pc值和next program counter，只要之前这个指令来过，就记下来分支地址和它的转移目标地址，下一个IF到来的时候就不需要取指令了。
集成化指令分派部件
预测返回地址

分支预测的一个变种：branch folder，不仅有PC和next PC，还把指令放到表中，直接在译码段就开始比对。

两种办法可以使得机器一拍流出一堆指令，使CPI小于1，超级标量处理器，一种是VLIW（very long instruction word）。超标量是标量集合，把彼此不太关联的一些指令组合起来，一次发出的是若干个指令，每拍流出的指令数是变化的。可以采用动静态方法实现超标量，机器不存在在执行中调整指令顺序的能力，编译器对指令顺序进行调配，调整了优化参数打开超标量之后可能会不对！

VLIW指的是一条超长指令字，经典的概念是不允许乱序流出的。它是一个拥有固定数量指令的指令包，有若干种特定类型的指令组成，机器一次发出的是一个指令包。

静态调度超标量：指令有序流出，所有的流水线冒险都必须在编译时预先检查，在流出时如果有冒险就不允许流出。编译器的工作量非常大。

现在使用的超标量是把指令打一个包，让他去执行，这个指令包一般会对指令有要求，指令流出时一拍内流出多条，指令总线做宽一点，大家排好队一起往前走，这样很简单，但是电路实现很复杂，指令要控制好先后顺序，不能出现无序流出。还可以把指令流出这一步切成流水线，把流水线本身的一站作为子流水线。

超标量机器指令取：取指令并用64位译码器译码。

从cache中取两条指令；
确定是没有指令、1条指令还是两条指令；
把它们送到正确的功能部件。

静态超标量不允许乱序流出，有一些特定的顺序不可乱。

指令流出的过程中，允许两个指令同时流出，有一个限制，浮点指令流出时需要一个整数指令寄存器，在进行整数和浮点调度时，不能分开调度，要统筹考虑。

现在所使用的超标量寄存器每个时钟4条以上，包括了上述两种方法。实际上对RISC机器流出4条多。像x86机器可能流出3条，但是这三条CISC指令可以拆出20多条指令。

超标量的时候有一些限制：

浮点功能部件不能被充分利用，需要更少的整数操作；
需要大量的指令级并行（相关性很小的部分）；
超标量时一个循环的判断分支带来了不能并行的阻碍。

控制的相关性引发的控制冒险可能会导致指令的“空槽”，超标零的性能被限制，需要前瞻执行，用来克服类似分支指令导致的麻烦。最好能够把分支指令当成普通指令直接扔进去执行。

基于硬件的前瞻和预测：允许指令提前流出执行。必须有动态分支预测，前瞻是一种保证，保证预测不会影响全局。加上动态调度。必须要有undo的功能，来处理前瞻执行不正确的情况，这样实质上是基于大量缓冲的功能。

基于硬件的前瞻性执行做了一个确认段，实行基于数据流的检查，只要数据流是正确的，就可以保证执行是正确的，因此要添加确认段，确认正确了再写进去。这里隐含了一点，指令可以乱序流出执行，但是确认是顺序的，这说明指令在通过指令流出部件的时候被打上了某种标记来标志它的顺序。所有的结果包括例外都要得到确认。

机器基于硬件实现前瞻，采用复杂电路解决的是分支问题（控制相关问题），指令级并行开发的深的话，如果不能提供足够的并行度，则造成浪费。硬件的前瞻执行是分支指令的预测过程，很多指令通过这种办法在控制相关未解决的情况下执行了。确认执行错了之后，可以回退，撤销之前的执行。

执行乱序、确认有序是一个排队等待的过程，要有一种排队机制来支持确认，它实际上是一个缓冲过程，这个排队过程称为ROB（再定序缓冲，Reorder Buffer），保存对机器执行有影响的状态。保存已经执行完但是没有提交的指令的结果，提供额外的寄存器作为保留站。

三个重要的ROB域：

操作域，用来保存指令，例如分支指令、load/store指令、寄存器操作指令；
目标域，记录目标寄存器，可能是寄存器也可能是存储器的地址，这个结果要被写到哪里；
值域，在确认的时候保存结果，直到指令真正被执行。

工作流程：

指令流出
- 如果有保留站且再定序缓冲有空，指令流出，一条指令流出至少要占用两个资源。如果指令所需数据在寄存器中或再定序缓冲中存在，则取出来送到保留站。
- 指令流出的时候先做一些分类，之后做译码，决定做什么操作，扔到运算部件去。
- 进行标志状态的修改
指令执行
- 如果有操作数未准备好，就监视CDB（common data bus），这个过程检查数据相关；
- 指令可能会等很多拍
写结果
确认过程

一个store指令的确认：前提是被确认的指令到了再定序缓冲的顶部，要把结果寄存器更新掉，把它从ROB种清除掉。

一个不正确的分支预测表明前瞻执行是错误的，刷新ROB，重新从正确的分支开始执行，一个正确的分支预测则使得这个分支与正常的指令类似。

浮点程序中的分支是有极强的规律性的，整数程序中的分支不明显。

基于存储器地址的前瞻性执行：减少对于顺序地址计算的限制，使用硬件预测依赖。

堆栈、寄存器的使用对ILP的效率影响。
别名分析：对程序执行的并行性有影响。

只有发现依赖之后才前瞻，首先找到相关性，相关性基础上处理器进入前瞻状态。

数据值预测/地址值预测：很难，是一种很精确的前瞻方法，不允许有误差，。如果能进行完美的值预测，则不需要编程啦。

线程级并行：可以以线程的方式组织程序运行，一个线程是一个独立拥有数据和指令的实体。可以根据需要派生线程。多个线程并发执行有一个重要概念：同时多线程（SMT），既能同时执行，也要同步。

编译调度

使用编译技术提高流水线性能，减少因为数据冒险导致的阻塞和分支预测。

假定使用5站流水线，已经完全流水，如果没有相关性则会顺畅地流下去，没有任何阻塞；如果有分支指令则在分支指令及其前一个指令之间有1拍延迟，整数部件load有1拍延迟，整数部件无延迟。

如果是分支指令，取指令1拍，指令译码1拍，产生结果得到分支目标1拍，这个结果不经过任何过程再返回。如果采用锁定机制（发现是分支指令就不取下下一条指令了），这时已经到指令译码了，刚好已经取进来一条了，这就叫做分支延迟槽，再往后的指令先停下，跟进来的这条指令就允许向下流，或者更彻底，只要发现了是分支指令，跟着进来的那个也不管了，这会导致两拍的开销。

循环展开、指令调度、寄存器重命名。

确定指令的调整是否是有效的，移动的指令不影响执行结果；
确定循环和循环之间不存在相关性；
使用不同寄存器避免在使用相同寄存器时的不必要约束；
在循环展开时注意处理结尾的迭代；
明确load和store在循环展开时是否可以交换，不同迭代的load/store相互独立，分析内存地址明确是否是同一地址
如果存在相关性，必须确定和原始代码的相关性一致。

通过使用寄存器重命名，在两次迭代之间减少相关性，而不影响一个迭代内部的相关性，也有代价，比如多用几个寄存器，或者代码体积会增大，编译器更复杂。

有的情况下编译时就能预测分支是否成功，它的成功率分布很离散，从9%到59%。改成基于方向的，如果程序到了分支，如果程序往前走（可能是if），认为不成功的概率居多，如果往回走（循环），成功的概率居多，猜错率在30%-40%。

改一下，使用程序的上下文信息，每次预测的时候使用上一次预测的结果，可能会生成更精确的预测；再进一步地，基于统计信息，先得到一些统计信息，基于统计预测分支的走向，这种方法的指导性很不强。

超长指令字机器，首先要确定机器的最大并行度，全靠软件做，先把指令打包，确定封装包之间的相关性，在所有的指令中间，确定一条指令跟正在被处理的所有指令是否相关。

静态超标量通过编译器调度来帮助处理器达到更高的性能，动态超标量不需要编译器调度，但是需要硬件的开销。

超长指令字是对编译器及其依赖的一种技术，最小化潜在的数据冒险延迟，将一些指令封装进一个流出包中，也不需要检查潜在的相关性，执行中认为去拿的数据一定是对的，如果没有一定的保障，则可能会拿不对的数据，需要编译器进行控制，编译器需要控制指令包内、包之间的相关性，好处就是硬件会很简单，不需要考虑前瞻和相关性，仍然能达到很高的性能，VLIW使用多个独立的功能部件，把一组指令按某种方式组合，构成一个长指令字向外发送。

每一个VLIW功能部件需要16-24个二进制位来表述功能部件完成的工作和寄存器。可能包含七个部件：2个整型部件，2个浮点部件，2个内存，1个分支部件。一个长指令字里出去的指令应该都是无关的，部件之间不存在数据交换通道。

早期超长指令字格式非常死板，这个地方是一个整数就是一个整数，指令部件就是一条一条往运行部件送，代码二进制不兼容，必须要依靠硬件和软件的适配。所以很难见到超长指令字机器。如果打包的时候没有要求的操作往里填，则填空指令，指令槽的利用率可能会比较低。

VLIW问题：

代码数量增加了；
每个指令之间是互锁的，在执行的时候如果一个指令被卡住，后边都会被卡住；
二进制代码不兼容，如果有部件的增删，则要重新编译代码。
VLIW对循环展开的次数要求很高，可能不够展开的；
对功能部件利用率比较低，需要插入很多的空指令。

VLIW有压缩的余地：把立即数提出来生成一个立即数域；程序在执行之前可以压缩，从存储器中取出来的时候再解压缩。

互锁机制：所有功能部件操作是同步的，不用判断数据相关，编译器解决，硬件就不用解决了，有一条指令阻塞了，其他的都会被堵住。如果在访存的时候碰到了，访存时间可能很长，指令之间的互锁机制会使性能不可忍受。很多机器在处理时将一些部件从互锁机制解开了，编译器也会解决互锁。对指令流出之后，可以不同步执行。

二进制代码的兼容性跟指令集、流水线结构、功能部件的结构/数量相关，这是超标量机器占主导的主要原因。

代码迁移过程：实用的是对代码进行调整和转换，例如在执行的时候把串行转换成VLIW。

指令的多流出和向量处理器：成本是相当的，向量处理器性能高些；多指令流出对代码要求比较低，不需要向量化，且多存储器的带宽要求比较低。向量往往作为处理器的加速部件。

开发ILP的高级编译技术

通过一部分硬件的支持（前瞻），通过软件技术的方法（编译）提高并行性。

循环级并行：检测和减少迭代之间的依赖，找到并行性。
软件流水线：一种循环展开的过程，解决面向不同应用的问题，不用根据体系结构进行优化。
路径调度：控制指令相关的调度策略，将执行过程看成一个路径。

检测相关性：

进行代码调度
检测循环是否有并行性，检测在执行中时间上的概念
减少名相关

一旦涉及到循环，数组和指针是最头疼的，一个有效工作的循环一般都有数组和指针，也就存在别名（alias）问题，这往往因为数组或向量下标引起的。也需要去找是否存在环状的相关性。

相关发生在两遍循环之间的问题经常存在，一次迭代使用了上一次迭代的结果。只要不存在这种相关性，即使存在其他的相关性，也可以同时流出。

如果一个for循环存在两边循环之间的相关，需要破坏掉相关才能实现并行性，如果没有相关环的话就可以破坏，如果能把上一遍循环的计算拉到这一次循环中计算，这样就能不依赖于另外一次循环。对于两次相关的爹地啊，相关的语句放到一起，不相关的语句拆开放到两次迭代中。语句之间影响并行的因素就清除掉了，但是循环之间必须保存的有序性也要保存。

相关性的检测：可以获得的并行性收到循环次数的限制，循环展开的次数越多越好，有的循环没有那么多次可以供你展开，循环展开也需要更多的硬件资源。需要知道循环不同遍之间是不是访问的相同的地址？更复杂的分析需要知道两次访存是不是请求的相同的（多个）地址。

递归：存在某种相关性，关联很确定，存在比较多的并行性。

两边循环出现循环相关的距离即为相关元素的间隔。相关距离越大，相关的冒险越小，导致机器阻塞的概率也越小，通过循环展开获得的潜在并行性也越大。如果相关距离是5，那可以循环展开得到4个副本，循环距离变为1，如果把循环距离为1的循环展开的话，循环距离不会改变。

如果展开的话可能会增加一些相关性，因为要把一些计算提前，越是循环次数远的，相关性就越长，这样就给并行以机会。

编译器检测相关性：水平极其有限，假设下标函数构成仿射函数，就是一个线性函数，被写成a ( x * i + b)的形式，a和b是常数。

检测循环中是否有相关性，即检测可能数据相关的两个语句所代表的两个仿射函数是否有整数解，如果有，则可能相关。

从理论上说，编译时不能确定认为变量相关，可能会存在一组整数解，但是可能取不到这一组解，可能与加载的运行负载有关。相关检测可能会成本很高，基本就是程序执行的一个过程，每一次迭代之间都可能存在这个问题。

GCD Test：如果不是存在整数解，而在两个仿射函数a ( x * i + b)和c ( x * i + d)中，GCD(c, a)能被(d-b)整除，则可能存在相关性。

编译器如何工作：在检测相关性时进行分类，识别名相关并通过重命名或副本技术消除掉，在分析时主要分析真相关（先写后读相关）、输出相关（写后写相关）、反相关（先读后写相关），其他的都是伪相关。

for (i = 1; i <= 100; i++) {
	Y[i] = X[i] / c;  /* S1 */
	X[i] = X[i] + c;  /* S2 */
	Z[i] = Y[i] + c;  /* S3 */
	Y[i] = c - Y[i];  /* S4 */
}

Y[i]存在很多相关，写后读、写后写等，S1 S3与S4中的Y[i]存在相关，可以消除，S1中的Y[i]使用中间变量替代；X[i]存在读后写相关，S2中的左边X[i]是最终结果了，不能用临时变量替换，要生成一个临时数组。

for (i = 1; i <= 100; i++) {
	T[i] = X[i] / c;  /* S1 */
	X1[i] = X[i] + c;  /* S2 */
	Z[i] = T[i] + c;  /* S3 */
	Y[i] = c - T[i];  /* S4 */
}

现在的结果是都用了数组，其实对Y的处理可以使用临时变量。编译器可以把替换Y的临时变量使用寄存器搞。

编译器可以：做指令的相关性分析，确定访存地址和循环展开的成本；对循环级并行，是不是循环有利于并行；访存是不是存在相关。

软件流水和路径调度

对硬件需求少。
软件流水是一种展开技术，相关性更少一些，得到更大的并行性。是一种对循环的重组技术，从每一遍循环里面提取公用的指令，构成新的循环，这个循环过程中间，从循环体来看，看不到一遍一遍的循环展开，但是从执行上看是在一遍一遍循环执行。

循环的每次迭代是一个指令序列，按照每个循环指令序列平行展开，认为一次循环内的相关指令的相关距离小于两次循环之间的相关指令的相关距离。

竖着的四条指令更可能相关，横着的四条指令相关指令距离更大，相关距离越大则相关冒险更小，所以可以横着实现并行且指令的顺序跟竖着是一样的。对循环重组，横向取指令，总的想法是把原本竖着的循环翻转过来。构成了一个像新的循环像流水线一样的相关距离更大的循环。

把“load、add、store”三条指令展开，开始三句是补偿代码，称为填充期，最后三句称为排空期。循环指令越多，排空期和填充期的指令也就越多。一边循环的指令的长度决定了补偿代码的长度，第一遍循环的最后一条指令作为软件循环的第一条指令，所以第一遍循环的前边所有指令作为补偿代码，类似的，后边作为排空代码。都有一个问题是偏移量的计算都必须要单独计算。

两条指令之间由于一条指令延迟过长，耽误了下一条指令的计算，就可以用常规循环展开进行展开。

软件流水的代码空间比循环展开小一些，没有大量的展开。循环展开有效的减少控制变量造成的损耗，软件流水降低空转、阻塞。

循环展开减少了循环控制变量的修正，如果是多层嵌套的循环，会乘上上一层循环的循环次数，更优化。软件流水主要减少每次循环引发的阻塞，在机器以峰值计算的时候更有效，腾出更多的空间使两条指令的相关距离更大。

基本代码调度：基本块本身是没有分支的程序块，超越基本块研究指令集并行。全局代码调度是跨越分支指令的调度，在循环体内部存在分支指令，调动循环体内部的控制流，从非循环的指令之间也存在并行性，对内部非循环控制流的代码比控制指令调度更复杂。

关键路径：全局代码调度的目的是把代码压缩，压缩到最短的指令序列，不包含分支指令的序列，形成的代码就叫关键路径，这段代码的所有指令会以最大概率从头到尾顺一遍，最可能没有分支指令。

代码的调度：数据的生产消费关系流（写后读）不能改变，代码的例外特征不能改变。在全局指令调度的时候，尽量减少可能产生例外的指令的调度。

全局代码调度实际上需要权衡，是否将一个语句调度到前方，需要进一步分析变量的依赖，这种调度可能会好，可能会坏。

路径调度产生一段可以并行执行的代码，针对分支，首先把程序中的分支抽离，剩下的是路径，这样找到了一个主干，认为主干有并行性，真正执行效果跟程序有关。路径调度比循环展开更进一步，发现跨越分支指令的并行性。路径调度的主要原因是每一拍都要流出大量的指令。

第一步是路径选择，选到一条路分为两步，路径选择大概有一条指令序列可以产生最短指令代码序列完成功能，经过选择的这一段代码就是路径，如果把循环连着控制指令一起展开，如果不成功就出去，呐循环展开本身就是一个关机按路径，产生一个代码序列，如果把控制变量去掉，则变成代码块；第二步是路径压缩，进行代码调整等一系列的修正，得到一串代码，就是可以执行的代码，之后压缩完的代码可以组合成超长指令字的指令包，它是一个全局的代码调度过程，在产生关键路径的中间，保证相关性不被破坏。

路径调度比简单的流水线调度获得更高的并发性，在控制相关上有特点；通过代码的调度跨越非循环的分支指令来预测程序的分支特征。如果对分支指令的信息足够精确，就能够得到非常快的代码。

路径选择第一步需要选择可能正确的路径，认为为真的概率比较高。代码不管经过什么调整，保证结果正确。

路径压缩需要挑出一个指令序列，填满机器所需要的指令。做分支指令调度的时候，有分支指令做好代码补偿，在路径的出入口做好。其中一个关键假设是关键路径执行概率最高，否则做代码补偿就得不偿失。

代码的移动可能导致控制相关的局部特征发生变化，导致某些指令的控制相关性发生变化。

软件ILP策略：

循环展开
软件流水
路径调度

编译器完成指令级并行的实现所需要的硬件支持，把精力集中到分支指令上。软件需要更多了解分支指令的特征，分支指令的特征并不好预测，它的执行是动态的，硬件可以提供一定的支持，例如前瞻性的执行，特别是对指令出故障的时候，对故障断定很精确，也提供一种机制，需要软件来执行这种机制，入条件指令，把if语句转成单条的指令，可以消除相关，把控制相关转成数据相关，在分支指令出现的代码段中也不出现调度问题了，只是数据操作问题，也没有相关问题。最后一种支持是前瞻的，一种是静态的在编译时就处理，设置抑制标志，不让前瞻性的过程扩散，如果扩散了则挂起，或者硬件提供寄存器，软件使用寄存器；动态调度是前边讲的算法。

条件指令是使用编译克服分支相关的一种方法，任何一条指令都带一个条件，如果条件是真的话就执行，是假的话就是一个空操作。这个过程内含了一个控制分支，完成后边数据的操作与前边相关，不再存在控制相关，而是转变成数据相关。第二个是把程序条件处理变成后端。

条件分支指令不允许产生意外，仍然占用运行时间，控制变量必须要预先产生，只有一个条件，只能做很简单的操作，最后是导致机器总体性能受影响。大部分机器支持条件传送指令。

指令作废：程序在执行时，条件应该尽早产生，以避免数据冒险等问题，否则应该作废。

条件指令的限制：

作废的指令依然占用资源
指令的控制变量应该尽早产生
只能对简单的指令采用条件指令
产生性能阻碍

前瞻操作的三种功能：

数据流正确性
例外正确处理
访存的冲突应该被正确识别

执行前瞻的四种方法：

硬件和OS对指令前瞻执行，对某些应用很难实现，需要OS作标志
前瞻指令不允许产生意外，需要编译器在编译时确认哪条指令是前瞻指令
一定范围的指令，如果是前瞻的话，打上指令，抑制影响范围
后援机制，在执行的时候，把结果放到后援存储中，数据也不最终写回，直到前瞻被确认。

指令进行全局调度的时候，例外和相关性不能改变，如果前瞻出现错误且对机器状态产生影响了，那这个前瞻就不能被采纳。

例外大概两种，一种是终止性的，程序不能被继续执行，如访存的保护错误；一种是可恢复的，当例外发生后，机器的机制对其处理，处理完之后可以正常执行，比如缺页。

软硬件联合前瞻，由操作系统和硬件可以处理可恢复的故障。如果前瞻的指令导致了一次终止性的故障，那就返回一个没有定义的值，当OS因为前瞻的故障发现返回一个无意义的值，则认为这是一个不可恢复的故障，进行一系列处理。如果引起终止的指令不是前瞻的，且引起了终止性的意外，那就终止。

既然是前瞻的过程，那最后的时候被前瞻的指令可能会系统忽视掉，它引发的终止性意外也可能被忽视掉。正常情况下一个程序返回一个无定义的值，则会崩掉；但是前瞻执行的时候会加上一个标志，增加确认过程，不会遇到例外就终止。或者加上一个前缀，当加上前缀之后，说明这条指令是前瞻的。或者所有寄存器加上抑制标志，每一条指令都有一条附加标志，告诉系统是不是前瞻的，如果是前瞻的，当碰到例外的时候，这个例外并不是马上就处理，先放一会，一直放到前瞻指令被确认的时候再处理。

这个例外在执行的时候可能会影响到一大批寄存器，也可能带来例外，但是这里的例外只能在指令被确认的时候再处理，所以记录下已经影响到的寄存器，如果一个前瞻指令使用了抑制位被置为抑制的寄存器，即某个操作数被抑制，那这个指令的另一个操作数也会被抑制，这是抑制的传递关系。如果正常指令访问被抑制的寄存器，机器就出故障了。

抑制位带来问题：操作系统需要单独指令控制抑制位。

后援问题：在分支指令之间调整指令，把这条指令定义为前瞻，提供一个reorder buffer，指令执行结束之后进行确认，把结果送到寄存器中。

设置专用check指令，用它顶替要进行前瞻执行的load，这个load就可以到处挪，这个check和load是一对，check检查保存在手里的load的地址和之前的地址，看前边是不是有写后读地址。

多处理器和线程级并行

并行体系结构的分类：

single instruction stream, single data stream(SISD)
single instruction stream, multiple data stream(SIMD)
multiple instruction stream, single data stream(MISD)
multiple instruction stream, multiple data stream(MIMD)

多指令流多数据流处理机采用的通用的芯片，提供了一种灵活性，通过软件和硬件的支持，对操作者来讲等价于一个单用户的多处理机，通过多个芯片提供很高的加速比，由于有多个处理器，对n个处理器来说至少有n个线程才能发挥处理能力。

依据互联策略，现有的MIMD有两类，一个是集中共享存储器体系结构，对于处理器和存储器，采用共享特征，多个处理器采用共享的存储器，总线把处理器和存储器联系在一起。由于多个处理器共享存储器，在时间和优先权上是一样的，因此总线采用仲裁机制判断哪个处理器使用了存储器，表现出一种对称。通过对称的策略，把这种机器叫做对称多处理机（SMP），实现了均匀访问，又可以叫做UMA。

把多个存储器分布到节点上，多个节点互联形成机器，带来的系统规模和可扩展性比较好，每个处理器访问存储器的时候大部分时候访问节点上局部的存储器，只有有必要的时候才访问远程存储器，远程访问经过互联网络，有较大时延，每个节点都有处理器、存储器、IO、互连网络接口，形成一个大的存储空间。两个好处：扩大带宽规模，局部存储器的访问是整个系统的大部分，远程访问量小得多，充分利用节点上的带宽，延迟小。缺陷是处理器之间的通信通过互联网络完成，变得比较复杂且有比较大的延迟。

多个处理器之间通信的话，一个是共享地址空间进行通信，多个处理器访问同一个地址单元，假如物理存储器是分布的，则叫做distributed shared memory（DSM），也叫做NUMA，对存储器访问不一样。

对共享地址空间来说，地址空间是共享的，一个空间只有一个地址单元，访问所采用的指令就是直接操作。对于多个地址空间来说，一个逻辑地址可能指的是多个地址空间，实际上是信息传递的多处理器，通过显式的数据传输完成。

对信息传递来说，通过同步方式实现，首先要传送一个请求，才得到一个应答。从另外一种角度，先把数据写过去再发送通知，当处理器之间的通信比较清楚的时候这种方式更简洁，这是异步的方式，提高运行效率。

通讯结构的性能问题：三个影响性能的主要因素：

通信带宽，有处理器、内存和互联机构影响
通信延迟，包括发送开销（数据送上通信的端口）、飞行时间（第一个二进制位从发送端口到接收端口的时间）、传送时间（所有数据除以速率）、接收开销。
通信延迟隐藏，假如是一个串行程序改成并行，在通信延迟期间做其他的事情，把通信延迟隐藏掉，这个隐藏过程是一个重叠过程，把通信延迟的影响降到最低。

算法决定了各个处理器之间的通信量，通常计算和通信之比随着处理器数量增加逐渐降低，处理器数量增加了，通信代价大了。处理的数据增大的时候，计算量增大，通信量也增大，二者之比增大。

小规模时，集中共享存储器是最简单的；围绕处理共享数据解决同步问题。

通过多级cache解决提高整体性能，私有数据一定要进cache，共享数据涉及多个处理器共享，在多个cache都有拷贝，需要解决cache相关性问题，着重从多个备份之间的关系。

如果系统是相关的，必须可以读出最近写入的正确数据，两个方面，相关性（能够读出来哪个值，指的是内容的问题，正确的还是错误的？）和一致性（什么时候能把写进去的值读出来，时间上的问题）。

满足以下条件一个存储系统才是相关的：

一个处理器P对x进行写之后进行读，其他处理器不对x进行写操作，这时返回的数据是P写进去的。
一个处理器对x进行读是在另一个处理器对x进行写之后，两次操作相隔时间很长且没有其他处理器对x进行写操作，读出来的值是另一个处理器写进去的值。
对同一个单元的写必须是串行化的，同一单元被两个不同的处理器执行的两个
写被所有处理器看上去都是相同的顺序。

相关性（coherence）定义了对同一单元的读和写问题，指内容上的问题，一致性（consistency）定义了读和写相对于其他存储单元的访问的行为问题，指时间上的问题。

读可以是乱序，但是写必须是按照程序规定顺序的。

相关性cache提供了迁移功能，是指数据项能够从远程移动到局部的cache中使用，为了减低延迟和带宽需求。复制指的是把当前的数据拷贝同时在多个cache中存在，也能从降低延迟方面获得好处。

cache相关性协议的关键问题是跟踪任何共享数据的状态，根据状态采取策略，有两类协议。首先是基于目录的方法，专门有一个物理存储器用于保留共享数据状态，查阅目录存储器就能找到共享数据的状态，适合分布式共享存储器结构。snooping（监听）使cache块中既存在数据，又包含了状态，状态是分布式存放的。

通过两种方式完成跟踪，维护相关性，为了保证处理器在对数据进行写之前，进入“专有”状态，把除了我要写的拷贝之外的所有其他拷贝都作废，称为“写作废”，当前要写的处理器对当前要写的数据进行专有访问。由于这是最简单的方法，广泛使用。可以用于监听或目录策略。专有状态保证没有其他的处理器可以读写，所有其他的cache拷贝都作废。通过仲裁把多个要写的请求进行仲裁，把其他的拷贝进行作废，其他的处理器重新读入一个拷贝，基于新写入的数据再写。强制所有的写操作串行化。

写广播（写更新）方式：当新的数据项写入一个拷贝的时候，要更新所有其他的拷贝，这里需要把所有的拷贝都更新。

对于同一个字的多次写，写广播代价大，每次写都要广播，对写作废来说只需要一次广播，这时已经进入独占状态，再次写的话不需要广播了。对于cache块中间的每一个字的写，在写更新协议中多次广播，在写作废中只有第一次需要写。不管是对一个字的多次写还是对多个字的写，写作废都只需要一次广播。

读和写一个数值之间，一个处理器写进入，另一个处理器要看到的话，写广播的延迟比较短，写作废需要重新调入数据块，更慢。

写广播占用带宽多，写作废的带宽需求比较小。

为了完成写作废，首先完成总线的访问，并且把共享数据地址送上总线，让其他的拷贝作废掉，其他处理机监听总线，检测到这个地址在其他处理机的cache内存在，则作废掉。对总线的访问串行化导致了对写的串行化。对共享数据的写要等到获得总线访问权之后。

对于写直达cache，写进数据之后存储器也要生效，如果其他的处理机获得最新值比较容易，从存储器里边取到最新值送到需要的处理器上。

写回cache，大部分最新的数据保存在cache中，存储器和cache不一样。监听总线上的地址，处理器发现总线上的地址和内部的一个cache一致，就把已经修改的数据提供给需要的存储器，因为现在数据已经被修改了，这里的是最新的。

通常的cache块都有自己的tag，标志当前的共享数据状态。有个无效位，说明是不是有效的。增加一个额外的共享状态位表示这个块是否是共享的，增加一个脏位看是否被修改过。

当只有一个拷贝时，这个处理器就是这个cache块的拥有者。cache地址和总线地址需要对比，地址的对比是串行的，cache只能满足一个的请求，所以监听控制器的操作会影响访问速度，如何提高对比速度，分成两份，一份由CPU对比，一份由总线对比；或者多级cache，CPU访问一级cache，总线访问其他cache，CPU和总线互不干扰，提高效率。

如果CPU操作了一级cache，总线可以操作其他cache。基于总线的相关性协议通过有限状态控制器实现的，控制器分布在每一个节点上，相应来自处理器和总线的不同请求，对两边的不同操作进行处理，并比较地址。对写命中和写失效都要出现总线事务，合并起来共同看作写失效的状态，减少要处理的事务。

最重要的是事务的处理是原子性的，操作必须是一气呵成不能中断的，全部过程不能有其他的插入。非原子性的事务可能会引入死锁风险。只要保证原子性的逻辑性，中间可以插入其他操作，只要不改变数据值，特别是写操作。为了充分利用并行性，且保证原子性，执行一些状态转移操作。

把状态变迁用状态转移图表示出来。

处理机之间的通信引起的失效叫相关性失效，可以分成两个部分，真共享失效、假共享失效，区别在于对同一块中间同一个字/不同一个字的共享，因为cache的共享是基于块的。

失效可分为三种：

强制性失效：第一次读入这个块的时候一定会失效
相关性失效：对相关数据处理引起的失效
容量失效：cache容量不足导致替换引起的失效

cache增大失效率降低，块大的话失效率也降低。

在监听协议里，每一个cache的状态分布到每一个cache块中，这种情况对分布可变规模的存储器有影响，因为分布可变的存储器使用互连网络，再使用监听协议就不适合了。一种可能的替代方法是目录存储器，把所有存储器共享的状态存下来。

现有的目录协议将每个块设置一个目录项，目录项的数量是存储块和存储器数量的乘积。为了防止目录成为整个系统的瓶颈，把目录存储器分布到系统中间，每个节点增加一个目录存储器。

目录协议两种必须实现的操作：处理读失效，处理对于共享的干净的cache的写，处理对共享块的写失效是上述二者的结合。目录要跟踪cache块的状态。首先在共享状态下，一个或多个处理器都有拷贝，未缓冲状态没有处理器有这个cache块的拷贝，专有状态是只有一个处理器有这个cache块的拷贝，如果这时候写的话，存储器的拷贝就是旧的，写完之后处理器是这个块的拥有者。

考虑到要写，分布共享存储器结构中，更需要写作废的支持，因为通过互联网络进行广播的话代价更大。共享状态最简单的支持是位向量，当块被共享的时候，每一位都标志出这个处理机是否有这个块的拷贝。

使用互连网络无法使用仲裁功能，仲裁是总线特有的；互连网络是面向信息传递的，总线是面向事务的，因此互连网络必须采用发送确认的方法。

局部节点是请求产生的节点。home节点是请求的存储单元和目录项所在的节点。远程节点是有cache块拷贝的节点。物理地址空间是竞态分布的，存储器地址清楚的话，节点号也清楚了。例如，地址高位代表节点号，低位代表位移。

目录协议的实现：目录存储器中，cache状态是反应数据状态的真实状态的，为了解决相关性，存储器中每个数据项变化时都引起目录项的变化，所以分布共享存储器中目录的操作占了总操作数的一半。送到目录中的信息导致2个操作，首先是更新目录的状态，由共享进入专有等；然后发送相应的信息，以满足请求。存储块可能是未缓冲的，可能是有多个缓冲的，或者专有的。三个状态下，目录所执行的操作不同。

未缓冲时，即在数据块还在存储器中时，读失效的时候，请求的处理器要求存储器将数据送到处理器cache中，置为唯一共享节点，块置为共享状态。当写失效时，首先要送给请求方处理器这个数据块的值，把它在共享集合上置1，变成共享状态。

处于共享状态时：读失效时，请求处理器从存储器中收到数据，请求的处理器被添加到共享集合中，写失效时，请求的处理器要进行写，首先拿到数据，所有在共享集合中的处理器收到失效信息，只留下请求的这个处理器，共享集合仅包含请求的处理器。

在专有状态下，所有处理器中只有一个拷贝。读失效意味着这个数据块将进入共享状态，发送取数据信息到拥有这个块的处理器，导致了块的状态变成共享状态，拥有者把数据发送到存储器，在从存储器把数据发送到请求的处理器，把标识进行更新。数据写回执行把cache中的脏数据写回到存储器中，拥有者把块送回地址所在的节点，这个块成了未缓冲的。写失效意味着专有的写状态要转移到另一个处理器，这个块将有一个新的拥有者，首先要发送信息到老的拥有者，使得cache作废，然后把原来的数值送回到目录，在把数据送回到请求方，请求方拿到了数据，成为新的拥有者。

当块处在专有状态时，读写失效时，先把数据送回到目录，从目录再存储再送到请求的节点。为了提高效率，把数据直接送到请求节点，再送到存储器节点，这个操作可以把间接的变成直接的，但是在实现中增加了复杂性，同时使得死锁可能性增加了，在送给使用方的同时送给存储器。

基于目录的方法用空间换时间，减少了访问量但是增加了目录存储器，大小与系统规模N的平方成正比，为了改进，提出了有限映射和链式结构两种。

有限映射假定在不同cache中的拷贝数量小于一个常数，可以通过比较少的位向量标识块，但是有m个的限制。
链表结构不存在有限映射中m的限制。

数据分布引起整个系统中的带宽使用效率的不同。

同步

多个处理器在时间上协调一致。典型的同步机构时系统在硬件原语的支持下通过软件实现的例程。高竞争状态中同步起到一致协调的作用，也成为系统的瓶颈。

硬件原语是面对用户的一些汇编指令，与基本指令不同的是涉及硬件操作多。实现同步的最主要能力是使用一组硬件原语，自动读取修改共享数据。硬件原语是构成面向用户的同步操作的主要组成。对存储单元的读写需要多条语句，如果在这多条语句中插入其他的指令，可能会造成同步失败，使用原语可以降低出错减少时间。

典型的硬件原语操作是“自动交换”，把寄存器的数据和存储单元的数据交换，通过交换，把存储单元中的数值拿到。假设建立一个锁，0代表这个锁可用，1代表不可用，要实现最后读出来是0，表明得到了锁。

存储单元的读写通过仲裁，只能有一个首先完成，多个处理器竞争单元时不会产生冲突。

使用交换指令使用原语的根源在这个原语的操作是一气呵成的，没有其他间隔打断。读和写这两点在实现同步上是不可缺的，如果没有这两点构成一个同步原语，不能实现的。

test-and-set：首先读出来一个数据，测试是不是满足，如果满足则置入一个新数据。

fetch-and-increment：取出来单元数据，自动加一，然后再写进去。

使用一致性实现一个旋转锁，一个处理器不停的测试看是否能获得锁，直至成功，修改锁为占有状态。旋转的过程通常在用户希望这个锁持有的时间很短，低延迟使用时间短的时候适合旋转锁。

很多处理器竞争一个锁的延迟和复杂度不是线性增长的，几乎是二次方，也造成比较大的流量。串行化是锁开销大的最主要原因。竞争大的时候降低串行化，形成有序的通信。软件实现的方法：所有进程争抢这个锁但是只有一个进程能抢到，第一次获得锁失败的话第二次就要延迟一会再去试探。

或者排队锁方法，通过软件构造等待处理器队列，通过队列进行排序，通过顺序有序使用资源。

组合树方法：在软件上实现对大规模机器同步的方法，把大量的竞争化解为对多个小点的竞争，使用n元树结构，一般来说使用k表示树的扇入（fan-in）。在k元树的最底层开始同步，逐级向上，直至根节点。如16个节点的话，就是一个二层的树，之前的代价是16的平方，现在是两倍的4的平方。

总线上10个处理器，同时完成对锁的竞争，假设每个总线事务100个时钟周期，忽略读写占用时间，只计算在竞争锁的时候的代价，对10个处理器获得锁的时候要占用多少总线事务。当i个处理器在竞争时，有i个链取获得锁、i个条件写来尝试获得锁，1个写，一共2i+1个总线事务，要全部通过要进行累加，对n个处理器来说，一共n(n+1)个总线事务。在同步点上进行同步造成相当长的延迟，同时影响了总线的访问。

栅栏同步（barrier）：强制所有进程等待，直到所有进程到达栅栏，再一起释放。这个过程通过两个旋转锁实现，一个是保护计数器，计算到达栅栏的进程数；一个是用于把所有进程卡在这，一旦所有进程都到了就释放。可能会出现进程组中的一个进程永远离不开barrier。

通过sense-reversing区分不同进程到达的barrier是否是同一次进入barrier，如果不是同一次的话可能会造成死锁。

硬件对大规模同步的支持：有些机器通过硬件实现了栅栏同步，类似组合树的方法。保存关于同步的处理器并对其排队，叫做排队锁，硬件上使用位阵列，把先后到达的每一个处理器进行排队，通常是与目录结构结合在一起。

排队锁：当对锁变量第一次失效的时候，这次失效被送同步控制器，如果锁被释放，直接从队列里返回下一个处理器，如果锁不可用则创建一个排队记录。当锁释放的时候，选择下一个处理器进入使用状态，把下一个处理器拿到队列前端。

区别是首次访问锁还是一直在锁里边，这样可以实现排队操作或者释放锁的操作；

另外一个原语是fetch-and-incement，自动取出一个变量并增加数值。这个指令会使barrier指令有改进的空间，因为它将取并增量两个操作结合在一起。现有的MPP机器都采用的是硬件barrier方法。

一致性问题：什么时候能看到被其他处理器更新过的数字，什么时间生效，通常使用共享变量通信。通过读出被写进去的数据来检测是否已经更新过。

两个代码段：

P1:
A = 0;
...
A = 1;

L1:
if (B==0) ...

P2:
B = 0;
...
B = 1;

L2:
if (A==0) ...

如果这个程序能同步正确执行的话，A和B都在cache里，如果写总是能马上生效，那两个if都绝不可能同时为真，因为如果到达两个if，A和B都被赋值为1了。假设写作废被延迟，处理机允许继续向前推进，可能出现P1和P2两个都没看到作废，这种情况就与预计的正确程序行为相违背。

最简单的一致性模型是顺序一致性，需要任何访存顺序一致的程序运行结果一致，它消除了含糊的执行方式，处理器延迟对任何存储器访问的过程，直到所有的写生效；同样的可以将下次访存延迟直到本次访存结束。

一致性涉及到不同变量和不同时间的问题，因此对两个变量的访问必须按照一定的顺序。

在上边的代码中，必须在写操作完成后在进行读A或B，在顺序一致性中也不能简单地把写放到缓存中而已就继续往下执行。

一个处理机对变量的写和另一个处理机对变量的访问通过一对同步操作进行排序，意味着同步操作把数据引用进行了排序，同步把顺序定下来，这就确定了一致性，两个处理器的操作通过同步确定了顺序。如果没有同步操作，变量在读写期间出现顺序不定的情况，称为数据竞争，因为此时对数据的访问基于处理器之间的相对速度，输出是不可预计的，结果正确性不能保证。

同步原语在实现上提供了较为宽松的顺序一致性，即便系统提供了较为宽松的一致性模型，一个同步的程序也会按照标准顺序一致性那样执行，这实际上提供了一种时间上的重叠，为并行的开发提供了条件。

松弛一致性模型的主要思想是允许读写无序进行，而是使用同步操作来强制实现有序，这样的话处理器的操作就像顺序一致性一样。依据松弛的情况分为3种主要的类型。

写后读：写完全生效之后才能进行读，这叫做全存序模型，或者处理器一致性，因为只保留了写的一致性，许多程序在这个模型下保持顺序一致性。旁路和写缓冲是两种主要方法。写缓冲中如果有要读的地址，就先在缓冲中拿到。

写后写：多次写的一个模型，部分存序，在流水线中，第一个写还没有完成的时候第二个写已经启动，两个写之间存在并行，因为两个写之间存在节拍的差距。

读后读/写：弱排序模型。

顺序松弛可以使处理器获得明显的性能提升，在实现上需要硬件的支撑。

线程级并行

多线程使多个线程共享处理机，处理机必须对每个线程的状态进行复制，便于进程切换，没有硬件支撑条件也谈不上多线程并行。比如，对线程所需要的文件来说，有寄存器文件，分开的PC等，提供对不同线程的切换能力，不同节拍可以切换到不同线程，线程切换也要比进程切换更快。

通常有两种方式实现多线程，一个是细粒度的，在指令之间就能完成线程的切换，使多线程的执行是交错的，切换经常采用时间片轮转的方式，优点是隐藏吞吐率上的损失，充分利用CPU的时间，如果线程执行IO时就可以先被切换先来，但是它的总执行时间被延长了。粗粒度的线程级并行在比较长的停顿出现时才进行切换，比如局部cache的失效，它依赖于程序执行的特点，缺点是受限于吞吐率，在有比较大的输入输出时才切换，没有办法充分利用短停顿。粗粒度多线程经常要填充流水线，产生一个起步时间，存在局限性，只有在停顿时间比较长的时候才有效。

SMT（simultaneous multithreading）是多线程的一种，使用处理器的多流出和动态调度能力，在指令级并行的同时实现线程级并行。SMT的基础是处理器有多个功能部件可以并行执行。寄存器换名和动态调度是为了支持不同线程的指令级并行。同时多线程是在多流出支持下，每拍流出的指令可以是来自多个线程的，第一拍是来自两个不同的线程，第二拍是来自另外的线程，以此类推，在线程和指令两个层面实现并行。

有多少个活跃的线程？有多少缓冲区？取指能力是否能满足流水线的需要？等都是SMT的问题，不能完全百分百的利用每一个流水槽。每个线程都要有自己的寄存器组、缓冲等。各个线程的指令要能够独立提交，结果要回到各个线程本身，这要求在逻辑上要提供每个线程的独立重排序缓冲区。

优先线程基于同时多线程，把执行的时间最小化，在多个线程并行的时候，只要有可能，首先流出的就是优先线程的指令，优先线程调度不出的空槽填充其他线程的指令。为最大化单个线程的性能，优先线程的取指、分支预测等应尽可能往前。如果有两个优先线程的话，两个线程就都要优先，两条指令流都要优先服务。

多线程每个都有寄存器，寄存器文件需要很大，保存多现场；保持系统低开销，优先线程需要优先取指；由SMT引起的cache冲突上需要良好处理，引起系统性能下降反而得不偿失。

交叉问题

许多多处理器使用多级cache较少对全局通信的需求，如果cache提供了多级包含特性，即近一级的cache一定是远一级cache的子集，一级cache中的内容一定是二级cache中的子集。

如果L2是L1容量的4倍，在L2中1个起始地址的块，在L1中是4个块。如果L1中的块大小是b，L2中的块大小是4b，则如果在L2中作废一个块x，需要作废以x，x+b，x+2b，x+3b为起始地址的小块（这在L2中被看作是一个块，在L1中被看作是4个块），在L1中同样要作废起始地址为x的一个块，但是没有作废起始地址为x+b的块（如果有的话），这就违背了包含原则。任何时候都要遵守包含特性。

非封锁cache和延迟隐藏：多处理机的失效处罚比较大，延迟也较大，这意味着有更大的延迟可以被隐藏，还有因为流水线失效的延迟可以被隐藏；cache使用非封锁cache支撑了弱一致性模型实现，弱一致性模型可以实现对访存的重排序，重复利用；非封锁cache对实现预取很有必要，利用尽可能空的时候实现存储的迁移，充分利用时间，实现多端口的并行访问。

非绑定是指一个cache的数值要根据其最新数值的变化而变化，不跟随某一个局部拷贝，对全局来说都是一致的。如果是预取到寄存器中，就是绑定的，因为如果数据进入了寄存器就是脱离了地址空间，跟存储地址空间的数据就没有关系了，存储器里的变化跟寄存器里没有关联了。非绑定是在硬件预取设计中不可获取的，只能在地址空间中实现预取。

有几个问题：局部节点需要对多个未完成的访问进行跟踪，跟踪预取地址；流出请求之前，节点必须保证在流出请求之前，对同一个块没有流出其他请求。

定义一个内存一致性模型的另一个原因是针对共享数据，确定合法的编译优化范围。最简单的来说是实现同步（硬件支撑下的对存储器访问的同步）。

通过虚拟存储器实现共享内存，不必从物理内存上考虑容量。共享数据如何从共享cache块移向更大的单元。通过OS进行调度页面。