High-performance computing for viscosity solution

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.

  • [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. "
    }

A Causality-Ordered Fast Iterative Method for Eikonal Equations

The Fast Iterative Method (FIM) is an efficient numerical algorithm to solve the eikonal equation for a broad range of applications.  Because it is based on simple queues instead of complex data structures, this algorithm has inherent parallelism and has been extended to various parallel computing systems, such as multiCPUs or multiGPUs.  However, the computational cost of FIM is significantly affected by the complexity of the input data; it hurts the overall performance of the algorithm.  In this work, we propose a novel algorithm, the Causality-Ordered Fast Iterative Method (CO-FIM), to solve redundant computation problems of FIM.  The proposed method introduces causality information between grid nodes. This efficiently prevents the situation in which nodes having dependency on each other are updated at the same time, which is the main reason for redundant calculations of FIM. Moreover, we propose a hybrid parallel algorithm that combines with the Group-Order approach.