计算机系统结构笔记
计算机系统结构复习笔记
@Trenchance 2025.06.21
基础知识
层次结构
程序员包括下面四类：机器语言，操作系统，汇编语言，编译程序程序员。
分类
Flynn分类法、冯氏分类法和Handler分类法。
Flynn分类法：
冯氏分类法：
最大并行度：计算机系统在单位时间内能够处理的最大的二进制位数。
Handler分类法（并行度加流水线）：
计算机系统设计
4个定量原理
设计方法
“由上往下”（top-down）设计，适合于专用机的设计，而不适合通用机的设计。
由下往上”（bottom-up）设计，采用这种方法时，软件技术完全处于被动状态，这会造成软件和硬件的脱节，使整个系统的效率降低。
“从中间开始”（middle-out）设计：
性能评测
基准测试程序套件：由各种不同的真实应用程序构成。
SPEC系列：最成功和最常见的测试程序套件。
其他
冯诺依曼计算机：输入，输出，运算器，控制器，存储器。以运算器为中心，指令驱动。
计算机系统的改进：
软件的可移植性：一个软件可以不经修改或者只需少量修改就可以由一台机器移植到另一台机器上正确地运行。差别只是执行时间的不同。我们称这两台机器是软件兼容的。
实现可移植性的常用方法：采用系列机，模拟与仿真（使软件能在具有不同系统结构的机器之间相互移植），统一高级语言 。
系列机：由同一厂家生产的具有相同的系统结构，但具有不同组成和实现的一系列不同型号的机器。
兼容机：由不同公司厂家生产的具有相同系统结构的计算机 。
模拟：用软件的方法在一台现有的机器（称为宿主机）上实现另一台机器（称为虚拟机）的指令集。
仿真：用一台现有机器（宿主机）上的微程序去解释实现另一台机器（目标机）的指令集。
翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。
解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。
并行性：
流水线
流水线级数，段数
时间最长的段被称为瓶颈段。
通过时间，排空时间
解决流水线瓶颈的常用方法
流水线设计的若干问题
瓶颈问题；流水线额外开销（流水寄存器延迟，时钟偏移），增加流水线深度提升性能，但是深度受限于额外开销，时钟周期小到和额外开销相同时流水没有意义。流水线冲突。
流水线相关与冲突
IF：从主存取指令，PC++
ID：读寄存器
EX：计算出有效地址或者ALU计算
MEM：根据EX算出来的有效地址，写到主存或者PC（LD从主存读数据）
WB：写寄存器
相关：数据相关（真数据相关，对应RAW），名相关（两条指令之间并没有数据流动），控制相关（分支指令引起）。
名相关：反相关（对应WAR），输出相关（对应WAW）。使用换名技术消除名相关。
解决先写后读相关的两种方法：定向技术，指令调度。
流水线冲突：结构冲突（硬件资源受限无法重叠执行）（注意：有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致 IF MEM 访存冲突。这不是数据冲突），数据冲突（当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们串行执行时的顺序，则发生了数据冲突，数据冲突包含RAW，WAW，WAR），控制冲突（流水线遇到分支指令或其他会改变PC值的指令所引起的冲突）。
定向：用于解决数据冲突，EX段和MEM段之间的流水寄存器中保存的ALU 运算结果总是回送到ALU的入口。但是解决不了LD和ADD之间冲突。
控制冲突：一般情况下，分支指令在MEM完成PC写入，带来3周期延迟：
单周期延迟分支：在分支指令之后插入一条额外的指令（称为延迟槽指令），出现这句话默认分支指令提前到ID完成。
例题详见作业题。
指令级并行
指令级并行 ILP，计算机可以并行执行两条或两条以上的指令。
开发ILP有两种：资源重复，流水线。
目前我们流水线最大受阻：按序流出，按序执行。
记分牌（4段流水）
4段流水线与其解决的冲突：
流出：如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件流出该指令（解决WAW）。
读操作数：源操作数可用就从寄存器取（解决RAW，使得指令乱序）。
执行：占用多个周期。
写结果：检测是否存在WAR冲突。如果不存在，或者原有的WAR 冲突已消失，记分牌就通知功能部件把结果写入目的寄存器。如果前面的某条指令（按顺序流出）还没有读取操作数； 而且：其中某个源操作数寄存器与本指令的目的寄存器相同，在这种情况下，记分牌必须等待，直到该冲突消失。
Tomasulo（3段流水）
记分牌需要在流出和写结果段解决WAW和WAR冲突，Tomasulo使用寄存器换名解决WAW和WAR冲突。
Tomasulo算法基本硬件结构：
注意：当指令流出时，如果其操作数还没有计算出来， 则将该指令中相应的寄存器号换名为将产生这个 操作数的保留站的标识。
指令流出到保留站后，其操作数寄存器号或者换 成了数据本身（如果该数据已经就绪），或者换 成了保留站的标识，不再与寄存器有关系。
Tomasulo流水线：3段
流出：若保留站有空闲，就把指令送到保留站r（结构冲突）。若操作数就绪，就送入保留站r。若操作数未就绪，就把将产生该操作数的保留站的标识送入保留站r，一旦被记录的保留站完成计算，它将直接把数据送给保留站r（解决WAR，WAW）。
执行：执行。
写结果：计算结果放到CDB上，所有等待该计算结果的寄存器和保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。
Tomasulo+ROB 前瞻执行（4段流水）
前瞻执行4段流水：流出，执行，写结果，指令确认。
其中写结果只需要把结果写到ROB中；指令确认，如果前面所做的猜测是对的，把在ROB中的结果写到 寄存器或存储器，如果猜错，从另一条分支重新开始执行。
关键思想：允许指令乱序执行，但必须顺序确认。 在指令被确认之前，不允许它进行不可恢复的操作。
ROB代替Tomasulo中保留站的换名工作：
对比Tomasulo：
ROB实现指令的顺序完成，实现了精确异常；
Tomasulo乱序完成，不精确异常。
其他动态分支预测技术
分支历史表BHT（ID完成预测，五段流水线无好处，只有在判定分支是否成功所需的时间大于确定分支目标地址所需的时间才有用）。
分支目标缓冲器BTB（IF完成预测）。
多指令流出技术
超标量静态+动态，超长指令字只能静态。前者对程序员透明。
多发射处理机主要有超标量处理机、超流水处理机、超标量超流水处理机和超长指令字处理机。
超流水线处理机
将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。如MIPS R4000。
指令流水线级数为8或8以上的流水线处理机称为超流水线处理机。
互联网络
互联函数
立方体互联函数适用于构造超立方体网络。
互联网络
评估互连网络性能的两个基本指标：时延和带宽。
通信时延：指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成，软件开销，通道时延，选路时延，竞争时延。
网络时延：通道时延与选路时延的和。
静态互联网络
超立方体（k-立方体）：
带环立方体（k-CCC）：
k元n-立方体网络：参数n是立方体的维数，k是基数，即每一维上的结点个数。
动态互联网络
动态互联网络包括：总线网络，多级互联网络，交叉开关网络。
级控制信号：交换
部分级控制信号：移数
总结一下，STARAN网络有两种控制方式，级控制和部分级控制；Omega网络采用单元控制。
级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。
单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。
部分级控制：第i级的所有开关分别用i＋1个信号控制。
STARAN采用二功能2×2开关（只有直送，交换两种），当开关为1时，采用交换，0时采用直送。级控制时用于交换，第i级交换开关处于交换状态（0接1，1接0）时，实现的是Cubei互连函数；部分级控制时用于移数。
Omega级间采用均匀洗牌连接（循环左移），采用四功能2×2开关（直送，交叉，上播，下播），全部单元控制。
间接二进制n方体网络则采用单元控制。
消息传递机制
四种寻径方式：线路交换，存储转发，虚拟直通，虫蚀方式。
四种通信模式：单播（1-1），选播（1-*），广播（1-all），会议（*-*）。
寻径
先把源和目的异或计算方向，然后按照方向一步一步走。
向量处理机
向量处理方式
向量处理机结构
提高向量处理机性能的常用技术
链接技术
注意这里是一二两条指令可以并行的。如果不链接，就是纵向处理（因为 CRAY-1 为寄存器－寄存器结构，这是分组处理方式，该计算机的向量寄存器为64位，题目中N小于64不需要分组，也就是纵向了）。
分段开采
向量的长度大于向量寄存器的长度。
一条向量指令
Te ：向量流水线的通过时间，第一对向量元素通过流水线并产生第一个结果所花的时间。
Tstart：从一条向量指令开始执行到还差一个时钟周期就产生第一个结果所需的时钟周期数。可称之为该向量指令的启动时间。（也就是通过时间周期数-1）。
Tvp：一条向量指令的处理时间，(Tstart+n)Tc。
一组向量指令
把能在同一个时钟周期内一起开始执行的几条向量指令称为一个编队（他们数据和结构都不冲突）（类似于例4.2的前两条）。
总的时间等于所有编队执行时间加和（因为编队之间有冲突，必须等排空，所以直接加和。其实类似于例4.2的2N+15的计算）。
当一个编队是由若干条指令组成时，其执行时间就应该由该编队中各指令的执行时间的最大值来确定。
m：编队的个数。n：向量长度，这里＜向量寄存器长度MVL。
T^(i)^start：第i编队中各指令的启动时间的最大值。
Tstart：Σ1到m T^(i)^start 即该组指令总启动时间。
Tall = Tstart + mn 。
分段开采时的一组向量指令
m：编队的个数。n：向量长度，这里>向量寄存器长度MVL。
其实还是Tall = Tstart + mn ，只是这里引入了额外处理操作Tloop，(Tstart+Tloop) 总共加了(n/MVL上界) 次。
例题：
有些人问上面那题为什么不要减一，因为题目直接给的是启动时间，而不是通过时间。
注意链接的情况，直接把链接部件启动时间加和即可。
性能评价
为什么分子有个2，因为这段指令其实只有两条是浮点运算。分母就是上面算的TN。
阵列处理机 SIMD
常见机器：Illiac Ⅳ。
多处理机 MIMD
根据存储器的组织结构 ，把现有的MIMD机器分为两类：集中式共享存储器结构（SMP对称式共享存储器多处理机，UMA机器），分布式存储器多处理机（优于集中式共享存储器结构）。
两种存储器系统结构：共享地址空间（分布式共享存储器系统DSM，NUMA机器）；把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。
两种通信机制：共享存储器通信机制，处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。消息传递通信机制，多个独立地址空间的计算机采用（分为同步和异步，同步发送一个消息后一直要等到应答结果才继续运行，异步通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方）。
SMP对称式共享存储器多处理机
多个处理器共享一个存储器。
共享数据进入Cache产生了一个新的问题：Cache的一致性问题。
Cache一致性协议：目录式协议（物理存储器中数据块的共享状态被保存在一个称为目录的地方），监听式协议（每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息）。
写作废协议：在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其它的副本)。
写更新协议：当一个处理器对某数据项进行写入时，通过广播使其它Cache中所有对应于该数据项的副本进行更新。
监听协议实现
补充一下计组内容：
RdMiss，当一个处理器（P1）试图读取一个内存地址（A），但该地址对应的数据块不在其本地 Cache 中，或者在其 Cache 中的状态是 Invalid (I) 时，就会发生读缺失。
其他持有有效副本的 Cache，监听到 RdMiss 请求后，将最新的数据块写回主存，同时将其自身 Cache 中该块的状态降级为 **S (Shared)**。P1 收到数据后，将块状态设为 S。
WtMiss，当一个处理器（P1）试图写入一个内存地址（A），但该地址对应的数据块不在其本地 Cache 中，或者在其 Cache 中的状态是 Invalid (I) 时，就会发生写缺失。
发起 WtMiss 请求会要求系统中所有其他 Cache 作废（Invalidate）它们持有的地址 A 的任何有效副本，同时获取对目标数据块的独占所有权（状态变为 M）。
“发生替换”和“不发生替换”的关键在于：
- 目标位置的状态： 新数据块要放入的 Cache 行是否已经包含一个有效的（状态非
I）、且地址不同的数据块（旧块）。 - 旧块的状态： 如果要被替换的旧块是“脏的”（即状态为
M），则需要额外的操作（写回内存）来维护内存一致性。如果旧块是“干净的”（状态为S），则可以直接丢弃。
目录协议
背
计算机系统结构: 指程序员所看到的计算机属性，即概念性结构以及功能特性。
多功能流水线按照同一时间内各段之间的连接方式来分，流水线可分为静态流水线和动态流水线。
解决RAW的两种办法：定向，指令调度。
程序员包括下面四类：机器语言，操作系统，汇编语言，编译程序程序员。
系列机：由同一厂家生产的具有相同的系统结构，但具有不同组成和实现的一系列不同型号的机器。
实现可移植性的常用方法：采用系列机，模拟与仿真（使软件能在具有不同系统结构的机器之间相互移植），统一高级语言 。
兼容机：由不同公司厂家生产的具有相同系统结构的计算机 。
模拟：用软件的方法在一台现有的机器（称为宿主机）上实现另一台机器（称为虚拟机）的指令集。
仿真：用一台现有机器（宿主机）上的微程序去解释实现另一台机器（目标机）的指令集。
翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。
解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。
提高并行性的三种途径：时间重叠，资源重复，资源共享。
开发ILP（指令级并行）两种：资源重复，流水线。
开发指令级并行的方法主要有两类：基于硬件的动态开发方法以及基于软件的静态开发方法。
对于正常执行程序最重要的两个属性：数据流（数据从生产者到消费者指令的实际流动）和异常行为（改变指令顺序不改变异常发生的情况）。
前瞻执行的基本思想：执行指令的结果写入ROB中，等到指令确认之后再写入寄存器存储器。
基于硬件前瞻执行三种思想：动态分支预测；在控制相关结果尚未出来之前，前瞻的执行后续指令；动态调度进行跨基本块调度。
多发射处理机主要有超标量处理机、超流水处理机、超标量超流水处理机和超长指令字处理机。
超标量静态+动态，超长指令字只能静态。前者对程序员透明。
交换函数E，均匀洗牌σ（循环左移），碟式函数β（首尾交换），反位序函数ρ（倒序）。
通信时延：指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成，软件开销，通道时延，选路时延，竞争时延。
网络时延：通道时延与选路时延的和。
四种寻径方式：线路交换，存储转发，虚拟直通，虫蚀方式。
纵向处理：存储器存储器结构。
纵横处理：寄存器寄存器结构。
MIMD机器分为两类：集中式共享存储器结构（SMP对称式共享存储器多处理机，UMA机器），分布式存储器多处理机（优于集中式共享存储器结构）。
MIMD机器分为两类：集中式共享存储器结构（SMP对称式共享存储器多处理机，UMA机器），分布式存储器多处理机（优于集中式共享存储器结构）。
两种存储器系统结构：共享地址空间（分布式共享存储器系统DSM，NUMA机器）；把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。
两种通信机制：共享存储器通信机制，处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。消息传递通信机制，多个独立地址空间的计算机采用（分为同步和异步，同步发送一个消息后一直要等到应答结果才继续运行，异步通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方）。
动态网络：总线网络，多级互联网络，交叉开关网络。
Cache一致性协议：目录式协议（物理存储器中数据块的共享状态被保存在一个称为目录的地方），监听式协议（每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息）。
写作废协议：在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其它的副本)。
写更新协议：当一个处理器对某数据项进行写入时，通过广播使其它Cache中所有对应于该数据项的副本进行更新。
填空题
