Eikonal Equation
The eikonal equation has a wide range of applications related to distances or travel time in space, such as geoscience, computer vision, image processing, path planning, and computer graphics. Recently, the research on eikonal equation solvers has focused more on developing efficient parallel algorithms to leverage the computing power of parallel systems, such as multi-core CPUs and graphics processing units (GPUs). However, only a little research literature exists for the massively parallel eikonal equation solver because of its complications related to data and work management. In HVCL, we are interested in high-performance computing for the eikonal equation solver. It includes an advanced label-correcting method, adaptive domain decomposition method, heterogeneous computing approach, streaming solution.
A Group-Ordered Fast Iterative Method
In the past decade, many numerical algorithms for the eikonal equation have been proposed. Recently, the research of eikonal equation solver has focused more on developing efficient parallel algorithms in order to leverage the computing power of parallel systems, such as multi-core CPUs and GPUs. In this work, we introduce an efficient parallel algorithm that extends Fast Iterative Method, originally developed for the GPU, for multi-core shared memory systems. First, we propose a parallel implementation of FIM using a lock-free local queue approach and provide an in-depth analysis of the parallel performance of the method. Second, we propose a new parallel algorithm, Group-Ordered Fast Iterative Method (GO-FIM), that exploits causality of grid blocks to reduce redundant computations, which was the main drawback of the original FIM. In addition, the proposed GO-FIM method employs clustering of blocks based on the updating order where each cluster can be updated in parallel using multi-core parallel architectures.
A Multi-GPU Fast Iterative Method using On-the-fly Adaptive Domain Decomposition
The recent research trend of eikonal solver focuses on employing state-of-the-art parallel computing technology, such as GPUs. Even though there exists previous work on GPU-based parallel eikonal solvers, only a little research literature exists on the multi-GPU Eikonal solver due to its complication in data and work management. In this work, we propose a novel on-the-fly, adaptive domain decomposition method for efficient implementation of the block-based Fast Iterative Method on a multi-GPU system. The proposed method is based on dynamic domain decomposition so that the region to be processed by each GPU is determined on-the-fly when the solver is running. In addition, we propose an efficient domain assignment algorithm that minimizes communication overhead while maximizing load balancing between GPUs. The proposed method scales well, up to 6.17 for eight GPUs, and can handle large computing problems that do not fit to limited GPU memory.
