第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机 第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机 第6章 多处理机系统 第7章 其它计算机结构 2019/1/2

第4章 流水技术与向量处理 4.1 标量流水工作原理 4.2 标量流水中的障碍及控制 4.3 流水线的调度技术 4.4 先进的流水技术 4.5 Pentium微处理器中的流水技术 4.6 向量流水技术 2019/1/2

本章学习要求 掌握标量流水的性能分析及障碍的处理方法 掌握非线性流水调度技术 掌握向量流水机的结构特征、向量指令并行性分析 了解标量流水、超标量流水、超流水及超长指令字计算机的基本工作原理 2019/1/2

提高指令执行速度的主要途径： (1) 提高处理机的工作主频 (2) 采用更好的算法和设计更好的功能部件 (3) 采用指令级并行技术 三种指令级并行处理机： (1) 流水线处理机和超流水线(Super-pipelining)处理机 (2) 超标量(Superscalar)处理机 (3) 超长指令字(VLIW: Very Long Instruction Word)处理机 2019/1/2

4.1 标量流水工作原理 什么是流水线？ 考虑设计一个洗衣机的工作流程，假定它有三道工序：洗涤、清洗、甩干。每个环节为5分钟。 需要完成的任务为3批，则考虑下述工作方式的工作效率： 第一种：串行工作方式，即按照如下方式工作： …… 第1批洗涤 第1批清洗 第1批甩干 第2批洗涤 第2批清洗 第2批甩干 第3批洗涤 第3批清洗 第3批甩干 3批衣服的整个工作时间为3*3*5=45分钟 2019/1/2

第二种：重叠工作方式，设计三个部件，可以同时工作，每个部件只做一样工作，操作方式如下图： 第1批洗涤 第1批清洗 第1批甩干 第2批洗涤 第2批清洗 第2批甩干 第3批洗涤 第3批清洗 第3批甩干 T Δt 3批衣服的工作时间为5*5=25分钟，节省20分钟。 2019/1/2

加速比：串行方式与流水线方式的时间比：上述为 45/25=1.8 效率：即洗衣机的利用率，上述洗衣机的效率是9/15=3/5=60% 引出下述关于洗衣机工作的有关性能特点： 吞吐率：单位时间内完成的任务数TP=n/T 加速比：串行方式与流水线方式的时间比：上述为 45/25=1.8 效率：即洗衣机的利用率，上述洗衣机的效率是9/15=3/5=60% 将一条指令的执行分为几个阶段，让几条指令按重叠或流水方式工作，以提高程序的执行速度。这就引出了计算机中的流水线技术。 2019/1/2

指令的重叠解释与先行控制 计算机系统中广泛存在着重叠工作方式 指令的解释方式一般只有三种：顺序、重叠和流水 重叠和流水给指令的执行带来了高的吞吐率和加速比，同时也给系统增加了障碍 2019/1/2

指令的解释过程 ALU LOAD/STORE IF ID EX MEM WB 取指 译码、读寄存器堆 执行 计算访存有效地址 --- 访存（读或写） WB 结果写回寄存器堆 将读出的数据写入寄存器堆 2019/1/2

一、指令的重叠解释方式 取指令k 分析k 执行k 取指令k+1 分析k+1 执行k+1 1、顺序执行方式 一条指令的执行过程：取指令->分析->执行 执行n条指令所用的时间为： 如每段时间都为t，则执行n条指令所用的时间为：T=3nt 主要优点：控制简单，节省设备。 主要缺点：执行指令的速度慢，功能部件的利用率很低。 取指令k 分析k 执行k 取指令k+1 分析k+1 执行k+1 2019/1/2

如果每个过程的时间相等，则执行n条指令的时间为：T=(1+2n)t 主要优点： 指令的执行时间缩短 功能部件的利用率明显提高 2、重叠执行方式(最简单的流水线方式) 如果每个过程的时间相等，则执行n条指令的时间为：T=(1+2n)t 主要优点： 指令的执行时间缩短 功能部件的利用率明显提高 主要缺点： 需要增加一个IBR 取指 分析 执行 2019/1/2

3、更高重叠度的重叠解释方式 取指k+2 分析k+2 执行k+2 取指k+1 分析k+1 执行k+1 取指k 分析k 执行k 如果三个过程的时间相等，执行n条指令的时间为：T=(2+n)t 理想情况下同时有三条指令在执行 处理机的结构要作比较大的改变，必须采用先行控制方式 取指k+2 分析k+2 执行k+2 取指k+1 分析k+1 执行k+1 取指k 分析k 执行k 2019/1/2

重叠方式对计算机组成的要求 1．访存冲突 分析与取指均要访问主存 解决： 1）采用两个独立编制的存贮器 数据/指令 但增加了复杂性 1．访存冲突 分析与取指均要访问主存 解决： 1）采用两个独立编制的存贮器 数据/指令 但增加了复杂性 2）采用多体交叉存贮器 3）指令缓冲寄存器 2．功能部件的冲突 解决：设置独立的分析部件和执行部件 2019/1/2

3．同步 分析与执行所需的时间不同，要求的是一次 重叠 一次重叠：任何时间都是“分析K+1”与“执行K”的重叠 =>相邻两条指令的重叠 T=(n+1)t 2019/1/2

无条件转移/条件转移当转移成功时，重叠预取无效，变为顺序执行 4．转移 无条件转移/条件转移当转移成功时，重叠预取无效，变为顺序执行 应尽可能不使用或少使用条件转移指令 5．相关 邻近指令之间出现某种关联，为避免出错而不能同时执行的现象。 局部性相关、全局性相关 2019/1/2

2019/1/2

先行控制技术 基本思想：使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。 (a)重叠方式 分析部件空闲 执行部件空闲 分析k+1 分析k 执行k 执行k+1 分析k+2 执行k+2 分析部件空闲 执行部件空闲 (b)先行控制 2019/1/2

缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作 关键：缓冲技术＋预处理技术 缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作 预处理技术：把进入运算器的指令都预处理成R-R型指令，与缓冲技术相结合，为进入运算器的指令准备好所需的全部操作数 先行控制方式使运算器可专注于运算，从而可大幅度提高程序的执行速度 硬件要求：增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。 2019/1/2

工作原理 栈的深度要求：D指缓≥D操作≥ D读栈≥ D写栈 主 存 存 控 指令分析器 先行 指令栈 先行读 数栈 后行写 执行 部件 存 控 指令分析器 先行 指令栈 先行读 数栈 后行写 执行 部件 先行操作栈 数据缓冲栈 栈的深度要求：D指缓≥D操作≥ D读栈≥ D写栈 2019/1/2

二、标量流水工作原理 基本思想：流水是重叠的进一步延伸，使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度。 流水线的表示方法：连接图、时空图、预约表 2019/1/2

流水线的每一个阶段称为流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。 1、简单流水线的连接图表示 流水线的每一个阶段称为流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。 有些复杂指令，在执行阶段也采用流水线方式工作，称为操作流水线。 取指 访存 执行 译码 写回 IF ID EX MEM WB S1 S2 S3 S4 S5 输入 输出 2019/1/2

一种指令流水线 2、流水线的时空图 采用“时空图”表示流水线的工作过程。 一条简单流水线的时空图： 取指 形成操 作数地址 译码 取操 作数 一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机 2、流水线的时空图 采用“时空图”表示流水线的工作过程。 一条简单流水线的时空图： 取指 形成操 作数地址 译码 取操 作数 执行 保存 结果 2019/1/2

一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)： m ED1 时间 空间 t1 t2 t3 t4 t5 ED2 ED3 ED4 ED5 EA1 EA2 EA3 EA4 EA5 MA1 MA2 MA3 MA4 MA5 NL1 NL2 NL3 NL4 NL5 t6 t7 t8 NL：规格化 MA：尾数加 EA：对阶 ED：求阶差 NL MA EA ED t 2019/1/2

