将基于pram模型的算法转换为基于logp模型的算法的一种

《将基于pram模型的算法转换为基于logp模型的算法的一种》由会员分享，可在线阅读，更多相关《将基于pram模型的算法转换为基于logp模型的算法的一种（7页珍藏版）》请在金锄头文库上搜索。

1、 第 18卷 第 6期小 型 微 型 计 算 机 系 统Vol. 18 No. 61997年 6月MINI-M ICRO SYSTEM SJun. 1997将基于 PRAM模型的算法转换为基于 LogP模型的算法的一种方法*焦 进 张晓云 姜殿启 张德富(南京大学计算机软件新技术国家重点实验室 南京 210093)(南京大学计算机科学与技术系 南京 210093)摘 要 本文提出了一种将基于 PRAM模型的并行算法转换为基于 LogP模型的并行算法的方法 , 并通过在算法的通信结构有向无环图上进行线性分组的方法 , 实现基于 Log P模型的算法的优化。关 键 词 PRAM, Log P, 有

2、向无环图 , 线性分组1 引 言并行计算发展到今天 , 已经出现了 PRAM、 BSP、 Log P等多种并行计算模型。不同类型的并行计算机通常有不同类型的并行计算模型 ,而一般解同一个问题在不同类型的并行计算 机上需要有不同的并行程序 ,这就给用户带来了极大的困难 ,使得并行计算机难以推广使用。为了便于并行程序在不同类型的并行计算机上移植 ,必须对基于某种并行计算模型的算法转换为基于另一种并行计算模型的算法的方法进行深入研究。 以前研制的并行算法多数是基于 PRAM模型的 ,已经取得了相当广泛的应用。 但是PRAM模型也存在着同步困难、通讯效率低等缺点 ,为了克服这些不足 ,近年来国际上提出

3、了 不少新的并行计算模型。其中 Log P模型由于充分考虑了并行计算的通信特性 ,更接近于实用模型 ,因而受到了广泛重视 ,对它的研究正方兴未艾。 为了充分利用已有的应用软件资源 ,便于并行程序在不同类型的并行计算机上进行移植 ,本文提出了将基于 PRAM模型的算法转换为基于 Log P模型的算法的一种方法 ,并通过在算法的通信结构有向无环图 ( DAG)上进行线性分组的方法 ,实现转换后基于 LogP模型的算法的优化。2 PRAM模型和 LogP模型共享存储器式并行计算机系统8 是应用最广泛的并行计算机系统之一 , PRAM模型正是1996-07-03收稿 * 国家“863 ”高科技基金资助

4、项目。焦进,硕士生,主要从事并行处理研究。张晓云,硕士生 ,主要从事并行处理研究。 姜殿启,硕士生 ,主要从事并行处理研究。 张德富 ,教授 ,博士生导师 ,主要从事并行处理和分布系统研究。基于这种系统 ,由 n个带有局部私有内存的处理器构成 ,它们之间通过一个共享的全局内存进图 1 PRAM系统结构示意图行通信。 其结构示意如图 1所示:一个 PRAM模型的计算由一连串的读、计算和写序列组成。 在读步 骤中 ,每个处理器从全局内存中读取数据到局部内存中。 在计算步骤中 ,每个处理器处理各自局部内存中的数据 ,并把结果存放在局部内存中。 在写步骤中 ,每个处理器将各自局部内存中的结果写入相应的

5、全局内存中。 由于 PRAM模型比较直观 ,编程简单 ,因而得到了广泛应用。但 PRAM模型是同步并行处理 ,没有考虑通信开销 ,效率较低。而在大规模并行计算 中 ,现有的 MIMD机器一般是异步的 ,所以要在 MIMD机器上实现 PRAM模型是非常困难的 ,同步代价太高。 虽然目前已经提出了不少异步方式的 PRAM算法6, 7,但由于未全面考虑并行计算的通信特性 ,都有一定的缺陷 ,效率不高。加州大学伯克利分校的 D. E. Culler等人在 1993年提出的 Log P并行计算模型1, 2 则充分考虑了并行计算的多种因素 ,效率较高 ,与并行计算的实际情况比较接近。 Log P模型机器是

