《向量流水处理机》PPT课件.ppt

第十四讲向量流水处理机 计算机系统结构 2 向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法 3 向量处理的基本概念 从数学的概念上讲 标量是指单个量 而向量是指一组标量 例如 有一个数组A a1 a2 a3 an 其中括号内的每一个元素ai就是一个标量 而A称为向量 它由一组标量组成 一条向量指令可以处理N个或N对操作数 我们把这N个互相独立的数叫做向量 对这样一组数的运算叫做向量处理 因此 向量指令的处理效率要比标量指令的处理效率高得多 4 向量处理方式 有三种处理方式 横向处理方式 又称为水平处理方式 横向加工方式等 向量计算是按行的方式从左至右横向地进行 纵向处理方式 又称为垂直处理方式 纵向加工方式等 向量计算是按列的方式自上而下纵向地进行 纵横处理方式 又称为分组处理方式 纵横向加工方式等 横向处理和纵向处理相结合的方式 要根据向量运算的特点和向量处理机的类型选择向量的处理方式 5 向量处理方式 例如 向量计算 A B C 的循环程序用C语言为for i 1 i n i di ai bi ci 水平处理法 横向 d1 a1 b1 c1 d2 a2 b2 c2 dn an bn cn 6 水平处理法 假设中间结果为t i 计算第1个分量 t 1 b 1 c 1 d 1 a 1 t 1 计算第2个分量 T 2 b 2 c 2 d 2 a 2 t 2 计算第N个分量 t N b N c N d N a N t N 当采用流水方式计算时 在每个向量加乘运算中都会发生数据相关 而且当使用静态流水线时 还要进行2次乘和加功能的转移 这样共出现N次相关 2N次功能转换 因此 横向处理方法不适合于向量流水处理 7 纵向处理法 向量计算是按列的方式自上而下纵向地进行 即先是所有B和C向量元素对的相加运算 中间结果暂存到k1 kN中 然后再纵向加工所有对应元素的乘法运算 b1 c1 b2 c2 bN cN 8 纵向处理法 用向量指令形式来表示 则变成 K B CD K A只需要两条指令就能实现VADDB C KVMULK A D显然 当采用流水方式计算时 数据相关在两条向量指令间仅有1次 而流水线加 乘功能的切换只需1次 因此 纵向处理方法可获得较高的吞吐率 适合于在向量处理机中应用 9 纵横处理法 当向量长度N大于向量寄存器长度n时 需要分组处理 分成k组 组内采用纵向处理方式 组间采用横向处理方式 分组方法 n k m r其中 m为每组长度 r为第k 1组剩余分量Bi Ci Ki 1到m Ki Ai Di 1到m Bi Ci Ki m 1到2m Ki Ai Di m 1到2m 10 纵横处理法 每组用两条向量指令 每组发生相关两次 其中组内发生数据相关一次 组间切换时发生相关一次 主要优点 减少访问主存储器的次数例如 中间变量K不写入主存储器 11 向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法 12 基本结构 主存 标量寄存器 标量功能部件 向量功能部件 向量寄存器 向量缓冲器 向量指令控制部件 向量存取部件 指令处理部件 向量功能部件 向量功能部件 控制部分 控制部件和缓冲部件 中间REG 标量流水 功能部件和标量寄存器 S 向量流水 功能 存取部件和寄存器 V VM VL 向量流水处理机的结构 13 向量流水处理机的结构 按向量元素和结果存放分M M和R R两类 存储器 存储器结构多个独立的存储器模块并行工作处理机结构简单对存储系统的访问速度要求很高寄存器 寄存器结构运算通过向量寄存器进行需要大量高速寄存器对存储系统访问速度的要求降低 14 存储器 存储器结构 向量处理机的基本思想是把两个向量的对应分量进行计算 产生一个结果向量 参加运算的向量数据在存储器中 运算的结果也送到存储器中 其结构与数据流的示意图如下图所示 如果以向量加法为例子 C A B 一种能实现两个向量相加的流水结构的加法器 15 多模块存储器系统的向量处理机 16 向量计算C A B的时空图 假设一个存取周期等于两个时钟周期 并假设向量A B C各有8个 那么理想实现C A B向量计算的时空图如图所示 为了不发生读写冲突 各向量元素在存储模块中的位置是有意安排的 由于运算流水线分为4段 因此输入数据进入流水线4个时钟周期之后才能产生相应的输出值 当数据充满后 流水线就一直处于忙碌状态 17 功能部件4功能部件3功能部件2功能部件1存储体M8存储体M7存储体M6存储体M5存储体M4存储体M3存储体M2存储体M1 0123456789101112131415t 12345678 12345678 12345678 12345678 RB6RB6RA8RA8WC4WC4 RB5RB5RA7RA7WC3WC3 RB4RB4RA6RA6WC2WC2 RB3RB3RA5RA5WC1WC1 RB2RB2RA4RA4 RB1RB1RA3RA3 RA2RA2 RA1RA1 WC8WC8 WC7WC7 WC6WC6 WC5WC5 RB8RB8 RB7RB7 C A B向量处理时序图 18 具有延迟缓冲器的向量流水线结构然而实际情况并非总和上述理想化的情况一样 假如结果向量C的第一个元素C1不是存放在我们想存放的模块M5而是在模块M6 那么将出现存储模块的读写冲突 为了消除争用存储器的现象 可在运算流水线的输入端和输出端增加可变延迟缓冲器 如图所示 显然 有了输入输出缓冲器 可以实现向量操作无冲突地进行 存储系统 可变延迟器 流水处理部件 可变延迟器 先启动读A 再启动读B A延迟2个时钟进入加法器 19 寄存器 寄存器结构 使主存有较高带宽的另一种方法是由一级或多级中间存储器形成一个层次结构的存储器系统 其中带宽最高的这一级存储器安排在离处理器最近的位置 当处理器需要向量时 把向量从主存送到速度最快的这一级存储器 反之 运算结果也先送到速度最快的中间存储器 由于中间级存储器起着数据的中间存储作用 功能上相当于寄存器 因此称为寄存器 寄存器型向量处理机 20 Cray 1向量机结构 21 对于向量运算来说 中间存储器是8个向量寄存器 V 每个向量寄存器有64个分量 每个分量为一个64位寄存器 执行向量指令时 流水结构运算器在一个时钟周期内从两个V寄存器得到一对操作数 完成某种操作后用一个时钟周期时间把结果送入另一个V寄存器 注意 此处的向量运算流水线是从向量寄存器而不是从主存储器获得数据 同样 从流水线输出的结果向量也是送回向量寄存器 而另一方面 主存储器与V寄存器之间的数据传送以成组传送方式进行 对标量运算来说 有两级中间存储器 速度很快的一级是8个64位的S寄存器 它是标量寄存器 主存与T寄存器之间以成组传送方式进行数据交换 22 中间存储器的优点 这种中间存储器与Cache相比的一大优点是速度快 因为CRAY 1流水运算器通过寄存器寻址方式访问中间存储器 而访问Cache必须查Cache表 这需要较长时间 23 向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法 24 提高向量流水处理机性能的方法 一 多功能部件并行操作二 链接技术三 分段开采技术四 向量递归技术 25 一 多功能部件并行操作 对向量机中多个功能部件 使其能并行操作 并行操作条件 1 不存在向量寄存器使用冲突不允许出现RAW WAR WAW RAR相关 如 V4 V1 V2V5 V1 V2V5 V2 V3V5 V3 V4 2 不存在功能部件使用冲突每种功能部件一般只设置一个 如 V3 V1 V2V6 V4 V5 26 二 链接技术 利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术 实质上 链接技术是标量流水定向传送方法在向量寄存器中的应用 例如下面的向量加 向量乘操作 ADDVV1 V2 V3 V1 V2 V3MULVV4 V1 V5 V4 V1 V5 27 由于这两条指令间对V1向量寄存器存在先写后读相关 通常必须等加法指令做完后才可开始乘法指令 但如果使向量寄存器V1在同一时钟周期内 既接收一个功能部件送来的运算结果 又可把这一结果作为下一个向量指令运算所需的源操作数传送给另一个功能部件 那就可使这两个部件链接起来进行操作 通常把这种链接称为超级向量操作 当链接进入充分流水操作状态后 在1个时钟周期就可同时获取两个操作结果 28 链接条件 1 不存在功能部件使用冲突 2 共用向量寄存器中向量长度 起始地址 偏移量 步长均相等 3 参与链接的先行指令产生结果周期相同 4 只有在先行指令产生第一结果分量的那个时钟方可链接 否则不行 适用情况 即第1条指令的结果 是第2条指令的操作数 这时 所得到的第1条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作 可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器 形成两条指令的链接注意 不同向量机对向量指令的链接方法有所不同 29 例 用链接技术进行向量运算 D A B C 假设向量长度 64 且向量B C已由存储器取至V0和V1 解 用下面3条向量指令可完成上述运算 LVV3 M A V3 AADDVV2 V0 V1 V2 V0 V1MULVV V2 V3 V V2 V3第1 2条指令无向量寄存器使用冲突 也无功能部件使用冲突 因而可以并行执行 第3条指令与第1 2条指令均存在先写后读相关冲突 因而可将第3条指令与第1 2条指令链接执行 由于同步的要求 数据进入 流出每个功能部件 包括访问储存器 都需1个时钟周期时间 30 访存与浮点加并行 再与浮点乘链接LDV3 AADDVV2 V0 V1MULVV4 V2 V3 V0 V4 V1 V2 V3 1 3 2 4 5 6 1 3 2 4 5 6 浮点加 浮点乘 D B C 访存 存储器 A 并行和链接操作图 1 3 2 4 6 7 5 31 浮点加 访存 浮点乘 654321 654321 7654321 启动 流出 启动 第一个结果流出 1234567891011121314151617 一个数据处理时间17 第一 二条指令并行与第三条链接 32 若三条指令串行执行 即每次只有前条指令结束 才执行后继指令 那么三条指令执行的总时间为 1 6 1 N 1 1 6 1 N 1 1 7 1 N 1 3N 22 拍 若第一 二条指令并行与第三条串行 1 6 1 N 1 1 7 1 N 1 2N 15 拍 若第一 二条指令并行与第三条链接 1 6 1 1 7 1 N 1 N 16 拍 可以看出采用并行与链接后 可以很有效的改善性能 33 三 分段开采技术 处理长向量的程序结构称为向量循环 当向量的长度大于向量寄存器的长度时 必须把长向量分成长度固定的段 分段开采技术一次处理一个向量段 将长向量分段成循环是系统硬件和软件控制完成的 程序员看不到这种向量分段为循环的过程 即对程序员是透明的 每经过一次循环 就处理长向量的一个段 一般在进入循环以前 根据向量长度计算出循环计数值 34 例 A和B为长度N的向量 for i 1 i N i a i 5 b i c 当向量长度N为64或更小时 计算A数组的7条指令序列是 1 S1 5 0在标量寄存器内设置常数2 S2 C将常数C装入标量寄存器3 VL N在VL寄存器内设置向量长度4 Vo B将B向量读入向量寄存器5 V1 S1 VoB数组的每个分量乘常数6 V2 S2 V1C和5 B x 相加7 A V2将结果向量存入A数组 35 当N超过64时 要采用向量循环开采技术 在进入循环前 把N除以64 确定循环次数 如果有余数 则在第一次循环中首先计算 第4条到第7条指令组成循环1 S1 5 0在标量寄存器内设置常数2 S2 C将常数C装入标量寄存器3 VL N在VL寄存器内设置向量长度for i 0 i N 64 i 4 Vo B将B向量读入向量寄存器5 V1 S1 VoB数组的每个分量乘常数6 V2 S2 V1C和5 B x 相加7 A V2将结果向量存入A数组 36 前面所讲的三种技术措施都是在单处理机结构的向量计算机上实现的 为了更有效地提高向量处理性能 新型向量机采用了多处理机系统结构 在确定的应用背景下 向量处理机系统性能应该随处理机数目的增加而线性地提高 但是系统规模的扩展性不仅涉及CPU 还涉及存储器和I O资源 另外还要考虑价格和效率 因此 在系统设计时 力求做到处理速度 存储容量和I O吞吐能力三者之间的平衡 否则会出现瓶颈 整个系统的效率得不到发挥 采用多处理机系统结构 37 加速向量归约操作 应用举例 实现方法一 正常方法 1 C A B 流水 向量 操作 2 对C进行递归折叠求和 串行 循环 操作 实现方法二 加速方法 1 C V3 V4 流水 向量 操作 2 V0 V0 C 归约操作 38 归约实现方法 V0 V0 C 1 置V0各分量为0 V0和C的计数器C0 C1均为0 2 计数器C0在t8之前保持为0 C1在每个时钟周期后加1 直到第一个结果分量出来 8个时钟周期 3 计数器C0在t8之后每个时钟周期加1 直到等于向量计算长度为止 39 V00 C0 V00 C0 V00 C1 V01 C1 V00 C7 V07 C7 V00 C8 V08 C0 C8 V01 C9 V09 C1 C9 V07 C15 V015 C7 C15 V048 C56 V056 C0 C8 C56 V049 C57 V057 C1 C9 C57 V055 C63 V063 C7 C15 C63 t0 t8 t16 t63 结果 V0的最后8个分量为C0至C63之和 40 向量化编译技术一 向量化基本功能 1 并行性检测是否可用向量表示 是否存在相关 条件语句 操作数的间接访问等 2 并行性表示与开发用向量指令代替循环 用屏蔽向量实现条件判断 指令系统具有向量功能 编译程序支持向量操作 41 向量化编译技术二 向量化编译优化 1 通用优化方法公共子表达式消除 常数调入 复制语句传递等 2 循环体优化固定表达式移出 归约变量消除 向量指令表示等 3 向量寄存器优化分配重新分配向量寄存器 减少向量寄存器使用冲突 4 向量指令并行化重新排序向量指令 减少流水功能转换频率 争取功能部件并行操作 向量指令链接 42 向量处理机实例 向量处理机主要出自美国和日本 美国著名的向量计算机公司有 CRAY CDC TI等日本公司有 NEC Fujitsu Hitachi等 43 向量计算机系统结构的主要优点 向量计算机系统结构的主要优点 1 通过流水线方式有效提高了存储器带宽 2 流水结构的运算器有很高的性能价格比 3 非常简单的机制就能满足通信和同步要求向量处理机通常以Mflops作为速度单位 一般认为 在标量计算机中 执行一次浮点运算需要 条指令 平均需 条指令 44 向量计算机系统结构的发展趋势 向量计算机系统结构的发展趋势是 1 提供多种向量运算指令 2 除具有向量处理功能外还有其它功能 3 采用多层次的存储器系统 4 流水线技术与并行技术相结合 向量计算机系统结构要解决的六个技术问题 1 处理机带宽 有两条途径 运算部件采用流水线结构 用多个运算器构成并行系统 45 2 存储器带宽 多种解决方法 用多个独立的存储体构造大容量存储器系统 采用多层次的存储器系统提高访问速度 采用Cache和可寻址的寄存器组效果最好 采用流水线技术 存储系统的速度快5 20倍 3 输入 输出带宽 有10 29个DMA通道 4 通信带宽 共享存储器或互连网络 5 同步系统 多流水线结构通过控制程序使所有流水线能够同步工作 6 多用途 例如 能够处理非数值计算问题 46 作业 5 165 17