3、流水线的预约表 时间 流水段 1 2 3 4 5 6 7 S1 X S2 S3 S4 2019/1/2

三、流水线工作方式 1、流水线的结构 流水线的基本结构中主要包括三大部分：锁存器、时钟、功能段。 流水线中每个段都是由一些执行算术和逻辑功能的组合逻辑线路组成的，它们可以互相独立地对流过的信息进行某种操作，相邻两站由高速锁存器（latch）隔开，信息在各段间的流动靠同时送到各站的时钟信号来控制。 取指 访存 执行 译码 写回 IF ID EX MEM WB S1 S2 S3 S4 S5 输入 输出 指令的流水处理 2019/1/2

S1 S2 Sm 输入 输出 ….. .…. 时钟 流水线的基本结构 2019/1/2

2、流水线工作的三个时间 建立时间、正常流动时间、排空时间。 1 2 3 n n-1 ... 4 5 T 填入 正常 排空 流水时空图 空间 T0=m △ t0 n △ t0 T (m-1) △ t0 (n-1) △ t0 填入 正常 排空 流水时空图 空间 时间 2019/1/2

3、流水线的分级、分类 分级：（处理的级别分类） 部件级(操作流水线)：将复杂的算逻运算组成流水工作方式； 指令级：把一条指令解释过程分成多个子过程 ； 处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中 2019/1/2

功能：单功能流水线（如CRAY-1）、多功能流水线（如TI-ASC） 工作方式：静态流水线、动态流水线 连接方式：线性、非线性 其他分类： 功能：单功能流水线（如CRAY-1）、多功能流水线（如TI-ASC） 工作方式：静态流水线、动态流水线 连接方式：线性、非线性 处理数据：标量流水、向量流水 1 2 3 4 出 入 非线性流水线 2019/1/2

4、流水线举例 1)ASC算术运算流水线（多功能） 输入 相乘 累加 输出 1 6 7 8 乘 输入 减阶 对阶移位 相加 规格化 输出 1 2 3 4 5 8 加 输入 减阶 对阶移位 相加 规格化 相乘 累加 输出 1 2 3 4 5 6 7 8 2019/1/2

静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。 ... 1 2 3 4 n-1 n 5 8 6 7 时间 空间 (段号) 加法 一 二 三 四 乘法 静态多功能流水线时-空图 静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。 2019/1/2

... 1 2 3 4 5 n-1 n 8 6 7 一 二 三 四 五 六 七 动态多功能流水线时-空图 m 时间 加法 乘法 一 二 三 四 五 六 七 动态多功能流水线时-空图 m 区别：如果从软硬功能分配的观点上来看，静态流水线其实是把功能负担较多地加到软件上，以简化硬件；动态流水线则是把功能负担较多地加在硬件上，以提高流水的效能。 2019/1/2

四、标量流水线性能分析 衡量流水线处理机的性能主要是吞吐率、加速比和效率。 1．吞吐率：单位时间内能处理的指令条数或能输出的数据量。吞吐率越高，计算机系统的处理能力就越强。就流水线而言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。 最大吞吐率：流水线达到稳定状态后可获得的吞吐率。 （1）Tpmax=1/t （2）TPmax=1/ max{t1，t2，t3，t4} “瓶颈”子过程： 1 2 3 4 t t 3t t 2019/1/2

子过程3为瓶颈段的时空图 m T S1 S2 S3 S4 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t12 t13 输出 最大吞吐率TPmax=1/3t 2019/1/2

解决瓶颈有两种方法 A： B： 1 31 2 32 33 4 3a 3b 3c 3 瓶颈段细分 重复设置瓶颈流水段 2019/1/2

重复设置瓶颈流水段后的工作时空图 m S1 S2 S3a S3c S3b S4 1 2 3 5 4 6 7 8 9 10 11 12 t1 2019/1/2

实际吞吐率 （1）完成n条指令的解释共需时间 可以看出不仅实际的吞吐率总是小于最大的吞吐率，而且只有当n>>m时，实际的吞吐率才能接近于理想的最大吞吐率。 (2)各功能段时间不相等 2019/1/2

2.效率：设备的利用率，直接反映了处理机结构有 效程度。流水线有建立时间、排空时间，不总是满 负载工作。 各段时间相等： 各段时间不等： 2019/1/2

加速比：M段流水线的速度与等效的非流水线的速 度之比。 各段时间相等: 各段时间不等: 2019/1/2

流水线的吞吐率、加速比与效率的关系 K=6 K=10 任务 个数 加速比 10 2 4 6 8 1 16 32 64 128 因为 因此：E=TP· Δt ，S=k·E 2019/1/2

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

方法二，公式分析法。当流水线中各功能段的 执行时间不相等时，有 完成4个任务时： Tp=4/(15△t) E=24 △t /(4*15△t)=40% Sp=4*6 △t /15△t=1.6 完成40个任务时，如何画时空图呢？？ 方法二，公式分析法。当流水线中各功能段的 执行时间不相等时，有 2019/1/2

2019/1/2

例2、以浮点加法运算为例（四段）各段时间相等，求Z=A+B+C+D+E+F+G+H的TP、E、Sp。 空间 7 1 2 3 4 5 6 5 6 7 5 6 7 5 6 7 15 时间 Z=A+B+C+D+E+F+G+H 1 2 3 4 5 6 7 TP=7/15△t E=7*4/(15*4)=7/15 Sp=4*7/15=28/15=1.87 2019/1/2

例3. ASC计算机功能算术运算流水线各段时间 相等，6次浮点加、 5次定点乘的吞吐率、效率 和加速比。 1,2,3,4,5,8组成加法流水 1 2 3 4 5 6 7 8 对阶 减阶 输出 相加 规格化 相乘 累加 输入 ASC计算机的流水线 1,6,7,8组成乘法流水 2019/1/2

分析：T加=6+(6-1)*1=11 T乘=4+(5-1)*1=8 TP= 11/(11+8)△t =11/19 △t 2 3 4 5 6 8 7 时间 浮加 定点乘 一 二 三 四 五 分析：T加=6+(6-1)*1=11 T乘=4+(5-1)*1=8 TP= 11/(11+8)△t =11/19 △t E= (6*6+5*4) △t /(19*8△t)=11.54% Sp= 56 △t /19 △t =2.94 2019/1/2

4.2 标量流水中的障碍及控制 保持流水线性能条件：不能停顿或断流。 影响流水线性能因素：相关和功能切换。 相关类型： 全局相关：转移指令引起的相关 结果：流水线断流，流水线中后续指令全部作废。 局部相关：资源或结构相关；指令相关；数据相关。 结果：流水线停顿，流水线中后续指令有效。 2019/1/2

一、资源相关 资源相关：功能部件、主存资源 当有多条指令进入流水线后在同一机器周期内争用同一功能部件所引起的相关（冲突） 当有多条指令进入流水线后在同一机器周期内同时访问主存资源 2019/1/2

两条指令同时要用一个加法器 例1： ALU LOAD/STORE IF 取指 ID 译码、读寄存器堆 EX 执行 计算访存有效地址 MEM - 访存（读或写） WB 结果写回寄存器堆 将读出的数据写入寄存器堆 指 令 流水段 不同类型指令中各流水段进行的操作 2019/1/2

例2： 两条指令同时访存造成资源相关 冲突 取指 译码 执行 访存 写回 MEM EX ID IF 指令 i+4 WB i+3 i+2 取指 译码 执行 访存 写回 MEM EX ID IF 指令 i+4 WB i+3 i+2 i+1 Load指令 8 7 6 5 4 3 2 1 时钟 两条指令同时访存造成资源相关 冲突 2019/1/2

解决方法： 9 EX ID IF 指令 i+4 MEM 停顿 i+3 WB i+2 i+1 Load指令 8 7 6 5 4 3 2 1 时钟 9 使i+3指令停顿一拍进入流水线，以解决访存相关； 或重复设置一个存储器；采用先行控制技术 2019/1/2

