您好、欢迎来到现金彩票网!
当前位置:双彩网 > 先行指令站 >

第3章流水线技术要点解读ppt

发布时间:2019-07-04 01:53 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第 3 章 流水线技术 主讲: 顾一禾 本章学习内容 流水线的基本概念和工作原理 流水线性能分析 流水线操作中存在的主要障碍和解决方法 向量处理机 3.1 重叠执行和先行控制 3.1.1 重叠执行 1. 顺序解释方式 一条指令完全解释执行完毕后,才开始对下一条指令进行解释执行。 顺序解释方式的特点 控制简单,节省设备。 处理机执行指令的速度慢。 功能部件的利用率很低。 2. 重叠解释方式 在两条相邻指令的解释过程中,某些不同解释阶段在时间上存在重叠部分。这样在一条指令解释执行完成之前就可以开始下一条指令的解释工作。 重叠方式 1 重叠方式 2 设各阶段周期均为t0,则执行n条指令共需 T=nt0+2t0=(n+2)t0 重叠解释方式的特点 与顺序执行方式相比,缩短了程序的执行时间。 提高了功能部件的利用率。 需要增加硬件支持。 需要设置独立的取指令部件、指令分析部件和指令执行部件。 访问主存冲突的解决方法 ⑴ 程序与数据分存于两个独立的存储器中 两个独立的存储器独立编址和控制,可以同时访问,这样可以解决取指与取数的访存冲突问题。 ⑵ 指令和数据仍然混合存放在同一个主存中,但设置两个Cache,即指令Cache和数据Cache。 这种程序空间和数据空间相互独立的系统结构被称为哈佛结构。 ⑶ 采用多模块交叉存取技术 将数据与程序存放在内存不同的存储体内,即可同时访问。但此方法有一定的局限性。 ⑷ 采用指令缓冲站,存放预取的后续指令 在主存空闲时,将所需的后续指令预取到指令缓冲存储区中。在“取指令”阶段需取指时,到指令缓冲存储区中取;而在取操作数时,到内存取。 指令缓冲站的工作过程 先行控制下的一次重叠工作方式 采用指令缓冲站方法时,由于访问寄存器速度较快,可取指与分析指令合并为一步,任何时候只允许上条指令的“执行”与下条指令的 “分析”相重叠。这种重叠工作方式称为“一次重叠”。 采用一次重叠工作方式,完成n条指令所需的执行时间为: T=(n+1)×t0 因为一次重叠工作方式中前后指令的重叠时间有一定的约束,因此只需要一套指令分析和执行部件就可以完成重叠工作,使得硬件简单。 执行时间不等时的一次重叠工作方式 当取指和分析部件的执行时间不等时,执行时间短的部件,必须等待执行时间长的部件功能的完成,导致部件的空闲,使得完成n条指令所需的执行时间变为: 3.1.2 先行控制 缓冲技术:在工作速度不固定的两个功能部件之间设置缓冲器,用以平滑它们的工作。 预处理技术:预取指令、对指令进行加工以及预取操作数等。 先行控制技术: 将缓冲技术和预处理技术相结合,通过对指令流和数据流的预处理和缓冲,使指令分析部件和执行部件都能分别连续不断地工作。 先行控制方式的基本思想 在控制器内设置先行读数站,先行操作站,后行写数站等,使分析部件和执行部件能够分别连续不断地分析和执行指令。 采用先行控制后指令的执行情况 理想情况下,指令执行部件应该一直忙碌。连续执行n条指令的时间为: 先行控制的基本结构 采用先行控制方式的处理机结构 三个独立的控制器 指令分析(控制)器:完成指令译码,形成操作数的有效地址,进行指令预处理。 存储控制器:完成对存储器的读写控制。 运算控制器:完成对运算器的操作控制。 四个缓冲站 设置缓冲站的目的:平滑主存、指令分析部件、运算器三者之间的工作。 先行指令站:预取并存放后续指令。 先行读数站:预取并存放后续指令所需的操作数。 先行操作站:将预处理后的指令变换成运算器能够执行的操作命令并保存。 后行写数站:接收运算器的运算结果,向主存发出写数请求。 各缓冲站均由一组若干个能快速访问的存储单元和相关的控制逻辑组成,均采用先进先出的工作方式。 各缓冲部件的深度(个数): D指缓≥D操作栈≥D读数≥D写数 存储器控制器响应存储器请求的优先级: 通道→写数→读数→取指 3.2 流水线的基本概念 流水方式 把一个重复的过程分为若干个子过程,由专门的功能部件来实现。 把多个处理过程在时间上错开,每个子过程都可以有效地在其专用功能段上与其它子过程同时执行。 流水线的级(段) 流水线中的每个子过程及其功能部件称为流水线的级或段,段与段相互连接形成流水线。 流水线的深度 流水线中的段数。 流水线举例 指令流水线 浮点加法流水线 流水处理的时空图 时空图从时间和空间两个方面描述流水线的工作过程。 在时空图中,横坐标代表时间,纵坐标代表流水线段指令流水线的时空图 流水寄存器(锁存器) 流水线每一个功能部件后面的缓冲寄存器(锁存器),称为流水寄存器。 作用:在流水线相邻的两段之间传送数据,以保证提供后面要用到的数据,并把各段的处理工作相互隔离。 如果每个流水段的延迟时间(通过时间)均为Δts ,锁定时间为Δtl ,则每功能段的处理时间Δti为: Δti= Δts+Δtl 流水处理机的最高工作频率为: 若每个流水段的延迟时间不等,则最高工作频率为: 流水技术的特点 流水线把一个处理过程分解为若干个子过程(段),每个子过程由一个专门的功能部件来实现。 流水工作时,信息从上一级向下一级流动,由流水线中的公共时钟控制,实现同步传送。 流水线中各段的时间应尽可能相等,否则将引起流水线堵塞、断流。时间长的段将成为流水线的瓶颈。 流水技术适合于大量重复的时序过程,只有在输入端不断地提供任务,才能充分发挥流水线的效率。 流水线的通过和排空时间 通过时间:第一个任务从进入流水线到流出结果所需的时间。 经过通过时间后,流水线进入满载。 排空时间:最后一个任务从进入流水线到流出结果所需的时间。 在通过和排空时间内,流水线都不是满载的。 流水线 流水线.按处理级别分 ⑴ 部件级——运算操作流水线 将复杂的算逻运算分段组成流水工作方式。 例:将浮点加法操作分成求阶差、对阶、尾数相加、结果规格化四个子过程。 浮点加法器流水线的时空图 ⑵ 处理机级——指令流水线 把一条指令解释过程分成多个子过程组成流水工作方式。 如前面所提到的将指令执行过程分为取指、译码、执行、访存及写回五个子过程。 ⑶ 系统级——处理机间流水线(宏流水线) 将系统中多个处理机串联起来,对同一数据流进行不同的处理,每个处理机完成整个任务中的一部分专门任务。 2.按功能分 ⑴ 单功能流水线 只完成一种固定功能的流水线。 如浮点加法或乘法流水线。 ⑵ 多功能流水线 同一流水线的各功能段可进行不同的连接,使流水线在不同时间或同一时间内完成不同的功能。 多功能流水线. 按工作方式分 ⑴ 静态流水线 在同一时间内,流水线只能以一种功能方式工作。 静态流水线可以是单功能流水线,也可以是多功能流水线。 当是多功能流水线时,则从一种功能方式变为另一种功能方式时,必须先排空流水线,然后为另一种功能设置初始条件后方可使用。 对于静态多功能流水线来说,只有当输入的是一串相同的运算任务时,流水线的效率才能得到充分的发挥。 静态流水线时空图 静态流水线 ⑵ 动态流水线 在同一时间内,可以将流水线中的不同功能段连接成不同的功能子集(前提条件是功能部件的使用不发生冲突),以完成不同的运算功能。 动态流水线时空图 动态流水线 静态、动态流水线.按连接方式分 ⑴ 线性流水线 从流水线的输入到输出,每个功能段只允许经过一次,流水线中不存在反馈回路。 一般的流水线均属于线性流水线。 ⑵ 非线性流水线 流水线各功能段之间除了串行连接外,还存在反馈回路,因此从流水线的输入到输出过程中,某些功能段将被数次通过。 非线性流水线适合于进行线性递归的运算。 非线 →S1 →S2 为了防止两条或两条以上的指令对同一功能段的争用,非线性流水线需要对输入流水线的指令进行比较复杂的控制。 非线性流水线通常使用预约表来进行分析。 预约表 5.按任务流动方式分 ⑴ 顺序流动流水线 输出端的任务流出与输入端的任务流入顺序完全相同。 ⑵ 乱序流动流水线 输出端的任务流出与输入端的任务流入顺序不完全相同。 在乱序流动流水线中,当某任务阻塞时,后面的任务可绕过它继续流动。 例如有的指令需要读数据,有的不需要,在不冲突的情况下,只要执行部件有空闲,不读数的指令可先在执行部件中执行。 6. 标量处理机与向量流水处理机 流水线处理机 指令执行部件中采用了流水线的处理机。 标量处理机 处理机不具有向量数据表示和向量指令,仅对标量数据进行流水处理。 向量流水处理机 具有向量数据表示和向量指令的处理机。 向量流水处理机是向量数据表示和流水技术的结合。 3.3 流水线 吞吐率Tp 单位时间内流水线能处理的任务数量或输出的结果数。 设任务数为n,流水线段数为m,完成n个任务的时间为Tm,则吞吐率Tp ⑴ 最大吞吐率Tpmax 流水线达到稳定状态后可获得的吞吐率。 ⑵ 实际吞吐率Tp 流水线实际工作时的吞吐率。 Tp<Tpmax 设在m段流水线中,各段的延迟时间均为Δt,可以利用时空图分析该流水线完成n个任务的实际吞吐率和流水线的最大吞吐率。 完成n个任务所需的总时间 完成n个任务所需的总时间: Tm=(n+m-1) Δt 完成n个任务的实际吞吐率: 最大吞吐率: 最大吞吐率就是流水线满载时的吞吐率,实际吞吐率与最大吞吐率的关系: 可见,实际吞吐率小于最大吞吐率 Tp<Tpmax 只有当 n>>m时,Tp≈Tpmax 设完成一个任务需要的时间为T,则各段的延迟时间可视为Δt: ∴ m↗ 或 Δt ↙ 都可以增加流水线的吞吐率。 如果流水线各段的延迟时间不等,则吞吐率取决于最慢段所需的时间。 流水线Δt 完成n个任务的实际吞吐率: 最大吞吐率: 本题中Tpmax=1/3Δt 流水线瓶颈问题的解决方法 ⑴细分瓶颈段 将瓶颈子过程进一步细分成若干个子子过程,使每一个子子过程与其他子过程时间相等。 如将瓶颈段S3进一步分成S3a,S3b和S3c三个时间上相当于Δt的子子过程,便可消除S3瓶颈,使最大吞吐率由1/3Δt 恢复成 1/Δt。 瓶颈部分细分后的时空图 ⑵重复设置瓶颈段 在瓶颈段,并联设置多套功能段部件,使它们轮流工作。 如在瓶颈段S3并联设置3套功能部件,可使吞吐率恢复到1/Δt。 重复设置瓶颈段后的时空图 重复设置瓶颈功能段的控制复杂,需要在流水线中设置数据分配器和数据收集器。 解决流水线 加速比 Sp 加速比:采用流水方式后的工作速度与等效的顺序串行方式的工作速度之比。 对n个求解任务,若用串行方式完成工作需要时间为Tl,用m段流水线完成工作需要时间为Tm,每个功能段的延迟时间为Δt,则流水线的加速比为: 最大加速比: 由最大加速比 Spmax=m 可知: 增加流水线的深度m,可以提高流水线的最大加速比 。 但只有在任务数n很大的情况下,才能有效地发挥流水线 加速比与流水段数、任务数的关系 若流水线各功能段的延迟时间不等,则加速比为: 3.3.3 效率 E 效率:流水线中的各功能段的利用率。 由于流水线有建立和排空时间,因此各功能段的设备不可能一直处于工作状态,总有一段空闲时间。一般用流水线各段处于工作时间的时空区与流水线中各段总的时空区之比来衡量流水线的效率。 流水线的最大效率 当n→∞时,流水线的效率最高。 若流水线各段的延迟时间不同,则效率为: 吞吐率、加速比和效率的关系 E=Tp·Δt=Sp/m=Sp/Spmax 效率是实际加速比和最大加速比之比。 只有E=1时,才能达到Sp=m 当Δt不变时,效率与吞吐率成正比。所以为提高效率所采用的方法,对提高吞吐率也有好处。 例:设有浮点加法器流水线,试分析算式 Z=A+B+C+D+E+F+G+H 在流水线中执行时的流水线的性能。 为提高运算速度,可采用算法: Z={[(A+B)+(C+D)]+[(E+F)+(G+H)] } = [(1)+(2)]+[(3)+(4)] = [一]+[二] 吞吐率: 加速比: 效率: 例:设有静态加、乘双功能流水线段组成加减流水线段组成乘法流水线,各段的延迟时间均为Δt,流水线的输出可直接返回输入端或暂存到相应的缓冲寄存器中。 现有A、B两个向量,每个向量有四个元素,要求在此流水线上计算: 请适当安排操作顺序,在最短时间内完成计算工作,并求出流水线工作时的实际吞吐率、加速比和效率。 解: (1)选择适合于流水线+B1)×(A2+B2)和(A3+B3)×(A4+B4); 然后求总的乘积结果。 实际工作的时空图 从图中可见,在总共18Δt时间内输出7个结果,因此该流水线的实际吞吐率为: Tp=7/18Δt 流水线%。 若用串行方法完成上述的加乘操作,则需要做4次加法和3次乘法,求一次和需6Δt,求一次积需4Δt,总共需要时间: Tl=4×6Δt+3×4Δt=36Δt 加速比: Sp=Tl/Tm=36Δt/18Δt=2 流水线效率较低的原因 ⑴ 多功能流水线在按某种功能流水时,总有一些当前功能不需要的段处于空闲状态。 ⑵ 静态流水线在功能切换时,要等待前一种运算全部排空,才能重新连接、切换功能,需要有排空和建立两种不同功能流水的额外开销。 ⑶ 经常发生下一步要等待上一步计算结果反馈的情况,即出现数据相关问题。 ⑷ 任务数少时,建立和排空时间所占的比例大。 流水线较适合于求解的操作相同,且输入、输出间相互独立的连串运算。 当任务充足时,流水线的吞吐率可接近于最大吞吐率,流水线,而加速比也可接近于流水线的段数值。 例:有一条由5段组成的动态多功能流水线△t,其余各段时间均为△t,而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算: 试计算其吞吐率、加速比和效率。 (1) 选择适合于流水线工作的算法 应先计算A1×B1、A2×B2、A3×B3、A4×B4; 再计算 (A1×B1)+(A2×B2)、 (A3×B3)+(A4×B4); 最后求总的累加结果。 实际工作的时空图 性能计算 吞吐率: 加速比: 效率: 3.3.5 流水线. 瓶颈问题 理想情况下,流水线在工作时,其中的任务是同步地每一个时钟周期往前流动一段。 当流水线各段不均匀时,机器的时钟周期取决于瓶颈段的延迟时间。 在设计流水线时,要尽可能使各段时间相等。 2. 流水线的额外开销 ⑴ 流水寄存器延迟 ⑵ 时钟偏移开销 ⑴ 流水寄存器延迟 流水寄存器需要建立时间和传输延迟 建立时间:在触发写操作的时钟信号到达之前,寄存器输入必须保持稳定的时间。 传输延迟:时钟信号到达后到寄存器输出可用的时间。 ⑵ 时钟偏移开销 流水线中,时钟到达各流水寄存器的最大差值时间。(时钟到达各流水寄存器的时间不是完全相同) 流水线段数的选择 如果流水线段数过多,时钟周期很小,以至于与时钟偏移和流水寄存器的附加开销相当,会导致在一个时钟周期内没有足够时间用于有效工作,流水线也就失去了作用。 设在非流水线部件上完成一个任务所需的时间为t;在同等速度的m段带锁存器的流水线上完成同样任务的时间为: t/m+d d为锁存器的延迟时间。 流水线的最大吞吐率: 由于流水寄存器延迟和时钟偏移开销对流水线的性能有较大的影响,特别是当流水深度比较大、时钟周期比较小时,其影响更为突出,所以计算机系统的设计人员必须选用高性能的锁存器作为流水线寄存器。 流水线的段数与成本 设流水线的总造价为:C总=C+mh C:流水线各功能段总成本,h:锁存器成本 根据son对流水线的性能价格比PCR的定义,得流水线的性能价格比为: 为得到最佳PCR,即PCR的最大值,对m求导,得到性能价格比PCR的极值,由于大于零的极值只有一个,因此,这个极值就是最大值。 当性能价格比PCR取得最大值时,它所对应的流水线 最佳流水线段数为: t为流水线的总延迟时间。 性价比与流水线的段数 在设计一条流水线的时候,可以根据极限公式,在流水线的总延迟时间t一定的情况下,通过调整流水线本身的价格C,锁存器的延迟时间d和锁存器的价格h来选取最佳的流水线。 一般流水线段以上的流水线段以上的流水线的处理机称为超流水线处理机。 注:早期规定5段之内为普通流水。 关于流水线的几个问题 流水线并不能减少(而且一般是增加)单条指令的执行时间,但却能提高吞吐率。 增加流水线的深度(段数)可以提高流水线的性能。 流水线的深度受限于流水线的额外开销。 当时钟周期小到与额外开销相同时,流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。 3. 流水线的冲突问题 如果流水线中的任务之间存在关联,则可能需要任务之间的相互等待,形成流水线的冲突,引起流水线的停顿,从而影响流水线的性能。 解决流水线的冲突问题是流水线设计中要解决的重要问题之一。 3.4 流水线段流水线 一条指令的执行过程: IF→ID→EX→MEM→WB 取指令周期(IF) IR ← Mem[PC] ;指令寄存器IR ←指令 PC值加4 ;(假设每条指令占4个字节) 指令译码/读寄存器周期(ID) 译码 用IR中的寄存器编号去访问通用寄存器组,读出所需的操作数。 执行/有效地址计算周期(EX) 不同指令所进行的操作不同: 存储器访问指令:ALU把所指定的寄存器的内容与偏移量相加,形成用于访存的有效地址。 寄存器-寄存器ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算。 寄存器-立即数ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数进行运算。 分支指令:ALU把偏移量与PC值相加,形成转移目标的地址。同时,对在前一个周期读出的操作数进行判断,确定分支是否成功。 存储器访问/分支完成周期(MEM) 该周期处理的指令只有load、store和分支指令。其他类型的指令在此周期不做任何操作。 load指令:用上一个周期计算出的有效地址从存储器中读出相应的数据。 store指令:把指定的数据写入这个有效地址所指出的存储器单元。 分支指令:分支“成功”,就把转移目标地址送入PC。分支指令执行完成。 写回周期(WB) ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALU运算指令:结果数据来自ALU。 load指令:结果数据来自存储器系统。 不同类型指令在各功能段中完成的操作 在上述实现方案中: 分支指令需要 4 个时钟周期(如果把分支指令的执行提前到ID周期,则只需要 2 个周期)。 store指令需要 4 个周期。 其他指令需要 5 个周期完成。 指令执行过程的流水线实现 每一个周期作为一个流水段。 在各段之间加上流水寄存器(锁存器)。 5段流水线的两种描述方式 ⑴类时空图描述 ⑵ 数据通路形式描述 采用流水线方式实现时需解决的问题 ⑴ 保证不会在同一时钟周期要求同一个功能段做两件不同的工作。 例如,不能要求ALU同时做有效地址计算和算术运算。 ⑵ 避免IF段的访存(取指令)与MEM段的访存(读/写数据)发生冲突。 可以采用分离的指令存储器和数据存储器; 一般采用分离的指令Cache和数据Cache。 ⑶ 因为ID段和WB段可能要访问同一寄存器,即: ID段:读;WB段:写,为了防止寄存器冲突,可将写操作安排在时钟周期的前半拍完成,将读操作安排在时钟周期的后半拍完成。 ⑷ 考虑PC的问题 流水线为了能够每个时钟周期启动一条新的指令,就必须在每个时钟周期进行PC值的增量操作,并保留新的PC值。这种操作必须在IF段完成,以便为取下一条指令做好准备。 (需设置一个专门的加法器) 但分支指令也可能需要改变PC的值,而且是在MEM段进行,这会导致冲突。 3.4.2 相关 要使流水线具有良好的性能,必须设法使流水线能畅通流动,即必须能做到充分流水,不发生断流。 相关:两条指令之间存在某种依赖关系。 如果两条指令相关,则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。 使流水线断流的相关问题 局部相关:指令执行过程中的资源冲突、数据相关。 全局相关:控制相关,如转移指令、中断的处理 相关的三种类型 数据相关(也称真数据相关) 名相关 控制相关 1. 数据相关 数据相关:相邻指令的数据存在一定的关系。 对于两条指令 i(在前)和 j(在后),如果下述条件之一成立,则称指令j与指令i数据相关。 指令j使用指令i产生的结果; 指令j与指令k数据相关,而指令k又与指令i数据相关。 数据相关具有传递性。 数据相关反映了数据的流动关系,即如何从其产生者流动到其消费者。 例:下面这一段代码存在数据相关。 Loop: L.D F0,0(R1) // F0为数组元素 ADD.D F4,F0,F2 // 加上F2中的值 S.D F4,0(R1) // 保存结果 DADDIU R1,R1,-8 // 数组指针递减8个字节 BNE R1,R2,Loop // 如果R1≠R2,则分支 当数据的流动是经过寄存器时,相关的检测比较直观和容易。 当数据的流动是经过存储器时,相关的检测比较复杂。 原因: 相同形式的地址其有效地址未必相同。 形式不同的地址其有效地址却可能相同。 2. 名相关 名:指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名,但是它们之间并没有数据流动,则称这两条指令存在名相关。 指令j 与指令i 之间的两种名相关 反相关:如果指令j写的名与指令i读的名相同,则称指令i和j发生了反相关。 指令j 写的名=指令i 读的名 输出相关:如果指令j和指令i写相同的名,则称指令i和j发生了输出相关。 指令j写的名=指令i写的名 名相关的两条指令之间并没有数据的传送。 如果一条指令中的名改变了,并不影响另外一条指令的执行。 可以通过换名技术改变指令中操作数的名来消除名相关。 换名技术 换名技术:通过改变指令中操作数的名来消除名相关的技术。 寄存器换名:对寄存器操作数进行换名。 寄存器换名既可以用编译器静态实现,也可以用硬件动态完成。 例:下述代码中存在名相关 DIV.D F2,F6,F4 ;F2←F6/F4 ADD.D F6,F0,F12 ;F6 ←F0+F12 SUB.D F8,F6,F14 ;F8 ←F6-F14 DIV.D和ADD.D在F6存在反相关。 进行寄存器换名(F6换成S)后,变成: DIV.D F2,F6,F4 ADD.D S,F0,F12 SUB.D F8,S,F14 3. 控制相关 控制相关:指由分支指令引起的相关。 为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行。 典型控制相关是“if-then”结构,例如: if p1 { S1; }; S; if p2 { S2; }; 控制相关带来的两个限制 与一条分支指令控制相关的指令不能被移到该分支之前,否则这些指令就不受该分支控制了。 如上例中,then 部分中的指令不能移到if语句之前。 如果一条指令与某分支指令不存在控制相关,就不能把该指令移到该分支之后。 如上例中, 不能把S移到if语句的then部分中。 3.4.3 流水线冲突 流水线冲突:由于相关的存在,使得流水线中的下一条指令不能在指定的时钟周期执行。 三种流水线冲突: ① 结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突,也称为资源冲突。 ② 数据冲突:当指令在流水线中重叠执行时,因数据相关而发生的冲突。 ③ 控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。 ①、②由局部相关引起,③由全局相关引起。 流水线冲突带来的问题 导致错误的执行结果。 流水线可能会出现停顿,从而降低流水线的效率和实际的加速比。 约定 当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则继续进行(否则就永远无法消除冲突)。 3.4.3.1 结构冲突 当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突。 (资源冲突、资源相关) 当发生结构冲突时,流水线中某种指令组合将因为争用资源而不能正常执行。 导致结构相关的常见原因: 功能部件不是完全流水 资源份数不够 例:访存冲突 有些流水线处理机只有一个存储器,将数据和指令放在一起,访存指令会导致访存冲突。 解决办法一: 插入暂停周期, 即 “流水线气泡”或“气泡”。引入暂停后的时空图 引入暂停后的时空图 解决方法二 设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。 为了减少硬件成本,有时流水线设计者允许结构冲突的存在 主要原因: 如果把流水线中的所有功能单元完全流水化,或者重复设置足够份数,那么所花费的成本将相当高。 3.4.3.2 数据冲突 数据冲突 当相关的指令靠得足够近时,它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序,使之不同于它们非流水实现时的顺序,则发生了数据冲突。 根据指令读访问和写访问的顺序,可以将数据冲突分为三种类型。 1. 写后读冲突(RAW) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 设有指令 i 和 j ,i 在 j 之前进入流水线。 写后读冲突:指令j对某单元或寄存器的读出先于i指令对同一单元或寄存器的写入。 即先后进入流水线的指令i与指令j之间关于同一操作数相关。 写后读冲突也称为先写后读相关、流相关、WR相关、RAW相关等。 RAW是最常见的数据冲突,对应于线. 写后写冲突(WAW) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 写后写冲突(WAW ):指令j对某单元或寄存器的写入先于i指令对同一单元或寄存器的写入。 写后写冲突由输出相关引起。 可能发生写后写冲突的流水线: 乱序流水线。 流水线中不只一个段可以进行写操作。 当先前某条指令停顿时,允许其后续指令继续前进。 写后写冲突也称写写相关、WW相关、WAW相关、写后再写相关等。 3. 读后写冲突(WAR) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 读后写冲突(WAR ):指令j对某单元或寄存器的写入先于i指令对同一单元或寄存器的读出。 读后写冲突由反相关引起。 可能发生读后写冲突的流水线: 乱序流水线。 有些指令的写结果操作提前了,而且有些指令的读操作滞后了。 指令被重新排序。 读后写冲突也称先读后写相关、变量名相关、反相关、RW相关、WAR相关等。 不同类型的数据相关 数据相关的分类 3.4.3.3 解决数据相关的办法 ⑴ 时间后推法 遇到数据相关时,就停顿后继指令的运行,直至前面指令的结果生成并写入寄存器。 时间后推法将使流水线有较长的停顿。 ⑵ 采用定向技术 定向技术也称旁路技术或相关专用通路技术 定向技术的关键思想: 在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方,那么就可以避免停顿。 定向技术的实现: 在执行过程中建立直接的专用通道,将执行结果直接送往需要的执行部件。 采用定向技术消除数据冲突 工作过程 采用定向技术后的流水线数据通路 采用定向技术后的数据通路情况 当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时,控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。 结果数据不仅可以从某一功能部件的输出定向到其自身的输入,而且还可以定向到其他功能部件的输入。 到数据存储器和ALU的定向路径 例 DSUB R1,R2,R3 LD R5,0(R1) SD R5,12(R1) 需要停顿的数据冲突 并不是所有的数据冲突都可以用定向技术来解决。 例: LD R1,0(R2) DADD R4,R1,R5 AND R6,R1,R7 XOR R8,R1,R9 无法将LD指令的结果定向到DADD指令 装入延迟的解决方法 无法将LD指令的结果定向后续指令的情况也称为RISC机流水线中的装入延迟。 解决方法:设置流水线互锁机制。 作用:检测发现数据冲突,并使流水线停顿,直至冲突消失。 实现方法:增加流水线互锁硬件,实现插入“停顿”的功能。 插入停顿的过程 插入停顿前后的时空图 减少定向传送次数的方法 在ID段中,将读寄存器堆的操作安排在ID段的后半部分,在WB段中,将写寄存器堆操作安排在WB段的前半部分,以减少定向传输操作。 ⑶ 依靠优化编译解决数据冲突 让编译器重新组织指令顺序来消除冲突 这种技术称为指令调度或流水线调度。 例: 执行A=B+C时的装入延迟导致的暂停 指令调度技术 由于LOAD的执行时间不确定,所以优化编译不能从根本上解决问题。 3.4.3.3 控制冲突 控制冲突即控制相关,主要是由转移指令引起的,是一种全局性的相关。 当转移发生时,将使流水线的连续流动受到破坏。因此比起数据相关来,控制相关会使流水线丧失更多的性能,使流水线的吞吐率和效率严重下降。 执行分支指令的结果 分支成功: PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后,才改变PC值。 不成功或者失败: PC的值保持正常递增,指向顺序的下一条指令。 处理分支指令最简单的方法 “冻结”或者“排空”流水线 。 优点:简单。 前述5段流水线中,改变PC值是在MEM段进行的,给流水线个时钟周期的延迟。 简单处理分支指令:分支成功的情况 简单处理分支指令:分支失败的情况 当分支失败时,实际上分支后第一条指令已经正确取出,再重复IF周期已无必要,这时流水线空等不是一种好的选择。 由分支指令引起的延迟称为分支延迟。 分支指令在目标代码中出现的频度:每3~4条指令就有一条是分支指令。 设:流水线,分支指令出现的频度为30% 则:流水线 正常程序的流水线吞吐率: 有转移程序时的流水线吞吐率: 使流水线的性能降低 减少分支延迟的方法 在流水线中尽早判断出分支转移是否成功。 尽早计算出分支目标地址。 后续的讨论假设: 判断工作被提前到ID段完成,即分支指令是在ID段的末尾执行完成,所带来的分支延迟为一个时钟周期。 1. 静态转移预测 当流水线译码出某指令为条件转移指令时,在其所需的条件码建立之前,先将一个方向猜测为成功路径,通常是选取发生概率较高的路径,并在转移条件码生成之前只对这个方向上的若干条指令进行预取、译码和取操作数,按该方向继续流动。 若猜测失败,必须返回原分支点重新执行另一分支方向。 ⑴ 预测分支失败 允许分支指令后的指令继续在流水线中流动,就好象什么都没发生似的。 若确定分支失败,将分支指令看作是一条普通指令,流水线正常流动。 若确定分支成功,流水线就把在分支指令之后取出的所有指令转化为空操作,并按分支目地重新取指令执行。 要保证:分支结果出来之前不会改变处理机的状态,以便一旦猜错时,处理机能够回退到原先的状态。 ⑵ 预测分支成功 假设分支转移成功,并从分支目标地址处取指令执行。 起作用的前提:先知道分支目标地址,后知道分支是否成功。 在前述的5段流水线中,因为判断分支成功和分支目标地址的计算均在EX段完成,所以这种方法对减少该流水线的分支延迟没有任何好处。 若判断分支成功和分支目标地址的计算在后续功能段中实现,则此方法可以减少的分支延迟。 ⑶ 延迟分支 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成,不管分支是否成功,都要按顺序执行延迟槽中的指令。 延迟分支以及指令的执行顺序 具有一个分支延迟槽的流水线的执行过程 分支延迟指令的调度 任务:在延迟槽中放入有用的指令。 调度工作由编译器完成。能否带来好处,取决于编译器能否把有用的指令调度到延迟槽中。 三种调度方法 从前调度 从目标处调度 从失败处调度 调度前后的代码 三种方法的要求及效果 分支延迟受到两个方面的限制 可以被放入延迟槽中的指令要满足一定的条件。 编译器预测分支转移方向的能力。 进一步改进:分支取消机制(取消分支) 分支延迟槽中存放预测指令。当分支的实际执行方向和事先所预测的一样时,执行分支延迟槽中的指令,否则就将分支延迟槽中的指令转化成一个空操作。 “预测成功-取消”分支的执行过程 预测分支成功的情况下,分支取消机制的执行情况 ⑷ 加快短循环程序的处理 循环操作是一种特殊的条件转移。循环操作是否结束,主要根据循环操作次数是否已达到原来规定次数。 短循环程序:循环段中的指令数目少于指令缓冲器长度。 若将短循环程序段全部放入指令缓冲器中,就可在整个短循环程序段执行过程中不必再访问主存,而只需重复执行这一循环段,从而可加快执行速度。 2.动态转移预测 动态转移预测:根据转移历史预测转移方向。 动态转移预测用于提高转移方向的猜准率。 静态转移预测方法不考虑转移历史,动态转移预测方法考虑了转移历史,因而有较高的猜准率。 一种具有较高猜准率的动态方法是考虑以前两次转移的历史。 TT:00; TN:10 NT:01 ; NN:00 这种方法仅当两次连续猜错时,预测状态才会发生改变。如从11状态变为10,再变为00。 经在RISC机上实际测试,这种方法的猜准率可高达83%。 3.5 非线性流水线的调度 例:分析以下非线个任务时的性能。 吞吐率: 加速比: 效率: 3.5.1 功能段的使用冲突 功能段的使用冲突:几个任务在同一时刻争用同一流水功能段。 为了避免冲突,需要延迟输入新任务进入流水线。 非线性流水线的调度: 找出一个最小的循环周期,按此周期向流水线输入任务,使流水线既不产生功能冲突,又可以获得最高的吞吐率和效率。 非线性流水线主要依据“预约表”来规划调度方案 非线形流水线的连接图和预约表 一张预约表可能与多个流水线连接图相对应 一个流水线连接图可能对应与多张预约表 3.5.2 非线性流水线. 根据流水线的连接图和一个任务通过流水线的顺序列出预约表。 预约表中的冲突情况 用预约表描述冲突的另一种方法 2. 根据预约表建立禁止表 ⑴ 启动距离(等待延迟时间) 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离(Initiation Interval)或等待时间(Latency)。 启动距离通常用时钟周期数来表示,它是一个正整数。若启动距离是n,表示两次输入之间需隔n个时钟周期。 ⑵ 禁止启动距离 引起功能部件冲突的启动距离。 即预约表中同一行中两个“×”之间的距离。 禁止表:所有禁止启动距离构成的集合。 上图中, F={1,5,6,8} 即要想避免冲突,相邻两个任务进入流水线的间隔拍数就一定不能为1,5,6,8拍。 ⑶允许启动距离 在非线性流水线中的所有功能段,任何时刻都不会引起部件功能冲突的启动距离。 (4)启动循环 使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。 3. 由禁止表形成原始冲突向量 冲突向量:一个n位的位向量 C=(Cn,Cn-1、…、C2、C1) Ci=0:允许输入; Ci =1:禁止输入 n:最止启动距离(所有启动距离中的最大值) 原始冲突向量:由禁止表直接形成的冲突向量。 如根据禁止表 F={1,5,6,8}得到的原始冲突向量为:C=(10110001) 注意:Cn总为1 因为冲突向量中的C2、C3、C4和C7均为0,所以第二个任务可距第一个任务2拍、3拍、4拍或7拍后流入流水线. 形成新的冲突向量 根据原始冲突向量,按允许启动距离输入下一任务,当该任务进入流水线后,将形成新的冲突向量。再根据新的冲突向量中按允许启动距离输入下一任务,就可以形成新的冲突向量,以便确定后续任务何时可输入。 新的冲突向量的形成方法: 根据现行冲突向量,选择允许启动距离 i,将现行冲突向量右移 i 位,再与原始冲突向量相或,即可得到新的冲突向量。( i 的值可以大于最止距离 ) 流水线状态图 按新冲突向量的形成方法依次重复,一直进行到不再产生新的冲突向量,并形成闭合回路为止,即可得到流水线状态图。 例:按原始冲突向量 C=(10110001)形成的流水线. 根据流水线状态图选择调度方案 流水线状态图中的每一个闭合回路都是一种调度方案,其中平均延迟时间最小者为最佳调度方案(最小启动循环)。 最佳调度方案:3,4,3,4, … 或 4,3,4,3, … 采用最佳调度方案:3,4,… 完成5个任务时,流水线的性能评价。 实际吞吐率:Tp=5/23Δt 效率:E=(10+15+5+10+5) Δt/(5×23)Δt=9/23 最大吞吐率:Tpmax=1/平均延迟=1/ 3.5Δt 不等间隔的调度方案平均延迟时间短,但控制复杂。 为了简化控制,可采用间隔为7 的调度方案,成为等间隔(恒定循环)调度方案,但平均延迟时间增加了。 上述调度方法是一种无冲突调度,它是一种不改变流水线结构的调度方法。 这种调度方法的关键在于合理安排时序与控制部件。 这些理论最早是由E.S.Davidson及其学生们于1971年提出来的。 例:一条4功能段的非线性流水线,每个功能段的延迟时间都相等,它的预约表如下: (1)写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线)求最佳启动循环和最佳平均启动距离(平均延迟时间)。 (4)求平均启动距离最小的恒定循环。 解: (1)禁止向量为:(2,4,6) 初始冲突向量:C= (101010) (2)构造状态图 根据所选择的调度策略,可以得到如下的流水线 采用非计算延迟功能段进行优化调度 无冲突调度的问题 当采用最小启动循环启动非线性流水线,流水线中的许多流水段还有空闲。反映在预约表中还有空白的格子。即使是最繁忙的流水段也还有空闲,因此,按照上一节介绍的调度方法得到的最小启动循环,实际上并不能使非线性流水线充分发挥效率。 最小平均启动距离的范围 L.E.Shar于1972年提出了流水线最小平均启动距离的限制范围。 对于一条静态可重构的流水线,通过预约表可以得到其最小平均启动距离的范围。 ⑴ 最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。实际上也就是同一个任务通过流水线中任意一个流水段的最多次数。 ⑵ 最小平均启动距离应小于或等于状态图中任意一个简单循环的平均启动距离。 ⑶ 最小平均启动距离的上限是冲突向量中1的个数再加上1。 这个限制在许多情况下是相当宽松的。 优化调度的基本思想: 让流水线瓶颈段的功能充分发挥,不要空闲,使非线性流水线得到最好的吞吐率、加速比和效率且平均延迟时间最短。 1. 确定最小平均启动距离 最小平均启动距离是预约表中任意一行中“×”的最大个数。 2. 选择按最小平均启动距离等间隔输入作为最佳调度方案。 3. 运用预留算法在流水线中插入非计算延迟功能段,实现优化调度。 预留算法 将预约表中任意一行中与前一个“×”的距离为最小平均启动距离的整数倍的“×”所在的时钟周期通过延迟的方法预留出来。 采用预留算法来调度非线性流水线,可以达到最优调度。 这是一种改变流水线结构的调度方法 前例中非线功能段之间加入非计算延迟功能段D1和D2。 例:流水线的逻辑图和预约表如下,求流水线的最佳调度方案和优化调度方案。 解:禁止表:F={2,4,6} 原始冲突向量:C=(101010) 状态图: 调度方案可选:1,7; 3,5; 5,3 启动距离最小的恒定循环调度方案为:5 优化调度方案 最小平均启动距离:2 采用预留算法: 完成5个任务时,两种调度方案的性能比较: ① 采用3,5 最佳调度方案 实际吞吐率:Tp=5/23Δt 效率:E=(10+10+5+10) Δt/(4×23)Δt =35/92≈0.38=38% 最大吞吐率:Tpmax=1/平均延迟=1/ 4Δt ②采用优化调度方案,最小平均启动距离为2 实际吞吐率:Tp=5/16Δt 效率:E=(10+10+5+10) Δt/(4×16)Δt =35/64 ≈0.55=55% 最大吞吐率:Tpmax=1/平均延迟=1/ 2Δt 3.6 向量处理机 在流水线处理机中,设置向量数据表示和相应的向量指令,称为向量处理机。 不具有向量数据表示和相应的向量指令的流水线处理机,称为标量处理机。 标量流水机的性能提高的制约 (1) 流水线工作的时钟周期不可能取得很短。 流水深度的增加会使时钟周期缩短,但也增加了流水线中出现相关性的可能性,将造成较大比例的断流,而为等待相关消除就需要更多的时钟周期,这导致每条指令执行所需的时钟周期数的增加。 当时钟周期减小时,将加剧时钟在流水线入口和出口处的扭斜错位程度,使级间锁定变得困难,导致不能可靠工作。 (2) 取指令及译码的速率受限。 即在一个时钟周期内最多只能启动一条指令,通常称为Flynn瓶颈。 3.6.1 向量流水处理的主要特点 (1) 在向量操作中,每个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的,有利于发挥流水线的性能,允许向量流水线) 一条向量指令相当于一个标量循环,可降低对指令访问带宽的要求,也消除了由循环转移可能引起的控制相关。 (3) 若向量指令所要访问的向量元素均相邻,则可利用多模块、交叉存取的方法加快向量元素的存取速度,减少访存等待时间的开销。 在对相同数量的数据项进行操作时,向量操作要比一串标量指令操作更快。 向量流水机可使访存和有效地址计算流水化。 高档的向量机允许多个向量操作同时进行,从而可开发对不同元素进行多个向量操作的并行性。 3.6.2 向量机的基本系统结构 向量机系统结构的分类 ① 存储器 — 存储器工作方式向量机 向量操作的源向量和目的向量都取自或存放到主存中。 ② 寄存器 — 寄存器工作方式向量机 向量操作的源向量和目的向量都取自或存放到向量寄存器中。 典型的向量机基本系统结构 向量机主要由标量流水部件和向量流水部件组成: 向量功能部件 向量取存部件 向量寄存器或向量缓冲部件 向量控制器 标量寄存器 标量处理部件等 向量处理机的典型结构图 例:一个典型向量求解问题: Y=a×X+Y 其中X和Y为向量,初始值存放在存储器中,a为标量。 采用双精度运算时的算法:a乘X后再加Y。 (1) 用标量机运算 用标量机运算,采用循环程序: 用标量指令对向量中的每个元素进行一次乘、加和存储操作。 为了实现循环操作,每次必须指明对X和Y中元素位置的下标变量并进行增量,同时使操作次数减1,判别循环是否结束。 设X和Y向量的首地址分别存放在Rx和Ry中,向量元素长度为64。 LD F0,a ;标量a装入F0 ADDI R4,Rx,#512 ;将向量元素的末地址装 ;入R4中 LOOP:LD F2,0(Rx) ;取向量元素X(i) MULD F2,F0,F2 ;a与X(i)相乘 LD F4,0(Ry) ;取向量元素Y(i) ADDD F4,F2,F4 ;aX(i)与Y(i)相加 SD 0(Ry),F4 ;存结果向量元素 ADDI Rx,Rx,#8 ;增量向量元素X下标 ADDI Ry,Ry,#8 ;增量向量元素Y下标 SUB R20,R4,Rx ;R4-Rx→R20,计算是 ;否到达限界值 BNZ R20,LOOP ;若循环未结束,转LOOP (2) 用向量机运算 LD F0,a ;标量a装入F0 LV V1,Rx ;装入向量X,LV为向量取指令 MULTV V2,F0,V1 ;向量X与标量a相乘 LV V3,Ry ;装入向量Y ADDV V4,V2,V3 ;向量加aX+Y SV Ry,V4 ;存结果向量, ;SV为向量存指令 标量机与向量机计算Y=a×X+Y的比较 因为向量指令是对64个元素进行操作,且没有对元素下标变量增量和判循环是否结束的指令,所以向量机只需执行6条指令即可完成操作,从而大大降低了对指令带宽的要求。 3.6.3 向量处理方法 向量机中对向量的加工方式的要求: 尽量避免出现数据相关和尽量减少对向量操作功能的转换。 1. 横向加工方式 横向加工方式:逐个求出结果向量的各个元素。 例:设A、B、C和D都是长度为N的向量,需进行向量运算 D=A×(B+C),采用横向加工方式时是按向量顺序计算的。 d1=a1×(b1+c1) d2=a2×(b2+c2) … dN=aN×(bN+cN) 处理过程:逐个求D中的N个分量 k←b1+c1 :其中k为暂存单元 d1←k×a1 k←b2+c2 d2←k×a2 …… 在每个向量元素的加乘运算中,都会发生数据相关。 当采用静态流水线次乘和加功能的转换。 共出现N次相关,2N次功能转换。 横向加工方式只适合于标量循环算法,不适合于向量流水处理。 2.纵向(垂直)加工方式 纵向(垂直)加工方式:先对所有元素执行一种相同的运算,再对所有元素执行另一种相同的运算。 如上例中,先纵向加工所有B和C向量中元素对的相加操作,中间结果暂存到k1~kN中,然后再纵向加工所有对应元素的乘法操作。 先算: k1=b1+c1 k2=b2+c2 … kN=bN+cN 再算: d1=a1×k1 d2=a2×k2 … dN=aN×kN 用向量指令形式表示为: K=B+C D=K×A 在两条向量指令间有1次数据相关, 1次流水线功能切换。 纵向加工方式的特点 ⑴ 纵向加工方式可获得较高的吞吐率。 由于元素个数N不受限制,且需要有一个暂存中间向量K(由k1~kN个分量组成),所以纵向加工方式适合于存储器 — 存储器工作方式的向量机。 ⑵ 纵向加工方式对主存带宽要求高。 为减轻主存的负担,可在主存与流水部件之间设置缓冲器。 3.纵横向加工方式 纵横向加工方式: 将向量元素分成长度为某个固定值的若干组,每个组内采用纵向加工方式,组之间采用横向加工方式。 纵横向加工方式适合于采用寄存器 — 寄存器方式工作的向量机。 注意:因向量寄存器的长度有限,当向量长度超过向量寄存器可表示的最大限度n时,必须分组加以处理。 设向量长度为N, s为组数,r为余数(余下的部分也作为一组处理) 则:N=s×n+r 其中n≤N,r<n,n、s、r均为正整数。 第一组计算: k1~n=b1~n+c1~n d1~n=a1~n×k1~n 第二组计算: kn+1~2n=bn+1~2n+cn+1~2n dn+1~2n=an+1~2n×kn+1~2n … 纵横(分组)处理方式 每组内各有两条向量指令,各组内有一次数据相关,需2次流水功能切换,需n个中间向量寄存器单元。 采用纵横向加工方式,组内的元素计算均在寄存器中完成,可大大减少访存次数,降低了对主存带宽的要求,减少了因存储器冲突而引起的等待。提高了处理速度。 3.6.4 Cray-1向量机 美国Cray公司于1976年提供的巨型机产品。 运算速度每秒亿次浮点运算。 主频:80MHz 字长:64位 其速度高的原因之一是采用了层次结构的存储器系统。 Cray-1 处理机结构图 (1)主存与流水结构运算器之间有一级或两级的中间存储器。 向量运算: 8个64个分量的向量寄存器组V:V0 ~ V7 每个分量为一个64位寄存器。 向量指令能对向量寄存器的分量进行连续的重复处理。 (2)执行向量指令时,流水结构运算器在一个时钟周期内从两个V寄存器得到一对操作数,完成某种操作后用一个时钟周期的时间把结果送入另一个V寄存器。 (3)主存储器与V寄存器之间的数据传送以成组传送的方式进行。 向量流水线是从向量寄存器而不是从主存储器取数据。同样,从流水线输出的结果向量也是送回向量寄存器。 存储器和工作寄存器之间的数据通路可以看成是具有固定时间延迟的数据传送流水线类向量指令 CRAY-1向量处理的特点 每个向量寄存器Vi都有连到6个向量功能部件的单独总线。 每个向量功能部件也都有把运算结果送回向量寄存器组的总线。 只要不出现向量寄存器冲突(Vi冲突)和功能部件冲突,各Vi之间和各功能部件之间都能并行工作,大大加快了向量指令的处理。 Vi冲突:并行工作的各向量指令的源向量或结果向量使用了相同的Vi。 例:源向量相同 V3←V1+V2 V5←V4∧V1 功能部件冲突:并行工作的各向量指令要使用同一个功能部件。 例:都需使用乘法功能部件 V3←V1×V2 V5←V4×V6 3.6.5 增强向量处理性能的方法 1. 多功能部件的并行操作 在向量机中采用独立的多个功能部件并行工作。 并行约束条件: ① 不存在向量寄存器使用冲突。 向量寄存器使用冲突是指并行工作的向量指令中的源向量或结果向量使用相同的向量寄存器。 ② 不存在功能部件使用冲突。 功能部件冲突是指同一功能部件为多条并行工作向量指令所使用。 例1: ① V0←V1+V2 无冲突情况,可以并行处理 V5←V3×V4 例2: ② V0←V1+V2 运算时发生向量寄存器使用 V3←V1×V4 冲突,不可以并行处理 两条指令不能同时执行,必须在第一条指令执行完,将V1释放后,第二条指令方可开始执行。 因为两条指令中使用V1时的首元素下标可能不同,向量长度也可能不同,从而难以由V1同时向两条指令提供所需的源向量。 ③ V3←V1+V2 运算时发生功能部件冲突, V6←V4+V5 不可以并行处理 在理想情况下,若有m个部件并行工作,可使运算速度提高m倍,但实际上由于程序本身并行度有限和可能发生上述的冲突情况,因此能完全并行工作的功能部件数总是小于m的。 3.6.6 提高向量处理机性能的方法 设置多个功能部件,使它们并行工作。 采用链接技术,加快一串向量指令的执行。 采用循环开采技术,加快循环的处理。 采用多处理机系统,进一步提高性能。 3.6.6.1 设置多个功能部件 设置的多个独立功能部件能并行工作,并各自按流水方式工作,从而形成了多条并行工作的运算操作流水线个单功能流水部件: 向量部件:向量加,移位,逻辑运算 浮点部件:浮点加,浮点乘,浮点求倒数 标量部件:标量加,移位,逻辑运算,数“1”/计数 地址运算部件:整数加,整数乘 3.6.6.2 链接技术 链接特性: 当相邻两条指令存在先写后读相关时,只要前一条指令的结果向量的第一个元素产生并存入结果向量寄存器,就可以将它作为下一条指令的源操作数,启动下一条指令的运算,从而将两个或两个以上的功能部件链接起来。 链接技术: 当从一个流水线部件得到的结果直接送入另一个功能流水线的操作数寄存器时所发生的连接过程。即中间结果不必送回存储器或寄存器,并在向量操作完成以前就使用它。 在寄存器 — 寄存器系统结构中,所有的向量操作数在把它们送入流水线之前,都要预先装入向量寄存器中。中间和最后结果(流水线输出)在把它们存入主存储器以前,也要把它们装入向量寄存器中。 ★ 链接技术是利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术。 ★ 链接技术的实质是标量流水定向传送方法在向量寄存器中的应用。 例:向量加和向量乘的操作: ADDV V1,V2,V3 ;V1←V2+V3 MULTV V4,V1,V5 ;V4←V1×V5 这两条指令间对V1向量寄存器存在先写后读相关,如果使向量寄存器V1在同一时钟周期内,既接收一个功能部件送来的运算结果,又可把这一结果作为下一个向量指令运算所需的源操作数送给另一个功能部件,就可使这两个部件链接起来进行操作。通常把这种链接称为超级向量操作。 当链接进入充分流水操作状态后,在一个时钟周期内就可同时获取两个操作结果。 例:要进行向量运算 D=A×(B+C) 设向量长度≤64,且B和C已由存储器取至V0和V1,则完成运算的向量指令为: LD V3,A ;V3←A ADDV V2,V0,V1 ;V2←V0+V1 MULTV V4,V2,V3 ;V4←V2×V3 第一、二条指令因既无向量寄存器使用冲突,也无功能部件使用冲突,因而可并行执行。 第三条指令与第一、二条指令均存在先写后读相关冲突,因而可将第三条指令与第一、二条指令链接执行。 设:把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要1拍时间。 从存储器中把数据送入访存功能部件需要1 拍时间。 若这三条指令全部用串行方法则所需时间为: [(1+6+1)+N-1)+[(1+6+1)+N-1]+[(1+7+1)+N-1)=3N+22拍 若前两条指令并行执行,第三条指令串行执行,则所需时间为: [(1+6+1)+N-1)+[(1+7+1)+N-1) =2N+15拍 采用并行和链接加速技术后,当被加工向量长度为N时,执行所需时间为: (1+6+1)+(1+7+1)+(N-1) =17+N-1 =N+16拍 实现链接的时间上的要求 ① 只有当前一指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接,若错过该时刻就无法进行链接,只有等前一向量指令全部执行完毕,释放向量寄存器资源后才能执行后面指令。 在上面的例子中,当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时,要求先行的两条指令产生运算结果的时间必须相等,即要求有关功能部件的延迟时间相等(如上例中的访存和浮点加功能部件延时均为6个时间单位)。 ②进行链接的向量指令的向量长度必须相等,否则就不可能链接。 例:在CRAY-1机中,浮点功能部件中各功能段的执行时间为: 浮点加法:6拍;浮点乘法:7拍;求倒数:14拍;存储器存/取:6拍;启动功能部件: 1拍;打入结果: 1拍。 分析任务数为50时,下列指令段的完成时间: ① V0←存储器 ② V3←V1+V2 ③ V4←V0×V3 ④ V0←V4+V5 分析: ①与②无功能和寄存器冲突,可并行。 ②与③先写后读数据相关,可以链接。 ④与②有功能冲突,必须在①与②执行完后,才能启动④,即④只能串行工作 。 ① V0←存储器 ② V3←V1+V2 ③ V4←V0×V3 ④ V0←V4+V5 执行时间: (1+6+1)+(1+7+1)+(50-1)+(1+6+1)+(50-1) =123拍 例:分析在CRAY-1机中,任务数为50时,下列指令段的完成时间。 ① V0←存储器 ② V1←V2+V3 ③ V6←V4×V5 分析:三条指令均无功能冲突,可采用全并行的方式,指令段的完成时间为: (1+7+1)+(50-1)=58拍 例:分析在CRAY-1机中,任务数为50时,下列指令段的完成时间,设浮点求倒数的执行时间为14拍。 ① V2← V0×V1 ② V3←存储器 ③ V4←V2+V3 ④ V5←1/V4 分析: ①与②无功能和寄存器冲突,可并行。 ①与②节拍不一致, ③不能与①、②链接,只能串行执行。 ③与④先写后读数据相关,可以链接。 执行时间: (1+7+1)+(50-1)+ (1+6+1)+(1+14+1)+(50-1)=131拍 3.6.6.3 分段开采技术 1. 向量操作长度控制 ⑴ 实际程序中的向量长度往往并不与向量机的自然向量长度相同。 自然向量长度:向量寄存器型的向量机中,每个向量寄存器可存放的向量元素个数。 ⑵ 程序中一个具体的向量操作长度在编译时经常是未知的,因为在一个代码段中可能需要不同的向量长度。 如果向量的长度大于向量寄存器的长度,则需要采用分段开采技术。 分段开采技术(向量循环) 当向量的长度大于向量寄存器的长度时,必须把长向量分成长度固定的段,然后循环分段处理,每一次循环只处理一个向量段。 分段开采由系统硬件和软件控制完成,对程序员是透明的。 分段开采的实现 将向量长度按向量寄存器的长度(MVL)分段,分段后的向量长度即是每次向量操作的长度,它必须等于或小于向量寄存器长度。 向量长度小于向量寄存器长度时,均可放入向量寄存器。 向量长度大于向量寄存器长度时,需采用分段开采技术(向量循环)。 例: 设A和B是长度为N的向量,需要在Cray-1向量处理器上实现以下的循环操作: DO 10 I = 1,N 10 A(I)= 5.0 * B(I) + 1.0 当N ≤64时 S1 ← 5.0 ;将常数5.0送入标量寄存器S1 S2 ← 1.0 ;将常数1.0送入标量寄存器S2 VL ← N ;在向量长度寄存器VL中设置向量长度N V0 ← B ;从存储器中将向量B读入向量寄存器V0 V1 ← S1 × V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果从向量寄存器V2存入 存储器的向量A 当N >64时,需要进行分段开采 分段数K (循环次数) : 余数L: S1 ← 5.0 ;将常数5.0送入标量寄存器S1 S2 ← 1.0 ;将常数1.0送入标量寄存器S2 VL ← L ;在向量长度寄存器VL中设置向量长度L V0 ← B ;从存储器中将向量B[0..L-1],读入向量 ;寄存器V0 V1 ← S1×V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果从向量寄存器V2存入存储器 ;的向量A[0..L-1] VL ← 64 For (I=0 to K-1) { V0 ← B ;从存储器中将向量B[L+I*64..L+I*64+63] ;读入向量寄存器V0 V1 ← S1 * V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果V2存入存储器的向量 ; A[L+I*64… L+I*64+63] } 2. 向量访问步长 存储器是一维线性空间,当需要在其中存放二维或多维数组时,必须将其各元素映射到一维线性空间中。 以行为主的存储方式: 当按行进行元素访问时,要访问的元素的地址是相邻连续的。 当按列进行元素访问时,要访问的元素的地址是不连续的,需要采用向量跨步方式进行访问。 例:元素为100×100的A=B×C矩阵乘法的程序段为: for ( i=0; i100 ; i++) for ( j=0; j100;j++) { A[i,j]=0.0; for ( k=0; k100;k++) A[i,j]=A[i,j]+B[i,k]×C[k,j]; } 在执行内循环k时,若以行为主存放矩阵元素,则B矩阵中元素是连续存放的,C矩阵中元素是以跨步方式进行访问的,相邻元素的间距为100。 支持完全的一维数据显式访问的向量机 能支持对向量跨步访问的向量机。 当向量由存储器装入向量寄存器后,原来在存储器中间隔存放的元素在向量寄存器中便成为逻辑上相连续的。 能支持完全的一维数据显式访问的向量机能以行、列,甚至沿对角线访问这些方向上的向量元素。 CRAY—1巨型机属于能支持完全的一维数据显式访问的向量机。 CYBER—205巨型机采用存储器—存储器工作方式,它不支持完全的一维数据显式访问,只能以连续方式访存。 如果要进行跨步访问运算,则必须先将这些在存储器中不连续存放的向量元素,先经过运算部件进行依次排序,然后再送入存储器使它们相邻连续存放,最后再从存储器中连续取出进行运算,显然这将大大降低运算性能。 在向量机中,向量的取、存操作除了需要说明起始地址外,还应说明访问元素的跨步。 元素的跨步需要存放在一个寄存器中,并在向量操作过程中始终保持此参数值。 向量机中通常采用一个专用地址流部件来生成跨步向量元素访问。 支持二维数据显式访问 除了支持一维数据显式访问外,还可直接支持对子矩阵的访问,上、下三角矩阵元素的访问,平行四边行图形元素的访问等。 支持二维数据显式访问需要更多的访问参数,如每组序列长度,组间跨步等参数。 向量机的访存冲突 向量机为了增加访存速率,大都采用低地址位的多体交叉存储器。 当向量机支持跨步长度访问时,就可能出现对同一存储体的访问间隔时间小于访存周期时间 问题,使得上一次对某一存储体的访问还未结束前,又对同一存储体提出了新的访问要求,从而将加剧访存冲突。 例:设有16个存储体,访问时间为12个时钟周期,共要访问64个向量元素。对于步长为1的访问,将需要12+63=76个时钟周期。但当步长为16的倍数时,由于每次对存储器访问将与前一次访问相冲突,因此,每个元素访问都需要12个周期,这样64个元素访问就需要64×12=768个时钟周期。 防止访存冲突的方法 ⑴ 使跨步和存储体数互为质数 例:使存储体数量为17而跨步步长为16。 ⑵ 增加存储体数目 增加存储体数目可以减少访问冲突。 对于64个存储体,步长为32的访问,每隔一次访问就会发生访问冲突。 当访问步长为8时,每隔八次访问才会发生访问冲突。 当向量机中有多条存储器流水线时,就需要有更多存储体以防止发生冲突,因此,当代的向量巨型机中,存储体数都大于64,有的甚至多达512个。 采用多处理机系统 许多新型向量处理机系统采用了多处理机系统结构。例如: CRAY-2 包含了4个向量处理机 浮点运算速度最高可达1800MFLOPS CRAY Y-MP、C90 最多可包含16个向量处理机 3.6.7 向量处理机的性能评价 3.6.7.1 向量指令的处理时间 执行一条向量长度为n的向量指令所需的时间为 Ts :向量流水线的建立时间。 Ts包括向量起始地址的设置、计数器加1,条件转移指令执行等。 Tvf :向量流水线的流过时间。 Tvf是从向量指令开始译码算起,到第一对向量元素流过流水线直到产生第一个结果元素所需的时间。 Tc :流水线瓶颈段的执行时间 Tc 也称为启动率Ir,表示向量流水线填满后,每流出一个结果所需时间。 如果流水线不存在“瓶颈”,每段的执行时间等于一个时钟周期,则上式可以写为: Tvp=[s+e+(n-1)]Tclk s:向量流水线建立时间所需的时钟周期数 e:向量流水线流过时间所需的时钟周期数 n:向量长度 Tclk :时钟周期 如果将向量功能部件启动所需的时钟周期数记为Tstart ,即令 Tstart=(s +e-1),则: Tvp = (Tstart + n) Tclk 向量的启动时间 Tstart 向量的启动时间 Tstart也称向量操作流水线的延迟,和向量流水线的流过时间几乎相等。 当每个流水功能部件的延迟时间均为一个时钟周期时,Tstar所需的时钟周期数约等于流水功能部件的流水段数即流水线的深度。 例:一个向量乘法流水部件的启动时间为l0个时钟周期。启动率为1。对于长度为64的向量乘法,产生每个向量元素结果所需时钟周期数为: 对于运行速度较慢的向量流水操作,启动时间的大小对它的影响不大,但对于启动率为1的高速向量流水操作,启动时间的增加就将使性能受到较大影响。 决定一组向量指令执行时间的主要因素 ① 向量的长度 ② 向量操作之间是否链接 ③ 向量功能部件的冲突和数据的冲突性 向量编队 把几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。 同一个编队中的向量指令之间一定不存在流水向量功能部件的冲突和数据的冲突。 如果存在有冲突和相关的指令,则必须分在不同的编队中。 ?例1:假设每种流水功能部件只有一个,则下面一组向量操作能分成4个编队: LV V1, Rx ;取向量x MULTSV V2,F0,V1 ;向量和标量相乘 LV V3,Ry ;取向量Y ADDV V4,V2,V3 ;加法 SV Ry,V4 ;存结果 划分成的编队是: 1.LV 2.MULTSV,LV 3.ADDV 4.SV 第一条指令LV为第一个编队。MULTSV指令因为与第一条LV指令相关,它们不能在同一个编队中。 MULTSV指令和第二条LV指令之间不存在功能部件冲突和数据相关,所以这两条指令为第二个编队。 ADDV指令与第二条LV指令数据相关,所以ADD为第三个编队。 SV指令与ADDV指令数据相关,所以它为第四个编队。 编队的运行时间 一个编队的运行时间为队中耗时最长的指令的运行时间。 设第i个编队中所有向量指令处理的向量元素个数均为n,一个编队内所有向量指令执行完毕所要的时间为: Tci:第i个编队的执行时间 Tstartij :第i个编队中第j条指令所使用向量功能部件的启动时钟周期数 编队后向量指令序列总的执行时间 m:向量指令序列编队的个数 Tstart:向量指令序列编队总的启动时钟周期数 编队并采用分段开采技术后,向量指令序列执行所需的总的时钟周期数Tn为: Tloop:分段开采所需的额外的时间开销 MVL:向量处理机的向量寄存器长度 例2:在一台向量处理机上实现 A=B×s 操作,其中A和B是长度为200的向量,s是一个标量。向量寄存器长度为64,该向量机的 Tloop为15个时钟周期,各功能部件的启动时钟周期数为: Load:7 Mul:7 Store:6 求总的执行时间。 解:因为向量长度超过了向量寄存器的长度,所以要采取分段处理的方法。每次循环主要由下面3条向量指令组成: LV V1,Rb MULTSV V2,V1,F0 (s已预存入F0) SV Ra ,V2 3条指令相关,编队数 m=3;向量长度 n=200 分段数 ∵ 3个编队串行工作 ∴ Tstart=7(load)+7(mul)+6(stor

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

http://deafbook.net/xianxingzhilingzhan/265.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有