第4章-流水技术与向量处理

2023/9/21第4章流水技术与向量处理

4.1标量流水工作原理4.2标量流水中的障碍及控制4.3流水线的调度技术4.4先进的流水技术4.5Pentium微处理器中的流水技术4.6向量流水技术2023/9/22本章学习要求掌握标量流水的性能分析及障碍的处理方法掌握非线性流水调度技术掌握向量流水机的结构特征、向量指令并行性分析了解标量流水、超标量流水、超流水及超长指令字计算机的基本工作原理2023/9/23提高指令执行速度的主要途径：

(1)提高处理机的工作主频

(2)采用更好的算法和设计更好的功能部件

(3)采用指令级并行技术三种指令级并行处理机：

(1)流水线处理机和超流水线(Super-pipelining)处理机

(2)超标量(Superscalar)处理机

(3)超长指令字(VLIW:VeryLongInstructionWord)处理机2023/9/24……4.1标量流水工作原理什么是流水线？考虑设计一个洗衣机的工作流程，假定它有三道工序：洗涤、清洗、甩干。每个环节为5分钟。需要完成的任务为3批，则考虑下述工作方式的工作效率：第一种：串行工作方式，即按照如下方式工作：第1批洗涤第1批清洗第1批甩干第2批洗涤第2批清洗第2批甩干第3批洗涤第3批清洗第3批甩干3批衣服的整个工作时间为3*3*5=45分钟2023/9/25第二种：重叠工作方式，设计三个部件，可以同时工作，每个部件只做一样工作，操作方式如下图：第1批洗涤第1批清洗第1批甩干第2批洗涤第2批清洗第2批甩干第3批洗涤第3批清洗第3批甩干TΔtΔtΔtΔtΔt3批衣服的工作时间为5*5=25分钟，节省20分钟。2023/9/26引出下述关于洗衣机工作的有关性能特点：吞吐率：单位时间内完成的任务数TP=n/T

加速比：串行方式与流水线方式的时间比：上述为45/25=1.8

效率：即洗衣机的利用率，上述洗衣机的效率是9/15=3/5=60%将一条指令的执行分为几个阶段，让几条指令按重叠或流水方式工作，以提高程序的执行速度。这就引出了计算机中的流水线技术。2023/9/27指令的重叠解释与先行控制计算机系统中广泛存在着重叠工作方式指令的解释方式一般只有三种：顺序、重叠和流水重叠和流水给指令的执行带来了高的吞吐率和加速比，同时也给系统增加了障碍2023/9/28指令的解释过程ALULOAD/STOREIF取指取指ID译码、读寄存器堆译码、读寄存器堆EX执行计算访存有效地址MEM---访存（读或写）WB结果写回寄存器堆将读出的数据写入寄存器堆2023/9/29一、指令的重叠解释方式1、顺序执行方式一条指令的执行过程：取指令->分析->执行执行n条指令所用的时间为：

如每段时间都为t，则执行n条指令所用的时间为：T=3nt主要优点：控制简单，节省设备。主要缺点：执行指令的速度慢，功能部件的利用率很低。取指令k分析k执行k取指令k+1分析k+1执行k+12023/9/210

2、重叠执行方式(最简单的流水线方式)

如果每个过程的时间相等，则执行n条指令的时间为：T=(1+2n)t

主要优点：

指令的执行时间缩短

功能部件的利用率明显提高主要缺点：

需要增加一个IBR取指分析执行取指分析执行取指分析执行2023/9/2113、更高重叠度的重叠解释方式把取第k+1条指令提前到分析第k条指令同时执行如果三个过程的时间相等，执行n条指令的时间为：T=(2+n)t理想情况下同时有三条指令在执行处理机的结构要作比较大的改变，必须采用先行控制方式取指k+2分析k+2执行k+2取指k+1分析k+1执行k+1取指k分析k执行k2023/9/2121．访存冲突分析与取指均要访问主存解决：

1）采用两个独立编制的存贮器数据/指令

但增加了复杂性

2）采用多体交叉存贮器

3）指令缓冲寄存器2．功能部件的冲突

解决：设置独立的分析部件和执行部件重叠方式对计算机组成的要求2023/9/2133．同步分析与执行所需的时间不同，要求的是一次重叠一次重叠：任何时间都是“分析K+1”与“执行K”的重叠=>相邻两条指令的重叠分析K执行K分析K+1执行K+1T=(n+1)t2023/9/2144．转移

无条件转移/条件转移

当转移成功时，重叠预取无效，变为顺序执行应尽可能不使用或少使用条件转移指令5．相关