二、指令相关 后续指令的内容取决于当前指令执行的结果，即指令允许修改引起的相关 解决相关：不准修改指令、变指令相关为数据相关 EX R1 D2 B2 X2 IBM370中的“执行”指令 2019/1/2

三、数据相关 由于流水线中的各条指令间的重叠解释，使得原来对操作数的访问顺序发生了变化，从而导致了数据之间的相关。这种相关有三类：先写后读（改用相关） 、先读后写（用改相关） 、写写相关（改改相关） 。 设有i 和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为： 2019/1/2

RAW读写(先写后读) --- 指令 j 试图在指令 i 写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。 i: R1+R2->R3 j: R3*R4->R5 WAR写读(先读后写) --- 指令 j 试图在指令 i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。 i: R3*R4->R5 j: R1+R2->R3 WAW写写(先写后写) --- 指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。 i: R1*R2->R3 j: R4+R5->R3 2019/1/2

解决数据相关的办法用软件和硬件技术： 时间推后法 旁路技术或相关专用通路技术 例： n : load A IF ID EX WR n+1: load B IF ID EX WR n+2: add A,B IF ID 气泡 EX WR n+3: store C IF ID 气泡 EX WR n+4 : jump K IF ID EX WR n+5: load E 停顿 停顿 停顿。。 n+6 ……… 停顿。。 K: IF ID EX 例中有资源相关、有控制转移相关，这将影响流水线的性能。 2019/1/2

数据相关和定向传递指令 IF ID EX WB IF ID EX WB IF ID EX WB IF ID EX WB IF ID EX 写R1完成 ADD R1,R2,R3 IF ID EX MEM WB 定向传递R1值 SUB R4,R1,R5 IF ID EX MEM WB AND R6,R1,R7 IF ID EX MEM WB OR R8,R1,R9 IF ID EX MEM WB XOR R10,R1,R11 IF ID EX MEM WB 数据相关和定向传递指令 2019/1/2

ALU 运算结果 写RF RF 读RF 操作数寄存器 专用通路（旁路） RF ALU 旁路 Buffer Mult 2019/1/2

四、全局性相关 由转移指令（条件/无条件）引起的相关 转移指令在程序中所占比例约为20-25%，不可忽视 解决这种相关的方法：猜测法、加快和提前形成条件码、加快短循环程序的处理、采用延迟转移技术 2019/1/2

1、猜测法：选取发生概率较高的分支为猜测方向，若猜对，继续执行；否则,作废猜测方向的执行，返回实际转移处。 （1）如何提高猜测命中率 静态猜测法：猜测不成功方向。由程序员和编译程序把发生概率高的分支安排在猜测方向。 动态猜测法：根据转移历史猜测。 I-1 I-2 I+4 I+1 I+2 I+3 I K+3 K+2 K+1 k branch 成功 不成功 2019/1/2

转移目标缓冲器(BTB) 利用BTB(Branch Target Buffer)硬件，动态地预测转移方向 Y = 欲取指令的PC 查找 按正常顺 序执行 N Y = 预测PC值 转移指令地址 转移目标地址 状态 2019/1/2

转移预测原理：用2位二进制数记录实际转移状态(历史位)，高位为1时预测转移发生，高位为0时预测转移不发生。 注意：初始状态、状态修改、猜测方向表示 预测 发生 11 10 不发生 01 00 转移1 不转移0 2019/1/2

猜测执行只完成译码、取操作数或执行但不写结果； 采用后援寄存器保存可能被破坏的状态。 预防猜不中时的加速处理： （2）猜测的后续处理 分支现场的保护及恢复： 猜测执行只完成译码、取操作数或执行但不写结果； 采用后援寄存器保存可能被破坏的状态。 预防猜不中时的加速处理： 预取猜测方向的另一方向的前几条指令，放到缓冲器中，加速猜不中时回头速度。 I-1 I-2 I+4 I+1 I+2 I+3 I K+3 K+2 K+1 k branch 成功 不成功 2019/1/2

2、加快和提前形成条件码 3、优化延迟转移技术 4、加快短循环处理 单条指令的条件码并不一定要等执行完成得到运算结果后才能形成 循环程序判断的提前形成 3、优化延迟转移技术 a.将转移指令前的那条指令调度到延迟槽中； b.将转移目标处的那条指令调度到延迟槽中； c.将转移不发生时该执行的那条指令调度到延迟槽中。 4、加快短循环处理 2019/1/2

五、流水线中的中断处理 流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题 不精确断点法：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。断点就是最后进入流水线的那条指令 2019/1/2

特点：硬件开销小，控制简单，适用于常规的 I/O操作。 申请中断 S1 S8 S7 S6 S5 S4 S3 S2 输入 输出 i+5 i i-1 i+1 i+2 i+3 i+4 i-2 PC： 不精确断点 精确断点 特点：硬件开销小，控制简单，适用于常规的 I/O操作。 2019/1/2

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

例4 在一条单流水线处理机上执行下面的程序。每条指令都要经过“取指”,“译码”,“执行”和“写结果”4个流水段。每个流水段的延迟时间都是5ns。 在“执行”流水段,LS部件完成LOAD或STORE操作,其它操作都在ALU部件中完成,两个操作部件的输出端有直接数据通路与任一操作部件的输入端相连,ALU部件产生的条件码也能够直接送入控制器。 2019/1/2

3:LOOP:LOAD R2,A ;R2 ← A向量的一个元素 4: MUL R2,R1 ;R2 ←(R2)*(R1) 1: SUB R0, R0 ;R0←0 2: LOAD R1,#8 ;向量长度8 3:LOOP:LOAD R2,A ;R2 ← A向量的一个元素 4: MUL R2,R1 ;R2 ←(R2)*(R1) 5: ADD R0,R2 ;R0 ←(R0)+(R2) 6: DJNE R1,LOOP;R1 ←(R1)-1若(R1)≠0则转 7: STORE R0,S ;保存结果 (1)采用静态分支预测技术,每次都预测转移不成功。 画出指令流水线的时空图。计算流水线的吞吐率和 加速比。并分别计算出译码部件和ALU部件的使用 效率。 (2)采用静态分支预测技术,每次都预测转移成功。计 算指令流水线的吞吐率和加速比。并分别计算出译 码部件和ALU部件的使用效率。 2019/1/2

(1)解:每次预测转移不成功,流水线时空图如下: 2 3 4 5 6 取指 写回 ALU LS 译码 7 ... 重复8次 m 52 2019/1/2

(2)解:每次预测转移成功,流水线时空图如下: 1 2 3 4 5 6 取指 写回 ALU LS 译码 7 ... 重复8次 m 2019/1/2

4.3 流水线的调度技术 静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。 动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式两种。 2019/1/2

一、静态调度技术 静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。 非线性流水线中存在着前（反）馈回路，必然会引起功能段的冲突而发生流水线停顿。调度方法会减少停顿时间。 调度方案是基于二维预约表和状态图来进行分析 2019/1/2

1 2 3 4 5 6 7 非线性流水线的连接图 S1 S2 S3 S4 输出 输入 反馈线 S1 X S2 S3 S4 时间 流水段 1 2 3 4 5 6 7 S1 X S2 S3 S4 非线性流水线的预约表 2019/1/2

非线性流水线调度举例 某流水线结构如下： 流水线调度方案如下： S1 S2 S3 S4 S5 入 ① ② ③ ④ ⑥ ⑤ ⑦ ⑧ ⑨出 2019/1/2

指令总拍数为n，流水线有k个段，则形成n×k的预约表，段的使用情况用“×”表示。 预约表如下： （1）形成预约表 指令总拍数为n，流水线有k个段，则形成n×k的预约表，段的使用情况用“×”表示。 预约表如下： × 5 4 3 × × 2 1 9 8 7 6 t S 2019/1/2

