# 计算机系统结构 > 40+8学时，平时分：小测试，1-10周 > 平时10%（小测试）+实验20%+阶段30%（1-3章节）+期末40%（4-6章节，一点点前面） > 刘亚秋 # 0 绪论 * AIPSN * A * Acceleration * Amdahl $\begin{align}S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}\end{align}$ * I * Instruction * Interface * P * Processing * Parallel S(ingle)/M(ultiple) I(nstruction) S/M D(ata flow) * S * Storage(Memory) * System * N * Network * coNnection # 1 计算机系统结构 ## 1.1 计算机系统结构的基本概念 ### 1.1.1 计算机系统的层次结构 * 计算机系统=硬件（hardware）/固件（firmware）+软件（software） * 计算机语言从低级向高级发展 * 从计算机语言的角度，把计算机系统按功能划分成多级层次结构  ### 1.1.2 计算机系统结构的定义 * 经典定义：computer architecture is a computer programmer see attribute, namely the conceptual sturcture and functional characteristics（程序员所看到的计算机属性，即概念性结构与功能特性） * 按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同的属性 * 透明性：低层次存在但对高层次通常不可见 * 广义的系统结构定义：指令系统结构（instruction set architecture），组成（organization 偶然 micro architecture），硬件（hardware） * 本课给出的定义：计算机系统结构是程序员所看到的**计算机属性**，即（硬件子系统的）概念结构及其功能特性，是计算机软硬件的交界面 * 数据表示 * 寻址规则 * 寄存器定义 * 指令集 * 中断系统 * 机器工作状态的定义与切换 * 存储系统 * 信息保护 * I/O结构 * 计算机系统结构：计算机系统的软、硬件的界面 * 计算机组成：计算机系统结构的逻辑实现 ### 1.1.3 系统结构、计算机组成和计算机实现 * 计算机系统结构的实质 * 确定计算机系统中硬软件的界面，界面之上是软件实现的功能，界面之下是硬件和固件实现的功能 * 包含物理机器级中的数据流和控制流的组成以及逻辑设计等 * 着眼于物理机器级内各事件的排序方式和控制方式，各部件的功能及其联系 * 计算机实现 * 着眼于器件技术，微组装技术 * 具有相同系统结构的计算机可以采用不同的计算机组成，同一种计算机组成又可采用多种不同的计算机实现 ### 1.1.4 计算机系统结构的分类 1. Flynn分类法 按照指令流和数据流的多倍性进行分类 * 指令流：极速那几执行的指令序列 * 数据流：由指令流掉用的数据序列 * 多倍性：在系统最受限的部件上，同时处于同一执行阶段的指令或数据的最大数目 * 分为了4类（单/多 -> 指令流/数据流） * SISD * SIMD * MISD * MIMD 2. 冯氏泽云分类法 用系统的最大并行度对计算机进行分类 * 最大平行度：计算机系统在单位时间内能够处理的最大的二进制位数 最大并行度=字宽$n$$\times$一次能同时处理的字数$m$ * 字串位串：$n＝1,m＝1$ * 字串位并：$n>1,m＝1$。同时处理单个字的多个位 * 字并位串：$n＝1,m>1$。同时处理多个字的同一位 * 字并位并：$n>1,m>1$。同时处理多个字的多个位  3. Handler分类法 根据并行度和流水线对计算机进行分类 把计算机的硬件结构分成3个层次 * 程序控制部件（PCU）的个数$k$ * 算术逻辑部件（ALU）或处理部件（PE）的个数$d$ * 每个算数逻辑部件包含基本逻辑线路（ELC）的套数$w$ * $t=(k,d,w)$ ## 1.2 计算机系统结构的发展 ## 1.4 计算机系统结构的设计 ### 1.4.1 计算机系统设计者的主要任务 计算机系统设计者的任务包括：指令系统的设计、数据表示的设计、功能的组织、逻辑设计以及其物理实现 ### 1.4.2 计算机系统设计的主要方法 1. 由上往下（top-down）设计 * 首先确定面对使用者的那级机器（最高层，应用语言虚拟机）的基本特征、数据类型和格式、基本命令等。然后再逐级往下设计，每级都考虑如何优化上一级的实现 * 适合于专用机的设计，而不适合通用机的设计 2. 由下往上（bottom-up）设计 * 软件技术完全处于被动状态，这会造成软件和硬件的脱节，使整个系统的效率降低 * 在早期受制于硬件种类与性能，采用得比较多，现在已经很少被采用了 3. 从中间开始（middle-out）设计 * 综合考虑软、硬件的分工，从中间开始设计 * 避免了软、硬件设计的分离与脱节 ### 1.4.3 计算机系统的设计准则 * 以经常性事件为重点（大概率事件优先原则） * 对经常发生的情况采用优化方法的原则进行选择，以得到更多的总体上的改进 * 程序的局部性原理 * 程序的时间局部性 程序即将用到的信息很可能就是目前正在使用的信息 * 程序的空间局部性 程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者临近。 ### 1.4.4 计算机系统设计的定量原理 * Amdahl定律 加速比=总执行时间（前）/总执行时间（后） $\begin{align}S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}\end{align}$ $S_n$系统加速比 $T_0$原执行时间 $T_n$新执行时间 $F_e$被改进部分原执行时间占原总执行时间的占比 $S_e$被改进部分的部件加速比 * Amdahl定律是一个性能改进的递减规则 * 如果仅仅对计算任务中的一部分做性能改进，则改进得越多，所得到的总体性能的提升就越有限 * 如果只针对整个任务的一部分进行改进和优化，那么所获得的加速比不超过：1/（1－这一部分的可改进比例） * 为了使系统能够获得较高的加速比，可改进部分必须占用较大的比例 * 例： 假设FPSQR操作占整个测试程序执行时间的20% 一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍 另一种实现方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。 分别计算出两种设计方法的加速比如下 $\begin{align}S_{F P S Q R}=\frac{1}{(1-0.2)+\frac{0.2}{10}}=\frac{1}{0.82}=1.22\end{align}$ $\begin{align}S_{F P}=\frac{1}{(1-0.5)+\frac{0.5}{2}}=\frac{1}{0.75}=1.33\end{align}$ ## 1.5 定量分析技术基础 ### 1.5.1 计算机系统的性能评测 执行时间与吞吐率 ### 1.5.2 基准测试程序 用于测试和比较性能的基准测试程序的最佳选择是真实应用程序 ### 1.5.3 主要性能指标 1. MIPS（Million Instructions Per Second） MIPS=时钟频率/($CPI\times 10^6$) 2. MFLOPS（Million Floating-point Operations Per Second） ### 1.5.4 CPU性能 * 执行一个程序所需的CPU时间 CPU时间=执行程序所需的时钟周期数$\times$时钟周期时间=IC$\times$CPI$\times$时钟周期事件 时钟周期时间=1/系统时钟频率 * 每条指令执行的平均时钟周期数CPI（Cycles Per Instruction） CPI=执行程序所需的时钟周期数/IC IC=所执行的指令条数 * **CPU时间=IC$\times$CPI$\times$时钟周期时间** * 一般来说，计算机系统中现有$n$种指令 $CPI_i$：第$i$种指令的处理时间；$IC_i$：在程序中第$i$种指令出现的次数 则： CPU时钟周期数=$\begin{align}\sum_{i=1}^{n}(CPI_i\times IC_i)\end{align}$ CPU时间=CPU时钟周期数$\times$时钟周期时间 CPI=时钟周期数/$IC$=$\begin{align}\frac{\sum_{i=1}^{n}(CPI_i\times IC_i)}{IC}=\sum_{i=1}^{n}(CPI_i\times \frac{IC_i}{IC})\end{align}$ 其中：$\begin{align}\frac{IC_i}{IC}\end{align}$反映了第$i$种指令在程序中所占的比例 * 例： 假设FP（浮点）指令的比例为25%，其他指令的平均CPI为1.33 其中，FPSQR（浮点平方根）占全部指令的比例为2%，FP操作的平均CPI为4，FPSQR操作的CPI为20 现有两种改进方案，第一种是把FPSQR操作的CPI减至2，第二种是把所有的FP操作的CPI减至2，试比较两种方案 改进前CPI=0.25\*4+0.75\*1.33=1.9975 改进FP后CPI=1.9975-0.25\*(4-2)=1.4975 改进FPSQR后CPI=1.9975-0.02\*(20-2)=1.6375 **注意算法，FPSQR是包含在FP之中的，只能算$\Delta$CPI** # 2 指令系统 ## 2.1 数据表示 **此部分内容计组中已有涉及，不再赘述** ## 2.2 指令系统的分类 | 类型 | 优点 | 缺点 | | -------- | -------------------------------------- | ------------------------ | | 堆栈型 | 指令长度短，代码密度高，占用存储空间小 | 代码效率低，执行效率不高 | | 累加器型 | 指令长度短，代码密度高，代码效率高 | 执行效率不高 | | 寄存器型（主流） | 指令简单，执行效率高，对编译程序支持好 | 指令长度长 | 对比：   ## 2.3 寻址技术 寻址技术就是寻找操作数及其他信息的地址的技术，它是软件和硬件的一个主要分界面 * 寻址方式选择 * 使用**频度分析法**根据指令系统风格和各种寻址方式的使用频率，选择高频率的寻址方式 * 定位方式 * 直接定位方式（编译期） * 在程序装入主存储器之前，程序中的指令和数据的主存物理地址就已经确定 * 静态定位方式（装入期） * 在程序装入主存储器的过程中随即进行地址变换，确定指令和数据的主存物理地址 * 动态定位方式（运行期） * 在程序执行过程中，当访问到相应的指令或数据时才进行地址变换，确定指令和数据的主存物理地址 ## 2.4 指令格式的优化设计（阶段内容） 指令一般由两部分组成：操作码和地址码 * 操作码 * 指令的操作种类 * 所用操作数的类型 * 地址码 * 操作数地址 * 地址的附加信息 * 寻址方式 指令格式优化设计的目标：**节省程序的存储空间**；指令格式要**尽量规整**，以**减少硬件译码的复杂度** ### 2.4.1 指令格式评价方法 * 编码的平均码长$l$ * $\begin{align}l=\sum_{i=1}^{n} p_{i} \cdot l_{i}\end{align}$ * $p_i$：第$i$种操作码在程序中出现的概率 * $l_i$：第$i$种操作码的编码长度 * 编码的信息冗余量$R$ * $\begin{align}R=1-\frac{H}{l}\end{align}$ * $H$：为信息熵（理论上的最短码长） $\begin{align}H=-\sum_{i=1}^{n} p_{i} \cdot \log _{2}{p_{i}}\end{align}$ ### 2.4.2 常见指令格式 * 固定长度操作码 * 思想 所有指令的操作码长度都是相同的。如果需要编码的指令有$n$条，则固定长度操作码的位数至少需要$\lceil log_2n \rceil$位。目前许多的RISC采用该思想。 * 例子  在该例中，所有操作码长度$l=\lceil log_2 7 \rceil=3$ 由信息熵可得$H=1.95$ 因此，$R=1-{1.95}/{3}=0.35$ * 优点 非常规整；硬件译码设计简单 * 缺点 码字存在信息浪费 * Huffman编码法 * 思想 概率高的用短位数表示，概率低的用长位数表示 * 算法 利用Huffman树实现 * 特点 理论上最优化的编码方式，但操作码很不规整，译码电路设计复杂 * 扩展编码法 * 思想 将固定长度操作码和Huffman编码法相结合形成，对Huffman编码，根据宏观频率分布将其扩展成有限几种长度的编码（简单来说就是舍弃一部分效率以换取电路的可行性） * 问题 存在多种扩展编码方式，需要按需选择 * 不定长扩展编码法  ## 2.5 指令集结构的系统设计 * 指令系统性能 * 完整性 任何通用计算机指令系统都应该具备基本的指令种类 * 高效率 指令的执行速度要快，使用频度要高 * 兼容性 “计算机系统的生命力之所在” * 规整性 是硬件设计（如：VLSI技术）和软件设计（如：编译程序）的需要 * 对称性 各种与指令系统有关的数据存储设备的使用、操作码的设置等都要对称 * 均匀性 对于各种不同的数据类型、字长、操作种类和数据存储设备，指令的设置要同等对待 * 基本指令系统 * 数据传送类指令 * 运算类指令 * 程序控制指令 * 输入输出指令 * 处理机控制和调试指令 ## 2.5.1 复杂指令系统计算机（CISC） 增强原有指令的功能以及设置更为复杂的新指令取代原先由软件子程序完成的功能 * 从面向目标程序的优化实现来改进指令系统 * 优化目的 * 缩短目标程序的长度，即减少程序的空间开销 * 缩短目标程序的执行时间，即减少程序的时间开销 * 优化途径 * 对使用频率高的指令，增强其功能、加快其执行速度并缩短字长 * 对使用频率高的指令串，增设新指令来替代它 * 对使用频率低的指令，取消或合并，但要考虑到指令系统的兼容性问题 * 从面向高级语言的优化实现来改进指令系统 * 优化目的 * 尽可能减小高级语言和机器语言之间的语义差距，以利于支持高级语言编译器的构造，目的在于缩短编译器的代码长度及编译时间 * 优化方法 * 增强对高级语言支持的指令的功能 * 增强对编译程序支持的指令的功能 * 高级语言计算机 * 从面向操作系统的优化实现来改进指令系统 * 优化目的 * 减少运行操作系统所需的辅助操作时间 * 节省操作系统所占用的存贮空间 * 优化方法 * 对操作系统中常用的指令和指令串的使用频率进行统计和分析来改造 * 增设专用于操作系统的新指令 * 将操作系统中由软件子程序实现的某些功能改用硬件或固件实现 ## 2.5.2 精简指令系统计算机（RISC） RISC应有如下的特点 * 大多数指令在单周期内完成 * LOAD/STORE结构 * 硬布线控制逻辑 * 减少指令和寻址方式的种类 * 固定的指令格式 * 注重编译优化技术 RISC为使**流水线**高效率执行： * 简单而统一格式的指令译码 * 大部分指令可以单周期执行完成 * 仅LOAD和STORE指令可以访问存储器 * 简单的寻址方式 * 采用延迟转移技术 * 采用LOAD延迟技术 RISC为使优化编译器便于生成优化代码： * 三地址指令格式 * 较多的寄存器 * 对称的指令格式 # 3 流水线技术 提高计算机性能的两个重要方法 1. 缩短执行每条指令所需的平均周期数CPI 如：RISC技术 2. 提高处理机内执行指令中的并行度，即在同一时刻同时运行多条指令 如：**流水线技术** ## 3.1 先行控制技术 先行控制（Look-ahead）技术的关键是缓冲技术和预处理技术的结合。通过对指令流和数据流的预处理和缓冲，能够尽量使指令分析器和指令执行部件独立地工作并始终处于忙碌的状态 1. 指令的重叠执行 通常指令的解释方式可分为顺序、重叠和流水三种。顺序模式执行缓慢且易于理解，此处不再赘述 在计算机系统中广泛采用重叠操作方式。它是指在计算机中不同部件或同一部件内的各种操作在时间上存在重叠部分。 一条指令在计算机内部的执行通常可以划分为取值、分析、执行三个步骤，将不同指令之间进行重叠步骤运行，可以有效加快计算机的指令执行速度，并且充分利用不同阶段的部件 一次重叠执行： *  二次重叠执行： *  2. 先行控制技术 实现指令的重叠执行可能会遇到以下的问题 1. 需要独立的取值、分析、执行部件 可以通过设置对应的独立存储控制器、指令控制器和运算控制器解决 2. 主存访问冲突 取指、分析、执行三个阶段中都可能涉及到访存操作，一旦三个独立的部件同时提出对存储器的读写请求时就会引起主存访问冲突 可以通过设置缓存（程序Cache，数据Cache）；多体交叉存储器结构来环节，但引入先行控制技术是解决问题的根本方法  在部件之间设立适当的缓冲栈，可以确保前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。可以有效的平衡不同部件，不同执行阶段产生的时间差异，减少部件出现空等现象，提高部件的利用率 **缓冲栈的深度应当满足以下的关系** $D_{fetch\ com}\geq D_{opr\ com} \geq D_{read} \geq D_{write}$ ## 3.2 流水线的基本概念 ### 3.2.1 流水线技术 1. 流水线技术 把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。（重叠执行的进阶版本） 流水线中的每个子过程及其功能部件称为**流水线的级或段**，段与段相互连接形成流水线。流水线的段数称为**流水线的深度**。 2. 流水线结构 重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器**用于保存本流水段的执行结果**，就成了一个简单的流水线结构。  3. 时空图 时空图可以直观地表现流水线的工作过程  * 横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。 如果各级执行所需的时间相等，在横轴上应表现为等距离的时间段。 * 纵轴表示段，即流水线的各个子操作过程，通常也称为**功能段**。 4. 流水机的工作频率 为了确保不同阶段之间协调工作，如果每个流水段的延迟时间（通过该段的时间）为$\Delta ts$，锁定时间为$\Delta tl$。则该流水机的最高工作频率为$\begin{align}{TP}_{MAX}=\frac{1}{\max (\Delta t s+\Delta t l)}\end{align}$ 5. 流水线的工作特点 1. 一条流水线通常由多个流水段组成。流水线的段数也称为流水线的“深度”或“流水深度” 2. 每个流水段有专门的功能部件对指令进行某种加工。 3. **各流水段所需时间应尽量相等**，否则，时间长的流水段将成为流水线的瓶颈，会造成流水线的“阻塞”和“断流” 4. 流水线工作阶段可分为建立（充入）、满载和排空三个阶段 5. 在**理想情况**下，当流水线充满后，每隔$\Delta t$时间将会有一个结果流出流水线。 ### 3.2.2 流水线种类 1. 按处理机分类 * 操作部件级 最低级别的流水线 把处理机的算术逻辑运算部件分段 如一个浮点加法部件的流水线：  部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为**超流水线处理机**。 * 处理机级 也称指令流水线 将一条指令的解释执行过程分解成若干个子过程 * 处理机间级 处理机间流水线通常是多处理机系统中对任务采取的一种处理策略 2. 按流水线功能分类 * 单功能流水线 一条流水线只能完成一种单一的任务 * 多功能流水线 时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线 3. 按工作方式分类 * 静态流水线 当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线 静态流水线既可以是单功能流水线也可以是多功能流水线  * 动态流水线 没有时间上的限制，而可以在任何时候根据需要改变其连接的流水线 动态流水线一定是多功能流水线  4. 按连接方式分类 * 线性流水线 在部件上没有反馈连接的流水线 指令依次通过各个部件仅一次就完成指令执行的全过程 * 非线性流水线 各部件除了串行连接外还通过**反馈线**连接，使得某些部件可以得到重复使用，指令在通过这种流水线时可能在反馈部件上重复运行若干次 **非线性流水线的冲突避免是本章重点之一** 5. 按流入流出顺序分类 * 顺序流水线 输出的结果与输入的次序相同，早期的流水线通常都是顺序流水线 * 乱序流水线 将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序 6. 按数据表示方式不同 * 标量流水线 * 向量流水线 7. 按控制方式不同 * 同步流水线 处理机内的指令流水线通常都是同步流水线，通过统一的时钟控制各级同时进行动作（Base clock） * 异步流水线 处理机间流水线通常都是异步流水线，通过回调应答来确保可靠性 ## 3.3 流水线的性能指标 * 吞吐率 流水线在单位时间内完成的任务量 $\begin{align}TP=\frac{n}{T_k}\end{align}$ $n$是完成任务的总数，$T_k$是完成这$n$个任务所用的总时间 * 如下一条$m$级的流水线执行$n$条指令的时空图：  完成这$n$条指令所需的总时间$T_k=(m+n-1)\Delta t$ 则吞吐率$\begin{align}TP=\frac{n}{(m+n-1)\Delta t}\end{align}$ 当任务量足够多$n\rightarrow \infty$时，$m-1$可以忽略不计，得到的最大吞吐率为$\begin{align}TP_{\max }=\lim _{n \rightarrow \infty} \frac{n}{(m+n-1) \Delta t}=\frac{1}{\Delta t}\end{align}$ * 通常情况下各阶段执行时间不等  则吞吐率为$\begin{align}TP=\frac{n}{\sum_{i=1}^{k} \Delta t_{i}+(n-1) \max \left(\Delta t_{1}, \Delta t_{2}, \ldots, \Delta t_{k}\right)} \end{align}$ 同理可得当$n\rightarrow \infty$时，最大吞吐率为$\begin{align}TP_{\max }=\frac{1}{\max \left(\Delta t_{1}, \Delta t_{2}, \ldots, \Delta t_{k}\right)}\end{align}$ 在后例中可以显然发现，如果流水线中各级的执行时间不相等，其中时间最长者就成了流水线中的“瓶颈”。因此消除瓶颈是设计流水线的一个重要原则，通常采取以下两种方式： 1. 分割瓶颈部件的工作 2. 重复设置瓶颈部件 * 加速比 处理同一批任务，不用流水线与采用流水线所花费的时间之比 $\begin{align}S=\frac{T_0}{T_k}\end{align}$ $T_0$是不用流水线所用的时间，$T_k$是使用流水线所用的时间 不用流水线时，每条指令执行时必须在时间上顺序地完成各处理步骤，那么$n$条指令所需时间就为$T_0=n\cdot k\Delta t$。而一个采用流水线的处理机所需时间为$T_k=(k+n–1)\Delta t$。 加速比为$\begin{align} S=\frac{T_{0}}{T_{k}}=\frac{n \cdot k \Delta t}{(k+n-1) \Delta t}=\frac{k \cdot n}{k+n-1} \end{align}$ 当任务量足够多$n\rightarrow \infty$时，最大加速比为$\begin{align} S_{\max }=\lim _{n \rightarrow \infty} \frac{k \cdot n}{k+n-1}=k \end{align}$ 进一步的，考虑各级执行时间不等的情况，根据前述可以得到总时间为$\begin{align}\sum_{i=1}^{k} \Delta t_{i}+(n-1) \max \left(\Delta t_{1}, \Delta t_{2}, \ldots, \Delta t_{k}\right)\end{align}$。 因此，一般情况下的加速比为$\begin{align}S=\frac{n \cdot \sum_{i=1}^{k} \Delta_{i}}{\sum_{i=1}^{k} \Delta_{t}+(n-1) \max \left(\Delta_{t}, \Delta_{t}, \ldots, \Delta_{t}{ }_{k}\right)}\end{align}$ * 效率 效率$\begin{align} E=\frac{(Time*Space)_{actual}}{(Time*Space)_{occupied}} \end{align}$  在该图中，各级执行时间相等的流水线效率为$\begin{align}E=\frac{n \cdot k \Delta t}{k \cdot(k+n-1) \Delta t}=\frac{n}{k+n-1}\end{align}$ 显然，n越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为$\begin{align}E_{\max }=\lim _{n \rightarrow \infty} \frac{n}{k+n-1}=1\end{align}$ * 小结 均考虑在各级执行时间相等$\Delta t$的流水线下，一条$k$级流水线执行$n$条指令的情况 吞吐率：$\begin{align}TP=\frac{n}{(k+n-1)\Delta t}\end{align}$ 加速比：$\begin{align} S=\frac{n \cdot k \Delta t}{(k+n-1) \Delta t}=\frac{k \cdot n}{k+n-1} \end{align}$ 效率：$\begin{align}E=\frac{n \cdot k \Delta t}{k \cdot(k+n-1) \Delta t}=\frac{n}{k+n-1}\end{align}$ 容易发现三者之间两两均存在关系 $S=k\cdot E$ $E=TP\cdot \Delta t$ $S=TP\cdot k \cdot \Delta t$ * 例：线性多功能静态流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。 用TI－ASC计算机的多功能静态流水线计算两个向量的点积：$Z＝AB＋CD＋EF＋GH$  为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个加法AB＋CD和EF＋GH，最后求总的结果Z。 $Z＝\{[(AB)＋(CD)]＋[(EF)＋(GH)]\}$  * 解： * 有$T_k＝20\Delta t$，$n=7$，则流水线的吞吐率$TP$为 $\begin{align}{TP}=\frac{{n}}{{T_k}}=\frac{7}{20 \cdot \Delta {t}}=0.35 \frac{1}{\Delta {t}}\end{align}$ * 如果采用顺序执行方式，完成一次乘法要用4个$\Delta t$ ，完成一次加法要用6个$\Delta t$ ，则完成全部运算要用：$\begin{align}T_{0}=4 \times 4 \Delta t+3 \times 6 \Delta t=34 \Delta t\end{align}$ 则流水线的加速比$S$为： $\begin{align}{S}=\frac{{T}_{0}}{{~T}_{{k}}}=\frac{34 \cdot \Delta {t}}{20 \cdot \Delta {t}}=1.70\end{align}$ * 整个流水线共有8段，流水线效率$E$为： $\begin{align}E=\frac{T_0}{k \cdot T_{k}}=\frac{34 \cdot \Delta t}{8 \times 20 \cdot \Delta t}=0.21\end{align}$ **改用动态流水线** AB+CD运算前移两个时间单位 EF+GH运算前移一个时间单位 (AB+CD)+(EF+GH)运算前移一个时间单位  改用动态流水线后$T_k＝19\Delta t$ $\begin{align}{TP}=\frac{{n}}{{T_k}}=\frac{7}{19 \cdot \Delta {t}}=0.368 \frac{1}{\Delta {t}}\end{align}$ $\begin{align}{S}=\frac{{T}_{0}}{{~T}_{{k}}}=\frac{34 \cdot \Delta {t}}{19 \cdot \Delta {t}}=1.789\end{align}$ $\begin{align}E=\frac{T_0}{k \cdot T_{k}}=\frac{34 \cdot \Delta t}{8 \times 19 \cdot \Delta t}=0.224\end{align}$ 提升约1.11\% ## 3.4 流水线的相关与冲突 * 从经典的五段流水线角度出发 一条指令的执行过程分为5个周期:取指令周期（IF) 、指令译码/读寄存器周期(ID)、执行l有效地址计算周期（EX)）、存储器访问/分支完成周期(MEM)、写回周期（WB）  在这种情形下，指令对流水线的占用情况如下表 | $\quad$ | ALU（逻辑运算） | LOAD/STORE（访存/写回） | BRANCH（分支） | | ------- | ---------------- | ----------------------- | ---------------------------- | | IF | 取指 | 取指 | 取指 | | ID | 译码，读寄存器堆 | 译码，读寄存器堆 | 译码，读寄存器堆 | | EX | 执行 | 计算有效地址 | 计算转移目标地址，设置条件码 | | MEM | -- | 访存 | 转z移目标地址送PC | | WB | 结果写回寄存器堆 | 读出数据写入寄存器堆 | -- | * 指令相关性 * 相关是指两条指令之间存在某种依赖关系 * 从对流水线的分析中可以发现，如果流水线始终处于“充满”的状态，实际性能可以达到或接近理论值。如果流入流水线的指令出现断流，将极大地影响流水线的性能 * 造成断流的原因主要有三大类： * 名相关 * 名：指令所访问的寄存器或存储单元的名称 * **如果两条指令使用相同的名（使用相同的部件），但是它们之间并没有数据流动**，则称这两条指令存在名相关 * 若两条指令存在**先读后写**的名相关，也称指令间存在**反相关** * 若两条指令存在**写入同名**的名相关，也称指令间存在**输出相关** * 名相关的指令并没有数据传送，因此一条指令的名改变了也不影响另一条指令的执行。但**名相关的两条指令的执行顺序必须严格遵守** * 可以通过换名技术，改变操作数中的名来消除名相关 * 换名技术例题： ``` DIV.D F2,F6,F4 ADD.D F6,F0,F12 SUB.D F8,F6,F14 ``` ``DIV.D``和``ADD.D``存在反相关 那么就可以进行寄存器换名，将F6换成S，就变成 ``` DIV.D F2,F6,F4 ADD.D S,F0,F12 SUB.D F8,S,F14 ``` 这样就消除了名相关 * 数据相关 * 指令之间存在数据流动，通常是后续的指令使用的前驱指令的结果，则称指令之间存在数据相关 * 数据相关具有**传递性**，即如果指令i和指令j数据相关；指令j和指令k数据相关，则指令i和指令k也数据相关 * 数据相关性要求指令之间的数据流动必须有序进行，不能乱序 * 控制相关 * 控制相关是指由分支指令引起的相关 * 常见的结构是``if-then``结构 * 控制相关带来了以下两个限制: * 与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了 * 如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后 * 流水线冲突 * 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行 * 流水线冲突有3种类型： * 结构冲突 结构相关是当多条指令进入流水线后，硬件资源满足不了指令重叠执行的要求（争用同一部件）时产生的 解决方法：暂停一排，也称流水线气泡 * 数据冲突 数据相关是指令在流水线中重叠执行时，当后继指令需要用到前面指令的执行结果时发生的 三种情形： * 写后读 * 定向传送部件 * 流水线互锁，插入暂停 * 指令调度，允许输出结果的次序与输入指令的次序不同 * 读后写 * 由于非按序执行造成的先写后读 * 写后写 * 由于非按序执行造成了两次写入次序不同 * 控制冲突 控制相关是当流水线遇到分支指令和其他改变PC的值的指令时引起的 <!-- * 流水线的无冲突调度 预约表习题： 一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns，它的预约表如下：  * 写出流水线的禁止向量和初始冲突向量。 * 画出调度流水线的状态图。 * 求流水线的最小启动循环和最小平均启动距离。 * 求平均启动距离最小的恒定循环。 * 求流水线的最大吞吐率。 * 按照最小启动循环连续输入10个任务，求流水线的实际吞吐率。 * 画出该流水线各功能段之间的连接图。 --> # 4 存储系统 ## 4.1 存储系统的基本概念 ### 4.1.1 存储系统的定义 采用多种存储器技术，构成多级存储层次结构，利用程序访问的**局部性原理**，来解决对存储系统的速度，成本与容量的需求矛盾  ### 4.1.2 存储系统的性能参数 * 存储容量$S$ 由于$S_1$主存通常不用来存储大量信息，一般来说$S=S_2$ * 每位价格$C$ $\begin{align}C=\frac{C_{1} S_{1}+C_{2} S_{2}}{S_{1}+S_{2}}\end{align}$ 当$S_1<<S_2$时，$C=C_2$ * 命中率$H$ 命中率：CPU访问存储系统时，在$M_1$中找到所需信息的概率 $\begin{align}H = \frac{N_{1}}{N_{1}+N_{2}}\end{align}$ $N_1$访问$M_1$的次数；$N_2$访问$M_2$的次数 * 平均访问时间$T_A$（以一个两级存储体系为例Cache+主存） $\begin{aligned} {T}_{{A}} &={HT}_{1}+(1-{H}) \quad\left({T}_{1}+{T}_{{M}}\right) \\ &={T}_{1}+(1-{H}) {T}_{{M}} \\ {T}_{{A}} &={T}_{1}+{FT}_{{M}} \end{aligned}$ 分两种情况来考虑CPU的一次访存 * 当命中时，访问时间即为$T_1$（命中时间） * 当不命中时，情况比较复杂 * 不命中时的访问时间为：$\begin{array}{l} {T}_{2}+{T}_{{B}}+{T}_{1}={T}_{1}+{T}_{{M}} \\ {T}_{{M}}={T}_{2}+{T}_{{B}} \end{array}$ 不命中开销$T_M$：从向$M_2$发出请求到把整个数据块调入$M_1$中所需的时间$T_2+T_B$ ### 4.1.3 存储器的层次结构 | $\quad$ | "Cache-主存"层次 | "主存－辅存"层次 | | -------------------------- | ---------------------- | ------------------------------ | | 目的 | 弥补主存**速度的不足** | 弥补主存**容量的不足** | | 实现 | **完全由硬件实现，对程序员透明** | 依靠辅助软硬件，特别是操作系统 | | 一、二级之间的访问速度比值 | 几比一 | 几万比一 | | 不命中时CPU是否切换 | 不切换 | 切换到其他进程 |  * 存储层次的四个问题 1. 当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上? (映象规则) 2. 当所要访问的块在高一层存储器中时，如何找到该块? (查找算法) 3. 当发生不命中时，应替换哪一块? (替换算法) 4. 当进行写访问时，应进行哪些操作? (写策略) ## 4.2 Cache基本知识 * Cache和主存分块 Cache是按块进行管理的。**Cachc和主存均被分割成大小相同的块**。信息以块为单位调入Cache * 主存块地址（块号）用于查找该块在Cache中的位置 * 块内位移用于确定所访问的数据在该块中的位置  * Cache的重要性 * 矛盾：DRAM密度高，价格低，但速度与CPU的差距越来越大。 * 办法：Cache-利用局部性原理，加快经常性事件原理，将程序和数据放到与CPU速度匹配的高速存储器中（效率取决于命中率，根据程序特点不同，目前平均可做到95%) * 工作原理示意图  主存$\rightarrow$Cache地址变换即**映像规则** ### 4.2.1 映像规则 1. 全相联映像 主存中的任一块可以被放置到Cache中的**任意**一个位置 **空间利用率最高，冲突概率最低，实现最复杂** 2. 直接映像 主存中的任一块可以被放置到Cache中**确定的**一个位置 **空间利用率最低，冲突概率最高，实现最简单** 通常都采用循环分配的策略，即对应主存的第$i$块，将其映像到Cache的第$i\%M$块，$M$为Cache的总块数 3. 组相联映像 主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置 **一种介于全相联与直接映像之间的折中策略** 引入了**组的概念**，若干**块**组成一**组**，即对应主存的第$i$块，将其映像到Cache的第$i\%G$组内的任意一块，$G$为Cache的总组数 由于全相联Cache的设计过于复杂，通常一组内的块数不会太多，绝大多数的计算机中的$n=M/G\leq 4$ | $\quad$ | $n$（路数） | $G$（组数） | | ---------- | ----------- | ----------- | | 全相联映像 | $M$ | $1$ | | 直接映像 | $1$ | $M$ | | 组相联映像 | $1<n<M$ | $1<G<M$ | ### 4.2.2 查找算法 用于确定Cache中是否有要访问的块，可以通过**查找目录表**实现，每个主存块都能唯一的通过块地址的高位来确定  * 全相联映像 直接记录主存块号与Cache块号之间的映射即可  * 直接映像 根据表示块号在目录表中的有效位是否为1来判断Cache内是否有对应块数据。如有，直接根据主存块地址的低位去访问Cache即可  * 组相联映像 将主存区号与主存组内块号共同记录标识一块，并将其映射结果作为Cache组内块号，用于访问Cache  ### 4.2.3 替换算法 1. 随机法 随机替换一个块 实现简单，命中率尚可 2. FIFO法 替换掉最早装入Cache内的块 命中率不佳 3. LRU法 替换掉近期最少被访问的块 实现复杂，命中率高 对容量不大的Cache，一般来说， LRU命中率优于随机法 对于容量很大的Cache，LRU和随机法的命中率差别不大  ### 4.2.4 写策略 不同的写策略将会引起不同的Cache与主存内容关系 1. 写直达 执行“写”操作时，不仅写入Cache，而且也写入下一级存储器 易于实现，一致性好，但写修改入下一级的过程无法经由Cache优化，**CPU会产生写停顿** *引入写缓冲器，分离开CPU写缓存与写内存的操作，可以起到加速效果* 当写不命中时，直接写入下一级 2. 写回法 执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。通常需要借助“修改位”实现 速度快，对存储器带宽要求较低 当写不命中时需要先把块调入Cache，再行写入 ### 4.2.5 Cache性能分析 * 平均访存时间 **平均访存时间=命中时间$+$不命中率$\times$不命中开销** <!-- 平均访存时间$=$指令所占百分比$\times$（指令命中时间$＋$指令失效率$\times$失效开销）$+$ 数据所占的百分比$\times$（数据命中时间$＋$数据失效率$\times$失效开销）  --> * 程序执行时间（CPU时间） **CPU时间=（CPU执行周期数$+$存储器停顿周期数）$\times$时钟周期时间** **存储器停顿时钟周期数=访存次数$\times$不命中率$\times$不命中开销** **例题1** 假设Cache的**命中时间为1个时钟周期**，**失效开销为50个时钟周期**，在混合Cache中一次Load或Store操作访问Cache的命中时间都要**增加一个时钟周期**（因为混合Cache只有一个端口，无法同时满足两个请求，混合Cache会导致结构冲突） 1. 试问指令Cache和数据Cache容量均为16KB的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低（假设程序中约有75%的指令为取指令，25%的指令为写指令）？ 2. 又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？  解： 1. $Miss_{sep}=75\% \times 0.64\%+25\% \times 6.47\%=2.0975\%$ $Miss_{mix}=1.99\%$ 混合Cache的失效率更低 2. $AMAT_{sep}=1+2.0975\% \times 50=2.04875$ $AMAT_{mix}=1+1.99\% \times 50+25\% \times 1=2.245$ **例题2** 假设Cache**不命中开销为50个时钟周期**，当不考虑存储器停顿时，所有指令的**执行时间都是2个时钟周期**，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响 解： 在有Cache时，CPU时间为$2+1.33*2\%*50=3.33$ 在无Cache时，CPU时间为$2+1.33*50=68.5$ 加速比为20.571 **例题3** 考虑两种不同组织结构的Cache：直接映象Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： 1. 理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次 2. 两种Cache容量均为64KB，块大小都是32字节 3. 在组相联Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响 4. 这两种结构Cache的不命中开销都是70ns 5. 命中时间为1个时钟周期，64KB直接映象Cache的不命中率为1.4%，相同容量的两路组相联Cache的不命中率为1.0% 解： 1. $AMAT_{direct}=1\times 2ns+1.4\% \times 70ns=2.98ns$ $AMAT_{2-way}=1\times 2.2ns+1.0\% \times 70ns=2.90ns$ 2. $CPUTIME_{direct}=2.0\times 2ns + 1.3\times (2.98-1\times 2ns)=5.274ns$ $CPUTIME_{2-way}=2.0\times 2.2ns + 1.3\times (2.90-1\times 2.2ns)=5.31ns$ ### 4.2.6 改进Cache的性能 * 降低不命中率 * 减少不命中开销 * 减少Cache命中时间 ## <div style="color:red;"> 4.3 降低Cache不命中率 </div> * 三种类型的不命中 1. 强制不命中 * 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中 （冷启动不命中，首次访问不命中） * 解决：**增加块大小**，预取（本身很少） 2. 容量不命中 * 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中 * 解决：**只能增大Cache容量** 3. 冲突不命中 * 在**组相联或直接映象Cache**中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况 * 解决：**提高相联度**（理想情况：全相联），牺牲Cache **需要注意的是，许多降低不命中率的方法会增加命中时间或不命中开销** ### 4.3.1 增加Cache块大小（解决强制不命中） * 不命中率与块大小的关系 * 对于给定的Cache容量，**当块大小增加时，不命中率开始是下降，后来反而会上升**  * 原因: * 一方面，更大的容量减少了强制性不命中 * 另一方面，由于增加块大小会减少Cachc中块的数目，所以有可能会**增加冲突不命中** * Cache容量越大，使不命中率达到最低的块大小就越大 * 从失效开销的角度来讲，块大小的选择取决于下一级存储器的延迟和带宽两个方面 * 高延迟和高带宽时，宜采用较大的Cache块 * 与之相反，宜采用较小的Cache块，块的数量多，就有可能减少冲突失效 * 增大Cache容量，进而增加块大小 * 是降低不命中率的最直接的方法 * 缺点： * 增大成本 * 可能增加命中时间 * 增加Cache容量会降低不命中率，但当Cache容量已经很大时，再增大Cache的效果也会不明显 **例题4** 假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节，即：经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。请问对于表中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？  解： 需要注意的一点是，每一次访存实际上只有**请求字**是立即需要的，因此每一次访存最多也只会调一块。（可能会因为一些指令预取等优化策略导致每次访存调入Cache多块，但不在此处的讨论范围内） $AMAT=1+Miss\times (40+Size_{Block}/16 \times 2)$ 结果如  ### 4.3.2 提高相联度（解决冲突不命中） * 采用相联度**超过8**的方案的实际意义不大（已经等效于全相联） * **2:1 Cache经验规则** * **容量为$N$的直接映象Cache的不命中率 和 容量为$N/2$的两路组相联Cache的不命中率 近似相同** * **提高相联度是以增加命中时间为代价的** **例题5** 假定提高相联度全按下列比例增大处理器时钟周期： 1. 时钟周期2路=1.10$\times$时钟周期1路 2. 时钟周期4路=1.12$\times$时钟周期1路 3. 时钟周期8路=1.14$\times$时钟周期1路 假定**命中时间为1个时钟**，直接映象情况下**失效开销为50个时钟周期**，而且假设不必将失效开销取整。使用表中的失效率，试问分别当Cache为多大时，以下不等式成立？  1. 平均访存时间8路<平均访存时间4路 2. 平均访存时间4路<平均访存时间2路 3. 平均访存时间2路<平均访存时间1路 解： $AMAT_{1-way}=AMAT_{direct}=(1+Miss_{1-way}\times 50)$ $AMAT_{2-way}=1.10\times 1+Miss_{2-way}\times 50$ $AMAT_{4-way}=1.12\times 1+Miss_{4-way}\times 50$ $AMAT_{8-way}=1.14\times 1+Miss_{8-way}\times 50$ **（需要特别注意的是，处理器时钟周期的延长只会影响命中时间的时钟周期，而失效开销涉及到访问存储器，这里的时钟周期通常取决于内存时钟周期，不受处理器时钟周期的影响）** 可得各种容量和相联度情况下Cache的平均访存时间  当Cache容量不超过16KB时，上述三个不等式成立 从32KB开始，对于平均访存时间有：$AMAT_{4-way}<AMAT_{2-way}$，$AMAT_{2-way}<AMAT_{direct}$，但$AMAT_{8-way}>AMAT_{4-way}$。 特殊计算32KB情况： 1. $AMAT_{1-way}=(1+0.02\times 50)=2$ 2. $AMAT_{2-way}=1.10\times 1+0.014\times 50=1.8$ 3. $AMAT_{4-way}=1.12\times 1+0.013\times 50=1.77$ 4. $AMAT_{8-way}=1.14\times 1+0.013\times 50=1.79$ ### 4.3.3 “牺牲”Cache（解决冲突不命中） * 一种能减少冲突不命中次数而又不影响时钟频率的方法 * 基本思想 * 在Cache和它从下一级存储器调数据的通路之间设置一个**全相联的小Cache**，称为“牺牲”Cache ( Victim Cache)。**用于存放被替换出去的块（称为牺牲者）**，以备重用（时空局部性原理） * 每当发生不命中时，先检查牺牲Cache中有无所需的块，若没有，再访问主存。 * 作用 * 对于减小**冲突不命中**很有效,特别是对于小容量的直接映象数据Cache，作用尤其明显 * 项数为4的Victim Cache能使4KB Cache的冲突不命中减少$20\% \sim 90\%$ ### 4.3.4 伪相联Cache（列相联Cache） * 工作原理 在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若正常命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找；若找到，则发生了伪命中，否则就只好访问下一级存储器  * 优点 命中时间小 不命中率低 * 缺点 多种命中时间会使CPU流水线设计复杂化，伪相联往往用在离处理器比较远的Cache上（如二级Cache） **例题6** 假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据(伪命中)时，需要2个额外的周期。仍用例题5中的数据，问：当Cache容量分别为2KB和128KB时，直接映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？ 解： 1. Cache为2KB时 $AMAT_{direct}=(1+0.098\times 50)=5.9$ $AMAT_{2-way}=(1*1.10+0.076\times 50)=4.9$ $AMAT_{p-asso}=(1+(0.098-0.076)\times 2+0.076\times 50)=4.844$ 2. Cache为128KB时 $AMAT_{direct}=(1+0.01\times 50)=5.9$ $AMAT_{2-way}=(1*1.10+0.007\times 50)=4.9$ $AMAT_{p-asso}=(1+(0.01-0.007)\times 2+0.007\times 50)=1.356$ ### 4.3.5 硬件预取 发生指令失效时取两个块（32字），被请求指令块放入Cache，下一块放入指令流缓冲器中；如果被请求的指令块恰好在指令流缓冲器中，直接取出，并预取下一指令块 **预取发生在Cache失效与访存之间，通常需要一个不大的时间周期** 预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能 **例题7** Alpha AXP21064，使用8KB指令Cache并采用指令预取技术，预取命中率为25%，其实际失效率是多少？若不采用指令预取技术，Alpha AXP21064的指令Cache必须为多大才能保持平均访存时间不变  解： 1. $AMAT_{preFetch}=1+1.10\% \times (25\%\times 1+(1-25\%)\times 50)=1.41525$ $AMAT_{nonPreFetch}=1+Miss\times 50=1.4152$，则$Miss<=0.8304\%$，指令Cache至少为16KB才能保持平均访存时间不变 ### 4.3.6 编译器控制的预取 在编译时加入预取指令，在数据被用到之前发出预取请求 按照预取数据所放的位置，可把预取分为两种类型： * 寄存器预取：把数据取到寄存器中 * Cache预取：只将数据取到Cache中 在预取数据的同时，处理器应能继续执行，只有这样，预取才有意义。即预取是非阻塞Cache (非锁定Cache) 的 编译器控制预取的**目的：使执行指令和读取数据能重叠执行** 编译器控制预取主要的优化对象是**循环** 编译器控制预取的**重点在于：优化可能会导致不命中的访问，使程序避免不必要的预取**，从而较大程度地减少平均访存时间 ### 4.3.7 编译器优化 ``gcc test.c -O2 -o test`` 常见解决方案： 1. 程序代码与数据重组 2. 数组合并 将本来相互独立的多个数组合并成为一个复合数组，以提高访问它们的局部性 3. 内外循环交换 尽量按数据在主存中存储的顺序进行访问 4. 循环融合 将若干个独立的循环融合为单个的循环 5. 分块 把对数组的整行或整列访问改为按块进行，使一个Cache块被替换前最大限度利用它 ## 4.4 减少Cache不命中开销 ### 4.4.1 采用两级Cache 第一级Cache（L1）小而快 第二级Cache（L2）容量大 类似的策略可以类比前述的Victim Cache，实际的平均访存时间需要考虑两次命中的情况 对于L2 Cache通常有以下结论 1. 在L2 Cache比L1 Cache大得多的情况下，两级Cache的全局不命中率和容量与L2 Cache相同的单级Cache的不命中率非常接近 2. 因此，在评价L2 Cache时，不宜采用局部不命中率，而应当选取全局不命中率 **例题10** 考虑某一两级Cache：第一级Cache为L1，第二级Cache为L2。 1. 假设在1000次访存中，L1的不命中是40次，L2的不命中是20次。求各种局部不命中率和全局不命中率 2. 假设L2的命中时间是10个时钟周期，L2的不命中开销是100时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间是多少个时钟周期？ 解： 1. $L1_{miss}=1-40/1000=4\%$ $L2_{miss}=1-20/40=50\%$ $L12_{miss}=1-20/1000=2\%$ 2. 平均访存时间$=1+4\%\times (10+50\%\times 100)=3.4 c$ 平均停顿时间$=1.5\times 4\%\times (10+50\%\times 100)=1.5\times(3.4-1)=3.6 c$（需要考虑减去命中的影响即可） **在L2 Cache中可以使用更大的容量，并选用更大的块** **例题11** 给出有关第二级Cache的以下数据： 1. 对于直接映象，命中时间L2 ＝ 10个时钟周期 2. 两路组相联使命中时间增加0.1个时钟周期，即为10.1个时钟周期 3. 对于直接映象，局部不命中率L2 ＝ 25% 4. 对于两路组相联，局部不命中率L2 ＝ 20% 5. 不命中开销L2 ＝ 50个时钟周期 试问第二级Cache的相联度对不命中开销的影响如何？ 解： 1. 当直接映像时，L1 Cache的不命中开销为$10+50\times 25\%=22.5$ 2. 当两路组相联是，L1 Cache的不命中开销为$10.1+50\times 20\%=20.1$ 因此两路组相联更优 ### 4.4.2 读失效优先于写策略 问题成因：Cache中的写缓冲器导致对存储器访问变得复杂，即立即读了仍保存在写缓冲器内未得到写入Cache内的数据 解决方案： 1. 推迟对读失效的处理（会导致读失效的开销增大） 2. 额外检查写缓冲器中的内容（主板设计更加复杂） **例题8** 考虑以下指令序列： ``` SW 512(R0),R3; [512]+R3 (Cache索引为0) LW Rl,1024(R0); R1+M[1024] (Cache索引为0) LW R2,512(R0); R2+M[512] (Cache索引为0) ``` 假设Cache采用写直达法和直接映象，并且地址512和1024映射到同一块，写缓冲器为4个字，试问寄存器R2的值总等于R3的值吗？ 解： 对Cache的访问来看 * 在执行STORE指令之后，R3中的数据被放入写缓冲器。 * 第一条LOAD指令使用相同的Cache索引（地址512和1024映射到同一块），因而产生一次失效。 * 第二条LOAD指令欲把地址为512的存储单元的值读入寄存器R2中，这也会造成一次失效。如果此时写缓冲器还未将数据写入存储单元512中，那么第二条让LOAD指令将把错误的旧值读入Cache和寄存器中。 结论：如果不采取适当的预防措施，R2饱的值就不会等于R3的值。 ### 4.4.3 子块放置技术 把Cache块进一步划分为更小的块(子块)，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位 子块放置技术可以使得选取更大的块大小成为可能，而这将可以减少标识的位数。只需要传送子块也可以使得不命中开销更小 ### 4.4.4 请求字处理技术 从下一级存储器调入Cache的块中，**只有一个字是立即需要的**。这个字称为请求字（而以块为单位处理数据是利用的局部性原理，但确实仅仅只有那一个字是立即需要的，可以有效加速） 常见有两个方式： * 尽早重启动 调块时，从块的起始位置开始读起。**一旦请求字到达，就立即发送给CPU，让CPU继续执行** * 请求字优先 调块时，**从请求字所在的位置读起**。这样，第一个读出的字便是请求字。将之立即发送给CPU。同时从存储器调入该块的其余部分 **当Cache块较小或局部性显著时（强空间关联访问）效果不大** ### 4.4.5 非阻塞Cache技术 Cache失效时仍**允许CPU进行其它的命中访问** 需要考察重叠失效个数对平均访问时间的影响 **例题9** 在两路组相联和"允许**一次失效**下命中"这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？ 1. 假设8KB直接映像Cache的平均失效率为： * 对于浮点程序，直接映象Cache为$11.4\%$ * 对于整数程序，直接映象Cache为$7.4\%$ 2. 假设8KB两路组相联Cache的平均失效率为： * 对于浮点程序，两路组相联Cache为$10.7\%$ * 对于整数程序，两路组相联Cache为$6.0\%$ 并给出如下非阻塞Cache平均存储器等待时间与阻塞Cache的比值  并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期 解： 1. 浮点程序中 两路组相联时：存储器等待时间为$10.7\% \times 16=1.712$ 允许一次失效下命中时：存储器等待时间$11.4\% \times 16 \times 76\%=1.38624$ 加速比为$123.5\%$ 2. 整数程序中 两路组相联时：存储器等待时间为$6.0\% \times 16=0.96$ 允许一次失效下命中时：存储器等待时间$7.4\% \times 16 \times 81\%=0.95904$ 加速比为$100.1\%$ 浮点程序中的优化更为显著 ## 4.5 减少命中时间 ### 4.5.1 选择小容量、结构简单的Cache * 硬件越简单，速度就越快 * 应使Cache足够小，以便可与CPU放在同一块芯片上，距离足够近，传输也就越快（距离越短，信号损失越少，可以允许的频率就越高） ### 4.5.2 虚拟Cache 可以直接用虚拟地址进行访问的Cache。标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址 在命中时不需要地址转换，省去了地址转换的时间。即使不命中，地址转换和访问Cache也是并行进行的，其速度比物理Cache快很多  ### 4.5.3 Cache访问流水化 对第一级Cache的访问按流水方式组织 访问Cache需要多个时钟周期才可以完成 ### 4.5.4 踪迹Cache 问题产生：当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的，即流水线难以满载运行 **采用踪迹Cache，用以存放CPU所执行的动态指令序列**，踪迹cache将找到的动态的包括**所有分支的指令**装入一个cache块。这样cache块中包含的就是有CPU决定的执行指令的动态记录，而不是主存局部决定的静态指令序列 ## 4.6 小结 | 优化技术 | 不命中率 | 不命中开销 | 命中时间 | 硬件复杂度 | 说明 | | --------------------------------------------------------- | -------- | ---------- | -------- | ---------- | ---- | | [增加块大小](#431-增加Cache块大小（解决强制不命中）) | + | - | | 0 | | | [增加Cache容量](#431-增加Cache块大小（解决强制不命中）) | + | | | 1 | | | [提高相联度](#432-提高相联度（解决冲突不命中）) | + | | - | 1 | 重点 | | [牺牲Cache](#433-“牺牲”Cache（解决冲突不命中）) | + | | | 2 | 重点 | | [伪相联Cache](#434-伪相联Cache（列相联Cache）) | + | | | 2 | 重点 | | [硬件预取指令](#435-硬件预取) | + | | | 2~3 | | | [编译预取指令](#436-编译器控制的预取) | + | | | 3 | | | [编译优化](#437-编译器优化) | + | | | 0 | | | [读失效优先于写策略](#442-读失效优先于写策略) | | + | - | 1 | | | 写缓冲归并 | | + | | 1 | | | [请求字处理技术](#444-请求字处理技术) | | + | | 2 | | | [非阻塞Cache技术](#445-非阻塞Cache技术) | | + | | 3 | 重点 | | [两级Cache](#441-采用两级Cache) | | + | | 2 | 重点 | | [容量小结构简单的Cache](#451-选择小容量、结构简单的Cache) | - | | + | 0 | | | [虚拟Cache](#452-虚拟Cache) | | | + | 2 | | | [Cache访问流水化](#453-Cache访问流水化) | | | + | 1 | | | [踪迹Cache](#454-踪迹Cache) | | | + | 3 | | ## 4.7 并行主存系统 并行主存系统是在**一个访存周期内能并行访问多个存储字**的存储器，能有效地提高存储器的带宽 * 单体多字存储器 * 多体交叉存储器 * 高位交叉编址 * 低位交叉编址（有效地解决访问冲突问题） ## 4.8 虚拟存储器 虚拟存储器是“主存—辅存”层次进一步发展的结果 虚拟存储器可以分为两类：页式和段式 * 页式虚拟存储器把空间划分为大小相同的块 * 段式虚拟存储器则把空间划分为可变长的块（段） * 页面是对空间的机械划分，而段则往往是按程序的逻辑意义进行划分 * 多数计算机采用段式和页式的结合：段页式 快速地址转换技术 * 地址变换缓冲器TLB # 5 输入输出系统 ## 5.1 引言 计算机处理的任务可分为计算密集型和输入输出密集型两种 输入输出系统的功能是在主机与外设之间进行数据传送以及对外设进行控制操作 ## 5.2 输入输出基本概念 ### 5.2.1 输入输出系统的特点 输入输出系统是**处理机**与外界进行数据交换的通道 * 实时性 * 对于一般输入输出设备,如果处理机提供的服务不及时，可能丢失数据，或造成外围设备工作的错误 * 对策：**层次结构** * 与设备无关性 * 处理机采用统一的硬件和软件对品种繁多的设备进行管理 * 对策：**分类处理** * 异步性 * 输入输出设备通常不使用统一的中央时钟，各个设备按照自己的时钟工作，但又要在某些时刻接受处理机的控制 * 处理机与外围设备之间，外围设备与外围设备之间能并行工作 * 对策：**自治控制** ### 5.2.2 输入输出系统的组织方式 * 层次结构 最内层是**输入输出处理机**、**输入输出通道**等 中间层是**标准接口** 标准接口通过设备控制器与输入输出设备连接  * 分类处理 **面向字符**的设备：如字符终端、打字机等 **面向数据块**的设备：如磁盘、磁带、光盘等 * 自治控制 **输入输出系统是独立于CPU之外的自治系统。处理机与外围设备之间要有恰当的分工** ### 5.2.3 基本输入输出方式 * 程序控制输入输出方式 * 何时对何设备进行IO操作受CPU控制 * CPU要通过指令对设备进行测试才能知道设备的工作状态 * 数据的输入和输出都要经过CPU * 适用于低速外围设备 * 优点：灵活性好，易于扩展，可以轻松改变外围设备优先级 * 缺点：不能实现处理机与外围设备之间的**并行工作** * 中断输入输出方式 * CPU与外围设备能够并行工作 * 能够处理例外事件 * 数据的输入和输出都要经过CPU * 用于连接低速外围设备 * DMA * 主存储器既可以被CPU访问，也可以被外围设备访问。申请排队外围设备的访问申请安排在最高优先级 * 在DMA方式中，CPU不仅能够与外围设备并行工作，而且整个数据的传送过程不需要CPU的干预 * 适用于高速外围设备 * 常见方式： * 周期窃取 * 在每一条指令执行结束时，CPU测试有没有DMA服务申请，并借用CPU完成DMA工作流程 * 周期窃取方式与程序控制输入输出方式和中断输入输出方式的不同处主要在：**它不需要使用程序来完成数据的输入或输出，只是借用了一个CPU的周期来完成DMA流程。** 因此工作速度很快 * 优点：硬件结构简单，容易实现 * 缺点：数据输入或输出过程中**实际上占用了CPU的时间（一个周期）** * 直接存取 * 整个工作流程全部用硬件（而不是CPU）完成 * 优点与缺点正好与周期窃取方式相反 * 数据块传送 * 在设备控制器中设置一个比较大的数据缓冲存储器。设备控制器与主存储器之间的数据交换以数据块为单位，并采用**程序中断方式**进行 * 采用数据块传送方式的外围设备有软盘驱动器、行式打印机、激光打印机、卡片阅读机、绘图仪等 ## <div style="color:red;"> 5.3 通道处理机 </div> ### 5.3.1 通道的作用和功能 现有问题：CPU的输入输出负担很重，需要处理设备数据初始化，传输，前处理，后处理等各种工作，不能专心用于用户程序的计算工作 **因此，引入通道处理机的概念** 通道的主要功能： 1. 接受CPU发来的指令，选择一台指定的外围设备与通道相连接 2. 执行CPU为通道组织的通道程序 3. 管理外围设备的有关地址 4. 管理主存缓冲区的地址 5. 控制外围设备与主存缓冲区之间数据交换的个数 6. 指定传送工作结束时要进行的操作 7. 检查外围设备的工作状态，是正常或故障 8. 在数据传输过程中完成必要的格式变换 ### 5.3.2 通道的工作过程 1. 在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道 2. 通道处理机执行通道程序，完成指定的数据输入输出工作 3. 通道程序结束后再次调用管理程序进行处理  ### 5.3.3 通道的种类 1. 字节多路通道 为**多台低中速**的外围设备服务  **每次为一台设备传输一个字节的数据**  $T_S$：设备选择时间；$T_D$：为一台设备传输一个字节的时间；$P$：设备数；$n$：一台设备传输的字节数 $T_{BYTE}=(T_S+T_D)\cdot P\cdot n$ 2. 选择多路通道 为**高速**外围设备服务  **每次选择一台设备并全部传输完毕**  $T_S$：设备选择时间；$T_D$：为一台设备传输一个字节的时间；$P$：设备数；$n$：一台设备传输的字节数 $T_{SELECT}=T_S\cdot P+T_D\cdot P\cdot n$ 与字节多路相比**节约了频繁切换设备的时间**，但也就限制了其只能应用于高速设备，如果用于低中速设备就会出现响通道被一个设备所占用而响应不及时的情况 3. 数组多路通道 是字节多路通道与选择多路通道综合产物 **每次为一台高速设备传送一个数据块，并轮流为多台外围设备服务**（在为一台高速设备传送数据的同时，有多台高速设备可以在**定位或者在找扇区**）  $T_S$：设备选择时间；$T_D$：为一台设备传输一个字节的时间；$P$：设备数；$n$：一台设备传输的字节数 $\begin{align}T_{BLOCK}=\frac{T_S\cdot P \cdot n}{k}+T_D\cdot P\cdot n\end{align}$ 选择多路通道是$k=n$时的特殊情况，数组多路可以综合传输快速与及时响应的优点 ### 5.3.4 通道流量分析 通道流量：**单位时间内能够传送的最大数据量**。又称通道吞吐率，通道数据传输率等 通道最大流量：通道在满负荷工作状态下的流量 $\begin{align} f_{BYTE}=\sum_{i=1}^{p} f_i \quad f_{S E L E T E}=\operatorname{Max}_{i=1}^{p} f_i \quad f_{B L O C K}=\operatorname{Max}_{i=1}^{p} f_i \end{align}$ $\begin{align}f_{MAX-BYTE}=\frac{p\cdot n}{T_{BYTE}}=\frac{1}{T_S+T_D}\end{align}$ $\begin{align}f_{MAX-SELECT}=\frac{p\cdot n}{T_{SELECT}}=\frac{1}{T_S/n+T_D}\end{align}$ $\begin{align}f_{MAX-BLOCK}=\frac{p\cdot n}{T_{BLOCK}}=\frac{1}{T_S/k+T_D}\end{align}$ **为保证通道不丢失数据，通道的实际流量应不大于通道最大流量** **例题1** 一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10us、30us、30us、50us和75us发出一次数据传送请求 1. 计算这个通道的实际流量和工作周期 2. 如果这个字节多路通道的最大流量正好等于通道实际流量，并假设数据传输率高的设备，其优先级也高。5台设备在0时刻同时向通道发出第一次传送数据的请求，并在以后的时间里按照各自的数据传输率连续工作。画出通道分时为各台设备服务的时间图，并计算处理完各设备的第一次请求的时刻 3. 从时间图中发现什么问题？如何解决？ 解： 1. $f_{BYTE}=\sum_{i=1}^{5}f_{D_i}=1/(10\times 10^{-6})+...=200000B/s$ 工作周期为$1/f_{BYTE}=5\mu s$ 2. 可以发现其D5设备的第一次请求没有得到及时处理，其第二次请求已经到来。此时第一次请求被丢失  3. **增加通道的最大工作流量** **动态改变设备的优先级** **增加缓冲存储器** **例题3** 一个字节多路通道连接有5台设备，它们的数据传输率如下表：  1. 计算这个字节多路通道的实际工作流量 2. 为了使通道能够正常工作，请设计通道的最大流量和工作周期 3. 当这个字节多路通道工作在最大流量时，各台设备都在0时刻同时向通道发出第一次传送数据的请求，并在以后的时间里按照各自的数据传输速率连续工作。画出通道分时为各台设备服务的时间关系图，并计算这个字节多路通道处理完各台设备的第一次数据服务请求的时刻 解： 1. $f_{BYTE}=\sum_{i=1}^{5}f_{D_i}=196.6KB/s$ 2. $f_{MAX-BYTE}\geq f_{BYTE}$，于是设$f_{MAX-BYTE}=200KB/s$，则其工作周期为$5\mu s$ 3. 分别为$5\mu s$、$10\mu s$、$20\mu s$、$30\mu s$、$90\mu s$。见图  **例题4** 一个字节多路通道连接有4台外围设备，每台设备发出输入输出服务请求的时间间隔、它们的服务优先级和发出第一次服务请求的时刻如下表:  1. 计算这个字节多路通道的实际流量和工作周期 2. 在数据传送期间，如果通道选择一次设备的时间为3微秒，传送一个字节的时间为2微秒，画出这个字节多路通道响应各设备请求和为设备服务的时间关系图 3. 从（2）的时间关系图中，计算通道处理完成各设备第一次服务请求的时刻。 4. 从（2）画出的时间关系图中看，这个字节多路通道能否正常工作（不丢失数据）？为什么？ 5. 在设计一个字节多路通道的工作流量时，可以采用哪些措施来保证通道能够正常工作（不丢失数据）？ 解： 1. $f_{D_1}=1/(10\times 10^{-6})=100KB/s$ $f_{D_2}=1/(75\times 10^{-6})=13.33KB/s$ $f_{D_3}=1/(15\times 10^{-6})=66.67KB/s$ $f_{D_4}=1/(50\times 10^{-6})=20KB/s$ $f_{BYTE}=\sum D_i=200KB/s$，其工作周期为$5\mu s$ 2. $5\mu s$不变，见图 **（DEV2的第一次请求丢失）**  3. 分别为$5\mu s$、$160\mu s$、$20\mu s$、$40\mu s$ 4. 并不能，因为DEV2的第一次请求因为优先级关系而被丢失 5. **增加通道的最大工作流量** **动态改变设备的优先级** **增加缓冲存储器** ## 5.4 输入输出处理机 ### 5.4.1 输入输出处理机的作用 现有问题： * 虽然通道处理机相比直接处理已经大幅简化了CPU的任务，但**每完成一次输入输出操作都需要在首尾两次中断CPU的现行程序** * 通道处理机不能处理自身及输入输出设备的故障 * 数据格式转换、码制转换、数据块检验等工作要CPU完成 * 文件管理、设备管理等工作，通道处理机本身无能为力 **因此，引入输入输出处理机的概念**，进一步分离IO与处理的任务。除了具有数据的输入输出功能之外，还具有运算功能和程序控制等功能，就像一般的处理机那样  ### 5.4.2 输入输出处理机的种类 输入输出处理机的多种组织方式： 1. 多个输入输出处理机从功能上分工 2. 以输入输出处理机作为主处理机 3. 采用与主处理机相同型号的处理机作为输入输出处理机 4. 采用廉价的微处理机来专门承担输入输出任务 # 6 多处理机系统 > 并行性的概念 计算机系统**在同一时刻或者同一时间间隔内**进行多种运算或操作 同时性：两个或两个以上的事件在**同一时刻**发生 并发性：两个或两个以上的事件在**同一时间间隔内**发生 * 从数据处理的角度 * 字串位串 * 字串位并 * 字并位串 * 字并位并 * 从执行程序的角度来看 * 指令内部并行（内部微操作并行） * 指令级并行 * 线程级并行 * 任务级或过程级并行 * 作业或程序级并行 提高并行性的技术途径 1. 时间重叠 引入时间因素，让多个处理过程在时间上相互错开，**轮流重叠地使用同一套硬件设备的各个部分**，以加快硬件周转而赢得速度 2. 资源重复 引入空间因素，以数量取胜。**通过重复设置硬件资源**，大幅度地提高计算机系统的性能 3. 资源共享 使多个任务按一定时间顺序轮流使用同一套硬件设备。经典应用：**分时系统** ## <div style="color:red;"> 6.1 引言 </div> ### 6.1.1 并行计算机系统结构的分类 Flynn分类法 按照指令流和数据流的多倍性进行分类 * 指令流：极速那几执行的指令序列 * 数据流：由指令流掉用的数据序列 * 多倍性：在系统最受限的部件上，同时处于同一执行阶段的指令或数据的最大数目 * 分为了4类（单/多 -> 指令流/数据流） * SISD * SIMD * MISD * MIMD 根据系统中处理器个数的多少，可把现有的MIMD计算机分为两类： * 集中式共享存储器结构 * 最多由几十个处理器构成 * 通过大容量的Cache和总线互连使各处理器共享一个单独的物理存储器 * 分布式存储器结构 * 系统由各个节点组成，每个节点都包含独立的： * 处理器 * 存储器 * I/O * 互连网络接口  * 优点 * 如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求 * 对**局部存储器的访问延迟小** * 缺点 * 处理器之间的通信较为复杂，且**各处理器之间访问延迟较大** * 发展 引入簇（超级节点）的概念 * 每个结点内包含**个数较少（例如2～8）的处理器** * 处理器之间可采用另一种互连技术（例如总线）相互连接形成簇 * 充分利用局部性原理，减少跨节点的信息交互，减少因I/O导致的等待 ### 6.1.2 存储器系统结构和通信机制 * 地址空间的组织方案 * 共享地址空间 * 一致存储器访问结构（UMA：Uniform Memory Access） * 多个处理机共用一块存储空间，编址也是固定的 * 效率高，操作简单，但可伸缩性较差，扩容有限 * 非一致存储访问结构（NUMA：Non-Uniform Memory Access） * 物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址，处理器之间通过互联网络进行数据交互 * 这类机器的结构也被称为：分布式共享存储器结构（DSM: Distributed Shared-Memory） * 独立地址空间 * 把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的 * 每个结点中的存储器只能由本地的处理器进行访问，远程的处理器不能直接对其进行访问 * **每一个处理器-存储器模块（节点）实际上是一台单独的计算机** * 通信机制 * 共享存储器通信机制 * 由共享地址空间的计算机系统采用 * 处理器之间是通过用load和store指令对相同存储器地址（统一编址）进行读/写操作来实现的 * 优点 * 与常用的对称式多处理机使用的通信机制**兼容** * **易于编程**，同时在简化编译器设计方面也占有优势 * 当通信数据量较小时，通信开销较低，带宽利用较好 * 可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突 * 消息传递通信机制 * 由多个独立地址空间的计算机采用 * 处理器之间是通过发送消息来进行通信，这些消息请求进行某些操作或者传送数据 * 远程过程调用（RPC）：目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回 * 同步消息传递Await 请求处理器发送一个消息后一直要等到应答结果才继续运行 * 异步消息传递Async 发送方不经请求就直接把数据送往数据接收方 * 优点 * **硬件较简单** * 通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少，以便编程者和编译程序设法减少通信开销 * 相互转化 * 在共享存储器上支持消息传递相对简单 * 在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供**地址转换和存储保护功能**，即将存储器访问转换为消息的发送和接收 ### 6.1.3 并行处理面临的挑战 回忆Amdahl定律 加速比=总执行时间（前）/总执行时间（后） $\begin{align}S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}\end{align}$ * **程序中的并行性有限** 有限的并行性使计算机要达到很高的加速比十分困难 **例题1** 假设如果要用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例 $\begin{align}80=\frac{1}{(1-F_e)+\frac{F_e}{100}}\end{align}$ $F_e=0.9975$，并行部分的比例要高达$99.75\%$，即串行部分的比例不能超过$0.25\%$ 然而事实上程序中的串行部分会占据相当的比重，100个处理器也不太可能实现理论上100的加速比，因为会有通信与调度开销。因此**有限的并行性使计算机要达到很高的加速比十分困难** 解决：采用并行性更好的算法 * **相对较大的通信开销** 多处理机中远程访问的延迟较大，在现有的计算机中，处理器之间的数据通信大约需要100～1000个时钟周期 **例题2** 假设有一台32个处理器的多处理机，对远程存储器访问时间为400 ns。除了通信以外，假设所有其他访问**均命中局部存储器**。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为1 GHz，如果指令基本的IPC为2（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后者快多少? 无远程访问的情况下$CPI=1/IPC=1/2=0.5$ 在有远程访问的情况下$CPI=0.5+0.2\% \times 4\times 10^{-7} \times 1 \times 10^{9}=1.3$ 前者比后者快了**2.6倍** 解决：靠系统结构支持和编程技术 * 在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：**应用程序的高层特性**（good code or bad code）。如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等... * **并行程序的计算/通信比率** 是反映并行程序性能的一个重要的度量 计算/通信比率随着**处理数据规模的增大而增加**；随着**处理器数目的增加而降低** ## 6.2 对称式共享存储器系统结构 多个处理器共享一个存储器 支持对共享数据和私有数据的Cache缓存 * 私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用 共享数据进入Cache产生了一个新的问题：**Cache的一致性问题** ### 6.2.1 多处理机Cache一致性 允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致 如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是**一致**的 处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但**必须以程序规定的顺序进行写** ### 6.2.2 实现一致性的基本方案 Cache一致性协议 * 在多个处理器中用来维护一致性的协议 * 关键：跟踪记录共享数据块的状态 * 两类协议 * 目录式协议 物理存储器中数据块的共享状态被保存在一个称为**目录**的地方 * 监听式协议（小规模并行机通常使用） 每个Cache除了包含物理存储器中块的数据拷贝之外，也**保存着各个块的共享状态信息** Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作（使用最新的数据副本） 采用两种方法来解决Cache一致性问题 * 写作废协议 在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权（即写入之前作废其他任何数据副本） * 写更新协议 当一个处理器对某数据项进行写入时，通过广播使其它Cache中所有对应于该数据项的副本进行更新 * 二者区别 写作废协议实现简单，操作便捷。连续写入时只需要一次作废操作，而写更新则需要每一次广播 写作废针对Cache块（粗粒度），写更新则针对字节（细粒度） 写作废协议导致了所有数据副本只有一个有效块，因此写入后的读取操作延迟较大，而写更新则实时更新到每一个Cache中，写入后的读取操作延迟较小 ### 6.2.3 监听协议的实现 小规模多处理机中实现写作废协议的**关键是利用总线进行作废操作** 对于写直达Cache，因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值 对于写回Cache，数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中 每个Cache块加一个特殊的**状态位**来说明它是否为共享。拥有唯一Cache块拷贝的处理器通常称为这个Cache块的拥有者（Owner)，处理器的写操作使自己成为对应Cache块的拥有者。当对共享块进行写时，本Cache将写作废的请求放在总线上，Cache块状态由共享（shared）变为非共享（unshared）或者专有（exclusive）  ## 6.3 分布式共享存储器系统结构 这些系统都有Cache，为了解决一致性问题，规定共享数据不进入Cache，仅私有数据才能保存在Cache中 ### 6.3.1 基于目录的Cache一致性 目录：一种专用的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息 位向量：记录哪些Cache中有副本，每一位对应于一个处理器，长度与处理器的个数成正比，由位向量指定的处理机的集合称为共享集S 在目录协议中，存储块的状态有3种： * 未缓冲：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本 * 共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同 * 独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时（这个处理机称为该块的拥有者）  ### 6.3.2 目录的三种结构 * 全映象目录 * 每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应于一个处理机  * 优点：处理比较简单，速度也比较快 * 缺点：存储空间的开销很大$O(n^2)$，可扩放性差 * 有限映象目录 * 提高其可扩放性和减少目录所占用的空间 * 核心思想：采用位数固定的目录项  * 链式目录 * 用一个目录指针链表来表示共享集合。当一个数据块的副本数增加（或减少）时，其指针链表就跟着变长（或变短） * 优点：既不限制副本的个数，又保持了可扩放性 ## 6.4 互连网络 ## 6.5 并行化技术