6、一个用互连网络连接起来的计算机群 ,每台计算机都由一功能强大的微处理器、 Cache和大容量的 DRAM内存组成。 Log P模型是由一组通过点对点消息传递的进程组成的模型。它们的通信性能可以用以下四个参数来刻划1 :L: 通信延迟 ( Latency)。 是在源地址和目的地址之间发生短消息 (消息长度较短 )传递的 延迟上界。o: 通信开销 ( overhead)。 定义为一个处理器传送或接收消息的时间长度 ,在这期间 ,处理 器不能执行别的操作。g: 通信间隔 ( gap)。 定义为一个处理器在连续传送或连续接收消息时的最小时间间隔 ,即 每个处理器的可用通信带宽。P : 处理器数目 (

7、Processors)。 在该模型中没有考虑各个处理器的特性。图 2 LogP模式示意图Log P模型示意如图 2所示: Log P模型是异步执行的 ,消 息传递的延迟上限是 L,在任意时 刻最多可以有 L /g 条消息在网 上传递 ,如超出这个限制则传送会 停顿直到要传递的消息小于这个 限制。 由图 2可见 ,一个最简单的 通信操作 ,从一个处理器向另一个 处理器发送或接收消息 ,需要 L + 2o的时间。而如果要向另一个处理器发送一组 n条消息 ,则 可形成一条通信流水线 ,处理器在花费 o时间发送第一条消息后 ,即可每隔一个时间间隔 g发 送下一条消息 ,每条消息花费 L时间到达目的地

