地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (5): 568-574.doi: 10.3724/SP.J.1047.2015.00568

• 本期要文(可全文下载) • 上一篇    下一篇

并行地理计算算法性能评测技术研究

陈翠婷1,2, 方金云1,2, 邱强1,2, 姚晓1,2, 李栋宾2   

  1. 1. 中国科学院大学, 北京100049;
    2. 中国科学院计算技术研究所, 北京100190
  • 收稿日期:2014-12-26 修回日期:2015-02-22 出版日期:2015-05-10 发布日期:2015-05-10
  • 通讯作者: 方金云(1967-),男,副研究员,博士生导师,主要从事海量空间信息处理技术等研究。E-mail:fangjy@ict.ac.cn E-mail:fangjy@ict.ac.cn
  • 作者简介:陈翠婷(1991-),女,硕士生,主要从事空间分析算法、并行计算、数据挖掘等研究。E-mail:chencuiting@ict.ac.cn
  • 基金资助:

    国家高技术研究发展计划"( 863"计划)基金项目(2011AA120302、2011AA120306)。

A Technology to Evaluate the Performance of Parallel Geo-Computing Algorithms

CHEN Cuiting1,2, FANG Jinyun1,2, QIU Qiang1,2, YAO Xiao1,2, LI Dongbin2   

  1. 1. University of Chinese Academy of Sciences, Beijing 100049, China;
    2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2014-12-26 Revised:2015-02-22 Online:2015-05-10 Published:2015-05-10

摘要:

从并行地理算法的正确性评测、性能评测、评测流程和评测工具实现等角度,研究了高性能集群环境下的评测技术。在正确性评测假设基础上,将评测用例在不同进程数环境下的计算结果与该算法在单进程环境下的运算结果逻辑求差得出相对误差,提出了问题规模计算方法。根据评测用例的问题规模确定评测用例的权重,提出了性能指标和评测流程,并通过评测工具自动获得同一个并行地理计算算法。在多个不同评测用例下的评测指标来衡量算法的计算误差与性能,形成评测报告。经实验验证,本文方法能较好地满足并行地理计算算法评测的需求,为并行空间分析算法性能优化提供技术保障。

关键词: 地理计算, 并行算法, 正确性评测, 性能评测

Abstract:

We study and propose the evaluation approach for parallel geo-computation algorithms from the following aspects: correctness evaluation, performance evaluation, evaluation routines and evaluation tools. This approach proposes the hypotheses for correctness evaluation which are viewed as the foundation of measuring the correctness of geo-computation algorithms. To measure the correctness, we compute the relative errors by comparing the results using a certain algorithm under the single-process with the corresponding results evaluated under the multi-process environment. In this paper, we present a method in which the weights of the evaluation cases are determined by the computation scale. We also discuss a method which computes the computation scale of evaluation cases. The method involves the data scale, data distribution coefficient and time consumption per unit computation. Meanwhile, the geo-computation algorithms are evaluated by cases with weights. Under some circumstances, we can obtain the various evaluation indicators of a certain algorithm, such as the execution time, the speedups, and the parallel efficiency. In addition, this paper designs an evaluation routine based on the correctness evaluation and performance evaluation. It obtains the correctness evaluation and performance indicators of our target algorithms and generates the final reports. After experiments, we may confirm that our techniques can meet the requirements for evaluating parallel geo-computation algorithms. It could provide an effective support to algorithm optimization.

Key words: parallel algorithms, correctness evaluation, performance evaluation, geo-computation