【计算机组成原理】计算机系统结构笔记（5）：标量处理机

200802本篇是郑纬民《计算机系统结构》的读书笔记，欢迎各位路过指正！今天是第五章：标量处理机。

5. 标量处理机

5.1 先行控制技术

• 指令的重叠执行方式：

  • 顺序执行方式：用时$T=\sum_{i=1}^n(t_{ti}+t_{ai}+t_{ei})$T=∑i=1n​(tti​+tai​+tei​)，其中$t_{ti}$tti​为取指时间，$t_{ai}$tai​为分析时间，$t_{ei}$tei​为执行时间。
  • 一次重叠执行方式：如果两个过程的时间相等，则执行$n$n条指令的时间为：$T=(1+2n)t$T=(1+2n)t。
  • 二次重叠执行方式：如果三个过程的时间相等，执行$n$n条指令的时间为：$T=(2+n)t$T=(2+n)t。需要采用先行控制技术。

• 先行控制方式的原理：解决两个问题：(1).有独立的取指令部件、指令分析部件和指令执行部件，把一个控制器分解为存储控制器、指令控制器、运算控制器；(2).要解决访问主存储器的冲突问题：采用低位交叉存取方式或两个独立的存储器、独立的指令存储器和数据存储器、采用先行控制技术（缓冲技术和预处理技术）

• 有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。

• 处理机结构：

  • 三个独立的控制器：存储控制器、指令控制器、运算控制器。
  • 四个缓冲栈：先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈。

• 先行指令缓冲栈：处于主存储器与指令分析器之间。平滑主存储器取指令和指令分析器使用指令之间的速度差异。

  • RR型指令：不必处理，直接送先行缓冲栈；
  • RS型指令，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行缓冲栈；
  • RI型指令，指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈。
  • 转移指令，一般在指令分析器中直接执行。
  • 先行指令缓冲栈的组成：只要指令缓冲栈没有充满，就自动发出取指令的请求。先行程序计数器PC1，用来指示取指令，现行程序计数器PC，记录指令分析器正在分析的指令地址。但是是分析和执行时间相差大，且有数据相关问题。
  • 指令执行时序：设置了指令缓冲栈，取指令的时间就可以忽略不计。
  • 理想情况下，指令执行部件应该一直忙碌。连续执行n条指令的时间为：$T_{先行} = \sum_{i=1}^n t_{ei}$T先行​=∑i=1n​tei​。
  • 设置先行缓冲栈的目的：使指令分析器和指令执行部件能够独立工作。

• 先行操作栈：处于指令分析器和运算控制器之间使指令分析器和运算器能够各自独立工作。

• 先行读数栈：处于主存储器与运算器之间滑运算器与主存储器的工作。由地址寄存器、操作数寄存器、和标志三部分组成。

• 后行写数栈：由地址寄存器、数据寄存器和标志三部分组成。当运算器执行这条RR*型写数指令时，只要把写到主存的数据送到后行写数栈的数据寄存器中即可。

• 缓冲深度的设计方法：以静态分析为主，通过模拟来确定缓冲深度。

• 先行指令缓冲栈的设计：

  • 先行指令缓冲栈已经充满：则缓冲深度为$D_I = \lceil \frac{L_1(t_2-t_1)}{t_2}\rceil$DI​=⌈t2​L1​(t2​−t1​)​⌉，其中$L_1$L1​为指令序列最大长度，平均分析时间为$t_1$t1​，平均取一条指令 的时间为$t_2$t2​。如果这种指令流的连续长度超过$L_1$L1​，则先行指令缓冲栈失去作用。
  • 若先行指令缓冲栈原来为空：缓冲深度为：$D_{I}=\lceil\frac{L_{2} \cdot\left(t_{1}^{\prime}-t_{2}^{\prime}\right)}{t_{1}^{\prime}}\rceil$DI​=⌈t1′​L2​⋅(t1′​−t2′​)​⌉指令流的连续长度超过L2，先行指令缓冲栈失去缓冲作用。
  • 在一般处理机中连续执行短指令的概率大。
  • 其余缓冲栈的设计原则：先行指令缓冲栈的缓冲深度>先行操作栈的缓冲深度，>先行读数栈的缓冲深度，>后行写数栈的缓冲深度。

5.2 流水线技术

• 空间并行性：设置多个独立的操作部件；

• 时间并行性：分时使用同一个部件的不同部分。

• 流水线工作原理：在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器。加入流水寄存器，会增加指令的执行时间。

• 指令流水线一般4至12个流水段，≥8个流水段的称为超流水线处理机。

