《20100428第三章 并行计算模型和任务分解策略》由会员分享，可在线阅读，更多相关《20100428第三章 并行计算模型和任务分解策略（9页珍藏版）》请在金锄头文库上搜索。
1、第三章 并行计算模型和任务分解策略首先，我们将研究不同类型的并行计算机，为了不严格限定于某个指定机型，我们通过模 型把并行计算机抽象为几个特定属性。为了说明并行程序中处理器之间的通信概念模型我们讨 论了不同的程序模型，另外为了分析和评估我们算法的性能，我们讨论了多计算机架构下评估 并行算法复杂度的代价模型。在介绍并分析的各种代价模型的基础上给出了改进型的代价模型。其次我们定义这样几个指标如负载均衡和网络半径等用来研究图分解问题的主要特性。并 把图分解问题归纳为一般类型和空间映射图类型。我们重点研究的是后者，因为多尺度配置真 实感光照渲染算法可以很方便的描述成空间映射图形式。3.1 并行计算机模
2、型以下给出并行计算机的模型的概述，根据其结构并行计算机大致可分为以下几类。多计算机(Multicomputer):个von Neumann计算机由一个中央处理器(CPU)和一个存储单 元组成。一个多计算机则由很多von Neumann计算机通过互联网络连接而成的计算机系统。见 图 3.1。每个计算机(节点)执行自己的计算并只能访问本地的存储。通过消息实现各计算机之间 的互相通讯。在理想的网络中，两个计算节点之间的信息传送代价与本地的计算节点和它的网 络阻塞无关，只和消息的长度相关。以上多计算机和分布式存储的MIMD机器之间的主要区别 在于后者的两个节点间的信息传输不依赖于本地计算和其它网络阻塞
3、。分布式存储的MIMD类型的机器主要有IBM的SP, Intel的Paragon,曙光4000系列，Cray 的T3E, Meiko的CS-2, NEC的Cenju 3,和nCUBE等。通过本地网络的连接的集群系统可以认 为是分布式存储的 MIMD 型计算机。多处理器(Multiprocessor): 一个多处理器型并行计算机(共享存储的MIMD计算机)由大量处 理器组成，所有的处理器都访问一个共同的存储。理论上理想的模型就是 PRAM 模型(并行的 随机访问系统)，即任何一个处理器访问任一存储单元都是等效的(见图 3.2)。并发存储访问是否 允许取决于所使用的真正的模型【34】。混合模型：分
4、布式共享存储(DMS)计算机，提供了一个统一的存储访问地址空间但是分布式 物理存储模块。编译器和运行时系统负责具体的并行化应用。这种系统软件比较复杂。执行同样的指令流。典型的机型有MasPar的MR和联想机器CM2。 多计算机系统具有良好的可扩展性，价格低廉的集群式并行计算机就属于这种模型，本文 中的算法主要基于多计算机体系结构。3.2 程序模型并行程序的编程语言如C或Fortan。并行结构以某种类库的形式直接整合进这些编程语言中。编 程模型确定了并行程序的风格。一般可分为数据并行、共享存储和消息传递 等模型35。数据并行编程：数据并行模型开始于编写同步SIMD并行计算机程序。程序员需要在每个
5、处理器 上独立执行一个程序，每个处理器均有其自己的存储器。程序员需要定义数据如何分配到每个局部 存储中。实际应用中大量的条件分支的需要使得其很难高效的运行在SIMD型的机器上。共享存储编程：共享存储模型是一个简单的模型，因为程序员写并行程序就像写串行程序一样。 一个程序的执行与几个处理器独立，也不需要同步。一个处理器的执行状态独立于其它处理器的运 行状态。由于所有运行程序均访问统一的全局存储器，这就需要小心处理任何一个处理器需要访问 的数据都必须和其它处理器的访问之间没有任何冲突。消息传递模型：我们把消息传递模型和SPMD(单一程序多数据)应用技术结合使用。每个程序独 立在几个处理器上执行，不
6、需要同步(MIMD系统)。每个程序均立即访问本地存储，通过消息传递实 现远程的存储访问。通信方式主要有一下几个不同类型：点对点通信(point-to-point communication ):一个处理器发送一个数据包到另一个处理器，使用 发送操作，目标处理器必须调用一个接受操作获得这些数据。我们假定一个处理器可以同时和其它 处理器通信，我们还假定一个处理器在同一时间只能和一个处理器通信。且通信为异步，也就是说 接收处理器可以在发送操作完成后的任意时间调用接收命令。集合通信(collective communication):集合通信涉及到多处理器之间的通信。投射(cast):一个处理器同时拷
7、贝同样的信息到其它多个处理器的过程。聚合(combine)：组内每个处理器只负责发送整个数据段的一部分，由一个主处理器接受所有结 果，这个过程需要一个额外的数据统计数据项的个数。M个处理器之间的集合通信可以通过大量的点对点通信以树形方式在时间内完成，这 里假定每个处理器之间的通信物理链路均是独立的。对于并行语言的实现方面，很多的研究工作在对现有的串行程序语言的基础上进行扩展以实现 并行化计算方面作出了大量有益的尝试，如HPC+36或HPF 37等试图在C+或Fortran语言中应 用不同的程序模型。现在把并行性能整合到现有的编成语言中的一个可行方案就是给对语言提供能 实现并行处理和通信的运行库
8、。这其中关键的挑战在于扩展已有语言中新的语言元素和关键字。目前对现有语言进行并行化扩展的工作还处于比较初级的阶段。建立一个标准去规范这方面的 应用是必要的，基于这样标准可以整合大量不同的计算模型，因此，使用消息传递作为编程模型可 以使得程序保持一定的灵活性，随着将来并行语言的不断扩充和发展而已有的并行应用方案在不需 要修改。本文采用的编程模型是消息传递模型。这在过去的若干年里业界已形成了消息传递模型的一个 标准一MPI【38, 39】。当前很多超级计算机实现了大量高效的MPI应用。采用免费、高效、可移 植性好的称之为MPICH的并行编程语言构建适用于集群系统的并行计算的应用，可以使得我们基于
9、MPI的应用可以很容易的移植到其它很多并行计算环境中。3.3 代价模型确定了基于消息传递模型进行并行算法的设计，接着就需要分析该算法的算法复杂度。对于算 法复杂度问题，由于大量不同类型的超级计算机的存在使得统一且能准确预测一个算法的特性几乎 不可能。因此我们必须指定一个代价模型作为我们的分析依据。显然这个模型应该尽可能模拟当前 的超级计算机的性能结构。前人已在该领域做了大量的工作来定义一般的代价模型，使得我们可以 通过该模型准确预测并行算法的复杂性，而不用考虑编程模型或使用哪种硬件。首先介绍目前比较 常见的几种并行计算代价模型，接着在同步性、通信方式和参数等 3个方面对它们作一简单分析比较。
10、详细的概述文章见【40】 。本文采用的机器模型是多计算机，该模型包括了 p个独立的处理器，每个只能访问其本地的存储。 处理器间异步工作且通过一个由处理器对之间的双向通信链路连接而成的网络进行通信。以点对点 方式通信，例如，一个处理器发送数据包到另一个处理器，就是用send操作。目标处理器调用receive 操作接收数据。衡量点对点通信的代价的方法很多，下面介绍一些主要方法。真正具有大规模处理器的超级计算机不会给每对处理器之间提供独立的物理的通信链路。而是 采用处理器之间的通道共享方式。如果两处理器对之间需要同时占用该通道进行通信时就会发生消 息阻塞。由于这种阻塞和特定的网络拓扑结构有关，所以以
11、下一般代价模型没有考虑这些问题。但 我们将在第3.4.3中讨论如何避免或减少阻塞的一般方法。这还考虑了在分布式存储模型上整合其它 的作为原子操作的通信类如涉及到群组处理器之间的集合通信。显然这些通信可以通过大量的点对 点通信方式得到。我们只使用点对点的通信模式，使得我们的算法不需要依赖那些需要更高效的专 门的硬件支持集合通信。3.3.1 Postal模 型Postal【67】模型主要用来描述具有下面3个方面特点的消息传递的通信系统：完全连通、 同时I/O和通信延迟。一个带有n个处理机和通信延迟几的消息传递系统卜上旳(J齐有下面3个 属性：(1) 完全的连通性。系统中的每一个处理机能够向系统中的
12、任何其他处理机发送点对点消 息；同时的I / 0。一个处理机p可以在给处理机q发送消息的同时接收处理机r发送来的消息；(3)通信延迟。如果在t时刻处理机P向处理机q发送我消息M.贝陀在时间间隔二山+1内忙 于发送消息M,而且q在时间间隔I十八一，+於内忙于接收消息M。上面是从处理机的观点来分析一个消息传递系统。在这样的一个系统中，处理机之间靠通 过一个通信网络互相发送和接收消息来通信,这样就产生了一个抽象的全连通的系统。而在很 多系统中,通过不同的输人输出端口,处理机确实可以同时发送和接收消息。在Postal模型中，message被用来表示一个在处理机之间进行通信的不可分割的数据单元， 一个m
13、essage在发送的时候、传输的时候和接收的时候都不能被分成更小的快。一个原子message 被定义为一个数据大小的单元，而发送或者接收一个message的时间被定义为一个时间单元。发 送大块数据的时候，这些数据会首先被分成多个message,每个message都被单独地发送和接收， 这在许多报文交换系统(packet switching)中都是一种标准的实现。上面所说的通信延迟中包括各方面的系统开销，具体来说包括消息准备时间、输出缓冲拷 贝时间、输出端口提交延迟、网络传输延迟、输人端口延迟、输人缓冲拷贝时间和消息中断时 间。这里的通信延迟还包括所有的软件开销和硬件开销。从形式上来说，的值为消
14、息M的发 送方开始发送消息到接收方完全接收完消息所用的时间。尽管从形式上来说是这样，可实际 的精确值可能取决于实际的发送接收组和宴际通信网络的负载；通常，的值应该是相对固定 不变的，不同的处理机之间不能有很大的浮动。3.3.2 BSP 模型根据BSP (bulk synchronous parallel)66 模型，一个并行计算机由下面3部分组成：第一，若 干个存储器或者处理机组件;第二,这些组件之间的点对点通信；第三，这些组件之间的同步机制。 为简单起见，可以认为每个组件中包含一个处理机和本地存储器；在模型中，不要求关于通信 系统、互连网络和同步系统的额外信息。在BSP模型中，一个并行系统由
15、下面3个参数来表示：(1) P，系统中处理机的数目；(2) g，把通信开销转换为计算开销的因子；(3) L，两个同步之间的最短时间。连续的两个同步之间的周期被定义为超步(superstep)。在一个超步中一个处理机可以进行3 个操作：首先各处理机处理本地存储器中的数据，可以是本地计算；然后各处理机向别的处理 机提出远程内存读写请求，而通信实际发生在超步中的时间是不可预知的；最后，所有处理机 进行障栅同步，本次超步的数据通信仅当同步以后有效。在BSP模型中，计算操作的总量用处理机在计算过程中所做的基本操作的数目来表示，通信 量贝用字数来表示。假设在同一次计算和通信中数据项的大小是一样的，而且假设
16、在一个超步 中的通信总量是被发送或者接受的最大字数。通过因子g，通信开销被转换成计算开销，其中g 是系统中计算带宽与通信带宽的比值。具体地说，就是每个处理机发送或者接收至多h个字的开 销与在相同的时间内进行加次计算操作。L表示连续的两次同步之间所能执行的操作的次数，它 的具体值由同步操作的实现和上层算法来决定。同步操作使得超步之间相互无关，根据BSP模型实现的算法的总开销就是所有超步开销的总 和，而每一个超步的开销由该超步中计算开销和通信开销所决定。BSP模型的一个不足之处在于处理器的同步只在superstep之间。一个消息在一个superstep开 始时发送只能被用于下一个superstep，即使superstep的长度比网络延时还要长；另一个缺点就是 这个模型不能统计消息注入网络的时间。这些不足可由以下模型弥补。3.3.3 LogP 模型LogP【68】是一个能很好地符