邻近指令之间出现某种关联，为避免出错而不能同时执行的现象。局部性相关、全局性相关2023/9/2152023/9/216先行控制技术基本思想：使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。(a)重叠方式分析k+1分析k执行k执行k+1分析k+2执行k+2分析部件空闲执行部件空闲分析k+1分析k执行k分析k+2(b)先行控制执行k+1执行k+22023/9/217关键：缓冲技术＋预处理技术缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作预处理技术：把进入运算器的指令都预处理成R-R型指令，与缓冲技术相结合，为进入运算器的指令准备好所需的全部操作数先行控制方式使运算器可专注于运算，从而可大幅度提高程序的执行速度硬件要求：增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。2023/9/218工作原理主存存控指令分析器

先行指令栈先行读数栈后行写数栈执行部件先行操作栈数据缓冲栈

栈的深度要求：D指缓≥D操作≥D读栈≥D写栈2023/9/219二、标量流水工作原理基本思想：流水是重叠的进一步延伸，使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度。流水线的表示方法：连接图、时空图、预约表2023/9/2201、简单流水线的连接图表示流水线的每一个阶段称为流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。有些复杂指令，在执行阶段也采用流水线方式工作，称为操作流水线。取指访存执行译码写回IFIDEXMEMWBS1S2S3S4S5输入输出2023/9/221

一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机2、流水线的时空图采用“时空图”表示流水线的工作过程。一条简单流水线的时空图：取指形成操

作数地址译码取操作数执行保存结果2023/9/222一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：ED1时间空间0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差EDEAMANLmt2023/9/2233、流水线的预约表

时间流水段1234567S1XXXS2XXS3XXS4X2023/9/224三、流水线工作方式取指访存执行译码写回IFIDEXMEMWBS1S2S3S4S5输入输出指令的流水处理

流水线的基本结构中主要包括三大部分：锁存器、时钟、功能段。流水线中每个段都是由一些执行算术和逻辑功能的组合逻辑线路组成的，它们可以互相独立地对流过的信息进行某种操作，相邻两站由高速锁存器（latch）隔开，信息在各段间的流动靠同时送到各站的时钟信号来控制。1、流水线的结构2023/9/225S1S2Sm输入

输出流水线的基本结构.….…..时钟2023/9/226121321nn-1...43215432...543......54.........5nn-1......n-1.........nn-1n1234△t0△t0

△t0△t0T0=m△t0n△t0T(m-1)△t0(n-1)△t0填入正常排空流水时空图空间时间建立时间、正常流动时间、排空时间。2、流水线工作的三个时间2023/9/2273、流水线的分级、分类分级：（处理的级别分类）部件级(操作流水线)：将复杂的算逻运算组成流水工作方式；指令级：把一条指令解释过程分成多个子过程；处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中2023/9/228其他分类：功能：单功能流水线（如CRAY-1）、多功能流水线（如TI-ASC）工作方式：静态流水线、动态流水线连接方式：线性、非线性处理数据：标量流水、向量流水1234出入非线性流水线2023/9/2291)ASC算术运算流水线（多功能）输入减阶对阶移位相加规格化相乘累加输出123456784、流水线举例输入减阶对阶移位相加规格化输出123458加输入相乘累加输出1678乘2023/9/230...1234......n-1n...1234......n-1n...1234......n-1n...1234......n-1n12345867...1234...n-1n...1234......n-1n时间空间(段号)加法一二三四二三一二一一乘法......静态多功能流水线时-空图静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。2023/9/231区别：如果从软硬功能分配的观点上来看，静态流水线其实是把功能负担较多地加到软件上，以简化硬件；动态流水线则是把功能负担较多地加在硬件上，以提高流水的效能。...12345......n-1n...12345......n-1n...12345......n-1n...12345......n-1n12345867...12345......n-1n...12345......n-1n时间加法乘法一二三四五六一二三四五六七一二三四五一二三四动态多功能流水线时-空图m2023/9/232四、标量流水线性能分析衡量流水线处理机的性能主要是吞吐率、加速比和效率。

1．吞吐率：单位时间内能处理的指令条数或能输出的数据量。吞吐率越高，计算机系统的处理能力就越强。就流水线而言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。最大吞吐率：流水线达到稳定状态后可获得的吞吐率。（1）Tpmax=1/

t（2）TPmax=1/max{

t1，

t2，

t3，

t4}“瓶颈”子过程：1234

t

t3

t

t2023/9/233子过程3为瓶颈段的时空图最大吞吐率TPmax=1/3

tmTS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234输出2023/9/2341312323342143a3b3c333瓶颈段细分重复设置瓶颈流水段解决瓶颈有两种方法A：B：2023/9/235T重复设置瓶颈流水段后的工作时空图mS1S2S3aS3cS3bS4123546789101112123546789101112147102581136912123546789101112t1t12t172023/9/236实际吞吐率（1）完成n条指令的解释共需时间

可以看出不仅实际的吞吐率总是小于最大的吞吐率，而且只有当n>>m时，实际的吞吐率才能接近于理想的最大吞吐率。(2)各功能段时间不相等2023/9/2372.效率：设备的利用率，直接反映了处理机结构有效程度。流水线有建立时间、排空时间，不总是满负载工作。各段时间相等：各段时间不等：2023/9/238各段时间相等:各段时间不等:加速比：M段流水线的速度与等效的非流水线的速度之比。2023/9/239K=6K=10任务

