并行计算模型和任务分解策略

《并行计算模型和任务分解策略》由会员分享，可在线阅读，更多相关《并行计算模型和任务分解策略（9页珍藏版）》请在金锄头文库上搜索。

1、第三章并行计算模型和任务分解策略首先，我们将研究不同类型的并行计算机，为了不严格限左于某个指左机型，我们通过模 型把并行计算机抽象为几个特左属性。为了说明并行程序中处理器之间的通信概念模型我们讨 论了不同的程序模型，另外为了分析和评估我们算法的性能，我们讨论了多汁算机架构下评估 并行算法复杂度的代价模型。在介绍并分析的各种代价模型的基础上给出了改进型的代价模型。其次我们泄义这样几个指标如负载均衡和网络半径等用来研究图分解问题的主要特性。并 把图分解问题归纳为一般类型和空间映射图类型。我们重点研究的是后者，因为多尺度配宜貞. 实感光照渲染算法可以很方便的描述成空间映射图形式。3.1并行计算机模型

2、以下给出并行计算机的模型的概述，根拯其结构并行计算机大致可分为以下几类。多讣算机（Multicomputer）： 一个von Neumann计算机由一个中央处理器（CPU）和一个存储单 元组成。一个多计算机则由很多von Neumann计算机通过互联网络连接而成的计算机系统。见 图3.1o每个讣算机（节点）执行自己的讣算并只能访问本地的存储。通过消息实现各计算机之间 的互相通讯。在理想的网络中，两个计算节点之间的信息传送代价与本地的讣算肖点和它的网 络阻塞无关，只和消息的长度相关。以上多计算机和分布式存储的MIMD机器之间的主要区别 在于后者的两个节点间的信息传输不依赖于本地计算和其它网络阻塞

3、。分布式存储的MIMD类型的机器主要有IBM的SR Intel的Paragon,曙光4000系列，Cray 的T3E. Meiko的CS2 NEC的Cenju 3,和nCUBE等。通过本地网络的连接的集群系统可以认 为是分布式存储的MIMD型计算机。多处理器（Multiprocessor）： 一个多处理器型并行计算机（共享存储的MIMD讣算机）由大量处 理器组成，所有的处理器都访问一个共同的存储。理论上理想的模型就是PRAM模型（并行的 随机访问系统），即任何一个处理器访间任一存储单元都是等效的（见图3.2）o并发存储访问是否 允许取决于所使用的真正的模型【34】。混合模型：分布式共享存储（D

4、MS川算机，提供了一个统一的存储访问地址空间但是分布式 物理存储模块。编译濡和运行时系统负责具体的并行化应用。这种系统软件比较复杂。图3.1多讣算机模型SIMD汁算机：在一个SIMD（单指令流多数据流）计算机中在不同数据流阶段所有的处理器执行同样的指令流。典型的机型有MasPar的MR和联想机器CM2。多计算机系统具有良好的可扩展性，价格低廉的集群式并行计算机就属于这种模型.本文 中的算法主要基于多讣算机体系结构。3.2程序模型并行程序的编程语言如C或Fortano并行结构以某种类库的形式直接整合进这些编程语言中。编 程模型确定了并行程序的风格。般可分为数据并行.共学存储和消息传递等模型35。

5、数据并行编程：数据并行模型开始于编写同步SIMD并行计算机程疗;。程序员需要在每个处理器 上独立执行个程疗:，每个处理器均有其自己的存储器。程序员需要定义数据如何分配到每个局部 存储中。实际应用中人量的条件分支的需要使得其很难高效的运行在SIMD型的机器上。共宇存储编程：共学存储模型是个简单的模型，因为程序员写并行程序就像写串行程序样。 个程序的执行与几个处理器独立，也不需要同步。个处理器的执行状态独立于其它处理器的运 行状态。由于所有运行程序均访问统的全局存储器，这就需要小心处理任何个处理器需耍访问 的数据都必须和其它处理器的访问之间没有任何冲突。消息传递模型：我们把消息传递模型和SPMD（

