计算机系统结构

计算机系统结构1流水线的结构相关结构相关：如果指令在流水线重叠执行过程中，硬件资源满足不了指令重叠执行的要求，会产生资源冲突或竞争，称为流水线结构相关。

指令执行Load、Store：存储器操作指令ALU：运算BRANCH转移控制部件：执行转移指令第2页,共39页，2024年2月25日，星期天表2.1不同类型指令中各流水段的操作IF：按指令计数器内容访问主存，指令送到寄存器ID：指令译码。读寄存器IE：形成操作数地址ME:访问主存读取操作数----常与取指发生结构冲突WB:读出结果写回寄存器。结构相关常常发生在存储器操作指令load/store

第3页,共39页，2024年2月25日，星期天

假定流水线中有五条指令I1,I2,I3,I4,I5.非流水机器中，指令顺序执行，资源不会冲突。流水线执行时，系统资源可能发生冲突。LOAD中

ME:访问主存

IF:（主存中）取指令延迟技术：使某些指令延迟、停顿一或多个时钟周期第4页,共39页，2024年2月25日，星期天解决存储器争用冲突的办法延迟技术：使某些指令延迟、停顿一或多个时钟周期双端口存储器：允许同时读两个数据或指令双存储器（哈弗结构）：一个数据存储，一个指令存储。4软件优化编译：指令重新排序消除结构相关。其它功能部件的结构相关，解决冲突办法与上述思路类似。第5页,共39页，2024年2月25日，星期天2流水线的数据相关

流水线中，多条指令并行执行，程序在实际执行中可能导致数据供求关系上产生冲突(违反了原定的次序)，称为数据相关。

如以下两条指令：

ADD

R1，R2，R3；(R2)＋(R3)→R1SUBR4，R1，R5；(R1)－(R5)→R4第6页,共39页，2024年2月25日，星期天

指令在流水线中执行时,可能改变指令读／写操作数顺序ID：读寄存器R1

先写后读WR