个数加速比10246811248163264128因为因此：E=TP·Δt，S=k·E流水线的吞吐率、加速比与效率的关系2023/9/240例1.

有一四段线性流水线,每功能段延时时间分别是：△t1=△t3=△t4=△t,△t2=3△t。现在这个流水线上分别执行4个任务和40个任务。求实际吞吐率、效率和加速比。解法一：时空图分析法时间12343111223234123123123444443△t3△t空间152023/9/241Tp=4/(15△t)E=24△t

/(4*15△t)=40%Sp=4*6△t

/15△t=1.6完成4个任务时：完成40个任务时，如何画时空图呢？？方法二，公式分析法。当流水线中各功能段的执行时间不相等时，有2023/9/2422023/9/243例2、以浮点加法运算为例（四段）各段时间相等，求Z=A+B+C+D+E+F+G+H的TP、E、Sp。时间空间Z=A+B+C+D+E+F+G+H1234567TP=7/15△tE=7*4/(15*4)=7/15Sp=4*7/15=28/15=1.871111222233334444555566667777152023/9/244例3.ASC计算机功能算术运算流水线各段时间相等，6次浮点加、5次定点乘的吞吐率、效率和加速比。1,2,3,4,5,8组成加法流水1,6,7,8组成乘法流水12345678对阶减阶输出相加规格化相乘累加输入ASC计算机的流水线2023/9/245分析：T加=6+(6-1)*1=11T乘=4+(5-1)*1=8TP=11/(11+8)△t=11/19△tE=(6*6+5*4)△t/(19*8△t)=11.54%Sp=56△t/19△t=2.9412345612345612345612345612345867123456123456时间浮加定点乘一二三四五一二三四五一二三四五一二三四五2023/9/2464.2标量流水中的障碍及控制保持流水线性能条件：不能停顿或断流。影响流水线性能因素：相关和功能切换。相关类型：全局相关：转移指令引起的相关结果：流水线断流，流水线中后续指令全部作废。局部相关：资源或结构相关；指令相关；数据相关。结果：流水线停顿，流水线中后续指令有效。2023/9/247一、资源相关资源相关：功能部件、主存资源当有多条指令进入流水线后在同一机器周期内争用同一功能部件所引起的相关（冲突）当有多条指令进入流水线后在同一机器周期内同时访问主存资源2023/9/248例1：两条指令同时要用一个加法器ALULOAD/STOREIF取指取指ID译码、读寄存器堆译码、读寄存器堆EX执行计算访存有效地址MEM-访存（读或写）WB结果写回寄存器堆将读出的数据写入寄存器堆指令流水段不同类型指令中各流水段进行的操作2023/9/249两条指令同时访存造成资源相关MEMEXIDIF指令i+4WBMEMEXIDIF指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321

时钟指令冲突取指译码执行访存写回例2：2023/9/250EXIDIF指令i+4MEMEXIDIF停顿指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321

时钟指令9WBMEM使i+3指令停顿一拍进入流水线，以解决访存相关；或重复设置一个存储器；采用先行控制技术解决方法：2023/9/251二、指令相关后续指令的内容取决于当前指令执行的结果，即指令允许修改引起的相关解决相关：不准修改指令、变指令相关为数据相关EXR1D2B2X2IBM370中的“执行”指令2023/9/252三、数据相关由于流水线中的各条指令间的重叠解释，使得原来对操作数的访问顺序发生了变化，从而导致了数据之间的相关。这种相关有三类：先写后读（改用相关）

、先读后写（用改相关）、写写相关（改改相关）。设有i和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为：2023/9/253RAW读写(先写后读)---指令j试图在指令i写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。

i:R1+R2->R3

j:R3*R4->R5WAR写读(先读后写)---指令j试图在指令i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。

i:R3*R4->R5j:R1+R2->R3WAW写写(先写后写)---指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。

i:R1*R2->R3

j:R4+R5->R32023/9/254解决数据相关的办法用软件和硬件技术：时间推后法旁路技术或相关专用通路技术例：

n:loadAIFIDEXWRn+1:loadBIFIDEXWRn+2:addA,B

IF

ID

气泡EXWRn+3:storeCIFID气泡EXWRn+4:jumpKIFIDEXWRn+5:loadE停顿停顿停顿。。

n+6………停顿。。

K:IFIDEX例中有资源相关、有控制转移相关，这将影响流水线的性能。2023/9/255IF

ID

EX

MEM

WB

IF

ID

EX

WB

IF

ID

EX

WB

IF

ID

EX

WB

IF

ID

EX

WB

ADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11定向传递R1值数据相关和定向传递指令写R1完成MEM

MEM

MEM

MEM

2023/9/256ALU运算结果写RF

