第四章 向量处理机 银河-I巨型计算机 银河-II巨型计算机

Presentation on theme: "第四章 向量处理机 银河-I巨型计算机 银河-II巨型计算机"— Presentation transcript:

1 第四章 向量处理机 银河-I巨型计算机 银河-II巨型计算机
2000年由1024个CPU组成的银河Ⅳ超级计算机系统峰值性能达到每秒1.0647万亿次浮点运算 2010年天河一号（二期系统）：2570万亿次浮点运算

2 第四章 向量处理机 一.标量处理与向量处理 一个既有大小又有方向的量称为向量。 如果有下面的一个向量运算，其中A和B都是N×N的矩阵：

3 第四章 向量处理机 要求计算: C=A×B

4 第四章 向量处理机 在标量计算机中，我们可以很容易的编出一段循环程序，进行这个矩阵乘法运算，比如一段用FORTRAN语言编的程序段为：
DO 100 I = 1, N DO 100 J = 1, N C(I,J) = 0.0 DO 100 K = 1, N C(I,J) = C(I,J) + A(I,K) * B(K,J) 100 CONTINUE

5 如果将这段程序编译成一个假想的汇编程序表示，就成了一个三重循环的汇编程序：
INITIALIZE I=1, J=1, K=1 10 CLR C(I,J) LOAD A(I,K) LOAD B(K,J) MUL A(I,K), B(K,J) ADD C(I,J), A(I,K) // C(I,J)←C(I,J) + A(I,K)×B(K,J) INC K // K←K+1 IF K≤N GOTO 20 STORE C(I,J) INC J // J←J+1 IF J≤N GOTO 10 INC I // I←I+1 IF I≤N GOTO 10 HALT 对一个操 作数进行 操作 对一对操 作数进行 操作

6 上述操作如果由向量计算机来完成，其可能的程序如下所示：
DO 100 I=1,N C(I,J) = 0.0 (J = 1:N) DO 100 K=1,N C(I,J) = C(I,J) + A(I,K) * B(K,J) (J=1:N) 100 CONTINUE 从形式上看，这两段程序差不多，但是在向量计算机上，不管是单元清零，还是做乘法和加法，一条语句处理的都是N个（或N对）数据，而不是一个或一对。

7 第四章 向量处理机 要求计算: C=A×B

8 第四章 向量处理机 二.向量处理机的概念与特点 1．向量处理机
把向量数据表示与流水线结合起来，就构成了向量流水处理机，简称为向量流水机或向量处理机。 向量处理机的处理对象是向量元素。

9 第四章 向量处理机 2．向量流水处理的特点 1）在向量机中，一条向量指令往往针对的是一个向量，因此一条向量指令相当于一个标量循环。
2）在向量运算中，每一个结果元素仅与参加运算的元素有关，与上一次运算的值无关。 3）若向量指令所要访问的向量元素相邻，则可以将其存储到多体交叉存储器中。 4）一般向量机中，允许访问存储器与有效地址的计算流水化，在高档向量机中还允许多个向量操作同时进行，即多向量并行操作。

10 第四章 向量处理机 三．向量处理的几种方式 向量处理的对象是一些数组，在实际处理时，可以由编译程序选择不同的处理方式。
假定有一个向量运算，其程序表示如下： DO i = 1,N,1 100 Fi = Ai² ＊B + Di ＊ ( Ai² - Ei ) 按照处理元素的排列次序，可以把处理方式分为三种。 ⑴ 横向处理方式 ⑵ 纵向处理方式 ⑶ 纵横处理方式

11 Fi = Ai² * B + Di * ( Ai² - Ei )
DO i = 1,N,1 100 Fi = Ai² ＊ B + Di ＊ ( Ai² - Ei ) ⑴ 横向处理方式 先取i=1的各数组元素,计算出F1的值,再依次算出Fi的值。 ⑵ 纵向处理方式 Fi = Ai² * B + Di * ( Ai² - Ei ) 求出整个A²的值，作为第一个运算单元 第二个运算单元 第三个运算单元 ⑶ 纵横处理方式 将被处理的数组分割为比较小的数组，在这个较小的数组中进行纵向处理，然后在各小数组处理的基础上进行横向处理。