8、,接收方花费 o时间接收每条信息。因此总共 花费了 2o+ ( n( 1) g+ L时间。 而处理器之间交换 n条信息则复杂得多2,执行时间为 2L + 2o + ( n- 1- L /g)* max( g, 2o)。 Log P模型充分考虑了网络性能和通信开销 ,体现了并行计算网络化的一个方向。 它不仅28小 型 微 型 计 算 机 系 统 1997年能指导程序员进行基于网络信息传递的并行编程 ,而且能比较准确地估测并行计算的时间和 性能2,有着独到的优越性。3 PRAM到 LogP的转换算法Log P和 PRAM是完全不同的两种并行计算模型 ,前者是基于网络的分布式存储结构 ,后 者是共享

9、内存结构。 共享内存结构可以看成是全局共享一个地址空间 ,而内存是分布在各个处理器上 ,实际上在许多大规模并行处理机上就是这样实现的。 根据 PRAM模型和 LogP模型的特性 ,我们提出了算法在这两种模型之间进行转换的方法 ,首先将 PRAM程序转换为与之 等价的 Log P程序 ,然后将共享的内存单元分配给每个处理器 ,最后进行线性分组优化。 其过程如图 3所示:图 3 PRAM模式到LogP模式的转换示意图关于分组优化的问题在后面讨论 ,现在先来讨论将一个算法在两种模型之间进行转换。 在 PRAM模型中 ,每个进程通过共享内存变量进行通信 ,在进程开始时从共享内存读取输入数据 ,在进程结

10、束时从局部内存向共享内存写结 果。 因此 ,我们可以列出在每个进程中从别的进程得到的结果变量和别的进程要用到的变量 ,将与各个变量联系的赋值语句转换为相应的消息传送或接收语句。当共享内存变量 V出现在赋值语句的右边时 ,则本进程 i从相应的进程 j接收 V;当共享内存变量 V出现在赋值语句的左边时 ,则本进程 i向要用到共享内存变量 V的进程 j发送 V。设共享内存用整型数组 Arr表示 , V1, . . . , Vm为局部变量 ,进程 i在 t时刻执行赋值语句如下:Arr f(i): = ( Arr1f1(i) , . . . , Arrmfm(i)其中 , 为一表达式 , fj(i)为只

11、与i有关的函数。则该进程转换为消息传递模型的算法如下:Process( i, t)V1: = receiv e( Arr f1( i), ( f1(i) , t1) ) ;V2: =receiv e(Arrf2(i), (f2(i) ,t2) ) ;Vm: =receive(Arrfm(i), (fm(i) ,tm) );V1: =(V1, . . .Vm ;send(V1, (i1, t1) );send(V2, (i2, t2) );send(Vk, (ik, tk) );End 其中 receive( Arr fj(i), ( fj(i) , tj) )表示进程 i在 t时刻接收从进程

12、fj(i)在 tj时刻发送来的数据 Arrfj(i),相应地 , send(Vj, (ij, tj) )表示进程 i在 tj时刻向进程 ij发送数据 Vj。这样 ,基于 PRAM模型的程序就可转换为与之等价的基于 LogP模型的程序 ,由于每个节点上的处理器都带有大量的 DRAM内存 ,可以为每条通信通道设置一个缓存 ,因此 ,其通信方式可以是异步的。 要进一步优化 LogP模型的算法 ,则需充分考虑消息传递和消息处理的延迟及网络的带宽。 由于网络通信延迟 ,当两个进程并行执行的时间大于其串行执行时间时 ,就有必要将两个进程合并成一个进程以减少执行时间;但这样就会降低并行度。 如何选择一个平衡

13、点就成为优化 Log P模型的一个重要环节。 本文提出了一个基于通信结构的有向无环图分组优化策略。296期 焦 进等: 将基于PRAM模型的算法转换为基于Log P模型的算法的一种方法 4 构造有向无环图在 PRAM模型中 ,我们定义处理器 i与处理器 j发生一次通信为: 当处理器 j在 t1时刻写完公共内存中某个单元后 (对 EREW PRAM独占读写 PRAM模型而言 ,同一时刻只能由一 个进程读写共享内存的同一内存单元 )或同时 (对 CRCW PRAM并发读写 PRAM模型而言 ,同一时刻允许有多个进程读写共享内存的同一内存单元 ) ,处理器 i在 t2时刻读取该单元内的数据 , t1

14、 t2,且在 t1到 t2时刻内没有其他处理器写数据到该单元 ,我们则称处理器 i在 t2时刻与处理器 j进行了一次通信 ,用 Communicate(i, t2, j, t1)= 1来表示。假设一个 PRAM算 法 A的数据结构为数组 ,其大小为 n,而算法的输入数据尺寸即为该数组的大小 ,算法 A所用到的处理器数为 P( n) ,最长运行时间为 T( n)。 那么我们定义算法 A的通信结构为一个有向无环图。 定义: 算法 A的输入 x的大小为 n,则其通信结构为一个有向无环图 Gx= ( Vx, Ex) ,其中:Vx= : 0 i , ): t =2iThen aj : =aj +aj -

15、2i- 1;Endif;Endfor; Endfor; 该算法的 P( n)= n, T( n)= 2. logn- 1 。 当 n= 16时 ,其通信结构有向无环图如图 4所示:图 4 前缀求和算法的通信结构图显然 ,该算法的最长运行时间取决于其通信结构有向无环图 G中的最长路径。 设 G的直 径为 D,深度为 d,各个节点中的最长运行时间为 ,则在最长路径上需计算 D个任务 ,要进行30小 型 微 型 计 算 机 系 统 1997年D- 1次通信 ,而发送和接收每条消息需时间为 o,由于 G的深度为 d,故每个进程最多可接收 或发送 d条消息 ,每次接收或发送必须有时间间隔为 g。 因此

16、,整个算法的最长运行时间 T应满足以下条件:T ( D- 1)*L + D * ( (d- 1)* max( g, o)+ o+ ( ).5 分组优化前面我们定义了算法的通信结构有向无环图 ,下面我们就针对该有向无环图进行线性分组优化。 分组就是将有向无环图中的节点映射到 m个组 (对应于 m个处理器 ) ,使得每个组中的任务都在同一个处理器上执行。我们假设用四元组 (v, w, t, p)来表示节点 v在 t时刻与处理器 p的状态关系 w,有计算 c( w= compute) ,从 p接收数据 r( w= receive)和向 p发送数据 s( w=send)三种状态。 则可定义 LogP模型分组如下:定义: 对于有向无环图 G的分组 C为一个由若干个组 Bi组成的 ,每个组 Bi为一个四元组的有限序列 ,且满足以下条件:( 1) 对于任意 (v, w, t