（2）由预约表形成禁止表F F={各段中冲突间隔拍数} ---功能段1的禁止间隔拍数为8； ---功能段2的禁止间隔拍数为5和6； ---功能段3的无禁止间隔拍数； ---功能段4的禁止间隔拍数为1； ---功能段5的禁止间隔拍数为1。 F={1，5，6，8} （3）由禁止表F形成初始冲突向量C0 C0 =（10110001）， ci=1冲突，0不冲突。 2019/1/2

（4）由初始冲突向量C0形成状态转换图 a. 取C0分别间隔2、3、4、7拍，且将C0分别逻辑右移2、3、4、7位，高位补0后再与C0按位“或”，形成新的冲突向量C1 、C2 和C3 ； 10110001 10110111 10111101 10111011 初始状态 3 4 2 7 C0 C1 C2 C3 2019/1/2

b. 再分别取C1间隔2、7拍；取C2间隔4、7拍；取C3间隔3、7拍。方法同上，直至全部完成。 10110001 10110111 10111101 10111011 10111111 初始状态 3 4 2 7 C0 C1 C2 C3 C4 注意：向量Ci右移后，总是与原始向量C0作逻辑加。 2019/1/2

（5）根据状态图写出调度方案 每一个闭合回路就是一个调度方案（策略） C0 C1 C2 C3 C4 10110001 10110111 10111101 10111011 10111111 初始状态 3 4 2 7 C0 C1 C2 C3 C4 2019/1/2

平均延时最小的调度方案为最佳调度方案，本例为（3，4）和（4，3）。 本例中调度方案如下： 调度策略 平均间 隔拍数 (2, 7) 4.50 (4, 3) 3.50 (2, 2, 7) 3.67 (4, 3, 7) 4.67 (3, 4) (4, 7) 5.00 (3, 7) (7) 7.00 (3, 4, 7) 平均延时最小的调度方案为最佳调度方案，本例为（3，4）和（4，3）。 对非C0开始的调度方案由流水线控制器完成控制的过渡。 2019/1/2

调度方案的验证 原理：二维预约表 方法：给定任务数，使用每一种可能的调度方案进行调度 验证：调度过程中有无功能段的冲突？ 2019/1/2

例如，按(3,4)调度方案，连续输入3个任务的 调度过程如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S1 √ S2 S3 S4 S5 2019/1/2

按（4，3）调度方案 连续输入6个任务的时空图 S1 S2 S3 S4 S5 m t 2019/1/2

性能分析 设共输入8个任务，按最佳调度方案（平均时延最小3.5拍）（3，4）进行调度，计算流水调度的最大和实际吞吐率 2019/1/2

水线的总值时间为6个时钟周期,所有相继段必须 在每个时钟周期之后才能使用。 例5 设有一4段流水线处理机如下图所示。此流 水线的总值时间为6个时钟周期,所有相继段必须 在每个时钟周期之后才能使用。 (1)列出这一流水线的4行6列的预约表; (2)列出禁止表和画出状态图; (3)求出平均延迟最小的调度方案和最大吞吐率。 S1 S2 S3 S4 输出 输入 2019/1/2

禁止表的原始冲突向量为：F={4}，C=(1000) 解法一：4行6列的预约表(一) 功能段 1 2 3 4 5 6 S1 √ S2 S3 S4 禁止表的原始冲突向量为：F={4}，C=(1000) 2019/1/2

平均延迟最小的 调度方案是： (1,2,3,2)。 最小平均延迟是： 2▲t。 最大吞吐率是： TPmax=1/2▲t。 解法一的状态转移图 1000 1100 1110 1111 1010 1001 1011 1101 1 2 3 解法一的状态转移图 平均延迟最小的 调度方案是： (1,2,3,2)。 最小平均延迟是： 2▲t。 最大吞吐率是： TPmax=1/2▲t。 2019/1/2

禁止表的原始冲突向量为：F={2,4}，C=(1010) 解法二：4行6列的预约表(二) 功能段 1 2 3 4 5 6 S1 √ S2 S3 S4 禁止表的原始冲突向量为：F={2,4}，C=(1010) 2019/1/2

平均延迟最小的 调度方案是： (3)。 最小平均延迟是： 3▲t。 最大吞吐率是： TPmax=1/3▲t。 解法二的状态转移图 1010 1111 1011 1 3 5 解法二的状态转移图 2019/1/2

二、动态调度技术 动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式 优点： （1）能处理某些在编译时无法知道的相关情况 （2）能简化编译程序设计 （3）使代码有可移植性 缺点：相应的硬件较为复杂。 2019/1/2

1、集中式动态调度 静态调度中的指令是按序( In-order )执行，如果一条指令在流水线中发生停顿，后续指令就不再前进了 动态调度可使指令按无序( Out-order )方式工作 集中式动态调度：依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作 2019/1/2

状态记录控制器（记分牌）记录与控制在流水线的EX 段开始。 IF ID 整数部分 浮点加 浮点乘 浮点除 RF 记录控制器 指令 控制/状态 EX MEM WB 集中式动态调度 状态记录控制器（记分牌）记录与控制在流水线的EX 段开始。 2019/1/2

检测功能： 控制功能： 功能部件（资源）冲突； 源、目的REG引起的RAW、WAR、WAW相关。 有冲突或相关的指令推后进入流水线的执行部件，否则正常指令进入流水线的执行部件； 记录功能部件、REG、指令的状态； 根据记录的状态，控制后续指令的进入。 2019/1/2

2、分布式动态调度 此方法是由Tomasulo于1967年提出来的，已在IBM360/91机中采用。 （1） 运算部件：一个加法部件和一个乘除部件。 （2）保存站：加法部件中有A1~A3三个保存站，乘 除部件有M1和M2两个保存站，用来保存当前参加运 算的数据。 2019/1/2

（3） 指令操作缓冲栈：存放经分析后由指令部件送来的指令，译码后， 产生相应的控制信号送到各个部件。 （3）  指令操作缓冲栈：存放经分析后由指令部件送来的指令，译码后， 产生相应的控制信号送到各个部件。 （4）浮点操作数寄存器（FLB）：存放由主存预取来的操作数。 （5）浮点寄存器（FLR）：存放操作数的寄存器。 （6） 存储数据缓冲站（SDB）：存放将写入存储器的结果数据，也有站号。 （7） 公共数据总线（CDB）：以上各部件间的连接总线。 2019/1/2

IBM360/91的浮点运算部件结构框图 加法器 乘/ 除法器 寄存器 1010 1011 1100 1000 1001 6 5 4 3 2 操作数 缓冲器 (FLB) 控 操作栈 (FLOS) 忙 制 位 站号 源1 控制 源2 号 站 存数 (SDB) 加法器 乘/ 除法器 译码器 寄存器 (FLR) M1 M2 A1 A2 A3 1010 1011 1100 FLB 总线 FLR总线 1000 1001 CDB 公共数 据总线 指令处理部件 存储器总线 6 5 4 3 2 1 站号： 0110 0001 F7 F2 F0 保存站 IBM360/91的浮点运算部件结构框图 2019/1/2

