A Hybrid Solution to Parallel Calculation of Augmented Join Trees of Scalar Fields in Any Dimension

Abstract

Scalar fields are used to describe a variety of details from photographs, to laser scans, to x-ray, CT or MRI scans of machine parts and are invaluable for a variety of tasks, such as fatigue detection in parts. Analyzing scalar fields can be quite challenging due to their size, complexity, and the need to understand both local and global details in context. Join trees are a data structure used to capture the geometric properties of scalar fields, including local minima, local maxima, and saddle points. Unfortunately, computing these trees is expensive, and their incremental construction makes parallel computation nontrivial. We introduce an approach that combines three strategies, pruning, spatial-domain parallelization, and value-domain parallelization, to parallelize join tree construction using OpenCL. The resulting implementation show a significant speedup, making computation of trees on large data practical on even modest commodity hardware.

Downloads

Download the Paper Download the BiBTeX

Citation

Paul Rosen, Junyi Tu, and Les Piegl. A hybrid solution to parallel calculation of augmented join trees of scalar fields in any dimension. Computer-Aided Design and Applications, pages 1--8, 2018.

Bibtex


@article{Rosen.2018.CADA,
  title = {A Hybrid Solution to Parallel Calculation of Augmented Join Trees of Scalar Fields in Any Dimension},
  author = {Paul Rosen and Junyi Tu and Les Piegl},
  journal = {Computer-Aided Design and Applications},
  pages = {1--8},
  year = {2018},
  publisher = {Taylor \& Francis},
  abstract = {Scalar fields are used to describe a variety of details from photographs, to laser scans, 
   to x-ray, CT or MRI scans of machine parts and are invaluable for a variety of tasks, such as 
   fatigue detection in parts. Analyzing scalar fields can be quite challenging due to their size, 
   complexity, and the need to understand both local and global details in context. Join trees are a 
   data structure used to capture the geometric properties of scalar fields, including local minima, 
   local maxima, and saddle points. Unfortunately, computing these trees is expensive, and their 
   incremental construction makes parallel computation nontrivial. We introduce an approach that 
   combines three strategies, pruning, spatial-domain parallelization, and value-domain parallelization, 
   to parallelize join tree construction using OpenCL. The resulting implementation show a significant 
   speedup, making computation of trees on large data practical on even modest commodity hardware.}
}