12 第四章 向量处理机 四.向量处理机的结构 1. 向量处理机的基本结构 包括： 标量流水部件：标量功能部件、若干标量寄存器
向量流水部件：向量功能部件、向量存取部件、向量寄存器、向量控制器等 2. 向量处理机的类型 存储器-存储器型 寄存器-寄存器型

13 第四章 向量处理机 存储器-存储器结构 功能流水线 存储系统 译码器 指令 数据A 数据B 数据C 向量处理机基本结构框图

14 第四章 向量处理机 在数据通道中加入可变长度的延迟电路方案框图 指令 指 令 译 码 向量控制 功能选择 地址形成器 延迟选择 可变延迟器
存储器系统 地址形成器 功能选择 向量控制 指令 指 令 译 码 延迟选择 可变延迟器 功能处理流水线 C = AΔB A B

15 第四章 向量处理机 由8个存储器模块组成存储系统的向量处理机 A B C A0 A1 A2 A3 A4 A5 A6 A7 B0 B1 B2
M0 M1 M2 M3 M4 M5 M6 M7 B C = AΔB 运算器 流水线结构

16 假定A和B向量都只有8个元素，运算结果C向量也有8个元素。这个向量处理机的工作过程可以用下图表示。
存储器-存储器结构向量处理机的一种工作时空图 P4 P3 P2 P1 M7 M6 M5 M4 M3 M2 M1 M0 1 2 3 4 5 6 7 RA7 RB7 W7 RA6 RB6 W6 RA5 RB5 W5 RA4 RB4 W4 RA3 RB3 R B3 W3 RA2 RB2 W2 RA1 RB1 W1 RA0 RB0 W0 8 9 10 11 12 13 14 15 16 17

17 第四章 向量处理机 A B C A0 A1 A2 A3 A4 A5 A6 A7 B6 B7 B0 B1 B2 B3 B4 B5 C4 C5
M0 M1 M2 M3 M4 M5 M6 M7 B C = AΔB 运算器 流水线结构 由8个存储器模块组成存储系统的向量处理机

18 改变向量存储方法后可以得到如下的时空图：
P4 P3 P2 P1 M7 M6 M5 M4 M3 M2 M1 M0 1 2 3 4 5 6 7 8 9 10 11 12 13 改变向量存储方法后的处理机时序图 RB5 RA7 W3 RB4 RA6 W2 RB3 RA5 W1 RB2 RA4 W0 RB1 RA3 RB0 RA2 W6 RA1 RB7 W5 RA0 RB6 W4 W7

19 第四章 向量处理机 寄存器-寄存器结构 以CRAY-1机为例 美国CRAY公司 1976年 每秒1亿次浮点运算 时钟周期：12.5 ns
1）功能部件 共有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。

20 第四章 向量处理机

21 第四章 向量处理机 6个单功能流水部件：进行向量运算 整数加（3拍） 逻辑运算（2拍） 移位（4拍） 浮点加（6拍） 浮点乘（7拍）
浮点迭代求倒数（14拍） 括号中的数字为其流水经过的时间，每拍为一个时钟周期，即12.5 ns。

22 第四章 向量处理机 2）向量寄存组V 由512个64位的寄存器组成，分成8块。 编号：V0～V7
每一个块称为一个向量寄存器，可存放一个长度（即元素个数）不超过64的向量。 每个向量寄存器可以每拍向功能部件提供一个数据元素，或者每拍接收一个从功能部件来的结果元素。

23 第四章 向量处理机 3）标量寄存器S和快速暂存器T 4）向量屏蔽寄存器VM 标量寄存器有8个：S0～S7 64位
64位，每一位对应于向量寄存器的一个单元。 作用：用于向量的归并、压缩、还原和测试操作、对向量某些元素的单独运算等。

