第3 章
信息加工的流水线技术
流水线技术的应用极其广泛,随处可见,如工业领域、管理工作等,在计算机体系结构
中也得到普遍应用。本章以用于信息加工的处理机流水线为基础,介绍流水线及其表示
方法与特点分类,阐明流水线处理机实现的基本结构,分析线性流水线的性能与非线性流
水线的调度策略,讨论流水线的相关及其处理方法。
3.1 流水线及其特点与分类
【问题小贴士】 在工作和生活中,常常听到流水线这个词,也不知不觉中应用流水线
技术。如新生入学报到就采用了流水线技术,学校构建新生入学报到流水线分为两步:
①将新生入学报到工作分解并按某种时序将它们线性排列:打印报到流程表→办理缴费
或助学贷款→到院系报名(含领校园卡、登记信息、递交材料等)→购买或领取日常用品;
②新生入学报到的各项子工作由不同部门指派人去负责完成。这时学生报到需要经过多
人多处,每处的子工作是专业化的,相对于报到整体工作要简单得多。与采用集中一处报
到相比,其最大优势为学生报到的速度快,即单位时间内可以有更多学生完成报到。①根
据其他课程讲述的“指令处理过程”和时间重叠概念,当处理机处理指令序列(运行程序)
时,是否也可以采用流水线技术呢? 如果可以,如何构建? 这样能够带来什么好处,它们
是怎样形成的? 怎样定义流水线呢? ②根据浮点加减法运算步骤,浮点加减法运算是否
可以采用流水线来执行呢? 由此,有哪些不同特性的流水线呢? ③对于新生入学报到流
水线,大部分学生直接刷卡缴费,少数学生需要助学贷款,这时会带来什么问题? 由此,怎
样使流水线速度快、效率高,并且如何充分发挥流水线效率呢? ④为了便于流水线技术的
应用,自然需要采用一定的方法来描述它。那么,流水线有哪些表示方法? 各种方法有什
么优势和适用性?
3.1.1 指令序列处理及其流水线概念
1.单条指令的处理过程
单条指令的处理过程可以分为若干个阶段,最简单、直观地可以分为取指令、分析指
令和执行指令三个阶段,其处理过程如图3-1所示。取指令阶段的任务为:按照程序计
数器的地址内容访问主存储器,读出一条指令(二进制代码)并送到指令寄存器。分析指
令阶段的任务为:对指令寄存器中的操作码字段进行译码,分析指令的功能操作;分析地
址码字段中的寻址方式,并进行形式地址变换,生成操作数存储单元地址(立即寻址除
105
第
3
章 信息加工的流水线技术
外), 并获取操作数;同时程序计数器自动产生一个增量,形成下一条指令的主存单元地
址。执行指令阶段的任务为:根据功能操作要求,对操作数进行运算操作,并把结果送到
指定的地址中。
图3-
1
单条指令的处理过程
2.
指令序列的处理方式
当在同一个处理器中处理一段程序的指令序列时,若假设三个阶段所花费的时间均
为Δt,则可以采用顺序、一次重叠和二次重叠三种处理方式。
1)顺序处理
顺序处理是指在任何时刻处理器至多仅能处理一条指令,指令之间是完全串行处理
的,即第
k
条指令处理结束后,再处理第k+1 条指令,以此类推。顺序处理过程如图3
所示,若程序包含
N
条指令,程序运行所需要的时间为:T=3NΔt。
-2
图3-
2
指令序列的顺序处理过程
顺序处理的优点在于控制简单、实现成本较低。而主要缺点有两个:一是指令处理
的速度慢,指令之间是完全串行处理;二是功能部件的利用率低,如取指令时主存是忙碌
的,处理器则是空闲的。
2)一次重叠处理
一次重叠处理是指在任何时刻处理器至多仅能处理两条指令,指令之间可能有两条
指令在处理,即第
k
条指令的执行与第k+1 条指令的取指令同时发生。一次重叠处理过
程如图3-3所示,若程序包含
N
条指令,程序运行所需要的时间为:T=(2N
+1)Δt。
图3-
3
指令序列的一次重叠处理过程
一次重叠处理与顺序处理相比,主要优点有两个:一是处理
N
条指令所需要的时间
缩短近1/2;二是功能部件的利用率明显提高,如主存基本处于忙碌状态。但一次重叠处
理的实现需要增加一些硬件,而付出了一定的代价,过程控制也变得复杂些。如为了在第
k
条指令执行的同时可以取第k+1 条指令,必须增加一个指令寄存器,原来的指令寄存
器用于存放第
k
条指令,新增的指令寄存器用于存放第k+1 条指令。
3)二次重叠处理
二次重叠处理是指在任何时刻处理器至多仅能处理三条指令,指令之间可能有三条
106
计算机体系结构
指令在处理,即第k-1条指令的执行与第
k
条指令的分析以及第k+1 条指令的取指令同
时发生。二次重叠处理过程如图3-4所示,若程序包含
N
条指令,程序运行所需要的时
间为:T=(
N
+2)Δt。
图3-
4
指令序列的二次重叠处理过程
二次重叠处理进一步提高了指令序列的执行速度,相对于顺序处理,处理
N
条指令
所需要的时间缩短近2/3,但过程控制更加复杂,也需要付出更高代价。
可见,采用重叠方式处理指令序列,使程序运行如同工业生产流水线一样,源源不断
地处理指令,有效地提高了指令序列的处理速度。当然,也带来许多问题,如指令处理过
程各阶段不相等、指令之间的相关性等,这就需要先行控制、相关处理等新技术的支持。
3.
流水线及其优势实现基础
流水线在工业生产中随处可见。如汽车装配流水线,把汽车装配分为多道工序(子过
程), 每道工序的任务由一人或多人完成,各道工序所花费时间也大致相等。当汽车装配
流水线启动之后,每隔一定的时间(一道工序的时间)就有一辆汽车下线。如果跟踪一辆
汽车装配的全过程,就会发现每辆汽车装配都经过了每道工序,装配总时间并没有减少,
但由于多辆汽车在时间上重叠装配,使得单位时间内有更多的汽车下线,装配速度得到极
大提高。计算机中的流水线与工业生产中的流水线十分相似。
一般说来,流水线技术是指把一个重复的任务处理过程分解为若干个子过程,当每个
子过程均设置一个功能部件来实现时,一个过程的子过程可以与其他过程的不同子过程
同时进行,实现多个不同过程在时间上重叠工作。将任务处理过程所包含的所有子过程
或实现子过程的所有功能部件按一定次序连接在一起,则称为流水线(Pipelining)。任务
从流水线的一端进入,经过流水线上的功能部件,从流水线的另一端排出。
从本质上讲,流水线技术是一种时间并行技术,是通过时间重叠的技术途径实现并行
处理(时间并发性), 换句话说,流水线是通过多个小功能部件并行工作来提高处理速度。
把一个重复的任务处理过程分解为若干个子过程,由此为每个子过程设置一个对应独立
的功能部件来实现,这些小功能部件是由大功能部件分解而来的,使它们并行工作就可以
提高任务的处理速度。
流水线中的子过程或功能部件称为流水段或功能段,也可以称为流水节拍、流水步骤
等,流水线中的功能段数量称为流水线的深度。流水线技术是一种非常经济而有效的技
术,已成为计算机中普遍应用的一种并行处理技术。采用流水线技术只需要增加少量的
硬件,就可以把处理器的运算速度提高许多倍。
3.1.2
流水线的表示
流水线通常有三种表示方法:连接图、时空图和预约表。其中时空图用于表示线性
第
3
章 信息加工的流水线技术
107
流水线;预约表用于表示非线性流水线;而连接图既可以表示线性流水线,也可以表示非
线性流水线。现假设一条指令的处理过程分为取指令、译码、执行、保存结果4个子过程,
相应处理指令的流水线则包含取指令、译码、执行、保存结果4个功能段,且对于某些指
令,执行功能段还需要重复使用。
1.
连接图表示法
所谓连接图实质是将带执行时间标记的各功能段按照任务在功能段上的执行顺序从
左到右排列,并用带箭头的直线把它们连接起来。上述包含4个功能段的线性指令流水
线的连接图如图3-5所示,而执行功能段还需要重复使用的非线性指令流水线的连接图
如图3-6所示。显然,通过连接图可以看出流水线所包含功能段的结构关系和任务在流
水线上的处理顺序;反过来,分析任务处理过程并划分出过程阶段是画出流水线连接图的
基础。
图3-
5
线性指令流水线的连接图
图3-
6
非线性指令流水线的连接图
2.
时空图表示法
所谓时空图实质是利用平面直角坐标的第一象限,以横坐标为时间、纵坐标为空间
(功能段), 由此在一定范围的平面区域内标记由流水线处理的任务编号,以表示该区域对
应的时间段通过对应的功能段来处理对应编号的任务。上述包含4个功能段的线性指令
流水线的时空图如图3-7所示,且当流水线中各功能段执行时间相等时,横坐标被分割成
长度相等的时间段。时空图是描述线性流水线最常用、最直观有效的表示方法,横坐标表
示输入流水线的任务在流水线中所经历的时间,纵坐标表示输入流水线的任务在流水线
中所经过的功能段。
图3-
7
线性指令流水线的时空图
通过时空图可以看出任务在任一时刻所处的处理状态,以及同一时间段有哪些功能
段在处理任务。如从图3-7的横坐标来看,5条指令依次分别在t0、t1、t2、t3、t4 时刻进入
108
计算机体系结构
流水线,在t4、t5、t6、t7、t8 时刻排出流水线;在t4 时刻以前,每隔一个时间段就有一条指
令进入流水线,从t4 时刻开始,每隔一个时间段就有一条指令排出流水线。另外,从图3-7
的纵坐标来看,在t4~t5 时间段,取指令、译码、执行、保存结果4个功能段分别在处理第
5、4、3、2条指令的对应子过程。反过来,流水线连接图是建立流水线时空图的基础。
3.
预约表表示法
所谓预约表实质是利用一张表,其中行为空间(功能段)、列为时间,当仅描述一个任
务在流水线上的处理过程时,则在某个单元格内标记“×”,以表示该单元格对应功能段在
对应时间段被该任务占用;当描述序列任务在流水线上的处理过程时,则在某个单元格内
标记“×j ,(”) 以表示该单元格对应的时间段通过对应的功能段来处理对应下标编号的任
务。上述包含4个功能段的非线性指令流水线的单指令预约表如图3-8所示,序列指令
预约表见3.5节。预约表是描述非线性流水线最常用、最直观有效的表示方法,行表示输
入流水线的任务在流水线中所经历的时间,列表示输入流水线的任务在流水线中所经过
的功能段。
图3-
8
非线性指令流水线的单指令预约表
通过单任务预约表可以看出,任务处理需要多少个时间段,以及在任务处理过程中哪
些功能段被重复使用。从图3-8来看,预约表有5列,则指令处理需要5个时间段,且执
行功能段在第3、4时间段被重复使用。特别地,有的单任务预约表可能同一列有两个单
元格带“×”,表明在同一时间段,任务可能进行不同处理,如分支指令,由于条件不同,分
支后的时间段进行的是不同的操作。
3.1.3
流水线的分类
流水线种类很多,从不同的角度可以将流水线分为若干不同类型,以反映流水线在某
方面的结构、特点或性能等。
1.
按流水线功能多寡来分类
按照功能多寡来分,可以将流水线分为单功能流水线和多功能流水线两种。
1)单功能流水线
单功能流水线(UnifunctionPipelining)是指流水线各功能段之间的连接固定不变,
仅能够用于处理功能特性相同的任务。如流水线浮点加法器专门用于浮点加法运算,流
水线浮点乘法器专门用于浮点乘法运算,如图3-9所示的是浮点加法器的流水线连接图,
其所包含的6个功能段之间以固定形式连接在一起,实现唯一的浮点加法运算。
2)多功能流水线
多功能流水线(MultifunctionPipelining)是指流水线各功能段之间的连接可以改变,
第
3
章 信息加工的流水线技术
109
图3-
9
浮点加法器的线性单功能流水线的连接图
在不同时间或同一时间内,通过不同的连接可以处理不同功能特性的任务。典型的多功
能流水线是texas仪器公司的高级科学计算机ASC,其处理器的流水线包含8个功能段,
依次为输入、求阶差、对阶、尾数加、规格化、尾数乘、累加和输出。在一台ASC 处理器内
有4条相同的流水线,每条流水线都可以通过不同连接来分别实现整数加减法运算、整数
乘法运算、浮点加法运算、浮点乘法运算和逻辑运算、移位操作、数据转换等。如图3-10
所示的是ASC 计算机中处理器流水线的部分连接图,功能段之间可以建立不同的连接来
实现不同的运算。另外,ASC 计算机除支持标量运算之外,还支持向量运算,可以构建非
线性流水线,图3-10(c)所示的是对两个浮点向量求点积的流水线连接,它就是一个带有
反馈回路的非线性流水线。
图3-10
TI-ASC
计算机处理器的多功能流水线的连接图
2.
多功能流水线按在同一段时间内的功能段间连接是否可变来分类
对于多功能流水线,按照在同一段时间内是否可以实现多种连接以同时处理多种不
同功能的任务,可将其分为静态流水线和动态流水线两种。
1)静态流水线
静态流水线(StaticPipelining)是指在同一段时间内,多功能流水线功能段之间仅能
够按照一种方式连接,并且处理相同功能特性的任务。对于静态流水线,只有当按照这种
连接流入的所有任务都流出之后,多功能流水线才能改变连接以处理其他功能特性的任
务。如图3-10 所示的8段多功能流水线,如果按照图3-11 所示的时空图处理任务,那么
它就是一种静态流水线。由图3-11 可看出,开始时流水线按照浮点加减运算实现来连
接,当
N
个浮点加减运算全部处理结束即第
N
个浮点加减运算排出之后,多功能流水线
110
计算机体系结构
图3-11
TI-ASC
计算机处理器的静态流水线的时空图
才改变为按照定点乘运算实现来连接。
2)动态流水线
动态流水线(DynamicPipelining)是指在同一段时间内,多功能流水线的功能段之间
可以按照多种方式连接,从而可以处理不同功能特性的任务,当然任何一个功能段仅能参
与到一种连接中。如图3-10 所示的8段多功能流水线,如果按照图3-12 所示的时空图处
理任务,那么它就是一种动态流水线。由图3-12 可以看出,浮点加减运算还未处理结束
排空,流水线就已按照定点乘运算实现进行连接,并开始定点乘法运算。所以,在同一段
时间内和同一条多功能流水线上,两种运算分别使用不同的功能段来同时实现。
图3-12
TI-ASC
计算机处理器的动态流水线的时空图
特别地,对于静态流水线,只有连续向其输入功能特性相同的任务,效率才能得到充
分的发挥。如果连续输入静态流水线的是功能特性不同的任务,如输入的一串操作是浮
点加、定点乘、浮点加、定点乘…… 静态流水线将如同顺序处理方式一样,效率得不到发
挥。而对于动态流水线,由于其允许两种功能特性不同的任务同时进行处理,因此动态流
水线的效率高于静态流水线,但动态流水线的控制极其复杂,目前大多数处理器均采用静
态流水线。
3.
按流水线的级别来分类
按照级别来分,可将流水线分为功能部件级、处理机级和处理机之间级三种。
第
3
章 信息加工的流水线技术
111
1)指令流水线
指令流水线(InstructionPipelining)又称为处理机级流水线,它是把指令处理过程分
解为多个子过程,每个子过程在独立的功能部件中执行,使指令处理实现流水线化。如
图3-5和图3-6所示的4功能段指令流水线即是将指令处理过程分为取指令、译码、执行、
保存结果4个子过程的指令流水线。
2)运算操作流水线
运算操作流水线(ArithmeticPipelining)又称为功能部件级流水线,它是把运算分解
为多个子过程,每个子过程在独立的部件中执行,使运算操作实现流水线化。对于较复杂
的运算往往采用流水线来实现,如浮点加运算与浮点乘运算等。图3-9所示的6功能段
线性单功能流水线即是浮点加的运算操作流水线;图3-10 所示的多功能流水线即是多功
能运算操作流水线。
3)宏流水线
宏流水线(MacroPipelining)又称为处理机之间级流水线,它是由两台或以上的处理
机通过存储器串行连接起来,每台处理机分别对任务中的一部分工作进行处理。如图3-13
所示的是宏流水线,在逻辑上将前一台处理机的输出存入存储器中,作为后一台处理机的
输入,这样同一数据流的不同部分或不同变换将分别在不同的处理机上实现。
图3-13
宏流水线基本结构
4.
按流水线功能段之间是否存在反馈来分类
按照流水线功能段之间是否存在反馈来分,可以把流水线分为线性流水线和非线性
流水线两种。
1)线性流水线
线性流水线(LinearPipelining)是指流水线各功能段之间串行连接,数据按顺序流经
流水线各功能段一次,且仅流经一次。图3-5所示的指令流水线和图3-9所示的运算操
作流水线均为线性流水线。
2)非线性流水线
非线性流水线(NonlinearPipelining)是指在流水线各功能段之间除串行连接外,还
存在反馈回路,任务可以多次流经存在反馈回路的功能段。图3-6所示的指令流水线是
非线性流水线,其中功能段S3 存在反馈回路,表示S3 可以被多次使用;图3-10 的浮点点
积运算流水线也是非线性流水线。
另外,流水线还可以按照控制方式分为顺序流水线和乱序流水线、同步流水线和异步
流水线,按照数据表示方式分为标量流水线和向量流水线。
3.1.4
流水线的特点
在处理机中,采用流水线方式处理指令与采用串行方式相比具有许多特点。在处理
机与程序的设计过程中,应充分注意这些特点,以设计出高效率的处理机流水线并充分发
112
计算机体系结构
挥其效率。
(1)流水线各功能段延迟时间应尽量相等才能充分发挥效率。流水线中任务的流动
节拍不能快于延迟时间最长、执行速度最慢的功能段,该功能段是流水线的“瓶颈”,将引
起流水线“堵塞”与“断流”,使得其他功能段将不能充分发挥其效率。
(2)流水线必然存在不能充分发挥效率的“装入时间”与“排空时间”。“装入时间”是
指第一个任务进入流水线到排出流水线的时间,“排空时间”是指最后进入流水线的任务
到其排出流水线的时间。在这两个时间段内,有功能段空闲,流水线没有充满;只有流水
线完全充满后,流水线的效率才能得到充分发挥。
(3)必须连续不断地为静态流水线提供同种任务才能充分发挥效率。如为使流水线
化的浮点加法器充分发挥效率,就需要连续提供浮点加法运算。但由于程序本身的原因
和程序设计过程中人为的原因,如数据相关等,不可能连续为浮点加法器提供同种运算。
因此,对于流水线处理机,特别是当流水线级数较多时,应该在软件和硬件等多方面尽量
为流水线提供连续的任务。
(4)在流水线每个功能段的后面应设置一个缓冲寄存器(又称锁存器、闸门寄存器
等), 以平滑各功能段的延迟时间。在流水线中,每个功能段的延迟时间不可能绝对相等,
另外还存在电路的延迟时间与时钟偏移等,因此在功能段之间传送任务时,必须通过锁存
器来保存功能段自身的执行结果,如图3-14 所示。
图3-14
在流水线功能段后面设置的锁存器
显然,在指令流水线中加入锁存器之后,每条指令的实际处理时间增加了。尽管如
此,采用流水线后通过多条指令并行处理可以使整个程序的运行时间缩短,但并没有真正
减少每条指令的处理时间,这就限制了流水线的深度。一旦时钟周期很小,与时钟偏移和
锁存器的附加开销相当时,流水线就失去了作用,在一个时钟周期内没有足够的时间用于
有效工作。
3.流水线处理机的实现结构
2
【问题小贴士】①流水线是通过多个小功能部件并行工作来提高处理速度,这些小
功能部件是由串行处理指令序列的大功能部件分解而来的。那么,当把指令处理过程分
解为取指令、分析、执行三个阶段时,处理机应该具备怎样的结构才能实现多条指令的并
行处理? 为什么?②当多条指令并行处理时,为什么处理机对主存储器的访问会产生冲
突? 这时会影响处理机的工作效率吗? 为什么?③针对流水线功能段的延迟时间不相等
的问题,提出了先行控制技术,那么该技术可以解决哪些问题? 是如何解决的? 为了实现
先行控制技术,处理机应该具备怎样的结构? 这时,指令处理过程可以分为哪些阶段?
第
3
章 信息加工的流水线技术
113
3.2.1
重叠处理的实现结构及其访问冲突
1.
重叠处理的实现结构
当采用二次重叠方式处理指令序列时,可以同时处理3条指令,且3条指令分别处于
取指令、分析指令和执行指令三个不同的阶段。显然,为实现二次重叠处理,处理机必须
具有独立的取指令部件、分析指令部件和执行指令部件,才能够使三条指令的不同阶段同
时进行。自然,每个部件必须具有各自的控制逻辑,以控制实现各自的功能。由于指令分
析不需要微操作,也就不需要相应的控制逻辑;由于取指令即是存储访问操作,与读写操
作数的操作相同,因此取指令所需要的控制逻辑与读写操作数共享,且称之为存储控制
器。把执行指令部件的控制逻辑称为运算控制器,则二次重叠处理指令序列的基本结构
如图3-15 所示。
图3-15
二次重叠处理指令序列的实现结构
在Inter8086 微处理器中就有重叠处理指令序列的雏形,8086 微处理器的组成可分
为总线接口部件和执行部件两部分。总线接口部件的任务有:从主存单元预取指令,送
到指令队列缓冲器暂存,实现取指令;从指定主存单元或I/O端口取数据送至执行部件,
或把执行部件的运算操作结果送至指定的主存单元或I/O端口,实现数据存取。执行部
件负责从指令队列缓冲器取指令,并进行译码分析和指令执行。这两个功能部件再加上
一个队列缓冲器,就可以实现取指令与分析、执行指令之间的一次重叠。
2.
主存访问冲突及其解决方法
当采用二次重叠处理指令序列的实现结构后,处理器可以并发进行取指令、分析指令
和执行指令。取指令需要访问主存,分析指令可能需要访问主存来读取操作数,执行指令
可能需要访问主存来写结果,这样就使得主存访问可能发生冲突。在一般的计算机中,指
令与数据是混存于一个主存中的,而主存的一个存取周期仅能访问一个存储字。所以当
计算机仅有一个主存储器时,往往无法实现指令之间的重叠处理。目前,重叠处理指令序
列时发生主存访问冲突的解决方法有三种。
(1)设置两个独立编址的主存储器。设置指令存储器和数据存储器,指令存储器用
于存放程序的指令序列,数据存储器用于存放数据。这两个存储器可以同时独立访问,从
而解决了取指令与读写操作数之间的访问冲突。如果规定指令执行阶段的运算结果仅写
到通用寄存器而不直接写到主存,那么取指令、分析指令和执行指令就可以并发进行。目
前,高性能微处理器的芯片内部均配置两个高速缓冲存储器(Cache), 一个是指令Cache,
一个是数据Cache。
114
计算机体系结构
(2)主存储器采用多体交叉编址的并行存储器。多体交叉编址的并行存储器在一个
存取周期内可以访问多个存储字,如果同时进行的取指令与读写操作数所存放的存储单
元不在同一个存储体中,就可以实现指令序列的重叠处理,否则无法重叠处理指令序列。
(3)采用先行控制技术。流水线各功能段的延迟时间不可能绝对相等,也不可能在
较长时间内为流水线连续不断地提供同种任务。因此,当处理器采用二次重叠处理指令
序列的结构时,取指令、分析指令和执行指令等部件不可能完全处于忙碌状态,流水线效
率不可能得到充分发挥。前面两种解决访问冲突的方法不仅对此无能为力,而且还没有
完全解决访问冲突;设置两个主存时,操作数读与写之间的访问冲突仍然存在;采用并行
存储器时,三种主存访问的存储单元必须在不同的存储体上。先行控制技术既可以有效
地解决访问冲突,又可以充分发挥流水线效率。
3.2.2
先行控制及其实现结构
1.
先行控制技术的基本原理
先行控制技术最早出现在IBM 公司研制的STRETCH 计算机上,目前在处理器中
已得到广泛应用。先行控制技术是为了连续流畅地实现指令序列重叠处理而提出的,没
有先行控制技术的支持,将无法连续流畅地重叠处理指令序列,也就无法实现真正意义上
的流水线。
在二次重叠处理指令序列中,假设取指令、分析指令和执行指令的延迟时间相等,则
流水线连续流畅,否则功能段之间存在相互等待现象。但实际上功能段的延迟时间往往
是不相等的,若取指令、分析指令和执行指令的时间分别为Δt1、Δt2、Δt3,且Δt2>Δt3>
Δt1,采用二次重叠处理指令序列的过程如图3-16 所示。从图3-16 可以看出,取指功能
段在取出第k+1 条指令后,由于分析功能段对第
k
条指令的分析还未结束,第k+1 条
指令则不能进入分析功能段而产生堵塞,导致取指功能段空闲;执行功能段在执行第
k
条指令后,由于分析功能段对第k+1 条指令的分析还未结束,执行功能段得不到第k+1
条指令而产生断流,又导致执行功能段空闲。另外,当指令之间存在相关时,重叠也会被
打断。如若第
k
条指令是转移指令,则按顺序取来的第k+1 条指令可能无效,从而产生
停顿。
图3-16
各功能段延迟时间不相等时二次重叠处理的时空图
为使流水线连续流畅而不产生停顿,当流水线某功能段的延迟时间较长时,则在该功
能段前面设置预处理栈或在其后面设置后行处理栈,或者同时设置预处理栈和后行处理
栈。这样功能段之间相互隔离,所有功能段各自处于忙碌状态,当任务在流水线上流动
时,即使功能段之间存在等待时间,但各自的任务流动是连续的。这就是先行控制技术的
基本原理。预处理栈一方面对后继任务进行预处理,另一方面用于缓存预处理好的后继
第
3
章 信息加工的流水线技术
115
任务;而后行处理栈一方面对任务进行后行处理,另一方面用于缓存后行处理好的任务。
当然,如果功能段后行处理栈的缓冲器已满,那么该功能段则产生堵塞;如果功能段预处
理栈的缓冲器为空,那么该功能段则产生断流;这时流水线仍不是连续流畅的,但可以使
功能段空闲降到最低。
先行控制技术不仅使得任务在流水线上连续流畅地流动,而且还有效地解决了主存
访问冲突。当多个功能段同时访问主存时,根据具体情况,让其中一个功能段访问主存,
该功能段前面的功能段则对后继任务进行预处理,其后面的功能段则对任务进行后行
处理。
2.
先行控制定义
先行控制是通过对任务进行预处理和缓冲,以平滑功能部件(功能段)之间工作速度
上的差异,使功能部件各自独立地工作,始终处于忙碌状态,提高任务序列的处理速度。
显然,先行控制技术实质是缓冲技术和预处理技术相结合的结果,这两种技术是先行控制
的关键。
缓冲技术是在工作速度不固定的两个功能段之间设置缓冲栈,用以平滑它们的工作
速度的差异。预处理技术是把需要进入某功能段的任务进行外围处理,以减少任务在该
功能段中的延迟时间。如把需要进入运算器的指令均处理为寄存器-寄存器型(RR 型)指
令,结合缓冲技术,则可以为进入运算器的指令准备好所需要的全部操作数。
3.
先行控制的实现结构
将指令处理分为取指令、分析指令和执行指令三个阶段,执行指令所包含的微操作复
杂多变,延迟时间也最长,而取指令与分析指令所包含的微操作相对固定简单。为此,在
二次重叠处理指令序列的基本结构基础后,增设4个先进先出的先行缓冲栈。在分析指
令部件与运算控制器之间增设后行操作栈,在主存储器与执行指令部件之间增设先行读
数栈,在执行指令部件后面增设先行写数栈,并使取指令部件增加缓冲功能,先行控制实
现的基本结构如图3-17 所示。特别地,通常把先行指令缓冲栈、先行读数栈、先行操作栈
和后行写数栈统称为先行控制器,把先行控制器与指令分析器合称为指令控制部件,而把
运算部件及运算控制器合称为指令执行部件。
图3-17
先行控制实现的基本结构
1)先行指令缓冲栈
先行指令缓冲栈是主存与指令分析器之间的一个缓冲部件,用于平滑它们之间工作
116
计算机体系结构
速度上的差异。存储控制器一般将取指令的优先级设为最低,其次是操作数的读写,输入
输出的优先级最高。只要主存有空闲,就通过预取从主存中取多条指令存放于先行指令
缓冲栈中。而当指令分析器空闲时,它就从先行指令缓冲栈中得到所需要的指令。
由于正在处理的指令与从主存中取出的指令是不同的,所以需要设置两个程序计数
器———先行程序计数器PC1 和现行程序计数器PC2,二者计数的顺序是一致的,以维持正
确的指令序列。先行指令缓冲栈的组成结构如图3-18 所示。存储控制器根据先行程序
计数器PC1 的内容,从主存中取指令;指令分析器则根据现行程序计数器PC2 的内容,从
先行指令缓冲栈取指令。
图3-18
先行指令缓冲栈的组成结构
2)先行操作栈
先行操作栈是指令分析器和运算控制器之间的一个缓冲部件,用于平滑它们之间工
作速度上的差异。当运算部件空闲时,运算控制器就从先行操作栈取出一条RR* 型指
令(由“*”来区分真正的RR 型指令), 该指令所需要的操作数则来自于先行读数栈或通
用寄存器中。RR* 型指令是先行操作栈预处理的结果,其预处理是将变址型(RS 型)、存
储器型(SS 型)等指令转换为RR* 型指令。
3)先行读数栈
先行读数栈是主存与运算部件之间的一个缓冲部件,用于平滑它们之间工作速度上
的差异。如果先行操作栈遇到从主存读取源操作数的指令,则由先行操作栈计算出主存
有效地址后送到先行读数栈,先行读数栈从主存读取源操作数,并把它送到RR* 型指令
所指示的寄存器。这样,运算部件执行指令时,均不需要访问主存来获取源操作数,从而
缩短了指令的执行时间。
4)后行写数栈
后行写数栈与先行读数栈一样,是主存与运算部件之间的一个缓冲部件。如果先行
操作栈遇到向主存写入操作数的指令,则由先行操作栈计算出主存有效地址后送到后行
写数栈;当运算部件执行RR* 型指令后,将结果操作数送入后行写数栈,由后行写数栈
把结果操作数写入主存。这样,运算部件执行指令时,均不需要将结果操作数写入主存,
从而缩短了指令的处理时间。
4.
栈缓冲深度的选择
先行控制器所包含的4个缓冲栈中的缓冲寄存器个数即是缓冲深度。缓冲深度小,
缓冲效果不大;缓冲深度大,控制复杂,延迟时间长,还会浪费寄存器。至于选择多大的缓
冲深度,一般是在静态分析的基础上,通过模拟方法来确定栈的缓冲深度。而静态分析方
法是从两个极端情况来考察。
第3 章 信息加工的流水线技术1 17
一是假设先行指令缓冲栈的缓冲深度为Di,且已完全充满。若此时先行指令缓冲栈
输出端输出的指令较简单,指令分析器的速度快,缓冲栈流出指令的速度也快;而在先行
指令缓冲栈的输入端,由于需要访存取指令,指令流入速度慢。设平均每条指令的分析时
间为t1、访取时间为t2,且有t2>t1。在先行指令缓冲栈从完全充满到全部被排空的过程
中,指令分析器分析了L1 条指令,所花费时间为L1t1;同时,从主存中读取了L1-Di 条
指令,所花费时间为(L1-Di)t2。则有:
L1t1 =(L1 -Di)t2
Di =éL1(t2 -t1)/t2 ù (3-1)
由于先行指令缓冲栈为空时,指令分析器被迫处于等待状态。为使先行指令缓冲栈
不被取空,其深度必须大于éL1(t2-t1)/t2 ù。
二是假设先行指令缓冲栈为空,此时先行指令缓冲栈输出端输出的指令较复杂,指令
分析器的速度慢,缓冲栈流出指令的速度也慢。相比之下,访存取指速度快,先行指令缓
冲栈输入端指令流入速度也快。设平均每条指令的分析时间为t1* 、访取时间为t2* ,且有
t1* >t2* 。从先行指令缓冲栈为空到完全充满的过程中,从主存读取到先行指令缓冲栈的
指令为L2 条,所花费时间为L2t2* ;同时,指令分析器分析了(L2-Di)条指令,所花费时
间为(L2-Di)t1* 。则有:
L2t2* =(L2 -Di)t1*
Di =éL2(t1* -t2* )/t1* ù (3-2)
由于先行指令缓冲栈充满时,缓冲栈将失去效果。为使先行指令缓冲栈不被充满,其
深度必须小于éL2(t1* -t2* )/t1* ù。
所以,先行指令缓冲栈的深度主要由主存速度决定。为减小先行指令缓冲栈的深度,
必须使指令访取时间t2 尽量接近指令分析时间t1,即提高主存速度。由于指令分析时间
一般小于指令执行时间,采用类似的方法可以计算出其他缓冲栈的深度。对于采用先行
控制技术的处理机,各缓冲栈的深度有如下关系:
D 先行指令≥D 先行操作≥D 先行读数≥D 后行写数
如IBM/370/165机,D 先行指令=4,D 先行操作=3,D 先行读数=2,D 后行写数=1。
3.2.3 不同级别的流水线结构
1.先行控制的指令流水线结构
在采用先行控制的处理机中,其各个部件构成一条流水线,如图3-19所示。先行控
制处理机处理指令序列时,把指令处理分解为6个子过程,即取指令、指令译码、指令变
换、读操作数、运算和存结果。
图3-19 先行控制的指令流水线结构
如有一个程序按指令顺序共有i+j+k+n+m +p+q+r 条指令,且k=1,p=1。
118
计算机体系结构
在某一时刻,运算部件正在执行第
k
条指令,而第
k
条指令之前的最前面的
i
条指令已全
部处理完,结果已写到主存储器。已通过运算的
j
条指令在后行写数栈中等待把结果写
到主存储器,第
k
条指令之后的
n
条指令已由先行操作栈完成预处理,以RR* 型指令存
放在先行操作栈中,所需要的操作数也已读到先行读数栈。往后的
m
条指令已生成RR*
型指令并存放在先行操作栈中,但所需要的操作数还未读到先行读数栈。再往后的第
p
条指令正在指令分析器中分析,第
p
条指令后的
q
条指令已从主存储器预取到先行指令
缓冲栈中,最后的
r
条指令则还在主存储器中,其中第一条正准备从主存储器流到CPU
中。可见,先行控制的指令流水线上有大量的指令存在,使得任何功能段都基本上处于忙
碌状态。
2.
运算操作的流水线结构
把运算过程中的各种操作为一个子过程,这样每个子过程的延迟时间不可能绝对相
等,但偏移不大。因此,采用集中控制方式,使所有功能段与一个统一时钟同步,时钟周期
的长短由所有运算操作中延迟时间最长的操作决定。由于运算操作的延迟时间不同,功
能段之间可能会有干扰。为了避免干扰,保证功能段之间的时间宽度匹配,在各功能段之
间增设门(Latch)寄存器,这样运算操作的流水线结构如图3-20 所示。
图3-20
运算操作的流水线结构
3.
宏流水线结构
宏流水线是多台处理机对同一数据流的不同作业分别进行处理,其结构则是异构型
多处理机。多处理机处理任务的效率不仅与体系结构有关,而且与算法、语言和软件等有
关。宏流水线结构如图3-13 所示。
3.2.4
流水线结构中存在的问题
1.
瓶颈段问题
当流水线各功能段延迟时间相等时,在流水线上流动的所有任务在每个节拍同步地
往前流动一段。当流水线各功能段延迟时间不相等时,延迟时间最长的功能段就成为瓶
颈段,统一时钟由瓶颈段的延迟时间决定。因此,在设计流水线结构时,应尽可能使各功
能段延迟时间相等。
2.
额外开销问题
当在流水线上处理任务时,会产生额外的开销,这些开销在进行非流水线方式处理时
是不会存在的。流水线上的额外开销包含两部分:门寄存器延迟和时钟到达偏差。由于
流水线功能段之间均需要设置门寄存器,而门寄存器需要有建立时间和传输延迟。时钟
到达各门寄存器的时间不是完全相同的,应该把它们的最大偏差计入统一时钟之中,使得
119
第
3
章 信息加工的流水线技术
统一时钟周期变长。所以当采用指令流水线来处理指令序列时,不仅不可能减少单条指
令的处理时间,由于额外开销的存在,反而会增加这个时间。因此,在设计流水线结构时,
应尽可能减少额外开销。
3.
任务间相关问题
无论是运算操作流水线还是指令流水线或宏流水线,如果后面任务的计算需要用到
前面任务的计算结果,而前面任务的计算还没有结束,则后面任务就会停止向前流动,即
引起流水线的停顿。流水线上流动的前后任务只要存在关联关系,就是相关问题。因此,
在设计流水线结构时,解决好相关问题可以有效地提高流水线的性能。
3.线性流水线性能及其最佳段数选取
3
【问题小贴士】①对于处理机,在指令序列串行处理的基础上,采用流水线技术并行
处理指令序列,可以提高指令的处理速度和功能部件的利用率,那么流水线任务处理速度
和资源利用率分别利用什么指标来衡量? 如何计算它们?②由于流水线功能段之间均需
要设置门寄存器,由此便会产生任务传输延迟,且功能段越多延迟越大,可见并非流水线
上的功能段越多越好,那么如何选取流水线功能段数量?③当流水线各功能段延迟时间
不相等时,将出现“瓶颈”段,且引起流水线“堵塞”与“断流”。采用先行控制技术,可以尽
可能地避免“堵塞”与“断流”,这能否从根本上解决“瓶颈”段所带来的问题?④处理机指
令主要包括运算加工、数据传输和程序转移三种类型,运算指令和传输指令与后继指令的
处理顺序与程序顺序始终一致,转移指令与后继指令的处理顺序与程序顺序可能一致也
可能不一致,是否一致则一般在转移指令处理的后期才能决定,这使得转移指令的后继指
令应该停顿延迟,那么这样对流水线效率的影响有多大? 上述问题的解决涉及许多变换
计算,还需要通过练习来掌握直至熟悉。
3.3.1
线性流水线的性能指标
通常用于衡量流水线性能的主要指标有吞吐率、加速比和效率,它们从不同侧面反映
流水线性能。
1.
吞吐率
吞吐率(ThoughPutRate,TP)是指在单位时间内流水线所处理的任务数量或输出
的结果数量。即有:
TP
=N/TK
(3-3)
其中,
N
为任务数,TK
是处理
N
个任务所用的时间。式(3-3)是计算流水线吞吐率的基
本公式。
1)流水线各功能段延迟时间相等时的吞吐率
若有一条
K
个功能段的线性流水线,各功能段延迟时间均为Δt。当
N
个任务理想
地连续输入流水线时,流水线的时空图如图3-21 所示,其处理
N
个任务所需要的时间可
从两个方面来分析。一是从流水线输出端来看,用
K
个Δt
输出第一个任务,即“装入时
间”为KΔt,之后则每隔一个Δt
输出一个任务,其余
N
-1个任务输出需要(
N
-1)Δt
1 20 计算机体系结构
的时间。二是从流水线输入端来看,每隔一个Δt 向流水线输入一个任务,需要NΔt 的
时间,另外还需要K -1个Δt 来把任务排空,即“排空时间”为(K -1)Δt。因此,流水线
处理N 个任务需要的总时间为:
TK =(N +K -1)Δt (3-4)
将式(3-4)代入式(3-3)中,则得到当流水线各功能段延迟时间相等时连续输入N 个
任务到含K 个功能段的线性流水线的实际吞吐率为:
TP = N
(N +K -1)·Δt (3-5)
图3-21 各功能段延迟时间均相等的流水线时空图
当N 趋于无穷大时的最大吞吐率为:
TPmax =lim N →∞
N
(N +K -1)·Δt= 1
Δt (3-6)
最大吞吐率与实际吞吐率的关系是:
TP = N
N +K -1=TPmax (3-7)
从式(3-7)可以看出,流水线的实际吞吐率小于最大吞吐率,它除与Δt 有关之外,还
与流水线的段数K 和输入流水线中的任务数N 有关。只有当N 远大于K 时,才有
TP ≈TPmax。
2)流水线各功能段延迟时间不相等时的吞吐率
若有一条K 个功能段的线性流水线,各功能段延迟时间分别为Δt1,Δt2,…,ΔtK ,即
流水线中存在“瓶颈”功能段,且“瓶颈”功能段的延迟时间为max{Δt1,Δt2,…,ΔtK }。设
K =4,Δt1=Δt3=Δt4=Δt,Δt2=3Δt,则线性流水线的连接图如图3-22所示,相应时空
图如图3-23所示。从图3-23可以看出,除第一个任务外,其余(N -1)个任务必须按
“瓶颈”段延迟时间间隔连续流入流水线。因此,各功能段延迟时间不相等且连续输入任
务时的线性流水线的实际吞吐率为:
TP =N/( ΣK
i=1Δti + (N -1)max{Δt1,Δt2,…,ΔtK})
(3-8)
图3-22 各功能段延迟时间不相等的流水线连接图
第
3
章 信息加工的流水线技术
121
图3-23
各功能段延迟时间不相等的流水线时空图
式(3-8)中表示总时间的分母中的第一项是流水线处理第一个任务所需要的时间,
第二项是处理其余
N
-1个任务所需要的时间。当
N
趋于无穷大时的最大吞吐率为:
TPmax=
1 (3-9)
max{Δt1,Δt2,…,ΔtK
}
从式(3-8)和式(3-9)中可以看出,当流水线中各功能段延迟时间不相等时,流水线
的最大吞吐率与实际吞吐率主要由“瓶颈”段的延迟时间决定。这时除“瓶颈”段一直忙碌
外,其余功能段都有空闲时间,图3-23中“△”符号表示对应功能段在相应时间内是空闲
的,这实际上是资源的浪费。
2.加速比
加速比(SpedupRatio,S)是指对于同一批任务采用串行处理方式所用的时间与采
用流水线所用的时间之比。则流水线加速比为:
S=T0/TK
(3-10)
其中,T0、TK
分别为对于同样一批任务不采用流水线处理与采用流水线处理所用的时
间,式(3-10)是计算流水线加速比的基本公式。
1)流水线各功能段延迟时间相等时的加速比
若有一条
K
个功能段的线性流水线,各功能段延迟时间均为Δt。采用流水线处理
N
个连续输入的任务所需要的时间可见式(3-4),而不采用流水线处理这
N
个任务所需
的时间为:
N
·KΔt。因此,流水线的实际加速比为:
N
·KΔtN
·KS=
(
N
+
K
-1)Δt=
N
+
K
-1 (3-11)
当
N
趋于无穷大时的最大加速比为:
Smax=lim
N
·
K
(3-12)
N
→∞
N
+
K
-1 =
K
从式(3-12)中可以看出,当
N
远大于
K
时,在线性流水线各功能段延迟时间相等的
情况下,流水线的最大加速比等于流水线的功能段数量。
2)流水线各功能段延迟时间不相等时的加速比
根据流水线各功能段延迟时间不相等时吞吐率的计算分析,一条有
K
个功能段的线
性流水线处理
N
个连续任务的实际加速比为:
K
Σ(K) Δti+
(N-1)max{Δt1,Δt2,…,ΔtK
} (3-13)
S=
N
·ΣΔti
i=1i=1
1 22 计算机体系结构
3.效率
效率(Efficiency,E)是指流水线上的资源利用率,在时空图上则定义为N 个任务占
用的时空区与K 个功能段占用的总时空区之比,即有:
E =N 个任务占用的时空区/K 个功能段占用的总时空区(3-14)
式(3-14)是计算流水线效率的基本公式,其分母是处理N 个任务所需要的时间与
K 个功能段所围成的时空总面积K ·TK ,分子是处理N 个任务时实际占用的有效时空
面积。因此,流水线的效率包含时间和空间两方面的因素,通过时空图来计算流水线的效
率是极其必要又非常方便的。
1)流水线各功能段延迟时间相等时的效率
若有一条K 个功能段的线性流水线,各功能段延迟时间均为Δt。在流水线上处理
N 个连续输入的任务所需要的时间可见式(3-4),在这段时间内K 个功能段均被占用,
则时空图的总面积为K ·(N +K -1)Δt。任一任务占用的时空区为K ·Δt,N 个任务
实际占用的有效面积为N ·KΔt。则流水线效率为:
E = N ·KΔt
K ·(N +K -1)Δt= N
N +K -1 (3-15)
当N 趋于无穷大时的最大效率为:
Emax =lim N →∞
N
N +K -1=1 (3-16)
从式(3-16)中可以看出,当N 远大于K 时,流水线效率达到最大值即为1,这时“装
入时间”和“排空时间”忽略不计,流水线的各功能段均处于忙碌状态,时空图中每个时空
块均被有效利用。
2)流水线各功能段延迟时间不相等时的效率
根据流水线各功能段延迟时间不相等时吞吐率的计算分析,一条有K 个功能段的线
性流水线处理N 个连续任务的实际效率为:
E =N ·ΣK
i=1Δti K ·é
.
êê
ΣK
i=1Δti + (N -1)max{Δt1,Δt2,…,ΔtK}ù
.
úú
(3-17)
4.吞吐率、加速比和效率之间的关系
比较式(3-5)和式(3-15),可以得到:
E =TP ·Δt 或 TP =E/Δt (3-18)
式(3-18)说明:当流水线各功能段的延迟时间均为Δt 时,流水线的效率与吞吐率成
正比,即若采取措施提高了流水线的效率,则同时也提高了吞吐率。
比较式(3-11)和式(3-15),可以得到:
E =S/K 或 S =K ·E (3-19)
式(3-19)说明:流水线效率是流水线实际加速比S 与其最大加速比Smax=K 之比,
只有当流水线效率达到最大值1时,才能使实际加速比达到最大值K 。
当N 远大于K 时,则有:
Emax =1, Smax =K , TPmax =1/Δt (3-20)
123
第
3
章 信息加工的流水线技术
当流水线各功能段的延迟时间相等时,流水线上的各个功能段始终处于忙碌状态,没
有空闲时间,这时流水线的吞吐率、加速比和效率都很高,达到最大值。但实际上由于多
种原因,流水线的实际吞吐率、加速比和效率远低于相应的最大值。例如,流水线存在装
入和排空时间,输入的任务往往不是连续的,程序本身存在相关,多功能流水线在处理某
种任务时有的功能段不需要使用等。
特别地,计算流水线吞吐率、加速比和效率有许多公式,在实际分析流水线的性能时,
应该注意它们各自适用的场合,但式(3-3)、式(3-10)和式(3-14)具有普适性。另外,当
任务输入不连续时,需要先画出时空图,然后利用时空图来计算各项性能指标。
3.3.2
流水线最佳段数的选取
当流水线各功能段的延迟时间相等时,由于任务处理时间是不变的,所以增加流水线
功能段数量
K
,会使功能段延迟时间Δt
变小。由式(3-6)和式(3-12)可以看出,流水线
的最大吞吐率和最大加速比均可以得到提高。但由于每个功能段的输出端都必须设置一
个锁存器,使得在流水线功能段数量增加时,锁存器上的总延迟时间也将增加,任务处理
的总时间也必将增加。另外,随着流水线功能段数量增加,锁存器数量也将增加,流水线
的造价也会增加。所以,在设计流水线时,需要综合考虑各方面的因素,根据最佳性价比
来选取流水线功能段的数量。
假设采用串行处理时,处理一个任务所需要的时间为T。采用含有
K
个功能段的流
水线处理时,每个功能段的延迟时间为T/K,流水线的最大吞吐率为TPmx=1/(T/
K
+
D)(
D
为锁存器的总延迟时间)。又设流水线
K
个功能段的总造价为A,(a) 每个锁存器的
价格为B,则流水线的总价格为C=A+BK
。由此,将流水线的性价比PCR 定义为:
TPmax1 1PCR=
C
=T/
K
+
D
·
A
+BK
(3-21)
通过对自变量
K
求导,可得到PCR 的极值。由于大于零的极值只有一个,这个极值
就是最大值。如图3-24 所示,当性价比PCR 取得最大值时,它所对应的流水线的功能段
数量就是最佳段数K0:
K0=
TA/DB
(3-22)
图3-24
流水线性价比与功能段数的关系
由式(3-22)可以看出,流水线最佳段数与任务处理时间
T
和流水线功能段的造价
A
的平方根成正比,与锁存器的总延迟时间
D
和锁存器价格
B
的平方根成反比。目前,一
般处理机流水线的功能段数为2~10,极少超过15,且一般把段数大于或等于8的流水线
称为超流水线。