RF读RFALU操作数寄存器专用通路（旁路）旁路RFALUBufferMultMult2023/9/257四、全局性相关由转移指令（条件/无条件）引起的相关转移指令在程序中所占比例约为20-25%，不可忽视解决这种相关的方法：猜测法、加快和提前形成条件码、加快短循环程序的处理、采用延迟转移技术2023/9/2581、猜测法：选取发生概率较高的分支为猜测方向，若猜对，继续执行；否则,作废猜测方向的执行，返回实际转移处。（1）如何提高猜测命中率静态猜测法：猜测不成功方向。由程序员和编译程序把发生概率高的分支安排在猜测方向。动态猜测法：根据转移历史猜测。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功2023/9/259转移目标缓冲器(BTB)

利用BTB(BranchTargetBuffer)硬件，动态地预测转移方向转移指令地址转移目标地址状态欲取指令的PC查找预测PC值=按正常顺序执行NY2023/9/260转移预测原理：用2位二进制数记录实际转移状态(历史位)，高位为1时预测转移发生，高位为0时预测转移不发生。注意：初始状态、状态修改、猜测方向表示预测发生11预测发生10预测不发生01预测不发生00转移1不转移0不转移0不转移0转移1转移1转移1不转移02023/9/261（2）猜测的后续处理分支现场的保护及恢复：

猜测执行只完成译码、取操作数或执行但不写结果；采用后援寄存器保存可能被破坏的状态。预防猜不中时的加速处理：

预取猜测方向的另一方向的前几条指令，放到缓冲器中，加速猜不中时回头速度。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功2023/9/2622、加快和提前形成条件码单条指令的条件码并不一定要等执行完成得到运算结果后才能形成循环程序判断的提前形成3、优化延迟转移技术

a.将转移指令前的那条指令调度到延迟槽中；

b.将转移目标处的那条指令调度到延迟槽中；

c.将转移不发生时该执行的那条指令调度到延迟槽中。4、加快短循环处理2023/9/263五、流水线中的中断处理流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题不精确断点法：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。断点就是最后进入流水线的那条指令2023/9/264S1S8S7S6S5S4S3S2输入输出i+5ii-1i+1i+2i+3i+4i-2PC：不精确断点申请中断精确断点特点：硬件开销小，控制简单，适用于常规的I/O操作。2023/9/265

精确断点法：不论第i条指令是在流水线中哪一段发出的中断申请，给中断处理程序的现场全都是对应第i条的。适用于程序性错误和机器故障等产生的中断精确断点法中对原有现场的恢复，要增加后援寄存器，以保留各功能段状态i:FADDR1,R2;(R1)+(R2)→R1i+1:FMULR3,R1;(R3)*(R1)→R3S6：加法结果溢出精确断点法有利于程序调试2023/9/266例4

在一条单流水线处理机上执行下面的程序。每条指令都要经过“取指”,“译码”,“执行”和“写结果”4个流水段。每个流水段的延迟时间都是5ns。在“执行”流水段,LS部件完成LOAD或STORE操作,其它操作都在ALU部件中完成,两个操作部件的输出端有直接数据通路与任一操作部件的输入端相连,ALU部件产生的条件码也能够直接送入控制器。2023/9/2671:SUBR0,R0;R0←02:LOADR1,#8;向量长度83:LOOP:LOADR2,A;R2←A向量的一个元素

4:MULR2,R1;R2←(R2)*(R1)5:ADDR0,R2;R0←(R0)+(R2)6:DJNER1,LOOP;R1←(R1)-1若(R1)≠0则转

7:STORER0,S;保存结果(1)采用静态分支预测技术,每次都预测转移不成功。画出指令流水线的时空图。计算流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。(2)采用静态分支预测技术,每次都预测转移成功。计算指令流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。2023/9/26852112112322333454445556666取指写回ALULS译码3333444455556666333344445555666633334444555566667777............重复8次m(1)解:每次预测转移不成功,流水线时空图如下:2023/9/269112112322333454445556666取指写回ALULS译码333344445555666633334444555566667777......重复8次m(2)解:每次预测转移成功,流水线时空图如下:2023/9/2704.3流水线的调度技术静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式两种。2023/9/271一、静态调度技术静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。非线性流水线中存在着前（反）馈回路，必然会引起功能段的冲突而发生流水线停顿。调度方法会减少停顿时间。调度方案是基于二维预约表和状态图来进行分析2023/9/272非线性流水线的连接图

时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线的预约表S1S2S3S4输出输入反馈线2023/9/273某流水线结构如下：非线性流水线调度举例

S1S2S3S4S5入①②③④⑥⑤⑦⑧⑦⑨出⑧

流水线调度方案如下：2023/9/274（1）形成预约表指令总拍数为n，流水线有k个段，则形成n×k的预约表，段的使用情况用“×”表示。预约表如下：××5××4×3××××2××198765438271tS2023/9/275（2）由预约表形成禁止表FF={各段中冲突间隔拍数}

---功能段1的禁止间隔拍数为8；