24 第四章 向量处理机 2.CRAY-1向量处理的显著特点 1）每个向量寄存器Vi都有连到6个向量功能部件的单独总线。
2）每个向量功能部件也都有把运算结果送回向量寄存器组的总线。 3）只要不出现Vi冲突和功能部件冲突，各Vi之间和各功能部件之间都能并行工作，大大加快了向量指令的处理。

25 第四章 向量处理机 Vi冲突：并行工作的各向量指令的源向量或结果向量使用了相同的Vi。 例如：源向量相同 V3←V1＋V2 V5←V4∧V1
功能部件冲突：并行工作的各向量指令要使用同一个功能部件。 例如：都需使用乘法功能部件 V3←V1×V2 V5←V4×V6

26 3.CRAY-1向量指令类型 1）Vk ← Vi op Vj ）Vk ← Si op Vj 3）Vk ← 主存 ） 主存 ← Vi

27 第四章 向量处理机 五.提高向量处理机性能的方法 主要有： 设置多个功能部件，使它们并行工作。 采用链接技术，加快一串向量指令的执行。
采用循环开采技术，加快循环的处理。 采用多处理机系统，进一步提高性能。

28 第四章 向量处理机 1、设置多个功能部件 设置多个独立的功能部件。这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线。 例如：CRAY-1向量处理机有4组12个单功能流水部件： 向量部件：向量加，移位，逻辑运算 浮点部件：浮点加，浮点乘，浮点求倒数 标量部件：标量加，移位，逻辑运算， 数“1”/计数 地址运算部件：整数加，整数乘

29 第四章 向量处理机 2. 向量链接技术 所谓“链接”就是将相关两条流水线对向量的处理进行前后衔接的技术。
比如，有下面的一段程序： ADDV V1，V2，V3 ； V1 ← V2 + V3 MULTV V4，V1，V5 ； V4 ← V1 × V5 两条指令存在先写后读数据相关。若向量寄存器V1能在同一时钟周期内既能接收加法运算的结果，又能把这一结果作为下一条指令的源操作数传送给乘法运算功能部件，那么就能使两个功能部件链接起来工作。

30 假定，一个程序段有以下三个向量操作： V3 ← A V2 ← V0 + V1 V4 ← V2 * V3 存储器 A B C V0 V1 V2
5 6 访存口 浮点加 7 D V4 浮点乘

31 假设：把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要一拍时间，从存储器中把数据送入访存功能部件需要一拍时间。
3. 第1、2条向量指令并行执行，并与第3条指令链接执行。 从访存开始到把第一个结果元素存入V4所需的拍数（亦称为链接流水线的建立时间）为： [（1＋6＋1）] ＋[（1＋7＋1）] = 17 （拍） 3条指令的执行时间为： [（1＋6＋1）]＋ [（1＋7＋1）] ＋（N－1） = N＋16 （拍） 2. 前两条指令并行执行，然后再串行执行第3条指令，则执行时间为： [（1＋6＋1）＋N－1]＋[（1＋7＋1）＋N－1] = 2N ＋15 （拍） 1. 3条指令全部用串行方法执行，则执行时间为： [（1＋6＋1）＋N－1]＋[（1＋6＋1）＋N－1] ＋[（1＋7＋1）＋N－1] = 3N ＋22 （拍） 存储器 A B C V0 V1 V2 V3 1 2 3 4 5 6 访存口 浮点加 7 D V4 浮点乘 V3 ← A V2 ← V0 + V1 V4 ← V2 * V3

32 进行向量链接的要求 保证：无向量寄存器使用冲突和无功能部件使用冲突 1）前一条指令的结果是后一条指令的输入。
2）当一条向量指令的两个源操作数分别是两条先行指令的结果时，要求先行的两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等。 3）要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接。 4）只有在前一条指令的第一个结果元素送入到结果向量寄存器的那一个时钟周期才可以进行链接。

