仅供参考~

看到了，没记住是最悲剧的……

第一章 基础知识

系统结构的相关概念

计算机系统的层次结构概念

由硬件、软件和固件（被固化在ROM中的微程序）组成的复杂系统。 按语言功能（非组成）划分成多级层次结构:

  • 硬件层(物理机):如果问几层的话还是去除L0硬件层
    • 第0层：硬件
    • 第1层：微程序（固件） 由微程序控制实现，逻辑程序员用微指令集编写，微程序由固件／硬件来解释。
    • 第2层：机器语言机器(软硬件界面) 机器语言是指令系统，程序通过中央处理机由L1级微程序或L0级硬联逻辑进行解释
  • 虚拟机:
    • 第3层：操作系统机器 运行在L2级的操作系统级解释程序。 包括传统的机器指令(如算术、逻辑运算)及操作系统级指令(打开、关闭文件、读/写文件等) 与L2级指令相同由微程序解释
    • 第4层：汇编语言机器 汇编语言程序，负责将上级语言翻译成L2和L3级语言，再由机器执行。完成汇编语言翻译的程序称为汇编程序
    • 第5层：高级语言机器 语言：如C、C++、FORTRAN等。高级语言程序一般由称为编译程序的翻译到L4或L3级上。个别高级语言程序如Python等,采用解释方法实现，即用解释程序翻译到L4或L3级。
    • 第6层：应用语言机器 语言：为满足某种用途而专门设计的面向问题的应用语言（使用超级计算机时优化用的语言吧)，由应用程序包翻译到L5级上
广义机器、虚拟机器、透明性、编译、解释
  • 广义机器: 执行和存储程序的算法和数据结构的集合体
  • 虚拟机器: 由软件实现的机器
  • 透明性: 在计算机技术中，一种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。通常底层机器的属性对于高层机器程序员来说是透明的。
  • 编译: 转换程序将高一级机器上程序转换为低一级机器上的等效程序，然后在低一级机器上运行，实现程序的功能。
  • 解释: 把高一级机器上的每一条语句，转换为低级机器上的一段等效程序并执行。执行完后，去高一级机器再取下一条语句或指令执行，如此反复，直到解释执行完整个程序。
计算机系统结构、组织和实现
  • 计算机系统结构: 计算机系统的软、硬件的界面
  • 计算机组成: 计算机系统结构的逻辑实现
  • 计算机实现: 计算机组成的物理实现 具有相同系统结构的计算机可以采用不同的物理组成。 同一种物理组成又可以采用不同的计算机实现。
计算机系统分类方法

Flynn 分类法 按指令流和数据流的组织方式分类 * 单指令流单数据流（SISD）计算机系统：传统顺序处理计算机 * 单指令流多数据流（SIMD）计算机系统：阵列处理机 * 多指令流单数据流（MISD）计算机系统：未定 * 多指令流多数据流（MIMD）计算机系统：多处理机

系统分析技术

大概率事件优先原理

优先加速使用频率高的部件

此原理适用于资源分配、减灾防灾等

Amdahl定律、加速比定义

Amdahl定律可计算因改进某些部件而获得的系统性能的加速比, 也可用来确定系统中对性能限制最大的部件

程序访存的局部性原理

程序执行时所访问的存储器地址分布不是随机的

常用经验规则: 程序执行时间的90%都是在执行程序中10%的代码

可以根据程序最近的访问情况来比较准确地预测将要访问的指令和数据。凡是涉及数据重用的地方都可能会用到它。

CPU性能公式
CPU时间

\[ CPU_{时间} = 执行程序所需的时钟周期数 \times 时钟周期时间 \]

时钟周期时间t(ns)是系统时钟频率的倒数

每条指令执行的平均时钟周期数CPI

\[CPI = \frac{执行程序所需的时钟周期数}{IC}\] IC：所执行的指令条数

则CPU时间可以写成下式 \[CPU时间 = IC ×CPI ×时钟周期时间 \]

性能评价标准

  • 性能指标（CPU时间， CPI， MIPS,MFLOPS) MIPS 每秒百万条指令数
  • 性能比较
    • 执行时间
    • 吞吐率

实例

1.11 假设浮点数指令FP指令的比例为30%，其中浮点数平方根FPSQR占全部指令的比例为4%, FP操作的CPI为5，FPSQR操作的CPI为20, 其他指令的平均CPI为1.25.现有两种改进方案，第一种是把FPSQR操作的CPI减至3, 第二种是把所有的FP操作的CPI减至3, 试比较两种方案对系统性能的提高程度。 答: 改进之前，系统指令平均时钟周期CPI为 \[CPI=\sum{(CPI_i \times \frac{I_i}{I_c})}=(5 \times 30 % )+(1.25\times70 %) = 2.375\]

