基于消息传递接口(message passing interface,MPI),对不同的等高线简化算法并行计算的适宜性进行了比较研究。首先基于时间复杂度分析,对简化算法的效率进行分析。构建了基于MPI的等高线并行计算过程,探讨了并行计算中数据划分与合并、通信方式与计算过程3个关键问题。选取4种典型的简化算法,利用数据量呈等差分布的等高线数据进行简化并行计算试验。试验表明,算法并行计算效率不会随着节点数增加而持续性提高,尤其是串行算法效率很高的算法;基于MPI的非阻塞通信方式相对于阻塞通信方式可以提高并行计算效率;算法约束参数与数据的空间分布特征共同影响算法的并行计算效率。分析简化算法的并行计算适宜性时,应该综合考虑算法的时间复杂度、约束参数、数据量、数据分布特征以及计算环境等多个因素。该研究对于并行计算在地图综合乃至地学计算领域的拓展与应用具有重要意义。
The parallel computing suitability of the different contour simplification algorithms was compared based on MPI. The efficiency of the simplification algorithms was analyzed based on the time complexity analysis. The three key points such as data partitioning and consolidating, communication mode and computing process was explored after we constructed the parallel computing process of contour simplification. The study selected four typical simplification algorithms and ran the parallel computing experiment using the contour data which the quantity is arithmetic. The experiment result proves that the parallel computing efficiency of the simplification algorithms cannot be constantly promoted with the computing nodes increasing, especially for the high efficiency serial algorithms. The non-blocking communication mode can help to promote the parallel computing efficiency comparing to the blocking communication mode in MPI. The constraints of the simplification algorithms and the distribution characteristics of the spatial data influence the parallel computing efficiency. Analyzing the parallel computing suitability of simplification, time complexity and the constraints of the simplification algorithms, quantity and the distribution characteristic of data and computing environment should be considered. The study bears substantial significance to the development and application of parallel computing in map generalization and geo-computing area.