通过修改站号（重命名），消除WAR、WAW相关； 通过设置保存站，减少资源相关冲突； 借助CDB作相关专用通路。 S1：(FLB1)→F0 S2： (F0)*(FLB2)→F0 S3： (F0) →A S4： (FLB3)→F0 S5： (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作相关专用通路。 2019/1/2

4.4 先进的流水技术 流水中指令级并行性的进一步开发 粗粒度并行性：在多处理机上分别运行多个进程，由多台处理机合作完成一个程序； 细粒度并行性：指在一个进程中进行操作一级或指令一级的并行处理。 RISC机进一步开发细粒度并行性 2019/1/2

一、超标量流水处理技术 每个时钟周期平均执行指令的条数大于或等于2 超标量处理机典型结构： 多条指令流水线、多个功能部件 先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU,图形加速部件GPU，大量的通用寄存器，两个一级高速Cache 超标量处理机的指令级并行度ILP大于1 2019/1/2

IF ID FA1 FA2 FA3 MD1 MD2 MD3 AL LS 浮点加法部件 乘除法部件 定点ALU部件 取数存数部件 WR 超标量流水线处理机的一般结构 2019/1/2

超标量处理机MC88110的结构 整数 部件 位 操作 浮点 加 乘法 部件 除法 部件 图形 部件 内部总线 读数存 数部件 通用寄 存器堆 扩展寄 存器堆 目标 指令 指令分配 转移部件 数据Cache (8KB) 指令Cache (8KB) 系统总线 32位地址总线 32位数据总线 超标量处理机MC88110的结构 2019/1/2

IF ID FA1 FA2 FA3 MD1 MD2 MD3 AL LS 浮点加法部件 乘除法部件 定点ALU部件 取数存数部件 WR 先行指 令窗口 注：先行指令窗口除了能够做数据相关性分析和功能部件冲突的检测之外，还至少有一套取指令部件和一套指令译码部件 2019/1/2

超标量流水处理机的时空图 IF 时钟 周期 指令 I1 I2 I3 ID EX WR 1 2 3 4 5 6 I4 I5 I6 I7 I8 2019/1/2

超标量流水线的调度 按序发射：当指令按策划功能序的次序发射时，称之为按序发射（in-order issue） 无序发射：为改善流水线性能，可以将有相关的指令推后发射，而将后面的无相关性的指令提前发射，即不按程序原有次序发射指令，称之为无序发射（out-of-order） 按序完成：完成顺序与发射顺序一致 无序完成：完成顺序与发射顺序不一致 2019/1/2

常用的调度方法 按序发射按序完成—静态调度策略；（Pentium) 按序发射无序完成—动态调度策略；（ PentiumII/III ） 无序发射无序完成—动态调度策略。 无论那种调度策略，都要保证程序运行的最终结果是正确的，发射策略由译码控制器完成，完成策略由执行控制器完成。 2019/1/2

1 2 3 4 5 6 7 8 9 10 按序发射按序完成之调度过程 IF1 ID1 L/S WR1 IF2 ID2 部件 FA1 WR2 顺序 (RAW) (WAW) MD1 MD2 MD3 AL I1 I2 I3 I4 I5 I6 指令 时钟周期 1 2 3 4 5 6 7 8 9 10 流水线2 流水线1 I1： LOAD R1，A ；主存单元A→ R1 I2： FADD R2，R1 ；(R1)+( R2) →R2 I3： FMUL R3，R4 ；(R3)×(R4) →R3 I4： FADD R4，R5 ；(R4)+( R5) →R4 I5： DEC R6 ；(R6)-1→ R6 I6： FMUL R6，R7 ；(R6)×(R7) →R6 按序发射按序完成之调度过程 2019/1/2

1 2 3 4 5 6 7 8 9 按序发射无序完成之调度过程 流水线1 I1 IF1 ID1 L/S WR1 时钟周期 流水线2 I2 1 2 3 4 5 6 7 8 9 流水线1 I1 IF1 ID1 L/S WR1 时钟周期 流水线2 I2 IF2 ID2 (RAW) FA1 FA2 FA3 WR2 I3 IF1 ID1 MD1 MD2 MD3 WR1 I4 IF2 ID2 部件 FA1 FA2 FA3 WR2 I5 IF1 ID1 AL WR1 I6 IF2 ID2 (RAW) MD1 MD2 MD3 WR2 I1： LOAD R1，A ；主存单元A→ R1 I2： FADD R2，R1 ；(R1)+( R2) →R2 I3： FMUL R3，R4 ；(R3)×(R4) →R3 I4： FADD R4，R5 ；(R4)+( R5) →R4 I5： DEC R6 ；(R6)-1→ R6 I6： FMUL R6，R7 ；(R6)×(R7) →R6 指令 按序发射无序完成之调度过程 2019/1/2

1 2 3 4 5 6 7 8 无序发射无序完成之调度过程 流水线1 I1 IF1 ID1 L/S WR1 时钟周期 流水线2 I3 IF2 1 2 3 4 5 6 7 8 流水线1 I1 IF1 ID1 L/S WR1 时钟周期 流水线2 I3 IF2 ID2 MD1 MD2 MD3 WR2 先行控制 I4 IF3 ID3 FA1 FA2 FA3 WR1 I2 IF1 ID1 FA1 FA2 FA3 WR2 I5 IF2 ID2 AL WR1 I6 IF2 ID2 MD1 MD2 MD3 WR2 I1： LOAD R1，A ；主存单元A→ R1 I2： FADD R2，R1 ；(R1)+( R2) →R2 I3： FMUL R3，R4 ；(R3)×(R4) →R3 I4： FADD R4，R5 ；(R4)+( R5) →R4 I5： DEC R6 ；(R6)-1→ R6 I6： FMUL R6，R7 ；(R6)×(R7) →R6 指令 无序发射无序完成之调度过程 2019/1/2

超标量流水线的资源冲突 在先进的超标量流水机中，有多个操作（执行）部件，如：ALU、FADD、FMUL、GPU、LSU等 操作部件必须采用流水结构，可减少资源冲突 2019/1/2

I1：FADD R0，R1 ；(R0)+(R1)→R0 I2：FMUL R2，R3 ；(R2)×(R3)→R2 ID1 ID2 FADD WR1 FMUL WR2 I1 I2 I3 I4 1 2 3 4 5 6 7 8 9 10 11 双流水线超标量处理机（操作部件非流水结构） 2019/1/2

I1：FADD R0，R1 ；(R0)+(R1)→R0 I2：FMUL R2，R3 ；(R2)×(R3)→R2 ID1 ID2 FA1 WR1 FM1 WR2 I1 I2 I3 I4 1 2 3 4 5 6 7 8 t 双流水线超标量处理机（操作部件流水结构） FA2 FA3 FM2 FM3 FM4 2019/1/2

二、超流水线处理机 两种定义： 一个周期内能够分时发射多条指令的处理机称为超流水线处理机。 指令流水线有8个或更多功能段的流水线处理机称为超流水线处理机。 提高处理机性能的不同方法： 超标量处理机是通过增加硬件资源为代价来换取处理机性能的。 超流水线处理机则通过各硬件部件充分重叠工作来提高处理机性能。 两种不同并行性： 超标量处理机采用的是空间并行性 超流水线处理机采用的是时间并行性 2019/1/2

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

每个时钟周期分时发送3条指令的超流水线 IF 时钟 周期 指令 I1 I2 I3 ID EX WR 1 2 3 4 5 6 I4 I5 I6 2019/1/2

MIPS R4000处理机的流水线操作 指令 Cache IF：取第一条指令 IS：取第二条指令 RF：读寄存器堆，指令译码 EX：执行指令 DF：取第一个数据 DS：取第二个数据 TC：数据标志校验； WB：写回结果 指令 译码 读寄 存器堆 ALU 数据 标志检验 寄存 器堆 IF IS RF EX DF DS WB TC 2019/1/2

MIPS R4000正常指令流水线工作时序 流水线周期 主时 钟 周期 当前CPU周期 IF IS RF EX DF DS TC WB IF 2019/1/2

三、超标量超流水线处理机 把超标量与超流水线技术结合在一起，就成为超标量超流水线处理机 指令执行时序 超标量超流水线处理机在一个时钟周期内分时发射指令n次，每次同时发射指令m条，每个时钟周期总共发射指令m × n条。 2019/1/2

每时钟周期发射3次,每次3条指令 IF 时钟周期 指令 I1 I2 I3 ID EX WR 1 2 3 4 5 I4 I5 I6 I7 I8 2019/1/2

不同结构计算机的性能分析 标量处理机的并行度(1,1) 超标量处理机的并行度(m,1) 超流水处理机的并行度(1,n) 2019/1/2

