计算机系统结构(ch-5)重点分析.ppt

第5章 并行处理技术 5.1 计算机系统结构中并行性的发展 5.2 SIMD并行处理机 5.3 SIMD计算机的互连网络 5.4 网络特性 5.5 静态互接网络 5.6 动态互接网络 5.1 计算机系统结构中并行性的发展 5.1.1 并行性的基本概念 1、并行性的定义 指在数值计算、数据处理、信息处理或是人工智能等求解过程中可能存在某些可同时进行运算或操作的部分。 开发并行性的目的是为了能进行并行处理，以提高计算机系统求解问题的效率。 并行性有二重含义，即同时性(simultaneity)和并发性(concurrency)。同时性是指多个事件在同一时刻发生；并发性是指多个事件在同一时间段内发生。 5.1.1 并行性的基本概念 2、并行处理的概念 是指一种相对于串行处理的信息处理方式，它着重开发计算过程中存在的并发事件。 进行并行处理时，每次处理的规模大小可能是不同的，这可用并行性颗粒度(granularity)来表示。 粗粒度开发主要采用MIMD方式，开发功能并行性；细粒度开发主要采用SIMD方式，开发数据并行性。 5.1.1 并行性的基本概念 5.1.2 并行性技术的实现途径 1.时间重叠（time interleaving） 引入时间因素，多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。 2.资源重复（resource replication） 是指在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。 3.资源共享（resource sharing） 是指利用软件的方法让多个任务按一定的时间顺序（分时）轮流地使用同一套资源，以提高其利用率，这样相应地也可以提高整个系统的性能。 5.1.3 计算机系统结构中并行性的发展 5.2 SIMD并行处理机 5.2.1 SIMD并行处理机的基本结构与特点 按存储器的组成方式不同分为两类 分布式存储器结构 集中式共享存储器结构 1. 分布式存储器结构 2. 集中式共享存储器结构 3. SIMD并行处理机的主要特点 (1)SIMD并行处理机利用的是资源重复，而不是时间重叠，利用并行性中的同时性，而不是并发性； (2)SIMD并行处理机是以某一类算法为背景的专用计算机； (3)SIMD并行处理机的研究必须与并行算法的研究密切结合，以使它的求解算法的适应性更强一些，应用面更广一些； (4)从处理单元上看，由于各处理单元都是相同的，因而可将SIMD并行处理机看成是一个同构型并行处理机。但从整体上看又是一个异构的多处理机系统（主机、处理单元阵列、标量处理机） 5.2.2 ILLIAC-IV的处理单元阵列结构 是世界上最早采用SIMD结构的计算机，美国宝来公司和伊利诺依大学1965年开始研制，1972年正式生产。采用分布式存储器结构。 阵列共由64个处理部件组成，排列成平面8×8阵列结构，每一个PU都与其四个邻近的PU相连，即按上、下、左、右方向可以与其它PU通信。 PU在连接上采用了纵向连环，横向闭合螺线，又称闭合螺线阵列。 在n×n个PU组成的阵列中，这种连接可以使任意两个PU间的最短距离不超过（n-1）步。 5.2.2 ILLIAC-IV的处理单元阵列结构 5.2.3 阵列处理机的并行算法 1. 矩阵加并行算法 设A和B是n×n阶矩阵，A、B的和矩阵为C，它也是n×n阶矩阵。矩阵加的算法为： A+B=C=(cij)n×n cij=aij + bij 1. 矩阵加并行算法 P≥n2 TP = t加 P＜n2 2. 矩阵乘并行算法 设A和B是n×n阶矩阵，A、B的乘积矩阵为C，它也是n×n阶矩阵。矩阵乘的传统串行算法为： A×B=C=(cij)n×n (1)若处理单元的个数P＜n2 (1)若处理单元的个数P＜n2 计算Cij时，需要所有子矩阵块Aik、Bkj(0≤k≤m-1)，因此A的块在处理机阵列每行作多对多广播，而B的块在处理机阵列每列作多对多广播。当Pij接收完Ai0，Ai1，…，Ai(m-1)；B0j，B1j，…，B(m-1)j后，执行子矩阵乘法和加法运算。 计算时间 用Pij计算Cij时，需对(n/m×n/m)阶子矩阵中的每个元素cij进行n次乘法和n次加法(cij=Σaikbkj)，故Pij的运行时间为： n×n/m×n/m×(t乘+t加)=n3/m2×(t乘+t加)=n3/P×(t乘+t加) 通信时间 ts：发送消息的启动时间，tw：传送每个浮点数时的通信时间，由于需要在m台处理机组成的组中作二次多对多广播，每次包含处理机阵列上所有行或列的m次并发广播，发送消息的个数由n2/P个元素的子矩阵组成，所以整个通信时间为：2(mts + mn2/P