6、单程序多数据）应用技术结合使用。每个程序独 立在几个处理器上执行，不需要同步（MIMD系统）。每个程序均立即访问本地存储.通过消息传递实 现远程的存储访问。通信方式主要有下几个不同类型：点对点通point-to-point communication）： 个处理器发送个数据包到另个处理器，使用 发送操作，目标处理器必须调用个接受操作获得这些数据。我们假定个处理器可以同时和其它 处理器通信，我们还假定个处理器在同时间只能和个处理器通信。且通信为异步，也就是说 接收处理器可以在发送操作完成后的任恿时间调用接收命令。集合通（collective communication）：集合通信涉及到多处理器之

7、间的通信。投射（cast）： 个处理器同时拷贝同样的信息到其它多个处理器的过程。聚合（combine）：组内每个处理器只负资发送整个数据段的部分，由个主处理器接受所有结 果，这个过程需要个额外的数据统计数据项的个数.M个处理器之间的集合通信可以通过人量的点对点通信以树形方式在（bg（加）时间内完成，这 里假定每个处理器之间的通信物理链路均是独立的。对于并行语言的实现方【fit很多的研究匸作在对现有的串行程序语言的基础上进行扩展以实现 并行化计算方面作出了大量有益的尝试，如HPC+36或HPF37等试图在（2卄或Fortran语言中应 用不同的程序模型。现在把并行性能整合到现有的编成语言中的个可

8、行方案就是给对语言提供能 实现并行处理和通信的运行库。这其中关键的挑战在于扩展已有语言中新的语言元素和关键字。目前对现有语言进行并行化扩展的工作还处于比较初级的阶段。建立个标准去规范这方而的 应用是必要的，基于这样标准可以整合大量不同的计算模型，因此，使用消息传递作为编程模型可 以使得程序保持定的灵活性，随着将来并行语言的不断扩充和发展而已有的并行应用方案在不需 要修改。本文采用的编程模型是消息传递模型。这在过去的若干年里业界已形成了消息传递模型的个 标准-MPI 38, 39 o当前很多超级计算机实现了人量高效的MPI应用。采用免费、高效、可移 植性好的称之为MPICH的并行编程语言构建适用

9、于集群系统的并行计算的应用，可以使得我们基于 2IPI的应用可以很容易的移植到其它很多并行计算环境中。3.3代价模型确宦了基于消息传递模型进行并行算法的设计，接着就需要分析该算法的算法复杂度。对于算 法复杂度问题，由于大量不同类型的超级计算机的存在使得统且能准确预测个算法的特性几乎 不可能。因此我们必须指定个代价模型作为我们的分析依据。显然这个模型应该尽可能模拟当前 的超级计算机的性能结构。前人已在该领域做了人量的工作来定义般的代价模型，使得我们可以 通过该模型准确预测并行算法的复杂性，而不用考虑编程模型或使用哪种硬件。首先介绍目前比较 常见的几种并行计算代价模型，接着在同步性、通信方式和参数

10、等3个方而对它们作简单分析比较。 详细的概述文章见【40】。本文采用的机器模型是多计算机，该模型包扌舌了p个独立的处理器，每个只能访问其本地的存储。 处理器间异步工作且通过个由处理器对之间的双向通信链路连接而成的网络进行通信。以点对点 方式通信，例如，个处理器发送数据包到另个处理器，就是用send操作。目标处理器调用receive 操作接收数据。衡量点对点通信的代价的方法很多，下闻介绍些主要方法。真正具有人规模处理器的超级计算机不会给每对处理器之间捉供独立的物理的通信链路。而是 采用处理器之间的通道共学方式。如果两处理器对之间需耍同时占用该通道进行通信时就会发生消 息阻塞。由于这种阻塞和特定的

11、网络拓扑结构有关，所以以下般代价模型没有考虑这些问题。但 我们将在第343中讨论如何避免或减少阻塞的般方法。这还考虑了在分布式存储模型上整合其它 的作为原了操作的通信类如涉及到群组处理器之间的集合通信。显然这些通信可以通过人量的点对 点通信方式得到。我们只使用点对点的通信模式，使得我们的算法不需要依赖那些需要更高效的专 门的硬件支持集合通信。3.3.1 Postal 模型Postal 67模型主要用来描述具有下而3个方而特点的消息传递的通信系统：完全连通、 同时I / 0和通信延迟。一个带有n个处理机和通信延迟入的消息传递系统MPSnU)有下而3个 属性：(1) 完全的连通性。系统中的每一个处