标量流水处理机上执行N条指令的时间： 超标量流水处理机上执行N条指令的时间： 2019/1/2

超标量超流水处理机上执行N条指令的时间： 2019/1/2

四、超长指令字(VLIW)计算机 VLIW是以一条长指令实现多个操作的并行执行，减少存储器访问。 主要特点： （1）单一的控制流。只有一个控制器，每个周期启动一条指令。 （2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。 （3）在编译阶段完成超长指令中多个可并行执行操作的调度。 2019/1/2

超长指令字计算机举例 如完成以下运算：C=A+B、K=I+J、 L=M-K、Q=C×K 需以下13条指令完成： （需花14个T ） LOAD A、LOAD B、C=A+B、STORE C、LOAD I、LOAD J、K=I+J、 STORE K、LOAD M、L=M-K、STORE L、Q=C×K、STORE Q 2019/1/2

操作并行度≤4 用VLIW则只需6个T RF (寄存器堆) 主 存 LOAD A LOAD B LOAD I LOAD J C=A+B LD/ST1 LD/ST2 FADD FMUL 存/取1 存/取2 浮点加 浮点乘 操作并行度≤4 LD/ST1 LD/ST2 FADD FMUL LOAD A LOAD B LOAD I LOAD J C=A+B LOAD M STORE C K=I+J STORE K L=M-K Q=C×K STORE L STORE Q 用VLIW则只需6个T 2019/1/2

在下列不同结构的处理机上运行8×8的矩阵乘法C=A×B，计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns，C的初始值为“0”。各操作部件的输出端有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。 例6 2019/1/2

（1）处理机内只有一个通用操作部件，采用顺 序方式执行指令。 解： 需要完成的乘法次数为8×8×8=512次 需要完成的加法次数为8×8×7=448次 执行完成总时间为： 2019/1/2

（2）单流水线标量处理机，有一条两个功能的 静态流水线，流水线每个功能段的延迟时间均为 一个时钟周期，加法操作和乘法操作各经过3个 功能段。 解： IF ID AD1 AD2 AD3 MU1 MU3 MU2 2019/1/2

（3）单流水线标量处理机，处理机内有两条独 立的操作流水线，流水线每个功能段的延迟时间 均为一个时钟周期。 解： IF ID AD1 AD2 AD3 MU1 MU3 MU2 2019/1/2

一条乘法指令和一条加法指令，处理要内有两 条独立的操作流水线，流水线的每个功能段的 延迟时间均为一个时钟周期。（不考虑数据之 （4）超标量处理机，每个时钟周期同时发送 一条乘法指令和一条加法指令，处理要内有两 条独立的操作流水线，流水线的每个功能段的 延迟时间均为一个时钟周期。（不考虑数据之 间的相关性，下同。） 解： 2019/1/2

（5）超流水处理机，把一个时钟周期分为两个 流水级，加法部件和乘法部件的延迟时间都为 6个流水级，每个时钟周期能够分时发射两条指 令，即每个流水级能够发射一条指令。 解： IF ID AD1 AD2 AD3 MU1 MU3 MU2 1 2 3 4 5 6 7 8 9 10 2019/1/2

（6）超标量超流水线处理机，把一个时钟周期 分为两个流水级，加法部件和乘法部件延迟时 间都为6个流水级，每个流水级能够同时发射一 条乘法指令和一条加法指令。 解： 2019/1/2

4.6 向量流水技术 向量流水的基本原理 CRAY-1型向量处理机 增强向量处理性能的方法 2019/1/2

4.6.1 向量流水的基本原理 提高流水性能方法： 向量操作特点 向量操作很适合于流水处理或并行处理。 增加流水线段数，以减少Δt； 每个时钟同时启动多条指令； 减少相关，减少功能变换次数，增加处理指令条数。 向量操作特点 1.向量元素间操作相互独立，且为相同操作。 2.相当于标量循环，对指令带宽的访问要求不高。 3.可采用多体交叉存储器，减少访存延迟。 向量操作很适合于流水处理或并行处理。 2019/1/2

例如：Y=a*X+Y X、Y为向量，长度为64；a为标量 LD F0，a ADDI R4, RX, #512 ；由X向量的末址地装入R4 LOOP: LD F2, 0(RX) ；取向量元素X(i) MULD F2, F0, F2 ；X向量与标量乘 LD F4, 0(RY) ；取向量元素Y(i) ADDD F4, F2, F4 SD 0(RY), F4 ；存结果向量 ADDI RX, RX, #8 ADDI RY, RY, #8 ；地址增量 SUB R20, R4, RX ；R4-RX→R20 JNZ R20, LOOP ；判是否为0 2019/1/2

如果用向量处理机来完成同样的操作 特点： 1、 执行指令6条（标量执行8*64+2=514条）。降低 了存储器对取指带宽的要求。 LD F0，a LDV V1, RX ；装入向量X MULV V2, F0, V1 ；X向量与标量乘 LDV V3, RY ；取向量元素Y ADDV V4, V2, V3 SDV RY, V4 ；存结果向量 特点： 1、 执行指令6条（标量执行8*64+2=514条）。降低 了存储器对取指带宽的要求。 2、标量运算过程中存在的数据相关性，在向量运算 过程中已基本消除（共2次）。 2019/1/2

一、向理处理的方式 有三种处理方式： 1．横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。 2．纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。 3．纵横处理方式，又称为分组处理方式，纵横向加工方式等。横向处理和纵向处理相结合的方式。 2019/1/2

向量处理方式 以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。 for (i = 1；i <= n；i++) y[i] = a[i] ×( b[i] + c[i] ); 2019/1/2

1、横向处理方式 逐个分量进行处理：设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. 存在两个问题： 在计算向量的每个分量时，都发生先写后读的数据相关。流水线性能降低 如果采用多功能流水线，必须频繁进行流水线切换 横向处理方式对向量处理机不适合 即使在标量处理机中，也经常通过编译器进行指令流调度。 2019/1/2

2、纵向处理 也称为垂直处理方式，纵向加工方式等 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条： ADDV T, B, C MULV Y, A, T 这种处理方式适用于向量处理机，数据相关不影响流水线连续工作。不同的运算操作只需要切换1次。 2019/1/2

将长度为n的向量分成若干组，每组长度为N，组内按纵向方式处理，依次处理各组，组间是横向处理方式。 3、纵横向处理方式 将长度为n的向量分成若干组，每组长度为N，组内按纵向方式处理，依次处理各组，组间是横向处理方式。 用于寄存器-寄存器结构的向量处理机中 向量寄存器的长度是有限的，例如，每个向量寄存器有64个寄存器。向量长度N=64时，需要分组处理。 分组方法：n＝Ｋ·N＋ｒ，其中：ｒ为余数，共分Ｋ＋１组。 组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式。 2019/1/2

二、向量处理机的分类 向量处理机的基本思想是把两个向量的对应分量进行运算，产生一个结果向量。最关键问题是存储器系统能够满足运算部件带宽的要求。 主要采用两种方法： 1. 存储器－存储器结构 多个独立的存储器模块并行工作 处理机结构简单，对存储系统的访问速度要求很高 2. 寄存器－寄存器结构 运算通过向量寄存器进行 需要大量高速寄存器，对存储系统访问速度的要求降低 2019/1/2

1、存储器－存储器结构 下图说明一个具有8个存储体的向量处理机： M 流水结构加法器 A B C=A+B 三条互相独立的数据通路，可并行工作，同一个存储模块同时只能为一个通路服务 2019/1/2

一种能实现两个向量相加的流水结构的加法器 参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子 C=A+B A 存储器 流水线运算部件(4) B C 一种能实现两个向量相加的流水结构的加法器 2019/1/2

