PRAM%2cBSP和LogP并行模型之间的关系及比较.pdfVIP

刘久星孙永强 (上海交通大学计算机科学及￡程系 上海200030) 摘要本文详细讨论jPRAM，BSP和LogP三种并行模型。我们提出用一个五元组 (P，G，o，L，s)来概括这三种模型，并指出它们之间的关系。本文还讨论j这 三种模型各自的优缺点，并指出BSP模型在总体上优于其他两种模型。 PRAM 关键词BSP Lngp并行计算模型 The and of the and Model Relationship PRAM，BSP Comparison LogP Liu Sun JiuxingYongqiang of Scienceand (Department Computer Engineering，ShanghaiJiaotong 200030) University，Shanghai AbstractInthis we discuss aboutthe and modeland a paper PRAM，BSP thoroughly LogP present methoda describethesemodels．Wealso the usingtuple(P，G，O，L，S)to coveradvantages and and ofthesemodelsreachtheconlusionthattheBSP is to disadvantages model superior other the two models， BSP KeywordsPRAM Parallel Model LogP Computing 目前，在并行汁算机的研究中，存在者一些“通用”的计算模型，其中最有影响的是PRAM，BSP和L罐P三种。这些模 型的应用非常广泛。首先，它们给并行算法的设计者提供了一个进行算法设计和分析的基础。其捩，这些模型都具有一定 的通用性，它们掩盖了大部分和具体机器相关的细节．从而使在这些模型上设计出的算法和程序具有良好的可移植性．能 够适用于一大类的目标机器。也就是说，这些模型是和体系结构无关的。另外．当井行算法具体应用到某一目标机器时． 它们可以给程序的性能评测(程序的运行时间，可扩展性等)提供依据[5]。 种模型，并指出它们之间的关系。本文还讨论yNZ-2种模型各自的优缺点，并指出BSP模型在总体上优于其他两种模型。 1三种模型的介绍 1．1 PRAM模型 RandomAccess PRAM(Parallel 局的共享存储器构成。各处理机同步地进行工作，都按读存储器、计算、写存储器的步骤