并行处理技术课件.pptx

什么是并行处理为什么要开发并行处理技术并行机的分类及基本结构并行处理的基本问题和技术,主要内容,多个处理单元(a collection of computing elements)协作、通信（cooperate&communicate）快速求解大型问题（to solve large problems fast）并行体系结构：用通信体系结构(Communication Architecture)对传统的体系结构进行扩展。,并行处理的基本问题,处理器之间协同的基础是什么？互连与通信编程人员使用何种方式编程？编程模型如何保证并行程序的正确性？存储一致性,并行处理的基本问题,1、互连与通信的问题互连网络的定义及特性静态网络动态网络多处理器通信问题,并行处理的基本问题,并行计算机往往采用多个处理节点。其根本思想就是将要完成的任务尽量分布到各个处理节点并发执行，在最理想的情况下并行计算机的性能是所有节点计算性能的简单相加。但是由于节点间存在着通信延时和各个节点间的同步关系，使得系统的整体性能通常达不到理想情况。比如在某些MPP上其持续速度只是峰值速度的3%10%。同时，并行计算也逐步向着松耦合（loosely Coupled）和复杂化的方向发展。大量的SMP集群(CLUMPs)的出现，使得并行计算机内部节点与节点间的通信瓶颈愈发明显。因此，解决并行计算机的通信问题也就成为了一个研究的热点。,互连与通信的问题,互连与通信的问题,互连网络的定义及特性定义：由开关元件按一定拓扑结构和控制方式构成的网络，以实现计算机系统内部多个处理机或多个功能部件间的相互连接。互连网络对并行处理机的性能影响很大，是系统构成的主要部分。互连网络有三大要素，即互连拓扑（包括连接通路）、开关元件和控制方式。由于这三大要素的工作方式和所处的地位不同，才出现了各种各样的互联网络。,操作方式：同步通信（Synchronous Communication)：收发双方必须在时间上同步。这类似于电话网中需要呼叫方和被呼叫方同步。异步通信(Asynchronous Communication)：收发双方不需要同步。这类似于发送和接收mail。,互连与通信的问题,控制策略：集中控制(Centralized control)：互连网络中的各级互连开关由一组信号统一控制。其优点是控制简单，实现容易，但网络的灵活性相对较差。分布控制(Distributed control)：互连网络中的各级互连开关由多个或多组信号分别控制，各（组）开关可处于不同状态。其优点是网络的灵活性强，但控制相对复杂，实现相对困难。,互连与通信的问题,电路交换(Circuit switching)：采用与电话网类似的方式，在数据传输期间，从发送节点到接收节点的整个连接通路必须保持。,优点：信息的传输延迟小，对一次接续而言，传输时延固定不变。信息的编码方案和信息格式由双方协调，不受网络限制。缺点：电路资源被通信双方独占，电路利用率低。,交换方式：,分组交换(Packet switching)：采用存储转发方式，把数据分解成许多比较短的、规格化的片段，进行交换和传输。,优点：为用户提供了灵活的通信环境（不同速率、不同代码、不同通信协议机制等）。实现线路动态统计复用，通信线路利用率高，可以在一条物理线路上同时提供多条信息通路。可靠性高，经济性好。缺点：由于网络附加的传输信息较多，对长报文通信的传输效率比较低。技术实现复杂。,互连与通信的问题,网络拓扑结构：静态网络(Static network)静态网络的特点与指标典型的静态网络动态网络(Dynamic network)互连函数多级互联网络,互连与通信的问题,A.静态网络的特点 静态网络由点点直接相连而成，这种连结方式在程序执行过程中不会改变。如果用图来表示，结点代表开关，边代表通信链路，则：结点间的链路无源，不能重构；开关元件与处理机相连；不直接相连结点间的通信需通过中间结点中转。,静态网络的特点与指标,B.静态网络的指标结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：结点度=入度+出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。,静态网络的特点与指标,网络规模：网络中结点数，表示该网络功能连结部件的多少。等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。结点间的线长：两个结点间的线的长度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。结点是否同构。通道是否有缓冲。,静态网络的特点与指标,1).线性阵列,对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。N很大时，通信效率很低。,典型的静态网络,2).环,对N个结点的环，考虑相邻结点数据传送方向：单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。,典型的静态网络,3).带弦环,对上图中12个结点的带弦双向环，结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。,结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。,典型的静态网络,4).链接（全互联）链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的链接：,有28条链路，直径为1，度为7，对称，等分宽度为16。,典型的静态网络,5).树形,4层的二叉树,一棵K层完全二叉树应有N=2K-1个结点，对大结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。由于结点度为常数，所以树是一种可扩展的系统结构。,典型的静态网络,树形的扩展：,带环树,二叉胖树,这两种结构都可以缓解根结点的瓶颈问题。,典型的静态网络,6).星形,星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称。,典型的静态网络,有N个结点的rr网（其中)，有2r(r-1)=2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。,7).网,典型的静态网络,有N个结点的rr网（其中)，有2N条链路，直径为r-1，结点度为4。,网的变形：Illiac 网,典型的静态网络,有N个结点的rr网（其中)，有2N 条链路，直径为2r/2，结点度为4，对称。,网的变形：环形网（2DTorus）,典型的静态网络,网的变形：搏动式阵列（Systolic Array）,典型的静态网络,8).超立方体,典型的静态网络,一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。例子：Intel的iPSC/1、iPSC/2、nCUBE,典型的静态网络,9).带环立方体,一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。,典型的静态网络,特点：网络的开关元件有源，链路可通过设置这些开关的状态来重构。只有在网络边界上的开关元件才能与处理机相连。,动态网络,互连函数是一级动态互联网络的一种抽象描述，是从输入到输出的一个映射。排列：N个数的每一种有确定次序的放置方法叫做一个N排列。置换：把一个N排列变成另一个N排列的变换叫做N阶置换。在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。,互联函数,1).恒等函数,其中，Xn-1 Xn-2Xk X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：,互联函数,2).方体函数（cube0，cube1，cuben-1),方体函数是由n个互连函数组成，其中0kn。比如，n为3时，3-立方体各结点地址如下：,互联函数,Cube0:,互联函数,Cube1:,互联函数,Cube2:,3).洗牌函数：均匀洗牌（Shuffle-Exchange),互联函数,子洗牌,即最低k位循环左移一位。,互联函数,超洗牌,即最高k-1位循环左移一位。,互联函数,逆洗牌函数,互联函数,4).蝶式,互联函数,5).PM2I函数（加减2i）共有2n个互连函数，对N个结点的网络为,例1：N=8（8个结点），则n=log28=3，所以：i=0，1，2；j=0，1，7。6个PM2I函数如下：,互联函数,PM2+0:(0 1 2 3 4 5 6 7）,PM2-0:(7 6 5 4 3 2 1 0）,互联函数,PM2+1:(0 2 4 6）（1 3 5 7）,PM2-1:(6 4 2 0）（7 5 3 1）,互联函数,PM22:(0 4）（1 5）（2 6）（3 7）,互联函数,A.多级网络的三要素（1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有2 2、4 4、8 8等。根据开关单元功能的多少，2 2又可以分为两功能和四功能开关。如下图所示：,多级互连网络,0,1,0,1,直送,多级互连网络,（2）级间互连模式（InterStage Connection）：均匀洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（Cross Switch)及立方体连结等。（3）控制方式级控制：每级只有一个控制信号单元控制：每个开关一个控制信号部分级控制：几个开关合用一个控制信号,多级互连网络,B.网,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,网的特点：开关单元：22四功能开关ISC：洗牌变换控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。例子：UIUC的CedarIBM的RP3NYU的Ultracomputer,多级互连网络,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,无阻塞的实现置换1=（0 7 6 4 2）（1 3）（5）,多级互连网络,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,置换2=（0 6 4 7 3）（1 5）（2）在开关F、G、H、I和J上发生阻塞,F,G,H,J,I,多级互连网络,网的特点(2)：并不是所有的置换在网中一次通过便可以实现。网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。,多级互连网络,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,网的广播功能：0018个输出端,多级互连网络,44开关构成的网：多路洗牌如16输入4路洗牌：网路级数为log416=2,0,1,第1级,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,第0级,级间变换:Sh(Sh(),可以认为是由4个2*2开关组成,多级互连网络,网的特点(3)：当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的网络。,多级互连网络,C.蝶式网络（Butterfly switch network）蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。两级64 64的蝶式网络如下图所示：它采用16个8 8交叉开关构成，两级间采用8路洗牌连接。,多级互连网络,两级64 64的蝶式网络,多级互连网络,总线本质上是一组导线和插座，用于处理器、存储模块和外围设备之间的数据传输。系统总线用于主设备如处理器和从设备如存储模块之间传输数据。总线仲裁逻辑每次只授予一个请求存储总线，因此也称争用总线。单总线层次总线,总线,目前已建立了许多标准总线，例如PCI、VME、Multibus、Sbus、MicroChannel、IEEE Futurebus。大多数总线在构造单处理机系统时价格很低。我们关心的是多处理机总线和层次总线，用它们来构造SMP、NUMA和DSM机器。这些可扩展的总线一般用硬件来支持高速缓存一致性、快速多处理机同步、以及分离事务中断处理等。,总线,M,P,C,高速缓存,IF,系统总线（在底板或中夹板上）,局部总线,存储器,存储器总线,C,IF,IOP,IF,IF,IF,IF,C,缓存器,缓存器,局部总线,局部总线,CPU板,I/O板,网络接口卡,以太网,打印机,磁盘,存储板,总线,总线互连的缺陷 总线有多个处理机分时共享，因此即使当总线带宽很高，每个处理器的带宽也只是总带宽的一部分。此外总线由于缺乏冗余机制易于出错，请总线也有有限的可扩展性。这些缺陷主要是受封装技术和价格因素的约束。总线一般限制在很小的机架内，当层次总线扩展到几个机架时，始终扭转和全局时问题就变得难于克服。使用交叉开关和多级网络代替总线结构将在一定程度上克服这些缺陷。,总线,基本术语与性能指标通信方式寻径算法软件开销,多处理器通信问题,基本通信方式 无论网络拓扑结构如何，高性能计算机节点间通信对于用户是透明的。其通信模式无外乎以下4种：单播(Unicast):一个源节点到一个目的节点；多播(Multicast):一个源节点到多个目的节点;广播(Broadcast):一个源节点到全体节点；会议(Conference):多个源节点到一个目的节点。,多处理器通信问题,1).消息、包和片消息（Message）：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。片（Flit）：片的长度固定，一般为8位。它们的相互关系如下图：,基本术语与性能指标,包,消息,基本术语与性能指标,2).互连网络 互连网络用来在多处理机(计算机)系统的处理结点之间传递消息。,互连网络性能的两个重要指标：传输时延（Transmission Latency）吞吐量（Throughput）,互连网络的描述：拓扑（Topology）寻径算法（Routing）流控制（Flow Control）,基本术语与性能指标,3).传输时延与吞吐量 一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。,基本术语与性能指标,一个网络的传输时延：在一定条件下发送消息的平均时延。,网络的吞吐量：单位时间内网络所能传输的消息数目或长度。,基本术语与性能指标,4).传输时延的公式,其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。它们具体定义如下：,基本术语与性能指标,建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。,其中：Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。,基本术语与性能指标,基本术语与性能指标,网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。,其中：TpD称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延，D为源结点与目的结点之间中间结点的数量。,中间结点上的平均时延,中间结点的数量,L/B称为线路时延：其中L为消息长度，B为结点之间的通道带宽。,基本术语与性能指标,阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。,基本术语与性能指标,5).网络的拓扑结构 第一代并行计算机：HyperCube TMC:CM-2 Intel:iPSC nCUBE 第二代并行计算机：nMesh Stanford:Dash MIT:Alewife Intel:Paragon,基本术语与性能指标,6).网络的寻径算法 决定发送一个消息到其目的地所经过的路径。可以分为：最短路径算法非最短路径算法 或者：确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。可适应算法：消息从结点A到结点B可以由几条不同的路径。,基本术语与性能指标,7).网络的流控制 当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。,基本术语与性能指标,1)、同步通信方式 同步通信方式是指发送节点和接收节点在时间上和空间上都要同步动作，任何一个环节发生问题，都会形成阻塞。所谓时间上的同步是指发送节点和接收节点必须在做好传送准备后，才能开始进行消息传递。所谓空间上的同步是指从源节点到目的节点的通信路径都已开通。,通信方式,因发生阻塞而使计算机节点等待的时间称为同步时间。处于等待状态的处理机是空闲的，特别是通信距离长时，每经过一个中继点，就会发生同步，是同步时间过长，并行处理的效率下降。在同步方式下，一般不设置通信缓冲区，一次传送的数据量不受缓冲区大小的限制。,通信方式,2)、异步通信方式 异步通信方式是指在通信通道上设置足够大的缓冲区，发方计算机将消息写入缓冲区，在缓冲区写满之前，不必等待收方节点接收消息；而接收方只需在必要的时候，从缓冲区中把数据读走。在时间上，收发双方不必同步。在空间上，只要缓冲区不满，发方就可以写；缓冲区不空，收方就可以读。异步方式需要足够大的缓冲区，增加了硬件开销，但它是非阻塞的通信系统。,通信方式,同步方式下，发送的数据量和接收的数据量必须相等；而异步方式下没有这种要求，因此，异步方式可以增加并行程序的灵活性。从速度上看，同步方式是收发双方同时工作，数据依次传递成功，而异步方式下，收发双方与缓冲区之间需要传递两次，因此异步方式所用时间较长。,通信方式,在使用总线方式的消息传递通路中，可在发放或受方计算机中设置缓冲区，并采用向对方发中断信号的方式进行异步通信。以收方有缓冲区为例：发送方向收方发中断信号后，向接收方的缓冲区发送数据。收到中断信号的接收方计算机中断正常运行的程序，接收缓冲区的数据，接收完成后，重返被中断的程序。,通信方式,在使用中断的异步方式中，缓冲区的管理要占用CPU的时间，这与在互连线路中设置缓冲区的方式相比，效率相对要低，但比同步方式要高。,通信方式,介绍四种寻径方式：存储转发（Store-and-Forward）虚拟直通（Virtual cut through）线路交换（Circuit Switching）Wormhole交换（Wormhole Switching),寻径算法,1).存储转发 当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。缺点：每个结点必须对整个消息进行缓冲，缓冲器较大。网络时延与发送消息所经历的结点数成正比,寻径算法,2).虚拟直通 中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。,其中，Lh为消息头部开始到其目的信息域的长度，显然有L Lh，所以D的影响比较小。而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。,寻径算法,3).线路开关 在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。,其中，Lc是为消息建立物理通路所传递的控制信息的长度。当L Lh时，D的影响较小。缺点：物理通道非共享传输过程中物理通道一直被占用,寻径算法,4).Wormhole Dally于1986年提出。首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于Worm的一个节，“蠕动”以节为单位顺序的向前爬行。,寻径算法,当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择：（1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。,寻径算法,（2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片不放弃它所占有的结点和通道。这是Wormhole技术和其它流控制技术都不同的地方。,寻径算法,优点：（1）每个结点的缓冲器的需求量小，易于用VLSI实现。（2）较低的网络传输延迟。所有的片以流水方式向前传送，时间并形性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。,寻径算法,（3）通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。（4）易于实现Multicast和Broadcast。允许寻径器复制消息包的片并把它们从多个输出通道输出。Wormhole方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。,寻径算法,55交叉开关,节点机,寻径算法,S,时间,I1,I2,D,L/B,D,存储转发（Store-and-forward）寻径技术的时空图,寻径算法,S,时间,I1,I2,D,电路开关寻径技术的时空图,寻径算法,S,时间,I1,I2,D,L/B,D,Wormhole寻径技术的时空图,包头,数据,寻径算法,软件开销,传统互连接口性能的主要瓶颈：同一数据反复拷贝，极大增加消息发送的时间。许多研究都表明，数据拷贝占整个发送、接收时间的 65。TCP/IP等上层复杂协议管理机制，不但增加了消息收发的开销，而且占用了大量的CPU资源和存储资源。研究表明，在连接以太网的主机上，35的通信时间都消耗在TCP/IP的协议处理开销和操作系统的开销之上。由于协议处于操作系统核内，因此用户程序在发送和接收消息时，操作系统在用户态与核心态之间进行切换频繁，增加了开销。,软件开销,提高互连接口性能的手段:(1)减少数据拷贝次数，实现一次数据拷贝，即用户发送数据直接由用户空间拷贝到接口硬件的缓冲区中，接收的数据直接由接口硬件缓冲区拷贝到用户接收缓冲区中。(2)简化TCP/IP协议，降低处理开销。复杂的TCP/IP所具有的许多功能是不必要的，必须以精简的消息层、网络层替代。(3)增强接口硬件的协议处理功能。将上层协议功能由接口板上的快速处理器或专用处理芯片来承担，降低CPU在网络通信处理上的开销。,软件开销,小结 减小通信时延是提高高性能计算机性能的一项非常关键的技术，其手段大体上有硬件和软件两种。硬件上：对于通信网络可以通过改进拓扑结构、提高通信速度的手段实现；对于节点可以使用高速缓存、超线程技术等。软件上：可以通过精简和优化协议改善通信过程的软件开销；同时在更高的层次上，可以通过改善任务划分和处理器的分配，以及适量的任务复制（即在不同节点上执行相同的任务）达到通信时延隐藏的效果。,互连与通信的问题,2、编程模型问题 如果能对计算机的系统结构进行高度的抽象，给出一个简洁的概念模型，那么，程序员在编写程序时，就不需要了解硬件结构的具体细节。这种抽象模型就是我们所说的编程模型。,并行处理的基本问题,从用户角度看，一个理想的抽象模型应与一台工作站或PC给用户的映象接近，因而可以使用我们最熟悉的传统的编程方式：,编程模型问题,RAM,File System,CPU,就并行计算机而言，除了计算单元以外，通信体系结构也是非常重要的一个方面。在为并行计算机编写程序时，就不得不考虑到不同节点上不同进程之间的通信问题，而这是一项非常复杂的工作。因此，在并行编程模型中，就必须对节点之间的通信、同步、协作等各种问题给出很好的定义。共享地址空间、消息传递以及数据并行是最常见的三种并行编程模型。,编程模型问题,共享存储：具有统一的地址空间。,编程模型问题,分布式存储：每个处理器的地址空间单独编址。,“大厅式”,“包间式”,例：假设有两台4节点的的多机系统，一台为共享存储，另一台为分布式存储，计算矩阵乘 AB=C。,编程模型问题,1）、共享存储 将矩阵A按行逻辑的均匀分为4块，矩阵B按列逻辑的均匀分为4块，均存放在共享存储器中。,编程模型问题,A=(A0，A1，A2，A3)T,B=(B0，B1，B2，B3),=,节点机 Pi 上程序执行步骤：K=i，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 4J+；如果J4,goto 2；,编程模型问题,编程模型问题,编程模型问题,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,C32,C21,完成,MIMD编程问题是否有MIMD编程的一般性方法？PCAM设计方法学划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping),编程模型问题,设计并行算法的四个阶段划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。,PCAM设计方法学,PCAM设计方法学,设计过程,域分解划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯；,PCAM设计方法学,示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：,PCAM设计方法学,功能分解划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。,PCAM设计方法学,划分判据划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？,PCAM设计方法学,通信通信是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通信则限制了这种并发性；,PCAM设计方法学,通信判据所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行?同步任务的计算能否并行执行？,PCAM设计方法学,组合组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；保持映射和扩展的灵活性，降低软件工程成本；,PCAM设计方法学,组合判据增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？,PCAM设计方法学,映射每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务 不同的处理器任务之间通信量大的 同一处理器映射实际是一种权衡，属于NP完全问题,PCAM设计方法学,映射判据采用集中式负载平衡方案，是否存在通信瓶颈？采用动态负载平衡方案，调度策略的成本如何？,PCAM设计方法学,MIMD所带来的其它相关问题编译问题如何在编译过程中自动的开发程序的并行性？如何在编译过程中自动的分配数据？调试问题 由于各个处理器（处理结点）按照自身的时钟执行程序，因此程序的执行过程变得异常复杂。如何确定程序的异常行为？,编程模型问题,