• 特点：只有连续提供同类任务才能发挥流水线效率、每个流水线段都要设置一个流水寄存器、各流水段的时间应尽量相等、流水线需要有装入时间和排空时间。

• 流水线的分类：

  • 流水线的各个流水段之间是否有反馈信号：线性流水线、非线性流水线。
  • 按照流水线的级别来分：处理机级流水线（指令流水线）、部件级流水线（操作流水线）、 宏流水线（处理机之间的流水线）。
  • 单功能流水线与多功能流水线：单功能流水线（只能完成一种固定功能的流水线）、多功能流水线（流水线的各段通过不同连接实现不同功能）。
  • 静态流水线与动态流水线：静态流水线：同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能。动态流水线：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。
  • 按照数据表示方式：标量流水线和向量流水线。
  • 按照控制方式：同步流水线和异步流水线。

• 流水线的性能分析：

  • 吞吐率$TP=\frac{n}{T_k}$TP=Tk​n​。各段时间不等，完成n个连续任务：吞吐率$TP=\frac{n}{\sum_{i=1}^kt_i + (n-1)\max (\Delta t_1,\Delta t_2,...,\Delta t_k)}$TP=∑i=1k​ti​+(n−1)max(Δt1​,Δt2​,...,Δtk​)n​。最大吞吐率为$TP=\frac{1}{\max (\Delta t_1,\Delta t_2,...,\Delta t_k)}$TP=max(Δt1​,Δt2​,...,Δtk​)1​。
  • 流水线各段执行时间不相等的解决办法：将瓶颈部分再细分、瓶颈流水重复设置：增加分配器和收集器。
  • 加速比$S= \frac{顺序执行时间T_0}{流水线执行时间T_k}=\frac{nk}{n+k-1}$S=流水线执行时间Tk​顺序执行时间T0​​=n+k−1nk​。最大加速比$S_{max} = k$Smax​=k。实际加速比$S=\frac{n\sum_{i=1}^k\Delta t_i}{\sum_{i=1}^kt_i + (n-1)\max (\Delta t_1,\Delta t_2,...,\Delta t_k)}$S=∑i=1k​ti​+(n−1)max(Δt1​,Δt2​,...,Δtk​)n∑i=1k​Δti​​
  • 效率$E=\frac{n个任务占用的时空区}{k个流水总的时空区}= \frac{T_0}{kT_k}$E=k个流水总的时空区n个任务占用的时空区​=kTk​T0​​。则$E=\frac{n}{k+n-1}$E=k+n−1n​，最高效率为1。实际效率为$E=\frac{n\sum_{i=1}^k\Delta t_i}{K[\sum_{i=1}^kt_i + (n-1)\max (\Delta t_1,\Delta t_2,...,\Delta t_k)]}$E=K[∑i=1k​ti​+(n−1)max(Δt1​,Δt2​,...,Δtk​)]n∑i=1k​Δti​​。各段设备量或价格不等时，流水线的效率为：$E=\frac{n\sum_{i=1}^ka_i\Delta t_i}{\sum_{I=1}^{i=k}a_i[\sum_{i=1}^ka_it_i + (n-1)\max (\Delta t_1,\Delta t_2,...,\Delta t_k)]}$E=∑I=1i=k​ai​[∑i=1k​ai​ti​+(n−1)max(Δt1​,Δt2​,...,Δtk​)]n∑i=1k​ai​Δti​​。
  • 流水线的吞吐率、加速比与效率的关系：$E = TP\cdot \Delta t, S=kE$E=TP⋅Δt,S=kE。
  • 流水线最佳段数的选择：性能价格比（PCR）定义为：$PCR = \frac{P}{C} = \frac{1}{t/k+d}\frac{1}{a+bk}$PCR=CP​=t/k+d1​a+bk1​。求其最大值则$k_0 = \sqrt{\frac{ta}{db}}$k0​=dbta​​。其中a为功能段身的总价格，b为每个锁存器的价格，d为流水锁存器的延迟时间，k为流水线段数。

• 非线性流水线的调度：找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各
  个功能段都不会发生冲突。

• 非线性流水线的冲突

  • 启动距离：连续输入两个任务之间的时间间隔。
  • 流水线冲突：几个任务争用同一个流水段。

• 无冲突调度方法（Davsion，1971）

  • 禁止向量：预约表中每一行任意两个“×”之间距离的集合。
  • 冲突向量：$C＝(C_mC_{m-1}…C_2C_1)$C＝(Cm​Cm−1​…C2​C1​)。 其中：m是禁止向量中的最大值。如果i在禁止向量中，则$C_i＝1$Ci​＝1，否则$C_i＝0$Ci​＝0。
  • 简单循环：状态图中各种冲突向量只经过一次的启动循环。