---功能段2的禁止间隔拍数为5和6；

---功能段3的无禁止间隔拍数；

---功能段4的禁止间隔拍数为1；

---功能段5的禁止间隔拍数为1。F={1，5，6，8}（3）由禁止表F形成初始冲突向量C0C0=（10110001），ci=1冲突，0不冲突。2023/9/276（4）由初始冲突向量C0形成状态转换图a.

取C0分别间隔2、3、4、7拍，且将C0分别逻辑右移2、3、4、7位，高位补0后再与C0按位“或”，形成新的冲突向量C1、C2和C3；10110001101101111011110110111011初始状态3427C0C1C2C32023/9/277b.再分别取C1间隔2、7拍；取C2间隔4、7拍；取C3间隔3、7拍。方法同上，直至全部完成。

注意：向量Ci右移后，总是与原始向量C0作逻辑加。1011000110110111101111011011101110111111初始状态34422777C0C1C2C3C4772023/9/278（5）根据状态图写出调度方案

每一个闭合回路就是一个调度方案（策略）1011000110110111101111011011101110111111初始状态34422777C0C1C2C3C47732023/9/279本例中调度方案如下：调度策略平均间隔拍数调度策略平均间隔拍数(2,7)4.50(4,3)3.50(2,2,7)3.67(4,3,7)4.67(3,4)3.50(4,7)5.00(3,7)5.00(7)7.00(3,4,7)4.67

平均延时最小的调度方案为最佳调度方案，本例为（3，4）和（4，3）。

对非C0开始的调度方案由流水线控制器完成控制的过渡。2023/9/280调度方案的验证原理：二维预约表方法：给定任务数，使用每一种可能的调度方案进行调度验证：调度过程中有无功能段的冲突？2023/9/281123456789101112131415S1√√√√√S2√√√√√√√√√S3√√√S4√√√√√√S5√√√√√√例如，按(3,4)调度方案，连续输入3个任务的调度过程如下：2023/9/282按（4，3）调度方案连续输入6个任务的时空图S1S2S3S4S5mt2023/9/283性能分析设共输入8个任务，按最佳调度方案（平均时延最小3.5拍）（3，4）进行调度，计算流水调度的最大和实际吞吐率2023/9/284例5设有一4段流水线处理机如下图所示。此流水线的总值时间为6个时钟周期,所有相继段必须在每个时钟周期之后才能使用。(1)列出这一流水线的4行6列的预约表;(2)列出禁止表和画出状态图;(3)求出平均延迟最小的调度方案和最大吞吐率。S1S2S3S4输出输入2023/9/285功能段123456S1√√S2√√S3√S4√解法一：4行6列的预约表(一)禁止表的原始冲突向量为：F={4}，C=(1000)2023/9/28610001100111011111010100110111101111212333223解法一的状态转移图平均延迟最小的调度方案是：(1,2,3,2)。最小平均延迟是：2▲t。最大吞吐率是：TPmax=1/2▲t。2023/9/287功能段123456S1√√S2√√√S3√√S4√解法二：4行6列的预约表(二)禁止表的原始冲突向量为：F={2,4}，C=(1010)2023/9/28810101111101113355解法二的状态转移图平均延迟最小的调度方案是：(3)。最小平均延迟是：3▲t。最大吞吐率是：TPmax=1/3▲t。2023/9/289二、动态调度技术动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式优点：（1）能处理某些在编译时无法知道的相关情况（2）能简化编译程序设计（3）使代码有可移植性缺点：相应的硬件较为复杂。2023/9/2901、集中式动态调度静态调度中的指令是按序(In-order)执行，如果一条指令在流水线中发生停顿，后续指令就不再前进了动态调度可使指令按无序(Out-order)方式工作集中式动态调度：依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作2023/9/291EX

MEMWB

集中式动态调度IFID整数部分浮点加浮点乘浮点除RF记录控制器指令控制/状态控制/状态状态记录控制器（记分牌）记录与控制在流水线的EX段开始。2023/9/292检测功能：功能部件（资源）冲突；源、目的REG引起的RAW、WAR、WAW相关。控制功能：有冲突或相关的指令推后进入流水线的执行部件，否则正常指令进入流水线的执行部件；记录功能部件、REG、指令的状态；根据记录的状态，控制后续指令的进入。2023/9/2932、分布式动态调度

此方法是由Tomasulo于1967年提出来的，已在IBM360/91机中采用。IBM360/91的浮点运算器主要部件：（1）

运算部件：一个加法部件和一个乘除部件。（2）保存站：加法部件中有A1~A3三个保存站，乘除部件有M1和M2两个保存站，用来保存当前参加运算的数据。2023/9/294（3）

指令操作缓冲栈：存放经分析后由指令部件送来的指令，译码后，产生相应的控制信号送到各个部件。（4）浮点操作数寄存器（FLB）：存放由主存预取来的操作数。（5）浮点寄存器（FLR）：存放操作数的寄存器。（6）

