将基于PRAM模型的算法转换为基于LogP模型的算法的一种.pdf

《将基于PRAM模型的算法转换为基于LogP模型的算法的一种.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、PRAM、BSP、LogP等多种并行计算模型。不同类型的并行计算机通常有不同类型的并行计算模型,而一般解同一个问题在不同类型的并行计算机上需要有不同的并行程序,这就给用户带来了极大的困难,使得并行计算机难以推广使用。为了便于并行程序在不同类型的并行计算机上移植,必须对基于某种并行计算模型的算法转换为基于另一种并行计算模型的算法的方法进行深入研究。以前研制的并行算法多数是基于PRAM模型的,已经取得了相当广泛的应用。但是PRAM模型也存在着同步困难、通讯效率低等缺点,为了克服这些不足,近年来国际上提出了不少新的并行计算模型。其中LogP模型由于充分考虑了并行

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

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

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

6、的微处理器、Cache和大容量的DRAM内存组成。LogP模型是由一组通过点对点消息传递的进程组成的模型。它们〔1〕的通信性能可以用以下四个参数来刻划:L:通信延迟(Latency)。是在源地址和目的地址之间发生短消息(消息长度较短)传递的延迟上界。o:通信开销(overhead)。定义为一个处理器传送或接收消息的时间长度,在这期间,处理器不能执行别的操作。g:通信间隔(gap)。定义为一个处理器在连续传送或连续接收消息时的最小时间间隔,即每个处理器的可用通信带宽。P:处理器数目(Processors)。在该模型中没有考虑各个处理器的特性。LogP模型示意

7、如图2所示:LogP模型是异步执行的,消息传递的延迟上限是L,在任意时刻最多可以有[L/g]条消息在网上传递,如超出这个限制则传送会停顿直到要传递的消息小于这个限制。由图2可见,一个最简单的图2LogP模式示意图通信操作,从一个处理器向另一个处理器发送或接收消息,需要L+2o的时间。而如果要向另一个处理器发送一组n条消息,则可形成一条通信流水线,处理器在花费o时间发送第一条消息后,即可每隔一个时间间隔g发送下一条消息,每条消息花费L时间到达目的地,接收方花费o时间接收每条信息。因此总共〔2〕花费了2o+(n(1)g+L时间。而处理器之间交换n条信息则复杂得

8、多,执行时间为2L+2o+(n-1-L/g)*max(g,2o)。