第三章并行计算模型和任务分解策略首先，我们将研究不同类型的并行计算机，为了不严格限定于某个指定机型，我们通过模型把并行计算机抽象为几个特定属性。

为了说明并行程序中处理器之间的通信概念模型我们讨论了不同的程序模型，另外为了分析和评估我们算法的性能，我们讨论了多计算机架构下评估并行算法复杂度的代价模型。

在介绍并分析的各种代价模型的基础上给出了改进型的代价模型。

其次我们定义这样几个指标如负载均衡和网络半径等用来研究图分解问题的主要特性。

并把图分解问题归纳为一般类型和空间映射图类型。

我们重点研究的是后者，因为多尺度配置真实感光照渲染算法可以很方便的描述成空间映射图形式。

3.1 并行计算机模型以下给出并行计算机的模型的概述，根据其结构并行计算机大致可分为以下几类。

多计算机(Multicomputer)：一个von Neumann计算机由一个中央处理器(CPU)和一个存储单元组成。

一个多计算机则由很多von Neumann计算机通过互联网络连接而成的计算机系统。

见图3.1。

每个计算机(节点)执行自己的计算并只能访问本地的存储。

通过消息实现各计算机之间的互相通讯。

在理想的网络中，两个计算节点之间的信息传送代价与本地的计算节点和它的网络阻塞无关，只和消息的长度相关。

以上多计算机和分布式存储的MIMD机器之间的主要区别在于后者的两个节点间的信息传输不依赖于本地计算和其它网络阻塞。

分布式存储的MIMD类型的机器主要有IBM的SP, Intel的Paragon, 曙光4000系列, Cray 的T3E, Meiko的CS-2, NEC的Cenju 3, 和nCUBE等。

通过本地网络的连接的集群系统可以认为是分布式存储的MIMD型计算机。

多处理器(Multiprocessor)：一个多处理器型并行计算机(共享存储的MIMD计算机)由大量处理器组成，所有的处理器都访问一个共同的存储。

理论上理想的模型就是PRAM模型(并行的随机访问系统)，即任何一个处理器访问任一存储单元都是等效的(见图3.2)。

并发存储访问是否允许取决于所使用的真正的模型【34】。

混合模型：分布式共享存储(DMS)计算机，提供了一个统一的存储访问地址空间但是分布式物理存储模块。

编译器和运行时系统负责具体的并行化应用。

这种系统软件比较复杂。

图3.1 多计算机模型图3.2 PRAM 模型SIMD计算机：在一个SIMD(单指令流多数据流)计算机中在不同数据流阶段所有的处理器执行同样的指令流。

典型的机型有MasPar的MP, 和联想机器CM2。

多计算机系统具有良好的可扩展性，价格低廉的集群式并行计算机就属于这种模型，本文中的算法主要基于多计算机体系结构。

3.2 程序模型并行程序的编程语言如C或Fortan。

并行结构以某种类库的形式直接整合进这些编程语言中。

编程模型确定了并行程序的风格。

一般可分为数据并行、共享存储和消息传递等模型[35]。

数据并行编程：数据并行模型开始于编写同步SIMD并行计算机程序。

程序员需要在每个处理器上独立执行一个程序，每个处理器均有其自己的存储器。

程序员需要定义数据如何分配到每个局部存储中。

实际应用中大量的条件分支的需要使得其很难高效的运行在SIMD型的机器上。

共享存储编程：共享存储模型是一个简单的模型，因为程序员写并行程序就像写串行程序一样。

一个程序的执行与几个处理器独立，也不需要同步。

一个处理器的执行状态独立于其它处理器的运行状态。

由于所有运行程序均访问统一的全局存储器，这就需要小心处理任何一个处理器需要访问的数据都必须和其它处理器的访问之间没有任何冲突。

消息传递模型：我们把消息传递模型和SPMD(单一程序多数据)应用技术结合使用。

每个程序独立在几个处理器上执行，不需要同步(MIMD系统)。

每个程序均立即访问本地存储，通过消息传递实现远程的存储访问。

通信方式主要有一下几个不同类型：点对点通信(point-to-point communication)：一个处理器发送一个数据包到另一个处理器，使用发送操作，目标处理器必须调用一个接受操作获得这些数据。

我们假定一个处理器可以同时和其它处理器通信，我们还假定一个处理器在同一时间只能和一个处理器通信。

且通信为异步，也就是说接收处理器可以在发送操作完成后的任意时间调用接收命令。

集合通信(collective communication)：集合通信涉及到多处理器之间的通信。

投射(cast)：一个处理器同时拷贝同样的信息到其它多个处理器的过程。

聚合(combine)：组内每个处理器只负责发送整个数据段的一部分，由一个主处理器接受所有结果，这个过程需要一个额外的数据统计数据项的个数。

M个处理器之间的集合通信可以通过大量的点对点通信以树形方式在时间内完成，这里假定每个处理器之间的通信物理链路均是独立的。

对于并行语言的实现方面，很多的研究工作在对现有的串行程序语言的基础上进行扩展以实现并行化计算方面作出了大量有益的尝试，如H PC++[36]或HPF [37]等试图在C++或Fortran语言中应用不同的程序模型。

现在把并行性能整合到现有的编成语言中的一个可行方案就是给对语言提供能实现并行处理和通信的运行库。

这其中关键的挑战在于扩展已有语言中新的语言元素和关键字。

目前对现有语言进行并行化扩展的工作还处于比较初级的阶段。