33 第四章 向量处理机 例. 以下两条向量指令只能串行执行的是（ ） A. V1 ←存储器 B. V2 ← V0+V1
V3 ← V1+V2  V5 ← V3*V4 C. V2 ← V0+V1      D. V2 ← V0+V1   V5 ← V3+V4       V5 ← V2*V3 答案：C

34 第四章 向量处理机 3. 分段开采技术 如果向量的长度大于向量寄存器的长度，该如何处理呢？ 当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。这种技术称为分段开采技术。 例.设A和B是长度为N的向量，考虑在Cray-1向量处理器上实现以下的循环操作： DO 10 I = 1，N 10 A（I）= 5.0 * B（I） + 1.0

35 5.0 * B（I） + 1.0 当N ≤64时，可以用以下指令序列： 当N >64时，就需要进行分段开采。 循环次数K ： 余数L：
S1 ← 5.0 ；将常数5.0送入标量寄存器S1 S2 ← 1.0 ；将常数1.0送入标量寄存器S2 VL ← N ；在向量长度寄存器VL中设置向量长度N V0 ← B ；从存储器中将向量B读入向量寄存器V0 V1 ← S1 × V0 ；向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2相加 A ← V2 ；将计算结果从向量寄存器V2存入存储器的向量A 当N >64时，就需要进行分段开采。 循环次数K ： 余数L：

36 第四章 向量处理机 S1 ← 5.0 ；将常数5.0送入标量寄存器S1 S2 ← 1.0 ；将常数1.0送入标量寄存器S2
VL ← L ；在向量长度寄存器VL中设置向量长度L V0 ← B ；从存储器中将向量B[0..L-1]读入向量 ； 寄存器V0 V1 ← S1 * V0 ；向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2相加 A ← V ；将计算结果从向量寄存器V2存入存储器 ；的向量A[0..L-1] 处理余 数部分, 计算L 个元素

37 第四章 向量处理机 For (I=0 to K-1) { V0 ← B ；从存储器中将向量B[L+I*64..L+I*64+63]
V1 ← S1 * V0 ；向量B中的每个元素分别和常数S1 ；相乘； V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2 ；相加 A ← V ；将计算结果V2存入存储器的向量 ； A[L+I*64… L+I*64+63] } 循环 K次, 分段 处理

38 第四章 向量处理机 4. 采用多处理机系统 许多新型向量处理机系统采用了多处理机系统结构。例如： CRAY-2 包含了4个向量处理机
浮点运算速度最高可达1800MFLOPS CRAY Y-MP、C90 最多可包含16个向量处理机

39 第四章 向量处理机 六. 向量处理机的性能评价 在向量处理机中, 衡量向量处理机性能的指标主要有： 向量指令的处理时间Tvp
机器向量长度为无穷大时的向量处理机的峰值性能R∞ 半性能向量长度n1/2 向量长度临界值nv

40 第四章 向量处理机 向量指令的处理时间Tvp （1）假定指令是预取的，那么一条向量指令的执行时间将由三部分组成，如下图所示: 其中，
n 建立段 第1个元素 通过流水线 2 Ts Tvf (n-1)Tc 其中， 建立段Ts是为向量指令的执行进行准备的阶段。 第二段Tvf是使被处理的向量中第一个（对）元素通过流水线所花费的时间。 第三段是所有后续元素通过流水线所花费的时间，Tc为流水线“瓶颈”段的执行时间。

41 得到向量指令执行时间: 通常，在数字计算机中，所有的操作时间都应是时钟周期的整数倍，而且也不会在流水线中存在“瓶颈”，假定基本时钟周期为TClk，上式可以写成: 式中的s和e表示前两段时间是时钟周期的多少倍，即需要多少个时钟周期。 上式也可以写成: 式中Tstart表示向量功能部件启动所需的时钟周期数，n为向量元素的个数。

