并行处理机基础.doc

第八章 并行处理机和多处理机【学习指南】一.首先透切理解以下基本概念：并行处理机基本结构、SIMD计算机基本结构、阵列处理机基本结构、IMD计算机的优缺点、共享存储多处理机、分布存储多处理机、多处理机系统的特点、MPP、SMP、机群系统。1. SIMD计算机模型（1）SIMD计算机的抽象模型在同一个控制部件的管理下,有多个处理单元。所有处理单元均收到从控制部件广播来的同一条指令，但操作对象是不同的数据。（2）SIMD计算机的操作模型SIMD计算机的操作模型用五元组表示：M = （N，C，I，M，R）。其中, 五元组中各符号的含义：N-机器的处理单元（PE）数；C-由控制部件（CU）直接执行的指令集，包括标量和程序流控制指令；I-由CU广播至所有PE进行并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其他由每个活动的PE对它的数据所执行的局部操作；M-屏蔽方案集，其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集；R-数据寻径功能集，说明互连网络中PE间通信所需要的各种设置模式。（3）可以用上述五元组描述一台具体的SIMD机器。（4）SIMD计算机处理单元的粒度：细粒度、中粒度。2. SIMD计算机的基本结构（1）分布式存储器结构分布式存储结构的体系模型、工作原理和特点。（2）共享存储器结构共享存储结构的体系模型、工作原理和特点。3. SIMD计算机的特点(1) SIMD计算机的实质是利用了多PE的空间并行性来提高计算速度。(2) SIMD计算机与流水线向量处理机的相同与不同。4. 多处理机结构由如何台独立的计算机组成，每台计算机能够独立执行自己的程序，又称多指令流多数据流（MIMD）结构。多处理机系统中的处理机之间通过某种方式（如互连网络）互连，从而实现程序之间的数据交换和同步。5. 使用多处理机的主要目的是利用多台处理机并发地执行一个作业，使得执行速度比单处理机快；有时候，使用使用多处理机的主要目的是提高可靠性而不是高性能，如果某台处理机出现故障，那么它的程序可以由系统中其它处理机来执行。6. 多处理机有两种基本的结构：共享存储器结构和本地存储器结构。共享存储器方案中，存储器和I/O设备是独立的子系统，为所有处理机所共享，这是实现信息交换和同步最简单的办法，任何两台处理机都可以通过共享存储器的单元实现通信。本地存储器结构每台处理机都有自己的存储器和I/O设备，处理机之间通过点对点的信息交换实现通信。7. 多处理机的主要特点包括：（1） 结构的灵活性。与SIMD计算机相比，多处理机的结构具有较强的通用性，它可以同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。（2） 程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并行性体现在指令外部，即表现在多个任务之间。（3） 并行任务派生。多处理机是多指令流操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。（4） 进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。8. 如果多处理机系统以峰值速度运行时，所有处理机都在做着有用的工作，并且忽略通信开销，那么N台处理机所构成的多处理机系统其效率和性能应该是单个处理机的N倍。实际上，由于以下原因，多处理机的峰值性能很难达到：多处理机间的通信延迟；处理机间的同步开销；没有足够多的任务时，若干台处理机处于空闲状态或执行无关工作；系统控制和操作调度所需的开销。多处理机的性能很大程度依赖于R/C比值，其中R代表程序的执行时间，C代表用于通信的开销。常见的多处理机性能模型包括：基本模型、随机模型、通信开销为线性函数的模型、完全重叠通信的理想模型、具有多条通信链的模型等。9. 在并行多处理机系统中的私有Cache会引起Cache中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache一致性问题。（1） 出现Cache一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。共享可写数据引起的不一致性。比如P1、P2两台处理机各自的本地高速缓冲存储器C1、C2中都有共享存储器是M中某个数据X的拷贝，当P1把X的值变成X/后，如果P1采用写通过策略，内存中的数据也变为X/，C2中还是X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。（2） 进程迁移引起的数据不一致性。P1中有共享数据X的拷贝，某时刻P1进程把它修改为X/并采用了写回策略，由于某种原因进程从P1迁移到了P2上，它读取数据时得到X，而这个X是“过时”的。（3） I/O传输所造成的数据不一致性。假设P1和P2的本地缓存C1、C2中都有某数据X的拷贝，当I/O处理机将一个新的数据X/写入内存时，就导致了内存和Cache之间的数据不一致性。10. 有两类解决Cache不一致性问题的协议机制：监听协议和基于目录的协议，它们实用于不同的系统结构。11. 多处理机系统主要有四类：第一类是多向量处理系统，以CRAY YMP-90、NEC SX-3和FUJITSU VP-2000等为代表；第二是基于共享存储的多处理机系统（SMP，shared memory mulptiprocessors），如SGI Challenge和Sun SparcCenter 2000；第三类是基于分布存储的大规模并行处理系统（MPP），比如Intel Paragon、CM-5、Gray T3D等；第四类是机群系统。二.通过做例题和习题，会做下列类型的计算题：(1)在SISD计算机和MIMD计算机计算内积公式的步骤(2)在SIMD计算机和MIMD计算机计算内积公式的步骤题分别确定在下列两种计算机系统中，计算表达式所需的时间：s=A1*B1+A2*B2+A4*B4。 (a) 有4个处理器的SIMD系统；(b) 有4个处理机的MIMD系统。设访存取指和取数的时间可以忽略不计；加法与乘法分别需要2拍和4拍；在SIMD和MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在SIMD系统中，PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的的通路。答假设4个PE分别为PE0，PE1，PE2，PE3。利用SIMD计算机计算上述表达式，4个乘法可以同时进行，用时=4个时间单位；然后进行PE0到PE1，PE2到PE3的数据传送，用时=1个时间单位。在PE1和PE3中形成部分和，用时=2个时间单位。接着进行PE1到PE3的部分和传送，用时=1*2=2个时间单位。最后，在PE3中形成最终结果，用时=2个时间单位