流水线技术概要

第二章流水线技术流水线是计算机体系结构设计中普遍应用的技术。本章介绍流水线的基本概念、表示方法、和分类，讨论流水线实现的基本结构、线性流水线的性能与非线性流水线的调度策略，分析流水线的相关及其处理方法。第一节流水线的基本概念第二节处理机实现流水线的基本结构第三节线性流水线的性能及其分析第四节流水线的相关及其处理第五节非线性流水线的调度一、多条指令的执行方式二、什么是流水线三、流水线的表示方法四、流水线的分类五、流水线的特点第一节流水线的基本概念一、多条指令的执行方式一条指令的执行过程可以分为多个阶段，通常分为取指令、分析指令、执行指令三个阶段。现假设三个阶段所需要的时间均为t。（1）顺序方式。顺序执行方式是指在任何时刻，处理机中只有一条指令在执行。执行n条指令所需要的时间为T=3nt。控制简单，节省设备。执行指令速度慢，功能部件的利用率低。（2）一次重叠方式。一次重叠执行方式是指在任何时刻，处理机中至多只有二条指令在同时执行。执行n条指令所需要的时间为T=(2n+1)t。时间缩短了近一半，功能部件利用率高。需要增加一些硬件，控制过程也复杂一些。（3）二次重叠方式。二次重叠执行方式是指在任何时刻，处理机中至多可以有三条指令在同时执行。执行n条指令所需要的时间为T=(n+2)t。时间缩短了近2/3，提高指令的执行速度。付出更高的代价。取指k分析k执行k取指k+1分析k+1执行k+1取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2顺序执行方式一次重叠执行方式二次重叠执行方式二、什么是流水线计算机中的流水线与工厂中的生产流水线十分相似，它是指把一个重复的过程分解为若干个子过程，一个过程的子过程可以与其它过程的不同的子过程并行进行，实现不同过程在时间上重叠进行的工作方式。实现流水线的技术方法称为流水线技术。从本质上讲，流水线技术是一种时间并行技术，是通过时间重叠的技术途径实现并行处理（时间并发性）。根据子过程划分，相应的流水线也要划分出相应的段，每一个段称为流水节拍、流水步、流水步骤、流水阶段、流水段、功能段等。一个流水阶段与另外一个流水阶段相连接形成流水线。过程从流水线的一端进入，经过流水线的处理，从流水线的另一端进出。流水线技术是一种非常经济而又有效的技术，已成为计算机中普遍使用的一种并行处理技术。采用流水线技术只需要增加少量的硬件，就能够把处理机的运算速度提高几倍。三、流水线的表示方法流水线的表示方法有三种：连接图、时空图和预约表，其中时空图用于表示线性流水线，预约表用于表示非线性流水线，而连接图则均可表示。1.连接图四个流水段的指令流水线的连接图如图所示，其实质是将带执行时间的各流水段按照流水线的执行顺序从左到右排列，并用带箭头的直线把它们连接起来。2.时空图时空图是一种最常用、能直观描述线性流水线工作过程的表示方法，四个流水段的指令流水的时空图如图所示。其实质是利用平面直角坐标系的第一象限。横坐标表示时间，即是输入到流水线的各个任务在流水线中所经过的时间。纵坐标表示空间，即流水线的每一个流水段。取指令译码执行保存结果取指令译码执行保存结果线性指令流水线的连接图非线性指令流水线的连接图12345123451234512345四功能段指令流水线时空图3.预约表预约表是一种最常用、能直观描述某过程非线性流水线工作状态的表示方法，四个流水段的指令流水线的预约表如图3.4所示。其实质是利用一张表，行表示时间即非线性流水线的段数，列表示空间既任务通过非线性流水线的时间，表中用“×”表示行对应流水段在列对应时间段要被使用。一行中可以有多个“×”，表明同一个任务在不同时间重复使用了同一个流水段；一列中有多个“×”则表明任务在同一时间使用了多个流水段。×××××四功能段非线性指令流水线预约表四、流水线的分类从不同的角度，可以把流水线分成多种不同类型，以反映流水线在某一方面的结构、特点或性能。1.按流水线的功能多寡分类（1）单功能流水线（UnifunctionPipelining）单功能流水线是指只能完成一种固定功能的流水线。输入示阶差对阶规格化尾数加输出六功能段线性单功能流水线的连接图（2）多功能流水线（MultifunctionPipelining）多功能流水线是指流水线的各段可以实现不同的连接，在不同的时间内，或在同一时间内，通过不同的连接方式实现不同的处理功能。输入尾数乘累加输出输入求阶差对阶尾数加规格化输出输入对阶尾数加规格化尾数乘输出累加求阶差定点乘法浮点加法浮点点积TI-ASC计算机的多功能流水线2.按多功能流水线在同一时间内各段连接方式分类在多功能流水线中，按照在同一时间内是否可以实现多种连接，来同时执行多种功能的要求，把多功能流水线分为静态流水线和动态流水线。（1）静态流水线（StaticPipelining）静态流水线是指在同一段时间内，多功能流水线只能按一种方式连接，实现一种功能。只有当按照这种连接流入的所有处理的对象都流出流水线之后，多功能流水线才能重新进行连接以实现其他功能。如图3.6所示中的8段多功能流水线如果按照图3.7所示的时空图工作，那么就是一种静态流水线。空间浮点加定点乘输出12…n-1n1…累加12…尾数乘123…规格化12…n-1n尾数加12…n-1n对阶12…n-1n求阶差12…n-1n输入12…n-1n1234…时间静态流水线的时空图（2）动态流水线（DynamicPipelining）动态流水线是指在同一段时间内，多功能流水线中的各段可以实现多种连接，同时执行多种功能。当然，任何一个功能段只能参加到一种连接中。空间浮点加定点乘输出12…n-1n123…累加1234…尾数乘12345…规格化12…n-1n尾数加12…n-1n对阶12…n-1n求阶差12…n-1n输入12…n-1n123456…时间动态流水线的时空图3.按流水线的级别分类按照流水线的级别，可以把流水线分为功能部件级、处理机级和处理机间级。（1）指令流水线（InstructionPipelining）指令流水线又称为处理机级流水线，它是把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。（2）运算操作流水线（ArthmeticPipelining）运算操作流水线又称为功能部件级流水线，它是把处理机的算术逻辑部件分段，使运算过程能进行流水操作。（3）宏流水线（MacroPipelining）宏流水线又称为处理机间流水线，它是由两个或两个以上的处理机通过存储器串行连接起来，每个处理机对同一数据流的不同部分分别进行处理，前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务中的一部分。处理机1存储器处理机2处理机n存储器存储器…一种宏流水线4.按流水线的各功能段之间是否有反馈回路分类按照流水线的各功能段之间是否有反馈回路，可以把流水线分为线性流水线和非线性流水线。（1）线性流水线（linearPipelining）线性流水线是指流水线各段串行连接，数据顺序流经流水线各段水线各段一次且仅流过一次。（2）非线性流水线（nonlinearpipelining）非线性流水线是指在流水线各段之间除有串行连接之外，还有反馈回路，数据流经有反馈回路的功能段的次数可以有多次。五、流水线的特点（1）流水线是由多个独立的从一个大的处理功能部件分解而来的小功能部件组成，依靠小功能部件并行工作来提高处理速度。把一个重复的处理过程分解为若干个子过程，每个子过程需要设置一个对应的功能部件来实现，这是流水线本质。（2）流水线中各功能段的时间应尽量相等，否则将引起“堵塞”、“断流”等。在流水线设计中，当遇到“瓶颈”时，必须采取办法解决。（3）流水线需要有“装入时间”和“排空时间”。“装入时间”是指第一个任务进入流水线到输出流水线的时间。“排空时间”是指第n个（最后一个）任务进入流水线到输出流水线的时间。（4）只有连续不断地提供同种任务才能充分发挥流水线的效率。因此，在采用流水线方式工作的处理机中，特别是当流水线的级数较多时，要在软件和硬件设计等多方面尽量为流水线提供连续的任务，以提高流水线的效率。（5）在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等。它的作用是保存本流水段的执行结果，如图所示。取指令译码执行存结果锁存器锁存器锁存器锁存器流水线中锁存器练习：如果一条指令执行过程分为取指令、分析指令、执行指令三个子过程，假设某程序共有1000条指令，当①三个子过程的延迟时间均为t；②三个子过程的延迟时间分别为t1、t2、t3时，计算下列3种情况执行该程序所需时间，并加以比较。（1）指令顺序执行；（2）一次重叠执行；（3）二次重叠执行。一、重叠执行方式的基本结构二、先行控制方式的基本结构三、先行控制的指令流水线四、运算操作流水线和宏流水线的基本结构五、流水线结构设计中的若干问题第二节处理机实现流水线的基本结构一、重叠执行方式的基本结构1.重叠执行方式的基本结构采用二次重叠执行方式，同时有三条指令分别在取指令、分析和执行。要使它们能够重叠执行，处理机在结构上必须有独立的取指令部件、指令分析部件和指令执行部件。它们有各自的控制线路，实现各自的功能，这样才能取指令、分析和执行的同时进行。为此，要把顺序执行方式中的一个集中的指令控制器分解成三个相结独立的控制器，分别是：存储控制器，简称存控；指令控制器，简称指控；运算控制器，简称运控。重叠执行方式的基本结构如图所示。重叠执行方式的基本结构取指部件读数写数主存储器分析部件运算部件寄存器组运算控制器存储控制器取指修改PC2.访问冲突及其解决方法采用了重叠执行方式的基本结构后，可实现取指令、分析和执行的并发进行，但存在访问主存的冲突问题（即资源冲突、结构相关）。例如，取指令要访存，分析指令时可能要访存取操作数，执行指令时可能要向主存写运算结果。在一般机器中，指令和数据是混合存放在一个主存中，而且在一个存储周期只能访问一个存储单元。因此，一般的存储器体系结构无法实现指令的重叠执行。解决这个问题的方法一般有以下三种。（1）设置两个独立编址的主存储器。（2）主存储器采用多体交叉编址的并行存储器。（3）采用先行控制技术是解决访存冲突的根本办法。二、先行控制方式的基本结构1.先行控制方式的基本原理在二次重叠执行方式执行指令中，假设取指令、分析指令和执行指令的时间相等，则流水线连续流畅，否则功能段会相互等待。但实际上往往是不相等的，若取指令、分析指令和执行指令分别为△t1、△t2、△t3，且△t2＞△t3＞△t1，多条指令的执行过程如图2-13所示。从图2-13可以看出，取指段在取完第k+1条指令后，由于分析段还没有分析完第k条指令，第k+1条指令不能进入分析段而产生了堵塞，导致取指段空闲；执行段执行完第k条指令后，由于分析段还没有分析完第k+1条指令，执行段得不到第k+1条指令而产生了断流，又导致执行段空闲。另外，当指令之间存在数据相关等相关时，重叠也会被打断。例如，如果第k条指令是转移指令，则顺序取来的第k+1条指令可能无效，从而产生了停顿。取指k分析k执行k分析k+1取指k+1执行k+1取指k+2分析k+2执行k+2各功能段延迟时间不相等的二次重叠执行方式先行控制方式的基本思想是：当流水线中某功能段的延迟时间较长时，该功能段前面的功能段对后继任务进行预处理，预处理好的后继任务置于缓冲器中。而该功能段后面的功能段则对以前置于缓冲器的任务进行后行处理。这样，所有的功能段都处于忙碌状态。某任务的流程中，各功能段之间有等待的时间间隔，但各自的流程是连续的。当然，如果前面功能段的缓冲器已满，或者后面功能段没有后行处理任务，流水线仍是不流畅的。采用先行控制方式工作，不仅可解决延迟时间不相等和不能在较长时间内提供同种任务而造流水线不流畅，解决了访问冲突。当有多个功能段要访问存储器时，根据具体情况，让某功能段访存，其前面的功能段则对后继任务进行预处理，而后面的功能