42 第四章 向量处理机 （2） 一组向量指令及其编队运行
一组向量指令的执行时间并不是每条指令执行时间的简单相加，而必须根据具体处理机作具体分析。 影响一组向量指令运行时间要素是：向量中元素的个数；组织编队的情况。 将能够组合在一起在一个时钟周期内一起开始执行的向量指令集合称为一个“编队”。

43 例1.下面是一组向量指令，假定每种指令都有一个功能流水线，它们可分成几个编队？
LV V1，RX ；从存储器取向量X到V1 MULTSV V2，S0，V1 ；标量S0乘向量V1，存入V2 LV V3，RY ；从存储器取向量Y到V3 ADDV V4，V2，V3 ；向量V2加上向量V3，存入V4 SV RY，V ；向量V4保存到RY中 解：按照原指令的排列次序对指令进行分析。由于第二条指令的执行依赖第一条指令的执行结果，这两条指令之间存在数据相关，不能成为一个编队。第一条指令与第三条指令之间没有数据相关，但是发生了功能部件冲突，不可能同时执行，所以也不允许乱序执行。后面的两条指令必须利用前几条指令的运行结果，都不可能与其他指令组成编队。 MULTSV V2，S0，V1 LV V3，RY

44 于是，这组指令的编队如下： LV V1，RX ；第一编队 MULTSV V2，S0，V LV V3，RY ；第二编队（惟一没有数据相关和部件冲突的两条指令） ADDV V4，V2，V ；第三编队 SV RY，V ；第四编队

45 实际程序段的执行时间还有两个因素必须考虑： 其一是标量代码部分的运行时间，表示为： Tloop
将一个编队计算一个元素的时间定义为基准时间Tchime，其值完全取决于处理机的结构，与向量中元素的个数无关。如果一段程序有m个编队，而向量长度为n时，完成这些向量元素的处理所花的时间为：mnTchime。 实际程序段的执行时间还有两个因素必须考虑： 其一是标量代码部分的运行时间，表示为： Tloop 其二是组织起向量流水线的时间，是各编队流水线启动开销之和,表示为：Tstart。 在计算程序段的执行时间中还必须考虑向量长度的影响。由此可得一段程序的执行时间为： 寄存器长度

46 例2.在某向量处理机上执行DAXPY的向量指令序列，也即计算双精度浮点向量表达式。
Y = α× X +Y 其中X和Y是双精度浮点向量，最初保存在外部存储器中，α是一个双精度浮点常数，已存放在浮点寄存器F0中。计算该表达式的向量指令序列如下： LV V1，Rx MULTFV V2，F0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4

47 假设： Tchime=1, Tloop＝15，向量寄存器长度MVL=64 ，各功能部件的启动时间为： 1）向量存储部件的启动：12个时钟周期
2）向量乘法部件的启动：7个时钟周期 3）向量加法部件的启动：6个时钟周期 分别计算在不采用链接技术和采用链接技术下完成上述操作的总的时间。 解：（1）不采用链接技术时，可以进行如下编队： 第一编队：LV V1，Rx； 第二编队：MULTFV V2，F0，V1；LV V3，Ry； 第三编队：ADDV V4，V2，V3； 第四编队：SV Ry，V4。 所以，Tstart＝ ，m = 4 LV V1，Rx MULTFV V2，F0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4

48

49 （2）若采用链接技术时，可以进行如下编队：
LV V1，Rx MULTFV V2，F0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4 （2）若采用链接技术时，可以进行如下编队： 第一编队：LV V1，Rx； MULTFV V2，F0，V1 ； 第二编队：LV V3，Ry； ADDV V4，V2，V3； 第三编队：SV Ry，V4。 所以，Tstart＝ ，m = 3

50 例3.有一台向量处理机，其寄存器的长度（MVL）为64个字，如果各功能流水线的启动时间与上题相同。假定Tloop为一个固定值15，Tchime近似等于1，向量长度为200。请计算为实现算式：A = B × s的运算需要花费的时间。 解：为完成这项运算，可以编译成以下三条向量指令： LOADV V1，RB ；取向量B MULTSV V2，V1，Fs；向量B乘上标量s，存入V2 STOREV RA，V2 ；存成向量A 由于这三条指令之间存在数据相关，若不采用链接，只能作为三个编队处理，即m = 3。200个向量元素应分为4组进行计算，而且每组都必须加入Tloop和Tstart。

