更实际的并行计算模型

MORE REALISTIC PARALLEL COMPUTATION MODELS

过去所报导的大量并行算法在小规模的并行机上均运行得很好，然而将其移植到大规模并行机上运行时性能却很差。原因之一就是并行计算模型（如ＰＲＡＭ）过于抽象，略去了一些诸如通信、同步等算法运行时不可忽略的因素。本文介绍目前所提出的几个较能反映近代并行机性能的更为实际的并行计算模型，包括异步ＰＲＡＭ，ＢＳＰ，ｌｏｇＰ和Ｃ３模型等。当然这些模型在与真实并行机吻合的程度、可使用性和分析较复杂算法时的可操作性等方面尚存异议，但是它们的确打开了研究并行计其模型的新途径，成为当今并行算法研究的热点之一。

The often reported many parallel algorithms were performed well on the small scale parallel computers,and found to perform poorly when transported to the large scale parallel computers.One of the reason is that the parallel computation model that algorithms based on is overly abstract,without considering the facts such as communication and synchronization which are very important during running algorithms.In this paper,we discuss some more realistic computation models including phase PRAM,BSP,logp and C3 models.Of course,as other new propossls,there will naturally be concerns regarding their utilities,matching the models to real machines and tractable to analyze non-trivial algorithms.However,they indeed open several avenues of researching parallel computation models becoming research highlight of algorithms.