第4章SIMD计算机

2019/12/201•第1章计算机系统设计基础•第2章数据表示与指令系统性能分析•第3章流水技术和向量处理•第4章阵列计算机•第5章多处理机系统•第6章数据流计算机2019/12/202超级计算机---6种机器模型•SIMD阵列计算机•并行向量处理机(PVP)•对称多处理机(SMP)•大规模并行处理机(MPP)•工作站机群(COW)•分布式共享存储多处理机(DSM)2019/12/2032019/12/204第4章阵列计算机4.1并行处理技术的基本概念4.2SIMD并行处理机结构4.3SIMD并行计算机算法4.4SIMD计算机的互连网络4.5相联处理机WuhanUniversity2019/12/205本章学习要求•了解并行性的基本概念、比较阵列机与多机系统并行性的特点•掌握典型的两种阵列机结构•重点掌握阵列机中的互连网络•了解相联处理机2019/12/2061.并行性在数值计算，数据处理，知识处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。包括同时性和并发性同时性（simultaneity）:指两个或多个事件在同一时刻发生在多个资源中。并发性（concurrency）:指两个或多个事件在同一时间间隔内发生在多个资源中在同一时刻或同一时间间隔内完成多个性质相同或不同的任务4.1并行处理的基本概念2019/12/2072.并行处理是一种相对串行处理的信息处理方式，侧重并发性。(1)并行性粒度当TC较大时，通信量大，则G较小，处理粒度较细。反之对于粗粒度的并行，通信量较小。粗粒度通常采用MIMD，细粒度则采用SIMD。picipiwiwttTcTG11)()(和所有处理器通讯时间总和所有处理器运算时间总2019/12/208(2)并行性等级划分作业级（程序）任务级（过程或程序段）子任务级（例行程序，或子程序）指令或语句循环或递归循环级5级4级3级2级1通信需求与调度开销并行程度粗粒度中粒度细粒度MIMD方式侧重软件SIMD方式侧重硬件2019/12/209①指令级：并行性发生在指令内部微操作之间或指令之间。取决于程序的具体情况。可借助于优化编译器开发细粒度并行性。②循环级：相当于迭代循环操作，典型循环包含的指令大约几百条，循环级并行性是并行机或向量计算机上运行的最优程序结构，并行处理主要由编译器在循环级中进行开发。③子任务级：属于中粒度。子程序是在单处理机或多处理机的多道程序设计这一级进行的。④任务级：这是与任务、过程、程序段、协同程序级相对应的中粒度或粗粒度规模。典型粒度包含的指令几千条，检测本级的并行性比细粒度级困难得多，需要更多地涉及过程间的相关性分析。⑤作业（程序）级：对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。2019/12/2010提高计算机系统的并行性的技术途径：(单机系统)时间重叠（TimeInterleaving）：在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。资源重复（ResourceReplication）：并行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。3、并行处理技术及发展2019/12/2011资源共享（ResourceSharing）：利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地提高整个系统的性能。例如多道程序分时系统.2019/12/20124.2SIMD并行计算机并行处理机又叫SIMD计算机。它是单一控制部件控制下的多个处理单元构成的阵列，所以又称为阵列处理机。多处理机是由多台独立的处理机组成的系统。本节主要介绍并行计算机的硬件结构2019/12/2013一、并行处理机的基本构成•并行处理机是通过重复设置大量相同的处理单元PE（ProcessingElement），将它们按一定的方式互连，在统一的控制部件CU（ControlUnit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。各PE之间的数据交换由ICN来实现。•从CU看，指令是串行执行的，从PE看，数据是并行处理的。按照佛林分类法，它属于SIMD计算机。•并行处理机的应用领域：主要用于高速向量或矩阵运算中。SIMD并行计算机（阵列处理机）2019/12/2014•并行处理机的操作模型可用五元组来表示：M＝(N，C，I，M，R),•其中：N为PE个数。如IlliacIV有64个PE。C为由控制部件CU直接执行的指令集，包括标量指令和程序控制指令。I为所有PE并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。M为屏蔽操作集，每种屏蔽将PE划分为允许操作和禁止操作两个子集。R是数据寻径集，说明互连网络中PE间通信所需要的各种设置模式。2019/12/2015二、并行处理机分类并行处理机根据存贮器采用的组成方式不同分成两种基本结构。1.分布存贮的并行处理机–各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器（ProcessingElementMemory）PEM。–在控制部件CU内设有一个用来存放程序的主存贮器CUM。整个系统在CU统一控制下运行系统程序和用户程序。2019/12/2016具有分布式存储器的并行处理机结构形式互连网络ICNPE0PE1PEM0PEM1PEMN-1PEN-1CUCUMI/O接口D管理处理机SC控制数据总线控制……控制总线后端处理机2019/12/2017•工作原理：所有指令都在控制部件中进行译码。译码后把只适合串行处理的标量或控制类指令留给控制部件自己执行，而把适合于并行处理的向量类指令“广播”给各个处理单元(PE)，控制让处于“活跃”的那些PE去并行地执行。各个处理单元可直接访问自已的局部存储器(PEM)，但它们之间的数据交换由互连网络(ICN)来实现。2019/12/20182.共享存贮的并行处理机每个PE没有局部存储器，存储模块以集中形式为所有PE共享。互连网ICN受CU控制，具有双向性，采用分布式存贮器组成基本结构。在采用集中式共享主存的构型中，K个存贮分体的数据经处理单元－主存模块互连网络ICN为全部N个处理单元所共享，要求K≥N。各处理单元在访问主存时,为避免发生分体冲突,也要求有合适的算法能将数据合理地分配到各个存储体中。2019/12/2019具有集中式共享主存的并行处理机结构形式PE0PE1PEN-1ICNMM0MM1I/O-CHI/OSMCUSCMMK-1……控制控制…2019/12/2020三、并行(阵列)处理机的结构特点–速度快，特别适于高速数值计算。–SIMD依靠的是资源重复，而不是时间重叠。它依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。–依赖于互连网络和并行算法。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。–不同结构对应的并行算法的实现方法不同，ICN的研究成为并行处理的又重点问题之一。–需要有一台高性能的标量处理机。2019/12/2021并行处理机与流水处理机的比较•流水处理机–方式：时间重叠，并行性中的并发性–粒度：细粒度–灵活性：好–系统评价：成本低，速度受限•并行处理机–方式：资源重复，并行性中的同时性–粒度：粗粒度，操作级–灵活性：差–系统评价：成本高，速度潜力大2019/12/2022四、并行处理机举例——ILLIAC-IV•1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位的浮点数，每个局部存储器PEM为2KX64位，总的运算速度为1GFLOPS。•美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1/20的速度。只实现了8X8＝64个PE，只达到50MFLOPS。•Illiac-IV系统的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。•用于天气预报、核物理工程及高速科学运算。2019/12/20232019/12/2024ILLICA-IV构成•Illiac-IV系统由三大部分组成：IlliacIV处理机阵列，阵列控制器CU，一台标准的BurroughsB6700输入输出计算机。2019/12/2025•每一个PUi只和它的东、西、南、北四个近邻直接连接。{PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64}•南北方向上同一列的PU连成一个环，东西方向上构成一个闭合螺线。•采用闭合螺线最短距离不超过7步。而普通网格最短距离不超过8步。1、处理单元阵列：由64个PUi构成,每个PUi包括(PEi和PEMi)由64个结构完全相同的处理单元PEi构成，每个处理单元PEi字长64位，PEMi为隶属于PEi的局部存储器，每个存储器有2K字，全部PEi由CU统一管理。2019/12/2026ILLIAC-IV的处理单元互连图2019/12/20272019/12/2028RGRRGBRGXRGARGMRGSMARAULUSUADAMUXT/R东西南北PEM、CUCUMLU每个PE逻辑框图MLU2019/12/20292、阵列控制器CU：相当一台小型控制计算机–阵列控制器CU实际上是一台小型控制计算机。对阵列处理单元实行控制和完成标量操作。标量操作与各PE的数组操作可以重叠执行。–控制器的功能有以下四个方面：(1)对指令进行译码，并执行标量指令；(2)向各处理单元发出执行数组操作指令所需的控制信号；(3)产生和向所有处理单元广播公共的地址和数据；(4)接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2019/12/2030具有分布式存储器的并行处理机结构形式互连网络ICNPE0PE1PEM0PEM1PEMN-1PEN-1CUCUMI/O接口D管理处理机SC控制公共数据总线CU……控制总线后端处理机2019/12/20313、I/O系统•IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。•磁盘文件系统是两套大容量并行读写磁盘系统及其相应的控制器•I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。•B6700管理计算机的作用是：管理全部系统资源，完成用户程序的编译或汇编，进行作业调度、存储分配、产生输入输出控制描述字送到CDC、处理中断，以及提供操作系统所具备的其他服务。2019/12/2032B67002019/12/2033并行处理机举例——BSP科学计算机2019/12/2034指令译码控制部件处理器存储器NW2NW117个存储块16个处理单元对准网络2（NW2）对准网络1（NW1）BSP的五级数据流水线构图（集中式共享存贮器）2019/12/2035BSP五级数据流水线的工作过程：（1）由17个存储器模块并行读出16个操作数；（2）经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序；（3）将排列好的16个操作送到并行处理单元完成操作；（4）所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序；（5）写入存储器；2019/12/2036无访问冲突的并行存储器•一维数组的无冲突访问（不讲）•行列相等的二维数组的无冲突访问•行列不相等的二维数组的无冲突访问•注：二维数组的无冲突访问是通过对数组元素的非顺序存储（错位存储）实现的。2019/12/20374x4二维数组无冲突访问的实现a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a33a00a01a02a03a13a10a11a12a21a22a23a20a30a31a32a33体号0123体