一种实用的并行计算模型

对于当前流行的工作站集群环境和各类并行机系统，文中提出了一种实用的并行计算模型，即基于LogGP的非独占异质同步模型NHBL（Nondedicated Heterogeneous Barrier LogGP），它旨在反映具有异质性和非独占性的NOW计算环境对并行算法设计和分析的影响，然后用NHBL模型分析了PSRS算法在国家高性能计算中心（合肥）的工作站集群NHPCC-Cluster和曙光－1000MPP由的代价，并用实测结果进行了验证。

A Realistic Parallel Computational Model

Network of workstations, NOW or COW, is attracting increased attention as a variable platform for high performance parallel computation. It has higher ratio of performance to price, and it is also more flexible and more scalable. But NOW has two major characteristics, nondedicated and heterogeneous, which distinguish the NOW system from conventional multi processor or other multi computer systems, and make other parallel computational models unsuitable and inaccurate for it. Thus a realistic parallel computational model, called Nondedicated Heterogeneous Barrier LogGP model, NHBL, is presented for NOW and MPP in this paper. NHBL model is based on the LogGP model and is expanded to fit in with NOW's special characteristics. This model is aimed to reflect the influence of different computing power between workstations and the influence of computations occupied by other user's applications on designing and analysis of parallel algorithms on NOW. This model also presents accurate computation and communication cost models. In this paper, we first describe NHBL model and its computation and communication cost models in details, and show the programming style and the method of NHBL model using PSRS algorithm under MPI environment. Then the computation and communication costs of PSRS algorithm are analyzed with NHBL model. At last, PSRS algorithm is implemented on NHPCC NOW and Dawning 1000 MPP, which located in National High Performance Computing Center at Hefei, and the analysis results are validated by those experiment results. Experimental results show that NHBL model captures the most important features of NOW, and it is practical and correct for NOW and MPP. Furthermore, NHBL model is a realistic computational model since it can work only with a subset of the parameters that is enough to the design and analysis of algorithms on certain platforms. More experiment data on more platforms and more accurate and simple cost models are our future work.