C=A+B向量处理时序图 1 2 3 4 5 6 7 8 功能部件4 功能部件3 功能部件2 功能部件1 存储体M8 存储体M7 存储体M6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t 1 2 3 4 5 6 7 8 RB6 RB6 RA8 RA8 WD4 WD4 RB5 RB5 RA7 RA7 WD3 WD3 RB4 RB4 RA6 RA6 WD2 WD2 RB3 RB3 RA5 RA5 WD1 WD1 RB2 RB2 RA4 RA4 RB1 RB1 RA3 RA3 RA2 RA2 RA1 RA1 WD8 WD8 WD7 WD7 WD6 WD6 WD5 WD5 RB8 RB8 RB7 RB7 C=A+B向量处理时序图 2019/1/2

2、寄存器-寄存器结构 向量寄存器与标量寄存器的主要差别是： 一个向量寄存器能够保存一个向量，例如：64个64位寄存器。连续访问一个向量的各个分量。 需要有标量寄存器和地址寄存器等。 采用寄存器-寄存器结构的主要优点：降低主存储器的流量。例如：采用寄存器-寄存器结构的CRAY-1与采用存储器-存储器结构的STAR-100比较，运算速度高3倍多，而主存流量低2.5倍。 STAR-100的主存储器流量：32×8W/1.28us=200MW/S CRAY-1的主存储器流量： 4W/50ns=80MW/S 2019/1/2

4.6.2 CRAY-1型向量流水处理机 CRAY-1型向量流水处理机的结构 CRAY-1型向量流水处理机的四类指令 2019/1/2

一、CRAY-1型机的结构 1976年由美国CRAY公司生产 V0-V7共8个向量寄存器，每个寄存器由64个64bit构成；8个64bit的标量寄存器S0-S7；8个24bit的地址寄存器A0-A7；64个24bit的中间寄存器B、 64个64bit的中间寄存器T；VM和VL 4组功能运算部件 2019/1/2

CRAY-1型向理处理机 VM 向量 运算 V0-V7 浮点 主存储器 T 标量 S0-S7 B 地址 A0-A7 VL 加(3) 浮加(6) 标量 标加(3) 地址 主存储器 CRAY-1型向理处理机 2019/1/2

二、向量处理机的四类指令 标量类指令和向量类指令共128条，其中4种向量指令如下图所示： Sj Vk Vi Vj Vk Vi 第一类向量指令 n … 4 3 2 1 Sj Vk Vi n … 4 3 2 1 Vj Vk Vi 第一类向量指令 第二类向量指令 2019/1/2

┇ M LDV 第三类向量指令 ┇ M STV 第四类向量指令 2019/1/2

4.6.3增强向量处理性能方法 多功能部件的并行执行 链接技术 条件语句和稀疏矩阵的加速处理 向量归约操作的加速处理 2019/1/2

一、多功能部件的并行执行 由于向量处理机处理每个功能部件，与每个向量寄存器Vi之间有总线互连。每个运算部件是流水操作，故其操作可重叠（并行） 并行操作条件： (1)不存在向量寄存器使用冲突 不允许出现RAW、WAR、WAW、RAR相关。 如：V4←V1+V2 V5←V2×V3 (2)不存在功能部件使用冲突 每种功能部件一般只设置一个。 如：V3←V1×V2 V6←V4×V5 2019/1/2

二、链接技术 利用向量寄存器之间先写后读的数据相关性，加快向量运算的技术 链接技术采用了“相关专用通道”思想，实现向量流水之间的“链接” 例如：有如下3条浮点向量指令： V3 ← A V2 ← V0＋V1 V4 ← V2×V3 2019/1/2

3条向量指令的执行示意图如下： I1：V3←A I2：V2←V0＋V1 I3：V4←V2×V3 ┇ M A LDV V3 ┇ V2 V1 6 ┇ V2 V1 V0 ADDV I2：V2←V0＋V1 1 6 ┇ V4 V3 V2 MULV I3：V4←V2×V3 1 7 2019/1/2

若三条指令串行执行，即每次只有前条指令结束，才执行后继指令，那么三条指令执行的总时间为： 如果每一个时钟周期的延迟称为1拍，在Cray-1机中LD指令需6拍，浮点加6拍，浮点乘7拍，向量寄存器的存与取的传送各为1拍，内存的传送为1拍。 若三条指令串行执行，即每次只有前条指令结束，才执行后继指令，那么三条指令执行的总时间为： T1=[(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1)+N-1]=3N+22(拍) 若第一、二条指令并行与第三条串行： T2=[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15(拍) 若第一，二条指令并行与第三条链接： T3=[(1+6+1)+(1+7+1)+(N-1)]=N+16(拍) 可以看出采用并行与链接后，可以很有效的改善性能。 2019/1/2

D B C 存储器 V4 V3 V2 A 访存 V1 V0 浮点加 浮点乘 1 2 3 4 5 6 7 访存与浮点加并行， 再与浮点乘链接 LD V3，A ADDV V2，V0，V1 MULTV V4，V2，V3 并行和链接操作图 2019/1/2

(1) 没有向量寄存器冲突(RAM,WAR,WAW,RAR)和运算部件(同一功能)冲突。 实现链接的条件： (1) 没有向量寄存器冲突(RAM,WAR,WAW,RAR)和运算部件(同一功能)冲突。 (2) 只有第一个结果送入向量寄存器的那一个周期可以链接。 (3) 先行的两条指令产生运算结果的时间必须相等。 (4)共用向量寄存器中向量长度、起始地址、偏移量、步长均相等。 2019/1/2

三、条件语句和稀疏矩阵的加速 Do 100 I=1,64 If (A(i) NE 0) Then A(i)=A(i)-B(i) Endif 100 continue 通过对A向量的测试后，形成一屏蔽向量。A(i) 元素为0时，屏蔽向量中对应位置“0” 2019/1/2

注：SENSV 为屏蔽向量生成指令 稀疏矩阵也可采取类似的方法来实现向量化 LDV V1, RA ；装入向量A到V1 LDV V2, RB LD F0, #0 ；装入浮点0 SENSV F0,V1 ；若V1(i) NE F0中相应位,将VMi置1 SUBV V1,V1,V2 ；在屏蔽向量控制下进行减法操作 CVM ；屏蔽向量置为全1 STV RA, V1 注：SENSV 为屏蔽向量生成指令 稀疏矩阵也可采取类似的方法来实现向量化 2019/1/2

四、向量归约操作的加速 归约(Reduction)操作难于向量化，因为它是递推(Recurrence)操作的一个特例，归约的结果将得到一个标量值。 Dot = 0.0 Do 10 I=1,64 10 dot=dot+A(i)*B(i) 此循环存在着迭代层间 的数据相关，无法直接 向量化 可将此循环分成可向量化部分和递推部分 2019/1/2

第一部分循环可向量化，第二部分仍需递推。 第二部分可采用递推折叠法(Recursive doubling)， Do 10 I=1,64 10 dot(i)=A(i)*B(i) Dot1=0.0 Do 20 I=1,64 20 dot1=dot1+dot(i) 第一部分循环可向量化，第二部分仍需递推。 第二部分可采用递推折叠法(Recursive doubling)， 使叠加向量长度缩短的方法完成求和。 2019/1/2

典型例题和部分习题解答 5.1 设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为Δt、2Δt和3Δt。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。 （1）顺序执行方式。 （2）仅“取指令”和“执行”重叠。 （3）“取指令”、“分析”和“执行”重叠 （4)先行控制方式 2019/1/2

（2）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令的执行同时结束，那么所需要的时间为： 解答： （1）顺序执行需要的时间如下： （2）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令的执行同时结束，那么所需要的时间为： （3）取指令、分析和执行重叠 (4)先行控制方式 2019/1/2

5.2 一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为Δt。开始5个Δt，每间隔一个Δt向流水线输入一个任务，然后停顿2个Δt，如此重复。求流水线的实际吞吐率、加速比和效率。 [解答]流水线的时空图如下： 2019/1/2

