计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

基于数据并行的碰撞检测

彭振,吴百锋   

  1. (复旦大学 计算机科学技术学院,上海 201203)
  • 收稿日期:2016-11-14 出版日期:2017-09-15 发布日期:2017-09-15
  • 作者简介:彭振(1987—),男,硕士研究生,主研方向为高性能计算;吴百锋,教授、博士生导师。
  • 基金项目:
    鲁班软件大学合作计划项目。

Collision Detection Based on Data Parallelism

PENG Zhen,WU Baifeng   

  1. (School of Computer Science,Fudan University,Shanghai 201203,China)
  • Received:2016-11-14 Online:2017-09-15 Published:2017-09-15

摘要: 在建筑信息建模的精确碰撞检测应用中,数据量日趋庞大,但串行执行无法随处理机主频的增加而持续加速。针对该问题,构建面向多核及众核处理机的数据并行计算模型,基于此提出一种数据并行碰撞检测方法。对参与碰撞检测的模型进行立方体细分,去除数据相关性,设计数据并行的模型组合、冲突检测和归约计算过程,并分析算法的抽象形式和理论执行时间。实验结果表明,该方法具有可行性和持续可扩展性,可为解决数据密集型问题提供一种高效的数据并行方式。

关键词: 数据并行, 碰撞检测, 单指令多数据, 建筑信息建模, 持续可扩展性

Abstract: The application of accurate collision detection in Building Information Modeling(BIM) is facing the increasingly large amount of data,but the serial execution cannot continue to accelerate with the increasing frequency of the processor.Aiming at this problem,this paper constructs a data parallel computing model for multicore and manycore machines and proposes a data parallel collision detection method based on this model.Firstly,models within collision detection are divided into cubes and the data correlation is removed.Secondly,the data parallel computing process with model combination,conflict detection and reduction calculation is designed.At last,the abstract forms and the theoretical execution times of the algorithm are analyzed.Experimental result shows that the proposed method has feasibility and continuous scalability which provides an efficient data parallel mode for solving data intensive problem.

Key words: data parallelism, collision detection, Single Instruction Multiple Data(SIMD), Building Information Modeling(BIM), continuous scalability

中图分类号: