并行处理技术.ppt

《并行处理技术.ppt》由会员分享，可在线阅读，更多相关《并行处理技术.ppt（131页珍藏版）》请在三一文库上搜索。

1、第六章 并行处理技术,什么是并行处理 为什么要开发并行处理技术 并行机的分类及基本结构 并行处理的基本问题和技术,主要内容,多个处理单元(a collection of computing elements) 协作、通信（ cooperate 广播 (Broadcast):一个源节点到全体节点； 会议 (Conference):多个源节点到一个目的节点。,多处理器通信问题,1).消息、包和片 消息（Message）：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。 包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-

2、512位。 片（Flit）：片的长度固定，一般为8位。 它们的相互关系如下图：,基本术语与性能指标,包,消息,基本术语与性能指标,2).互连网络 互连网络用来在多处理机(计算机)系统的处理结点之间传递消息。,互连网络性能的两个重要指标： 传输时延（Transmission Latency） 吞吐量（Throughput）,互连网络的描述： 拓扑（Topology） 寻径算法（Routing） 流控制（Flow Control）,基本术语与性能指标,3).传输时延与吞吐量 一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。,基本术语与性能指标,一个网络的传输时

3、延：在一定条件下发送消息的平均时延。,网络的吞吐量：单位时间内网络所能传输的消息数目或长度。,基本术语与性能指标,4).传输时延的公式,其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下：,基本术语与性能指标,建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。,其中： Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。 Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。,基本术语与性能指标,基本术语与性能指

4、标,网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。,其中： TpD称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延，D为源结点与目的结点之间中间结点的数量。,中间结点上的平均时延,中间结点的数量,L/B称为线路时延：其中L为消息长度， B为结点之间的通道带宽。,基本术语与性能指标,阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。,基本术语与性能指标,5).网络的拓扑结构 第一代并行计算机：HyperCube TMC: CM-2 Intel: iPSC nCUBE 第二代并行计算机：nMesh Stanford: Dash

5、 MIT: Alewife Intel: Paragon,基本术语与性能指标,6).网络的寻径算法 决定发送一个消息到其目的地所经过的路径。 可以分为： 最短路径算法 非最短路径算法 或者： 确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。 可适应算法：消息从结点A到结点B可以由几条不同的路径。,基本术语与性能指标,7).网络的流控制 当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。,基本术语与性能指标,1)、同步通信方式 同步通信方式是指发送节点和接收节点在时间上和空间上都要同步动作，任何一个环节发生问题，都会形成阻塞。 所谓时间上的同步是指发送节点

6、和接收节点必须在做好传送准备后，才能开始进行消息传递。 所谓空间上的同步是指从源节点到目的节点的通信路径都已开通。,通信方式,因发生阻塞而使计算机节点等待的时间称为同步时间。 处于等待状态的处理机是空闲的，特别是通信距离长时，每经过一个中继点，就会发生同步，是同步时间过长，并行处理的效率下降。 在同步方式下，一般不设置通信缓冲区，一次传送的数据量不受缓冲区大小的限制。,通信方式,2)、异步通信方式 异步通信方式是指在通信通道上设置足够大的缓冲区，发方计算机将消息写入缓冲区，在缓冲区写满之前，不必等待收方节点接收消息；而接收方只需在必要的时候，从缓冲区中把数据读走。 在时间上，收发双方不必同步。

7、在空间上，只要缓冲区不满，发方就可以写；缓冲区不空，收方就可以读。 异步方式需要足够大的缓冲区，增加了硬件开销，但它是非阻塞的通信系统。,通信方式,同步方式下，发送的数据量和接收的数据量必须相等；而异步方式下没有这种要求，因此，异步方式可以增加并行程序的灵活性。 从速度上看，同步方式是收发双方同时工作，数据依次传递成功，而异步方式下，收发双方与缓冲区之间需要传递两次，因此异步方式所用时间较长。,通信方式,在使用总线方式的消息传递通路中，可在发放或受方计算机中设置缓冲区，并采用向对方发中断信号的方式进行异步通信。 以收方有缓冲区为例：发送方向收方发中断信号后，向接收方的缓冲区发送数据。收到中断信

8、号的接收方计算机中断正常运行的程序，接收缓冲区的数据，接收完成后，重返被中断的程序。,通信方式,在使用中断的异步方式中，缓冲区的管理要占用CPU的时间，这与在互连线路中设置缓冲区的方式相比，效率相对要低，但比同步方式要高。,通信方式,介绍四种寻径方式： 存储转发（Store-and-Forward） 虚拟直通（Virtual cut through） 线路交换（Circuit Switching） Wormhole交换（Wormhole Switching),寻径算法,1).存储转发 当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A

9、到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。 缺点： 每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比,寻径算法,2).虚拟直通 中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。,其中，Lh为消息头部开始到其目的信息域的长度，显然有L Lh，所以D的影响比较小。 而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。,寻径算法,3).线路开关 在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消

10、息的尾部经过网络后，整条物理链路才被废弃。,其中，Lc是为消息建立物理通路所传递的控制信息的长度。当L Lh时，D的影响较小。 缺点： 物理通道非共享 传输过程中物理通道一直被占用,寻径算法,4).Wormhole Dally于1986年提出。 首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。 片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。 用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于Worm的一个节，“蠕动”以节为单位顺序的

11、向前爬行。,寻径算法,当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择： （1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。,寻径算法,（2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片不放弃它所占有的结点和通道。这是Wormhole技术和其它流控制技

12、术都不同的地方。,寻径算法,优点： （1）每个结点的缓冲器的需求量小，易于用VLSI实现。 （2）较低的网络传输延迟。所有的片以流水方式向前传送，时间并形性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。,寻径算法,（3）通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。 （4）易于实现Multicast和Broadcast。允许寻径器复制

13、消息包的片并把它们从多个输出通道输出。 Wormhole方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。,寻径算法,55 交叉开关,节点机,寻径算法,S,时间,I1,I2,D, L/B , D ,存储转发（Store-and-forward）寻径技术的时空图,寻径算法,S,时间,I1,I2,D,电路开关寻径技术的时空图,寻径算法,S,时间,I1,I2,D, L/B , D ,Wormhole寻径技术的时空图,包头,数据,寻径算法,软件开销,传统互连接口性能的主要瓶颈： 同一数据反复拷贝，极大增加消息发送的时间

14、。许多研究都表明，数据拷贝占整个发送、接收时间的 65。 TCP/IP等上层复杂协议管理机制，不但增加了消息收发的开销，而且占用了大量的CPU资源和存储资源。研究表明，在连接以太网的主机上，35的通信时间都消耗在TCP/IP的协议处理开销和操作系统的开销之上。 由于协议处于操作系统核内，因此用户程序在发送和接收消息时，操作系统在用户态与核心态之间进行切换频繁，增加了开销。,软件开销,提高互连接口性能的手段: (1)减少数据拷贝次数，实现一次数据拷贝，即用户发送数据直接由用户空间拷贝到接口硬件的缓冲区中，接收的数据直接由接口硬件缓冲区拷贝到用户接收缓冲区中。 (2)简化TCP/IP协议，降低处理

15、开销。复杂的TCP/IP所具有的许多功能是不必要的，必须以精简的消息层、网络层替代。 (3)增强接口硬件的协议处理功能。将上层协议功能由接口板上的快速处理器或专用处理芯片来承担，降低CPU在网络通信处理上的开销。,软件开销,小结 减小通信时延是提高高性能计算机性能的一项非常关键的技术，其手段大体上有硬件和软件两种。 硬件上：对于通信网络可以通过改进拓扑结构、提高通信速度的手段实现；对于节点可以使用高速缓存、超线程技术等。 软件上：可以通过精简和优化协议改善通信过程的软件开销；同时在更高的层次上，可以通过改善任务划分和处理器的分配，以及适量的任务复制（即在不同节点上执行相同的任务）达到通信时延隐

16、藏的效果。,互连与通信的问题,2、编程模型问题 如果能对计算机的系统结构进行高度的抽象，给出一个简洁的概念模型，那么，程序员在编写程序时，就不需要了解硬件结构的具体细节。这种抽象模型就是我们所说的编程模型。,并行处理的基本问题,从用户角度看，一个理想的抽象模型应与一台工作站或PC给用户的映象接近， 因而可以使用我们最熟悉的传统的编程方式 ：,编程模型问题,RAM,File System,CPU,就并行计算机而言，除了计算单元以外，通信体系结构也是非常重要的一个方面。在为并行计算机编写程序时，就不得不考虑到不同节点上不同进程之间的通信问题，而这是一项非常复杂的工作。 因此，在并行编程模型中，就必

17、须对节点之间的通信、同步、协作等各种问题给出很好的定义。共享地址空间、消息传递以及数据并行是最常见的三种并行编程模型。,编程模型问题,共享存储：具有统一的地址空间。,编程模型问题,分布式存储：每个处理器的地址空间单独编址。,“大厅式”,“包间式”,例：假设有两台4节点的的多机系统，一台为共享存储，另一台为分布式存储，计算矩阵乘 AB = C。,编程模型问题,1）、共享存储 将矩阵A按行逻辑的均匀分为4块，矩阵B按列逻辑的均匀分为4块，均存放在共享存储器中。,编程模型问题,A = (A0，A1，A2，A3)T,B = (B0，B1，B2，B3),=,节点机 Pi 上程序执行步骤： K = i ，

18、j=0； 各节点计算 Ai Bk； K = K+1 mod 4； j+； 如果j4, goto 2；,编程模型问题,编程模型问题,2）、分布式存储 矩阵A按行物理的均匀分布在4个计算结点上，而矩阵B则按列物理的分布在4个计算结点上。,编程模型问题,A = (A0，A1，A2，A3)T,B = (B0，B1，B2，B3),=,节点机 Pi 上程序执行步骤： K = i ，J0； 各节点计算 Ai Bk； Send(P 4+i-1 mod 4，Bk)； Rev(P i+1 mod 4，B k+1 mod 4)； K = K+1 mod 4 J+； 如果J4, goto 2；,编程模型问题,编程模型

19、问题,编程模型问题,C00,C11,C22,C33,编程模型问题,C00,C11,C22,C33,编程模型问题,C00,C11,C22,C33,C01,C12,C23,C30,编程模型问题,C00,C01,C11,C12,C33,C30,C22,C23,编程模型问题,C00,C11,C22,C33,C01,C12,C23,C30,C02,C13,C31,C20,编程模型问题,C00,C01,C02,C11,C12,C13,C33,C30,C31,C22,C23,C20,编程模型问题,C00,C11,C22,C33,C01,C12,C23,C30,C02,C13,C31,C20,C03,C10,

20、C32,C21,完成,MIMD编程问题 是否有MIMD编程的一般性方法？ PCAM设计方法学 划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping),编程模型问题,设计并行算法的四个阶段 划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 划分：分解成小的任务，开拓并发性； 通信：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。,PCAM设计方法学,PCAM

21、设计方法学,设计过程,域分解 划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据； 将数据分解成大致相等的小数据片； 划分时考虑数据上的相应操作； 如果一个任务需要别的任务中的数据，则会产生任务间的通讯；,PCAM设计方法学,示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：,PCAM设计方法学,功能分解 划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解； 划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解； 功能分解是一种更深层次的分解。,PCAM设计方法学,划分判据 划分

22、是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否合理？,PCAM设计方法学,通信 通信是PCAM设计过程的重要阶段； 划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信； 功能分解确定了诸任务之间的数据流； 诸任务是并发执行的，通信则限制了这种并发性；,PCAM设计方法学,通信判据 所有任务是否执行大致相当的通信? 是否尽可能的局部通信？ 通信操作是否能并行执行? 同步任务的计算能否并行执行？,PCAM设计方法学,组合 组合是由抽象到具体的过程，是将组合的任务能在一类并行

23、机上有效的执行； 合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程； 通过增加任务的粒度和重复计算，可以减少通讯成本； 保持映射和扩展的灵活性，降低软件工程成本；,PCAM设计方法学,组合判据 增加粒度是否减少了通信成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通信？ 有没有减少并行执行的机会？,PCAM设计方法学,映射 每个任务要映射到具体的处理器，定位到运行机器上； 任务数大于处理器数时，存在负载平衡和任务调度问题； 映射的目标：减少算法的执行时间 并发的任务 不同的处理器 任务之间通信量大的 同一处理器 映射实际是一种权衡，属于NP完全问题,PCAM设计方法学,映射判据 采用集中式负载平衡方案，是否存在通信瓶颈？ 采用动态负载平衡方案，调度策略的成本如何？,PCAM设计方法学,MIMD所带来的其它相关问题 编译问题 如何在编译过程中自动的开发程序的并行性？ 如何在编译过程中自动的分配数据？ 调试问题 由于各个处理器（处理结点）按照自身的时钟执行程序，因此程序的执行过程变得异常复杂。如何确定程序的异常行为？,编程模型问题,