51 所以全部执行时间为： T200 = 4×（15 + Tstart）+ 3×200×1 = Tstart Tstart是三条向量指令的启动时间之和，即： = 31个时钟周期。 T200 = 784个时钟周期。 若采用链接技术，结果如何？

52 第四章 向量处理机 2. 向量处理机的峰值性能R∞ R ∞表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。
单位为：MFLOPS

53 例. 对于上述例题2中向量指令序列中的操作而言，只有“MULTFV V2,F0,V1”和“ADDV V4,V2,V3”两条浮点操作向量指令。假设该向量处理机的时钟频率为200 MHz，那么：

54 第四章 向量处理机 3. 半性能向量长度n1/2 指向量处理机的运行性能达到其峰值性能的一半时所必须满足的向量长度。
是评价向量流水线的建立时间对性能影响的重要参数。 对于上面的例子: 由于该向量处理机的峰值性能R∞＝100 MFLOPS， 所以根据半性能向量长度的定义有：

55 第四章 向量处理机 2×n1/2 ×200 ＝ 50 n1/2 ×64＋3n1/2 64 假设 ≤64，那么有： n1/2
假设 ≤64，那么有： n1/2 64＋3n1/2 ＝ 2×n1/2 ×200 50 ＝ 8n1/2 5n1/2 ＝ 64，n1/2 ＝12.8 n1/2 ＝ 13

56 第四章 向量处理机 4. 向量长度临界值 nv 指对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。
对于上述DAXPY的例子 假设nv ＜64，在标量串行工作方式下实现DAXPY循环的开销为10个时钟周期。 1）那么在标量串行方式下，计算DAXPY循环所需要的时钟周期数为： Ts =( 10＋12＋12＋7＋6＋12 )×nv = 59nv

57 第四章 向量处理机 Tv = 64＋3nv 2）在向量方式下，计算DAXPY循环所需要的时钟周期数为： 根据向量长度临界值的定义，有：
Tv = Ts 64＋3nv = 59nv = 64 56 = 2 nv

58 复习： 1. 在向量机中，利用向量指令间存在的数据相关性来加快向量指令序列执行速度的技术称为 。
1. 在向量机中，利用向量指令间存在的数据相关性来加快向量指令序列执行速度的技术称为 。 2．有关半性能向量长度，下面哪种说法正确？（ ） A.该值是最大性能的一半 B.该值越大说明向量计算机性能越好 C.该值是为达到一半最大性能所需要的向量长度 D.该值必须是整数，计算的时候应该向下取整

59 答案： 1. 链接 2. C

60 课后作业 1. 在CRAY-1机上，V为向量寄存器，设向量长度均为32，s为标量寄存器，所用浮点功能执行部件的执行时间分别为；加法~6拍；乘法~7拍；从存储器读数~6拍；求倒数近似值~14拍；打入寄存器及启动功能部件各~1拍。试分析下列各组指令，说明各指令之间的关系（顺序、链接或并行？）（注：CRAY-1规定：不允许存储器写操作参与链接） （1）V0 ←存储器 （2）V2 ←V0*V1 V1 ←V2+V V3 ← 存储器 V4 ←V5*V V4 ←V2+V3

61 课后作业 （3）V0 ←存储器 （4）V0 ← 存储器 V3 ←V1+V2 V1 ←1/V0 V4 ←V0*V3 V3 ←V1+V2
V4 ← V5 *V s0 ← s2+s3 s0 ← s1+s V3 ← V1 *V4 （7）V3 ←存储器 （8） V0 ←存储器 V2 ← V0+V V2 ← V0+V1 V4 ← V2 *V V3 ← V2 *V1 存储器← V V5 ← V3 *V4