Award Abstract # 1148291
SI2-SSE: A GPU-Enabled Toolbox for Solving Hamilton-Jacobi and Level Set Equations on Unstructured Meshes

NSF Org: OAC
Office of Advanced Cyberinfrastructure (OAC)
Recipient: UNIVERSITY OF UTAH
Initial Amendment Date: June 25, 2012
Latest Amendment Date: March 31, 2014
Award Number: 1148291
Award Instrument: Standard Grant
Program Manager: Rajiv Ramnath
OAC
 Office of Advanced Cyberinfrastructure (OAC)
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: June 1, 2012
End Date: May 31, 2016 (Estimated)
Total Intended Award Amount: $499,999.00
Total Awarded Amount to Date: $531,999.00
Funds Obligated to Date: FY 2012 = $499,999.00
FY 2013 = $16,000.00

FY 2014 = $16,000.00
History of Investigator:
  • Robert Kirby (Principal Investigator)
    kirby@cs.utah.edu
  • Ross Whitaker (Co-Principal Investigator)
Recipient Sponsored Research Office: University of Utah
201 PRESIDENTS CIR
SALT LAKE CITY
UT  US  84112-9049
(801)581-6903
Sponsor Congressional District: 01
Primary Place of Performance: University of Utah
72 South Central Campus Dr
Salt Lake City
UT  US  84112-9200
Primary Place of Performance
Congressional District:
01
Unique Entity Identifier (UEI): LL8GLEVH6MG3
Parent UEI:
NSF Program(s): OFFICE OF MULTIDISCIPLINARY AC,
DYNAMICAL SYSTEMS,
Software Institutes,
CDS&E-MSS
Primary Program Source: 01001213DB NSF RESEARCH & RELATED ACTIVIT
01001314DB NSF RESEARCH & RELATED ACTIVIT

01001415DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 1253, 7433, 7478, 8004, 8005, 9150, 9251
Program Element Code(s): 125300, 747800, 800400, 806900
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

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.

The intellectual merit of this effort is the development of efficient algorithmic strategies for mapping numerical methods for solving H-J equations on unstructured meshes to commodity streaming architectures. The proposed work will tackle several important technical challenges. One challenge is maintaining sufficient computational density on the parallel computational units (blocks), especially as we move to 3D unstructured meshes. A second technical challenge is the loss in efficiency that comes with communication between blocks. The solutions to these challenges will allow us to exploit currently available commodity streaming architectures that promising to provide teraflop performance on the desktop, which will be a boon for a variety of communities that rely on computationally expensive, 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.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

James King, Sergey Yakovlev, Zhisong Fu, Robert M. Kirby and Spencer J. Sherwin ""Exploiting Batch Processing on Streaming Architectures to Solve 2D Elliptic Finite Element Problems: A Hybridized Discontinuous Galerkin (HDG) Case Study"" Journal of Scientific Computing , 2014
James King, Thomas Gilray, Robert M. Kirby and Matthew Might "Dynamic Sparse-Matrix Allocation on the GPU" International Supercomputing Conference (ISC), Frankfurt, Germany, June 19-23, 2016. , 2016
J. King, S. Yakovlev, Z. Fu, R. M. Kirby and S.J. Sherwin "Exploiting Batch Processing on Streaming Architectures to Solve 2D Elliptic Finite Element Problems: A Hybridized Discontinuous Galerkin (HDG) Case Study" Journal of Scientific Computing , 2014
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 , 2011
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 , v.35 , 2014 , p.C473
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 , 2013
Zhisong Fu, Sergey Yakovlev, Robert M. Kirby and Ross T. Whitaker ""Fast Parallel Solver for Levelset Equations on Unstructured Meshes"" Concurrency and Computation: Practice and Experience , 2014
Zhisong 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 , v.257 , 2014 , p.195
Zhisong 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 , 2014

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

The goal of this work 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. This effort will allow for the scientific extension and software solidification of both our previous and current Hamilton-Jacobi GPU efforts into a publicly available tool suite.  

The major scientific outcomes of this project were peer-reviewed journal articles that documented new algorithmic advances.   Advances in the following areas were made:

-- 2d/3d unstructured Eikonal solvers

-- Finite Element Method (FEM) and Algebraic Multigrid (AMG) solvers on teh GPU

-- 2d/3d unstructured level-set methods on the GPU

-- dynamically allocated sparse-matrix allocation methods on the GPU

-- hierarchical random ball cover algorithms on the GPU

The major engineering outcomes of this project were the hardening of the aforemented algorithms into a publicly available code: GPUTUM.  Efforts were made to test the code, document the use cases, set up mailing and distribution lists, and in general to make this code accessible to the scientific community.

The major educational outcomes of this project were the students trained, both graduate students and REU undergraduates, and the material and software used in the classroom (the new software suite being accessible for students).


Last Modified: 08/04/2016
Modified by: Robert M Kirby

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page