Accelerating Optimization of a Probabilistic Graphical Model through Data-Parallel Primitives

Fig. 1: Our new DPP-based image segmentation method applied to image-based data stacks (top) and slices (bottom) offers the potential to vastly accelerate data pipelines from DOE experimental facilities.

Scientific Achievement

An order-of-magnitude performance increase on CPU and GPU platforms for a challenging graph optimization problem results from algorithmic reformulatiion using data-parallel primitives [1].

Significance and Impact

Approaches such as this are a promising path forward for both portability and performance on rapidly evolving computer architectures, into the exascale regime and beyond into Post-Moore’s Law. This method has widespread science and security applications, from computational chemistry and bioinformatics, to cybersecurity.

Research Results

  • Challenging reformulation of a graph optimization problem: from traditional Von Neumann style coding to one based on data-parallel primitives (scan, sort, map, reduce, etc.)
  • Platform-portable, shared-memory parallel implementation: runs on CPUs and GPUs
  • Performance comparison with state-of-the-art implementations shows significant performance advantages
  • This algorithm is being used as part of a state-of-the-art image segmentation method, which is targeting analysis of image-based data from beamline science



  1. B. Lessley, T. Perciano, C. Heinemann, D. Camp, and Hank Childs, and E. W. Bethel, “DPP-PMRF: Rethinking Optimization for a Probabilistic Graphical Model Using Data-Parallel Primitives,” in 8th IEEE Symposium on Large Data Analysis and Visualization (LDAV), Berlin, Germany, Oct. 2018.