A hybrid solution to calculating augmented join trees of 2d scalar fields in parallel

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 the 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.

Paul Rosen, Junyi Tu, and Les Piegl. A hybrid solution to calculating augmented join trees of 2d scalar fields in parallel. In CAD Conference and Exhibition, 2017.

@inproceedings{Rosen.2017.CAD,
  title = {A hybrid solution to calculating augmented join trees of 2d scalar fields in parallel},
  author = {Paul Rosen and Junyi Tu and Les Piegl},
  booktitle = {CAD Conference and Exhibition},
  year = {2017},
  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 the
   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.}
}