第6章向量处理机

第6章向量处理机 6 1向量处理的基本概念6 2一般的向量处理机6 3提高向量处理性能的常用技术6 4向量处理的性能评价6 5多向量多处理机习题6 6 1向量处理的基本概念 由于向量内各个元素间很少相关 对向量中的各个元素一般又都是执行同一种操作 只要能由存储器不断地取得元素 就能对各向量元素进行流水处理 最充分地发挥流水线的效能 使输出端每个时钟周期能送出一个结果元素 这就是向量的流水处理 向量处理机是指将向量数据表示与流水线技术相结合 能进行向量流水处理的处理机 又称之为向量流水处理机 6 1 1向量流水处理的主要特点 1 在向量操作中 每个向量元素的计算与其它向量元素的计算是相互独立的 即每对向量元素的运算之间不存在数据相关 这就允许向量流水线有较深的深度 一条向量指令对应一个循环的数组运算 相当于将一层循环完全展开 从而消除了一层循环中的控制机制开销 2 一条向量指令中包含大量的数据运算 相当于一个标量循环 从而可降低对指令访存带宽的要求 此外 向量指令可消除标量运算方式中由循环转移引起的控制相关 3 向量指令所要访问的向量元素在存储器中的存放地址均相邻 可采用交叉存储体提高访问的速度 由于一个向量中通常含有多个元素 因此对存储器访问的延迟平均到每个元素上 其访存等待时间开销是较小的 上述的这些特点使得对相同数量的数据项进行操作时 向量操作要比一串标量指令操作更快 此外 向量流水处理机还可使访存和有效地址计算流水化 通过设置多个向量运算部件并且允许多个向量操作同时进行 可开发对不同元素进行多个向量操作的并行性 6 1 2向量处理机的基本系统结构为了满足向量计算机中运算器带宽的要求 向量处理机系统结构可分为存储器 存储器工作方式向量处理机和寄存器 寄存器工作方式向量处理机两大类 前者的工作特点是向量操作的源向量都取自主存且操作生成的结果向量也存放到主存中 而后者向量操作的源向量都取自向量寄存器且操作生成的结果向量也存放到向量寄存器中 存储器 存储器工作方式向量处理机中 主存储器系统采用多个模块构成 功能流水部件与主存储器系统之间有三条独立的数据通路 两条输入和一条输出数据通路 各数据通路可以同时工作 但一个存储器模块在某一时刻只能为一个通路服务 寄存器 寄存器工作方式向量处理机中 在主存储器系统与功能流水部件之间插入了一个小容量的高速向量寄存器组 从而可获得较高的带宽 为了最大限度地利用高速的向量寄存器组 应尽量使大量的操作在向量寄存器组之间进行 从而减少访存的次数 降低对存储器带宽的要求 早期的向量机都是存储器 存储器方式的 如TI公司的ASC 1972年 CDC公司的STAR 100 1973年 CYBER 205 1982年 和ETA 10 1986年 1976年CRAY公司研制的CRAY 1向量机首次采用了寄存器 寄存器工作方式 由于它在短向量操作时显示出良好的性能 再加上指令系统的简洁性 因此逐步成为向量机的主流 美国Cray公司生产的CrayY MP 1988年 和C 90 1991年 日本Fujitsu公司生产的VP2000 1991年 和VPP300 500 1993年 等大规模超级向量流水处理机均属这种类型 不管是哪一种类型的向量处理机 典型的向量处理机基本系统结构如图6 1所示 主要由一个标量流水部件和若干个向量流水部件组成 基本结构包括标量寄存器 标量功能部件 向量存取部件 向量寄存器或向量缓冲部件 向量功能部件以及向量控制部件等 图6 1向量处理机基本系统结构 在基于寄存器 寄存器型的向量处理机中 向量指令有六种类型 1 向量 向量指令 vector vectorinstruction 它从有关向量寄存器中读取一个或两个向量操作数 送入向量流水线 对各元素进行相应的运算 运算产生的结果放入另一个向量寄存器 2 向量 标量指令 vector scalarinstruction 运算的一个操作数来自向量寄存器 另一个操作数来自标量寄存器 标量数据对向量数据中的每一个元素进行操作 3 向量 存储器指令 vector memoryinstruction 它进行向量存取操作 在向量寄存器和存储器之间进行向量数据的传送 4 向量归约指令 vectorreductioninstruction 操作数来自向量寄存器 操作的结果为标量数据 如从一个向量中找出最大值 最小值和中间值等 5 聚集 散射指令 gatherandscatterinstruction 用两个向量寄存器 分别存放数据和变址值 聚集分布在存储器中的向量元素 或者把向量元素散射到存储器中 聚集指令根据变址值把存储器中的某个稀疏向量的非零元素取出放到向量寄存器中 散射指令进行相反的操作 把一个向量以稀疏向量的形式存入存储器 其非零项由变址值指出 6 屏蔽指令 maskinginstruction 这类指令利用屏蔽向量把一个向量压缩或者展开成一个较短或较长的索引向量 6 1 3向量的流水处理方式由于向量元素主要是浮点数 浮点数的运算比较复杂 需要经过多个节拍才能完成 所以向量很适合于用运算流水线处理 当用运算流水线处理一个数组时 对向量中的每个元素都执行相同的操作 而且每个向量的各元素间又是互相无关的 因而流水线能以每个时钟周期送出一个结果的最高速度连续流动 只要存储系统来得及提供这些处理的元素 流水线就能达到最高速度 为此 向量处理机都配有一个大容量的 分成多个模块交叉工作的主存储器 能使向量运算充分发挥出流水线的效能 选择什么样的向量流水处理方式相当重要 下面我们重点介绍向量的三种流水处理方式 1 横向 水平 处理方式横向处理方式是指采用逐个求向量中各元素 分量 的方法来进行向量处理的方式 例如要进行如下向量运算 D A B C A B C D都是含n个元素的向量 横向处理方式为 d1 a1 b1 c1 d2 a2 b2 c2 dn an bn cn 具体操作可以简写成 bi cik1k1 aidi 采用横向处理方式时 存在如下缺点 1 逐个求结果向量的各个元素 会发生大量的先写后读操作数相关 此例中 只有等加法流水线的结果输出回送到乘法流水线的输入端时 才能开始乘法 因而会使流水线的实际吞吐率下降 2 如果在采用一条多功能静态流水线组成方式的机器上实现上述运算 加 乘相间的运算会引起流水线功能段的频繁切换 那么流水线的实际吞吐率会降低成与顺序串行执行方式的一样 因此横向处理方式不适合于向量的流水处理 一般用于标量机实现循环程序 以缩短程序长度 节省存放中间结果向量所需的存储单元数 2 纵向 垂直 处理方式纵向处理方式是指采用对两个向量按相同操作执行完之后 再转去执行别的操作的方法来进行向量处理的方式 如上例 纵向处理方式为 bi cikiki aidi 采用纵向 垂直 处理方式 可以避免功能部件的频繁切换 也不会产生大量的先写后读操作数相关 有利于发挥出向量处理机的性能 因此 纵向处理方式特别适合于向量的流水处理 纵向处理方式是将两个向量先全部运算完 得到一个中间结果向量后 再用此中间结果向量与其它向量运算 由于向量长度一般较长 这种方式难以用大量的高速寄存器来存放中间向量 所以不得不采用面向存储器 存储器型的流水线处理 这样 会对主存频宽提出相当高的要求 如面向存储器 存储器型的向量处理机STAR 100采用32体交叉存储器 每个存储体的数据宽度为8个字 每个字为64位 主存的频宽为1600MB s 改进的方法是分组纵横处理方式 3 分组纵横处理方式分组纵横处理方式是指在向量的长度n超出了向量寄存器组中寄存器的个数时 将该向量分成若干个组 使每组都能装得进向量寄存器组中 对组内向量元素采用纵向处理方式 而各组间则采用软件方法编制循环程序的方法依次循环处理的方式 称之为分组纵横处理方式 如上例 若向量寄存器的长度为n 向量的长度N m n r 其中r n 采用分组纵横处理方式为 b1 c1 k1 第1组 k1 a1 d1 bn 2 1 cn 2 1kn 2 1 第2组 kn 2 1 an 2 1dn 2 1 bmn m r 1 cmn m r 1kmn m r 1 第m 1组 kmn m r 1 amn m r 1dmn m r 1 分组纵横处理方式对向量长度N的大小不加限制 但它是以向量寄存器的长度n为一组进行分组处理的 在每组运算中 用长度为n的向量寄存器作为运算寄存器并保留中间结果 从而大大减少了访问存储器的次数 这就可以降低对存储器信息流量的要求 也减少了访问存储器发生冲突所引起的等待时间 因而提高了向量处理的速度 6 2一般的向量处理机 向量处理机的结构因具体机器不同而不相同 这里重点介绍CRAY 1向量流水处理机系统的基本结构特点 本书在6 5节给出了其它向量处理机的基本结构 CRAY 1是20世纪70年代设计的一种典型的向量处理机 1976年开始出售 CRAY 1向量处理机不能独立工作 它需要一台前置机对整个系统进行管理 这里只介绍CRAY 1向量处理机本身 CRAY 1向量处理机有120种指令 向量有10种格式 标量有13种格式 它的时钟周期为12 5ns 每秒最多能执行8000万条指令 80MIPS 平均在20 80MIPS之间 如果所有资源能充分利用 每秒可进行16000万次浮点运算 160MFLOPS 图6 2是CRAY 1向量处理机的结构框图 图中画出了它的运算流水线 寄存器组 数据通路等 下面介绍CRAY 1向量处理机的一些主要的特点 6 2 1寄存器组CRAY 1的寄存器组一共有5种 其中向量寄存器组 V 标量寄存器组 S 和地址寄存器组 A 是基本的寄存器 标量保存寄存器组 T 和地址保存寄存器组 B 是两种中间的寄存器 基本寄存器组可以直接被功能部件访问 中间寄存器组则不能被功能部件访问 T和B寄存器组只是分别对S和A寄存器组提供支持 图6 2CRAY 1向量处理机结构框图 向量寄存器组V是CRAY 1向量运算所用的主要操作数寄存器 由512个64位的寄存器组成 分成8组 编号分别为V0 V7 每个向量寄存器组Vi可存放最多包含64个分量的一个向量 因此向量寄存器中最多可存放8个向量 一个向量操作数中的一组数据可以存放在一组向量寄存器中的若干分量寄存器中 向量操作数的长度放在向量长度寄存器VL中 VL长7位 向量指令能对向量寄存器组的各个分量进行连续的重复处理 每一个时钟周期 功能部件可从两个源向量寄存器组中得到一对分量 经过运算后 再用一个时钟周期送入结果向量寄存器组的相应分量中 由于采用流水线工作 每拍都提供和存回相继的分量 向量寄存器组Vi在同一时钟周期内可接收一个结果分量 并为下次操作再提供一个源分量 这种把寄存器组既作为结果寄存器组又作为源寄存器组的用法 可以实现将二个或多个向量指令链接执行来提高向量操作的并行程度和功能部件流水的效能 地址寄存器组A中有8个24位的寄存器 A0 A7 用于存放主存地址 变址值 移位计数值 循环计数值和I O通道地址等 B寄存器组中有64个24位的地址保存寄存器 存放在一段时间内要反复使用的地址 A寄存器组可以直接访问主存 也可以经过B寄存器组传送数据 标量寄存器组S中有8个64位的寄存器 S0 S7 用于存放执行标量的算术和逻辑运算指令时的操作数 T寄存器有64个64位的标量保存寄存器 S寄存器组可以直接访问主存 也可以经过T寄存器传送数据 P寄存器是指令计数器 图6 2中左下角有一个指令缓冲寄存器组 共有4组缓冲寄存器 每组有64个16位的寄存器 指令长度有16位和32位两种 NIP CIP LIP寄存器用来发送指令 其余的寄存器有 VM为64位的向量屏蔽寄存器 可在运算前屏蔽掉向量寄存器中的一些分量 XA为交换地址寄存器 RTC为实时时钟计数器 6 2 2多个单功能流水部件在CRAY 1向量处理机中 为了加快向量操作 采用了12个独立的单功能流水部件 这些功能部件分为4组 3个功能部件用于向量运算 整数加 逻辑运算 移位 3个功能部件用于浮点运算 浮点加 浮点乘 浮点迭代求倒数 4个功能部件用于标量运算 整数加 逻辑运算 移位 加 1 计数 2个功能部件用于地址运算 整数加 整数乘 这些功能部件本身都采用流水线结构 各功能部件的流水经过时钟数是不一样的 但满负荷流动时均可以每个时钟流出一个结果分量 可用于向量运算的功能部件有整数加 逻辑运算 移位 浮点加 浮点乘 浮点迭代求倒数部件 所需的流水经过时钟数相应分别为3 2 4 6 7 14 可用于标量运算的功能部件有整数加 逻辑运算 移位 加1计数部件 所需的流水经过时钟数相应分别为3 1 2 3 3 4 只要不发生寄存器冲突 这些功能部件都能并行工作 为了充分发挥向量寄存器组同3个向量功能部件和3个浮点功能部件的作用以及加快向量处理 CRAY 1设计成8组向量寄存器 V0 V7 中任一组向量寄存器 Vi 都有单独的输入总线连到6个功能部件 6个功能部件中的每个功能部件也都有单独的输出总线把结果送回到8组向量寄存器去 图6 2中的Vi Vj和Vk表示的不是公共总线 而是若干组单独的总线 也就是说 只要不发生向量寄存器的冲突和功能部件的冲突 各组向量寄存器之间和各个功能部件都能并行工作 这就大大加快了指令的处理速度 6 2 3运算流水线向量 标量和地址的运算都采用运算流水线 CRAY 1的四种典型向量指令如图6 3所示 执行第1种向量指令时 每个时钟周期从向量寄存器Vi和Vj顺序取得一对分量送入一个需n个时钟周期完成的功能部件 经过n个时钟周期后开始输出结果 每个时钟周期向另一个向量寄存器Vk送回一个结果向量分量 分量的个数由VL寄存器指明 在向量合并或测试时 由VM寄存器控制对哪些分量进行合并或测试 一条向量指令最多只能处理64对分量 如果向量的长度N大于64 向量寄存器放不下 必须执行向量循环 每条向量指令处理64个分量 循环N 64次 取大于N 64的最小整数 执行第2种向量指令时 一个操作数取自标量寄存器Sj 另一个操作数取自向量寄存器Vi 结果为向量 送回另一个向量寄存器Vk 以上两种向量指令 都是寄存器 寄存器型指令 在这种机器中 一般总是先把向量取到向量寄存器组中再运行 所以尽量使用这种寄存器 寄存器型指令 每个时钟周期都可以从功能部件中流出一个结果向量分量 因而速度可以很高 图6 3CRAY 1的4种向量指令 第3种和第4种向量指令是在主存与向量寄存器组间传送数据 前者是从主存把数据送到向量寄存器组 后者是从向量寄存器组送数到主存 主存同向量寄存器间数据通路可以看成是一个数据传送的流水线 两个方向传送的延迟时间均为6个时钟周期 从这些向量指令的执行情况可以看出 向量的运算都是采用流水线方式的 6 3提高向量处理性能的常用技术 本节将讨论四种提高向量处理性能的常用技术 第一种方法是采用多功能部件的并行操作 第二种方法是链接技术 第三种方法是加快条件语句和稀疏矩阵的处理 第四种方法是加快向量的归约操作 前两种方法主要是为了提高相邻的两条或多条向量指令的执行速度 后两种方法主要是为了使循环向量化 以提高向量处理的速度 6 3 1多功能部件的并行操作1 基本概念Vi冲突 或称向量冲突 是指并行工作的各向量指令的源向量或结果向量使用了相同的Vi 它包括源向量冲突 结果向量冲突 先读后写的向量冲突和源目向量相关 例6 1源向量冲突V4V1 V2V5V1 V3 在此例中的两条向量指令均使用了相同的向量寄存器V1作为源向量 故称这两条向量指令存在源向量冲突 由于两条向量指令中使用的V1的首下标 第1个元素 可能不同 向量长度也可能不同 从而难以由V1同时向两条向量指令提供所需的源向量 故这两条向量指令不能并行执行 例6 2结果向量冲突V3V1 V2V3V5 V4在此例中的两条向量指令均使用了相同的向量寄存器V3作为结果向量 故称这两条向量指令存在结果向量冲突 例6 3先读后写的向量冲突V3V1 V2V1V5 V4在此例中的第一条向量指令使用了向量寄存器V1作为源向量 第二条向量指令使用了相同的向量寄存器V1作为结果向量 故称这两条向量指令存在先读后写的向量冲突 例6 4源目向量相关V3V1 V2V5V3 V4 在此例中的第一条向量指令使用了向量寄存器V3作为结果向量 或称目标向量 第二条向量指令使用了相同的向量寄存器V3作为源向量 故称这两条向量指令存在先写后读的源目向量相关 由于在向量处理机中 任何一个向量寄存器Vi在同一时钟周期内可接收一个结果分量 并能为下次操作再提供一个源分量 因此存在源目向量相关的两条向量指令在不发生其它Vi冲突和功能部件冲突的前提下 可通过链接机构将两条向量指令的处理过程链接起来 实现两条指令的流水处理 功能部件冲突是指同一个功能部件被一条以上的要求并行工作的向量指令所使用 例6 5功能部件冲突V4V2 V3V5V1 V6在此例中的两条向量指令均使用了相同的乘法功能部件 故称这两条向量指令存在功能部件冲突 2 多功能部件的并行操作上一节我们在介绍CRAY 1的结构特点时已介绍了多个单功能流水部件和运算流水线 由于向量寄存器与用于向量处理的6个功能部件之间都有单独的输入输出数据总线 因此只要不发生向量寄存器的冲突和功能部件的冲突 各组向量寄存器之间和各个功能部件都能并行工作 例如 V2V0 V1V5V3 V4 第一条向量指令使用的向量寄存器为V0 V1和V2 第二条向量指令中使用的向量寄存器为V3 V4和V5 没有使用相同的向量寄存器 因此未发生向量寄存器冲突 第一条向量指令要使用浮点加运算部件 第二条向量指令要使用浮点乘部件 没有使用相同的功能部件 因此未发生功能部件的冲突 从以上分析可以看出 两条向量指令可以并行执行 即这两条向量指令可以同时启动不同的功能部件 使用不同的向量寄存器和不同的输入输出数据总线 同时实现两条向量指令的流水处理 6 3 2链接技术1 链接技术的概念链接技术是流水线中加快运算速度的一种重要技术 它是指在不出现源向量冲突 结果向量冲突 先读后写的向量冲突和功能部件冲突时 通过链接机构将有源目向量相关的前后两条或多条向量指令进行链接而实现并行处理的技术 机器会自动检查每一条向量指令是否可能与它前一条或二条向量指令存在源目向量相关 同时无源向量冲突 结果向量冲突 先读后写的向量冲突和功能部件冲突 若存在 则在前一条或二条指令的第一个结果分量都到达向量寄存器组并可以用作本条向量指令的源操作数时 立即启动本条指令工作而形成链 有了链接技术 可以使一些存在着源目向量相关的指令也能并行处理 CRAY 1机一共有8个向量寄存器组 一般可以有2 5个功能部件链接在一起工作 例6 6求向量运算D A B C 若向量的长度n 64 向量的分量为浮点数 且向量B C已取到V0和V1 试分析采用下述三条指令实现功能而采用的链接技术 V3存储器 访存取A向量 V2V0 V1 B向量和C向量相加 V4V2 V3 浮点乘 存D向量 这三条向量指令中 第2条与第1条既无功能部件冲突 又无Vi冲突 故这两条向量指令可以并行执行 第3条与第1条和第2条均无功能部件冲突 但存在Vi冲突 由于这种Vi冲突属于源目向量相关 因此只要第1条指令中结果向量V3的第1个分量与第2条指令中结果向量V2的第1个分量均产生 就可通过链接机构将这一对分量直接送往浮点乘功能部件 链接执行第3条指令 如图6 4 访存与浮点加并行执行 再与浮点乘链接执行 执行上述3条向量指令 获得第一个结果分量并存入V4 所需的拍数 亦称为链接流水线的流水时间 为 启动访存访存存V3送浮乘部件1 6 1 1送浮加部件浮加存V2送浮乘部件 17拍由于每拍可取得一个结果分量存入V4 因此获得全部结果分量所需的拍数为 17 n 1 拍 7 浮乘 1 存V4 图6 4并行和链接操作过程图 2 向量流水线处理举例例6 7在CRAY 1机上 设向量的长度均为64 所用浮点功能部件的执行时间分别为 相加需6拍 相乘需7拍 从存储器读数需6拍 打入寄存器及启动功能部件各需1拍 问下列各指令组 组内的哪些指令可以链接 哪些指令不可链接 不能链接的原因是什么 并分别计算出下列各指令组全部完成所需的拍数 1 V2V0 V1V3存储器V4V3 V5 2 V0存储器V1V2 V3V4V5 V6 3 V0存储器V2V0 V1V3V0 V4 解 1 第3条向量指令与第2条向量指令有源目向量相关 可以链接执行 第1条向量指令与第2 3条向量指令无关 可以与它们并行执行 送浮乘部件浮乘浮乘存V21 6 1 1送浮加部件启动访存访存存V3送浮加部件 64 1 79拍 6 浮加 1 存V4 2 三条向量指令都无关 所以三条向量指令可以并行执行 启动访存送浮加部件访存存V01送浮加部件 6浮加 1存V1 1 存V4 64 1 72拍送浮乘部件浮乘浮乘送浮乘部件 3 第2条向量指令与第1条向量指令有源目向量相关 可以链接执行 第3条向量指令与第2条向量指令有源向量冲突 故只能等到第2条向量指令执行完毕后 才能执行第3条向量指令 1 启动访存 6 访存 1 存V0 1 7 浮乘 1 存V2 64 1 送浮乘部件送浮乘部件 送浮加部件 1 6 浮加 1 存V3 64 1 151拍送浮加部件 在分析向量指令的处理时要注意 无关向量指令的并行执行 源目向量相关的向量指令的链接执行 除源目向量相关外其它发生Vi冲突的向量指令的串行执行 功能部件冲突的向量指令的串行执行 以及向量内部各分量流水处理之间的区别 6 3 3条件语句和稀疏矩阵的加速处理方法1 加快条件语句的执行当程序中含有条件语句或要进行稀疏矩阵运算时 通常无法发挥向量处理的优点 例如 对于如下FORTRAN程序 DO10I 1 64IF A I NE 0 THENA I A I B I ENDIF10CONTINUE 由于要执行条件语句 使循环体无法向量化 为加快条件语句的执行 使减法只有当A I 0时才执行 通常采用向量屏蔽技术来实现上述循环的向量化 所谓向量屏蔽技术 是指借用一个屏蔽向量来控制哪些向量元素参加运算 哪些元素不参加运算的技术 而屏蔽向量是通过向量测试得到的 假定向量A和B的起始地址存放在寄存器Ra和Rb中 采用向量屏蔽技术实现上述循环程序的向量处理机CRAY 1汇编语言源程序如下 LVV1 Ra 将向量A装入V1 LVV2 Rb 将向量B装入V2 LDF0 0 将浮点数0装入F0 SENSVF0 V1 若V1 i F0 则将VMi置为 1 SUBVV1 V1 V2 在屏蔽向量控制下进行减法操作 CVM 将屏蔽向量寄存器置为全 1 SVRa V1 将结果存入A 2 加快稀疏矩阵执行速度矩阵是许多科学与工程计算问题中研究的数学对象 我们把许多元素的值为零的矩阵称为稀疏矩阵 在计算机系统结构方面采用了一种稀疏向量方法来解决稀疏矩阵问题 例如在典型的稀疏矩阵运算中 常见到类似如下的程序段 DO10I 1 N10A K I A K I B M I 图6 5向量的聚合与射散操作图 此程序段完成的功能是对稀疏向量A和B求和 用指标向量K和M指明A和B中的非零元素 此时要求A和B必须有相同的非零元素长度N 除了指标向量外 也可用位向量来指明非零元素 支持稀疏矩阵运算的基本结构是使用指标向量的散射 聚合 scatter gather 操作 聚合操作是根据指标向量内容选取元素 它们的地址由基址加上指标向量中给定的相应地址偏移而形成 聚合操作后存于目的向量寄存器中的结果已不再是稀疏向量 而已成为稠密向量 若要将此稠密向量恢复成稀疏向量 可用散射操作 这也借助于同一指标向量来完成 向量的聚合与散射操作如图6 5所示 6 3 4向量归约操作的加速方法归约 reduction 操作一般难于向量化 因为对一个象一维数组那样的向量归约求值的结果得到的是一个标量值 归约操作是递推 recurrence 操作中的一个特例 对于向量归约操作的加速方法可采用 1 先将归约操作分解为可向量化部分和递推求和部分 不可向量化部分 2 再将递推求和部分采用递归折叠技术 它是加快向量归约操作的有效方法 例如 求有64个分量的向量A与B的点积 其FORTRAN程序如下 DOT 0 0DO10I 1 6410DOT DOT A I B I 由于此循环存在迭代层间的先写后读数据相关 因而无法直接向量化 现将其分解为可向量化部分和递推求和部分 DO10I 1 64 可向量化部分 10DOT I A I B I DOT1 0 0 递推求和部分 DO20I 1 6420DOT1 DOT1 DOT I 再将递推求和部分采用递归折叠技术进行修改 具体如下 LEN 32DO10I 1 6 分量的个数64 26 需递归折叠6次 DO20J 1 LEN 开始32个PE并行计算 然后16个PE并行计算 最后1个PE计算 共6步 即6次折叠 20DOT J DOT J DOT J LEN LEN LEN 210CONTINUE对于向量长度为64的操作 只需递推6步就可在DOT 1 中得到所需的递推和 6 4向量处理的性能评价 在评价向量流水处理机性能时 主要的参数为向量流水处理的时间和向量的长度 较常用的 与向量长度有关的评价向量流水处理机性能的参数有向量流水线的最大性能R 渐近性能 半性能向量长度n1 2 向量和标量的平衡点nv 6 4 1向量流水处理的时间在向量处理机的流水功能部件中 假设执行一个长度为n的向量操作的时间为Tvp Ts为流水线建立时间 包括向量起始地址的设置 计数器加1 条件转移指令执行等 Tl为第一对向量元素通过流水线的时间 Tc为流水线的时钟周期 则有 Tvp Ts Tl n 1 Tc s Tc l Tc n 1 Tc s l 1 Tc nTc 6 1 其中s为建立流水线所需时钟周期数 l为完成每对向量元素操作所需的子操作数 令To s l 1 Tc 有 Tvp To nTc 6 2 在上述流水线中 每对向量元素的平均执行时间tvp为 s l 1 Tc nTctvp Tvp n 6 3 limtvp lim Tc 6 4 R lim 1 Tc 6 5 s l 1 Tc nTc n n n tvp 1 n 其中R 表示当向量长度n趋于无穷大时 向量流水处理的最大性能 为了衡量向量流水线中的操作有效性 通常用半性能长度n1 2这一参数 它表示为达到向量流水线性能值一半时所需要的向量长度 n1 2R s l 1 Tc n1 2Tc2 R 1 Tc n1 21 s l 1 Tc n1 2Tc2Tcn1 2 s l 1 6 6 所以Tvp可表示为 Tvp n1 2 n Tc n1 2 n R 6 7 对于以串行方式工作的标量处理机 要完成同样的向量操作 所需时间Tsp为 Tsp Ts1 nlTcs 6 8 其中Ts1为标量循环建立时间 Tcs为标量部件工作的时钟周期 对于n个元素对 它的平均执行时间tsp为 Tsl Tsp n 6 9 limtsp lim lTcs 6 10 R lim 6 11 Tsl nlTcs n n n tsp 1 1 lTcs n 其中这里的R 表示当向量长度n趋于无穷大时 用标量处理机串行处理向量的各个元素所得到的最大性能 串行 向量流水两种操作方式的向量处理时间 向量处理速率与向量长度的关系如图6 6所示 图6 6串行 向量流水两种操作方式的向量处理时间 向量处理速率与向量长度的关系 6 4 2与向量长度有关的向量流水处理机性能参数1 向量流水线的最大性能R 向量流水线的最大性能R 是指向量长度趋于无穷大时的向量流水线的渐近性能 常在评价峰值性能时使用 单位为MFLOPS 2 半性能向量长度n1 2半性能向量长度n1 2是指为达到R 的一半值所需的向量长度 它是评价向量流水线建立时间对性能影响的参数 3 向量和标量的平衡点nv向量和标量的平衡点nv表示向量流水方式的工作速度优于标量串行方式时所需的向量长度临界值 若向量的长度n nv则表示向量流水方式的工作速度优于标量串行方式 反之 则表示采用标量串行方式处理向量的各元素时 速度优于向量流水方式 例6 8向量处理机CrayY MP 8的机器周期时间为6ns 一个周期可以完成一次加和一次乘运算 另外 8台处理机在最好情况下可以同时运算而互不干扰 计算CrayY MP 8的峰值性能 解 CrayY MP 8的峰值性能为 R 2667MFLOPS 1 1 816Tc 1066 10 9 106 例6 9若某个向量处理机其向量方式的执行速率Rv 10MFLOPS 标量方式的执行速率Rs 1MFLOPS 设a是程序中可向量化的百分比 要求 1 推导该向量机的平均执行速率Ra的公式 2 画出在 0 1 范围内 Ra与a的关系图 3 为使平均执行速率Ra 7 5MFLOPS 则a的值应取何值 4 假定Rs 1MFLOPS a 0 7 则为使Ra 2MFLOPS Rv应取何值 解 1 该向量机的平均执行速率Ra的公式为 Ra 6 12 11 0 9a 6 13 1 a 1 Rs a 1 Rv 1 2 在 0 1 范围内 Ra与a的关系图如图6 7所示 图6 7Ra与a的关系图 3 将Ra的值代入式6 13 有 7 5 1 1 0 9a a 0 963 4 将Rs a Ra的值代入式6 12 经计算后得 Rv 3 5MFLOPS 例6 10日本FOCOM向量处理机VP 200具有流水线链接和并行化功能 它有2条取存流水线连到向量寄存器 两者可并行工作 此外尚有加法和乘法流水线 各流水线间均可链接操作 现若要在VP 200向量机上实现以下的向量操作 A I B I C I D I E I F I G I 其中I 1 2 N 假设只考虑向量中各分量间的流水操作 而忽略加法和乘法操作的内部流水 设所有操作功能的延迟时间都为t1 取 存操作转换时将有t2的流水线重构延迟时间 试画出完成上述向量操作时 2条取存流水线 1条加法流水线和1条乘法流水线工作的时 空图 并以N t1 t2表示完成操作所需时间 解 假设各向量从存储器取出装入的向量寄存器如图6 8所示 为使向量操作所需的时间最短 由图6 8写出对应的向量指令序列如下 图6 8向量变量与向量寄存器的对应关系图 I1 V0存储器取B I I2 V1存储器取C I I3 V2V0 V1I4 V3存储器取D I I5 V4存储器取E I I6 V5V3 V4I7 V6V2 V5I8 V7存储器取F I I9 V8存储器取G I I10 V9V7 V8I11 V10V6 V9I12 存储器V10 流水线工作的时 空图如图6 9所示 图6 9向量操作的流水线时 空图 6 5多向量多处理机 这一节将介绍二十世纪八十年代和九十年代由美国和日本制造的大规模超级向量流水处理机 主要包括美国Cray公司生产的CrayY MP和C 90 日本Fujitsu公司生产的VP2000和VPP500 6 5 1CrayY MPCrayY MP816系统结构框图如图6 10所示 系统可以配置1台 2台 4台或8台处理机 CPU的时钟周期为6ns Y MP的8个CPU共享中央存储器 I O子系统 处理机间通信子系统和实时钟 中央存储器分成256个交叉访问的存储体 通过每个CPU对4个存储器端口的交叉访问可以实现对存储器的重叠存取 中央存储器的容量可以是16兆字 32兆字 64兆字和128兆字 最大可达1GB 固态存储器的容量可以从32兆字到512兆字 最大可达4GB 4个存储器访问端口允许每个CPU同时执行两个标量和向量取操作 一个存储操作和一个独立的I O操作 这些并行的存储器访问也采用流水线方式 使得向量读和向量写可以同时进行 图6 10CrayY MP816系统结构 系统内部有分解冲突的硬件 使存储器冲突引起的延迟减到最小 为了保护数据 在中央存储器及其输入和输出数据通道中都采用了单错校正 双错检测逻辑 CPU的计算系统由14个功能部件组成 分为向量 标量 地址和控制四个子系统 如图6 10所示 向量和标量指令可以并行地执行 所有算术运算都是寄存器到寄存器类型 向量指令可以使用14个功能部件中的8个 系统使用了大量地址寄存器 标量寄存器 向量寄存器 中间寄存器和临时寄存器 通过对寄存器及多条存储器和算术 逻辑流水线的使用 可以实现功能流水线灵活的链接 浮点和整数算术运算都是64位 大型指令高速缓存可同时存放512条16位的指令 主机中的处理机之间通信系统包括用于快速同步目的的共享寄存器群 每个群由共享地址寄存器 共享标量寄存器和信号灯寄存器组成 CPU之间向量数据通信是通过共享存储器实现的 实时钟由64位计数器组成 每个时钟周期计数器加1 由于时钟与程序执行同步 所以它可以用来准确地计算时间 I O子系统支持三类通道 传输速率分别为8MB s 100MB s和1GB s IOS和SSD是高速数据传输设备 通过8个高速缓存支持主机的处理工作 6 5 2C 90和机群C 90对Y MP系统在技术上和规模上作了进一步改进 C 90 16256系统由16个类似于Y MP的CPU组成 16台处理机共享主存储器的容量高达256兆字 2GB SSD存储器的容量最多达16GB 可选作第二级主存储器 两条向量流水线和两个功能部件可以并行操作 每个时钟周期能产生4个向量计算结果 这意味着每台处理机有4路并行性 因此16台处理机每个时钟周期最多可以产生64个向量计算结果 C 90运行UNICON操作系统 它是UNIX系统V和BerkeleyBSD4 3经过扩充而成的 许多主机可以驱动C 90 该系统提供向量化的Fortran77和C编译器 64路并行性和4 2ns时钟周期相配合 可使系统的峰值性能达到16GFLOPS 系统最大I O频宽为13 6MB s 为了求解大型问题 还可以把多台C 90连成机群结构 如图6 11所示 4个C 90机群通过速度为1000MB s的通道与SSD组连接 每个C 90机群只能访问自己的主存储器 然而它们共享SSD 换句话说 SSD中的大量数据可供4个C 90机群共享 每个机群也可以通过共享信号灯部件与其它机群进行通信 只有同步和控制信息才通过信号灯部件传输 在这个意义上说 C 90机群之间是松散耦合的 但整个系统能提供的最大并行性为256路 图6 11与公共SSD相连的四台CrayY MPC 90构成的一个松散耦合的256路并行系统 如果计算能划分得很好并且机群间负载很均衡 那么配置为4个C 90机群的系统 其峰值性能可以达到64GFLOPS 6 5 3FujitsuVP2000VP2000系列是日本Fujitsu公司制造的多向量多处理机 系统可以配置1至2台处理机 VP 2600 10单处理机系统的系统结构如图6 12所示 它可以扩充成双处理机系统 VP 2400 40 系统时钟为3 2ns 主存储器容量为1GB或2GB 系统存储器可扩充到32GB FujitsuVP 2000中的每个向量部件由二条装入 存储流水线 三条功能流水线和二条屏蔽流水线组成 两个标量部件与一个向量部件相连 因此 在双处理机配置时 最多可以有4个标量部件 在VP 2000的10个不同型号的处理机中 其最大向量性能范围为0 5到5GFLOPS FujitsuVP 2000中 总数为64KB的寄存器堆可以重构成8 16 32 64 128 256个向量寄存器 它们分别有1024 512 256 128 64 32个分量寄存器 所有分量寄存器的长度为64位 图6 12FujitsuVP2000系列超级计算机系统结构 6 5 4VPP500VPP500是Fujitsu公司推出的最新超级计算机系统 称为向量并行处理机 vectorparallelprocessor VPP500的系统结构可以配置1到2台控制处理机 7到222个处理部件 PE 它能够对MIMD提供灵活有效的支持 是一个高性能的分布式存储系统 整个系统使用全局共享虚拟主存的方法 将所有PE的局部内存在系统范围内进行统一编址 使得PE间可相互进行地址访问 图6 13是VP2000或VPX200为主机 VPP500为后端机的结构示意图 VPP500系列计算机系统融合了当前MPP领域的许多新技术 如交叉开关 路障 barrier 同步机制和系统分区机制等 VPP500系统的PE之间由无冲突高速交叉开关互联网络进行协调控制 在最大系统情况下使用了含有224 224个交叉开关的互联网络 这些交叉开关组装在两种类型共32块插件板上 这些交叉开关的实现占了全系统硬件最大配置的1 8和系统最小配置的1 30 它的使用有效地提高了数据传输率 VPP500系统交叉开关互联网络采用的是TCP IP协议进行PE间的进程通信 PE间的通信结构使用户程序能够直接进行数据传送 路障同步机制可以用硬件手段对运行在不同PE上的进程进行同步控制 路障的使用能够大幅度地减少操作系统的开销 只有当被同步的所有进程都到达同步点之后 进程才能继续往下执行 为了确保系统的灵活性 针对系统的分布式存储结构设计的UXP VPP操作系统还支持分区操作 即可将全系统的所有PE分成几个不同的PE组 在作业运行时 系统会根据各作业对资源的要求情况将作业分配到不同的PE组进行执行 系统的每个分区独立地执行自己的作业队列中的作业 VPP500中的每个处理部件PE是一个具有标量部件SU ScalarUnit 向量部件VU VectorUnit 数据传输部件DTU DataTransferUnit 和局部主存的独立计算节点 PE结构如图6 13右部所示 标量部件SU采用了LIW LongInstructionWord 的RISC技术 能够在单时钟周期内并发执行3个操作 峰值性能为三亿次标量运算和二亿次浮点运算 向量部件VU包含了一个128KB的大容量向量寄存器 向量屏蔽寄存器和7条流水线 峰值性能达到2 2GFLOPS 为了取得更好的运算性能 浮点运算 内存访问和向量指令的执行是异步的 通过使用专门的数据传输部件DTU PE可以同时传送 接收和处理数据 DTU为PE间数据交换提供约400MB s的单向传输能力和800MB s的双向传输能力 DTU负责将逻辑地址转换为物理地址 以利于访问虚拟的全局存储器 DTU还配有专门的硬件以实现快速路障同步机制 图6 13Fujitsu公司VPP500系统结构 每个PE最大可扩充到1GB主存 峰值性能可达1 6到2 2GFLOPS 主存容量和I O能力都有很大的可扩展性 VPP500系列的PE数目为4到224个 含2个控制处理机CP 最高性能可达355 2GFLOPS 总存储能力可达222GB PE主板上的VLSI使用的是高性能 低功耗的256K个GaAs门和BiCMOSLSI电路 工艺水平达到0 35 m 元件密度达8百万个晶体管 门延迟仅为40ps 这些LSI被安装在多层的MCM Multi ChipModule 中 然后再装到PE主板上 MCM意思为多芯片模块组装技术 它是把多个未封装的裸芯片安装在一块多层高密度互连基板上 然后封装在同一管壳中 主存元件由60ns的4Mbit或者16Mbit的SDRAM SynchronousDynamicRAM 芯片构成 以上所有元件均被安装在一块主板上 使得整个系统的组装结构十分紧凑 PE硬件具有优良的可扩展性和最优的性能价格比 装配简单方便 习题6 1 解释下列术语 向量流水处理向量处理机向量冲突源目向量相关功能部件冲突链接技术向量屏蔽技术向量流水线的最大性能半性能向量长度向量和标量的平衡点 2 简述向量流水处理的主要特点 3 向量流水处理机的工作方式可分为哪两大类 它们的主要特点是什么 4 向量的流水处理方式有哪几种 各有什么特点 试从加工速度 需使用的中间变量等方面加以比较 5 在CRAY 1向量处理机上 V为向量寄存器 设向量长度均为64 所用浮点功能执行部件的执行时间分别为 加法需6拍 相乘需7拍 从存储器读数需6拍 求倒数近似值需14拍 打入寄存器及启动功能部件 包括存储器 各需1拍 问下列各指令组中的哪些指令可以链接执行 哪些指令可以并行执行 试说明其原因并分别计算出各指令组全部执行完所需的拍数 1 V0存储器 2 V2V0 V1V3V1 V2V3存储器V6V4 V5V4V2 V3 3 V0存储器 4 V0存储器V3V1 V2V11 V0V4V0 V3V3V1 V2V6V4 V5V5V