• 优化调度方法（Shar，1972）流水线最小平均启动距离的限制范围：预约表中“×”最多的行一定是瓶颈流水段。实现最优调度的目标是使瓶颈流水段处于忙碌状态，没有空闲周期。

5.3 相关性分析技术

• 数据相关：在执行本条指令的过程中用到的指令、操作数、变址量等是前面指令的执行结果。

• 控制相关：由条件分支指令、转子程序指令、中断等引起的相关。

• 处理方法：推后处理、设置专用路径。

• 指令相关：结果地址(n)＝指令地址(n+1)。解决指令相关的根本办法是： 在程序执行过程中不允许修改指令。

• 主存操作数相关：A1（n）＝ A2（n＋1）。解决办法：运算结果写到通用寄存器（写回），而不写到主存（写通）。对于访问主存储器的请求，写结果的优先级高于读操作数。

• 通用寄存器数据相关：

  • 发生R1(n)＝R1(n＋1)称为R1数据相关。
  • 发生R1(n)＝R2(n＋1)称为R2数据相关。
  • 方法一：把读操作数、写运算结果与指令执行合在一个节拍。
  • 方法二：建立相关专用通路。

• LOAD相关：R1(n)＝R2(n＋1)，或 R1(n)＝R1(n＋1)，

  • 方法一：由编译器在LOAD之后插入不发生数据相关的指令。
  • 方法二：由硬件自动插入空操作，直到LOAD操作完成。

• 控制相关：因程序的执行方向可能被改变而引起的相关。处理方法：在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器。

• 一般条件转移：当条件码是上一条指令产生时，相关最严重。当转移成功时，指令执行过程完全串
  行，而且要作废先行指令缓冲栈中的指令。在采用流水线方式的处理机中，通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。

• 复合条件转移：转移成功造成的影响比一般条件转移指令还要大。

• 条件分支对流水线的影响：(1)延迟转移技术和指令取消技术（单流水线处理机）(2)动态分支预测技术（根据近期转移是否成功的记录来预测下一次转移的方向）、静态分支预测技术（在程序实际执行过程中，转移预测的方向不能改变）。

  • 条件分支在流水线中的执行过程：转移成功，猜测错误，要先作废流水线中已经执行的指令；然后再从分支点开始执行指令。一条k段流水线有k-2个功能段是浪费的。当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。
  • 目前的处理机有两种做法：（1）只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；（2）一直执行到运算完成，但不送回运算结果。
  • 条件分支对流水线性能的影响：假设条件转移指令在一般程序中所占的比例为$p$p，转移成功的概率为$q$q。n条指令的总的执行时间是： $T_{K-IF}＝(n+k-1)\Delta t + npq(k-1)\Delta t$TK−IF​＝(n+k−1)Δt+npq(k−1)Δt。有条件转移影响的流水线最大吞吐率为：$TP_{MAX-IF} = \frac{1}{(1+pq(k-1))\Delta t}$TPMAX−IF​=(1+pq(k−1))Δt1​。流水线吞吐率下降的百分比为$D=\frac{pq(k-1)}{1+pq(k-1)}$D=1+pq(k−1)pq(k−1)​。

• 静态分支预测技术：

  • 软件法：通过编译器尽量降低转移成功的概率。
  • 硬件法：通过改变硬件结构来降低转移指令对流水线的影响。
  • 两个先行指令缓冲栈向前条件转移，转移成功与不成功各50%在先行指令缓冲栈中增加一个先行目标缓冲栈。

• 动态分支预测技术：

  • 在指令Cache中记录转移历史信息：加一个字段称为转移历史表。
  • 设置转移目标地址缓冲栈：用高速缓冲栈保存最近k条转移指令的转移历史表和转移目标地址。
  • 设置转移目标指令缓冲栈：字段改为存放转移目标地址之后的n条指令。

• 提前形成条件码：可在运算开始或中间产生条件码。

• 精确断点与不精确断点：对于输入输出设备的中断服务不需要有精确断点。使用不精确断点则流水线可以不断流。但是程序的调试困难、程序执行的结果可能出错。要设置一定数量的后援寄存器。

5.4 动态调度技术

• 顺序流动：任务按顺序流入流水线，也按顺序流出流水线。

• 乱序流动：指令流出流水线的顺序与流入流水线的顺序不同。