存储数据缓冲站（SDB）：存放将写入存储器的结果数据，也有站号。（7）

公共数据总线（CDB）：以上各部件间的连接总线。2023/9/295浮点操作数缓冲器(FLB)控浮点操作栈(FLOS)忙制位站号源1控制站号源2站号源1站号源2控制控制号站存数缓冲器(SDB)加法器乘/除法器译码器站号浮点寄存器(FLR)M1M2A1A2A3101010111100FLB总线FLR总线10001001CDB公共数据总线指令处理部件存储器总线654321站号：

01100001F76543F21F0保存站IBM360/91的浮点运算部件结构框图2023/9/296S1：(FLB1)→F0S2：(F0)*(FLB2)→F0S3：(F0)→AS4：(FLB3)→F0S5：(F0)+(FLB4)→F0;F0站号置为0001;F0置忙位为1，M1源1为0001，源2为0010，F0站号为1000;C1站号置1000;F0站号置为0011;F0置忙位为1，A1源1为0011，源2为0100，F0站号为1010调度方法特点：通过FLR的“忙”位，检测RAW相关；通过修改站号（重命名），消除WAR、WAW相关；通过设置保存站，减少资源相关冲突；借助CDB作相关专用通路。2023/9/2974.4先进的流水技术流水中指令级并行性的进一步开发粗粒度并行性：在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；细粒度并行性：指在一个进程中进行操作一级或指令一级的并行处理。RISC机进一步开发细粒度并行性2023/9/298一、超标量流水处理技术每个时钟周期平均执行指令的条数大于或等于2超标量处理机典型结构：

多条指令流水线、多个功能部件先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU,图形加速部件GPU，大量的通用寄存器，两个一级高速Cache超标量处理机的指令级并行度ILP大于12023/9/299超标量流水线处理机的一般结构IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWR2023/9/2100整数

部件整数

部件位

操作浮点加乘法

部件除法

部件图形

部件图形

部件内部总线读数存

数部件通用寄

存器堆扩展寄

存器堆目标

指令指令分配

转移部件数据Cache(8KB)指令Cache(8KB)系统总线32位地址总线32位数据总线超标量处理机MC88110的结构2023/9/2101IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWRIFID先行指

令窗口注：先行指令窗口除了能够做数据相关性分析和功能部件冲突的检测之外，还至少有一套取指令部件和一套指令译码部件2023/9/2102IF时钟

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR超标量流水处理机的时空图2023/9/2103超标量流水线的调度按序发射：当指令按策划功能序的次序发射时，称之为按序发射（in-orderissue）无序发射：为改善流水线性能，可以将有相关的指令推后发射，而将后面的无相关性的指令提前发射，即不按程序原有次序发射指令，称之为无序发射（out-of-order）按序完成：完成顺序与发射顺序一致无序完成：完成顺序与发射顺序不一致2023/9/2104按序发射按序完成—静态调度策略；（Pentium)按序发射无序完成—动态调度策略；（PentiumII/III）无序发射无序完成—动态调度策略。无论那种调度策略，都要保证程序运行的最终结果是正确的，发射策略由译码控制器完成，完成策略由执行控制器完成。常用的调度方法2023/9/2105IF1ID1L/SWR1IF2ID2部件FA1WR2FA3FA2顺序(RAW)顺序(WAW)顺序顺序(RAW)MD1MD2MD3WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2MD1MD2MD3I1WR2IF2I2I3I4I5I6指令时钟周期12345678910流水线2流水线1I1：LOADR1，A；主存单元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6按序发射按序完成之调度过程2023/9/2106IF1ID1L/SWR1IF2ID2部件FA1WR2FA3FA2(RAW)(RAW)MD1MD2MD3WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2MD1MD2MD3I1WR2IF2I2I3I4I5I6指令时钟周期123456789流水线2流水线1I1：LOADR1，A；主存单元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6按序发射无序完成之调度过程2023/9/2107IF1ID1L/SWR1IF2ID2FA1WR2FA3FA2MD1MD2MD3WR1IF1ID1FA2FA3FA1ID3IF3WR2ID2ALIF2WR1ID2MD2MD3MD1I1WR2IF2I3I4I2I5I6指令时钟周期12345678流水线2流水线1I1：LOADR1，A；主存单元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6无序发射无序完成之调度过程先行控制2023/9/2108超标量流水线的资源冲突在先进的超标量流水机中，有多个操作（执行）部件，如：ALU、FADD、FMUL、GPU、LSU等操作部件必须采用流水结构，可减少资源冲突2023/9/2109I1：FADDR0，R1；(R0)+(R1)→R0

I2：FMULR2，R3；(R2)×(R3)→R2I3：FADDR4，R5；(R4)+(R5)→R4I4：FMULR6，R7；(R6)×(R7)→R6IF1IF2ID1ID2FADDIF1ID1IF2ID2WR1FMULWR2FADDFMULWR1WR2I1I2I3I41234567891011双流水线超标量处理机（操作部件非流水结构）2023/9/2110I1：FADDR0，R1；(R0)+(R1)→R0

