《计算机系统结构》读书笔记（十六）
第六章 向量处理机
向量处理机是有向量数据表示的处理机，分向量流水和阵列处理两类
向量流水处理机是以时间重叠途径开发的。
阵列处理机是以资源重复途径开发的
6.1 向量的刘水处理与向量流水处理机
由于向量内部各元素（分量）很少相关，且一般又是执行同一操作容易发挥流水线的效能，可将向量数据表示和流水线结合构成向量流水处理机，以调高面向向量数组计算类应用的计算机的速度性能。
6.1.1 向量处理和向量的流水处理
选择使向量运算最能充分发挥出流水效能的处理方式，是向量的流水处理所要解决的问题。
不同的向量处理方式会对流水处理机的结构、组成提出不同的要求，而结构和组成不同的向量处理机反过来也会要求采用不同的向量流水处理方式。
例 D=A+(B+C)，其中ABCD都是有N个元素的向量。
若采用逐个求D向量元素的方法，既访存存取ai，bi，ci元素求di，再取ai+1，bi+1，ci+1，求di+1
这种处理方式为横向（水平）处理方式。
横向处理宜于在标量处理机上用循环程序来实现，却难以使流水线连续流动。
采用对整个向量按相同操作都执行完之后再转去执行别的操作，才能较好地发挥流水处理的效能，处理方式改为
，再执行，称这种方式为纵向（垂直）处理方式。
若向量的长度N太长，超出了向量寄存器组中寄存器的个数，可以将该向量分割成若干组，使每组都能装进向量寄存器，这样，每一组内均按纵向方式处理，组和组之间则采用软件方法编制循环程序的方式依次循环处理，这种叫分组纵横处理方式。
结论：向量横向处理是向量的处理方式，但不是向量的流水处理方式，而向量总想处理和分组纵横处理既是向量的处理方式，也是向量的流水处理方式。
6.1.2 向量流水处理机的结构举例
向量流水处理机的结构因具体机器的不同而不同
寄存器——寄存器型向量流水处理机的结构特点，以CRAY-1为例
CRAY-1由中央处理机，诊断维护控制处理机，大容量磁盘存储子系统，前段处理机组成的功能分布异构型多处理机。
中央处理机的控制部分有总容量为256个16位的指令缓冲器，分成4组，每组64个。
中央处理机的运算部分有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算，另外，还有可为流水线功能部件直接访问的向量寄存器组V0~V7，标量寄存器S0~S7及地址寄存器A0~A7
向量寄存器部分由512个64位寄存器组成，编号V0~V7，每个向量寄存器组Vi可存放最多64个分量（元素）的一个向量。
为处理长向量而形成的程序结构称为向量循环。
CRAY-1有标量类和向量类指令共128条。
6.1.3 通过并行、链接提高性能
一般可采取让多个流水线功能部分并行，流水线链接，加快条件语句和稀疏矩阵处理，加快向量的规约操作等办法来提高向量流水处理性能，前两者主要加快相邻向量指令的执行，后两者主要是让循环向量化。
把寄存器组即作为结果寄存器，又作为源寄存器组的作法，可实现将两条或多条向量指令链接成一个链来提高向量操作的并行程度和功能流水线和效能。
Vi冲突：并行工作的各向量指令的源向量或结果向量使用了相同的Vi
功能部件冲突：同一个功能部件被要求并行工作的多条向量指令所使用。
CRAY-1特点：只要不出现功能部件使用冲突和源向量寄存器使用冲突，通过链接机构可使有数据相关的向量指令仍能大部分时间并行执行。
可以链接的后续指令与前一条指令之间可以插入一些其他相关的指令，只要不错过连接时间，就可以提升系统性能。
CRAY-1指令可连接的贴点，使它能灵活地组织各流水线功能部件的并行操作，最多能并行处理6条向量指令，进一步发挥出流水线功能部件的效能，因此链接技术是提高计算机整体运算速度的一个非常重要的措施。
6.2 阵列处理机的原理
6.2.1 阵列处理机的构型和特点
1.阵列处理机的构形
阵列处理机有两种构形，差别主要在于存储器的组成方式和互联网络的作用不同。
构形1：分布式存储器的阵列处理及的构形
各处理单元有局部存储器（Processing Element Memory ,PEM）存放被分布的数据，只能被本处理单元直接访问。
在控制部分内还有一个存放程序和数据的主存储器，整个系统是在控制部件的控制下运行用户程序和部分系统程序，在执行主存储器内的用户程序时，所有指令都在控制部件内译码，把只适合串行处理的标量或控制类指令留在控制部件自己执行，把适合于并行处理的向量类指令播送给PE，控制处于活跃的那些PE并行执行。
为高度有效地处理向量数据，这种构形能把数据合理地预分配到各个处理单元的局部寄存器中，使个处理单元PEi主要用自己的PEMi中的数据运算，分布于各PEM的数据，可经系统数据总线从外部输入，也可以控制总线经过控制部件播送，执行向量指令时，可使用屏蔽位向量控制，让某些PE不工作，运算中，PE之间可通过互联网络（InterConnection NetWork,ICN）来交换数据，互联网络的连通路径选择也由控制部件统一控制。
处理单元阵列通过控制部件接到管理处理机SC上，管理处理机是一种通用机。
构形2：集中式共享存储器的阵列处理机构形
系统存储器室友K个存储分体（MM0~MMk-1）集中组成，经ICN为全部N个处理单元（PE0~PEN-1）共享，为使各处理单元对长度为N的向量中各个元素都能同时并行处理，存储分体个数K应等于或多于处理单元数N，各处理单元在访主存时，为避免发生分体冲突，要求有合适的算法能将数据合理地分配到各个存储分体中。
ICN在集中式共享存储器的阵列处理机构形中的作用为在处理单元与存储器分体之间进行转接工程数据通路，希望咯处理能告诉灵活，动态地与不同的存储分体相联，使尽可能多的PE能为无冲突地访问（单元）共享的主存模块，因此，有的阵列处理机称它为对准网络（Alignment Network）
2.阵列处理机的特点
阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等问题发展而来。
计算问题利用多个处理单元对向量或数组所包含的各个分量同时计算，从而易于获得提高的处理速度。
阵列处理机利用的是资源重复、并行性中的同时性，它的每个处理单元同等地负担起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件的那样搞。只有在硬件价格有了大幅下降及系统结构有了较大改进的情况下，阵列处理机才能有好的性能价格比，阵列处理机提高速度主要是靠增大处理单元数，比起向量流水出六级主要靠缩短时钟周期来说，速度提高的潜力大。
阵列处理机使用简单、规整的互联网络来约定处理单元间的连接。互联网络的结构形式先顶了阵列处理机可用的解题算法，也会对系统多种性能指标产生显著影响，因此，互联网络的设计时重点。
阵列处理机在机间互联上比固定结构的单功能流水线灵活，使相当一部分专门问题上的工作性能比流水处理机高的多，专用性轻得多。
阵列处理机是一种专用处理剂，它是以一定数量的专用算法为北京的，结构是与采用并行算法紧密联系在一起的。
阵列处理机基本上是一台专用于向量处理的计算机。
阵列处理机系统的控制部件必须是一台具有高性能、钳功能的标量处理机，以减少标量运算对系统性能的影响，编译时间的多少，则不仅与阵列处理机结构有关，也与机器语言的并行程度有关，特别是想要提高阵列处理机的通用性，建立一个有向量化功能的高级语言编译程序就是非常必要的了，陈列处理机还必须有一台高性能单处理机作为管理计算机来配合工作，运行系统的全部管理程序，阵列处理机实质上是由专门应对数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列的控制及标量处理的处理机和专门从事系统输入/输出的及操作系统管理的处理机组成的一个异构型多处理机系统。
6.2.2 ILLIAC IV的处理单元阵列结构
阵列处理机上的并行算法研究的是与结构紧密联系在一起的，ILLIAC IV阵列处理机上处理单元的互联结构采用的是分布存储器构形。
ILLIAC IV处理单元的阵列结构
使用一种闭合螺线阵列。
个处理单元组成的阵列中，任意两个处理单元之间的最短距离不超过步。
ILLIAC IV的处理单元是累加器型运算器，把累加寄存器RGA中的数据和存储器中的数据进行运算。结构保留在累加寄存器RGA中，每个处理单元内有一个数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送，并有一个屏蔽触发器用来控制让该PUi是否被屏蔽掉，使之不参与向量指令的操作。
6.2.3 ILLIAC IV的并行算法距离。
1.矩阵加
2.矩阵乘
3.累加和
在ILLIAC IV上可以实现累加和的并行运算，但由于屏蔽了部分处理单元，降低了他们的利用率，速度不是提高N倍，而是log2N倍
6.3 SIMD计算机的互联网络
6.3.1 互联网络的设计目标与互联函数
SIMD系统的互联网络的设计目标是：结构不要过分复杂，以降低成本；互联要灵活，以满足算法和应用的需求；处理单元间信息交换所需的传送步数要尽可能少，以提高速度性能；能用规整单一的基本构建组合而成，或者经多次通过或者经多级连接来实现复杂的互联，使模块性好，以便于用VLSI实现并满足系统的可扩充性。
为反映互连特性，每种互联网络可能一组互联函数定义，常用一种简单的函数式来表示，即把所有入端x和出端f(x)都用二进制编码，从两者的二进制编码上找出其函数规律。
6.3.2 互联网络应抉择的几个问题
在确定PE之间通信的互联网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结构做出抉择。
操作方式有同步、异步和同步与异步组合3中。
阵列处理机根据其SIMD性质，均采用同步操作方式，让所有PE按时钟同步操作，异步或组合操作方式一般多用于多处理机。
典型的互联网络时由许多开关单元和互联线路组成，互联通路的路径选择是通过置定开关单元的工作状态来控制的，可以有集中和分布两种控制策略。
交换方法主要有线路交换、包交换及线路与包交换组合3种。
线路交换是在源和目的间建立实际的连接通路，一般适合于大批量数据传输。
包交换是将数据置于包内传送，不用建立实际的连接通路，对短数据信息传送特别有效。
SIMD互联网络多采用硬连的线路交换。包交换则多用于多处理剂和计算机网络中。
网络的拓扑结构指的是互联网络入、出端可以连接的模式，有静态和动态两种，在静态拓扑结构中，两个PE之间的链是固定的，总线不能重新配置成其他PE相连。而动态拓扑结构中，两个PE之间的链通过置定网络的开关单元状态可以重新配置。
静态拓扑有一维的现形，二维的环型、星型、树型、胖树型、网络型、脉动阵列型，三维的弦环型、立方体型、环立方体型，以及其他复杂的连接形式。
静态网络的灵活性和适应性差，很少使用。
动态网络有单级和多级两类。
只有有限的几种连接，必须经过循环多次通过，才能实现任意两个处理单元之间的信息传送，称为动态单级网络（循环网络）
多个单级网络串联组成，以实现任意两个处理单元之间的连接，将多级互联网络循环使用，实现复杂的链接，称为多级循环网络（循环多级网络）
循环互连网络比多级互联网络节省设备，但通过时间长，对网络控制要求较高。
多级互联网络虽增加了设备和成本，但缩短了通过实践，使速度提高，而且利用不同的单级互联网络组合，可产生有不同特性和连接模式的多级互联网络，灵活性好。
目前由于器件价格明显下降，绝大多数阵列处理机都采用多级互联网络或多级循环互联网络。
循环互联网络的模型
6.3.3 基本的单级互联网络
1.立方体单级网络
立方体（Cube）单机网络名称来自三维立方体结构，立方体的每个顶点（网络的结点）代表一个处理单元。共有8个处理单元，用zyx三位二进制编码编号。它所能实现的入。出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他3个处理单元上。
例如：010只能连接到000、011、110
三维立方体单机网络有3种互连函数：Cube0、Cube1和Cube2
a)Cube0 b)Cube1 c)Cube2
推广到n维时，N个结点的立方体单级网络共有n=log2N种互联函数，即
式中，Pi为入端标号二进制码的第i位，且
当维数n>3时，称为超立方体（HyperCube）网络。
单级立方体网络的最大距离为n，即反复使用单级网络，最多经n次传送就可以实现任意一对入、出端间的连接。而且任意两个结点之间至少有n条不同的路径可走，容错强，只是距离小于n的两个结点之间的各条路径的长度可能不等。
2.PM2I单级网络
PM2I单级网络是“加减2”（Plus-Minus 2i）单级网络的简称。能实现与j号处理单元直接相连的是号为的处理单元，即：
式中，。它共有2n个互联函数。
由于，因此PM2I互连网络只有2n-1种互连函数是不同的。
处理器间用单向环网或双向环网互连，是PM2I网络的特例，采用PM2+0、PM2-0或PM2±0互连函数。ILLIAC IV处理单元的互联也是PM2I的特例，采用了PM2+0、PM2±3。
PM2I单级网络的最大距离为。由三维PM2I互连网络可以看出，最多只要两次使用，即可实现任意一对入出端号间的连接。
3.混洗交换单级网络
混洗交换单级（Shuffle-Exchange）网络包含两个互连函数，一个是全混（Perfect-Shuffle），另一个是交换（Exchange）。
全混连接规律是把全部按编码顺序排序的处理单元从当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。
互连函数表示为
式中，为入端编号的二进制码。
Shuffle函数不是可逆函数。如果把出端当做入端，入端当做出端，则原网络变为另一个互连网络，是原网络的逆网络。
在混洗交换网络中，最远的两个入、出端号是全0和全1，它们的连接需要n次交换和n-1次混洗，所以其最大的距离为2n-1。
4.蝶形单级网络
蝶形单级网络（Butterfly）的互连函数为
即将二进制地址的最高位和最低位相互交换位置
