高级计算机体系结构(精编)ppt课件

.,1,一.高级计算机体系结构基础,计算机的基本概念什么是计算机计算机的基本组成衡量计算机的因素影响计算机设计的主要因素及其发展趋势摩尔定律和工艺的发展计算机市场发展趋势多核结构的发展趋势计算机重要指标性能、成本、功耗我国计算机发展历史,.,2,现在的计算机中为什么用二进制？,计算机是由电子元器件构成的，二进制最易实现。,冯诺亿曼结构：数据和程序都在存储器中，CPU从内存中取指令和数据进行运算并把结果也放到内存中,.,3,用最少的指令描述一件事情-算法，编译,提高芯跳的速度-主频,每拍做更多的事情-体系结构,计算机怎样才能跑得快,.,4,第一代到第四代,第一代：电子管计算机（1946-1958）每秒几千到几万次运算冯诺依曼结构第二代：晶体管计算机（1958-1964）每秒几十万次高级程序语言出现：FORTRAN、COBOL等IBM7094、CDC1604等第三代：中小规模集成电路计算机（1964-1975）每秒几百万次操作系统逐步成熟、小型机出现IBM360、PDP11、VAX11第四代：大规模集成电路计算机（1975-）每秒亿次以上微处理器出现：Intel,AMD.,.,5,摩尔定律到达尺寸极限后怎么办？,会不会有新材料及新器件技术取代CMOS?硅的平台不可能被取代，但硅平台上生长的器件会不断改进摩尔定律的进一步延续的技术：纳米线技术、碳纳米管技术一个普及性的技术必须可以工业大规模可制备其他任何技术都不具备这个特点成为成熟的产业，从高向广发展飞机满天飞了，汽车还遍地跑,.,6,摩尔定律与系统结构,第一阶段：晶体管不够用计算机由很多独立芯片构成计算机结构受限于晶体管数目不够第二阶段：存储器速度太慢集成度提高，微处理器蓬勃发展存储容量指数增加，但访存速度增加缓慢Cache占多达80%的芯片面积第三阶段：晶体管越来越多而“难”用设计验证能力提高与晶体管增加形成剪刀差功耗问题突出、连线成为主要矛盾不得已向多核发展第四阶段：够用就行？,.,7,CPU发展趋势：高性能，低成本,高性能多核CPU正从向千亿次量级向万亿次量级迈进片上运算能力的增加使带宽问题日益突出结合一定领域需求的XPU开始盛行，处理器核加向量处理器（VPU）和图形处理器（GPU）等属于这类结构。继功耗问题之后，带宽问题导致第二次结构变革功耗问题导致多核结构，带宽问题导致专用核结构为了提高性能而牺牲微处理器的通用性和可编程性,.,8,Question?,1多核技术出现原因?,22个1G的多核Vs2G的单核处理器,3编程模型:SIMDvsMIMD?,4虚拟化技术的意义?,.,9,主频障碍,过去主频的提高一半靠摩尔定律，一半靠结构优化如P3是10级流水线，P4是20级流水线流水线很难再细分随着晶体管尺寸的缩小，连线延迟成为主要延迟局部线延迟不变（变短了，但也变细了）全局的连线延迟还会不断变长（芯片面积不变）高主频的复杂设计正在终结强调：局部化、流水化、异步、自定时,.,10,复杂度障碍,晶体管数目的指数增加与设计队伍的增加形成剪刀差设计能力、验证能力晶体管越来越难用串扰问题、片上漂移、可制造性设计处理器结构经历了简单、复杂、简单、复杂的螺旋上升过程最早期的处理器结构由于工艺技术的限制，不可能做得很复杂，一般都是串行执行随着流水线、动态调度、CACHE、向量机技术等技术的发展，处理器结构变得复杂，如IBM360系列的机器以及Cray的向量机RISC技术的提出使处理器结构得到一次较大的简化随着多发射乱序执行技术的实现，RISC结构越来越复杂，Intel和HP研制的EPIC结构没有从根本上对处理器结构进行简化,.,11,未来可能会流行的CPU结构,多核+向量处理典型：Larrabee(16wayALU/512bit)向量的位宽：64/128/256/512/1024众核：同构的基于分片的多核（tilebased）典型：Tile64处理器核的个数：64/128512/1024带有协处理器的异构多核典型：CELL通用处理器专用的协处理器（GPU、流处理器）,.,12,摩尔定律发展过程中碰到的“墙”,1980s：存储墙CPU变快，内存只变大不变快80%的晶体管用于片内高速缓存等2000s：功耗墙一Intel放弃4GHz的PentiumIV为标志，终止复杂的高主频设计多核设计成为主流未来还有可能碰到的“墙”带宽墙：“茶壶里倒饺子”（性能和带宽1-2FLOPS:1BPS的关系）成本墙：太贵了做不起（目前只剩Intel、IBM、TSMC三家）或用不起（10nm以后单片成本反而增加）应用墙：16核以上的CPU卖给谁？量大面广的应用需要多少核？如果克服不了上述“墙”，通用CPU的摩尔定律到2015年即告终止,.,13,带宽障碍,摩尔定律的新定义片内处理器核的个数指数增长封装引脚增加缓慢每个核使用的引脚数指数下降茶壶里倒饺子高速信号传输缓解带宽瓶颈目前引脚上的信号频率已经达到GHz很快会出现板上频率高于片内频率的现象,.,14,提高计算机的性能：减少指令数和提高IPC,结构提高计算机性能的常用方法和原则加快经常性事件的速度局部性原理利用并行性归一化时间计算方法当负载中各程序的执行百分比不同时，计算加权执行时间是一种方法，另一种方法是“归一化”。就是说，将执行时间对一台参考机器进行归一化，然后取其归一化执行时间的平均值。SPEC测试程序套件采用了该方法。平均归一化时间既可表示为算术平均值，也可表示为几何平均值。,.,15,影响CPU性能的因素,性能的最本质定义完成一个任务（如后天的天气预报）所需的时间以指令为基本单位,.,16,CPI及IPC,在指令系统确定后，系统结构设计者的主要目标就是降低CPI或提高IPC平均CPI“AverageCyclesperInstruction”CPI=(CPUTime*ClockRate)/InstructionCount=Cycles/InstructionCountInstructionFrequency,.,17,开发并行性,指令级并行是过去的20年里体系结构设计者提升性能的主要途径时间并行性：指令流水线空间并行性：SuperScalar（Out-of-Order）和EPIC（编译器优化）进一步挖掘指令级并行的空间不大数据级并行：SIMD向量机SSE多媒体指令作为指令级并行的有效补充，在高性能计算及流媒体等领域发挥重要作用，在专用处理器中应用较多线程级并行线程级并行大量存在于Internet应用多核处理器多线程处理器是目前的热点,.,18,低功耗优化方法,优化对象动态功耗优化静态功耗优化优化层次系统级算法级逻辑级电路级版图及工艺级,.,19,在三台不同指令系统的计算机上运行同一程序P时，A机需要执行1.0*108条指令，B机需要执行2.0*108条指令，C机需要执行4.0*108条指令，但实际执行时间都是10秒，请分别计算这三台机器在实行程序P时的实际运行速度，以MIPS为单位。这三台计算机在运行程序P时，哪台性能最高？为什么？2.如果要给标量处理器增加向量运算部件，并且假定向量模式的运算速度是标量模式的8倍，这里把向量模式所占的百分比时间称作向量化百分比。a）画出一张图来表示加速比和向量化百分比的关系，X轴为向量化百分比，Y轴为加速比。b）向量化百分比为多少时，加速比能达到2？当加速比达到2时，向量模式占了运算运行时间的百分之多少？向量化百分比为多少时，加速比能达到最大加速比的一半？c）假设程序的向量化百分比为70%。如果需要继续提升处理器的性能，一种方法是增加硬件成本将向量部件的速度提高一倍，另外一种方法是通过改进编译器来提高向量模式的应用范围，那么需要提升多少向量化百分比才能得到与向量部件运算速度提高一倍得到相同的性能？你推荐哪一种设计方案？3.假设有一个代表典型应用的基准测试程序。一款不包含浮点部件的处理器（可以通过整数指令的模拟来执行浮点指令）运行该基准程序的运行速度是120MIPS，在该处理器上增加浮点协处理器后运行该基准程序的运行速度是80MIPS。下面给出了一些参数：I基准测试中整数指令的数目，F基准测试中浮点指令的数目，Y模拟一条浮点指令需要的整数指令的数目，W无浮点协处理器时基准程序的运行时间，B有浮点协处理器时基准程序的运行时间。a）用上面的参数符号表示出两种配置处理器的MIPS值。b）在没有协处理器的配置下，假定F=8*106，Y=50，W=4秒，求I的值。c）在上题的条件下，求B的值。d）在包含协处理器的配置下，系统的MFLOPS是多少？e）你的同事想要购买这种协处理器来提高性能，而该配置下MIPS降低了，请问他的决策正确吗？解释你的观点5.对某处理器进行功耗测试，得到如下数据：时钟不翻转，电压1.2V时，电流为500mA；时钟频率为1GHz，电压1.2V时，电流为2500mA。请计算此处理器的静态功耗以及500MHz下的总功耗。,.,20,1.解：A为10MIPS，B为20MIPS，C为40MIPS。三台机器实际性能相同。2.解：加速比y与向量化比例x之间的关系是：y=1/(1-x)+x/8)=1/(1-7x/8)(A)(2)在式(A)中令y=2，可解得x=4/757.14%。此时向量模式运行时间占总时间比例是(4/7)/8)/(3/7+(4/7)/8)=1/7=14.29%(3)硬件方法，整体加速比为1/(1-0.7*(1-1/16)=2.91软件方法，设相同加速比下向量化比例为x，即1/(1-7x/8)=2.91,x=0.75所以推荐软件方法。3.解：(1)MIPSEMUL=(I+FY)/(W106)；MIPSFPU=(I+F)/(B106)(2)120=(I+810650)/(4106)=I=80106(3)80=(80106+8106)/(B106)=B=1.1(4)MFLOPS=F/(B-(W*I)/(I+F*Y)106)18.46(5)决策正确，因为执行时间缩短了，这才是关键标准。5.解：1.1V下静态功耗1.1*1.1/(1.05/0.5)=0.576W1.1V下1GHZ时动态功耗为1.1*2.5-0.576=2.174W1.1V下0.5GHZ功耗功耗为2.174*0.5/1=1.087W1.1V下0.5GHZ总功耗为1.087+0.576=1.663W,.,21,二.二进制与逻辑电路,计算机中数的表示CMOS门电路及工艺CMOS组合逻辑与时序逻辑CMOS电路延迟从Verilog到GDSII其它“0”和“1”表示方法,.,22,计算机中数的表示,二进制最容易逻辑实现自然界中的二值系统较多“1”和“0”的表示用电压的高低表示，半导体工艺，CMOS用磁通量的有无表示，超导体工艺用能级的高低表示，量子计算机用基因序列表示，A,G,C,T,DNA计算机，非二进制？,.,23,定点数的表示（1）,原码：A=an-1an-2.a1a0表示最高位an-1为符号位，0表示正，1表示负。其它位an-2.a1a0表示数值。原码的问题：加减法效率低，两个“0”补码本质是取模运算，如-2%12=10最高位an-1为符号位，0表示正，1表示负。A=an-1an-2.a1a0表示(-2n-1an-1+an-2.a1a0)an-1=0时，补码和原码一样，A表示正an-2.a1a0。an-1=1时，A表示(-2n-1+an-2.a1a0)。原码与补码的转换最高位为0时，一样最高位为1时，最高位不变，其余位“按位取反加一”。,.,24,定点数的表示（2）,补码运算取负数，每一位(包括符号位)求补，即按位取反加一。A-B=A+B的负数=A+(B求补)加法溢出判断：A和B的最高位一样，且结果的最高位与A和B的最高位不一样。1001+0101(-7+5)=1110,1100+0100(-4+4)=0000,0011+0100(3+4)=0111,1100+1111(-4-1)=1011,0101+0100(5+4)=1001,1001+1010(-7-6)=0011,.,25,浮点数的表示（1）,定点数的不足表示范围有限，太大或太小的数都不能表示除法不精确浮点数的表示：IEEE754标准三部分组成：符号位，阶码(exponent)，尾数(fraction)最高位是符号位阶码的移码表示，底为2，2(阶码-偏移值)规格化表示，尾数的最高位总为1，因此可以不存单精度和双精度扩展的单双精度,.,26,浮点数的表示（2）,IEEE754浮点格式参数,.,27,定点数的表示分别给出64位定点原码和补码表示的数的范围；在32位定点补码表示中，0 x80000000表示什么数？按照以下要求将浮点数表示出来把单精度数转化为十进制数：0 x7ff0000,0 xbe400000,0 xff800000把双精度数转化为十进制数：0 x4035000000000000,0 x8008000000000000把十进制数转化为单精度数：-100.0,0.25把十进制数转化为双精度数：1024.0,0.25,.,28,1.解：(1)-(263-1),263-1和-263,263-1(2)-2312.解：(1)0 x7ff0000=0,00001111,11111110000000000000000=(1.1111111)2*2(15-127)=3.8368135610839464260099560574934e-340 xbe400000=1,01111100,1000000000000000000=-(1.1)2*2(124-127)=-0.18750 xff800000=1,11111111,0000000000000000000=-(2)0 x4035000000000000=0,10000000011,0101000000000000000000000000000000000000000000000000=(1.0101)2*2(1027-1023)=210 x8008000000000000=1,00000000000,1000000000000000000000000000000000000000000000000000=-(0.1)2*2-1022=-2-1023(3)-100.0=-(1.100100)2*26=0b11000010110010000000000000000000=0 xc2c800000.25=(1.0)*2-2=0b00111110100000000000000000000000=0 x3e800000;(4)1024.0=(1.0)*210=0 x40900000000000000.25=(1.0)*2-2=0 x3fd0000000000000,.,29,三.指令系统结构ISA,指令系统结构的设计原则影响指令系统结构的因素指令系统的分类指令系统的组成RISC指令系统结构RISC系统结构的简史不同RISC结构的比较,.,30,指令系统的设计原则,指令系统在计算机中的位置硬件和软件的界面设计要求兼容性：在很长时间内保持不变，如X86通用性：编译器或程序员觉得好用，有较多功能，适合于各种应用高效性：便于CPU设计的优化，不同的实现方法得到不同的性能安全性：支持通用操作系统，考虑不同的安全要求,.,31,指令系统的分类,从功能上分类算术与逻辑运算、转移、访存、系统指令从指令使用数据的方式堆栈型、累加器型、寄存器型.从指令编码定长、变长,.,32,指令系统的类型,堆栈型（Stack）：零地址指令操作数在栈顶，运算操作不用指定操作数累加器型（Accumulator）：单地址指令一个操作数总在累加器中，结果也写回累加器寄存器型（Register）：多地址指令Register-Register型Register-Memory型Memory-Memory型,.,33,指令系统的组成,指令的主、谓、宾CPU、操作、操作数操作数数据类型：定点/浮点，32位/64位访存对象：字节/半字/字/双字，大/小尾端寻址方式：寄存器、立即数、直接、间接.操作算术与逻辑运算、转移、访存、系统指令指令访问控制：转移指令指令编码定长、变长,.,34,寻址方式,如何在指令中表示访存地址,.,35,寻址方式小结,至少支持以下寻址方式RegisterImmediateDisplacementRegisterindirect指令中常数位数地址偏移量位数12-16位立即数位数8-16位,.,36,转移指令,转移指令类型条件转移/无条件转移过程调用/过程返回转移地址类型相对：PC+偏移量绝对：指令中给出转移地址间接：根据寄存器内容转移（编译器不知道目标地址），如Switch语句、函数指针、动态链接、过程返回等,.,37,指令编码,需要考虑的因素操作码部分比较简单操作数的个数、类型对指令长度影响很大变长指令程序代码短、定长指令实现简单编码方法定长：RISC变长：VAX的指令1-53字节，其中ADD指令3-19字节，Intel的X86指令1-17字节混合：IBM360/370，MIPS16，Thumb，TITMS320C54x,.,38,MIPS指令类型,访存指令（包括定点和浮点）运算指令（包括定点和浮点）比较和转移指令（包括定点和浮点）系统管理指令TLB、CACHE、例外处理TRAP、Breakpoint,.,39,常见RISC指令系统比较,通过比较常见RISC处理器的指令系统加深对RISC的了解MIPS、PA-RISC、PowerPC、SPARC通过以下方面进行比较指令格式寻址方式指令功能,.,40,指令格式比较,.,41,指令功能比较,所有RISC处理器都有一些公共指令load/store指令算术运算及逻辑指令控制流指令系统管理指令不同处理器在发展过程中形成的特色举例MIPS的非对齐访问SPARC的寄存器窗口PowerPC的Link和Count寄存器HP的Nullification,.,42,1.给定下面的代码片段：A=B-C;D=A-C;B=D+A;a）分别写出上述代码片段在四种指令系统类型（堆栈型、累加器型、寄存器-存储器型、寄存器-寄存器型）下的汇编语言代码。b）假设操作码占用8位编码，内存地址和操作数都是16位，寄存器型结构有16个通用寄存器。对每种结构回答以下问题：1）需要读取多少指令字节？2）与内存交换的数据有多少字节？3）依据代码量衡量哪种结构最好？4）依据与内存交换的数据（指令和数据）量衡量哪种结构最好？2.16进制数0 x4C4F4F4E47534F4E要存在64位双字中。a）假设存储是假设存储是8字节对齐的，请依据小尾端格式将此16进制数写入内存中，并将每个字节解释为一个ASCII字符写在对应的字节下边。b)按照大尾端的格式重做上题。3.假定在指令系统设计中需要考虑两种条件转移指令的设计方法，这两种方法如下。1）CPUA：先通过一条比较指令设置条件码A，再用一条分支指令检测条件码。2）CPUB：比较操作包含在分支指令中在两种CPU中，条件转移指令都需要两个时钟周期，所有其他指令都需要一个时钟周期。在CPUA中，全部指令的25%是条件转移指令，因为每次条件转移都需要一次比较，所以比较指令约占所有指令的25%，因为CPUA不需要在转移中包含分支，所以它的时钟频率是CPUB的1.2倍。请问哪一种CPU性能更高？如果CPUA的时钟频率只是CPUB的1.1倍，结果又是多少？,.,43,4.如果对通常的MIPS指令集增加寄存器-内存形式的指令，如下所示，可以减少一些load数量。Lw$1,0($n)add$2,$2,$1可以合并成一条指令：add$2,0($n)1)给出一段符合上述例子的代码（load得到的值立即作为运算指令的源操作数），但是编译器依然无法用寄存器-内存形式的指令消除这条load指令。2）假设这样的修改带来了5%的主频下降，同时没有CPI影响。如果load占所有指令的26%，最少要消灭load指令的百分之多少，才能使得新指令集不导致性能下降？3）在传统的静态5级流水线上，寄存器-内存形式的指令有何实现困难？5.根据MIPS指令的编码格式回答下列问题。1）条件转移指令的跳转范围是多少？2）直接跳转指令的跳转范围是多少？6.用MIPS的LWL/LWR/SWL/SWR指令编写一段程序，把内存单元10051008的值取到寄存器R1，再存到内存单元20052008中。7.用MIPS的LL/SC指令编写一段从内存单元100（R2）取数，把取出来的数加100并存回到100（R2）的原子操作代码，并说明如果在此过程中处理器发生中断或该单元被其他处理器修改时处理器如何保证上述操作的原子性。,.,44,1.解(1),.,45,2.解：小尾端：Address0 xxx0000 xxx0010 xxx0100 xxx0110 xxx1000 xxx1010 xxx1100 xxx1110 x4E4F53474E4F4F4C大尾端：Address0 xxx0000 xxx0010 xxx0100 xxx0110 xxx1000 xxx1010 xxx1100 xxx1110 x4C4F4F4E47534F4E3.解：假设CPUA总指令数为x，转移指令有0.25x，条件码指令0.25x，其它指令0.5xA执行周期数2*0.25x+0.75x=1.25x则CPUB总指令数为0.75x，其中转移指令0.25x，其它指令0.5x。B执行周期数2*0.25x+0.5x=1x当CPUA频率为1.2倍时，性能是CPUB的1.2/1.25=0.96倍当CPUA频率为1.1倍时，性能是CPUB的1.1/1.25=0.88倍因此CPUA两种情况下都差4.a）lw$1,0($n)add$2,$2,$1bnez$1,1f/任何将$1作为src的指令都可以b）假设需要减少x的load指令。减少后，指令数为1-0.26x。则(1-0.26x)/0.95=1x=0.19%c）困难在于访存MEM在EXE之前就要进行，而add$2,0($n)需要先访存后EXE,.,46,5.a）条件转移指令的跳转范围。16+2位256KB（+-128KB）b）直接跳转指令的跳转范围。26+2位256MB（+-128MB）6.解：小尾端下dlir2,1005lwrr1,0 x0(r2)lwlr1,0 x3(r2)dlir2,2005swrr1,0 x0(r2)swlr1,0 x3(r2)7.解：1:llr1,100(r2)addr1,r1,100scr1,100(r2)beqzr1,1bnop如果在ll和sc之间（含ll和sc），发生了中断或者其他处理器修改100(r2)，则sc之后r1会变0，回到标号1重新执行。,.,47,四.指令流水线,一个简单的CPU数据通路控制逻辑时序控制指令流水线指令相关和流水线冲突流水线的前递技术流水线和例外多功能部件与多拍操作,.,48,指令流水线：时序的改进,上述时序的三个步骤指令地址送到PC、取指到IR、计算结果到GPR,可以合并为两个计算下一条指令的PC和指令执行重叠可以把计算下一拍PC值作为指令执行的一部分（转移指令的运算结果是PC的值）,.,49,能否把取指和运算也重叠？,大多数情况可以重叠第n+1条指令执行时，第n条指令已经执行完，因此第n+1条指令可以用到第n条指令的结果。但有一个例外如果第n+1条指令的取指也要用到第n条指令的结果，则第n+1条指令的取指必须等到第n条指令结束后才能执行。正是Branch指令的情况，可以用delayslot解决这个问题,.,50,上述流水线的进一步改进,上述流水线是两级流水线取指和执行执行阶段做的事情较多译码（包括读取寄存器的值）运算（ALU操作）访存（取数或存数）写回到寄存器时钟周期较长，一拍内必须做完上述四件事情可以把执行阶段再细分执行阶段分成译码、运算、访存、写回,.,51,流水线的相关问题,指令相关的概念流水线变深了，相关问题更为突出。在流水线中，如果某指令的某个阶段必须等到它前面另一条指令的某个阶段后才能开始，则这两条指令存在相关相关的指令要隔开足够远，否则后面的指令就必须等待在我们的流水线中，可能发生如下相关红线表示数据相关蓝线表示转移相关（从中可看出转移指令在译码阶段执行的必要性）还有结构相关（在我们的例子中不存在）,.,52,指令流水线的相关,数据相关：使用同一个寄存器引起的相关如后面的指令用到前面指令的结果控制相关：与PC有关的相关每条指令取指用到PC，转移指令修改PC结构相关：资源冲突多条指令同时使用一个功能部件相关引起流水线阻塞,.,53,由访存引起的结构相关,访存和取指都需要存储器端口Havard结构,loadinst1inst2inst3inst4,loadinst1inst2inst3nopinst4,.,54,数据相关,RAW(ReadAfterWrite)后面指令用到前面指令所写的数据WAW(WriteAfterWrite)两条指令写同一个单元在简单流水线中没有此类相关，因为不会乱序执行WAR(WriteAfterRead)后面指令覆盖前面指令所读的单元在简单流水线中没有此类相关在动态流水线中会有WAR和WAW相关,.,55,数据相关的例子,addr1,r2,r3subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11,.,56,控制相关,PC相关转移指令计算的下一条指令地址在EX阶段计算，下一条指令等2拍使用专门的地址运算部件把地址计算提前到译码阶段可以少等一拍使用一个转移指令延迟槽（delayslot）可以不用等待转移条件相关如果在ID阶段执行转移指令时转移指令的源操作数没有准备好还是要等待,.,57,流水线的前递技术：解决RAW相关的前递（Forwarding）技术,在执行（EX）阶段的运算结果出来后直接送到后续指令的EX阶段,addr1,r2,r3subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11,.,58,前递情况下的数据相关,取数指令的结果在MEM阶段才有效，后续相关指令需要阻塞一拍,lwr1,100(r2)subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11,.,59,通过静态调度解决相关,如下程序段的优化和非优化代码a=b+c;d=e-f;,Fastcode:LWRb,bLWRc,cLWRe,eADDRa,Rb,RcLWRf,fSWa,RaSUBRd,Re,RfSWd,Rd,Slowcode:LWRb,bLWRc,cADDRa,Rb,RcSWa,RaLWRe,eLWRf,fSUBRd,Re,RfSWd,Rd,.,60,Forwarding的相关处理逻辑,以ALU左端的输入为例当s1和前面两级的目标寄存器域d1和d2都不相等时，选择中间通路当s1=d2时，选择右边通路当s1=d1且当前操作不是LD时，选择左边通路当s1=d1且当前操作是LD时，后面流水线暂停，往前面流水线送空操作,.,61,例外(Exception)与流水线,例外原因I/O请求：外部中断指令例外：用户请求例外系统调用、断点、跟踪调试指令运算部件整数运算溢出、浮点异常存储管理部件访存地址不对齐、用户访问系统空间、TLB失效、缺页、存储保护错（写只读页）保留指令错：未实现指令硬件错等等,.,62,例外发生的流水阶段取指：访存例外译码：保留指令、中断指令如Trap、Syscall执行：整数溢出、浮点异常（如除零）等访存：访存例外其它：外部中断，可能在任何时候发生例外特征同步与异步用户请求与系统强制可屏蔽与不可屏蔽指令内与指令间可恢复与结束,.,63,在前述例外中，指令内可恢复例外的处理比较困难，条件转移指令的delayslot又增加了例外处理的难度精确例外：在处理例外时，发生例外指令前面的所有指令都执行完，例外指令后面的所有指令还未执行。精确例外是存储管理和IEEE运算规范的要求发生例外指令前面的指令继续执行完后面的指令不能修改机器状态，对运算状态字的修改可能在EX阶段进行多条指令发生例外,.,64,可以把每条指令的例外延迟到WB时再处理对机器状态的修改也在WB阶段进行对状态寄存器的修改从EX阶段延迟到WB阶段,.,65,简单流水线的例外处理任何一级流水发生例外时，在流水线中记录下发生例外的事件，直到WB阶段再处理如果在EX阶段要修改机器状态（如状态寄存器），保存下来直到WB阶段再修改。指令的PC值随指令流水前进到WB阶段例外处理专用外部中断作为IF的例外处理指定通用寄存器中的一个（如最后一个）为例外处理时保存PC值专用。当发生例外的指令在WB阶段时：保存该指令的PC（也在WB阶段），有些机器还保存其它状态置PC值为例外处理程序入口地址,.,66,1.假定某假定某RISCRISC处理器处理器为标准的五级流水线（IF/ID/EX/MEM/WB）结构，并且包含旁路硬件。对于下列指令序：LWR1,0(R0)LWR2,4(R0)ADDR3,R1,R2;a=b+eSWR3,12(R0)LWR4,8(R0)ADDR5,R1,R4;c=b+fSWR5,16(R0)分析上述指令序列之间的相关，并重排序执行列避免相关。指令可以比原先并重排序执行列避免相关。重排指令序列可以比原先指令序列的执行减少多少拍？2.对于下面的计算A=+B；C=A-B写出MIPSMIPS程序代码，并且画出5级静态流水线（无旁路）上的流水线状态。3.对于向量加法X(i)=a*X(i)+Y(i)，假设，假设X，Y的首地址分别存在R1，R2，a的值存在F0中。a）试写出对应的MIPS汇编代码。b）假设单发射流水线结构为IF/ID/EX/MEM/WBI，功能部件足够，Load、SStore操作和整数操作都花费1个时钟周期，加法操作为4个周期，乘法操作为10个周期。给出第一循环所有指令的流水线时空图。,.,67,4.假定某假定某RISC处理器为标准的五级流水线（IF/ID/EX/MEM/WB）结构，该静态流水线处理器可配置包含硬件旁路电、延迟槽分支预测等技术，并假定所有的运算和访存操作均为一拍完成。下面的代码在该处理器中执行Loop:LDR1,0(R2)DADDIR1，R1,#4;R1=R1+4SD0(R2),R1;将R1存入地址0+R2处DADDIR2,R2,#4;R2R2+4DSUBR4,R3,R2;R4=R3-R2BNEZR4,Loop;已知R3的初值R2+400a）不使用旁路硬件，但在同一个周期内寄存器的读和写能进行但预测采nottaken策略，如果猜测错误则刷新（flushing）流水线上的错误指令，画出这个指序列在RISC流水线上执行的时序，并计算执行这个循环需要多少时钟周期。b）使用旁路硬件，采taken策略进行分支预测，如果猜错误则刷新（flushing）流水线上的错误指令，画出这个序列在RISC上执行的序列，并计算执行这个循环需要多少个时钟周期。c）假设RISC流水线带有单拍的分支延迟和前递或旁路硬件，对包括槽在内指令序列进行调度，可以重排指令序并修改某些的操作数但不能改变指令的数目和采用别的指令，画出该流水线时序图并计算整个循环需要钟周期数。5.许多指令集中都会有一条空操作指令（例如MIPS指令集中的nop指令），请给出设计空指令的几个作用。,.,68,1.解：LWR1,0(R0)LWR2,4(R0)ADDR3,R1,R2;a=b+eSWR3,12(R0)LWR4,8(R0)ADDR5,R1,R4;c=b+fSWR5,16(R0),.,69,排序前共需要15拍。重排后的指令序列为：LWR1,0(R0)；LWR2,4(R0)；LWR4,8(R0)；ADDR3,R1,R2；ADDR5,R1,R4；SWR3,12(R0)；SWR5,16(R0),.,70,通过重排，上述指令序列只需要13拍，减少了2拍。2.解：MIPS代码如下：LWR1,0(R0);loadALWR2,4(R0);loadBADDR3,R1,R2;A=A+BSUBR4,R3,R2;C=A-BSWR3,0(R0);storeASWR4,8(R0);storeC,.,71,3.解：假设此处的浮点运算均为单精度浮点运算。数组的长度为N(N215-1)。ADDIUR3,R0,N;NSLLR3,R3,2;N*4ADDUR3,R1,R3;R3=R1+N*4Loop:LWC1F1,0(R1);loadX(i)LWC1F2,0(R2);loadY(i)MUL.SF3,F0,F1;a*X(i)ADD.SF4,F2,F3;a*X(i)+Y(i)ADDIUR1,R1,4;i+forXADDIUR2,R2,4;i+forYBNER1,R3,LoopSWC1F4,-4(R1);storetoX(i),.,72,.,73,4.解：/此题中(2)(3)两小问中认为WB和ID能通过旁路消除相关。(1)无旁路部件，前99次循环的流水线时空图如下,.,74,前99次循环，每次都是预测错，每个循环16个时钟周期。最后一个循环，预测对，但整个循环最后一条指令写回需要18个时钟周期。共计：1699+18=1602时钟周期(2)有旁路，预测taken，前99次循环流水线时空图如下：,.,75,前99次循环，执行一个循环需要8拍。最后一次循环完整执行完需要11拍。共计：899+11=803时钟周期(3)仍认为分支预测takenLoop:LDR1,0(R2)DADDIR2,R2,#4DSUBR4,R3,R2DADDIR1,R1,#4BNEZR4,LoopSD-4(R2),R1,.,76,前99次循环，执行一个循环需要6拍。最后一次循环完整执行完需要10拍。整个循环共计：699+10=604时钟周期5.解：空操作指令(nop指令)，其不改变程序可见寄存器、状态寄存器以及内存的状态，以及用于等待需要一定周期执行的操作。nop指令的作用，常见的有：取指的强制访存对齐（memoryalignment），防止相关风险（hazard），以及用于填充延迟槽（branchdelayslot）。,.,77,五.动态流水线技术,影响流水线效率的因素指令调度技术动态调度技术Tomasulo算法动态流水线的例外处理,.,78,影响流水线效率的因素,影响RISCCPU性能的因素IronRule:Runtime=程序指令数*CPIPipelineCPI=IdealpipelineCPI+Structuralstalls+RAWstalls+WARstalls+WAWstalls+Controlstalls,.,79,程序的相关性,数据相关（真相关）：导致RAW名字相关：会导致WAW和WAR控制相关：条件转移程序的相关性容易引起流水线堵塞，可以通过软件和硬件的方法避免堵塞或降低堵塞的影响编译调度：如循环展开乱序执行：需要等待的指令不影响其他指令,.,80,定义：指令j数据相关于指令i指令j使用了指令i产生的结果，或，指令j数据相关于指令k,指令k数据相关于指令i。数据相关的指令不能并行执行寄存器的数据相关比较容易判断存储器的数据相关不容易判断:100(R4)=20(R6)?对不同循环体，20(R6)=20(R6)?,1Loop:LDF0,0(R1)2ADDDF4,F0,F23SUBIR1,R1,84BNEZR1,Loop;delayedbranch5SD8(R1),F4;alteredwhenmovepastSUBI,数据相关,.,81,两条指令使用相同名字(寄存器或存储器)，但不交换数据逆相关(Antidependence):指令j写指令i所读的存储单元且i先执行。逆相关会导致流水线WAR相关。输出相关(OutputDependence):指令j与指令i写同一个单元且i先执行。逆相关会导致流水线WAW相关。寄存器的名字相关可以通过寄存器重命名（RegisterRenaming）解决，存储单元的重命名比较困难100(R4)=20(R6)?对不同循环体，20(R6)=20(R6)?在前述例子中，编译器必须知道0(R1)!=-8(R1)!=-16(R1)!=-24(R1),名字相关,.,82,静态调度的问题,在译码阶段把指令“隔开”来解决相关只要有一条指令停止，后面指令就不能前进象是一种译码部件的结构相关对编译要求高，最好是编译把相关指令隔开有些信息在译码时难以确定，如是否发生例外、访存操作需要多少周期等,DIVDf0,f2,f4ADDDf10,f0,f8SUBDf12,f8,f14,.,83,基本思想把相关的解决尽量往后拖延，直到不能再前进前面指令的等待不影响后面指令继续前进把译码分成两个阶段：发射和读操作数发射：指令译码，检查结构相关读操作数：检查操作数是否准备好，准备好就读数，否则等待当一条指令在读操作数阶段等待时，后面指令的发射可以继续进行在什么地方等待？乱序执行指令进入是有序的执行可以乱序，只要没有相关就可执行，多条指令同时执行结束也是有序的（早期有些机器是乱序的，现代操作系统一般要求有序结束），（怎么把乱序变成有序？）与静态调度相比有些相关编译无法检测、编译器更加简单、程序性能对机器依赖少,DIVDf0,f2,f4ADDDf10,f0,f8SUBDf8,f8,f14,动态调度思想,.,84,假设只考虑RAW相关，可能发生如下执行次序DIV发射，F1,F2都准备好MUL1发射，F0没准备好，所以没有读数据ADD发射，F3,F4都准备好MUL2发射，F0没有准备好，所以没有读数据ADD完成，F0写回F0准备好，MUL1读数据DIV完成，F0写回F0准备好，MUL2读数据,DIVF0,F1,F2MULF5,F0,F6ADDF0,F3,F4MULF7,F0,F8,解决WAW和WAR的办法,.,85,为了避免MUL1读回ADD写的F0值，MUL2读回DIV写的F0值最简单的做法是在MUL读F0之前ADD不能写回，在DIV写回之前ADD不能写回，正是记分板的办法在上述方法中，F0成为瓶颈，它必须保证DIV写、MUL1读、ADD写、MUL2读的串行次序，这是问题的本质所在。真正相关：MUL1用DIV的结果，MUL2用ADD的结果，F0最终的结果为ADD的结果。MUL1用DIV的结果不一定通过F0，MUL2用ADD的结果也不一定通过F0。,DIVF0,F1,F2MULF5,F0,F6ADDF0,F3,F4MULF7,F0,F8,解决WAW和WAR的办法,.,86,为了避免MUL1读ADD写的F0值，MUL2读DIV写的F0值也可以在MUL1的输入端指定只接收DIV的输出值，在MUL2的输入端指定只接收ADD的输出值，相当于DIV直接把结果写到MUL1的输入端，ADD直接把结果写到MUL2的输入端。要求：(1)DIV的输出连到MUL1的输入，ADD的输出连接到MUL2的输入;(2)MUL1和MUL2的输入端有寄存器，这些寄存器能够指定接收哪个部件的输出作为自己的值同样，为了避免F0的最终值为DIV所写的值可以在F0记录它当前接收哪个功能部件所写的值要求F0有一个标志,DIVF0,F1,F2MULF5,F0,F6ADDF0,F3,F4MULF7,F0,F8,解决WAW和WAR的办法,.,87,上述解决办法要求每个功能部件的输入端有一些寄存器每个寄存器（包括功能部件输入端的寄存器以及通用寄存器）都记录一个功能部件号，指定它当前接收哪个功能部件的值每个功能部件的输出接到每个功能部件的输入有了上述功能，WAR和WAW相关不用阻塞寄存器重命名技术,DIVF0,F1,F2MULF5,F0,F6ADDF0,F3,F4MULF7,F0,F8,DIVRenFa,F1,F2MULF5,RenFa,F6ADD(F0,RenFb),F3,F4MULF7,RenFb,F8,解决WAW和WAR的办法,.,88,Tomasulo算法小结,通过动态调度缓解流水线阻塞例如减少CACHE失效对性能的影响保留站：重命名寄存器+缓存源操作数避免寄存器成为瓶颈避免WAW和WAR阻塞缺点硬件复杂性结果总线成为瓶颈，多条结果总线增加硬件复杂度在IBM360/91后被广泛使用动态调度、寄存器重命名等思想一直被使用：PentiumII;PowerPC604;MIPSR10000;HP-PA8000;Alpha21264,.,89,例外（Exception）与流水线,I/O请求：外部中断指令例外：用户请求中断系统调用、断点、跟踪调试指令运算部件整数运算溢出、浮点异常存储管理部件访存地址不对齐、用户访问系统空间、TLB失效、缺页、存储保护错（写只读页）保留指令错：未实现指令硬件错等等,.,90,精确例外的要求:在处理例外时，发生例外指令前面的所有指令都执行完，例外指令后面的所有指令还未执行.非精确例外的原因:在乱序执行时,前面的指令发生中断时，后面的指令已经执行完并修改了寄存器或存储单元.在下面的例子中，没有任何相关，ADDF和SUBF指令可以比DIVF先结束。如果在ADDF结束后DIVF发生例外，此时无法恢复例外现场记分板和Tomasulo算法中都是非精确例外只要保证后面指令修改机器状态时,前面的指令都已经不会发生中断即可.,DIVFf0,f2,f4ADDFf10,f10,f8SUBFf12,f12,f14,动态流水线的精确例外处理,.,91,实现精确例外处理的一个办法是把后面指令对机器状态的修改延迟到前面指令都已经执行完有些指令在EX阶段也修改机器状态,如运算指令修改结果状态在执行阶段停止流水线会影响后面的指令执行可以用一些缓冲器来临时保存执行结果,当前面所有指令执行完后,再把保存在缓冲器中的结果写回到寄存器或存储器在流水线修改机器状态时（在执行或写回阶段）写到缓冲器增加提交（Commit）阶段,把缓冲器的内容写回到寄存器或存储器提交阶段只有前面指令都结束后才能进行有序提交：乱序执行,有序结束所用的缓冲器通常被称为ReorderBuffer（ROB）在猜测执行中也用上述机制都是在某些情况不确定的情况下先执行,但留有反悔的余地,硬件支持动态流水线的精确例外处理,.,92,内容:目标地址（存数地址或寄存器号）、值、操作类型写回时写回到ROB,因此后面指令有可能从ROB读操作数使用ROB号作为重命名号（原来使用保留站号），一条指令的结果寄存器被重命名为其结果ROB号保留站重命名源寄存器号,ROB重命名结果寄存器号提交时把结果写回寄存器或存储器只要一条指令没有提交,它就不会对寄存器或存储器的内容进行修改,在一条指令没有提交之前很容易取消该指令（由于前面指令发生了例外或由于猜测执行不正确）ROB可以和WriteBuffer合并,ReorderBuffer（ROB）,.,93,动态流水线小结,有序进入、乱序执行（允许超车）、有序结束主要数据结构保留站（发射队列）把有序变成乱序ROB把乱序重新变成有序重命名寄存器用于保存未提交的临时结果乱序的能力和有关队列大小紧密相关,.,94,2.证明：如果数组元素A(c*i+d)和A(c*i+d)之间存在相关，那么GCD(c,a)GCD(c,a)能够整出(d-b)。证明：如果A(a*i+b)和A(c*i+d)之间存在相关，则必然存在某个i1和i2，使得a*i1+b=c*i2+d这样d-b=c*i2-a*i1=