好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

计算机系统结构:第五章 标量处理机.ppt

197页
  • 卖家[上传人]:汽***
  • 文档编号:573177480
  • 上传时间:2024-08-14
  • 文档格式:PPT
  • 文档大小:3.05MB
  • / 197 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • tiger September 20141计算机系统结构n第一章 基本概念n第二章 指令系统n第三章 存储系统n第四章 输入输出系统**n第五章 标量处理机n第六章 向量处理机n第七章 互连网络n第八章 并行处理机n第九章 多处理机 tiger September 20142并行n两种并行性概念n同时性并行Simultaneity: 两个或两个以上事件在同一时刻发生n并发性并行Concurrency: 两个或两个以上事件在同一时间间隔内发生n三条技术途径n资源重复(空间并行性,同时性并行): 重复设置多个处理部件来提高速度n时间重叠(时间并行性,并发性并行): 流水线n资源共享: 分时系统,分布式系统n时间---空间关系n资源重复(空间并行性,同时性并行): 增加空间以多个空间容纳多条指令n时间重叠(时间并行性,并发性并行): 细分空间以多个子空间容纳多条指令 tiger September 20143第五章 标量处理机n标量处理机n只有标量数据表示和标量指令系统的处理机n提高指令执行速度的主要途径n提高处理机的工作主频n采用更好的算法和设计更好的功能部件n采用指令级并行技术n三种指令级并行处理机n流水线处理机和超流水线(Super-pipelining)处理机n超标量(Superscalar)处理机n超长指令字(VLIW: Very Long Instruction Word)处理机n同时性并行?并发性并行?n四种基本技术n先行控制技术n流水线技术n相关性分析技术n动态调度技术 tiger September 20144本章主要内容n5.1 先行控制技术n5.2 流水线技术n5.1.4,5.2.6 相关性分析技术n5.1.3,5.2.5 动态调度技术n5.3.1 超标量处理机n5.3.2 超流水线处理机n5.3.3 超标量超流水线处理机 tiger September 201455.1 先行控制技术n先行控制(Lookahead)技术最早在IBM公司的STRETCH机器中采用n先行控制技术的关键n缓冲技术n预处理技术n(目前,许多处理机中都已经采用了先行控制技术) tiger September 201465.1 先行控制技术n5.1.1 指令的重叠执行方式n1 顺序执行方式n执行n条指令所用的时间n如每段时间都为t,则执行n条指令所用的时间nT=3ntn主要优点:控制简单,节省设备n主要缺点:执行指令的速度慢,功能部件的利用率低取指令k分析k 执行k取指令k+1分析k+1 执行k+1 tiger September 201472 一次重叠执行方式n如果两个过程的时间相等,则执行n条指令的时间nT=(1+2n)tn一种最简单的流水线方式 n主要优点n指令的执行时间缩短n功能部件的利用率明显提高n主要缺点n需要增加一些硬件n控制过程稍复杂取指k分析k执行k取指k+1 分析k+1 执行k+1取指k+2 分析k+2 执行k+2 tiger September 201483 二次重叠执行方式n如果三过程的时间相等,执行n条指令的时间:T=(2+n)tn理想情况下同时有三条指令在执行n处理机的结构要作比较大的改变,必须采用先行控制方式取指k+2分析k+2执行k+2取指k+1分析k+1执行k+1取指k分析k执行k tiger September 20149n1 采用二次重叠执行方式,必须解决两个问题n(1) 有独立的取指令部件、指令分析部件和指令执行部件n一个集中的指令控制器要分解成三个相对独立的控制器n存储控制器、指令控制器、运算控制器n(2) 解决访问主存储器的冲突问题n取指令、分析指令、执行指令都可能要访问存储器5.1.2 先行控制方式的原理和结构 tiger September 201410n(1) 两个独立的存储器:独立的指令存储器和数据存储器n如果再规定,执行指令所需的操作数和执行结果只写到通用寄存器,那么,取指令、分析指令和执行指令就可同时进行n许多高性能处理机中,有独立的指令Cache和数据Cache。

      这种结构被称为哈佛结构n(2) 采用低位交叉存取方式n不能根本解决冲突问题n取指令、读操作数、写结果n(3) 采用先行控制技术n关键是缓冲技术和预处理技术n缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈,用以平滑它们的工作n预处理技术把进入运算器的指令都处理成RR型指令n运算器能够专心于数据的运算,从而大幅度提高程序的执行速度2 解决访存冲突的方法 tiger September 2014115.1.2.1 处理机结构n处理机内部设置一定容量的指令缓冲栈n指令分析器所需的指令事先取到指令缓冲栈,不必访问主存储器n取指令、分析指令和执行指令重叠执行 n三个独立的控制器n存储控制器、指令控制器、运算控制器n四个缓冲栈n先行指令缓冲栈、先行操作栈、先行读数缓冲栈、 后行写数栈 tiger September 201412先行指令缓冲栈的组成n只要指令缓冲栈没有充满,就自动发出取指令的请求n设置两个程序计数器n现行程序计数器PC,记录指令分析器正在分析的指令地址n先行程序计数器PC1,用来指示取指令 tiger September 201413先行控制方式中的一次重叠执行 n指令分析器每次取指令能在先行指令缓冲栈中得到,则取指令只需很短的时间就能完成n可把取指令与分析指令合并到一起n构成一次重叠执行方式n存在的主要问题n(1) 各类指令“分析”和“执行”所需要的时间相差很大n(2) 数据相关和变址相关n(3) 转移或转子程序指令n本节及以后两节逐个解决分析k执行k分析k+1 执行k+1分析k+2 执行k+2 tiger September 2014145.1.2.2 先行控制方式的指令执行时序n设置了指令缓冲栈,取指令的时间可忽略不计n1 一次重叠执行方式,分析指令和执行指令时间不相等时n2 采用先行缓冲栈的指令执行过程n4个先行缓冲栈:先行指令缓冲栈、先行操作栈、先行读数栈、后行写数栈 tiger September 2014153 指令执行过程的时空图表示方法n指令执行过程的另一种形式的时空图表示n理想情况下,指令执行部件应一直忙碌n连续执行n条指令的时间 tiger September 2014165.1.2.3 先行缓冲栈n设置先行缓冲栈的目的:使指令分析器和指令执行部件各自独立工作n1 先行指令缓冲栈n2 先行操作栈n3 先行读数栈n4 后行写数栈 tiger September 2014171 先行指令缓冲栈n位置:主存储器与指令分析器之间n作用:平滑主存储器取指令和指令分析器的工作n指令分析器从先行指令缓冲栈取指令n运算、移位、数据传送等指令处理成RR型指令,送入先行操作栈nRR型指令,不必处理,直接送先行操作栈nRS和RX型指令,主存有效地址送先行读数栈,用该先行读数栈的寄存器编号替换指令中的主存地址码部分,形成RR*指令送先行操作栈nRI型指令,指令中的立即数送先行读数栈,用该先行读数栈的寄存器编号替换指令中的立即数部分,形成RR*指令送先行操作栈n“吸收型”指令---在指令分析器中直接执行n无条件转移及条件转移指令 tiger September 2014182 先行操作栈n位置:指令分析器和运算控制器之间n作用:使指令分析器和运算器各自独立工作n工作过程n采用先进先出方式工作,由先行指令寄存器堆和控制逻辑组成 tiger September 2014193 先行读数栈n位置:主存储器与运算器之间n作用:平滑运算器与主存储器的工作n工作过程n每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成n也可把地址寄存器和操作数寄存器合为一个n当收到从指令分析器中送来的有效地址时,就向主存申请读操作数n读出的操作数存放在操作数缓冲寄存器中或覆盖掉地址寄存器中的地址 tiger September 2014204 后行写数栈n每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三个部分组成n指令分析器遇到向主存写结果的指令,把形成的有效地址送入后行写数栈的地址寄存器中,并用该地址寄存器的编号替换指令的目的地址部分,形成RR*指令送入先行操作栈n运算器执行这条RR*型写数指令时,只要把写到主存的数据送到后行写数栈的数据寄存器中即可 tiger September 2014215 在采用先行控制方式的处理机中,一个程序的执行情况指令地址指令地址指令指令执行情况行情况......k-i-1已执行完成的指令k-i......k-1在“后行写数栈”中等待把结果写到主存储器中的指令(等待运算结果的写数指令已包含在k...k+j+n等以下几行,不再单独出现)k正在“指令执行部件”中执行的指令k+1......k+j已由“指令分析器”预处理完成,被存放在“先行操作栈”中的RR*型指令,指令所需要的操作数也已读到“先行读数栈”中k+j+1......k+j+n指令已由“指令分析器”预处理完成,存放在“先行操作栈”中,指令所需要的操作数还没有读到“先行读数栈”中k+j+n+1正在“指令分析器”中进行分析和预处理的指令k+j+n+2......k+j+n+m已从主存储器中预取到“先行指令缓冲栈”中的指令k+j+n+m+1......还没有进入处理机的指令 tiger September 2014225.1.3 数据相关 n相关correlation: 相邻或相近的两条指令存在某种关系,可能影响指令的重叠执行,后一条指令不能在原定的时钟周期执行n数据相关n执行本条指令的过程中,用到的指令、操作数、变址量等正好是前面指令的执行结果n须等待前面的指令执行完成,并把结果写到主存或寄存器后,本条指令才能开始执行n控制相关n条件分支指令、转子程序指令、中断等引起的相关n数据相关有四种n指令相关n主存操作数相关n通用寄存器相关n变址相关n解决数据相关的方法有两种n推后分析法n设置专用路径法 tiger September 2014235.1.3.1 指令相关n发生指令相关n n: STORE R1, n+1nn+1: ……n满足关系: 结果地址(n)=指令地址(n+1)n当第n条指令把执行结果写到主存前,取出的第n+1条指令显然是错误的 tiger September 201424指令相关n造成的后果n采用k个流水段的流水线处理机中,第n条指令修改从第n+1到第n+k指令中的任意一条指令,都可能造成程序执行结果发生错误n采用先行控制方式的处理机中,如果执行部件正在执行第n条指令,与下面的任意一条指令发生相关,都可能造成程序执行结果发生错误n已经存放在先行操作栈中的指令n正在指令分析器中进行预处理指令n已经预取到先行指令缓冲栈中的指令n更为严重的是:有一些“吸收型”指令,已在指令分析器执行完成 tiger September 201425解决指令相关的根本办法n在程序设计中不允许修改指令n现代程序设计方法要求程序具有再入性,可被递归调用nIBM 370机中,用“执行指令”来解决指令相关n“执行指令”本身并不执行,它执行的是由第二地址((X2)+(B2)+D2)决定的主存单元中的指令。

      这个主存单元一般不在指令区,而是在数据区 tiger September 2014265.1.3.2 主存操作数相关n发生主存操作数相关的指令序列n指令执行结果写到主存,所需要的操作数也来自主存n n: OP A1, A2, A3 ;A1=(A2) OP (A3)nn+1: OP A1, A2, A3 ;A1=(A2) OP (A3)n出现下列两种情况之一时,发生主存操作数相关nA1(n)=A2(n+1)nA1(n)=A3(n+1) tiger September 201427 解决办法n运算结果写到通用寄存器,而不写到主存n对于访问主存储器的请求,写结果的优先级高于读操作数n对设置有先行操作栈的处理机,解决操作数相关的办法n刚进入先行操作栈中的指令在向主存读操作数之前,先把访问主存的地址与后行写数栈中的所有主存地址进行比较n如发现有相等的,则先行操作栈的读操作数要暂缓进行,等到发生操作数相关的指令执行完成,并把结果写回到主存之后再开始读操作数 tiger September 2014285.1.3.3 通用寄存器数据相关 n发生通用寄存器数据相关n发生的可能性最大,影响面也最大的一种数据相关n n: OP R1, A2 ;R1=(R1) OP (A2)nn+1: OP R1, R2 ;R1=(R1) OP (R2)n如果发生:R1(n)=R1(n+1),称为R1数据相关n如果发生:R1(n)=R2(n+1),称为R2数据相关n比R1数据相关晚1T tiger September 201429解决通用寄存器数据相关的方法n方法一 寄存器到运算器有直接数据通路n读操作数、写运算结果与指令执行合在一个节拍n数据从寄存器读出,在运算器中完成运算,结果写回寄存器的整个回路中,只有寄存器是时序逻辑n寄存器个数和操作部件个数不多时,是一种最常用的方法n存在问题n寄存器个数比较多时,读、写寄存器的时间长n功能部件数量比较多时,寄存器堆的读写端口很多。

      必须使用多级多路选择器 tiger September 201430n方法二 分析指令推后一个(机器)周期n下一指令分析阶段读操作数推后到上一指令执行阶段写结果后一周期n串行进行n速度损失大n方法三 分析指令推后一个节拍(T4+)n下一指令分析阶段读操作数推后到上一指令执行阶段写结果后一节拍 tiger September 201431方法四 设置专用数据通路n在运算器的入口处增加两个锁存器 tiger September 201432n第k条指令的执行结果,如果写回寄存器堆,然后再读出来,则第k+1条指令须推后两个周期n增加相关专用通路后,第k+1条指令的执行不必推后节省了两个时钟周期n通用寄存器数据相关出现的概率很高,增加一条相关专用通路是合适的n指令的执行结果在写回到通用寄存器的时候,同时也写入运算器入口处的锁存器n数据从锁存器读出,在运算器中完成运算,结果再写入锁存器的整个回路中,只有锁存器是时序逻辑 tiger September 2014335.1.3.4 变址相关 n采用变址方式的处理机,变址偏移量放在寄存器,与通用寄存器的数据相关类似,有可能发生变址相关n通用寄存器作变址寄存器,指令分析时用来计算有效地址n k: OP R1, R2; R1=(R1) OP (R2)nk+1: OP R1, A2(X2); R1=(R1) OP ((A2) + (X2))nk+2: OP R1, A2(X2) ; R1=(R1) OP ((A2) + (X2))n如果发生:R1(k)= X2(k+1)称为一次变址相关n如果发生:R1(k)= X2(k+2)称为二次变址相关n比一次变址相关多间隔一条指令的时间n变址相关专用通路 tiger September 2014345.1.3.a LOAD相关 nRISC处理机中,只有LOAD操作能访问存储器nLOAD操作的执行时间可能比较长n n: LOAD R1, A;R1=(A)nn+1: ADD R2, R1;R2=(R1) OP (R2)n如果R1(n)=R1(n+1),则发生LOAD数据相关(主存读且R1写)n解决方法n方法一:由编译器在LOAD之后插入不发生数据相关的指令n由于LOAD操作的执行时间不能确定,依靠插入指令不能根本解决问题n方法二:由硬件自动插入空操作,直到LOAD操作完成n只有一条流水线的处理机中,可采用停止节拍发生器的方法,直到存储器的回答信号到来,再启动节拍发生器 tiger September 201435各种数据相关的三种主要解决方法n1 采用硬件或软件的办法尽量避免数据相关发生n例如,为了避免通用寄存器数据相关,采用D型触发器构成通用寄存器堆,且通用寄存器堆在一个节拍中能够读出两个操作数并写回一个结果n2 在确保指令正确执行的前提下,推后指令分析n3 设置相关专用通路来解决数据相关 tiger September 2014365.1.4 控制相关n程序的执行方向可能被改变而引起的相关n可能改变程序执行方向的指令n无条件转移n一般条件转移n复合条件转移n子程序调用、中断n数据相关称为局部相关,影响到的仅仅是本条指令附近的少数几条指令n控制相关称为全局相关,影响的范围要大得多,它可能引起程序执行方向的改变 tiger September 2014375.1.4.1 无条件转移 n无条件转移指令在程序中一般如下  k: …… k+1: JMP L …: …… L: ……n流水线处理机中,无条件转移指令不进入执行流水段,一般在指令译码(或称为指令分析)阶段就实际执行完成 n如果在处理机中设置有先行指令缓冲栈,无条件转移指令一般能够在指令分析阶段就执行完成,形成转移地址L同时送入先行程序计数器PC1和现行程序计数器PC中,指令缓冲栈按照PC1的指示重新开始向存储控制器申请取指令 tiger September 2014385.1.4.1 无条件转移n转移距离比较远n指令L不在指令缓冲栈中,则要将指令缓冲栈中的所有指令全部作废n指令分析器要等待一个“取指令L”周期之后才能开始“分析L”n转移距离比较近n有可能指令L已经被取到了指令缓冲栈中n作废指令缓冲栈中的部分指令,即作废从k+2到L-1之间的所有指令n指令分析器完成“分析k+1”后,可接着进行“分析L”,即指令分析器仍可不停顿地连续工作 tiger September 2014395.1.4.1 无条件转移n设置有先行操作栈的处理机中,无条件转移指令一般对指令执行部件的工作不会造成影响n为进一步减少无条件转移指令造成的影响,在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器。

      就不会再发生作废先行缓冲栈中指令的情况 tiger September 2014405.1.4.2 一般条件转移 n条件转移指令有两种n一般条件转移指令的转移条件来自上一条指令,或更前面的指令n复合型条件转移指令直接根据本条指令的执行结果决定是否转移n k: ……;置条件码CC k+1: JMP(CC) L;CC为真转向L,否则继续执行k+2 k+2: …… ...: …… L: …… tiger September 2014415.1.4.2 一般条件转移n一般条件转移指令,相关最严重的情况发生在条件码是由上一条指令产生的n条件码要直到先行操作栈中的指令全部完成,在“执行k”的末尾才能形成n“分析k+1”在一开始就要根据条件码判断转移条件是否成立n指令分析器分析到条件转移指令时,必须停下来等待所需的条件码 tiger September 2014425.1.4.2 一般条件转移n无论转移是否成功,条件转移指令都在指令分析阶段就已执行完成n如果转移不成功n分析k+2n如果转移成功n指令L已经在先行指令缓冲栈,指令分析器接着“分析L”n指令L不在先行指令缓冲栈,指令分析器要等待一个周期n转移不成功,对程序执行影响不大n转移成功时,指令执行过程变成完全串行,而且要作废先行指令缓冲栈中的大量指令n采用流水线方式的处理机中,通过软件与硬件的多种手段来尽可能地降低转移成功的概率,减少转移成功造成的影响 tiger September 2014435.1.4.3 复合条件转移 n复合型条件转移指令本身就是一条运算指令,根据本条指令的运算结果决定是否转移n复合型条件转移指令的执行时间关系n k:OP L ;先执行OP操作n ;根据执行结果产生的条件码决定是否转向Lnk+1: ……n …: ……n L: ……n复合型条件转移指令不能在指令分析器中执行完成,须象其它运算型指令一样经指令执行部件执行n无条件转移指令和一般条件转移指令能在指令分析器中执行完成,称为吸收型指令 tiger September 2014445.1.4.3 复合条件转移n转移不成功n不造成任何影响,复合型条件转移指令就象一条普通的运算型指令一样n转移成功n造成的影响比一般条件转移指令还要大得多n全部或部分作废先行指令缓冲栈中已经预取的指令n全部或部分作废先行操作栈中的指令和先行读数栈中的操作数n可能作废当前在指令分析器中分析的指令 tiger September 201445!n数据相关数据引用的正确性指令分析器---运算器n控制相关指令流动的正确性n无条件转移先行指令缓冲栈n一般条件转移先行指令缓冲栈等待条件码n复合条件转移运算器---先行指令缓冲栈 tiger September 2014465.1.4.4 转移预测技术 nRISC关键技术n延迟转移技术(p118)n指令取消技术(p119)n静态分支预测n在程序执行过程中,转移预测的方向不能改变n动态分支预测n在程序执行过程中,能够动态地改变转移预测方向 tiger September 2014471 软件“猜测法” n转移不成功时,条件转移指令对流水线的影响比较小n编译器在对源程序进行编译时,为了达到比较好的效果,要尽量降低转移成功出现的概率n优点:不需要改变硬件结构,只要适当修改编译器就能够大幅度降低条件转移指令的影响n主要目的:通过编译器尽量降低转移成功的概率 tiger September 2014481 软件“猜测法”n例如:对于普通的循环程序,一般编译器生成的目标代码,转移成功的概率很高,不成功的只有一次。

      这种编译结果对流水线的影响非常大 tiger September 2014492 硬件“猜测法”n基本原理n通过改变硬件结构来降低转移指令对流水线造成的影响n实现方法n在先行指令缓冲栈的入口处设置一个简单的指令分析器,当这个指令分析器检测到转移指令时,就把转移目标地址L送入先行程序计数器PC1中,同时保留当前PC1中的内容到另一寄存器中n转移成功,则猜测正确转移指令对流水线不造成影响n转移不成功,用保存下来的地址恢复PC1和PC中的内容,清除先行指令缓冲栈、先行操作栈、先行读数栈,并重新开始取指令n软件和硬件要共同配合,软件与硬件都往同一个方向去猜测 tiger September 2014503 两个指令缓冲栈n原因n对于循环程序,软件“猜测法”或硬件“猜测法”都能获得很好效果n对于普通条件转移指令(向前转移);转移成功与不成功的概率很难预测n普通条件转移指令;如 “IF”语句编译产生的条件转移指令, 转移成功与不成功的概率一般各为50%n方法n增加一个指令目标缓冲栈n当指令分析器分析到条件转移指令时,按照转移成功的方向预取指令到这个指令目标缓冲栈中n原来的指令缓冲栈仍按照转移不成功的方向继续预取指令n转移不成功,则继续分析原来指令缓冲栈中指令n转移成功,则分析新增加的指令目标缓冲栈中的指令 tiger September 201451IBM 370/165机采用了两个先行指令缓冲栈n先行目标缓冲栈AIB的缓冲深度为4n为了简化对两套先行指令缓冲栈的控制,在转移成功时,交换先行目标缓冲栈AIB和原来的先行指令缓冲栈IB中内容,使指令分析器仍然从原来的指令缓冲栈IB中的取指令 tiger September 2014525.1.4.5 短循环程序的处理n对于短循环程序,一般先行指令缓冲栈的效率很低n短循环程序满足的三个条件n1 循环体的长度小于等于先行指令缓冲栈的深度n2 循环次数的控制采用计数转移指令实现n3 控制循环的条件转移指令一般是向后转移的指令n必须解决好三个问题n1 指令分析器如何发现短循环程序n2 如何控制短循环程序在先行指令缓冲栈中不被清除n3 如何控制循环体的执行次数,即处理好循环程序的出口n两种方法n1 在指令系统中设置专门的短循环程序的开门指令和关门指令,短循环标志触发器TLn2 用专门的硬件来识别短循环程序,目的是使短循环程序的处理对程序员透明n一级Cache:一级指令Cache、一级数据Cachen可以有效地提高循环程序的执行速度 tiger September 2014535.2 流水线处理机n空间并行性(同时性并行,资源重复)n设置多个独立的操作部件n多操作部件处理机n超标量处理机n时间并行性(并发性并行,时间重叠)n采用流水线技术n不增加或只增加少量硬件就能使运算速度提高几倍n流水线处理机n超流水线处理机n时间---空间关系n资源重复(空间并行性,同时性并行): 增加空间以多个空间容纳多条指令n时间重叠(时间并行性,并发性并行): 细分空间以多个子空间容纳多条指令 tiger September 2014545.2.1 流水线工作原理n5.2.1.1 从重叠到流水线n一次重叠执行方式,就是一种简单的指令流水线 n流水线的每一个阶段称为stage, 流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等n在每一个流水段的末尾或开头必须设置一个寄存器,称为流水寄存器、流水锁存器、流水闸门寄存器等n为了简化,流水线中一般不画出流水锁存器n先行控制技术--复杂,不整齐,不可预知,不可控n流水线 --简单,统一, 可预知, 可控分析器分析k+1流水锁存器执行部件执行k流水锁存器输入输出t1t2 tiger September 2014552 一种指令流水线n一般4至12个流水段n等于及大于8个流水段的称为超流水线处理机n机器周期(CPU周期,T1T2T3T4,一次数据通路,起点到终点)被分解到更细的操作步骤n流水线的连接图表示方法 表示流水线的逻辑关系n流水线的时空图表示方法 表示流水线的时间关系n流水线的预约表表示方法 将在非线性流水线中介绍取指形成操作数地址译码取操作数执行保存结果 tiger September 2014565.2.1.2 时空图n一条简单流水线的时空图nt 时间ns 流水段(空间)nk 指令(指令序号)------三元关系n水平方向------不同时间某流水段处理的指令n垂直方向------同一时间各流水段处理的指令n斜线 ------一条指令的流过过程n所有斜线放平,保持重叠------纵坐标为指令序号的时空图n所有斜线放平、首尾相接------T0,串行方式n斜线越陡峭,时间压缩越厉害,TN越小,流水线加速越多分析k分析k+1分析k+2分析k+3执行k执行k+1执行k+2执行k+3时间空间s0t1t2t3t4t5 tiger September 201457另一种时空图nt 时间ns 流水段(空间)nI 指令(指令序号)------三元关系n水平方向------不同时间某条指令的处理n垂直方向------同一时间各条指令的处理n斜线 ------一个流水段不同时间处理的指令n直观描述程序的执行过程n前一种时空图直观描述流水段与时间的关系IF时钟周期指令I1I2I3IDEXWRIFIDEXWRIFIDEXWR123456 tiger September 201458一个浮点加法器流水线的时空图n求阶差、对阶、尾数加和规格化4个流水段ED1时间空间0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL:规格化MA:尾数加EA:对阶ED:求阶差 tiger September 2014595.2.1.3 流水线的特点n1 在流水线中处理的必须是连续任务n只有连续不断地提供任务才能充分发挥流水线的效率n采用流水线方式工作的处理机,特别是当流水线的级数较多时,要在软件和硬件设计等多方面尽量为流水线提供连续的任务,以提高流水线的效率n2 把一个任务(一条指令或一个操作)分解为几个有联系的子任务,每个子任务由一个专门的功能部件来实现n流水线把一个大的功能部件分解为多个独立的功能部件,依靠多个功能部件并行工作来缩短程序的执行时间n3 在流水线的每一个功能部件的后面要要设置一个缓冲寄存器,或称为锁存器、闸门寄存器,用于保存本段的执行结果n因为流水线中每一段的延迟时间一般不可能都相等n在段与段之间传送子任务时,必须通过缓冲寄存器。

      当某一个流水段的执行时间变化范围比较大时,要设置多个缓冲寄存器 tiger September 2014605.2.1.3 流水线的特点n4 流水线各段的时间应尽量相等, 否则将引起“堵塞”、“断流”n执行时间长的一段将成为整个流水线的“瓶颈”,流水线中的各个功能部件将不能充分发挥作用n一种办法是把“瓶颈”流水段再细分,另一种办法是重复设置瓶颈功能段n5 流水线需要有“装入时间”和“排空时间”,流过时间kn装入时间,k-1, 全空-->全满, 指第一个任务进入流水线到填满流水线的时间n排空时间,k-1, 全满-->全空, 指第n个(最后一个)任务进入流水线到输出流水线的时间n这两种情况下,流水线不满载n流水线完全充满,整个流水线的效率才得到充分发挥n在流水线处理机的设计过程中,要充分注意上述问题,以设计出高效率的流水线n在流水线处理机上设计程序时,也必须注意流水线的上述特点,以充分发挥流水线处理机的高效率 tiger September 2014615.2.2 流水线的分类n5.2.2.1线性流水线与非线性流水线n流水线的各个流水段之间是否有反馈信号n线性流水线(Linear Pipelining)每个流水段都流过一次,且仅流过一次n非线性流水线(Nonlinear Pipelining)在流水线的某些流水段之间有反馈回路或前馈回路n线性流水线能够用流水线连接图唯一表示非线性流水线须用流水线连接图流水线预约表等共同表示S1输入S2S3输出前馈回路反馈回路一种简单的非线性流水线S1输入S2S3输出前馈回路反馈回路 tiger September 2014625.2.2.2 流水线的级别n处理机级流水线, 又称为指令流水线(Instruction Pipelining)n如采用先行控制器的处理机,各功能部件之间的流水线n1个任务=1条指令先行指令缓冲栈输入先行指令分析器先行读数栈先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果 tiger September 201463n部件级流水线(运算流水线Arithmetic Pipelining、操作流水线)n1个任务=1个加法, ......n浮点加法器流水线n处理机之间的流水线称为宏流水线 (Macro Pipelining)每个处理机对同一个数据流的不同部分分别进行处理n1个任务=1个数据流求阶差输入输出t1对阶尾数加规格化t2t3t4P1输入任务1MM…P2任务2MPn任务n输出5.2.2.2 流水线的级别 tiger September 2014645.2.2.3 单功能流水线与多功能流水线n单功能流水线n只能完成一种固定功能的流水线nCray-1计算机有12条;YH-1计算机有18条;Pentium有一条5段的定点和一条8段的浮点流水线;PentiumIII有三条指令流水线,其中两条定点指令流水线,一条浮点指令流水线n多功能流水线n流水线的各段通过不同连接实现不同功能nTexas公司的ASC计算机中的8段流水线,能够实现:定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等 tiger September 201465 tiger September 2014665.2.2.4 静态流水线与动态流水线n静态流水线n同一段时间内,多功能流水线中的各个功能段只能按照一种固定的方式连接,实现一种固定的功能n只有连续出现同一种运算时,静态流水线的效率才能得到充分的发挥n动态流水线n在同一段时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能 tiger September 201467n一次性整体切换1时间空间023 …n123 …n123 …n123 …n123 …n123 …n1234 …123 …12 ……1输入求阶差对阶尾数加规格化尾数乘累加输出静态流水线时空图浮点加法定点乘法静态流水线时空图 tiger September 2014681时间空间023…n123…n123…n123…n123…n123…n输入求阶差对阶尾数加规格化尾数乘累加输出动态流水线时空图………………123546123541234123…………浮点加法定点乘法n逐段切换动态流水线时空图 tiger September 201469流水线的其他分类方法n按照数据表示方式:标量流水线和向量流水线n按照控制方式:同步流水线和异步流水线n按照流水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同: 顺序流水线与乱序流水线n乱序流水线又称为无序流水线、错序流水线或异步流水线S1就绪回答S2就绪回答S3就绪回答输出就绪回答输入 tiger September 2014705.2.3 线性流水线的性能分析n衡量流水线性能的主要指标有:吞吐率TP、加速比S和效率En一般公式n吞吐率(Though Put)nn为任务数,Tk为完成n个任务所用时间n加速比(Speedup)nS = 顺序执行时间T0 / 流水线执行时间Tkn效率(Efficiency) tiger September 2014715.2.3.1 吞吐率(Though Put)n各段执行时间相等,输入连续任务情况下完成n个连续任务需要的总时间nTk= (k+n-1) tnk为流水线的段数nt为时钟周期nk+n-1n1从出口看 k+ n-1nk第1条指令流过时间流过时间nn-1条后续指令隔1T流出1条n2从入口看 n+ k-1nn条指令进入流水线的时间(吞吞)nk-1第n条指令排空时间排空时间n3从出口看 k-1+ nnk-1第1条指令装入时间装入时间nn条指令隔1T流出1条(吐吐)n4从入口看 n-1+ knn-1条指令进入流水线的时间nk最后1条指令流过时间流过时间n5从效率看k-1+ n-(k-1)+ k-1n先k-1逐段填充流水线,装入时间装入时间n最后k-1逐段排空流水线,排空时间排空时间n中间n-(k-1)流水线全满, 全效工作1时间空间S123… …n-1nS2S3S4123… …n-1n123… …n-1n123… …n-1nkt(n-1) tnt(k-1) tTk吐吐吞吞 tiger September 201472流水线吞吐率n各段执行时间相等, 输入连续n个任务吞吐率n最大吞吐率1/tn各段执行时间不相等、输入连续任务情况下n吞吐率=第1个任务流过时间+余后(n-1)个任务*瓶颈段时间n最大吞吐率 tiger September 201473流水线各段执行时间不相等时吞吐率计算n斜线间距撑开为瓶颈段时间n?S1输入t1=tS2t2=3tS3t3=tS4t4=t输出1时间空间S1S2S3S4∑ti(n-1) t2Tk23…n123…n123…n123…n tiger September 201474流水线各段执行时间不相等的解决办法n一是将“瓶颈”流水段细分(如果可分的话) 4段--->6段n二是将 “瓶颈”流水段重复设置npentium 4 20级、31级 1,2nPentium系统结构的核心是超标量流水线。

      U,V两条指令流水线,有各自的ALU、地址生成电路、与数据Cache的接口nRISC 2,4,8,16个整数运算器 2n?? Hyper Threading 超线程技术S1输入输出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1输入输出t1=tS2-1S2-2S2-3S3S4t3=tt4=tt2=3t tiger September 201475n消除“堵塞”、“断流”n前段能顺利后传n后段不需空等流水段重复设置的流水线1时间空间23nS1S2-1456…14…n-2n-1n-225…n-136…n123n456…n-2n-1123n456…n-2n-1S2-2S2-3S3S4“瓶颈”流水段重复设置1时间空间S1S2S3S423…n123…n123…n123…n堵塞断流 tiger September 2014765.2.3.2 加速比(Speedup)n各段执行时间相等,输入连续任务情况下 T0 = n k tn加速比n最大加速比=kn各段执行时间不等,输入连续任务情况下实际加速比 tiger September 201477 k=6 k=10任务个数n加速比S1024681124816 32 64 128流水线加速比 tiger September 2014785.2.3.3 效率(Efficiency)n计算流水线效率的一般公式nE=有效面积/占用面积n有效面积=有效的方块推挤后的实心长方形 = n k t =T0n=串行连接的(一行)方块=T0n占用面积=一个程序占用后不能为其他程序占用的时空区n=一个程序占用的时空区扩展成的外接长方形n=平行四边形+两个三角形n=kTkn各流水段执行时间相等,输入n个连续任务, 流水线的效率n流水线的最高效率=1 tiger September 201479流水线效率n各流水段执行时间不等,输入n个连续任务n流水线的效率n流水线各段的设备量或各段的价格不相等时n流水线的效率n即n其中,ai < k,且 tiger September 201480流水线的吞吐率、加速比与效率的关系n由一般公式n有S=k·En各段执行时间相等,输入连续任务情况下 T0 = n k tn有E=TP· t tiger September 2014815.2.3.5 流水线性能分析举例n例5.1:用一条4段浮点加法器流水线求8个浮点数的和:Z=A+B+C+D+E+F+G+Hn解:Z = [(A+B) + (C+D)] + [(E+F) + (G+H)]1时间空间23求阶差4567123456712345671234567对阶尾数加规格化加数A C E GA+BE+FB D F HC+D G+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+H tiger September 201482例5.1n时钟周期为t nn=7个浮点加法共用了nTk=15 tnk=4 段nT0=k n t = 4x7 t = 28 tn流水线的吞吐率(最简分数)n流水线的加速比n流水线的效率 tiger September 2014835.2.4 非线性流水线的调度技术n线性流水线n每个流水段都流过一次,且仅流过一次n非线性流水线n某些流水段之间有反馈回路或前馈回路n非线性流水线调度的任务n找出一个最小的循环周期n按照这周期向流水线输入新任务n流水线的各个功能段都不会发生冲突n流水线的吞吐率和效率最高 tiger September 2014845.2.4.1 非线性流水线的表示n线性流水线能够用流水线连接图唯一表示n流水线连接图不能唯一表示非线性流水线的工作流程n图5.44n流水线预约表(一个任务的处理过程,一个任务的时空图)S1S2S3S4输出输入反馈线前馈线 时间流水段1234567S1XXXS2XXS3XXS4X tiger September 201485n预约表表示一个任务的处理过程(一个任务的时空图)n预约表横坐标表示流水线的时钟周期,纵坐标表示流水线的各个流水段,中间有“X”表示该流水段在这一个时钟周期处于工作状态,空白表示该流水段在这一个时钟周期不工作n一行中可有多个“X”,表示一个任务在不同时钟周期重复使用同一流水段n一列中有多个“X”表示一个任务在同一个时钟周期同时占用了多个流水段n预约表的行数是流水线的段数(空间),预约表的列数是一个任务从进入流水线到流水线中输出所经过的时钟周期数(时间)---流过时间预约表 tiger September 201486预约表---连接图n一张预约表可能与多个流水线连接图相对应n与上面的预约表对应的另一种非线性流水线的连接图n移动段n拓扑关系不变n一个连接图对应有多张预约表n与前一个连接图对应的另一张预约表n同一段多个出口n时间、次序未限定 时间流水段1 2 3 4 5 6 7S1XXXS2XS3XXS4X tiger September 2014875.2.4.2 非线性流水线的冲突n向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离n预约表表示一个任务的处理过程(一个任务的时空图)n预约表移位叠加,得到多个任务的时空图n流水线在某些流水段发生冲突,即两个以上任务同时争用一个流水段。

      引起非线性流水线流水段冲突的启动距离称为禁止启动距离n必定发生冲突的启动距离,至少1行至少1格将出现两个或多个"X"重叠n不发生冲突的启动距离是一个循环数列使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环n要正确地调度一条非线性流水线,首先要找出流水线的所有禁止启动距离n所有禁止启动距离组合在一起成为一个数列,称为禁止向量 tiger September 201488启动距离为3的流水线冲突情况n预约表移位叠加,得到多个任务的时空图…X3X2X1S4…X4X2X3X1X2X1S3…X3X4X2X3X1X2X1S2…X2X3X4X1X2X3X1X2X1S1…1110987654321 时间流水段两个任务争用一个流水段三个任务争用一个流水段 tiger September 201489…X2X1X1S4…X2X2X2X1S3…X3X1X1S2…X2X1X1X1S1…1110987654321 时间流水段X2X2启动周期重复启动周期(5)是一个循环,称为恒定循环启动距离为5的流水线预约表 tiger September 201490启动距离为(1,7)循环时的流水线预约表时间流水段12345678910 11 12 13 14 15 16S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4 tiger September 201491非线性流水线调度的任务n找出一个最小的循环周期n按照这周期向流水线输入新任务n流水线的各个功能段都不会发生冲突n流水线的吞吐率和效率最高 tiger September 2014925.2.4.3 无冲突调度方法n相关理论由E.S.Davidson及其学生们于1971年提出n非线性流水线的禁止向量F(所有禁止启动距离)n计算预约表中每一行任意两个“×”之间的距离(空到X),去掉重复的---空到X间距作为启动距离必定冲突n由禁止向量F得到冲突向量CnC=(CmCm-1…C2C1)其中:m是禁止向量F中的最大值n如果i在禁止向量F中,则Ci=1,否则Ci=0nCi=0表示相应的间距可叠加,相应列任一行均无冲突n图5.44所示的预约表n禁止向量F=(3,4,6),冲突向量C=(101100) 时间流水段1234567S1XXX3,3,6S2XX3S3XX4S4X tiger September 201493由冲突向量构造状态图n把冲突向量送入一个m位逻辑右移移位器,当移位器移出0时,用移位器中的值与初始冲突向量C作“按位或”运算,得到一个新的冲突向量;否则不作任何处理;如此重复m次n预约表移位叠加,加入新任务,得到多个任务的时空图n移出1, 有冲突的启动距离,至少1行至少1格将出现两个或多个"X"重叠n中间形成的每一个新的冲突向量,也按这一方法进行处理n初始冲突向量和所有的新形成的冲突向量间用带箭头的线连接,当新形成的冲突向量和已有冲突向量出现重复时合并到一起 tiger September 201494例n一条有4个功能段的非线性流水线,每个功能段的延迟时间都相等n1写出流水线的禁止向量F和初始冲突向量Cn2画出调度流水线的状态图n3求流水线的最小启动循环和最小平均启动距离n4求平均启动距离最小的恒定循环 时间流水段1234567S1XXS2XXS3XXS4X tiger September 201495解n1.禁止向量为:F=(2,4,6)n初始冲突向量:C=101010(0)n2.初始冲突向量逻辑右移2、4、6位时,不作任何处理(冲突)n逻辑右移1、3、5和大于等于7时,移出0,要进行处理(叠加)n(0)右移1位之后:010101v101010=111111(0)--1-->(1)n(0)右移3位之后:000101v101010=101111(0)--3-->(2)n(0)右移5位之后:000001v101010=101011(0)--5-->(3)n(0)右移7位或大于7位后,还原到(0)(0)--7*->(0)n(1)右移7位或大于7位后,还原到(0)(1)--7*->(0)n(2)右移5位之后:000001v101010=101011(2)--5-->(3)n(2)右移7位或大于7位后,还原到(0)(2)--7*->(0)n(3)右移3位之后:000101v101010=101111(3)--3-->(2)n(3)右移5位之后:000001v101010=101011(3)--5-->(3)n(3)右移7位或大于7位后,还原到(0)(3)--7*->(0) 时间流水段1234567S1XX6S2XX4S3XX2S4X tiger September 201496例右移2、4、6位,移出位为1,表示用这些启动距离输入新任务要发生冲突,不做任何处理右移1、3、5和大于等于7位,移出位是0,表示用这些启动距离输入新任务不会发生冲突7*表示大于等于71010101111111011111010117*157*3537*57*7*157*3537*57*(0)(1)(2)(3) tiger September 201497简单循环n预约表与状态图是唯一对应n但不同的预约表也可能有相同的状态图 n3.简单循环:状态图中各个冲突向量最多只经过一次的启动循环n7*只能最后一个n简单循环的个数一般是有限的n由简单循环可计算出平均启动距离n最小的启动循环为(1,7)或(3,5)n其平均启动距离为 4n平均启动距离最小的恒定循环为(5)n(7)串行处理,性能最差简单循环 平均启动距离(1,7)4(3,7)5(5,7)6(3,5,7)5(5,3,7)5(3,5)4(5)5(7)7 tiger September 201498最小启动循环为(3,5)的流水线工作状态 时间功能段 12345678910 11 12 13 14 15 16S1X1X2X1X3X2X4X3…S2X1X2X1X2X3X4X3…S3X1X1X2X2X3X3X4…S4X1X2X3X4… tiger September 201499最小启动循环为(1,7)的流水线工作状态 时间流水段12345678910 11 12 13 14 15S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4吞吞吞 吞吐吐吐 tiger September 2014100?n?最小启动循环为(1,7), 10个,11个任务的完成时间n流过时间=7Tn?吞序列n?吐序列n?吞吐率 tiger September 20141015.2.4.4 优化调度方法nL.E.Shar于1972年提出流水线最小平均启动距离的限制范围n1 下限是预约表中任意一行里“×”的最多个数n2 小于或等于状态图中任意一个简单循环的平均启动距离n3 最小平均启动距离的上限是冲突向量中1的个数再加上1n1992年,L.E.Shar证明了上述限制范围n最有用的是第1条。

      预约表中“×”最多的行一定是瓶颈流水段n采用预留算法调度非线性流水线n第1步:确定最小平均启动距离n为预约表中任意一行中“×”的最多个数n第2步:确定最小启动循环n以恒定循环作为最小启动循环n第3步:采用预留算法,插入非计算延迟段实现最小启动循环 tiger September 2014102插入非计算延迟段实现最小启动循环n上一节的例子:S1、S2、S3对应的行有2个“×”,最小平均启动距离为2n以恒定循环(2)作为最小启动循环n在S4的输出端到S3的输入端中间插入一个非计算延迟D1n每一行中与第1个“×”的距离为2的倍数的位置都要预留出来(数空白),实现最小启动循环的叠加间距nS3行的第2个“×”从周期5延迟到周期6nS2行的第2个“×”也要向后延迟一个周期,从周期6延迟到周期7nS1行的第2个“×”也要向后延迟一个周期,从周期7延迟到周期8n流过时间增加,但平均启动距离最小 tiger September 2014103插入一个非计算延迟D1 tiger September 2014104n非线性流水线中,“×”最多的流水段一定是“瓶颈“流水段n最优调度的流过时间增加,但平均启动距离最小n最优调度的目标是使“瓶颈”流水段处于忙碌状态,没有空闲n最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优n?非恒定循环,如(1,3)的预留n?最优调度使得流过时间增加,吞吐率、加速比和效率等性能指标是否变坏 tiger September 2014105n先行控制--->流水线n 线性流水线--->非线性流水线n 无冲突调度--->优化调度 tiger September 20141065.2.5 局部相关(动态调度技术)n由硬件动态调整指令执行顺序以减少数据相关的影响n能处理编译阶段无法确定的相关关系,并简化编译器设计n在别的流水线机器上编译的代码也能够高效运行n采用静态调度方法生成的代码也能在采用动态调度法的机器中运行n5.2.5.1 顺序流动与乱序流动n5.2.5.2 乱序流动方式中的数据相关n5.2.5.3 数据重定向方法n5.2.5.4 Tomasulo动态调度算法 tiger September 20141075.2.5 局部相关(动态调度技术)n顺序流动方式,流水线的控制逻辑比较简单n在程序中有“先写后读”数据相关时,流水线可能会“断流”,这将降低流水线的吞吐率和效率n乱序流动方式中,除了有“先写后读”数据相关之外,还可能发生“先读后写”数据相关和“写-写”数据相关n“先写后读”数据相关又称为数据相关、写读相关、流相关、WR相关、RAW相关n“先读后写”相关又称为变量名相关、读写相关、反相关、RW相关、WAR相关n“写-写”数据相关又称为输出相关、WW相关、WAW相关或写后再写相关 tiger September 20141085.2.5.1 顺序流动与乱序流动n顺序流动方式:任务按顺序流入流水线,按顺序流出流水线n把如下一段程序输入到这条流水线中 tiger September 2014109顺序流动方式n指令k与指令k+2之间有数据相关n指令k+2停留(阻塞)在功能段S2中等待读取R0n后续的指令k+4、k+5、……不能进入流水线,k+3不能进入S2段n功能段S3、S4、S5将逐渐空闲(断流)n缺点:流水线“断流”,有些功能段“空闲”,吞吐率和效率降低n优点:流水线的控制逻辑比较简单WR tiger September 2014110乱序流动方式n乱序(Out of order)流动方式,错序流动方式、无序流动方式、异步流动方式等n指令流出流水线的顺序与指令原先的顺序不同n从流水线的输出端看,指令流出流水线的顺序与进入流水线的顺序不一样n造成流水线乱序流动方式的原因n“先写后读”数据相关n有些指令执行的时间短或经过的流水段比较少,超越执行时间长或经过流水段多的指令 tiger September 2014111乱序流动方式n指令k+2保持在功能段S2中等待读取R0n满足条件的后续指令k+3、k+4、k+5进入功能段S2执行,超越指令k+2进入后续功能段S3n不再出现“断流”,没有功能段“空闲”WR tiger September 2014112n在乱序流动方式中,还有另外两种不同的相关n下面的程序在采用乱序流动方式的流水线,可能发生三种不同的数据相关nF1、F2和F3是三个浮点寄存器,A和B是两个内存单元n(1)指令k的F1与指令k+1的F1之间:写读相关(RAW,先写后读相关)n(2)指令k+1的F1与指令k+2的左边那个F1之间:读写相关n(3)指令k的F1与指令k+2的左边那个F1之间:写写相关n还有:指令k+2的F1与指令k+3的F1之间之间有写读相关,指令k+1左边的F2与右边的F2之间有读写相关 tiger September 2014113n 流水线中指令j超越指令in有些书中把相关称为“冒险”(hazard)、“竞争”(competition)等n三种数据相关可以用下列关系式表示n写读相关D(i) ∩ S(j) ≠ n读写相关S(i) ∩ D(j) ≠ n写写相关D(i) ∩ D(j) ≠ (5.46)n这只是发生相关的必要条件,而不是充分条件5.2.5.2 数据相关及其避免方法 tiger September 20141145.2.5.2 数据相关及其避免方法 n执行程序过程中,只有避免数据相关,程序执行结果才正确n延迟执行n建立专用路径n建立专用路径来避免数据相关的基本原理是数据重定向n首先介绍常用的数据重定向的一般原理和基本方法n再介绍经典的建立专用路径避免数据相关的Tomasulo算法和CDC计分牌(scoreboard)算法 tiger September 20141155.2.5.3 数据重定向方法n1 三种数据相关的重定向方法n重定向之前,j只能在i之后执行n重定向之后,分为三种情况n(1)写读相关,j与i可以同时执行,就是专用数据通路法n(2)写写相关,j与i无先后时间顺序要求n(3)读写相关,j与i无先后时间顺序要求 tiger September 2014116三种数据相关的重定向方法 tiger September 20141172 读写数据相关和写写数据相关的重定向n编译器中称为变量换名技术n只要符合任何变量只允许定义一次的规则,读写数据相关和写写数据相关就自动消除n增加规则后,上面的数据重定向图中,把B换成了B’,读写数据相关和写写数据相关就不存在n三种数据相关中,实际上只有写读数据必须依靠硬件来解决n采用推后处理或增加专用数据通路 tiger September 2014118一个依靠编译器进行数据重定向的例子 tiger September 20141193 一个采用数据重定向的实际例子nk: LOAD F1, Ank+1: FADD F1, F2nk+2: FMUL F1, F3nk+3: STORE F1, Bn专门设置A→FADD、FADD→FMUL、FMUL→B三条专用路径n撤消F1→FADD和F1→FMUL的路径,A→F1、FADD→F1的传送路径 tiger September 20141203 一个采用数据重定向的实际例子 tiger September 20141215.2.5.4 Tomasulo动态调度算法n实际使用的动态调度算法主要有两种n1 Tomasulo算法最早在大型机IBM 360/91处理机的浮点处理部件中被采用n又称公共数据总线(CDB:Common Data Bus)法,或令牌法等n分散控制的方法n2 CDC计分牌(scoreboard)算法,最先在CDC 6600大型机中采用n集中控制方法 tiger September 20141225.2.5.4 Tomasulo动态调度算法n目的:解决异步流动的RAW和WAW相关n动态调度n寄存器重命名n动态存储器地址判别技术 tiger September 20141235.2.5.4 Tomasulo动态调度算法n以上节的一小段程序为例n如果在串行执行的处理机中,必须等待上一条指令执行完后,下一条指令才能开始执行n由于浮点加法器和浮点乘法器可以同时工作,如果采用乱序流动方式,在上面的这四条指令中可能发生“先写后读”和“写-写”两种数据相关n指令k的执行结果,把一个浮点操作数从主存储器中读出,送入浮点先行读数站的(FLB1)中,并在执行指令k+1时通过(FLB1)直接送入到浮点加法器的保存站A1,而不是送到浮点通用寄存器F1中,这就相当于建立了一条从主存储器到浮点加法器的专用数据路径n在执行指令k+1时,把浮点通用寄存器(F2)中的内容通过FLR总线送入浮点加法器的保存站A1中,同时把浮点先行读数站(FLB1)中的操作数通过另一条FLB总线也送入浮点加法器的保存站A1中,并启动浮点加法器开始工作。

      因为浮点加法器的运算结果要送入F1,因此,要把浮点加法器保存站A1的站号“10”装入浮点通用寄存器F1的站号中;另外,要把F1的“忙位”标志置“1”,表示浮点通用寄存器F1中的内容目前不能读出作为源操作数来使用 tiger September 20141245.2.5.4 Tomasulo动态调度算法n由于浮点加法器要执行两个时钟周期才能出结果,当执行指令k+2时,虽然可以把浮点通用寄存器(F3)中的内容通过FLR总线送入浮点乘/除法器的保存站M1中;但是,执行浮点乘法所需要的另一个操作数还不能从浮点通用寄存器F1中读出;这时,改为把保存在浮点通用寄存器F1中的站号“10”(浮点加法器保存站A1的站号)读出来,并通过控制总线送入到浮点乘/除法器的保存站M1中,并把F1内的站号改为浮点乘/除法器保存站M1的站号“8”,表示F1改从浮点乘/除法器接收运算结果n在浮点加法执行完成之后,把运算结果和保存站A1的站号“10”都送上公共数据总线CDB通过与所有站号中保存的内容进行相等比较,找到浮点乘/除法器的保存站M1;于是,把CDB上的数据送入M1,而不是送入浮点通用寄存器F1;这相当于建立了一条从浮点加法器到浮点乘/除法器的专用数据路径n浮点乘/除法器收到CDB上的数据之后就可以开始工作。

      在6个时钟周期之后,浮点乘法的执行结果连同保存站M1的站号都送上CDB通过与所有站号进行相等比较,把CDB上的数据送入到浮点通用寄存器F1n在浮点乘/除法器刚刚开始工作时,指令k+3开始执行由于浮点乘法的最终运算结果还没有出来,因此,就把保存站M1的站号“8”装入后行写数站的站号中当浮点乘法操作执行结束之后,在把运算结果通过CDB送入浮点通用寄存器F1的同时,也送入浮点后行写数站SDB,由SDB负责把这个结果写到主存储器的B单元 tiger September 2014125FLR 总线FLB 总线 tiger September 20141262 集中式动态调度(记分牌算法)n目的n实现多流水线异步流动方式,提高功能部件的利用率n工作原理n使用状态记录控制器记录各功能部件、进入流水线的各指令、源和目的REG的状态,然后进行统一调度n结构框图整数部件浮点加浮点乘浮点除记录控制器RFEXMEMWBIFID指令控制/状态控制/状态 tiger September 20141272 集中式动态调度(记分牌算法)n状态记录控制器(记分牌)n检测功能n功能部件(资源)冲突n源、目的REG引起的RAW、WAR、WAW相关n控制功能n有冲突或相关的指令推后进入流水线的执行部件,否则正常指令进入流水线的执行部件n记录功能部件、REG、指令的状态n根据记录的状态,控制后续指令的进入 tiger September 20141285.2.6 全局相关(相关性分析技术)n5.2.6.1 条件分支对流水线的影响n5.2.6.2 动态分支预测技术n5.2.6.3 提前形成条件码n5.2.6.4 精确断点与不精确断点 tiger September 20141295.2.6.1 条件分支对流水线的影响n条件分支或程序中断引起的相关被称为全局相关n全局相关对流水线的吞吐率和效率的影响相对于数据相关要大得多n处理好条件转移和中断的关键问题n要确保流水线能够正常工作n减少因“断流”引起的吞吐率和效率的下降 tiger September 20141301 条件分支的处理方法n一般程序中,条件转移指令占五分之一左右n条件转移指令对流水线的影响很大,必须采取措施来减少这种影响n可能采取的措施n(1) 延迟转移技术和指令取消技术n只能用于单流水线标量处理机,且流水线级数不能太多n据统计,编译器调度一条指令成功的概率在90%以上n调度两条指令成功的概率只有40%左右n没有合适的指令可调度时,编译器只能插入空操作nSUN公司的SPARC处理机, SGI公司的一部分MIPS处理机采用了延迟转移技术。

      HPPA处理机采用指令取消技术 tiger September 20141311 条件分支的处理方法n(2) 静态分支预测技术n转移预测的方向是固定的,或者预测转移不成功,或者预测转移成功n在程序实际执行过程中,转移预测的方向不能改变n静态转移预测可以只用软件实现,也可用硬件来实现,还可以在转移的两个方向上都预取指令nSUN/TI公司的SuperSPARC处理机采用静态转移预测技术,且设置有转移目标缓冲栈,在两个方向上都预取指令n(3) 动态分支预测技术n根据近期转移是否成功的历史记录预测下一次转移的方向n所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向 tiger September 20141322 条件分支在流水线中的执行过程n第i条指令所需要的条件码由第i-1条指令给出;k个功能段的流水线中,要等到第i+k-2条指令进入流水线时第i-1条指令才能形成条件码 tiger September 20141332 条件分支在流水线中的执行过程n转移不成功,则猜测正确,流水线的吞吐率和效率没有降低n转移成功,则猜测错误,要先作废流水线中已经执行的第i+1、i+2、……、i+k-2条指令;然后,再从分支点开始执行第P、p+1、…… 、i+k-3条指令n一条k段流水线有k-2个功能段是浪费的n当分支方向猜测错误时,可能造成程序执行结果发生错误n若第i+1条指令是:(R1)+(R2)→R1n寄存器R1中内容就被破坏,整个程序执行的结果将错误n目前的处理机有两种做法n一种方法是只进行指令译码和准备好运算所需要的操作数,在转移条件没有形成之前不执行运算n另一种方法是一直执行到运算完成,但不送回运算结果 tiger September 20141343 条件分支对流水线性能的影响n假设条件转移指令在一般程序中所占的比例为p,转移成功的概率为qnn条指令的总的执行时间是:TK-IF=(n+k-1)t+npq(k-1)tn有条件转移影响的流水线吞吐率n有条件转移影响的流水线最大吞吐率nTPMAX-IF=n流水线吞吐率下降的百分比nD= tiger September 20141353 条件分支对流水线性能的影响n典型程序中,转移指令占的比例为p=20%,转移成功的概率为q=60%n一条有8个功能段的指令流水线,由于条件转移指令的影响,流水线的最大吞吐率要下降 D8= =46%n如果指令流水线的功能段数为10,由于条件转移指令的影响,流水线的最大吞吐率将下降到原来的一半以下 D10= =52%n条件分支使流水线的吞吐率大约下降50% tiger September 20141365.2.6.2 动态分支预测技术n动态转移预测技术的两个关键问题n一是记录转移历史信息n二个是根据所记录的转移历史信息预测转移的方向n记录转移历史信息的方法有三种n第一种是把最近一次或几次转移是否成功的信息记录在转移指令中n第二种是用一个小容量的高速缓冲栈保存条件转移指令的转移目标地址n第三种是用Cache保存转移目标地址之后的n条指令n根据三种不同的记录转移历史信息的方法,有三类动态转移预测技术 tiger September 20141371 在指令Cache中记录转移历史信息n指令Cache中专门设置一个字段,称为“转移历史表”n执行转移指令时,转移成功或不成功的信息记录在这个表n当下次再执行到这条指令时,转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功n每一条指令一位的“转移历史表”,只记录最近一次转移是否成功的历史信息 tiger September 2014138只记录最近一次转移是否成功n箭头: “转移历史表”修改规则,即记录本条转移指令实际转移是否成功n执行条件转移指令时,如果“转移历史表”中记录的内容是“T”,则转移预测逻辑预测转移成功,并按照转移成功的方向取指令n如果记录的是“N”,按照转移不成功的方向继续取下一条指令 tiger September 2014139记录最近两次转移是否成功的历史信息n箭头: “转移历史表”修改规则,采用向左移位的方法n转移预测偏向于转移成功n只有历史上最近两次执行这条转移指令时转移都没有成功,本次才预测转移不成功n对于另外三种情况都预测转移成功 tiger September 20141401 在指令Cache中记录转移历史信息n“转移历史表”的修改规则和转移预测规则可以有多种多样n也可以记录转移预测是否成功的信息n预测本次转移方向时,也可以用最近预测是否成功的信息作为依据n“转移历史表”空白时,有两种做法n一种是在“转移历史表”中预置转移历史信息n另一种是根据指令本身的偏移字段的符号来预测转移方向n如果偏移字段的符号是负的,则预测转移成功,否则预测转移不成功n主要优点:不必专门设置转移缓冲栈,所记录的转移历史信息比较少nDEC公司的Alpha 21064超标量超流水线处理机就采用了这种转移预测方法,在一级指令Cache有一个“转移历史表”字段 tiger September 20141412 设置转移目标地址缓冲栈n用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址n“转移指令地址”字段采用全相联方式访问n当前指令地址与转移目标缓冲栈中的所有转移指令地址比较n如果发现有相等的n根据同一行中的“转移历史表”所记录的历史信息预测本次转移的方向n用转移目标地址预取指令n根据某一种规则修改“转移历史表” tiger September 20141423 设置转移目标指令缓冲栈 n上面方法的转移目标地址改为存放转移目标地址后的n条指令n预测转移方向的规则和修改“转移历史表”的规则与上面的方法相同 tiger September 20141435.2.6.3 提前形成条件码n必要性:尽早产生条件码有效减少流水线吞吐率和效率损失n可能性:对于大多数情况,可以在运算实际开始之前或者在运算中间产生条件码n乘法和除法n两个源操作数符号相同结果为正,相反结果为负n有一个操作数为“0”,则乘积为“0”n被除数为“0”,则商为“0”n除数为“0”,则除法结果溢出n加法和减法n同号相加,异号相减,结果符号与第一操作数相同n异号相加,同号相减,结果符号与绝对值大的操作数相同n溢出、是否为“0”可以通过一个比较器提前产生n在绝大多数情况下,在运算部件的入口处设置一个比较器,能提前形成结果的正负号、是否为“0”、是否溢出等条件码n如果能够在一个时钟之前就产生条件码,流水线就不会“断流”nAmdahl 470V/6(阿姆达尔)在运算部件的入口处设置一个LOCK部件来预判条件码 tiger September 20141445.2.6.3 提前形成条件码n流水线处理机中对循环程序的特殊的处理n产生条件码的运算型指令与使用条件码的条件转移指令分离n原程序n LOAD R1, NUM; 循环次数初值装入到寄存器R1nLOOP:…… ; 循体开始n ……n ……; 循环体结束n DEC R1 ; 循环次数减“1”n BNE LOOP ; 如循环未结束,继续执行循环体n ; 否则结束循环n HELT ; 程序结束nNUM: n; 循环次数n编译成如下程序n LOAD R1,NUM; 循环次数初值装入到寄存器R1nLOOP: LDEC R1; 专用循环次数减“1”指令n ……; 循体开始n ……n ……; 循环体结束n LBNE LOOP; 专用测试循环是否结束的指令n HELT; 程序结束nNUM: n; 循环次数 tiger September 20141455.2.6.4 精确断点与不精确断点n输入输出设备申请的中断服务,实际上不需要有精确断点n让已经进入流水线的所有指令都执行完成n断点就是最后进入流水线的那条指令的地址n程序性错误和机器故障等引起的中断,它们出现的概率很低n处理原则:不在于缩短时间,关键是要正确保存现场和正确恢复断点n不精确断点(Imprecise interrupt)方法n精确断点(Precise interrupt)方法 tiger September 2014146不精确断点法n采用不精确断点法,流水线可以不“断流”n所需要的硬件比较少,控制逻辑相对比较简单n中断响应时间稍长n要增加一条流水线的时间长度 tiger September 2014147采用不精确断点法可能会发生如下两个问题n(1) 程序执行的结果可能出错n例如,有如下两条指令ni: FADD R1, R2 ;(R1)+(R2)→R1ni+1: FMUL R3, R1 ;(R3)×(R1)→R3n第i条指令执行到S6段时发现浮点加法结果溢出,于是发出中断服务申请n采用不精确断点法,让进入流水线的第i+1条指令执行完成n第i+1条指令使用了不正确的通用寄存器R1中的内容作源操作数,因此,浮点乘法的执行结果一般也是不正确的n(2) 程序的调试困难n早期一批大型流水线处理机,多采用不精确断点法n近期的流水线处理机,一般采用精确断点法n设置一定数量的后援寄存器n把整个流水线中所有指令的执行结果和现场都保存下来 tiger September 20141485.3 超标量处理机与超流水线处理机 n超标量处理机nIntel公司的i860, i960, PentiumnMotolora公司的MC88110nIBM公司的Power 6000nSUN公司的SPARC、SuperSPARC、UltraSPARCn超流水线处理机nSGI公司的MIPS R4000, R5000, R10000n超标量超流水线处理机nDEC公司的AlphanFor rendering Pixar's "Toy Story", the first full length movie to be created only by computers, Pixar used more than 100 Sun SPARCstation 20 workstations and a SPARCserver 1000 to render the whole film. They all had TMS390 SuperSPARC processors. tiger September 2014149超标量、超流水、超标量超流水处理机的主要性能n指令级并行度n(每次发射指令条数,每个时钟周期发射次数)n同时性并行,并发性并行机器类型k段流水线基准标量处理机m度超标量n度超流水线(m,n)度超标量超流水机器流水线周期1个时钟周期11/n1/n同时发射指令条数1条m1m指令发射等待时间1个时钟周期11/n1/n指令级并行度ILP1mnm*n tiger September 20141505.3.1 超标量处理机n一般流水线处理机n一条指令流水线n一个多功能操作部件n每个时钟周期平均执行指令的条数小于1n多操作部件处理机n一条指令流水线n多个独立操作部件,操作部件可采用流水线,也可不流水n多操作部件处理机的指令级并行度小于1n超标量处理机典型结构n多条指令流水线n先进的超标量处理机有n定点处理部件CPUn浮点处理部件FPUn图形加速部件GPUn大量的通用寄存器n两个一级高速Cache(哈佛结构)n超标量处理机的指令级并行度大于1 tiger September 20141515.3.1.1 基本结构nMotorola公司的MC88110n10个操作部件,两个寄存器堆n整数部件通用寄存器堆,32个32位寄存器n浮点部件扩展寄存器堆,32个80位寄存器n每个寄存器堆有8个端口,分别与8条内部总线相连接n一个缓冲深度为4的先行读数栈和一个缓冲深度为3的后行写数栈n两个独立的高速Cache,各为8KB,采用两路组相联方式n转移目标指令Cache,在有两路分支时,存放其中一路分支上的指令 tiger September 2014152整数部件整数部件位操作浮点加乘法部件除法部件图形部件图形部件内部总线读数/存数部件通用寄存器堆扩展寄存器堆目标指令指令分配转移部件数据Cache (8KB)指令Cache (8KB)系统总线32位地址总线64位数据总线超标量处理机MC88110的结构 tiger September 20141535.3.1.2 单发射与多发射n单发射处理机n每个周期只取一条指令、只译码一条指令,只执行一条指令,只写回一个运算结果n取指部件和译码部件各设置一套n可只设置一个多功能操作部件, 也可设置多个独立操作部件n操作部件中可采用流水线结构,也可不采用流水线结构n设计目标是每个时钟周期平均执行一条指令,ILP的期望值=1 tiger September 2014154IF时钟周期指令I1I2I3IDEXWRIFIDEXWRIFIDEXWR123456单发射处理机的指令流水线时空图nIF: 取指令nID:指令译码nEX:执行指令nWR:写回结果 tiger September 2014155由4个操作部件组成的单发射处理机IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WR来自指令Cache通用寄存器后行写数栈 tiger September 2014156多发射处理机n每个周期同时取多条指令、同时译码多条指令,同时执行多条指令,同时写回多个运算结果n需多个取指令部件,多个指令译码部件和多个写结果部件n设置多个指令执行部件,复杂的指令执行部件一般采用流水线结构n设计目标是每个时钟周期平均执行多条指令,ILP的期望值大于1 tiger September 2014157IF时钟周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR多发射处理机的指令流水线时空图 tiger September 2014158n对齐回原来的WRi tiger September 2014159超标量处理机n定义:一个时钟周期内能同时发射多条指令的处理机n必须有两条或两条以上能够同时工作的指令流水线n通常还有1个先行指令窗口n从指令Cache中预取多条指令n对窗口内的指令进行数据相关性分析和功能部件冲突检测n保存由于功能部件冲突、数据相关或控制相关等原因暂时还不能发送到操作部件执行的指令n窗口的大小:一般为2至8条指令n采用目前的指令调度技术,每个周期发射2至4条指令比较合理 tiger September 2014160超标量处理机n每个周期发射两条指令nIntel公司的i860、i960、Pentium处理机nMotolora公司的MC88110处理机nIBM公司的Power 6000处理机n每个周期发射三条指令nSUN/TI公司SuperSPARC处理机nIntel的Pentium III处理机n操作部件的个数多于每个周期发射的指令条数n4个至16个操作部件n超标量处理机的指令级并行度n1<ILP<m; m为每个周期发射的指令条数 tiger September 2014161 tiger September 20141625.3.1.3 多流水线调度n多条流水线的调度问题是一个NP完全问题n顺序发射(in-order issue)与乱序发射(out-order issue)n顺序发射 指令的发射顺序按程序中的指令排列顺序进行n顺序完成(in-order completion)与乱序完成(out-order completion)n顺序完成 指令的完成顺序按程序中的指令排列顺序进行n多流水线调度主要有三种方法n顺序发射顺序完成n顺序发射乱序完成n乱序发射乱序完成 tiger September 20141635.3.1.3 多流水线调度 tiger September 20141641 顺序发射顺序完成6条指令按顺序分3个时钟周期发射 6条指令共用10个时钟周期完成除了流水线的装入和排空部分之外,还有8个空闲的时钟周期nI3慢I21T, I5慢I41T,对齐回原来的WRiI2I1写后读I3慢I21TFA1资源冲突I5慢I41TI6I5 R6写后写I6I5写后读 tiger September 20141652 顺序发射乱序完成n 顺序发射顺序完成对齐写的空位去掉I2I1写后读FA1资源冲突I6I5写后读 tiger September 20141662 顺序发射乱序完成n比顺序发射顺序完成调度方法少5个空闲时钟周期n6条指令总的执行时间为9个时钟周期n比顺序发射顺序完成调度方法节省1个时钟周期 tiger September 20141673 乱序发射乱序完成n采用乱序发射的指令调度方法,必须使用先行指令窗口n采用乱序发射,指令的完成次序必然也是乱序的I2I1写后读I2推迟至第2次发射I6I5写后读I6推迟至第3次发射 tiger September 20141683 乱序发射乱序完成n除装入和排空外,已没有空闲周期,功能部件得到充分利用n6条指令总的执行时间缩短为8个周期n比顺序发射顺序完成方法节省2个周期n比顺序发射乱序完成方法节省1个周期 tiger September 20141695.3.1.4 资源冲突n操作部件采用流水线结构,发生资源冲突的可能性很小n如果不采用流水线结构,发生资源冲突的可能性就大n下面是一个由4条指令程序的程序I1:FADD R0, R1 ;R0←(R0)+(R1)I2:FMUL R2, R3 ;R2←(R2)×(R3)I3:FADD R4, R5 ;R4←(R4)+(R5)I4:FMUL R6, R7 ;R6←(R6)×(R7)n有5个空闲周期,4条指令需11个周期 tiger September 20141705.3.1.4 资源冲突n4条指令共用8个周期n与没有采用流水线的方法相比,少用3个周期 tiger September 2014171在超标量处理机中,操作部件需要采用流水线结构n每个周期发射m条指令,操作部件的延迟时间为k个周期n部件不采用流水线结构,则使用同一个操作部件的两条指令的序号应该至少相差m×kn操作部件采用k个功能段的流水线结构,则使用同一个操作部件的两条指令的序号只需要相差m或m以上n超标量处理机中,指令流水线的段数一般在4至10之间,每个时钟周期发射的指令条数m在2至4之间;取中间值,k=7,m=3。

      若不发生资源冲突n操作部件不采用流水线结构,两条使用同一个功能部件的指令序号必须相差21或21以上n操作部件采用流水线结构,两条使用同一个功能部件的指令序号只需要相差3或3以上n超标量处理机中,操作部件一般要采用流水线结构n如果由于某种原因,操作部件不能采用流水线结构,则必须设置多个相同种类的操作部件 tiger September 2014172在超标量处理机中,操作部件需要采用流水线结构n普通标量处理机,希望相同操作连续出现n只有连续出现相同操作的指令序列时,流水线才能不“断流”,功能部件的效率才能得到充分发挥n超标量处理机则正好相反,希望相同操作不要连续出现n相同操作的指令序列连续出现时,会发生资源冲突n要求相同操作的指令能够相对均匀地分布在程序中n超标量处理机的这种要求正好符合一般标量程序的特点 tiger September 20141735.3.1.5 超标量处理机性能n指令级并行度n(每次发射指令条数,每个时钟周期发射次数)n同时性并行,并发性并行n单流水线普通标量处理机的指令级并行度记作(1,1)n超标量处理机的指令级并行度记作(m,1)n超流水线处理机的指令级并行度记作(1,n)n超标量超流水线处理机的指令级并行度记作(m,n)机器类型k段流水线基准标量处理机m度超标量n度超流水线(m,n)度超标量超流水机器流水线周期1个时钟周期11/n1/n同时发射指令条数1条m1m指令发射等待时间1个时钟周期11/n1/n指令级并行度ILP1mnm*n tiger September 20141745.3.1.5 超标量处理机性能n理想情况下,N条指令在单流水线标量处理机上的执行时间T(1,1)=(k+N-1)tn相同的N条指令在每个周期发射m条指令的超标量处理机上执行的时间T(m,1)=(k+ )tnkt第一条(批)指令的流过时间n(N-m)/m 后续指令批数,隔t流(吐)出一批n超标量处理机相对于单流水线标量处理机的加速比n理想情况下,超标量处理机的加速比的最大值 S(m,1)MAX=m tiger September 20141755.3.2 超流水线处理机n超流水线处理机的两种定义n1 一个周期内能够分时发射多条指令的处理机n2 指令流水线有8个或更多功能段的流水线处理机n提高处理机性能的不同方法n超标量处理机是通过增加硬件资源为代价(重复)n超流水线处理机则通过各硬件部件充分重叠工作n两种不同并行性n超标量处理机采用的是空间并行性(重复,同时性并行,增加空间)n超流水线处理机采用的是时间并行性(重叠,并发性并行,切分小空间) tiger September 20141765.3.2.1 指令执行时序n每隔1/n个时钟周期发射一条指令n流水线周期为1/n个时钟周期n在超流水线处理机中,流水线的有些功能段还可进一步细分nID功能段可再细分为译码、读第一操作数和读第二操作数三个流水段nWR功能段一般不再细分n因此有超流水线的另外一种定义n有8个或8个以上流水段的处理机称为超流水线处理机 tiger September 2014177n教材p333图5.79应更正为上图IF时钟周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每个时钟周期分时发送3次指令的超流水线 tiger September 20141785.3.2.2 典型处理机结构nMIPS R4000处理机每个时钟周期包含两个流水段,是一种很标准的超流水线处理机结构n指令流水线有8个流水段n两个Cache,指令Cache和数据Cache的容量各8KB,每个时钟周期可访问Cache两次n在一个时钟周期内可从指令Cache中读出两条指令,从数据Cache中读出或写入两个数据n主要运算部件有整数部件和浮点部件n采用顺序发射方式n?龙芯 tiger September 2014179 tiger September 2014180n取指、访问数据需跨越两个流水级nIS,DS,当前指令继续取指/读写,下一指令开始取指/读写时间指令CacheIF:取第一条指令 IS:取第二条指令RF:读寄存器堆,指令译码EX:执行指令DF:取第一个数据 DS:取第二个数据TC:数据标志校验WB:写回结果指令译码读寄存器堆ALU数据Cache标志检验寄存器堆IFISRFEXDFDSWBTCMIPS R4000处理机的流水线操作 tiger September 2014181IF流水线周期当前CPU周期IS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WB主时钟周期MIPS R4000正常指令流水线工作时序 tiger September 2014182nLOAD指令之后的两条指令中,任何一条指令要在它的EX流水级使用这个数据,指令流水线要暂停一个时钟周期暂停IFISRFEXDFDSTCWBISRFEXDFDSTCWBRFEXDFDSTCWBEXDFDSTCWBEXDFDSTCWBDFDSTCWBIFISRFI1I2I3I4I5I6运行运行Load指令使用Load数据MIPS R4000正常指令流水线工作时序 tiger September 20141835.3.2.3 超流水线处理机性能n指令级并行度为(1,n)的超流水线处理机,执行N条指令时间nkt 第一条指令的流过时间, k=未细分的段数,t=Tn(N-1)t/n 后续指令隔t/n流(吐)出一条n超流水线处理机相对于单流水线普通标量处理机的加速比n即n超流水线处理机的加速比的最大值nS(1,n)MAX = n tiger September 2014184n超标量超流水线处理机:超标量与超流水线技术结合在一起n5.3.3.1 指令执行时序n超标量超流水线处理机一个时钟周期内分时发射指令n次,每次同时发射指令m条,每个时钟周期共发射指令m×n条5.3.3 超标量超流水线处理机 tiger September 2014185IF时钟周期指令I1I2I3IDEXWR12345I4I5I6I7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRI10I11I12每时钟周期发射3次,每次3条指令 tiger September 20141865.3.3.2 典型处理机结构nDEC公司的Alpha处理机采用超标量超流水线结构n主要由四个功能部件和两个Cache组成:整数部件EBOX、浮点部件FBOX、地址部件ABOX和中央控制部件IBOXn中央控制部件IBOX可以同时从指令Cache中读入两条指令,同时对读入的两条指令进行译码,并且对这两条指令作资源冲突检测,进行数据相关性和控制相关性分析。

      如果资源和相关性允许,IBOX就把两条指令同时发射给EBOX、ABOX和FBOX三个指令执行部件中的两个n指令流水线采用顺序发射乱序完成的控制方式n指令Cache中有一个转移历史表,实现条件转移的动态预测nEBOX内还有多条专用数据通路,可以把运算结果直接送到执行部件 tiger September 2014187Alpha 21064处理机共有三条(种)指令流水线n整数操作流水线和访问存储器流水线分为7个流水段,取指令和分析指令为4个流水段,运算2个流水段,写结果1个流水段n浮点操作流水线分为10个流水段,其中,浮点执行部件FBOX的延迟时间为6个流水段n所有指令执行部件EBOX、IBOX、ABOX和FBOX中都设置有专用数据通路nAlpha 21064处理机的三种指令流水线的平均段数为8段,每个时钟周期发射两条指令nAlpha 21064处理机是超标量超流水线处理机 tiger September 2014188 tiger September 2014189IF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆,发射校验A1计算周期1,IBOX计算新的PC值A2计算周期2,查指令快表WR写整数寄存器堆,指令Cache命中检测SWAP1IFI0I1A0A1WR2345607个流水段的整数操作流水线 tiger September 2014190IF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆,发射校验ACABOX计算有效数据地址TB查数据快表HM写读数缓冲栈,数据Cache命中/不命中检测SWAP1IFI0I1ACTBHM2345607个流水段的访问存储器流水线 tiger September 2014191IF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆,发射校验F1-F5浮点计算流水线FWR写回浮点寄存器堆SWAP1IFI0I1F1F2FWR234560F3F4F578910个流水段的浮点操作流水线 tiger September 20141925.3.3.3 超标量超流水线处理机性能n指令级并行度为(m,n)的超标量超流水线处理机,连续执行N条指令所需要的时间nkt 第一条(批)指令的流过时间, k=未细分的段数,t=Tn(N-m)/m 后续指令批数,隔t/n流(吐)出一批n超标量超流水线处理机相对于单流水线标量处理机的加速比n理想情况下,超标量超流水线处理机加速比的最大值nS(m, n)MAX=m n tiger September 2014193 三种指令级并行处理机性能比较n相对于单流水线普通标量处理机的性能曲线n从三种指令级并行处理机的性能曲线,可得出结论n1 三种处理机的性能关系n2 实际指令级并行度与理论指令级并行度的关系n3 最大指令级并行度0.00.51.01.52.02.512345678相对性能超标量超流水线超标量超流水线指令级并行度 tiger September 20141941 三种处理机的性能关系n超标量处理机的相对性能最高,其次是超标量超流水线处理机,超流水线处理机的相对性能最低,主要原因n(1)超流水线处理机的启动延迟比超标量处理机大n超标量处理机每个时钟周期开始就同时发射多条指令n超流水线处理机把一个时钟周期平均分成多个流水线周期,每个流水线周期发射一条指令n(2)条件转移造成的损失,超流水线处理机比超标量处理机大n(3)超标量处理机指令执行部件的冲突比超流水线处理机小n指令执行过程中的每一个功能段,超标量处理机重复设置有多个相同的指令执行部件n超流水线处理机只是把同一个指令执行部件分解为多个流水级 tiger September 20141952 实际指令级并行度与理论指令级并行度的关系n横坐标给出的理论指令级并行度比较低时,处理机的实际指令级并行度的提高比较快n理论指令级并行度进一步增加时,处理机实际指令级并行度提高的速度越来越慢n实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当,否则,有可能造成花费了大量的硬件,但实际上处理机所能达到的指令级并行度并不高n目前,一般认为,m 和 n 都不要超过4 tiger September 20141963 最大指令级并行度n一个特定程序由于受到本身的数据相关和控制相关的限制,它的指令级并行度的最大值是有限的确定值n主要由程序自身的语义来决定,与这个程序运行在哪一种处理机上无关n对一个特定的程序,三条曲线最终都要收拢到同一个点上n不同程序,收拢点的位置不同n冯·诺依曼计算机---指令驱动---存储程序、顺序执行n数据相关、条件转移不可避免n影响了计组、系统结构、汇编、编译... tiger September 2014197?n1 多核与本章的哪部分技术接近?有何根本性不同?n2 超线程呢? 。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.