{"id":1739,"date":"2016-09-09T11:44:35","date_gmt":"2016-09-09T02:44:35","guid":{"rendered":"http:\/\/163.152.162.219\/wordpress\/?p=1739"},"modified":"2020-01-02T15:59:37","modified_gmt":"2020-01-02T06:59:37","slug":"high-performance-computing-for-viscosity-solution","status":"publish","type":"post","link":"https:\/\/hvcl.korea.ac.kr\/?p=1739","title":{"rendered":"High-performance computing for viscosity solution"},"content":{"rendered":"

Eikonal Equation <\/strong><\/p>\n

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.\u00a0 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).\u00a0 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.\u00a0 It includes an advanced label-correcting method, adaptive domain decomposition method, heterogeneous computing approach, streaming solution.<\/p>\n

A Group-Ordered Fast Iterative Method<\/strong><\/p>\n

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.<\/p>\n

\"\"<\/p>\n
[bibtex file=hong_group_2016.bib]<\/div>\n<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n
\n

A Multi-GPU Fast Iterative Method using On-the-fly Adaptive Domain Decomposition<\/strong><\/p>\n

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\u00a0 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\u0002 for eight GPUs, and can handle large computing problems that do not \ffit to limited GPU memory.<\/p>\n

\"\"<\/p>\n
[bibtex file=hong_multifim_2016.bib]<\/div>\n<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n
\n
\n<\/div>\n
<\/div>\n
A Causality-Ordered Fast Iterative Method for Eikonal Equations<\/strong><\/div>\n
<\/div>\n
The Fast Iterative Method (FIM) is an efficient numerical algorithm to solve the eikonal equation for a broad range of applications.\u00a0 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.\u00a0 However, the computational cost of FIM is significantly affected by the complexity of the input data; it hurts the overall performance of the algorithm.\u00a0 In this work, we propose a novel algorithm, the Causality-Ordered Fast Iterative Method (CO-FIM), to solve redundant computation problems of FIM.\u00a0 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.<\/div>\n
<\/div>\n
\"\"<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"

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.\u00a0 Recently, the research on eikonal equation solvers has focused more on developing efficient parallel algorithms to leverage the computing power of parallel systems, such Read More<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/posts\/1739"}],"collection":[{"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1739"}],"version-history":[{"count":12,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/posts\/1739\/revisions"}],"predecessor-version":[{"id":5085,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=\/wp\/v2\/posts\/1739\/revisions\/5085"}],"wp:attachment":[{"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1739"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1739"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hvcl.korea.ac.kr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1739"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}