banner about

A GPU-Enabled Toolbox for Solving Hamilton-Jacobi and Level Set Equations on Unstructured Meshes

Acknowledgement:

This material is based upon work supported by the National Science Foundation under Grant No. OCI-1148291 (PI: Kirby and co-PI: Whitaker).

Disclaimer:

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Award title:

SI2-SSE: A GPU-Enabled Toolbox for Solving Hamilton-Jacobi and Level Set Equations on Unstructured Meshes.

Duration:

June 1, 2012 through May 15, 2015


Research Challenges and Project Goal

A variety of application domains from geophysics to biomedicine employ some form of Hamilton-Jacobi (H-J) mathematical models. These models are a natural way to express conservation properties, and the two most prevalent H-J models seen in the literature are the Eikonal equation (a static H-J model based upon Fermat's Principle for determining minimal paths) and the Level-Set equations (a time-dependent H-J model used for addressing moving interface problems). The goal of this effort is to develop, test, document and distribute a collection of software tools for efficiently solving several classes of equations of H-J type – in particular, Eikonal (minimal path) equations and Level-set equations – on unstructured (triangular and tetrahedral) meshes using commodity streaming architectures. The PIs have previously demonstrated the feasibility of efficiently solving H-J equations on GPUs; this effort seeks to both scientific extend previous work as well as solidify the software into a publicly available tool suite.


Research Team

mike kirby ross whitaker zhisong fu dillon lee

Dr. Robert M. Kirby

Dr. Kirby is currently an Associate Professor in the School of Computing and a faculty member of the Scientific Computing and Imaging Institute at University of Utah. His research focus is on large-scale scientific computing and visualization, with an emphasis on the scientific cycle of mathematical modeling, computation, visualization, evaluation, and understanding.

Dr. Ross T. Whitaker

Dr. Whitaker is a Professor in the School of Computing and a faculty member of the Scientific Computing and Imaging Institute. He teaches image processing, computer vision, and pattern recognition. Ross run the Image Processing Laboratory, conducting research in image processing, computer vision, pattern recognition, and visualization. His approach to problems in these domains is usually based upon his background in differential geometry, differential equations, and signal processing.

Zhisong Fu - Ph.D. Student

Zhisong received his Bachelors of Engineering, Computer Science from Zhejiang University in China. He is presently a Ph.D student at Scientific Computing and Imaging Institute working with Professors Whitaker and Kirby on solving Eikonal equations with anisotropic speed on tetrahedral meshes, as well as building an efficient parallel FEM solver with Multigrid methods.

Dillon Lee - Developer

Dillon Lee has spent most of his time working with web-based technologies. Throughout his educational and professional development, Dillon's primary focus has been on developing applications using sound software architecture and well established design patterns. Before joining the Software Development Center, Dillon worked at Numira Biosciences as a Software Engineer where he developed software in the field of scientific visualization. Dillon received his Bachelor of Science in Computer Science from the University of Utah in 2009.

 


Intellectual Merit

The main intellectual merit of this work is the development of efficient algorithmic strategies for mapping numerical methods for solving H-J equations on unstructured meshes to commodity streaming architectures. The challenges of developing efficient algorithms for H-J equations on streaming architectures are significant. One challenge is maintaining sufficient computational density on the parallel blocks, especially as we move to 3D unstructured meshes. A second technical challenge is the loss in efficiency that comes with communication between blocks. These topics are being investigated in relation tospecific H-J implementations on the GPU.


Broader Impact

Our goal is to deploy currently available commodity streaming architectures so that personal supercomputing can become ubiquitous in a variety of communities that rely on simulation-based experiments. By overcoming the tedious and non-trivial step of developing and distributing software for solving H-J equations on unstructured meshes using commodity streaming architectures, the impact of this work has both longevity and ubiquity in a wide range of applications in diverse fields such as basic science, medicine, and engineering. Through a combination of peer-reviewed journal papers, publicly available software, on-site graduate and post-graduate training, and workshops and tutorials, we anticipate the scaffolding put in place through this focused effort will allow us and others to transform their simulation pipelines to currently available hardware, and in so doing enable new creative processes and accelerate their "time-to-discovery" through effective computing.


Current Results

Our currently focus upon initiation of this grant is two-fold: to start the "hardening" of previously developed GPU software routines (in particular, Eikonal solvers) and to initiate our scientific/technical investigation of efficiently solving level-set equations over unstructured meshes using GPUs.


Publications

2012:

Zhisong Fu, Robert M. Kirby and Ross T. Whitaker, "A fast iterative method for solving the Eikonal equation on tetrahedral domains", SIAM Journal of Scientific Computing, Under Review, 2012.


Z. Fu, T. James Lewis, Robert M. Kirby and Ross T. Whitaker, "Architecting the Finite Element Method Pipeline for the GPU", Journal of Computational and Applied Mathematics, Under Review, 2012.


References


Z. Fu, W.-K. Jeong, Y. Pan, R. M. Kirby, and R. T. Whitaker, "A fast iterative method for solving the Eikonal equation on triangulated surfaces", SIAM Journal of Scientific Computing, Vol. 33, No. 5, pages 2468-2488, 2011.