计算机系统结构

计算机系统结构演示文稿1现在是1页\一共有40页\编辑于星期二计算机系统结构2现在是2页\一共有40页\编辑于星期二6.1向量流水机的基本系统结构前面所介绍的标量流水机在实际应用中要使性能进一步提高，通常要受到以下两个因素的约束：⑴流水线的工作时钟不可能取得很短。⑵取指与译码的速率受到限制，即在一个时钟周期内最多只能启动一条指令，通常称为Flynn瓶颈。6.1.1向量流水处理的主要特点：⑴由于每一个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的，这就允许向量流水线有较深的深度。⑵一条向量流水指令相当于一个标量循环，从而可降低对指令访问带宽的要求，同时也消除了由循环转移起的控制相关。3现在是3页\一共有40页\编辑于星期二⑶若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中依次访问它们。由于一个向量中通常含有多个元素，因此对存储器访问的延迟平均到每个元素上其访存等待时间开销较小。由以上这些特点：⑴向量流水机对相同数量的数据项进行操作时，要比一串标量指令操作更快。⑵向量流水机还可使访存和有效地址计算流水化。⑶高档向量机还允许多个向量操作同时进行，从而可开发对不同元素进行多个向量操作的并行性。6.1.2向量机的基本系统结构向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分为R–R工作方式向量机和M–M工作方式向量机两大类。4现在是4页\一共有40页\编辑于星期二M–M方式是源向量来自于M，结果M。R–R方式是源向量来自于R，结果R。不管是哪一种计算机，其典型结构见P112图6.1设：Y=aX+Y其中X和Y为向量，初始值放在M•M中，a为标量。根椐表达式求解是单精度还是双精度操作，分别称为SAXPY或DAXPY循环，表示单或双精度的a乘以X后再加Y(这是一个常用循环。设向量长度为64，元素长度为8)。5现在是5页\一共有40页\编辑于星期二LDF0，a；标量a装入F0ADDIR4，Rx，#512；将向量元素的末地址装入R4中LOOP：LDF2，0(Rx)；取向量元素x(i)MULDF2，F0，F2；a与x(i)相乘LDF4，0(Ry)；取向量元素y(i)ADDDF4，F2，F4；ax(i)与y(i)相加SD0(Ry)，F4；存结果向量元素ADDIRx，Rx，#8；增量向量元素x下标ADDIRy，Ry，#8；增量向量元素y下标SUBR20，R4，Rx；R4-Rx→R20，计算是否到达限界值BNZR20，LOOP；若循环未结束，转LOOP

若用向量机来完成同样操作，则有：

LDF0，a；标量a装入F0LVV1，Rx；装入向量X，LV为向量取指令MULTVV2，F0，V1；向量X与标量a相乘LVV3，RY；装入向量YADDVV4，V2，V3；向量加aX+YSVRY，V4；存结果向量，SV为向量存指令循环体共有9条指令6现在是6页\一共有40页\编辑于星期二对两程序比较，可见①标量机共需要执行964+2=578条指令，而向量机仅有6条指令即可完成。②标量流水机中，流水线联锁(相关停顿)的频率远高于向量机，标量机中每一个元素都有ADD等待MUL及SD等待ADD的情况。而向量机每条指令只需停顿一次。6.1.3向量启动时间和启动率设有一条向量指令所需时间TVP为TVP=Tst+nIr(6.1)Tst：流水线启动时间；(包括流水线固有的延迟时间)以便设置为完成向量操作所需的相应参数(如向量长度等)。

n：向量长度；Ir：启动率。表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需的时间。

7现在是7页\一共有40页\编辑于星期二

对于R–R方式来说，流水线的启动时间主要取决于功能部件流水的深度。每个结果需要的钟周期数例：设一个向量乘法流水部件的启动时间为10个时钟周期，启动率Ir为1，则对于长度为64的向量乘法产生每个向量元素结果所需要的钟周期数为8现在是8页\一共有40页\编辑于星期二6.2向量操作长度控制和向量访问步长

向量寄存器型的向量机具有一个自然向量长度，即每个向量寄存器中的向量元素个数，例Cray-1机为64。但实际程序中的向量长度往往不会与此长度相等。一个具体的向量操作长度在编译时也常常是未知的，例如：