如果采用A方案：FPSQR操作的CPI减至3，则整个系统的平均时钟周期数为: \[CPI_A=CPI-(CPI_{FPSQR}-CPI_{FPSQR}^{'}) \times 4 %=2.375-(20-3) \times 4 %=1.695\]

如果采用B方案：把所有的FP操作的CPI减至3，则整个系统的平均时钟周期数为： \[CPI_B=CPI-(CPI_{FP}-CPI_{FP}^{'})\times4 %=2.375-(5-3)\times30 %=1.775\]

从降低整个系统的指令平均时钟周期数的程度来看，方案A要优于B。

另外，分别计算两种方案的加速比: \[S_A=\frac{改进前CPU的执行时间}{A的CPU执行时间}=(I_C\times时钟周期\times CPI)/(I_c \times 时钟周期\times CPI_A)=\frac{CPI}{CPI_A}\] \[S_A=\frac{2.375}{1.695}=1.4\] \[S_B=\frac{2.375}{1.775}=1.34\]

由此也可知，方案A优于方案B。

第三章 流水线技术

流水线的概念：

  • 静（动）态流水线
  • 单（多）功能流水线
  • 线性流水线 流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次
  • 非线性流水线 流水线中除了有串行的连接外，还有反馈回路
单功能与多功能流水线
（按照流水线所完成的功能来分类）
单功能流水线：只能完成一种固定功能的流水线。
多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。

例： 多功能流水线：加、乘流水线

流水线表示方法--时空图 、连接图

流水线特点：五段流水线（访存部件ME, 转移EX)

ALU LOAD/STORE BRANCH(转移)
IF 取指
ID 译码，读寄存器堆
EX 执行 计算访存有效地址 计算转移目标地址，设置条件码
MEM (空操作) 访问存储器(读或写) 若条件成立，将转移目标地址送PC
WB 结果写回寄存器堆 将读写的数据写入寄存器堆 (空操作)

性能指标 ： 吞吐率、加速比、效率、 最佳段数

流水线相关与冲突及解决办法

  • 数据相关（真数据相关）/名相关/控制相关
  • 结构冲突、数据冲突、控制冲突：
数据冲突解决办法
控制冲突解决办法

多功能流水线时空图

吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量

瓶颈问题
瓶颈问题

加速比：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。

流水线的效率：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率( 效率)

静态处理分支指令的基本方法： * 预测成功 * 延迟分支

降低流水线分支损失的方法有哪些？ （1）在流水线中尽早判断出分支转移是否成功； （2）尽早计算出分支转移成功时的PC值（即分支的目标地址） * “冻结”或“排空”流水线的方法 * 预测分支失败 * 预测分支成功 * 延迟分支

请对延迟分支办法中的三种调度策略进行评价。 1. 从前调动：分支必须不依赖于被调度的指令，总是可以有效提高流水线性能。 2. 从目标处调度：若分支转移失败，必须保证被调度的指令对程序的执行没有影响，可能需要复制被调度指令。分支转移成功时，可提高流水线性能。但由于复制指令，可能加大程序空间。 3. 从失败处调度：若分支转移成功，必须保证被调度的指令对程序的执行无影响。分支转移失败时，可提高流水线性能。

预测分支
预测分支

命中Cache似乎不考

第四章 向量处理机

向量处理方法

  • 横向处理:
    • N次数据相关、2N次功能相关
  • 纵向处理:
    • 1次数据相关、1次功能相关
    • 当向量长度超过寄存器长度N时，可分组处理
  • 纵横处理:
    • 组内纵向处理, 组间横向处理
    • 适合"寄存器-寄存器结构"工作的向量处理机

向量流水处理机结构

  1. 存储器-存储器结构：纵向处理
    • 占据一般存储器的3倍带宽，一个时钟周期内读入2个操作数并写回1个结果
    • 延迟缓冲器
  2. 寄存器-寄存器结构：纵横处理
    • 支持流水线链接技术
    • 不遭遇向量Vi冲突和功能部件冲突，就都能并行工作

提高向量处理机性能的方法

  • 多个功能部件的并行操作
  • 链接技术 WD相关 链接技术：具有先写后读相关的两条指令，在不出现功能部件冲突和Vi冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。
    • 空间方面约束条件
      • 向量寄存器使用冲突
        • 源寄存器冲突: 同时只能提供一个
        • 结果寄存器冲突: 同时只能写一个
      • 功能部件冲突
    • 时间方面约束条件
      • 前一条指令的第一个结果分量送入寄存器的那一个时钟周期方可链接
      • 执行时间和寄存器长度必须相同

顺序执行时，一个向量的所有操作数执行完方才进行下一个向量的处理。而链接执行，就可以在一个向量的一个操作数得到结果后立即获得，对下一个向量立即进行处理。这样就可以免去等待第一个向量所有操作数完成运算的过程。

  • 分段开采(循环开采)
    • 流水线启动时间
  • 多处理机系统结构

向量处理机性能的主要参数

一条向量指令的处理时间
  • 执行一条向量长度为n的向量指令所需的时间: \[T_{vp} = T_{s} + T_{e} + (n-1)T_{c}\]
    \(T_s\) : 流水线的建立时间为了使处理部件流水线能开始工作所需要的准备时间。 \(T_e\) : 向量流水线的通过时间第一对向量元素通过流水线并产生第一个结果所花的时间。 \(T_c\) : 流水线的时钟周期时间
    一条指令
    一条指令
    • 上式转换为时钟周期个数 \[T_{vp} = [s + e + (n-1)]T_c\]
    • 令 \(T_{start} = s + e -1\) , 则 \[T_{vp} = (T_{start} + n)T_c\] \(T_{start}\) : 向量指令的启动时间。产生第一个结果的前一个时钟周期数。
每秒多少个浮点运算结果（MFLOP或一个浮点运算的时间）

\[MFLOPS = \frac{I_{FN}}{T_p \times 1000000}\] \(I_{FN}\) : 程序中浮点运算总次数 \(T_p\) : 执行程序时间

一组向量指令的处理时间
  • 影响因素:
    • 向量的长度
    • 向量操作之间是否存在流水功能部件的使用冲突以及数据的相关性
    • 数据的相关性
  • 编队: 能在一个时钟周期内一起开始执行的几条向量指令
    • 流水功能部件冲突
    • \(V_i\) 冲突
    • 数据的相关性
  • 编队后时间计算公式 \[T_{all} = \sum_{i = 1}^{m}{T_{vp}^{(i)}}\]
  • 当一个编队是由若干条指令组成时，其执行时间就是该编队中各指令的执行时间的最大值
  • 一组向量指令、m个编队的处理时间 \[T_{all} = \sum_{i = 1}^{m}{T_{vp}^{(i)}} = \sum_{i = 1}^{m}{(T_{start}^{(i)} + n)T_c} = (\sum_{i = 1}^{m}{T_{start}^{(i)} + mn)}T_c = (T_{start} +mn)T_c\] \(T_{start}^{(i)}\): 第i编队中各指令的启动时间的最大值
    • 表示成时钟周期个数 \[T_{all} = T_{start} + mn\]
分段开采时一组向量指令的总执行时间(复习课件中未作为重点)
向量流水线的最大性能 \(R_{\infty}\)
例题
最大性能例题
最大性能例题
半性能向量长度 \(n_{\frac{1}{2}}\)

半性能向量长度 \(n_{\frac12}\) 是指向量处理机的性能为其最大性能的一半时所需的向量长度。 \(n_{\frac12}\) 小表示流水线建立的时间少。 \(n_{\frac12}\) 越小， 对给定的向量处理，流水线性能越好。反映为建立流水线而导致的性能损失。

半性能长度计算
半性能长度计算

长度向量临界值 \(n_v\)(同样不是重点)

实例

题目补充：各功能部件的启动时间为：取数和存数部件为12个时钟周期、乘法部件为7个时钟周期，执行标量代码的开销 \(T_{loop} = 15\) 个时钟周期，对一个向量元素执行一次操作的时间Tg=一个时钟周期。

第五章 指令集并行

指令级并行度ILP

指令间存在的一种固有的并行性，计算机可以并行执行两条或两条以上的指令。

开发指令级并行度可以降低指令执行的平均周期数CPI

开发ILP的方法可以分为两大类

  • 主要基于硬件的动态开发方法（动态调度）
    • 记分牌动态调度算法
    • Tomasulo算法
  • 基于软件的静态开发方法（静态调度）
记分牌(Scoreboard)算法

基本思想:记分牌硬件实现了对指令的动态调度。支持乱序执行，在没有结构冲突时尽早地执行没有数据冲突的指令，使多条指令同时处于执行阶段。

记分牌维护3张表： * 指令状态表 记录正在执行的各条指令已经到了哪一段 * 功能部件状态表 记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个字段组成： * Busy：忙标志，指出功能部件是否忙。初值为“no”； * Op：该功能部件正在执行或将要执行的操作； * \(F_i\)：目的寄存器编号； * \(F_j\)，\(F_k\)：源寄存器编号； * \(Q_j\)，\(Q_k\)：指出向源寄存器 \(F_j\)、 \(F_k\)写数据的功能部件 ； * \(R_j\)，\(R_k\)：标志位，“yes”表示 \(F_j\)，\(F_k\) 中的操作数就绪且还未被取走。否则就被置为“no”。

  • 结果寄存器状态表 指出哪个功能部件将把结果写入该寄存器 为了乱序执行，译码段ID分解成流出和读操作数 流出：指令译码，检查是否存在结构冲突。 读操作数：等待数据冲突消失，然后读操作数。

第3章的5段流水线局限性:只能按序流出(In-order Issue)和按序执行(In-order Execution)

每条指令的执行过程分为4段（主要考虑浮点操作） * 流出：如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同，就向功能部件流出该指令，并修改记分牌内部记录表。 解决了WAW冲突 * 读操作数： 监测源操作数的可用性，如果数据可用，就从寄存器中读出源操作数并开始执行。 解决了RAW冲突，导致乱序执行。 * 执行： 取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成执行。 在浮点流水线中，这一段要占用多个时钟周期。 * 写结果 执行前会检测是否存在WAR冲突

WAR冲突可能发生在以下情况: 1. 前面的某条指令（按顺序流出）还没有读取操作数；而且,其中某个源操作数寄存器与本指令的目的寄存器相同。 2. 在这种情况下，记分牌必须等待，直到该冲突消失。

记分牌MIPS处理器基本结构
记分牌MIPS处理器基本结构

性能受限(不考) * 程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指令。 * 记分牌的容量（寄存器大小？） 记分牌的容量决定了流水线能在多大范围内寻找不相关指令。流水线中可以同时容纳的指令数量称为指令窗口 * 功能部件的数目和种类 功能部件的总数决定了结构冲突的严重程度 * 反相关和输出相关 它们引起记分牌中WAR和WAW冲突。

Tomasulo算法

基本思想: * 通过分散控制处理数据相关和乱序执行。记录和检测指令相关，将发生RAW的可能性减少到最小 * 通过寄存器换名(通过保留站和流出逻辑实现)来消除WAR冲突和WAW冲突

结构图
结构图

保留站：保存已经流出并等待到本功能部件执行的指令，在保留站通过流出逻辑来完成的寄存器换名（顺序流出，乱序执行） 公共数据总线CDB :所有功能部件计算结果都送到CDB，由它把这些结果直接送到各个需要该结果的地方（乱序完成）

具体算法（可选，暂时不看）

相关与流水线冲突

相关: 程序中指令之间的一种相互依赖关系。是程序固有的属性。

流水线冲突: 由于相关的存在，使得流水线指令流中的下一条指令不能在指定的时钟周期执行。

三种相关: * 数据相关 * 名相关 * 控制相关

三种流水线冲突: * 结构冲突 * 数据冲突 * 控制冲突 ##### 数据相关及其处理技术(其余相关都不是重点)

理想流水线的CPI加上各类停顿的时钟周期数：

\[CPI_{流水线} = CPI_{理想} + 停顿_{结构冲突} + 停顿_{数据冲突} + 停顿_{控制冲突}\]

IPC：Instructions Per Cycle(每个时钟周期完成的指令条数) \[CPI = \frac{1}{IPC}\]

动态分支预测技术

  • 分支历史表BHT 用二进制数10、11、01、00来表示转移预测状态的转换图
    BHT状态转换
    BHT状态转换
    从图中可以看出，只有连续两次预测错误，才会改变对分支去向的预测

优点: 转移预测提前到取指阶段。预测正确，则没有延迟损失。

缺点:仅提供转移目标指令信息,未提供转移目标指令地址信息。

所以它只有在以下情况下才有用: 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。在前述5段流水线中，由于判定分支是否成功和计算分支目标地址都是在ID段完成的，所以BHT方法不会给该流水线带来好处。（用BHT时，上一条指令的EX在执行，分支预测的判定和取指是同时在进行的，判定时间(上一条指令的执行时间)更长时才可以保证存在开销减少的价值，否则预测成功，也是需要多花一个周期来进行译码）

预测不正确，则清除指令预取(队列)缓冲器。会产生延迟时间损失。

BHT方法可以同 I-cache（指令cache）结合起来

对于前述5段流水线来说，BHT方法是在ID段对BHT进行访问，所以在ID段的末尾，能够获得分支目标地址(在ID段计算出)、顺序下一条指令地址以及预测的结果。如果能再提前一拍，即在IF段就知道这些信息，那么分支开销就可以减少为0.BTB能够实现这一点。 （BHT方法不像静态分支预测技术会直接加载预测的分支指令地址，所以导致即便预测成功也需要一个时钟周期来取得地址）

  • 分支目标缓冲器BTB（有时也称为分支目标Cache）
    • 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存
    • 缓冲区以分支指令的地址作为标识
    • 得到转移目标指令地址信息
      结构图
      结构图

流水线各阶段进行的操作

超标量处理机

在每个时钟周期内流出多条指令， CPI＜1 在每个时钟周期流出的指令条数不固定,但有上限，依代码的具体情况而定。 设这个上限为n，就称该处理机为n-流出(发射)。 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。

超流水线处理机

将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。 对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出，而是每隔1/n个时钟周期流出一条指令。 实际上该超流水线计算机的流水线周期为1/n个时钟周期。

超长指令字（VLIW)处理机

在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。 指令包中，指令之间的并行性是通过指令显式地表示出来的。 指令调度是由编译器静态完成的。

流水线时空图必考。 超标量流水线调度策略及时空图 1.按序流出按序完成；2.按序流出无序完成；3.无序流出 第1条是无调度 第2条是动态调度，考上述的记分牌算法吧 第3条可能是考多流出技术

实例

记分牌算法中，记分牌中记录的信息由哪三部分构成

答: 指令状态表、功能部件状态表、结果寄存器状态表

动态分支预测技术

5.6 给出采用分支目标缓冲器(BTB)后，在流水线三个阶段(IF段、ID段、EX段）所进行的相关操作有哪些？

5.8 分支延迟
5.8 分支延迟
5.9
5.9
画超标量处理机时空图
画超标量处理机时空图

第九章 互联网络

互连网络相关概念

分类
  • 静态互联网络
  • 动态互联网络
    • 总线网络
    • 多级互连网络
    • 交叉开关网络
三大要素：互连结构、开关元件、控制方式
特征
拓扑结构 静态 动态
控制策略 集中式 分布式
定时方式 同步 异步
交换方法 线路交换 分组交换

互联函数

基本互联函数
恒等函数
交换函数

实现二进制地址编码中第k位互反的输入端与输出端之间的连接。

主要用于构造立方体和各种超立方体互连网络。

它共有 \(n = log_{2}{N}\) 种互联函数。（N为结点个数）

例子： 当N＝8时，n＝3，可得到常用的立方体互连函数: \[Cube_{0}(x_{2}x_1x_0) = x_2x_1\overline{x_0}\] \[Cube_{1}(x_{2}x_1x_0) = x_2\overline{x_1}x_0\] \[Cube_{2}(x_{2}x_1x_0) = \overline{x_2}x_1x_0\]

均匀洗牌函数

将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式 \[\sigma(x_{n-1}x_{n-2}\cdots x_1x_0) = x_{n-2}x_{n-3}\cdots x_1x_0x_{n-1}\]

逆均匀洗牌函数 将输入端的二进制编号循环右移一位而得到所连接的输出端编号。

蝶式函数

蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号 \[\beta(x_{n-1}x_{n-2}\cdots x_2x_1x_0) = x_0x_{n-2}\cdots x_1x_{n-1}\]

均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础

反位序函数

将输入端二进制编号的位序颠倒过来求得相应输出端的编号。

\[\rho(x_{n-1}x_{n-2}\cdots x_1x_0) = x_0x_1\cdots x_{n-2}x_{n-1}\]

移数函数

将各输入端都错开一定的位置（模N）后连到输出端。 \[\alpha(x) = (x\pm k)mod N\] \[1\leqslant x\leqslant N-1, 1\leqslant k\leqslant N-1\]

PM2I移数函数(重点)

该函数又称为“加减 \(2^i\) ”函数

\[ PM2\_{+i}(x) = (x +2^i)mod N\] \[ PM2\_{-i}(x) = (x -2^i)mod N\] \[ 1\leqslant x\leqslant N-1, 1\leqslant i\leqslant n-1, n=log\_2N\]

PM2I共有2n个互联函数(怎么算出来的?)

实质为1,2,4个环型网（环形网是什么）

移数函数可构成环型网(单向环网、双向环网)、方格网、移数网

互联网络的结构参数

网络参数 : 网络规模、 结点度、 距离、直径，等分宽度（重点)

  • 网络规模N：网络中结点的个数。
  • 结点度d：与结点相连接的边数（通道数），包括入度和出度。
    • 进入结点的边数叫入度。
    • 从结点出来的边数叫出度。
  • 结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
  • 网络直径D：网络中任意两个结点之间距离的最大值。 网络直径应当尽可能地小。
  • 等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。
    • 线等分宽度：B＝b×w 其中：w为通道宽度（用位表示） 该参数主要反映了网络最大流量。

互联网络的性能指标

评估互连网络性能的两个基本指标：时延和带宽 * 通信时延 指从源结点到目的结点传送一条消息所需的总时间 * 软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间 * 通道时延：通过通道传送消息所花的时间。 * 选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销 * 竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。 * 网络时延 通道时延与选路时延的和 * 端口带宽 对于互连网络中的任意一个端口来说，其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。 * 聚集带宽 网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。 * 等分带宽 与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量。

互联网络

典型互联网络:立方体型 和Illiac网，Omega网络（混洗函数）（重点） ##### 典型静态互联网络 * 线性阵列 * 环和带弦环 * 循环移数网络 * 树形和星形 * 胖树形 * 网格形和环网形 * Illiac网络 * 超立方体 * 带环n-立方体 * k元n立方体

动态互联网络

由交换开关构成的互联网络，可按运行程序的要求改变网络的连接状态

特点： * 网络中开关元件可以控制（有源）。 * 链路可通过设置开关的状态来重构。 * 网络边界上的开关元件可与处理机相连。

总线网络
交叉开关网络
多级互联网络的构成

MIMD和SIMD计算机都采用多级互连网络MIN（Multistage Interconnection Network）

一种通用的多级互连网络 * 由a×b开关模块和级间连接构成的通用多级互连网络结构 * 每一级都用了多个a×b开关 * 相邻各级开关之间都有固定的级间连接

各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。 * 控制方式：对各个开关模块进行控制的方式。 * 级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。 * 单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。 * 部分级控制：第i级的所有开关分别用i＋1个信号控制，0≤i≤n－1，n为级数。 * 常用的级间互连模式 * 均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等

多级立方体网络

多级立方体网络包括STARAN网络和间接二进制n方体网络等。 * 两者仅在控制方式上不同，在其他方面都是一样的。 * 都采用二功能（直送和交换）的2×2开关。 * 当第i级（ \(0\leqslant i\leqslant n-1\) ）交换开关处于交换状态时，实现的是 \(Cube_i\) 互连函数。

一个N输入的多级立方体网络有 \(log_2N\) 级，每级用 \(\frac N2\) 个2×2开关模块，共需要 \(log_2N\times\frac {N}{2}\) 个开关。

一个8个入端的多级立方体网络

STARAN网络采用级控制和部分级控制。 * 采用级控制时，所实现的是交换功能； * 采用部分级控制时，则能实现移数功能。

间接二进制n方体网络则采用单元控制。 * 具有更大的灵活性。

Omega网络

一个8×8的Omega网络 * 每级由4个4功能的2×2开关构成 * 级间互连采用均匀洗牌连接方式

一个N输入的Omega网络（重点） * 有 \(log_2N\) 级，每级用 \(\frac N2\)个2×2开关模块，共需要 \(\frac N2log_2{N}\) 个开关。 * 每个开关模块均采用单元控制方式。 * 不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。

动态互联网络的比较

消息传递机制（重点）

当源结点和目的结点之间没有直接的连接时，消息需要经过中间的结点进行传递。寻径就是用来实现这种传递的通信方法和算法。有的称之为路由

路由选择和消息传递方法式:

线路交换和包交换（存储转发，虚拟直通、虫孔方式） * 线路交换：在传递信息之前，先建立一条从源结点到目的结点的物理通路( 所需时间 Lt ×（D+1）/B)，然后再传递信息( 所需时间 L/B) 。包经中间结点时,包无需存储 

* 优点：包经中间结点时,包无需存储，实际通信时间较短，使用缓冲区少.

适合于具有动态和突发性的大规模并行处理数据的传送。 * 缺点： 1. 物理通道非共享。传输过程中通道一直占用。 2. 若频繁建立源到目的结点的通路，时间开销大 * 存储转发：最简单的分组交换方式。 * 存储转发中，包是信息传递的基本单位。包从源结点经过一系列中间结点到达目的结点。 * 要求：包经过的每个中间结点都要设置一个包缓冲器。当一个包到达某个中间结点时，该结点先把这个包全部存储起来，然后在出口链路可用、而且下一个结点的包缓冲器也可用的情况下，传递给下一个结点。

* L为消息包的长度    * 存储转发中网络时延与源和目的地距离成正比.           * 第一代多计算机系统常采用存储转发方式 * 缺点： 1. 包缓冲区大，不利于VLSI实现； 2. 网络时延大，与结点距离成正比。 * 虚拟直通: 为减少存储转发中 包存储的时延较大，包不必全部存入缓冲后再做路由判断，只要接收到用作寻径信息（头部），即进行路由选择。 1. 如果结点的输出链路空闲，包立即转送到下一个结点。如果整个通路都空闲，包直达目的结点，如同线路交换 2. 如果没有空闲链路时或出现寻径阻塞时，须将整个信息全部存储在寻径结点中。等同存储转发。
* 缺点： 1. 每个结点中需要有缓冲。以便没有空闲链路时，要用缓冲器存储。 2. 包缓冲区大，不利于VLSI实现； * 虫孔(wormhole)方式 　为减少存储转发中包的存储时延，包可分为更小的“片” 。当一个结点把头片送到下一结点后，后面的各个片也依次送出。 * 特点：包不必全部存入缓冲后再做路由判断，只要接收到用作寻径信息（头片），即进行路由选择。 * 结点中缓冲器的容量小，各片的传送可按流水方式进行。传输延迟略大于线路交换，网络冲突较小。 * 一个结点一旦开始传送一个包中的头片后，必须等待这个包所有片都送出后，才能传送其他包。不同包的片不能混合在一起传送。 * 在新型的多计算机系统中得到了广泛的应用。 * 与虚拟直通的不同之处 当输出通路忙时，结点是把一个片存储到缓冲器中。 片的大小比包小很多，所以能有效地减少缓冲器的容量，使得它易于用VLSI实现。

  • 存储转发与虫孔方式的时间比较
死锁与虚拟通道
流量控制策略
包冲突的解决
  • 通过通道在两个相邻结点之间传送一个片，要同时具备3个条件：
    • 源缓冲区已存有该片；
    • 通道已分配好；
    • 接收缓冲区准备接收该片。
  • 当两个包到达同一个结点时，可能都在请求同一个接收缓冲器或者同一个输出通道，这时必须对两个问题进行仲裁。
  • 4种解决方案
    1. 后一个包暂存(在缓冲区) 优点:不会浪费已经分配了的资源，但要求结点中有一个足够大的缓冲器来存放整个信息包。
    2. 阻塞后一个包 第一个包送入片缓冲区，用门控拒绝第二个包（阻塞）。不丢弃。
    3. 丢弃后一个包 第一个包送入片缓冲区。
    • 有可能会造成严重的资源浪费，而且要求重新进行被丢弃包的传输与确认。
    1. 后一个包绕道 在包寻径方面有更多的灵活性，但为了到达目的结点，可能要花费 较多的通道资源，造成浪费。
确定性寻径和自适应寻径
  • 确定性寻径：通信路径完全由源结点地址和目的地址来决定，也就是说，寻径路径是预先唯一地确定好了的，而与网络的状况无关。
  • 自适应寻径：通信的通路每一次都要根据资源或者网络的情况来选择。
    • 对于二维的网格网络来说，这种寻径方法被称为X-Y寻径。 先沿X维方向进行寻径，然后再沿Y维方向寻找路径。
    • 对于超立方体来说，这种寻径方法被称为E-cube寻径。
通信模式
  • 单播：对应于一对一的通信情况，即一个源结点发送消息到一个目的结点。
  • 选播：对应于一到多的通信情况，即一个源结点发送同一消息到多个目的结点。
  • 广播：对应于一到全体的通信情况，即一个源结点发送同一消息到全部结点。
  • 会议：对应于多到多的通信情况。

通道流量和通信时延是常用的两个参数 * 通道流量用传输消息所使用的通道数来表示。 * 通信时延用包的最长传输时间来表示。

优化寻径网络以最小通道流量或通信时延为目标。

实例

混洗交换题计算方法: 在混洗交换网络中，最远的两个入、出端号 是全 "0" 和 全"1", 它们的连接需要 n 次交换 和n-1 次混洗。 所以其 最大距离为2n - 1.

在有8个处理器的混洗交换网络中，若要使第0号处理器与第7号处理器相连，需要经过2次混洗和 \(\underline{3}\) 次交换

在有16个处理器的混洗交换网络中，若要使第0号处理器与第15号处理器相连，需要经过多少次混洗和交换

答：3次混洗和4次交换

设Cube为立方体互联函数， \(\sigma\) 为均匀洗牌函数， \(\beta\) 为蝶式函数， \(\rho\) 为反位序函数，分别求 \(Cube_{3}(0110)\) 、 \(\sigma_{(3)}(0110)\) 、 \(\beta(0110)\) 、 \(\rho^{(2)}(0110)\) .

答: * \(Cube_3(0110) = 0010\) * \(\sigma_{(3)}(0110) = 0101\) * \(\beta(0110) = 0110\) * \(\rho^{(2)}(0110) = 1010\)

9.11 N=16的STARAN网络在级控制方式下实现分组交换置换，如果实现的分组交换置换是：首先是4组4元交换，然后是2组8元交换，最后是1组16元交换，写出网络实现的互联函数。

9.12 具有 \(N=2^n\) 个输入端的Omega网络，采用单元控制。 (1) N个输入总共应有多少种不同的排列？ (2) 该Omega网络通过一次可以实现的置换总共可有多少种？ (3) 若N=8, 计算一次通过能实现的置换数占全部排列的百分比。

答: (1) N个输入可有N!种不同排列。 (2) 该Omega网络通过一关可以实现的置换有 \(2^{\frac{N}{2}log_2N}=N^{\frac{N}{2}}\) 种不同。 (3) 若N=8, 通过Omega网络一次可以实现的不重复置换有 \(8^4 = 4096\) 种。 8个输入可实现的不重复排列有 \(8! = 40320\) 种。 故，一次可实现的置换数占全部排列数的10.16%.

Omega网络
Omega网络

第十章 多处理机

多处理机概念:

  • 由若干台独立的计算机或处理机(CU或PU)组成，每台计算机能独立执行自己程序。不同于并行处理机。
  • 多个指令部件控制，统一操作系统，实现指令级以上(任务级、作业级）并行。MIMD结构。
  • 多处理机通过互连网络连接，以共享某种设备（主存、输入输出或网络）方式，实现程序间数据交换和同步。
  • 算法上，开发、挖掘和实现更多通用算法中隐含的并行性；不限于向量数组处理. 依靠软件手段解决资源分配和管理问题，特别是处理机管理和进程调度等。
MIMD计算机的特点、分类
Flynn分类法

SISD、SIMD、MISD、MIMD

MIMD已成为通用多处理机系统结构的选择，原因：
  • MIMD具有灵活性；
  • MIMD可以充分利用商品化微处理器在性能价格比方面的优势。 计算机机群系统（cluster）是一类广泛被采用的MIMD机器。
根据存储器的组织结构 ，把现有的MIMD机器分为两类

（每一类代表了一种存储器的结构和互连策略） * 集中式共享存储器结构 * 最多由几十个处理器构成。 * 共享一个集中式的物理存储器。 * 分布式存储器多处理机（DSM) * 存储器在物理上是分布的。 * 非均匀访存模型，NUMA。

多处理机一致性问题

Cache的一致性问题和原因
  • 允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，
  • 当某个处理器对其Cache中的数据进行修改后，会使得其Cache中的数据与其他Cache中的数据不一致。

例　由两个处理器（A和B）读写引起的Cache一致性问题

存储器的一致性
  • 如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。
  • 单处理机系统中，Cache一致性问题存在于Cache与主存之间，可通过全写法（write－through，写直达，写通过）解决。
  • 全写法：同时修改Cache和主存中值(或策略)。回写法：仅修改Cache值，不立即修改主存。
  • 全写法只能维持一个Cache和主存之间的一致性，不能更新其他处理机中的Cache的相同副本。 解决Cache一致性问题是多处理机的重要问题。
实现一致性的基本方案
  • 在一致的多处理机中，Cache提供迁移、复制两种功能：
  • 共享数据的迁移：把共享数据拷贝后迁入本地Cache 减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。
  • 共享数据的复制：把共享数据多个副本拷放在多个处理器Cache 不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。 一般情况下，小规模多处理机是采用硬件的方法来实现Cache的一致性。
Cache一致性协议

在多个处理器中用来维护一致性的协议。 * 关键：跟踪记录共享数据块的状态 * 两类协议（采用不同的技术跟踪共享数据的状态） * 目录式协议（directory）： 存储器数据块的共享状态被保存在一个称为目录的地方 * 监听式协议（snooping） 处理机向局部Cache 写数据通过总线广播，其他处理机对广播的写事务进行监视，如果某Cache中有数据副本，用写作废或写更新处理.

采用两种方法来解决Cache一致性问题。
  • 写作废协议 在处理器对某个数据项进行写入之前，作废其它的副本(保证它拥有对该数据项的唯一的访问权)
  • 写更新协议 当一个处理器对某数据项进行写入时，通过广播使其它Cache中所有对应于该数据项的副本进行更新。
监听协议的实现
  • 监听协议的基本实现技术
  • 实现监听协议的关键有3个方面
    • 处理器之间通过一个可以实现广播的互连机制相连。 通常采用的是总线。
    • 当一个Cache响应本地CPU的访问时，如果涉及到全局操作，就在总线上发出相应的消息。
    • 所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有则响应，并进行相应的操作 。
  • Cache发送到总线上的消息主要有以下两种：
    • RdMiss——读不命中
    • WtMiss——写不命中
  • 需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。
    • 写直达Cache：因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。
    • 对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。 （后面的讨论中，只考虑写回法Cache）
目录协议的基本思想

监听一致性协议的可扩放性很差

  • 主存中设置一个中央目录，存放每个数据块状态位和指针位（位向量） ，指针位对应处理机Cache 。

  • 目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。

  • 任何一个数据块，都可以在目录表唯一的一个位置中找到相关的信息。使一致性协议避免了广播操作

  • 状态位指示数据块状态，指针位（位向量）指向处理机Cache ，指出Cache中是否有数据块副本。

  • 当一个处理机写入本身Cache时，根据目录表有选择地通知存有数据块的处理机的Cache。避免Cache不一致性

目录协议的三种结构
  • 不同目录协议的主要区别主要有两个
    • 所设置的存储器块的状态及其个数不同
    • 目录的结构
  • 目录协议分为3类 全映象目录、有限映象目录、链式目录

多处理机分类

按多处理机之间物理连接的紧密程度与交互作用能力强弱
  • 紧耦合系统
  • 松耦合系统
按处理机结构
  • 同构型多处理机系统
  • 异构型多处理机系统
按系统组成结构
  • 并行向量处理机(PVP)
  • 对称多处理机(SMP)
  • 分布共享存储器多处理机(DSM)
  • 大规模并行处理机(MPP)
  • 工作站机群(COW)

五类机器特征比较

按存储器组织结构
  • 集中式共享存储器结构(SMP)
  • 分布式存储器结构（DSM)

第十三章 阵列处理机

阵列处理机

多处理单元(PE)按照一定互连方式，在同一控制部件(CU) 控制下，对各自数据完成同一条指令规定的操作。 * 从CU看，指令串行执行。 * 从PE 看，数据并行处理。 * 属于单指令流多数据流结构(SIMD)。细粒度并行处理机 * 应用领域：主要用于高速向量或矩阵运算。 操作模型

阵列处理机的操作模型可用五元组表示

阵列处理机＝（N，C，I，M，R） * N：机器的处理单元（PE）数。 例如：Illiac Ⅳ计算机有64个PE MP-1计算机有16384个PE * C：控制部件CU直接执行的指令集，包括标量指令和程序流控制指令。 * I：由CU广播至所有PE进行并行执行的指令集。 包括算术运算、逻辑运算、数据寻径、屏蔽以及其他由每个PE对它的数据所执行的局部操作。 * M：屏蔽方案集 每种屏蔽将所有PE划分成允许操作和禁止操作两种工作模式。 * R：数据寻径功能集 说明互连网络中PE间通信所需要的各种设置模式。

阵列处理机的结构

  • 分布式存储器的阵列机:
    • 含有多个相同的处理单元PE，每个PE有各自的本地存储器LM。
    • PE之间通过数据寻径网络以一定方式互相连接。它们在阵列控制部件的统一指挥下，实现并行操作。
    • 指令的执行顺序基本上是串行进行的。
    • 程序和数据是通过主机装入控制存储器。
  • 共享存储器的阵列机:
    • 集中设置存储器
      • 共享的多体并行存储器SM通过对准网络与各处理单元PE相连。
      • 存储模块的数目等于或略大于处理单元的数目。
    • 必须减少存储器访问冲突 （将数据合理地分配到各存储器模块中 ）
    • 在处理单元数目不太多的情况下是很理想的
    • 所有阵列指令都必须使用长度为n的向量操作数 （n为PE的个数)

阵列处理机的特点(与流水线向量对比) * 阵列机是以单指令流多数据流方式工作的 * 阵列机是通过设置多个相同的处理单元来开发并行性的，它利用并行性中的同时性，而不是并发性。所有处理单元必须同时进行相同的操作。这与利用时间重叠的向量流水处理机是不一样的。 * 阵列机是以某一类算法为背景的专用计算机。这是因为阵列机通过都采用简单，规整的互联网络来实现处理单元间的连接操作，从而限定了它所使用的求解算法类别。 * 阵列机的研究必须与并行算法的研究密切结合，以便能充分发挥它的处理能力。 * 阵列机的控制器实质上是一台标量处理机，而为了完成I/O操作以及操作系统的管理，尚需一个前端机。因此实际的阵列机系统是由上述三部分构成的一个异构型多处理机系统。

SIMD机与并行算法的关系

以Illiac Ⅳ为例，讨论阵列处理机的算法。

解有限差分方程（需要知道大致含义）

把一个有规则的网格覆盖在整个场域上，用网格点上的变量值写出差分方程组以代替场方程来进行计算。 描述平面场的拉普拉斯方程

差分法求解的精度与网格间距有直接的关系，网格越小，精度越高，但求解所花费的时空开销越大。

Illiac Ⅳ在计算时，是把内部网格点分配给各个处理单元的。因此，上述计算过程可以并行地完成，从而大幅度地提高处理速度。

矩阵加
矩阵乘

设A、B和C为3个8×8的二维矩阵。若给定A和B，则 C＝A*B的64个分量可利用下列公式计算。 \[c_{ij} = \sum_{k=0}^{7}{a_{ik}b_{kj}}\] \[0 \leqslant i,j \leqslant 7\]

FORTRAN 程序 

1
2
3
4
5
6
DO 10 I＝0，7
	DO 10 J＝0，7
		C（I，J）＝0
		DO 10 K＝0，7
		10  C(I，J) ＝C(I，J)＋A(I，K)*B(K，J)

* 在SISD计算机上求解，三重循环，每重循环执行8次，共需512次乘加的时间 * 在SIMD阵列处理机上求解这个问题 执行下列FORTRAN程序： 
1
2
3
4
DO 10 I＝0，7
	C（I，J）＝0
    DO 10 K＝0，7
    10  C(I，J) ＝C(I，J)＋A(I，K)*B(K，J)
速度提高到原来的8倍，即每个处理单元的计算时间缩短为64次乘加时间。

递归折叠求和算法

一个将N个数的顺序相加转变为并行相加的问题。

取N＝8。即有8个数A（I）要顺序累加（0≤I≤7） 这是一个串行程序，共要进行8次加法。

在阵列处理机上采用成对递归相加的算法，则只需 \(log_28＝3\) 次加法 。

实例

阵列处理机操作模型可以用5元组表示:阵列处理机=(N, C, I, M, R), 简述其中N、C、I、M、R的含义。 答:N为极其的处理单元(PE)数； C为控制部件CU I为由CU广播至所有PE进行并行执行的指令集 M为屏蔽方案集，其中每种屏蔽将所有PE划分成允许操作和禁止操作两种模式 R为数据寻径功能机，说明互联网络中PE间通信所需要的各种设置模式

13.3 简述阵列处理机的特点 答： 1. 阵列机是以单指令流多数据流方式工作的。 2. 阵列机是通过设置多个相同的处理单元来开发并行性的，它利用并行性的同时性，而不是并发性 3. 阵列机是以某一类算法为背景的专用计算机 4. 阵列机的研究必须与并行算法的研究密切结合 5. 阵列机的控制器实质上是一台标量处理机

试分析与比较SIMD计算机与向量计算机的相同与不同 答: 相同点: 都能对大量数据进行向量处理 不同点: * SIMD获得高处理速度主要是采用资源重复的并行措施 * 各个处理单元并行工作 * 向量处理机依靠的是多功能流水线部件时间重叠，指高速度 * 另一区别是SIMD计算机有它的互联网络

简述SIMD计算机的分布式存储器与共享存储器的异同 答: 相同点: 都存在互联网络 不同点: * 在共享方案中，共享的多体并行存储器通过对准网络与各处理单元相连 * 在分布内存方案中，每个处理单元有自己的本地存储器，处理单元之间的数据通过数据寻径网络完成。

存储器
存储器

这道题，推算体号地址公式的知识点不在我们书上，理论上，我们应该只能一个个尝试填表。

**例1．试分别在下面两种计算机系统上用最短的时间来计算表达式s=A1B1+A2B2+…A32*B32。假设加法和乘法分别需要两个和四个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE。试确定下列每种情况的最小计算时间：（重点，必考） 1. 一台SISD串行计算机。 2. 一台有8个PE的SIMD计算机，8个PE用移数函数PM2I连接。每个PE用一个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEi mod 8中，其中i=1，2，…，32。每个PE可在不同时刻执行加法或乘法**

答: 1. 在SISD计算机中,需要32次乘法和31次加法。 共需要时间：T=432+231=190单位时间

  1. 在SIMD计算机上计算的算法： 假定向量中的32对元素平均地分配到8个处理器中，每个处理器分配4对，则每个处理器计算时间为 44+32 总时间 =每个处理器计算时间+递归折叠求和算法 T=44+32+1+2+1+2+1+2=31