建立一个标准去规范这方面的应用是必要的，基于这样标准可以整合大量不同的计算模型，因此，使用消息传递作为编程模型可以使得程序保持一定的灵活性，随着将来并行语言的不断扩充和发展而已有的并行应用方案在不需要修改。

本文采用的编程模型是消息传递模型。

这在过去的若干年里业界已形成了消息传递模型的一个标准—MP I【38，39】。

当前很多超级计算机实现了大量高效的MPI应用。

采用免费、高效、可移植性好的称之为MPICH的并行编程语言构建适用于集群系统的并行计算的应用，可以使得我们基于MPI的应用可以很容易的移植到其它很多并行计算环境中。

3.3 代价模型确定了基于消息传递模型进行并行算法的设计，接着就需要分析该算法的算法复杂度。

对于算法复杂度问题，由于大量不同类型的超级计算机的存在使得统一且能准确预测一个算法的特性几乎不可能。

因此我们必须指定一个代价模型作为我们的分析依据。

显然这个模型应该尽可能模拟当前的超级计算机的性能结构。

前人已在该领域做了大量的工作来定义一般的代价模型，使得我们可以通过该模型准确预测并行算法的复杂性，而不用考虑编程模型或使用哪种硬件。

首先介绍目前比较常见的几种并行计算代价模型，接着在同步性、通信方式和参数等3个方面对它们作一简单分析比较。

详细的概述文章见【40】。

本文采用的机器模型是多计算机，该模型包括了p个独立的处理器，每个只能访问其本地的存储。

处理器间异步工作且通过一个由处理器对之间的双向通信链路连接而成的网络进行通信。

以点对点方式通信，例如，一个处理器发送数据包到另一个处理器，就是用send操作。

目标处理器调用receive 操作接收数据。

衡量点对点通信的代价的方法很多，下面介绍一些主要方法。

真正具有大规模处理器的超级计算机不会给每对处理器之间提供独立的物理的通信链路。

而是采用处理器之间的通道共享方式。

如果两处理器对之间需要同时占用该通道进行通信时就会发生消息阻塞。

由于这种阻塞和特定的网络拓扑结构有关，所以以下一般代价模型没有考虑这些问题。

但我们将在第3.4.3中讨论如何避免或减少阻塞的一般方法。

这还考虑了在分布式存储模型上整合其它的作为原子操作的通信类如涉及到群组处理器之间的集合通信。

显然这些通信可以通过大量的点对点通信方式得到。

我们只使用点对点的通信模式，使得我们的算法不需要依赖那些需要更高效的专门的硬件支持集合通信。

3.3.1 Postal模型Postal【67】模型主要用来描述具有下面3个方面特点的消息传递的通信系统：完全连通、同时I／O和通信延迟。

一个带有n个处理机和通信延迟的消息传递系统有下面3个属性：(1)完全的连通性。

系统中的每一个处理机能够向系统中的任何其他处理机发送点对点消息；(2)同时的I／O。

一个处理机p可以在给处理机q发送消息的同时接收处理机r发送来的消息；(3)通信延迟。

如果在t时刻处理机P向处理机q发送我消息M．则P在时间间隔内忙于发送消息M，而且q在时间间隔内忙于接收消息M。

上面是从处理机的观点来分析一个消息传递系统。

在这样的一个系统中，处理机之间靠通过一个通信网络互相发送和接收消息来通信，这样就产生了一个抽象的全连通的系统。

而在很多系统中，通过不同的输人输出端口，处理机确实可以同时发送和接收消息。

在Postal模型中，message被用来表示一个在处理机之间进行通信的不可分割的数据单元，一个message在发送的时候、传输的时候和接收的时候都不能被分成更小的快。

一个原子message 被定义为一个数据大小的单元，而发送或者接收一个message的时间被定义为一个时间单元。

发送大块数据的时候，这些数据会首先被分成多个message，每个message都被单独地发送和接收，这在许多报文交换系统(packet switching)中都是一种标准的实现。

上面所说的通信延迟中包括各方面的系统开销，具体来说包括消息准备时间、输出缓冲拷贝时间、输出端口提交延迟、网络传输延迟、输人端口延迟、输人缓冲拷贝时间和消息中断时间。

这里的通信延迟还包括所有的软件开销和硬件开销。

从形式上来说，的值为消息M的发送方开始发送消息到接收方完全接收完消息所用的时间。

尽管从形式上来说是这样，可实际^的精确值可能取决于实际的发送接收组和宴际通信网络的负载；通常，的值应该是相对固定不变的，不同的处理机之间不能有很大的浮动。

3.3.2 BSP 模型根据BSP (bulk synchronous parallel)[66]模型，一个并行计算机由下面3部分组成：第一，若干个存储器或者处理机组件;第二,这些组件之间的点对点通信；第三，这些组件之间的同步机制。

为简单起见，可以认为每个组件中包含一个处理机和本地存储器；在模型中，不要求关于通信系统、互连网络和同步系统的额外信息。

在BSP模型中，一个并行系统由下面3个参数来表示：(1)P，系统中处理机的数目；(2)g，把通信开销转换为计算开销的因子；(3)L，两个同步之间的最短时间。

连续的两个同步之间的周期被定义为超步(superstep)。

在一个超步中一个处理机可以进行3个操作：首先各处理机处理本地存储器中的数据，可以是本地计算；然后各处理机向别的处理机提出远程内存读写请求，而通信实际发生在超步中的时间是不可预知的；最后，所有处理机进行障栅同步，本次超步的数据通信仅当同步以后有效。

在BSP模型中，计算操作的总量用处理机在计算过程中所做的基本操作的数目来表示，通信量则用字数来表示。