1、第三章 并行技术和高端处理器提高计算机性能提高计算机性能(速度速度)所经历的主要历程所经历的主要历程:微程序设计模式微程序设计模式RISC设计模式设计模式并行设计模式并行设计模式指令并行、数据并行、线程并指令并行、数据并行、线程并行、多核并行等已成为提升计行、多核并行等已成为提升计算机速度的主要手段算机速度的主要手段高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器 同时性同时性(simultaneity): 是指把两个或多个事件在同一时刻发生的并行是指把两个或多个事件在同一时刻发生的并行性叫同时性性叫同时性。 概述: 计算机中的并行性 并行性并行性(p
2、arallelism): 是指在同一时刻或是同一时间间隔内完成两件是指在同一时刻或是同一时间间隔内完成两件或两件以上的工作。只要时间上互相重叠或两件以上的工作。只要时间上互相重叠, 就就存在并行性。这一概念引入计算机系统存在并行性。这一概念引入计算机系统, 成为成为提高其性能的主要技术之一。提高其性能的主要技术之一。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器以以n位并行加法为例位并行加法为例: 由于存在进位信号的传播延迟时间由于存在进位信号的传播延迟时间, 全部全部n位加位加法结果并不是在同一时刻获得的法结果并不是在同一时刻获得的, 因此并不存因
3、此并不存在同时性在同时性, 而只存在并发性的关系。而只存在并发性的关系。 如果有如果有m个存储器模块能同时进行读出信息个存储器模块能同时进行读出信息, 则则属于同时性。属于同时性。 高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器 从软件运行的角度看从软件运行的角度看, 并行性从低到高可分为并行性从低到高可分为: (1) 指令内部并行指令内部并行: 指令内部的微操作之间的并行指令内部的微操作之间的并行; (2) 指令级并行指令级并行(Instruction Level Parallel, ILP): 并行执行两条或多条指令并行执行两条或多条指令; (3
4、) 任务级或过程级并行任务级或过程级并行: 并行执行两个或多个过并行执行两个或多个过程或任务程或任务(程序段程序段); (4) 作业或程序级并行作业或程序级并行: 多个作业或程序间的并行。多个作业或程序间的并行。 高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器 从处理数据的角度从处理数据的角度, 并行性从低到高可以分为并行性从低到高可以分为: (1) 字串位串字串位串: 同时只对一个字的一位进行处理同时只对一个字的一位进行处理; (2) 字串位并字串位并: 同时对一个字的全部位进行处理同时对一个字的全部位进行处理; (3) 字并位串字并位串: 同时对
5、多字的同一位进行处理同时对多字的同一位进行处理; (4) 全并行全并行: 同时对多字的全部或部分位进行处理。同时对多字的全部或部分位进行处理。 在一个计算机系统中在一个计算机系统中, , 可以采取多种并行性措施。可以采取多种并行性措施。可以有可以有执行程序方面执行程序方面的并行性的并行性, , 又可以有又可以有数据处数据处理方面理方面的并行性。当并行性提高到一定级别则认的并行性。当并行性提高到一定级别则认为进入并行处理领域。例如为进入并行处理领域。例如, , 执行程序的并行性执行程序的并行性达到任务或过程级达到任务或过程级, , 或者处理数据的并行性达到或者处理数据的并行性达到字并位串一级字并
6、位串一级, , 即可认为进入并行处理领域。即可认为进入并行处理领域。 高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器提高并行性的三种技术途径提高并行性的三种技术途径: (1) 时间重叠时间重叠: 即多个处理过程在时间上相互错开即多个处理过程在时间上相互错开, 轮流重叠使用同一硬件设备的不同部分轮流重叠使用同一硬件设备的不同部分, 以加以加快硬件周转。原则上不要求重复的硬件设备。快硬件周转。原则上不要求重复的硬件设备。(2) 资源重复资源重复: 根据根据“以数量取胜以数量取胜”的原则的原则, 通过重通过重复设置资源复设置资源(尤其是硬件资源尤其是硬件资
7、源), 大幅度提高计算大幅度提高计算机系统的性能。如多处理器系统是资源重复的机系统的性能。如多处理器系统是资源重复的典型情况。典型情况。 (3) 资源共享资源共享: 这是一种软件方法这是一种软件方法, 它使多个任务按它使多个任务按一定时间顺序轮流使用同一套硬件设备。例如一定时间顺序轮流使用同一套硬件设备。例如分时系统就是遵循资源共享这一思想产生的分时系统就是遵循资源共享这一思想产生的 。 高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器系统设计的定量原理系统设计的
8、定量原理:只加速使用频率高的部件只加速使用频率高的部件:这是最重要和最广泛的设计准则。因为频繁使用这是最重要和最广泛的设计准则。因为频繁使用的部件对系统性能的影响大的部件对系统性能的影响大, 反之影响则小。反之影响则小。阿姆达尔阿姆达尔(Amdahl)定律定律:阿姆达尔定律是最基本的定量分析原则阿姆达尔定律是最基本的定量分析原则, 指系统指系统中对某一部件采用某种更快的执行方式后中对某一部件采用某种更快的执行方式后, 所能所能获得的系统性能的改进程度获得的系统性能的改进程度, 取决于这种执行方取决于这种执行方式被使用的频率式被使用的频率, 或所占总时间比例。或所占总时间比例。所以可以认为所以可
9、以认为, 阿姆达尔定律实际上定义了采取阿姆达尔定律实际上定义了采取增强增强(加速加速)某部分功能处理后某部分功能处理后, 可获得的性能改进可获得的性能改进或执行时间的加速比。或执行时间的加速比。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器假设假设: To: 表示不采用任何增强功能措施完成某一任务时间表示不采用任何增强功能措施完成某一任务时间; Te: 表示采取某种增强功能措施完成同一任务所需时间表示采取某种增强功能措施完成同一任务所需时间;fe: 表示可采用增强功能措施部分所占百分比表示可采用增强功能措施部分所占百分比; re: 表示采取增强功能措
10、施比不采取增强功能措施可加表示采取增强功能措施比不采取增强功能措施可加快执行的倍数快执行的倍数;则性能加速比为则性能加速比为:Sp =(未采用改进措施前执行某任务时间未采用改进措施前执行某任务时间)(采采用改进措施后执行某任务的时间用改进措施后执行某任务的时间) =Te To=(1 fe) +re fe1高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器Sp=(1 fe) +re fe1例例1: 假设将某系统的某一假设将某系统的某一部件的处理速度加快到部件的处理速度加快到10倍倍, 但该部件的原处理时间但该部件的原处理时间仅为整个运行时间的仅为整个运行时
11、间的40%, 则采用加快措施后能使整则采用加快措施后能使整个系统的性能提高多少个系统的性能提高多少?解解: 由题意可知由题意可知 fe=0.4, re=10, 根据阿姆达尔定律根据阿姆达尔定律,Sp=(1 fe) +re fe1=(1 0.4) +10 0.41=1.56式中式中: (1 fe)表示不可改进表示不可改进部分部分, 当当fe为为0时时(即没有可即没有可改进部分时改进部分时), Sp为为1(性能性能没有提高没有提高); 当当re时时, 则则Sp=1/(1 fe), 即改进部分比即改进部分比例越大例越大, 加速比越高。加速比越高。因此性能提高幅度受改进因此性能提高幅度受改进部分所占比
12、例的限制。部分所占比例的限制。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器例例2: 假设某程序中假设某程序中, 求浮点数平方根求浮点数平方根FPSQR操作占整个操作占整个程序执行时间的程序执行时间的20%, 而所有浮点运算指令操作占整而所有浮点运算指令操作占整个程序执行的个程序执行的50%。现用两种措施提高计算机系统。现用两种措施提高计算机系统性能性能, 一种是采用一种是采用FPSQR硬件硬件, 可以使可以使FPSQR操作的操作的速度提高速度提高10倍倍; 另一种是使所有浮点指令的速度提高另一种是使所有浮点指令的速度提高两倍两倍, 试比较两种方案。
13、试比较两种方案。解解: 在两种方案下在两种方案下, re分别是分别是10和和2, fe分别是分别是20和和50, 使用加速比公式使用加速比公式:SFPPSQR=(1 fe) +(fere)1=(1 0.2) +(0.210)1 1.22SFPP=(1 fe) +(fere)1 1.33=(1 0.5) +(0.52)1采用采用“提高浮点指令的速度提高浮点指令的速度”比比“FPSQR硬件硬件”更更好。好。第一节第一节 流水线技术流水线技术流水技术是指流水技术是指:高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器 将一个重复的时序过程分解成为若将一个重复的
14、时序过程分解成为若干个子过程干个子过程, 而每个子过程都可以在其专用功能段而每个子过程都可以在其专用功能段上与其它子过程同时执行。上与其它子过程同时执行。理论上讲理论上讲: 效率为一个工人的三倍。效率为一个工人的三倍。一、指令流水线一、指令流水线( (整数整数) ) 假设假设: 将一条指令的整个过程分解为四个阶段将一条指令的整个过程分解为四个阶段: 非流水线方式非流水线方式(假设各阶段时间等长假设各阶段时间等长):处理器处理器t存结果存结果 t取指令取指令 t指令译码指令译码 t指令执行指令执行 t4 t时间时间完成整完成整条指令条指令高级计算机系统结构高级计算机系统结构 第三章并行技术和高端
15、处理器第三章并行技术和高端处理器完成完成n条指令需要条指令需要n 4 t 时间。时间。如果将如果将处理器处理器按照指令各阶段的功能按照指令各阶段的功能重新设计重新设计:让完成不同功能所涉及的硬件部分在逻辑上相让完成不同功能所涉及的硬件部分在逻辑上相互独立互独立, , 让不同逻辑功能部件在时间上并行工作让不同逻辑功能部件在时间上并行工作, , 从而使多条指令的不同阶段的功能并行完成从而使多条指令的不同阶段的功能并行完成, , 以以提高指令执行速度。提高指令执行速度。如下图所示如下图所示:WBiEXi+1FEi+3DEi+2写数写数逻辑逻辑取指取指逻辑逻辑译码译码逻辑逻辑执行执行逻辑逻辑高级计算机
16、系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器例例: 如以下几条指令的执行过程如以下几条指令的执行过程:写数写数逻辑逻辑取指取指逻辑逻辑译码译码逻辑逻辑执行执行逻辑逻辑 FE1指令指令1WB4EX5DE6WB5EX6WB6DE1 FE2指令指令2EX1DE2 FE3指令指令3WB1EX2DE3 FE4指令指令4WB2EX3DE4 FE5指令指令5WB3EX4DE5 FE6指令指令6注: 该图不反映流水线时间重叠关系, 只反映指令在不同阶段的功能在什么部件上完成。将该图按执行的时间顺序改写为(如下图):高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处
17、理器第三章并行技术和高端处理器 FE指令指令1DEEXWB FE指令指令2DEEXWB FE指令指令3DEEXWB指令指令4 FEDEEXWB指令指令5 FEDEEXWB指令指令6 FEDEEXWB4 t时完成时完成第第1条指令条指令t t2 t7 t5 t3 t6 t4 t9 t8 t19 t时完成时完成第第6条指令条指令高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器二、浮点加法流水线二、浮点加法流水线 浮点加法的全过程为浮点加法的全过程为求阶差求阶差、对阶对阶、尾数相加尾数相加、规格化规格化四个子过程四个子过程, 分别用不同的部件来实现。分别用不
18、同的部件来实现。 采用流水线以后采用流水线以后, 虽然每个加法操作的总时间仍虽然每个加法操作的总时间仍然是然是4 t , 但在加法器的输出端但在加法器的输出端, 却是每隔一个却是每隔一个 t就输出一个加法结果。就输出一个加法结果。 高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器求阶差求阶差对阶对阶尾数相加尾数相加规格化规格化求阶差求阶差对阶对阶尾数相加尾数相加规格化规格化求阶差求阶差对阶对阶尾数相加尾数相加.求阶差求阶差对阶对阶.三、流水线性能指标三、流水线性能指标(1) 流水线吞吐率流水线吞吐率TP (也称流水线排空时间也称流水线排空时间)是指在单
19、位时间内是指在单位时间内, 流水线所完成的流水线所完成的任务数量任务数量或者输出结果的数量。或者输出结果的数量。TP = Tkn其中其中: n为任务数量为任务数量, Tk是处理完是处理完n个任务所个任务所用的时间。用的时间。上述计算吞吐率的基本公式可根据流水线上述计算吞吐率的基本公式可根据流水线的具体设计可进一步细分下述两种情况的具体设计可进一步细分下述两种情况:高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器针对指令流水线针对指令流水线, 则为指令数量则为指令数量 各时间段均等的流水线各时间段均等的流水线假设一个时间段均等假设一个时间段均等( t)的
20、流水线的流水线, 级数为级数为k , 第一条指令输入后第一条指令输入后, 经过经过k t的时间完成的时间完成, 此此后的每一个后的每一个 t完成一条指令完成一条指令, 这样这样, 流水线完流水线完成成n条指令所需时间为条指令所需时间为: Tk = k t + (n 1) t代入基本公式代入基本公式:TP = Tkn=k t + (n 1) tn最大吞吐率最大吞吐率:TPmax = limnk t + (n 1) tn= t1高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(排空时间排空时间) 各段时间不完全相等的流水线各段时间不完全相等的流水线一般情况
21、下一般情况下, 不同的指令以及指令的不同阶段所不同的指令以及指令的不同阶段所需时间可能都会有差异需时间可能都会有差异, 因此可以按实际所需时因此可以按实际所需时间分配每一级的时间长度。间分配每一级的时间长度。比如比如: 假设流水线采用假设流水线采用5级流水深度级流水深度, 每一级按以下每一级按以下分配时间长度分配时间长度:15432 t2 t3 t t t 但存在控制很复杂、但存在控制很复杂、时间瓶颈使部分功能部件利用率较低的缺陷。时间瓶颈使部分功能部件利用率较低的缺陷。第第2级部件需等待第级部件需等待第3级部件级部件2 t的时间之后才能的时间之后才能将操作交给第将操作交给第3级部件级部件;
22、即即: t1= t , t2= t , t3=3 t , t4=2 t , t5= t高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器指令指令1指令指令2指令指令3等待时间等待时间, 称为称为 流水线阻塞流水线阻塞 流水线执行情况流水线执行情况:1 2 3 3 3 4 4 51 2 3 3 3 4 4 51 2 3 3 3 4 4 5指令指令41 2 3 3 3 4 4 5t t8 t11 t14 t17 t从第从第2条指令开始条指令开始, 每每3 t完成完成1条指令条指令, 因此有因此有:TP = Tkn=+ (n 1) Max( t1 , t2 ,
23、 tk) n tiki=1高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(2) 流水线加速比流水线加速比TP =Max( t1 , t2 , tk)1最大吞吐率最大吞吐率:如上例中如上例中, 最大吞吐率最大吞吐率:TP =3 t1流水线加速比定义流水线加速比定义: 按顺序方式执行一批指令所用的时间与按流按顺序方式执行一批指令所用的时间与按流水线方式执行同一批指令所用时间之比。水线方式执行同一批指令所用时间之比。加速比加速比: S =TkTs顺序方式执行所用时间顺序方式执行所用时间流水线方式执行所用时间流水线方式执行所用时间高级计算机系统结构高级计算机
24、系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器假设流水线各段时间均等为假设流水线各段时间均等为 t , 则一条则一条k段流水段流水线完成线完成n条指令所需时间为条指令所需时间为: Tk =(k+n 1) t。假设按顺序执行假设按顺序执行n条指令条指令, 则完成则完成n条指令所需时条指令所需时间为间为: Ts = nk t 。因此有加速比因此有加速比: S =nk k+n 1 最大加速比最大加速比:Smax =nk k+n 1 limn=k即当即当nk时时, ,流水线加速比等于流水线段数流水线加速比等于流水线段数, , 因此理论上流水线段数越多越好因此理论上流水线段数越多越好,
25、, 但在设计但在设计上会带来许多问题。上会带来许多问题。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(3) 流水线效率流水线效率流水线效率是指流水线效率是指: 流水线中的功能部件的利用率流水线中的功能部件的利用率, 其值为流水线功能部件的实际使用时间与整个运其值为流水线功能部件的实际使用时间与整个运行时间之比。行时间之比。假设流水线级数为假设流水线级数为k , 各级时间相等各级时间相等( t), 完成完成n条条指令总时间为指令总时间为Tk , 则每一级的效率为则每一级的效率为(理想情况理想情况):E =由于各级相同由于各级相同, 则整条流水线利用率
26、则整条流水线利用率:ei =n tTk= (k+n 1) tn t= (k+n 1)n (k+n 1)n当当nk 时时, E趋于趋于1。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器例例. 一个四级流水线一个四级流水线(各级等长各级等长), 仅执行完一条指令时仅执行完一条指令时:E = (k+n 1)n= (4+1 1)1=41即即: 由于仅执行完一条指令由于仅执行完一条指令, 流水线四段中流水线四段中, 在任在任何一个何一个 t时间内时间内, 都只有一个段被使用都只有一个段被使用, 其余其余三个段为空闲三个段为空闲, 因此利用率只有四分之一。因此利
27、用率只有四分之一。再假设执行完三条指令再假设执行完三条指令, 且流水线无阻塞且流水线无阻塞:E = (k+n 1)n= (4+3 1)3=21流水线情况流水线情况:高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器 FE指令指令1DEEXWB FE指令指令2DEEXWB FE指令指令3DEEXWBt t2 t5 t3 t6 t4 t1在流水线执行过程中在流水线执行过程中, 各段空闲情况各段空闲情况:取指部件取指部件: 空闲空闲 t4、 t5、 t6译码部件译码部件: 空闲空闲 t1、 t5、 t6执行部件执行部件: 空闲空闲 t1、 t2、 t6写数部件
28、写数部件: 空闲空闲 t1、 t2、 t3即在整个即在整个6 t的时间的时间, 任何一个部件都存在任何一个部件都存在3 t的的空闲空闲, 利用率利用率1/2。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器如果各级的效率不完全相等如果各级的效率不完全相等, 则流水线效率为则流水线效率为:E = n tiki=1K tiki=1+(n1) max( t1 , t2. tk)高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器上述计算公式都是流水线在理想情况的计算方法上述计算公式都是流水线在理想情况的计算方法, 在实际
29、情况在实际情况, 流水线可能存在阻塞流水线可能存在阻塞, 不能按理想状不能按理想状态实现流水执行。态实现流水执行。 非理想状况下流水线效率分析非理想状况下流水线效率分析:假设一段程序由假设一段程序由n条指令构成的条指令构成的, 分为分为K级流水级流水, 用用 tij表示第表示第i条指令的第条指令的第j阶段所需时间。阶段所需时间。(1) 如果采用顺序执行如果采用顺序执行, 则有则有:第第1条指令完成时间条指令完成时间: t11 + t12 + t13. + t1K第第2条指令完成时间条指令完成时间: t21 + t22 + t23. + t3K第第3条指令完成时间条指令完成时间: t31 + t
30、32 + t33. + t3K第第n条指令完成时间条指令完成时间: tn1 + tn2 + tn3. + tnK顺序完成该程序所需时间为上述所有顺序完成该程序所需时间为上述所有 tij的累加的累加:TS = i=1nj=1k tij高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器第第1个部件使用时间个部件使用时间: t11+ t21+ t31+ tn1第第2个部件使用时间个部件使用时间: t12+ t22+ t32+ tn2第第3个部件使用时间个部件使用时间: t13+ t23+ t33+ tn3第第K个部件使用时间个部件使用时间: t1K+ t2K+
31、 t3K+ tnK所有所有K个部件的平均使用时间为个部件的平均使用时间为:( t11+ t21+ tn1) + ( t12+ t22+ tn2) + +( t1K + t2K+ tnK)K=TSK(2) 如果按流水线方式执行如果按流水线方式执行, 则有则有:假设完成的总时间为假设完成的总时间为TK , 所谓效率则是流水线部所谓效率则是流水线部件被实际使用的时间占总时间的比例。件被实际使用的时间占总时间的比例。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器所有部件的平均使用时间除以该程序完成的总时间所有部件的平均使用时间除以该程序完成的总时间(Tk)则
32、为利用率则为利用率, 即即:TS为顺序方式执行所用时间为顺序方式执行所用时间;Tk为流水线方式执行所用时间。为流水线方式执行所用时间。上式即为一种简单实际的流水线效率计算方法。上式即为一种简单实际的流水线效率计算方法。E =TSTkk Tkk=TS高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器四、流水线的相关与冲突四、流水线的相关与冲突1、流水线相关、流水线相关相关是指两条指令之间存在某种依赖关系。相关是指两条指令之间存在某种依赖关系。一般来说一般来说, 指令之间的依赖性越少指令之间的依赖性越少, 流水线各级流水线各级的并行性越高的并行性越高, 流水
33、线效率也越高。流水线效率也越高。反之反之, 依赖性越多依赖性越多, 流水线各级的并行性越低流水线各级的并行性越低, 流水线效率也越低。流水线效率也越低。有三种类型的相关有三种类型的相关:数据相关数据相关( (真数据相关真数据相关) )、名相关名相关、控制相关控制相关高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(1) 数据相关数据相关假设两条指令假设两条指令Insi和和Insj (Insi在在Insj之前之前) , 如果如果有下列情形之一有下列情形之一, 则称指令则称指令Insi和和Insj数据相关数据相关: Insj使用使用 Insi产生的结果产生
34、的结果 Insj与与 Insk数据相关数据相关, 而而Insk又与又与Insi数据相关数据相关后者表明数据相关具有传递性。后者表明数据相关具有传递性。如下程序段存在数据相关如下程序段存在数据相关:MOV Ri , 8MOV Rj , RiADD Rk , Rj由此可知由此可知, 数据相关会引发流水线阻塞。数据相关会引发流水线阻塞。第二条指令使用第一条指令产第二条指令使用第一条指令产生的结果生的结果, 第三条指令使用第第三条指令使用第二条指令产生的结果。二条指令产生的结果。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(2) 名相关名相关名相关是指名相
35、关是指: 如果两条指令使用了相同的寄存如果两条指令使用了相同的寄存器或者存储单元器或者存储单元, 但他们之间没有数据流动但他们之间没有数据流动, 则则称这两条指令名相关。称这两条指令名相关。 由于两条指令仅仅是使用了相同的名字而没有由于两条指令仅仅是使用了相同的名字而没有数据传输数据传输, 所以只需通过改变指令中操作数的所以只需通过改变指令中操作数的名称即可消除名相关名称即可消除名相关(可通过编译或硬件实现可通过编译或硬件实现)。(3) 控制相关控制相关控制相关是由分支指令引起的控制相关是由分支指令引起的, 程序流向需根程序流向需根据分支指令执行的结果来确定。据分支指令执行的结果来确定。控制相
36、关可引起流水线阻塞控制相关可引起流水线阻塞, 是流水线中要解是流水线中要解决的重要问题。决的重要问题。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器由于相关的存在由于相关的存在, 可能引发流水线冲突而导致流可能引发流水线冲突而导致流水线阻塞。水线阻塞。2、流水线冲突、流水线冲突(1) 数据冲突数据冲突:(2) 控制冲突控制冲突:(3) 结构冲突结构冲突:一条指令执行过程中一条指令执行过程中, 需要前面需要前面的指令的执行结果。的指令的执行结果。分支指令未执行完成分支指令未执行完成, 导致流水线导致流水线不能正常往下执行。不能正常往下执行。硬件资源满足
37、不了指令重叠执行硬件资源满足不了指令重叠执行的要求的要求, 而可能引发流水线阻塞。而可能引发流水线阻塞。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器五、分支预测技术五、分支预测技术主要讨论硬件动态地进行分支处理主要讨论硬件动态地进行分支处理, 即在程序即在程序运行过程中运行过程中, 根据分支指令过去的表现来预测根据分支指令过去的表现来预测其将来的行为。其将来的行为。采用动态分支预测应实现两个目的采用动态分支预测应实现两个目的: 判断预测是否成功判断预测是否成功 尽快找到分支目标地址尽快找到分支目标地址, 以避免流水线阻塞以避免流水线阻塞如何记录分支
38、的历史信息如何记录分支的历史信息, 要记录哪些信息要记录哪些信息?(2) 如何根据这些信息来预测分支的方向如何根据这些信息来预测分支的方向, 甚甚至提前取出分支目标指令至提前取出分支目标指令?为此为此, 需解决以下两个问题需解决以下两个问题:高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器此外此外, 在分支预测错误时在分支预测错误时, 要作废已经预取和分析要作废已经预取和分析的指令的指令, 恢复现场恢复现场, 并从另一路分支重新取指令。并从另一路分支重新取指令。如下图所示如下图所示:i 1ii+1i+2p+1p+2分支指令预测执行路径实际执行路径显然显
39、然, 为了能恢复现场为了能恢复现场, 需要在执行预测目标指需要在执行预测目标指令之前将现场保存起来。令之前将现场保存起来。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器1、分支历史表、分支历史表BHT采用采用Branch History Table(BHT)来记录分支指来记录分支指令的历史令的历史, 并按该历史情况来进行预测。并按该历史情况来进行预测。所谓所谓“历史历史”是指最近一次或几次的执行是成是指最近一次或几次的执行是成功还是失败。如果只记录最近一次的历史功还是失败。如果只记录最近一次的历史, 则则BHT 中只需要中只需要1个二进制位个二进制位
40、(最简单的一种方式最简单的一种方式)。为提高预测精度为提高预测精度, 常采用两位二进制来记录历史常采用两位二进制来记录历史,实际测试表明实际测试表明, 采用更多的位与采用两位的预测采用更多的位与采用两位的预测精度差异不大。精度差异不大。 两位分支预测的状态转换图如下两位分支预测的状态转换图如下:高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器00011011分支不成功分支不成功分支成功分支成功分支不成功分支不成功分支成功分支成功分支不成功分支不成功分支成功分支成功分支不成功分支不成功分支成功分支成功分支预测不成功分支预测不成功分支预测成功分支预测成功在
41、在00和和01状态下状态下, 预测不成功预测不成功, 在在10和和11状态下状态下, 预测成功。预测成功。 线条边的文字说明是指分支指令的实线条边的文字说明是指分支指令的实际执行情况。际执行情况。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器两位预测操作有两步两位预测操作有两步: 分支预测分支预测; 修改状态修改状态当分支指令到达译码阶段时当分支指令到达译码阶段时, 根据从根据从BHT中读出的中读出的信息进行预测信息进行预测:(1) 从BHT中读出的数据为“00”或“01”, 按“分支不成功”处理, 继续处理分支指令的下一条指令。当分支指令的实际执行
42、结果出来后, 如果发现预测正确, 继续执行指令, 否则, 作废已经预取的和分析的指令, 恢复现场, 并从分支路径重新取指令执行。 对状态的修改操作是: 在原状态为“00”情况下, 如果预测不正确, 则则将状态改为“01”; 否则, 就是预测正确, 状态不变；若原状态为“01”, 如果预测不正确, 则将状态改为“11”; 否则, 就是预测正确, 则将状态改为“00” 。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器(2) 从BHT中读出的数据为“10”或“11”, 按“分支成功”处理处理, 即从成功分支路取指令进行处理。待分支指令的实际执行结果出来后,
43、 如果发现预测正确, 继续执行指令, 否则, 作废已经预取的和分析的指令, 恢复现场, 并从分支路径重新取指令执行。 对状态的修改操作是:若原状态为“11”, 如果预测不正确, 则则将状态改为“10”; 否则, 就是预测正确, 状态不变; 若原状态为“10”, 如果预测不正确, 则将状态改为“00”; 否则, 就是预测正确, 则将状态改为“11” 。BHT可以放在指令高速缓存中可以放在指令高速缓存中, 也可以用专也可以用专门的硬件来实现。门的硬件来实现。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器BHT仅仅是预测分支是否成功仅仅是预测分支是否成功,
44、 而对分支目标地而对分支目标地址不提供支持址不提供支持, 还需要另外的时间来计算目标地还需要另外的时间来计算目标地址址, 因此因此, 如果确定分支目标地址的时间比较长如果确定分支目标地址的时间比较长时时(大于或远大于预测时间大于或远大于预测时间), BHT方法就没有什方法就没有什么意义。么意义。2、采用分支目标缓冲器、采用分支目标缓冲器BTBBTB是一个由硬件实现的专用表格。表格中是一个由硬件实现的专用表格。表格中每一项至少由两个字段构成每一项至少由两个字段构成: 已执行过的成功分支指令的地址已执行过的成功分支指令的地址 预测的分支目标地址预测的分支目标地址高级计算机系统结构高级计算机系统结构
45、 第三章并行技术和高端处理器第三章并行技术和高端处理器在每次取指令的同时在每次取指令的同时, 用该指令的地址与用该指令的地址与BTB中中的所有项目的第一个字段进行比较的所有项目的第一个字段进行比较, 如果有匹配如果有匹配的的, 意味着该指令是分支指令并且上一次执行分意味着该指令是分支指令并且上一次执行分支是成功的支是成功的, 据此预测本次执行也将分支成功据此预测本次执行也将分支成功, 分分支地址由该项的第二个字段给出支地址由该项的第二个字段给出;如果没有匹配的如果没有匹配的, 就把当前指令当作普通指令就把当前指令当作普通指令(不不是分支指令是分支指令)来执行。来执行。如下图所示如下图所示:高级
46、计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器当前取指令的地址当前取指令的地址成功的分支指令地址成功的分支指令地址 分支目标地址分支目标地址 A0P0A1P1.Ak-1Pk-1查找查找有匹配有匹配该指令为成功分支指令该指令为成功分支指令, 用预测的分用预测的分支目标地址作为下一条指令的支目标地址作为下一条指令的PC值值有有无无本指令不是分支指本指令不是分支指令令, 按普通指令执行按普通指令执行高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器由于由于BTB中存放的是执行过的成功分支指令的中存放的是执行过的成功分支指
47、令的地址地址, 所以如果当前指令的地址与所以如果当前指令的地址与BTB中的第一中的第一个字段匹配个字段匹配, 那么就将该匹配项中第二个字段中那么就将该匹配项中第二个字段中的地址送往的地址送往PC, 从分支目标处开始取指令。如从分支目标处开始取指令。如果预测正确果预测正确, 则不会产生任何分支延迟则不会产生任何分支延迟; 如果预如果预测错误测错误, 或者在或者在BTB中没有匹配的项中没有匹配的项, 则至少有则至少有两个时钟周期的延迟开销两个时钟周期的延迟开销 (更新更新BTB中的项中的项, 在在更新期间停止取指令更新期间停止取指令)。 采用采用BTB时所进行的处理步骤时所进行的处理步骤:高级计算
48、机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器当前当前PC值送存储器和值送存储器和BTBBTB中有匹配的项中有匹配的项成功分支指令成功分支指令正常执行指正常执行指令令(无延迟无延迟)将其将其PC值和分支目值和分支目标地址写入标地址写入BTB作为作为一个新的项一个新的项(有延迟有延迟) 否否是是以以BTB的第二个字段作的第二个字段作为分支目标地址送为分支目标地址送PC当前分支成功当前分支成功否否是是否否分支预测错误分支预测错误, 清清除已取指令除已取指令, 从另从另一分支取指令一分支取指令, 从从BTB中删除相应中删除相应项项 (有延迟有延迟) 是是分支预测正
49、分支预测正确确, , 继续执行继续执行后续后续( (无延迟无延迟) ) BTB的另一种形式是在分支目标缓冲器中增加一的另一种形式是在分支目标缓冲器中增加一个个“分支历史表分支历史表”(也称也称“转移历史表转移历史表”) 字段字段, 存存放过去所有执行过的分支指令的转移情况放过去所有执行过的分支指令的转移情况(无论转无论转移成功与否移成功与否), 该字段用于转移预测该字段用于转移预测(功能类似于签功能类似于签前述的前述的BHT)。当前预取的指令当前预取的指令分支指令地址分支指令地址 分支历史表分支历史表 分支目标地址分支目标地址 A0 T0 P0 A1 T1 P1 Ak1 Tk1 Pk1.查找该
50、方法实际上是BTB 与BHT相结合高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器第二节 向量处理技术向量处理机向量处理机:a1a2aN.A=b1b2bN.B=c1c2cN.C=d1d2dN.D=可以有如下几种处理方式可以有如下几种处理方式:具有向量数据表示和向量指令的流水线处理机。具有向量数据表示和向量指令的流水线处理机。 例例: 考虑以下向量计算考虑以下向量计算: D = A (B + C) 其中其中A、B、C、D是长度为是长度为 N 的向量。的向量。高级计算机系统结构高级计算机系统结构 第三章并行技术和高端处理器第三章并行技术和高端处理器1. 水
