第6章计算机系统

6.2并行处理技术的发展6.3SIMD并行处理机6.4多处理机结构6.5多处理机高速缓冲存储器（cache）一致性6.5多处理机举例第六章、并行处理技术和多处理机6.1概述6.6并行处理软件本章重点书P2526.1~6.9一并行性概念并行处理是一种有效的强调开发计算过程中并行事件的信息处理方式.在数值计算，数据处理，知识处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。同时性（simultaneity）:指两个或多个事件在同一时刻发生在多个资源中。并发性（concurrency）:指两个或多个事件在同一时间间隔内发生在多个资源中6.1概述在同一时刻或同一时间间隔内完成多个性质相同或不同的任务1．从计算机信息加工步骤和阶段看，并行性等级可分为：存贮器操作并行----并行存贮器系统和以相联存贮器为核心构成的相联处理机。处理器操作步骤并行----可以是一条指令的取指、分析、执行等操作步骤，也可以是具体运算。处理器操作并行----为支持向量、数组运算，可以通过重复设置处理单元进行，如并行处理机指令、任务、作业并行----称为较高级并行，属于多指令流多数据流计算机。二.并行的等级和分类2.从系统结构发展看:高性能的单处理机,SIMD并行处理机,多处理机,多计算机系统非冯.诺依曼计算机(属于多处理机系统)并行性的开发还可以按程序大小划分不同粒度的开发方式。我们先来介绍两个概念：颗粒规模（grainsize）或粒度（granularity）----是衡量软件进程所含计算量的尺度。测量方法是数一下颗粒（程序段）中的指令数目。一般用细、中、粗来描述，时延-（TC）是机器各子系统间通信开销的时间量度。如：存贮时延是处理机访问存贮器所需时间；同步时延是两台处理机互相同步所需的时间。3.程序划分和粒度并行性粒度：每次并行处理的规模大小。用字母G表示G=TW/TCTW：所有处理器进行计算的时间总和；TC：所有处理器进行通信的时间总和。（设系统共有P个处理器）当TC较大时，通信量大，则G较小处理粒度较细。反之对于粗粒度的并行，通信量较小。作业级（程序）任务级（过程或程序段）子任务级（例行程序，或子程序）指令或语句循环或递归循环级5级4级3级2级1通信需求与调度开销并行程度粗粒度中粒度细粒度现代计算机程序运行并行性级别五种程序执行级别体现了不同的算法粒度规模以及通信和控制要求的变化。级别越低，软件进程的粒度越细。一般情况，程序可在这些级别的组合状态下运行。（1）指令级：并行性发生在指令内部微操作之间或指令之间。取决于程序的具体情况。可借助于优化编译器开发细粒度并行性，它能自动检测并行性并将源代码换成运行时系统能识别的并行形式。（2）循环级：相当于迭代循环操作，典型循环包含的指令大约几百条，循环级并行性是并行机或向量计算机上运行的最优程序结构，并行处理主要由编译器在循环级中进行开发。（3）子任务级：属于中粒度。子程序是在单处理机或多处理机的多道程序设计这一级进行的。这一级并行性由算法设计者或程序员开发而非用编译器开发。（4）任务级：这是与任务、过程、程序段、协同程序级相对应的中粒度或粗粒度规模。典型粒度包含的指令几千条，检测本级的并行性比细粒度级困难得多，需要更多地涉及过程间的相关性分析。需编译器支持。（5）作业（程序）级：对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。小结：细粒度并行性常在指令级或循环级上借助于并行化或向量化编译器来进行开发的。任务或作业步骤（过程级）中粒度并行性开发需要程序员和编译器的共同作用。开发程序作业级的粗粒度并行性主要取决于高效的操作系统和所用算法的效率。共享变量通信常用于支持中、细粒度计算。消息传递型多计算机用于中粒度和粗粒度的计算。通常情况下，粒度越细，并行性潜力越大，通信和调度的开销也越大。细粒度能提供较高的并行度，但与粗粒度计算相比，其通信开销也较大。大规模并行性通常是在细粒度级上开发。如：SIMD或MIMD计算机上开发的数据并行性。提高计算机系统的并行性的技术途径：(单机系统)时间重叠（TimeInterleaving）：在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。资源重复（ResourceReplication）：并行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。资源共享（ResourceSharing）：利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地提高整个系统的性能。例如多道程序分时系统.6.2并行处理技术及发展(多机系统)功能专用化,机间互连,网络化技术途径发展成异构型多处理机,同构型多处理机,分布式处理机系统多道程序分时系统虚拟存储器多终端远程终端分布处理系统局域计算机网通信处理机计算机网多存储体多操作部件相联处理机并行处理机同构型多处理机系统可重构,容错多处理机紧密耦合系统现行控制高速缓存指令操作宏流水线异构型多处理机系统高级语言数据库处理机松散耦合系统、专用外围处理机多计算机系统单处理机资源共享资源重复时间重叠多机互连功能专用化网络化并行处理技术发展一、并行处理机的基本构成并行处理机是通过重复设置大量相同的处理单元PE（ProcessingElement），将它们按一定的方式互连，在统一的控制部件CU（ControlUnit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。并行处理机的控制部件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行，最多加上使用指令重叠或流水线的方式工作。指令重叠是将指令分成两类，把只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行处理的向量类指令播送到所有处理单元，控制让处于活跃的那些处理单元去并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。6.3SIMD并行计算机（阵列处理机）二并行处理机分类并行处理机根据存贮器采用的组成方式不同分成两种基本构成。（1）分布存贮的并行处理机各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器（ProcessingElementMemory）PEM。在控制部件CU内设有一个用来存放程序的主存贮器CUM。整个系统在CU统一控制下运行系统程序的用户程序。执行主存中的用户程序指令播送给各个PE，控制PE并行地执行。（2）共享存贮的并行处理机。每个PE没有局部存触器，存储模块以集中形式为所有PE共享。互连网IN受CU控制，具有双向性采用分布式存贮器组成基本结构。…ICNPE0PE1PEN-1MM0MM1MMN-1CUSCI/O-CHI/OSM……PEM0PE0PEM1PE1PEMN-1PEMN-1ICNCUCUMI/O接口DSC（A）具有共享存贮器并行处理机结构（B）分布存贮器并行处理机结构ILLIAC-IV结构（分布存贮器并行处理机结构）•处理单元阵列由64个PUi构成,每个Pui包括(PEi和PEMi)由64个结构完全相同的处理单元PEi构成，每个处理单元PEi字长64位，PEMi为隶属于PEi的局部存储器，每个存储器有2K字，全部PEi由CU统一管理，PEi都有一根方式位线，用来向CU传送每个PEi的方式寄存器D中的方式位，使CU能了解各PEi的状态是否活动，作为控制它们工作的依据。•阵列控制器CU相当一台小型控制计算机对处理单元阵列实现控制,(发控制信号,广播公共地址,广播公共数据)对指令流进行译码控制,利用CU内部资源可以进行标量操作,接受和处理各类中断，其他输入输出操作。•I/O系统由磁盘文件系统DFS，输入输出子系统和宿主计算机S/C构成（驻留操作系统，编译程序，I/O服务程序等）012047PEM0。。。。012047PEM1。。。。012047PEM63。。。。XDABRSPE0XDABRSPE1PE630163。。。。ACAR0ACAR1ACAR2ACAR3ALU控制器CU累加器ADB............方位总线指令控制线CU总线......到PE63到PE0ILLIAC-IV的处理单元原理图…...D为方式位寄存器R路由器互连用PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU57PU58ILLIAC-IV的处理单元互连图将PU63传送到PU10，最快可经PU63→PU7→PU8→PU9→PU10。（1）并行处理机：并行机中每个处理器以160ns的时钟周期进行向量计算。所有16个算术单元AE对不同的数据组（从并行处理机控制器广播来）进行同一种指令操作。（2）控制处理器：除了用以控制并行处理机以外，还提供了与系统管理机相连的接口。（3）文件存储器：半导体辅助存储器。BSP的计算任务文件从系统管理机加载到它上面。然后对这些任务进行排队，由控制处理机加以执行。（4）对准网络：包完全交叉开关以及用来实现数据从一个源广播至几个目的地以及当几个源寻找一个目的地地址时能分解冲突的硬件。这就需要在算术单元阵列和存储器模块之间具备通用的互连特性。而存储模块和对准网络的组合功能则提供了并行存储器的无冲突访问能力。算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能。科学处理机BSP系统结构（集中式共享存贮器)指令译码控制部件处理器存储器NW2NW117个存储块16个处理单元对准网络对准网络BSP的五级数据流水线构图（集中式共享存贮器）作用：（1）由17个存储器模块并行读出16个操作数；（2）经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序；（3）将排列好的16个操作送到并行处理单元完成操作；（4）所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序；（5）写入存储器；BSP的五级数据流水线在BSP中，存储器-存储器型的浮点运算是流水进行的。BSP的流水线组织由五个功能级组成。尤其是并行处理机包括有16个处理单元、17个存储器模块和2套互连网络（亦称对准网络）组合在一起，就形成了一条五级的数据流水线，使连续几条向量指令能在时间下重叠起来执行。共同特点：可以通过各种途径把它们转化成为对数组或向量的处理，利用多个处理单元对向量或数组所包含的各个分量同时进行运算，从而易于获得很高的处理速度。三并行处理机的特点并行处理机有如下特点：（1）利用资源重复（空间因素）而非时间重叠。（2）利用同时性而非并发性。它的每个处理单元在同一时刻要同等地担负起各种运算功能。（3）提高运算速度主要是靠增大处理单元个数，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多。（4）使用简单而又规整的互连网络来确定多个处理单元之间的连接模式。（5）并行处理机（阵列机）研究必须与并行算法研究密切结合，使之适应性更强，应用面更广。6．3．2SIMD并行处理机算法一．矩阵加矩阵加(配比加)是最简单的情况。假定两个8*8的矩阵A，B，相加，所得结果矩阵C也是一个8*8的矩阵。设AB的分量元素分别存在PEMi的Z,Z+1单元中,所得结果矩阵C各分量存在PEMi的Z+2单元中用下面三条指令可一次完成(64个处理单元并行)LDAZ；全部（Z）由PEMi送到PE的累加器RGAiADRNZ+1；全部（Z+1）与（RGAi）进行浮点规舍加结果送RGAiSTAZ+2；全部（RGAi）由PE送到DEMi的（Z+2）单元这里0≤i≤63ZZ+1Z+2A（0，0）B（0，0）C（0，0）PEM0A（0，1）B（0，1）C（0，1）PEM1A（7，7）B（7，7）C（7，7）PEM63......矩阵加存储器分举例矩阵乘是涉及二维数组运算。它比矩阵加复杂的多。设A，B和C为3个8*8的二维矩阵。若给定A和B，则