.png){kind=icon}
返回
Parallelizing discrete geodesic algorithms with perfect efficiency
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cad.2019.05.023.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper presents a new method for parallelizing geodesic algorithms on triangle meshes. Using the half-edge data structure, we define the propagation dependency graph to characterize data dependency in computing geodesics. Then, we design an active strategy such that the vertices and half-edges on the wavefront take the initiative to collect their input data and then propagate windows and update geodesic information in their own memory space. As a result, all the read and write operations can be carried out simultaneously. Our method, named AWP, works for both exact (e.g., the CH algorithm) and approximate (e.g., the fast marching method) geodesic algorithms. Our implementation on various NVIDIA GPUs exhibit perfect linear speedup, i.e., doubling the computational power (i.e., FLOPS) doubles the speed. We prove that the AWP-CH algorithm runs in O(n(2)/min(C, n)) time, where n and C are the numbers of faces and cores, respectively. Evaluation on GTX Titan XP shows that AWP-CH empirically runs in n(p) time, p is an element of [1.25, 1.35], for real-world models with n <= 10(7) and anisotropy measure tau <= 2.0. Thanks to its perfect efficiency and the trend of increasing the number of processors in graphics hardware, we believe that the actual performance of AWP can be further improved in the near future. (C) 2019 Elsevier Ltd. All rights reserved.
Keyword:
Discrete geodesics
Autonomous wavefront propagation
The Chen-Han algorithm
The fast marching method
Parallel algorithm
Perfect efficiency
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
3.1
论文数:
3.1K
被引数:
6.4K
机构
引用论文
.png){kind=icon}
EARLY DETECTION OF IMPLANTATION USING A RADIOIMMUNOASSAY SPECIFIC FOR HUMAN CHORIONIC GONADOTROPIN
PREAI
分享收藏
Saddle Vertex Graph (SVG): A Novel Solution to the Discrete Geodesic Problem鞍顶点图 (SVG): 离散测地问题的新解决方案
PREAI
分享收藏Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams从测地线Voronoi图的对偶构造内在的Delaunay三角剖分
OAAI
OAAI分享收藏
查看更多内容