High-performance computing for viscosity solution

Eikonal Equation

The Eikonal equation has been widely used in diverse fields, such as geoscience and geophysics, computer vision, image processing, path planning and computer graphics. It is a nonlinear boundary value problem defined by a first order hyperbolic partial differential equation. The Eikonal equation represents the wave propagation from the seed region where the motion is governed by the speed function, and the solution of the equation represents the geodesic distance of the shortest path from the nearest seed point. In HVCL, we are interested in High-performance computing for the Eikonal equation solver using multiGPU-cluster. 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.

  • [PDF] [DOI] S. Hong and W. K. Jeong, “A group-ordered fast iterative method for eikonal equations,” IEEE transactions on parallel and distributed systems, vol. 28, iss. 2, pp. 318-331, 2017.
    [Bibtex]
    @ARTICLE{hong_group_2016,
    author={S. Hong and W. K. Jeong},
    journal={{IEEE} Transactions on Parallel and Distributed Systems},
    title={A Group-Ordered Fast Iterative Method for Eikonal Equations},
    year={2017},
    volume={28},
    number={2},
    pages={318-331},
    keywords={iterative methods;multiprocessing systems;parallel algorithms;parallel architectures;pattern clustering;GO-FIM;blocks clustering;eikonal equations;grid blocks;group-ordered fast iterative method;lock-free local queue approach;multicore parallel architectures;numerical algorithms;parallel algorithm;Algorithm design and analysis;Data structures;Graphics processing units;Iterative methods;Parallel algorithms;Parallel architectures;Eikonal equation;{GPU};parallel computing},
    doi={10.1109/TPDS.2016.2567397},
    ISSN={1045-9219},
    month={Feb},}

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.

  • [PDF] [DOI] S. Hong and W. Jeong, “A multi-GPU fast iterative method for eikonal equations using on-the-fly adaptive domain decomposition,” Procedia computer science, vol. 80, pp. 190-200, 2016.
    [Bibtex]
    @article{hong_multifim_2016,
    title = "A Multi-{GPU} Fast Iterative Method for Eikonal Equations Using On-the-fly Adaptive Domain Decomposition ",
    journal = "Procedia Computer Science ",
    volume = "80",
    number = "",
    pages = "190 - 200",
    year = "2016",
    note = "International Conference on Computational Science 2016, \{ICCS\} 2016, 6-8 June 2016, San Diego, California, \{USA\} ",
    issn = "1877-0509",
    doi = "http://dx.doi.org/10.1016/j.procs.2016.05.309",
    url = "http://www.sciencedirect.com/science/article/pii/S1877050916306676",
    author = "Sumin Hong and Won-Ki Jeong",
    keywords = "Eikonal equation",
    keywords = "fast iterative method",
    keywords = "{GPU}",
    keywords = "parallel algorithms",
    keywords = "domain decomposition ",
    abstract = "Abstract The recent research trend of Eikonal solver focuses on employing state-of-the-art parallel computing technology, such as {GPU}s. Even though there exists previous work on {GPU}-based parallel Eikonal solvers, only little research literature exists on the multi-{GPU} Eikonal solver due to its complication in data and work management. In this paper, 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 {GPU}s. The proposed method scales well, up to 6.17x for eight {GPU}s, and can handle large computing problems that do not fit to limited \{{GPU}\} memory. We assess the parallel efficiency and runtime performance of the proposed method on various distance computation examples using up to eight {GPU}s. "
    }