I2：FMULR2，R3；(R2)×(R3)→R2I3：FADDR4，R5；(R4)+(R5)→R4I4：FMULR6，R7；(R6)×(R7)→R6IF1IF2ID1ID2FA1IF1ID1IF2ID2WR1FM1WR2WR1I1I2I3I412345678t双流水线超标量处理机（操作部件流水结构）FA2FA3FM2FM3FM4FA1FA2FA3FM1WR2FM2FM3FM42023/9/2111二、超流水线处理机两种定义：

一个周期内能够分时发射多条指令的处理机称为超流水线处理机。

指令流水线有8个或更多功能段的流水线处理机称为超流水线处理机。提高处理机性能的不同方法：

超标量处理机是通过增加硬件资源为代价来换取处理机性能的。超流水线处理机则通过各硬件部件充分重叠工作来提高处理机性能。两种不同并行性：

超标量处理机采用的是空间并行性

超流水线处理机采用的是时间并行性2023/9/2112指令执行时序每隔1/n个时钟周期发射一条指令，流水线周期为1/n个时钟周期在超标量处理机中，流水线的有些功能段还可以进一步细分，例如：ID功能段可以再细分为译码、读第一操作数和读第二操作数三个流水段。也有些功能段不能再细分，如WR功能段一般不再细分。因此有超流水线的另外一种定义：有8个或8个以上流水段的处理机称为超流水线处理机2023/9/2113IF时钟

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每个时钟周期分时发送3条指令的超流水线2023/9/2114MIPSR4000处理机的流水线操作指令CacheIF：取第一条指令 IS：取第二条指令

RF：读寄存器堆，指令译码

EX：执行指令 DF：取第一个数据

DS：取第二个数据 TC：数据标志校验；WB：写回结果指令

译码读寄

存器堆ALU数据Cache标志检验寄存器堆IFISRFEXDFDSWBTC2023/9/2115IF流水线周期当前CPU周期ISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWB主时

钟

周期MIPSR4000正常指令流水线工作时序2023/9/2116三、超标量超流水线处理机把超标量与超流水线技术结合在一起，就成为超标量超流水线处理机

指令执行时序

超标量超流水线处理机在一个时钟周期内分时发射指令n次，每次同时发射指令m条，每个时钟周期总共发射指令m×n条。2023/9/2117IF时钟周期指令I1I2I3IDEXWR12345I4I5I6I7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRI10I11I12每时钟周期发射3次,每次3条指令2023/9/2118不同结构计算机的性能分析标量处理机的并行度(1,1)超标量处理机的并行度(m,1)超流水处理机的并行度(1,n)超标量超流水处理机的并行度(m,n)2023/9/2119标量流水处理机上执行N条指令的时间：超标量流水处理机上执行N条指令的时间：2023/9/2120超流水处理机上执行N条指令的时间：超标量超流水处理机上执行N条指令的时间：2023/9/2121四、超长指令字(VLIW)计算机VLIW是以一条长指令实现多个操作的并行执行，减少存储器访问。主要特点：（1）单一的控制流。只有一个控制器，每个周期启动一条指令。（2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。（3）在编译阶段完成超长指令中多个可并行执行操作的调度。2023/9/2122

超长指令字计算机举例如完成以下运算：C=A+B、K=I+J、

L=M-K、Q=C×K需以下13条指令完成：（需花14个T

）LOADA、LOADB、C=A+B、STOREC、LOADI、LOADJ、K=I+J、STOREK、LOADM、L=M-K、STOREL、Q=C×K、STOREQ2023/9/2123主存RF(寄存器堆)LD/ST2FADDFMULLD/ST1LD/ST1LD/ST2FADDFMUL存/取1存/取2浮点加浮点乘操作并行度≤4LOADALOADBLOADILOADJC=A+BLOADMSTORECK=I+JSTOREKL=M-KQ=C×KSTORELSTOREQ用VLIW则只需6个T2023/9/2124例6