do10i=1，n10y(i)=ax(i)+y(i)

在向量长度寄存器中存放的长度值≤向量寄存器的长度(MVL)的向量均可放入向量寄存器。向量长度>向量寄存器长度时，就必须将向量长度按向量寄存器长度分段。分段后的向量长度即是每次向量操作的长度，必须≤向量寄存器长度。例子见P148中间程序。9现在是9页\一共有40页\编辑于星期二low=1VL=(nmodMVL)*找出零头长度值do20j=0，(n/MVL)*外循环do10i=low，low+VL-1*以长度VL操作V(i)=aX(i)+Y(i)*主要操作10continuelow=low+VL*下一向量的开始VL=MVL*将长度恢复成MVL20continue内循环例：有两个100100元素的矩阵A和B相乘的程序段如下：do10i=1，100

do10j=1，100C(i，j)=0.0

do10k=1，10010

C(i，j)=C(i，j)+A(i，k)B(k，j)10现在是10页\一共有40页\编辑于星期二向量由M•MR向，则在M•M中间隔存放的元素在R向中便成为逻辑上相连续的，如果向量机支持对向量的跨步访问，则称这种向量机为支持完全的一维数据显式访问。因为它能以行、列，甚至以对角线访问这些方向上的元素，Cray-1巨型机就是这种向量机。而M–M工作方式的Cyber–205巨型机中，则不支持这种完全一维数据显式访问，它只能以连续方式访存。如果要进行跨步访问运算，则必须先将这些在M•M中不连续存放的向量元素，先经过运算部件进行依次排序，然后再送入M•M使它们相邻连续存放，最后再从M•M中连续取出进行运算，显然这将大降低运算性能。

通常向量机，为了增加访存速率，大都采用低位地址多体交叉M•M，当向量机支持跨步长度访问时，就可能出现对同一存储体访问间隔时间<访存周期时间，若使得上一次对某一存储体的访问结束前，对同一存储体提出了新的访问要求，从而加剧访存冲突。4011现在是11页\一共有40页\编辑于星期二

例：设有16个存储体，访问时间为12个时钟周期，共要访问64个向量元素。

⑴对于步长为1的访问，除了第一次被访问的存储体需要12个周期外，以后每个存储体依次间隔1个周期就可进行一次访问，故共需要12+63=75个时钟周期。

⑵当步长为16的倍数时，由于每次对存储器访问将与前一次访问发生冲突时，因此，每一个元素的访问都需要12个周期，这样64个元素就需要6412=768个周期。

例：对于64个存储体，步长为32时，每隔一次访问(即两次访问后)就会发生一次冲突。步长为8时，每隔7次访问(即8次访问后)才会发生冲突。此外，增加存储体数目，通常也可减少产生访问冲突的频率。

☆为了使访存不发生冲突应设法使跨步和存储体数互为质数。

例：存储体数为17，而跨步长为16。

12现在是12页\一共有40页\编辑于星期二313现在是13页\一共有40页\编辑于星期二6.3向量处理方法例:D=A(B+C)的向量运算，A、D、C都是长度为n的向量。有下列三种加工方式。

⑴普遍采用的方法是按向量顺序计算的横向加工d1=a1(b1+c1)d2=a2(b2+c2)dn=an(bn+cn)这里每一步都要先进行bi+cik的运算，然后进行kaidi运算，这就要产生数据相关。

⑵另一种方法是垂直加工：①先进行纵向加工所有B和C中的元素的对应加法，即bi+ciki

②再进行纵向加工的乘法操作，即kiai

di14现在是14页\一共有40页\编辑于星期二此时向量指令表示形式变成K=B+CD=AK

由此可见，纵向加工具有较高的吞吐率，但需要一个中间向量K(具有k1kn共n个分量)，在M–M工作方式中都采用这种方式。

⑶称为纵横向加工(或称为分组加工)，以R–R工作方式的向量机均采用此加工方式。15现在是15页\一共有40页\编辑于星期二设N：向量长度

n：向量寄存器可表示的最大限度为，则N=kn+r

n≤N，r<n，k、n、r均为正整数。

