计算机系统结构.ppt
《计算机系统结构.ppt》由会员分享,可在线阅读,更多相关《计算机系统结构.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第六章第六章 向量流水处理向量流水处理 6.1 向量流水机的基本系统结构向量流水机的基本系统结构 向量流水处理的主要特点向量流水处理的主要特点 向量机的基本系统结构向量机的基本系统结构 向量启动时间和启动率向量启动时间和启动率6.2向量操作长度控制和向量访问步长向量操作长度控制和向量访问步长6.3 向量处理方法向量处理方法6.4增强向量处理性能的方法增强向量处理性能的方法 多功能部件的并行操作多功能部件的并行操作 链接技术链接技术 条件执行语句和稀疏矩阵和加速处理方法条件执行语句和稀疏矩阵和加速处理方法 向量归约操作的加速方法向量归约操作的加速方法6.5向量处理性能的评估参数和方法向量处理性能
2、的评估参数和方法6.6向量化编译技术向量化编译技术16.1 向量流水机的基本系统结构向量流水机的基本系统结构 前面所介绍的标量流水机在实际应用中要使性能进一步前面所介绍的标量流水机在实际应用中要使性能进一步提高,提高,通常要受到以下两个因素的约束:通常要受到以下两个因素的约束:流水线的工作时钟不可能取得很短。流水线的工作时钟不可能取得很短。取指与译码的速率受到限制,即在一个时钟周期内最取指与译码的速率受到限制,即在一个时钟周期内最多只能启动一条指令,通常称为多只能启动一条指令,通常称为Flynn瓶颈。瓶颈。6.1.1 向量流水处理的主要特点:向量流水处理的主要特点:由于每一个由于每一个当前当前
3、结果向量元素的计算结果向量元素的计算与以前与以前结果向量结果向量元素的计算是元素的计算是相互独立的相互独立的,这就允许向量流水线有较深的,这就允许向量流水线有较深的深度。深度。一条向量流水指令相当于一个标量循环,从而可降低一条向量流水指令相当于一个标量循环,从而可降低对指令访问带宽的要求,同时也消除了由循环转移起的控对指令访问带宽的要求,同时也消除了由循环转移起的控制相关。制相关。2 若向量指令所要访问的向量元素均相邻,则可以在若向量指令所要访问的向量元素均相邻,则可以在交交叉存储体叉存储体中依次访问它们。由于一个向量中通常含有多个中依次访问它们。由于一个向量中通常含有多个元素,因此对存储器访
4、问的延迟平均到每个元素上其访存元素,因此对存储器访问的延迟平均到每个元素上其访存等待时间开销较小。等待时间开销较小。由以上这些特点:由以上这些特点:向量流水机对相同数量的数据项进行操作时,要比一向量流水机对相同数量的数据项进行操作时,要比一 串标量指令操作更快。串标量指令操作更快。向量流水机还可使访存和有效地址计算流水化。向量流水机还可使访存和有效地址计算流水化。高档向量机还允许多个向量操作同时进行,从而可开高档向量机还允许多个向量操作同时进行,从而可开发对不同元素进行多个向量操作的并行性。发对不同元素进行多个向量操作的并行性。6.1.2 向量机的基本系统结构向量机的基本系统结构 向量机系统结
5、构按向量操作对象及结果主要存入在寄存向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中,可分为器中还是存放在存储器中,可分为RR工作方式向量机和工作方式向量机和MM工作方式向量机两大类工作方式向量机两大类。3 MM方式是源向量来自于方式是源向量来自于M,结果,结果M。R R方式是源向量来自于方式是源向量来自于R,结果,结果R。不管是哪一种计算机,其典型结构见不管是哪一种计算机,其典型结构见P112图图6.1 设:设:Y=a X+Y其中其中X和和Y为向量,初始为向量,初始值放在值放在MM 中,中,a为标为标量。量。根椐表达式求解是根椐表达式求解是单单精度精度还是还是双精度操作
6、双精度操作,分别称为分别称为SAXPY或或DAXPY循环,表示单或循环,表示单或双精度的双精度的a乘以乘以X后再加后再加Y(这是一个常用循环。这是一个常用循环。设向量长度为设向量长度为64,元素,元素长度为长度为8)。4 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(R
7、y),F4 ;存结果向量元素;存结果向量元素 ADDI Rx,Rx,#8 ;增量向量元素;增量向量元素x下标下标 ADDI Ry,Ry,#8 ;增量向量元素;增量向量元素y下标下标 SUB R20,R4,Rx ;R4-RxR20,计算是否到达限界值,计算是否到达限界值 BNZ R20,LOOP ;若循环未结束,转;若循环未结束,转LOOP 若用向量机来完成同样操作,则有:若用向量机来完成同样操作,则有:LD F0,a ;标量;标量a装入装入F0 LV V1,Rx ;装入向量;装入向量X,LV为为向量取向量取指令指令 MULTV V2,F0,V1 ;向量;向量X与标量与标量a相乘相乘 LV V3
8、,RY ;装入向量;装入向量Y ADDV V4,V2,V3 ;向量加;向量加aX+Y SV RY,V4 ;存结果向量,;存结果向量,SV为为向量存向量存指令指令循循环环体体共共有有9条条指指令令5 对两程序比较,可见对两程序比较,可见 标量机共需要执行标量机共需要执行9 64+2=578条指令,而向量机仅有条指令,而向量机仅有6条指令条指令即可完成。即可完成。标量流水机中,流水线联锁标量流水机中,流水线联锁(相关停顿相关停顿)的频率远高于向量机,的频率远高于向量机,标量机中每一个元素都有标量机中每一个元素都有ADD等待等待MUL及及SD等待等待ADD的情况。而的情况。而向量机每条指令只需停顿一
9、次。向量机每条指令只需停顿一次。6.1.3 向量启动时间和启动率向量启动时间和启动率 设有一条向量指令所需时间设有一条向量指令所需时间TVP为为 TVP=Tst+n Ir (6.1)Tst:流水线启动时间;:流水线启动时间;(包括流水线固有的延迟时间包括流水线固有的延迟时间)以便设置为完以便设置为完成向量操作所需的相应参数成向量操作所需的相应参数(如向量长度等如向量长度等)。n:向量长度;:向量长度;Ir:启动率。表示一旦向量指令开始运行后,:启动率。表示一旦向量指令开始运行后,即向量流水线填满后,即向量流水线填满后,每流出一个结果所需的时间。每流出一个结果所需的时间。6 对于对于RR方式来说
10、,流水线的启动时间主要取决于功能部件流水方式来说,流水线的启动时间主要取决于功能部件流水的深度的深度。每个结果需要的钟周期数每个结果需要的钟周期数例:例:设一个向量乘法流水部件的启动时间为设一个向量乘法流水部件的启动时间为10个时钟周期,启动率个时钟周期,启动率Ir为为1,则对于长度为,则对于长度为64的向量乘法产生每个向量元素结果所需要的的向量乘法产生每个向量元素结果所需要的钟周期数为钟周期数为76.2向量操作长度控制和向量访问步长向量操作长度控制和向量访问步长 向量寄存器型向量寄存器型的向量机具有一个的向量机具有一个自然向量长度自然向量长度,即每个,即每个向量寄存器中的向量元素个数,例向量
11、寄存器中的向量元素个数,例 Cray-1机为机为64。但实。但实际程序中的向量长度往往不会与此长度相等。一个具体的际程序中的向量长度往往不会与此长度相等。一个具体的向量操作长度在编译时也常常是未知的,例如:向量操作长度在编译时也常常是未知的,例如:do 10 i=1,n10 y(i)=a x(i)+y(i)在向量长度寄存器中存放的长度值在向量长度寄存器中存放的长度值向量寄存器的长度向量寄存器的长度(MVL)的向量均可放入向量寄存器。的向量均可放入向量寄存器。向量长度向量长度向量寄存器长度时,就必须将向量长度按向向量寄存器长度时,就必须将向量长度按向量寄存器长度分段。分段后的向量长度即是每次向量
12、操作量寄存器长度分段。分段后的向量长度即是每次向量操作的长度,必须的长度,必须向量寄存器长度。向量寄存器长度。例子见例子见P148中间程序。中间程序。8 low=1 VL=(n mod MVL)*找出零头长度值找出零头长度值 do 20 j=0,(n/MVL)*外循环外循环 do 10 i=low,low+VL-1 *以长度以长度VL操作操作 V(i)=a X(i)+Y(i)*主要操作主要操作 10 continue low=low+VL *下一向量的开始下一向量的开始 VL=MVL *将长度恢复成将长度恢复成MVL 20 continue内内循循环环例例:有两个有两个100 100元素的矩阵
13、元素的矩阵A和和B相乘的程序段如下:相乘的程序段如下:do 10 i=1,100 do 10 j=1,100C(i,j)=0.0 do 10 k=1,100 10 C(i,j)=C(i,j)+A(i,k)B(k,j)9 向量由向量由MMR向向,则在,则在MM中中间隔间隔存放的元素在存放的元素在R向向中便成为逻中便成为逻辑上相连续的,辑上相连续的,如果向量机支持对向量的跨步访问,则称这种向量如果向量机支持对向量的跨步访问,则称这种向量机为支持完全的一维数据显式访问机为支持完全的一维数据显式访问。因为它能以行、列,甚至以对。因为它能以行、列,甚至以对角线访问这些方向上的元素,角线访问这些方向上的元
14、素,Cray-1巨型机就是这种向量机。巨型机就是这种向量机。而而MM工作方式的工作方式的Cyber205巨型机中巨型机中,则,则不支持不支持这种完全一维这种完全一维数据显式访问,它只能以连续方式访存。如果要进行跨步访问运算,数据显式访问,它只能以连续方式访存。如果要进行跨步访问运算,则必须先将这些在则必须先将这些在MM中不连续存放的向量元素,先经过运算部件中不连续存放的向量元素,先经过运算部件进行依次排序,然后再送入进行依次排序,然后再送入MM使它们相邻连续存放,最后再从使它们相邻连续存放,最后再从MM中连续取出进行运算,显然这将大降低运算性能。中连续取出进行运算,显然这将大降低运算性能。通常
15、向量机,为了增加访存速率,通常向量机,为了增加访存速率,大都采用大都采用低位地址低位地址多体交叉多体交叉MM,当向量机支持跨步长度访问时,就可能出现,当向量机支持跨步长度访问时,就可能出现对同一存储体对同一存储体访问间隔时间访问间隔时间访存周期时间访存周期时间,若使得上一次对某一存储体的访问,若使得上一次对某一存储体的访问结束前,对结束前,对同一同一存储体提出了新的访问要求,从而存储体提出了新的访问要求,从而加剧访存冲突加剧访存冲突。4010 例例:设有:设有16个存储体,访问时间为个存储体,访问时间为12个时钟周期,共要访问个时钟周期,共要访问64 个个向量元素。向量元素。对于步长为对于步长
16、为1的访问的访问,除了第一次被访问的存储体需要,除了第一次被访问的存储体需要12个周个周期外,以后每个存储体依次间隔期外,以后每个存储体依次间隔1个周期就可进行一次访问,故共个周期就可进行一次访问,故共需要需要12+63=75 个时钟周期。个时钟周期。当步长为当步长为16的倍数时的倍数时,由于每次对存储器访问将与前一次访问,由于每次对存储器访问将与前一次访问发生冲突时,因此,每一个元素的访问都需要发生冲突时,因此,每一个元素的访问都需要12 个周期,这样个周期,这样64个个元素就需要元素就需要64 12=768个周期。个周期。例:例:对于对于64个存储体个存储体,步长为,步长为32时,每隔一次
17、访问时,每隔一次访问(即两次访问即两次访问后后)就会发生一次冲突。步长为就会发生一次冲突。步长为8 时,每隔时,每隔7次访问次访问(即即8 次访问后次访问后)才会发生冲突。才会发生冲突。此外,增加存储体数目,通常也可减少产生访问冲突的频率此外,增加存储体数目,通常也可减少产生访问冲突的频率。为了使访存不发生冲突应设法使跨步和存储体数互为质数。为了使访存不发生冲突应设法使跨步和存储体数互为质数。例:存储体数为例:存储体数为17,而跨步长为,而跨步长为16。113126.3 向量处理方法向量处理方法 例例:D=A(B+C)的向量运算,的向量运算,A、D、C都是长度为都是长度为n的向量。有的向量。有
18、下列三种加工方式。下列三种加工方式。普遍采用的方法是按向量顺序计算的普遍采用的方法是按向量顺序计算的横向横向加工加工d1=a1(b1+c1)d2=a2(b2+c2)dn=an(bn+cn)这里每一步都要先进行这里每一步都要先进行bi+cik的运算,的运算,然后进行然后进行k ai di运算,运算,这就要产生数据相关。这就要产生数据相关。另一种方法是另一种方法是垂直垂直加工加工:先进行纵向加工所有先进行纵向加工所有B和和C中的元素的对应加法,即中的元素的对应加法,即bi+ciki 再进行纵向加工的乘法操作,即再进行纵向加工的乘法操作,即ki ai di13 此时向量指令表示形式变成此时向量指令表
19、示形式变成K=B+CD=A K 由此可见,由此可见,纵向加工具有较高的吞吐率纵向加工具有较高的吞吐率,但需要一个中间向量但需要一个中间向量K(具有具有k1 kn共共n个分量个分量),在,在MM工作方式中都采用这种方式。工作方式中都采用这种方式。称为称为纵横向纵横向加工加工(或称为分组加工或称为分组加工),以,以RR工作方式的向量机工作方式的向量机均采用此加工方式均采用此加工方式。14设设 N:向量长度:向量长度 n:向量寄存器可表示的最大限度为,则:向量寄存器可表示的最大限度为,则 N=k n+r nN,r n,k、n、r均为正整数。均为正整数。k为组数,为组数,r为余数为余数(余下的部分也作
20、为一组处理余下的部分也作为一组处理)。加工方式是加工方式是:组内纵向加工,组间为横向加工。:组内纵向加工,组间为横向加工。第一组计算第一组计算k1 n=b1 n+c1 n d1 n=a1 n k1 n 第二组计算第二组计算k(n+1)2n=b(n+1)2n+c(n+1)2n d(n+1)2n=a(n+1)2n k(n+1)2n 由此可知,每组内各有两条向量指令,由此可知,每组内各有两条向量指令,各组内有一次数据相关需各组内有一次数据相关需2次流水功能切换次流水功能切换,只需只需n个中间向量寄存器单元个中间向量寄存器单元k1 n,Cray1与一与一些小巨型机都采用这种加工方式。些小巨型机都采用这
21、种加工方式。156.4增强向量处理性能的方法增强向量处理性能的方法 共有共有4种改善向量机性能的方法。种改善向量机性能的方法。采用多功能部件,使它们并行工作采用多功能部件,使它们并行工作。加快一串相关向量指令的操作速度加快一串相关向量指令的操作速度。又称。又称链接技术链接技术,首先在,首先在Cray-1巨型机上得到应用,目前的向量机都支持这种技术。巨型机上得到应用,目前的向量机都支持这种技术。另外两种方法另外两种方法主要是为了增加以向量方式操作的循环类型主要是为了增加以向量方式操作的循环类型。这两这两种方法在许多向量机上采用种方法在许多向量机上采用。多功能部件的并行操作多功能部件的并行操作 如
22、如Cray-1巨型机中,共有巨型机中,共有4组组12个单功能流水部件,见个单功能流水部件,见P151图图6.3。第一组为向量功能部件,有向量加,移,逻辑运算第一组为向量功能部件,有向量加,移,逻辑运算3个功能部件。个功能部件。16 第二组为浮点部件,第二组为浮点部件,FADD,FMUL,浮点倒数。,浮点倒数。第三组为标量功能部件,标量,逻辑运算第三组为标量功能部件,标量,逻辑运算 移位移位 数数/计数计数4个部件。个部件。延时延时17 第四组为地址功能部件,地址加和地址乘。第四组为地址功能部件,地址加和地址乘。这些功能部件都是独立的,只要满足一定的约束条件,这些功能部件都是独立的,只要满足一定
23、的约束条件,它们可以它们可以并行操作,约束条件是并行操作,约束条件是:不存在不存在使用使用R向向的冲突的冲突。不存在不存在功能部件使用的冲突功能部件使用的冲突。R向向使用冲突使用冲突:指并行工作的向量指令中的源向量或结果向量使:指并行工作的向量指令中的源向量或结果向量使用相同的用相同的R向向。例:例:V4V1+V2 V5V2V3 功能部件冲突功能部件冲突:指多条并行工作的向量指令:指多条并行工作的向量指令共用了同一共用了同一 个功能部个功能部件。件。例:例:V3V1+V2 V6V4+V5 理想情况,若有理想情况,若有m个部件并行工作,可使运行速度提高个部件并行工作,可使运行速度提高m倍,由倍,
24、由于实际程序并行度有限和可能发生上述冲突,因此,于实际程序并行度有限和可能发生上述冲突,因此,能完全工作的能完全工作的功能部件的总数总是功能部件的总数总是m。18例例 ADDV V1,V2,V3 MULTV V4,V1,V5例例 D=A(B+C)设向量长度设向量长度64,B和和C已由已由MMV0和和V1,则,则 LD V3,A ADDV V2,V0,V1 MULTV V4,V2,V3 而第三条指令而第三条指令与第一、二条指令均存在与第一、二条指令均存在先写后读先写后读的相关冲突,因的相关冲突,因而可将第三条指令与第一,二条指令链接执行而可将第三条指令与第一,二条指令链接执行 见图见图6.46.
25、4.2 链接技术链接技术 利用向量指令间存在的利用向量指令间存在的先写后读先写后读的数据相关性来加快指令序列执的数据相关性来加快指令序列执行速度的技术行速度的技术称为链接技术称为链接技术。19 采用采用并行和链接加速并行和链接加速技术,当被加工向量的长度为技术,当被加工向量的长度为N时,则执时,则执行时间:行时间:T=(1+6+1)+(1+7+1)+(N-1)=N+16拍拍加法和访存的延时乘法延时充满后连续流水结果数产生第1个结果的延时桌面3920 这三条指令这三条指令全部用串行方法全部用串行方法执行时则需要执行时则需要 T=(1+6+1)+N-1 2+(1+7+1)+N-1=3N+22拍拍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统 结构
限制150内