我们可以看出，在（11n+1）Δt的时间内，可以输出5n个结果，如果指令的序列足够长（n→∞），并且指令间不存在相关，那么，吞吐率可以认为满足： 加速比为： 从上面的时空图很容易看出，效率为： 2019/1/2

5.3 用一条5个功能段的浮点加法器流水线计算 每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。 [解答]首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下： 2019/1/2

这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号。 I1： R1←A1+A2 I2： R2←A3+A4 I3： R3←A5+A6 I4： R4←A7+A8 I5： R5←A9+A10 I6： R6←R1+R2 I7： R7←R3+R4 I8： R8←R5+R6 I9： F←R7+R8 这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号。 2019/1/2

部件m R2 R4 R1 R3 R5 R6 R7 R8 F 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 7 8 9 3 1 2 3 4 5 6 7 8 9 2 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 21Δt R1=A1+A2 R5=A9+A10 R2=A3+A4 R6=R1+R2 R8=R5+R6 R3=A5+A6 R4=A7+A8 R7=R3+R4 F=R7+R8 2019/1/2

整个计算过程需要21Δt，所以吞吐率为： 加速比为： 效率为： 2019/1/2

5.4 流水线由4个功能部件组成，每个功能部件的延迟时间为⊿t。当输入10个数据后，间歇5⊿t ，又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。 2019/1/2

[解答]按题意可得4个功能部件流水时的时空关系如下图所示 3 2 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 时间(⊿t) 5⊿t 所以，按周期性工作时的流水线平均吞吐率为 Tp=10/(14⊿t)=5/(7⊿t) 2019/1/2

5. 5 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A. B. C 5.5 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A*B*C*D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图(b)形式实现同一计算时，求该流水线的效率及吞吐率。 阶加 尾乘 规格化 ⊿t 3⊿t 积 操作数 图(a) 阶加 尾乘1 尾乘2 尾乘3 规格化 积 ⊿t 3⊿t 图(b) 2019/1/2

[分析]为了减少运算过程中的操作数相关，A*B*C*D应改为采用((A*B)*(C*D)) 的算法步骤进行运算。 [解答]按图(a)组织，实现A*B*C*D的时空关系如下图(A)所示。 时间 部件 输入 输出 A B C D A*B C*D A*B*C*D 13 规格化 尾乘 阶加 图(A) 吞吐率TP=3/(13⊿t) 效率E=(3×5⊿t)/(3×13⊿t)=5/13=38.5% 2019/1/2

流水线按图(b)组织时，实现A*B*C*D的时空关系如图(B) 吞吐率TP=3/(11⊿t) 时间 部件 输入 输出 A B C D A*B C*D A*B*C*D 规格化 尾乘3 尾乘2 尾乘1 阶加 图(B) 11 流水线按图(b)组织时，实现A*B*C*D的时空关系如图(B) 吞吐率TP=3/(11⊿t) 效率E =(3×5⊿t)/(5×11⊿t)=3/11=27.3% 2019/1/2

画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。 5.6 一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算： 画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。 2019/1/2

这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图（不完全）如下，图中的数字是指令号。 解答：为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示： I1： R1←A1*B1 I2： R2←A2*B2 I3： R3←A3*B3 I4： R4←A4*B4 I5： R5←A5*B5 I6： R6←A6*B6 I7： R7←R1+R2 I8： R8←R3+R4 I9： R9←R5+R6 I10： R10←R7+R8 I11： F←R9+R10 这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图（不完全）如下，图中的数字是指令号。 2019/1/2

部件m R1 R6 R7 R8 R10 F 6 1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 4 1 2 3 4 5 6 3 7 8 9 10 11 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 22Δt 乘法 R1=A1*B1 R2=A2*B2 R3=A3*B3 R4=A4*B4 R5=A5*B5 R6=A6*B6 R7=R1+R2 R8=R3+R4 F=R9+R10 R9=R5+R6 R10=R7+R8 加法 2019/1/2

整个计算过程需要22Δt，所以吞吐率为： 加速比为： 效率为： 2019/1/2

的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间流水线的效率。 5.7 有一个双输入端的加-乘双功能静态流水线，由经过时间为⊿t、2⊿t、2⊿t、⊿t的1、2、3、4四个子过程构成。加法按1→2→4连接，乘法按1→3→4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A*(B+C*(D+E*F))+G*H 的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间流水线的效率。 2019/1/2

[解答]根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如下图所示。图中已标出了流水线入、出端的数据变化情况。 [分析]因为是加-乘双功能静态流水线，为了能有高的吞吐率，应减少流水线的功能切换次数。因此，宜将算法调整成先一连串的乘，然后再切换成一连串的加。这样，将计算式展开成 A*B＋A*C*D＋A*C*E*F＋G*H.对于该表达式的计算，自然应先进行乘法流水。为了减少因先写后读相关而等待的时间，应尽量安排对计算式子项数最多的乘法先进行操作。此外，由于流水线中瓶颈子过程为2⊿t ，所以，流水输入端最快也只能每隔2⊿t输入一组数据。 [解答]根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如下图所示。图中已标出了流水线入、出端的数据变化情况。 2019/1/2

根据上图的流水时空图，可以看出，完成全部运算的时间 为24⊿t。在此期间的流水线效率为 E=(6×4⊿t+3×4⊿t)/(24⊿t×4)=3/8=37.5% 4 3 2 1 子过程 输入 输出 A C E F AC D EF ACD B ACEF G H AB GH AB+ACD ACEF+GH 最终结果 24 时间 乘法 加法 2019/1/2

5.8 在一个4段的流水线处理机上需经7拍才能完成一个任务，其预约表如下表所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此流水调度方案，输入6个任务，求实际的吞吐率。 1 2 3 4 5 6 7 S1 √ S2 S3 S4 2019/1/2

[分析]二维的预约表其实就是一个任务在流水时的时空图。在求出最佳调度方案后，要按流水调度方案输入6个任务时，只需按调度间隔时间点调度即可。要注意，间隔大于等于任务流经流水线最大拍数N（本例N=7）时，调入任务也不会发生冲突。在调度方案中计算出的最小平均延迟有多个时，应取其首项延迟小的。如首项延迟最小的相同，则取次项延迟小的，依次类推。这样，当按调度方案调入的任务数是调度意义周期性的任务数的整数倍时，可使实际的吞吐率更高些。 2019/1/2

[解答] 延迟禁止表F={2,4,6} 初始冲突向量C=(101010) 2019/1/2

状态转移图如下图所示。 7 101010 7 7 5 5 1 111111 3 101011 7 3 5 101111 状态转移图 初始状态 2019/1/2

各种调度方案及其相应的平均延迟如表所示。 平均延迟(拍) (1,7) 4 (3,5) (5,3) (5) 5 (3,7) (5,3,7) (5,7) 6 (7) 7 2019/1/2

由上表可知，最小平均延迟为4拍。此时流水线的最大吞吐率 TPmax=1/4(任务/拍) 最佳调度方案宜选其中按(l,7)周期性地调度的方案。 若按(3,5)调度方案输入6个任务，全部完成的时间为 3＋5＋3＋5＋3＋7=26（拍） 实际吞吐率TP=6/26(任务/拍) 若按(5,3)调度方案输入6个任务，全部完成的时间为 5＋3＋5＋3＋5＋7=28（拍） 实际吞吐率TP=6/28(任务/拍) 可见最佳的方案应当为（1，7）调度方案，输入6个任务的实际吞吐率较之其它方案的要更高些。 时间 ① ② ③ ④ ⑤ ⑥ 1 7 1 7 1 7 结果 2019/1/2

本章重点回顾 标量流水的性能分析（吞吐率，效率和加速比）、非线性流水的调度（根据二维预约表求出最佳调度方案）、向量流水中指令组执行时间的分析 2019/1/2

作业：4、8、11、17 The End 2019/1/2