在下列不同结构的处理机上运行8×8的矩阵乘法C=A×B，计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns，C的初始值为“0”。各操作部件的输出端有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。2023/9/2125（1）处理机内只有一个通用操作部件，采用顺序方式执行指令。解：需要完成的乘法次数为8×8×8=512次需要完成的加法次数为8×8×7=448次执行完成总时间为：2023/9/2126（2）单流水线标量处理机，有一条两个功能的静态流水线，流水线每个功能段的延迟时间均为一个时钟周期，加法操作和乘法操作各经过3个功能段。解：IFIDAD1AD2AD3MU1MU3MU22023/9/2127（3）单流水线标量处理机，处理机内有两条独立的操作流水线，流水线每个功能段的延迟时间均为一个时钟周期。解：IFIDAD1AD2AD3MU1MU3MU22023/9/2128（4）超标量处理机，每个时钟周期同时发送一条乘法指令和一条加法指令，处理要内有两条独立的操作流水线，流水线的每个功能段的延迟时间均为一个时钟周期。（不考虑数据之间的相关性，下同。）解：2023/9/2129（5）超流水处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件的延迟时间都为6个流水级，每个时钟周期能够分时发射两条指令，即每个流水级能够发射一条指令。IFIDAD1AD2AD3MU1MU3MU2解：123456789102023/9/2130（6）超标量超流水线处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件延迟时间都为6个流水级，每个流水级能够同时发射一条乘法指令和一条加法指令。解：2023/9/21314.6向量流水技术向量流水的基本原理CRAY-1型向量处理机增强向量处理性能的方法2023/9/21324.6.1向量流水的基本原理提高流水性能方法：增加流水线段数，以减少Δt；每个时钟同时启动多条指令；减少相关，减少功能变换次数，增加处理指令条数。向量操作特点1.向量元素间操作相互独立，且为相同操作。2.相当于标量循环，对指令带宽的访问要求不高。3.可采用多体交叉存储器，减少访存延迟。向量操作很适合于流水处理或并行处理。2023/9/2133例如：Y=a*X+YX、Y为向量，长度为64；a为标量LDF0，aADDIR4,RX,#512；由X向量的末址地装入R4LOOP:LDF2,0(RX)；取向量元素X(i)MULDF2,F0,F2；X向量与标量乘

LDF4,0(RY)；取向量元素Y(i)ADDDF4,F2,F4SD0(RY),F4；存结果向量

ADDIRX,RX,#8ADDIRY,RY,#8；地址增量

SUBR20,R4,RX；R4-RX→R20JNZR20,LOOP；判是否为02023/9/2134如果用向量处理机来完成同样的操作LDF0，aLDVV1,RX；装入向量XMULVV2,F0,V1；X向量与标量乘

LDVV3,RY；取向量元素YADDVV4,V2,V3SDVRY,V4；存结果向量特点：1、执行指令6条（标量执行8*64+2=514条）。降低了存储器对取指带宽的要求。2、标量运算过程中存在的数据相关性，在向量运算过程中已基本消除（共2次）。2023/9/2135一、向理处理的方式有三种处理方式：

1．横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。

2．纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。

3．纵横处理方式，又称为分组处理方式，纵横向加工方式等。横向处理和纵向处理相结合的方式。2023/9/2136向量处理方式以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。

for(i=1；i<=n；i++)

y[i]=a[i]×(b[i]+c[i]);2023/9/21371、横向处理方式

逐个分量进行处理：设k中间变量

第1个分量：k＝B[1]＋C[1],Y[1]＝A[1]×k;

第2个分量：k＝B[2]＋C[2],Y[2]＝A[2]×k;

……

第n个分量：k＝B[N]＋C[N],Y[N]＝A[N]×k.存在两个问题：

在计算向量的每个分量时，都发生先写后读的数据相关。流水线性能降低

如果采用多功能流水线，必须频繁进行流水线切换横向处理方式对向量处理机不适合

即使在标量处理机中，也经常通过编译器进行指令流调度。2023/9/21382、纵向处理也称为垂直处理方式，纵向加工方式等

T[1]=B[1]+C[1]

T[2]=B[2]+C[2]

……

T[n]=B[n]+C[n]

Y[1]=A[1]×T[1]

Y[2]=A[2]×T[2]

……

Y[N]=A[N]×T[N]采用向量指令只需要2条：

ADDVT,B,C

MULVY,A,T这种处理方式适用于向量处理机，数据相关不影响流水线连续工作。不同的运算操作只需要切换1次。2023/9/21393、纵横向处理方式

将长度为n的向量分成若干组，每组长度为N，组内按纵向方式处理，依次处理各组，组间是横向处理方式。用于寄存器-寄存器结构的向量处理机中

向量寄存器的长度是有限的，例如，每个向量寄存器有64个寄存器。向量长度N=64时，需要分组处理。分组方法：n＝Ｋ·N＋ｒ，其中：ｒ为余数，共分Ｋ＋１组。

组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式。2023/9/2140二、向量处理机的分类向量处理机的基本思想是把两个向量的对应分量进行运算，产生一个结果向量。最关键问题是存储器系统能够满足运算部件带宽的要求。主要采用两种方法：

1.存储器－存储器结构

多个独立的存储器模块并行工作

处理机结构简单，对存储系统的访问速度要求很高

2.寄存器－寄存器结构

运算通过向量寄存器进行

需要大量高速寄存器，对存储系统访问速度的要求降低2023/9/21411、存储器－存储器结构下图说明一个具有8个存储体的向量处理机：

MMMMMMMM流水结构加法器ABC=A+B三条互相独立的数据通路，可并行工作，同一个存储模块同时只能为一个通路服务2023/9/2142

参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子C=A+B存储器ABC流水线运算部件(