计算机体系结构——4 指令级并行
4.1 指令级并行的概念4.1.1循环展开调度的基本方法
4.2 指令的动态调度4.3 控制相关的动态解决技术4.3.1 分支预测缓冲4.3.2 分支目标缓冲
4.4 多指令流出技术4.4.1 多指令概述4.4.2 超标量处理机4.4.3 超长指令字
4.1 指令级并行的概念
当指令之间不存在相关时,它们在流水线中是可以重叠起来并行执行的。这种指令序列中存在的潜在并行性称为指令级并行
Instruction-Level Parallelism简记为ILP 如何知道指令之间可以并行?硬、软件如何支持指令级并行?如何研究这些问题?
硬件技术或者软件技术都可以提高指令级并行性必须要硬件技术和软件技术互相配合,才能够最大限度地挖掘出程序中存在的指令级并行 流水线处理器的实际CPI(平均每条指令使用的周期数)等于理想流水线的CPI加上各类停顿引起的周期数的总和 CPI班水线=CPI理想 +停顿(结构相关) +停顿(先写后读) +停顿(先读后写) +停顿(写数写) +停顿(控制相关) 减少其中的任何一种停顿,都可以有效地减少CPI,从而提高流水线的性能
本章研究的技术和克服的停顿
基本(程序)块:一段除了入口和出口以外 不包含其它分支的线性代码段
程序平均每6~7条指令就会有一个分支必须在多个基本块之间开发指令级的并行性 循环级并行:循环体中指令之间的并行性开发循环级并行的基本技术方法
指令调度(scheduling)循环展开(loop unrolling)换名(renaming)
4.1.1循环展开调度的基本方法
循环展开是展开循环体若干次,将循环级并行转化为指令级并行的技术 这个过程既可以通过编译器静态完成,也可以通过硬件动态进行
开发循环级并行性的另外一个重要技术是向量处理技术具有向量处理指令的典型机器是向量计算机,有关向量处理和向量计算机的内容本章不作讨论 本章中的分支指令就是指条件转移指令
本章通用浮点流水线延迟表
编译器在完成这种指令调度时,受限于以下两个特性
一是程序固有的指令级并行性二是流水线功能部件的执行延迟 本章中使用的浮点流水线的延迟如下表
流水线其他特性说明
整数流水线采用改进的MIPS整数流水线
由于数据的取操作的结果可以毫无停顿的通过相关通路机制传送到数据存部件,所以延迟为0定向通道或旁路机制 分支指令,由整数流水线执行
分支条件检测调整到ID段如果分支指令使用上一条指令的结果作为分支条件,将要延迟1节拍分支指令有1个节拍的延迟槽 浮点运算一般为64位无结构冒险
循环展开实例
编译过程
每一遍循环之间是不存在相关的
多遍循环可以同时执行而不会导致结果的错误 变量分配寄存器
整数寄存器R1用作循环计数器,初值为向量中最高端地址元素的地址浮点寄存器F2用于保存常数S为简单起见,假定最低端元素的地址为8
否则需要另外的指令来将它和R1做比较
循环无调度执行
如果分支指令使用上一条指令的结果作为分支条件,将要延迟1节拍
循环无调度执行结果分析
每遍循环需要10个时钟节拍只有3个时钟节拍(L.D,ADD.D,S.D)
有效比率为30%空转5个时钟节拍(50%)循环控制2个时钟节拍(20%) 调度代码,减少空转
如何进行调度
通过一个好的编译器来调度可以
调换SUBI和SD的位置将SD指令移到BNEZ的延迟槽内改变SD存取指令访问内存地址的偏移量
调度代码结果分析
每遍循环6个时钟节拍和未调度代码比较,加速比10/6=1.73个有效时钟节拍(L.D,ADD.D,S.D)
节拍有效比率50%1拍空转(占17%)2拍循环控制(占33%) 如何进一步减少空转和循环控制占用的比率?
循环展开 结果分析
循环使用28个时钟节拍
14个空转节拍
每个L.D有1个空转个节拍-共4拍每个ADD.D有2个空转节拍-共8拍DADDUI有1个空转节拍-共1拍BRANCH有1个空转节拍–共1拍 有14个指令流出节拍 每遍循环7个时钟节拍共计使用9个寄存器
循环展开总结
对指令进行移动是有效的展开是有用的用不同的寄存器
换名更多的寄存器 消除额外的测试开销在循环展开时分析LOAD/STORE指令进行内存地址换名保留真相关(先写后读相关必须进行保留)
4.2 指令的动态调度
编译器本质上通过对每个循环迭代中寄存器重命名来展开循环硬件也可通过寄存器重命名和乱序执行来获得同样的效果动态调度
记分牌Tomasulo’s算法
冒险的检测和调度
如果存在数据相关,硬件检测机制会做如下的事情知道相关消除动态调度
暂停指令停止取指令和发射指令 静态调度(开始于60s,流行于80s)消除动态调度
软件来负责调度指令 减少空转 动态调度
硬件对指令的执行重新排序来减少空转
动态调度
动态调度的目的在程序执行的时候,解决WAW,WAR和RAW 带来的冒险优点:
处理在编译的时候未知的相关,简化编译器在不同的流水线上都能有效的运行 缺点:
很大地增加了硬件的复杂性 两个动态调度技术
记分牌Tomasulo算法
记分牌
记分牌1964被Cray用于CDC 6600记分牌允许指令乱序执行,前提
充足的资源,无数据相关记分牌动态解决了先写后读相关指令可以乱序执行 基本原理
每条指令均经过记分牌,记录各指令间数据相关的信息如果记分牌判断出一条指令不能立即执行,它就检测硬件的变化从而决定何时能够执行
记分牌处理
流水线ID段被分为两级
流出一解析指令,检查结构相关读操作数一直到不存在数据相关时,才读取操作数 如果存在WAR或者WAW相关,记分牌会暂停这条指令的执行,直到相关消除后才继续执行
记分牌执行过程
流出(Issue)
本指令所需的功能部件有空闲正在执行指令使用的目的寄存器与本指令不同
保证WAW相关 读操作数(Read operands)
前面已流出的还在运行的指令不对本指令的源操作数寄存器进行写操作一个正在工作的功能部件已经完成了对这个寄存器的写操作动态解决RAW相关 前面两步完成了原来ID段的功能 执行(Execution)
开始于取到操作数后当结果产生后,修改记分牌FP流水部件会占用多个周期 写结果(Write result):
检查WAR相关 出现以下情况时,不允许指令写结果:
前面的某条指令还没有读取操作数其中某个源操作数寄存器与本指令的目的寄存器相同
记分牌结构
功能部件状态表用9个域来记录每个功能部件的状态
Busy:指示功能部件是否工作Op:功能部件当前执行的操作Fi:目的寄存器编号Fj,Fk:源寄存器编号Qj,Qk:向Rj,Rk中写结果的功能部件 ,Rj,Rk:标示Fj,Fk是否就绪,是否已经被使用
数据结构:程序实例
Tomasulo算法产生的背景
IBM 360/91比CDC6600晚三年推出
商业计算机使用Cache技术之前 整个360系列仅一个指令系统和一个编译器
要求具有很高的浮点性能,但不是通过高端机器 的专用的编译器实现只有四个双精度浮点寄存器,编译器调度的有效性受到很大限制访存时间和浮点计算时间都很长可支持循环的多次迭代重叠执行
Tomasulo算法与记分牌
采用了许多记分牌中的理念两个较大的差异Tomasulo算法中,冲突检测和执行控制是分布的,利用保留站实现Tomasulo算法不检查WAR和WAW相关,他们通过算法本身消除掉了 流出(Issue)1、从浮点指令队列中取出一条指令2、如果存在一个空的保留站,就流出这条指令3、如果操作数在寄存器中,就送到该指令对应 的保留站4、存储器取/存指令只要有空闲的缓存就可以 流出5、如果没有空闲的保留站或者缓存,就存在结 构相关,指令暂停,直到有空闲的保留站或者缓存
执行和结果写回
执行(Execute) 1、如果缺少一个或者多个操作数,就监听CBD
这个阶段实际是检测和自动维护RAW相关 2、如果两个操作数都就绪,这条指令就可以执行 结果写回(Write result) 1、如果结果已经产生,将其写到CBD上 2、通过CDB,把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站
4.3 控制相关的动态解决技术
4.3.1 分支预测缓冲
因为整数程序线性代码更多,浮点程序一般用来计算,所以浮点的循环更多,所以浮点运算失效率更低。
4.3.2 分支目标缓冲
4.4 多指令流出技术
4.4.1 多指令概述
4.4.2 超标量处理机
4.4.3 超长指令字
推荐文章
发表评论