第7页,共39页，2024年2月25日，星期天数据相关及其避免方法1后推法：遇到数据相关时，停顿后继指令的执行，直至前指令结果产生。2定向技术：又称旁路技术或专用通路技术，想法是使后续指令提前得到前指令(ALU类）结果。3

联锁硬件(适合存储器操作load,store指令）:4软件法（静态指令调度）：采用优化编译，通过指令重新排序方法来消除数据相关。

第8页,共39页，2024年2月25日，星期天定向技术解决数据相关的ALU方案通过专门电路将该运算结果提前送到有关缓冲寄存器。供后续指令执行（得到需要的操作数）。适合ALU类指令。第9页,共39页，2024年2月25日，星期天采用定向技术解决数据相关

ME:空操作WB：写回适合ALU类指令!第10页,共39页，2024年2月25日，星期天3

采用联锁硬件解决数据相关

定向传送技术来不及用时，可通过流水线联锁硬件，使某些指令或流水段暂停流动一或多个周期，再用定向传送技术。又称为空闲周期。

第11页,共39页，2024年2月25日，星期天

4软件法（静态指令调度）：优化编译法，通过指令重新排尽可能消除数据相关。

如ADD

R1，R2，R3；SUBR4，R1，R5；改为ADD

R1，R2，R3；………

SUBR4，R1，R5；使两条“相关”指令“分开”

第12页,共39页，2024年2月25日，星期天【例】假设某指令序列中20%的指令是LOAD指令，且紧跟LOAD指令之后的半数指令使用到LOAD指令载入的结果。如果这种数据相关将产生一个时钟周期的延迟，问理想流水线(没有任何延迟，CPI为1)的指令执行速度要比这种真实流水线快多少?

解：假定问理想流水线(没延迟）的CPI为1。LOAD指令之后的半数指令需要暂停，CPI为2。又知LOAD指令占全部指令的20%，所以真实流水线的实际CPI为

第13页,共39页，2024年2月25日，星期天2.4流水线控制相关

流水线控制相关：指因程序执行转移类指令而引起的冲突相关。包括无条件转移、条件转移、子程序调用、中断等，它们属分支指令，执行中可能改变程序方向，造成流水线断流。与数据相关相比,控制相关会引起程序执行方向的改变，使流水线损失更大，称为全局相关。全局相关结构图如下图所示。这里程序划分为三个部分B0,B1和B2

，

每一部分内不再有分支操作指令，称为一个基本块（basicblock）。第14页,共39页，2024年2月25日，星期天流水线控制相关流水线中条件转移类执行时，有两种结果：

1.发生转移，将程序计数器PC内容改成转移目标地址；

2.不发生转移，PC指向下一条指令地址。条件转移指令往往要在流水线末端时转移条件才能建立。流水线性能会大幅度下降。从相关角度看，条件转移指令或中断指令与后续指令存在着一种控制上的全局相关。第15页,共39页，2024年2月25日，星期天条件转移指令对流水线的影响

图中条件转移指令（BRANCH)通常要在ME段末尾才会使PC内容发生改变，流水线需停顿3个时钟，直到PC中生成新地址后，才能取出下一条指令。

在最坏情况，条件转移造成k-1个时钟周期的停顿第16页,共39页，2024年2月25日，星期天转移指令对性能的影响

设一有k个流水段的流水线，执行n条指令设条件转移指令在程序中所占的比例为p，转移成功概率为q。在最坏情况，一次转移造成k-1个时钟周期的“断流”。n条指令的程序，条件转移需要额外增加的时钟周期数是pqn(k-1)Δt，因条件转移,完成n条指令的总执行时间

第17页,共39页，2024年2月25日，星期天转移指令对性能的影响

相应的流水线吞吐率为

当n→∞时，流水线最大吞吐率为（分析公式意义）

流水线吞吐率下降率为

第18页,共39页，2024年2月25日，星期天【例】据统计，在一些典型程序中，转移指令所占的比例为20%，转移成功的概率为q＝60%。假设有一条8个流水段的指令流水线，问：由于条件转移指令的影响，流水线的最大吞吐率下降多少?

解：已知p＝0.20,q＝0.60

k＝8

根据则第19页,共39页，2024年2月25日，星期天静态分支技术静态转移预测技术(猜测法)提前形成条件码，生成转移目标地址延迟转移改进循环程序硬件上计算两个PC值(转移成功或失败)。动态分支预测技术“转移历史表”BHT。“转移目标缓冲栈”（BTB）转移目标指令缓冲栈BTIB。控制相关的解决方法第20页,共39页，2024年2月25日，星期天1静态转移预测技术：条件转移指令出现时，对条件转移方向进行预测（或转移成功或不成功）。按预测方向设置指令缓冲栈并预取指令。程序执行过程中，静态预测转移的方向变。静态转移预测可用硬件，也可软件实现。可以在转移的两个方向上都采取预取指令。第21页,共39页，2024年2月25日，星期天遇条件转移时，用“猜测法”选择一个分支方向。选择“转移不成功”方向。控制逻辑简单。“猜测”不正确，已执行多个流水段将浪费。静态转移预测技术

第22页,共39页，2024年2月25日，星期天2提前形成条件码，生成转移目标地址条件转移指令BRANCH通常要在ME形成条件转移地址。多数情况下，可以提前判别转移是否发生或形成条件转移代码。一些运算型条件转移指令，在实际运算前（ID)或运算中间(EX)就能产生条件码。不必等运算结束。把计算转移目标地址操作移到ID段完成.

静态分支技术

第23页,共39页，2024年2月25日，星期天3延迟转移：遇转移指令时，依靠编译器把一条或几条与转移结果无关的指令调度到转移指令后面（调度槽），以延长转移指令的可执行时间，这些调度指令完成后，转移指令的目的地址已计算出来。调度到转移指令后的无关指令须遵循有效和有用的原则。延迟转移要求流水线段数不能太多，段数越多，调度到转移指令后的“无关指令”也要愈多。没有合适指令调度时，无关指令可以是空操作。静态分支技术第24页,共39页，2024年2月25日，星期天“延迟转移”下的调度模式

调度的ADD字指令必须满足：1无关性。2有用性。3有效性

第25页,共39页，2024年2月25日，星期天“延迟转移”下的流水线时空图转移延迟槽中的指令“填补”了流水线原来须插入的暂停周期。假定把计算转移目标地址操作已移到ID段完成.

第26页,共39页，2024年2月25日，星期天4改进循环程序：

循环操作是程序中广泛使用的一种条件转移。条件转移是否结束，取决于循环操作是否达到规定次数。

一般转移不成功时，转移指令对流水线的影响较小。因此,对给定的程序，转移成功的概率越高，则对流水线的影响越大。编译器在对源程序进行编译时，通过提高循环程序中转移不成功的概率。

第27页,共39页，2024年2月25日，星期天i>0转移（概率大）i=0转移（概率小）

第28页,共39页，2024年2月25日，星期天5硬件上设置两个指令缓冲栈

当指令分析器分析到条件转移指令时，设置两个指令缓冲栈指令缓冲栈A——按转移不成功方向预取指令，指令缓冲栈B——按转移成功的方向预取指令。

当转移条件码产生时，转移不成功，分析A中的指令；否则,分析B中指令第29页,共39页，2024年2月25日，星期天动态分支预测技术

从转移指令近期转移是否成功的记录，预测下一次转移的方向。称为动态分支预测技术.一、如何记录转移历史信息根据记录的转移历史信息，预测转移方向。

记录转移历史信息的方法通常有三种：把最近几次转移或不转移的信息记录在一个“转移历史表”BHT。把最近几次转移或不转移的信息记录在一个“转移目标缓冲栈”（BTB）。第三种是存放在一个转移目标指令缓冲栈BTIB。第30页,共39页，2024年2月25日，星期天1

使用BHT的转移预测BHT格式：

[转移指令，历史表信息，转移目标指令(地址）]执行转移指令时，转移成功或转移失败的信息可记录在一个所谓的“转移历史表”BHT中。一个二进制位记录最近一次转移是否成功的信息。多个二进制位记录最近几次转移是否成功的信息。无论预测的转移方向与实际执行结果的转移方向是否相同，都要修改“转移历史表”BHT。为兼顾预测效果和便于硬件实现，常用2位计数器来记录最近二次转移是否成功的信息。第31页,共39页，2024年2月25日，星期天用二进制数字10、11、01、00来表示转移预测状态的转换图转移取：转移顺序取：不转移第32页,共39页，2024年2月25日，星期天转移历史表BHT的硬件逻辑结构

第33页,共39页，2024年2月25日，星期天优点:转移预测提前到取指阶段。预测正确，则没有任何延迟损失。预测不正确，则清除指令预取(队列)缓冲器。会产生延迟时间损失.当执行转移指令时，把转移成功与不成功的信息记录在“转移历史表”中。当一条转移指令第一次执行时，没有历史转移记录，这时可预置转移历史信息。

BHT方法可以同I-cache（指令cache）结合起来。BHT的转移预测第34页,共39页，2024年2月25日，星期天

用转移目标缓冲栈（BTB）的转移预测使用转移目标缓冲栈作为转移预测策略。把BHT中转移指令字段改为转移指令地址

BTB格式[转移指令地址，历史表信息，转移目标指令地址]一般在译码分析阶段得到转移指令地址

第35页,共39页，2024年2月25日，星期天使用转移目标指令缓冲栈(BTIB)转移指令在指令分析部件中译码时，转移不成功方向的指令已被预取到指令缓冲栈中，或者已经存放在I-cache中。在转移成功方向上也预取一部分指令，把BTB中的“转移目标地址”改为存放转移目标地址之后的n条指令。这种预测称为转移目标指令缓冲栈BTIB。

第36页,共39页，2024年2月25日，星期天例题：在一台单流水线处理机上执行下面程序。指令经过“取指”、“译码”、“执行”、“写结果”四个流水段，每个流水段延迟时间是5ns。但“执行”流水段LS部件和ALU部件只能有一个工作，LS部件完成LOAD和STORE操作，ALU部件完成其它操作。两个操作部件的输出端和输入端有直接输出通路相互切换连接，ALU部件产生的条件码能直接送入控制器。假定采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图.

I1SUBR0，R0