12、理机能够向系统中的任何英他处理机发送点对点消(2) 同时的I / Oo 一个处理机p可以在给处理机q发送消息的同时接收处理机r发送来的消息:(3) 通信延迟。如果在t时刻处理机P向处理机q发送我消息M.贝忖在时间间隔Dm+口呐忙 于发送消息而且q在时间间隔rH-1昇十肥内忙于接收消息此上而是从处理机的观点来分析一个消息传递系统。在这样的一个系统中，处理机之间靠通 过一个通信网络互相发送和接收消息来通信，这样就产生了一个抽象的全连通的系统。而在很 多系统中，通过不同的输人输出端口，处理机确实可以同时发送和接收消息。在Postal模型中，message被用来表示一个在处理机之间进行通信的不可分割的

13、数据单元， 一个message在发送的时候、传输的时候和接收的时候都不能被分成更小的快。一个原子message 被沱义为一个数据大小的单元，而发送或者接收一个message的时间被泄义为一个时间单元。发 送大块数拯的时候，这些数据会首先被分成多个message,每个message都被单独地发送和接收, 这在许多报文交换系统(packet switching)中都是一种标准的实现。上而所说的通信延迟中包括各方而的系统开销.具体来说包括消息准备时间、输岀缓冲拷 贝时间、输出端口提交延迟、网络传输延迟、输人端口延迟、输人缓冲拷贝时间和消息中断时 间。这里的通信延迟入还包括所有的软件开销和硬件开销。从

14、形式上来说，入的值为消息M的发 送方开始发送消息到接收方完全接收完消息所用的时间。尽管从形式上来说是这样，可实际 的精确值可能取决于实际的发送接收组和宴际通信网络的负载：通常，入的值应该是相对固立 不变的，不同的处理机之间不能有很大的浮动。3.3.2 BSP 模型根jBSP (bulk synchronous parallel)|66|型，一个并行讣算机由下而3部分组成：第一，若 干个存储器或者处理机组件;第二，这些组件之间的点对点通信；第三,这些组件之间的同步机制* 为简单起见，可以认为每个组件中包含一个处理机和本地存储器：在模型中，不要求关于通信 系统.互连网络和同步系统的额外信息。在BS

15、P模型中，一个并行系统由下面3个参数来表示：(1) P,系统中处理机的数目：(2) g,把通信开销转换为计算开销的因子：(3) L,两个同步之间的最短时间。连续的两个同步之间的周期被泄义为超步(superstep)a在一个超步中一个处理机可以进行3 个操作：首先各处理机处理本地存储器中的数据，可以是本地讣算；然后各处理机向别的处理 机提岀远程内存读写请求，而通信实际发生在超步中的时间是不可预知的；最后，所有处理机 进行障柵同步，本次超步的数摒通信仅当同步以后有效。在BSP模型中，计算操作的总量用处理机在计算过程中所做的基本操作的数目来表示，通信 量则用字数来表示。假设在同一次计算和通信中数据项

16、的大小是一样的，而且假设在一个超步 中的通信总量是被发送或者接受的最大字数找通过因子g，通信开销被转换成汁算开销，其中g 是系统中计算带宽与通信带宽的比值。具体地说，就是每个处理机发送或者接收至多h个字的开 销与在相同的时间内进行加次计算操作。L表示连续的两次同步之间所能执行的操作的次数，它 的具体值由同步操作的实现和上层算法来决定。同步操作使得超步之间相互无关，根据BSP模型实现的算法的总开销就是所有超步开销的总 和，而每一个超步的开销由该超步中计算开销和通信开销所决定。BSP模型的一个不足之处在于处理器的同步只在superstep之间。一个消息在一个supcrslcp开 始时发送只能被用于下一个superstep,即使superstep的长度比网络延时还要长：另一个缺点就是 这个模型