.png){kind=icon}
返回
AN EASILY IMPLEMENTED, BLOCK-BASED FAST MARCHING METHOD WITH SUPERIOR SEQUENTIAL AND PARALLEL PERFORMANCE
.png){kind=icon}
OA
AI
DOI：10.1137/18M1213464.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The fast marching method is well known for its worst-case optimal computational complexity in solving the Eikonal equation, and it has been employed in numerous scientific and engineering fields. However, it has barely benefited from fast-advancing multicore and many-core architectures because of the challenges presented by its apparent sequential nature. In this paper, we present a straightforward block-based approach for a highly scalable parallelization of the fast marching method on shared-memory computers. Central to our new algorithm is a simplified restarted narrow band strategy, which is used to replace the global bound for terminating the front marching by an incremental bound that increases by a given stride in each restart. Our algorithm greatly reduces load imbalance among blocks through a synchronized exchanging step after the marching step. Furthermore, simple activation mechanisms are introduced to skip blocks not involved in either step. Thus the new algorithm mainly consists of two loops, each for performing one step on a group of blocks. Notably, it does not contain any data race conditions, which is ideal for a direct loop level parallelization using multiple threads. A systematic performance study is carried out for several point source problems with various speed functions on grids with up to 1024(3) points using two different computers. Substantial parallel speedups, e.g., up to 3-5 times the number of cores on a 16-core/32-thread computer and up to 2 orders of magnitude on a 64-core/256-thread computer, are demonstrated with all cases. As an extra bonus, our new algorithm also gives much improved sequential performance in most scenarios. Detailed pseudocodes are provided to illustrate the modification procedure from the single-block to the multiblock sequential algorithm in a step-by-step manner.
Keyword:
Eikonal equation
fast marching method
narrow band approach
domain decomposition
parallel algorithm
shared-memory parallelization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容