k为组数，r为余数(余下的部分也作为一组处理)。

加工方式是：组内纵向加工，组间为横向加工。

第一组计算k1n

=b1n

+c1n

d1n

=a1nk1n

第二组计算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个中间向量寄存器单元k1n，Cray–1与一些小巨型机都采用这种加工方式。16现在是16页\一共有40页\编辑于星期二6.4增强向量处理性能的方法

共有4种改善向量机性能的方法。

⒈采用多功能部件，使它们并行工作。

⒉加快一串相关向量指令的操作速度。又称链接技术，首先在Cray-1巨型机上得到应用，目前的向量机都支持这种技术。

另外两种方法主要是为了增加以向量方式操作的循环类型。这两种方法在许多向量机上采用。6.4.1多功能部件的并行操作如Cray-1巨型机中，共有4组12个单功能流水部件，见P151图6.3。第一组为向量功能部件，有向量加，移，逻辑运算3个功能部件。17现在是17页\一共有40页\编辑于星期二第二组为浮点部件，FADD，FMUL，浮点倒数。第三组为标量功能部件，标量，逻辑运算移位数/计数4个部件。延时18现在是18页\一共有40页\编辑于星期二第四组为地址功能部件，地址加和地址乘。这些功能部件都是独立的，只要满足一定的约束条件，它们可以并行操作，约束条件是：

①不存在使用R向的冲突。

②不存在功能部件使用的冲突。

R向使用冲突：指并行工作的向量指令中的源向量或结果向量使用相同的R向。例：V4←V1+V2

V5←V2∧V3

功能部件冲突：指多条并行工作的向量指令共用了同一个功能部件。例：V3←V1+V2

V6←V4+V5

理想情况，若有m个部件并行工作，可使运行速度提高m倍，由于实际程序并行度有限和可能发生上述冲突，因此，能完全工作的功能部件的总数总是<m。19现在是19页\一共有40页\编辑于星期二例ADDVV1，V2，V3

MULTVV4，V1，V5例D=A(B+C)

设向量长度≤64，B和C已由M•M→V0和V1，则LDV3，A

ADDVV2，V0，V1

MULTVV4，V2，V3

而第三条指令与第一、二条指令均存在先写后读的相关冲突，因而可将第三条指令与第一，二条指令链接执行见图6.46.4.2链接技术

利用向量指令间存在的先写后读的数据相关性来加快指令序列执行速度的技术称为链接技术。20现在是20页\一共有40页\编辑于星期二

①采用并行和链接加速技术，当被加工向量的长度为N时，则执行时间：

T=(1+6+1)+(1+7+1)+(N-1)=N+16拍加法和访存的延时乘法延时充满后连续流水结果数产生第1个结果的延时桌面3921现在是21页\一共有40页\编辑于星期二②这三条指令全部用串行方法执行时则需要

T=[(1+6+1)+N-1]2+[(1+7+1)+N-1]=3N+22拍③前两条并行,第三条指令串行执行时需要

T=[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15拍☆要指出的是，当一条向量指令的两个源操作数分别是两条先行指令的结果R向时：①要求先行两条指令产生的运算结果的时间必须相等(即有关功能部件的延迟时间相等)。上例中访存和浮点加的延时均为6个时间单位。②还要求这两条向量指令的向量长度必须相等，否则就不可能链接。

可见并行加链接技术的加速效率还是较高的。要实现链接，除了前述条件之外，还有时间上的要求，即：只有当前一条指令的第一结果分量R向的那一个时钟周期可链接，错过该时刻，就无法进行链接，只有等前一向量指令全部执行完毕，释放R向资源后，才能执行后面指令。

22现在是22页\一共有40页\编辑于星期二针对不同的向量机，可能还有其他特殊的限制。

例Cray-1中允许自存储器取数操作参与链接，但不允许向存储器写数操作实现链接，因为Cray-1并不提供这种链接功能。6.4.3条件执行语句和稀疏矩阵和加速处理方法

⒈加快条件语句执行程序中如有条件执行语句或进行稀疏矩阵运算时，通常会使向量处理的优点不能充分发挥。

例:do100i=1，nif(A(i).ne.0)thenA(i)=A(i)–B(i)endif100continue

若采用向量屏蔽控制技术，使减法在只有当A(i)≠0时才执行，就可使上述循循环向量化。☆其关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元素参加运算。23现在是23页\一共有40页\编辑于星期二屏蔽向量是通过测试得到的。上例中是对A(i)=0否进行测试。

若A(i)=0，屏蔽向量的相应位Z“0”；

A(i)0，屏蔽向量的相应位Z“1”；

清零时，VM所有位Z“1”，此时后所有向量指令将对所有向量元素进行操作。下面给出上述循环的代码，设向量A和B的起始地址放在Ra和Rb中。

LVV1，Ra；将向量A装入V1LVV2，Rb；将向量B装入V2

LDF0，#0；将浮点0装入F0

SENSVF0，V1；若V1(i)≠F0，则将VMi置为1

SUBVV1，V1，V2；在屏蔽向量控制下进行减法操作CVM；将屏蔽向量寄存器置为全1SVRa，V1；将结果存入A24现在是24页\一共有40页\编辑于星期二指令序列中，SEMSV指令为屏蔽向量生成指令；

CVM为屏蔽向量寄存器Z“1”指令。屏蔽向量寄存器控制向量指令执行方法的缺点是：⑴执行时间没有减少⑵在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而相应的向量操作实际仍是进行，这会导至某些向量操作产生错误。

例：ifA(i)0thenB(i)=B(i)/A(i)在A(i)=0时，仅仅禁止运算结果B(i)/A(i)B(i)，但没有禁止B(i)/A(i)运算的进行，这就导致除数为0的非法运算。

比较好的方案是：根椐禁止向量，既禁止将结果写入目的寄存器，也禁止该操作执行。

⒉加快稀疏矩阵执行速度例：

例：有一个典型的稀疏矩阵运算，常见如下代码段：do100i=1，n100A(K(i))=A(K(i))+C(M(i))25现在是25页\一共有40页\编辑于星期二指标向量K和M指明A和C中的非零元素，此时要求A和C中必须有相同的非零元素个数。

除了指标向量外，也可用位向量来指明非零元素。

支持稀疏矩阵运算的基本结构是——指标向量的散射—聚合操作(Scatter—gather)。①聚合操作：是概据指标向量内容选取元素，它们的地址=基址+指标向量中给定的相应地址偏移量获得，聚合操作后存于目的向量寄存器中的结果已成为稠密向量。②散射操作：借助同一指标向量将稠密向量还原成稀疏向量。6.4.4向量归约操作的加速方法

归约(Reduction)操作是递推(Recurrence)操作中的一个特殊例子。归约操作一般难以向量化。

例：26现在是26页\一共有40页\编辑于星期二对于上述的第二部分递推循环，可用递归方法写出如下代码：len=32do100j=1，6do200i=1，len200dot(i)=dot(i)+dot(i+len)len=len/2100continuedot=0.0do10i=1，6410dot=dot+A(i)B(i)do10i=1，6410dot(i)=A(i)B(i)应用向量乘法做MULTVdot(1:64)=A(1:64)B(1:64)dot1=0.0do20i=1，6420dot1=dot1+dot(i)递推部分3727现在是27页\一共有40页\编辑于星期二6.5向量处理性能的评估参数和方法在向量流水功能部件上执行一个长度为n的向量操作时间Tvp可用以下公式表示：Tvp=Ts+T1+(n-1)

Tc=T0

+n

Tc

(6.2)

Ts：建立流水线的时间。

T1：为第一对向量元素通过流水线时间。

Tc：流水线时钟周期。T0

=Ts+T1-Tc

上式也可用下式表示：Tvp=sTc+lTc+(n-1)

Tc=(s+l+n-1)

Tc

(6.3)

s：建立流水线所需时钟周期数

l：完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。显然在上述流水线中，每对向量元素的平均执行时间是：28现在是28页\一共有40页\编辑于星期二为了表达n1/2的含义，可将Tvp改成Tvp=(n1/2+n)

Tc

=(n1/2+n)/R∞(6.4)由(6.2)和(6.4)两式可知Tvp=T0+n

Tc

=(n1/2+n)

Tc所以

n1/2=

T0/

Tc由(6.3)和(6.4)两式可知(n1/2+n)

Tc

=(s+l+n-1)

Tc所以

n1/2=

s+l-1因此n1/2=

T0/

Tc=

s+l-1对于串行方式工作的标量处理机，完成同样的向量操作所需时间Tsp为Tsp=Ts1+nlTcs

=(s1+nl)/Rcs

(6.5)

Ts1：标量循环建立时间。

Tcs：标量部件工作的时钟周期。

R∞：当向量长度→∞时，向量流水处理的渐近性能。

为了衡量向量流水线中的操作有效性，通常用半性能长度n1/2这一参数。

n1/2：指为了达到向量流水线最大性能值一半时所需要的向量长度。

29现在是29页\一共有40页\编辑于星期二对于n个元素对，它的平均执行时间图6.5给出了串行和向量流水两种操作方式的向量处理时间、处理速率与向量长度的关系。3130现在是30页\一共有40页\编辑于星期二在评估向量流水机性能时，除了执行时间性外，向量长度是一个很重要的参数。较常用的与向量长度有关的评价流水机性能的参数有三个：⑴R∞：当向量长度→∞时，向量流水的渐近性能常在评价峰值时用，单位为MFLOPS。⑵n1/2：为达到一半R∞值时所需的向量长度。是评价向量流水线建立时间对性能影响的参数。它表示为建立流水线而导至操作损失。★若n=n1/2，表明整个向量流水线处理时间中，只有一半是有效的操作。通常希望向量流水线有较小的n1/2

。

例：Cray-1向量机的n1/2=1020Cyber-205向量机的n1/2=100表明Cray-1流水线建立时间比Cyber-205要小得多。⑶nv：表示向量流水方式的工作速度优于标量串行工作方式时，所需的向量长度临界值。31现在是31页\一共有40页\编辑于星期二见P157图6.5(a)中的nv值=5。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。32现在是32页\一共有40页\编辑于星期二6.6并行向量处理技术并行向量处理机的通用体系结构如图6.6所示图6.6并行向量处理机的体系结构框图

并行向量处理机的主要特点是：向量处理部件数量不多，但有很高的处理性能；互连网络有很高的带宽和低的时延；采用大量的向量寄存器，而不使用Cache；向量部件和互连网络均是定制的，价格昂贵；向量化编程较容易。

33现在是33页\一共有40页\编辑于星期二EarthSimulator并行向量处理机由640个结点处理器组成，每个结点中含有以下部件：8个向量处理器(称为AP，算术处理器)，每个峰值性能为8Gflop/s；1个16GB的共享存储器；1个远程访问控制部件(RCU)；1个I/O处理器。每个向量处理器由以下部件组成：1个向量部件(内含8套，每套有6个向量流水线，包括装载/存储、逻辑、加/移位、乘法、除法以及屏蔽)、72个(256位)向量寄存器以及17个(256位)屏蔽寄存器；1个4路(每个周期可发射4条指令)超标量处理器，配备有128个标量寄存器以及存储容量均为64KB的I-Cache和D—Cache；1个存储器访问控制部件。该向量处理器的结构如图6.7所示。

设计并行向量处理机应遵循的要点是：使向量和标量处理的性能尽可能平衡；存储器系统应有足够的数据带宽；互连网络应有高的带宽和低的时延；应有良好的处理器规模可扩展性。3634现在是34页\一共有40页\编辑于星期二图6．7EarthSimulator的结点机结构

35现在是35页\一共有40页\编辑于星期二在EarthSimulator中，每个结点中含有32个主存部件，每个存储部件由64个存储体组成，总的存储容量为16GBps。向量处理器与存储部件间的数据传送速率为32GBps，因此一个结点机的总吞吐率为256GBps。为了使互连网络具有高带宽和低时延，EarthSimulator在结点内采用带宽为256GBps的单级纵横交叉开关，将8个AP、1个RCU、1个I/O部件与32个MMU(存储器部件)互连起来。640个结点之间用212.3GBps带宽的640640纵横交叉开关互连。

EarthSimulator并行向量处理机系统的峰值性能为40.96T(1T