• 乱序流动中的数据相关：RAW相关、WAR相关、WAW相关。相关称为冒险、竟争等。

• 数据重定向：

  • 写读相关，j与i可以同时执行即专用数据通路；
  • 写写相关，先后顺序无关；
  • 读写相关，先后顺序无关；
  • 后两种情况又称为变量换名技术。

• 变量换名技术：用来自动消除读写数据相关和写写数据相关。规则：一个变量只允许定值一次。

• 动态调度算法：

  • 集中控制：CDC计分牌算法；
    -** 分散控制**：Tomasulo算法, 公共数据总线法，令牌法等。

5.5 超标量处理机

• 普通标量流水线处理机：一条指令流水线，一个多功能操作部件。

• 多操作部件标量处理机：一条指令流水线，多个独立的操作部件。

• 超标量处理机典型结构：多条并行工作的指令流水线，多个独立的操作部件，指令级并行度（ILP）大于1。

• 单发射处理机：每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果。取指令部件和指令译码部件各设置一套。

• 多发射处理机：每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。多个取指令部件，多个指令译码部件和多个写结果部件。设置多个指令执行部件。

• 超标量处理机：有两条或两条以上能同时工作的指令流水线

• 先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。指令并行度1<ILP<m。

• 多流水线的调度的方法：顺序发射顺序完成、顺序发射乱序完成、乱序发射乱序完成。

• 顺序发射与乱序发射：指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射。

• 顺序完成与乱序完成：指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成。

• 资源冲突：如果不采用流水线结构，发生资源冲突的可能性就比较大。因此，在超标量处理机中，操作部件一般要采用流水线结构。超标量处理机则正好相反，相同操作不要连续出现。

• 超标量处理机性能：而超标量超流水线处理机的指令级并行度记作(m, n)。在理想情况下，N条指令在单流水线标量处理机上的执行时间为：$T(1,1)=(k+N-1)\Delta t$T(1,1)=(k+N−1)Δt。在每个周期发射m条指令的超标量处理机上执行的时间为：$T(m,1) = (k+\frac{N-m}{m})\Delta t$T(m,1)=(k+mN−m​)Δt。超标量处理机相对于单流水线标量处理机的加速比为：$S(m,1) = \frac{T(1,1)}{T(m,1)} = \frac{m(k+N-1)}{N+m(k-1)}$S(m,1)=T(m,1)T(1,1)​=N+m(k−1)m(k+N−1)​。超标量处理机的加速比的最大值为：$S(m,1)_{MAX}=m$S(m,1)MAX​=m。

5.6 超流水线处理机

• 超流水线处理机的两种定义：在一个周期内分时发射多条指令的处理机或指令流水线的段数大于等于8的流水线处理机。
• 提高处理机性能的两种方法：增加硬件资源、各部分硬件的重叠工作。
• 两种不同并行性：超标量处理机采用的是空间并行性；超流水线处理机采用的是时间并行性。
• 指令执行时序：每隔1/n个时钟周期发射一条指令。
• 超流水线处理机性能：指令级并行度为(1,n)的超流水线处理机，执行N条指令所的时间为$T(1,n) = (k + \frac{N-1}{n})\Delta t$T(1,n)=(k+nN−1​)Δt。超流水线处理机相对于单流水线普通标量处理机的加速比为：$S(1,n) = \frac{n(k+N-1)}{nk+N-1}$S(1,n)=nk+N−1n(k+N−1)​，最大的加速比为$S(1,n)_{MAX} = n$S(1,n)MAX​=n。

5.7 超标量超流水线处理机

• 一个时钟周期发射m次，每次发射n条指令。

• 指令级并行度为(m,n)的超标量超流水线处理机，连续执行N条指令所需要的时间为：$T(m,n) = (k + \frac{N-m}{mn})\Delta t$T(m,n)=(k+mnN−m​)Δt。加速比为$S(m,n) = \frac{mn(k+N-1)}{mnk+N-m}$S(m,n)=mnk+N−mmn(k+N−1)​，最大加速比为$S(m,n)_{MAX} = mn$S(m,n)MAX​=mn。

• 三种标量处理机的性能比较

• 超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低。 原因：超标量处理机功能部件的冲突比超流水线处理机小。条件转移等操作造成的损失，超流水线处理机要比超标量处理机大。超流水线处理机的启动延迟通常要比超标量处理机大。
• 实际指令级并行度与理论指令级并行度的关系：当理论指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。 目前，一般认为，m 和 n 都不要超过 4。
• 最大指令级并行度：由程序自身的语义决定。