Performance of a GPU-based Direct Summation Algorithm for Computation of Small Angle Scattering Profile

Konstantin Berlin, Nail A. Gumerov, Ramani Duraiswami, David FushmanarXiv 2013 · arXiv

Introduction

Small Angle Scattering (SAS) of X-rays or neutrons is an essential experimental technique for characterizing the structural properties of biological macromolecules in solution. Unlike high-resolution methods such as X-ray crystallography, SAS allows for the study of proteins and nucleic acids in their native liquid environments. However, the utility of SAS often depends on iterative structural refinement—a process that requires calculating theoretical scattering profiles for thousands of candidate models to find the best fit for experimental data.

The Computational Bottleneck: Debye Summation

The primary computational challenge in SAS modeling is the calculation of the theoretical scattering profile, typically performed using the Debye summation. This method calculates the interactions between every pair of atoms in a molecule, resulting in a quadratic complexity of $O(N^2)$. For a medium-sized protein complex containing 20,000 atoms, a single calculation can take several minutes on a standard CPU. When multiplied by the hundreds of thousands of iterations required for ab initio refinement, this calculation becomes a prohibitive bottleneck in structural biology workflows.

GPU-Accelerated Direct Summation

To address this, researchers at the University of Maryland developed a high-performance algorithm leveraging General-Purpose Graphics Processing Units (GPGPUs). By treating the Debye sum as an N-body problem, the algorithm parallelizes the interaction calculations across thousands of GPU threads.

The implementation utilizes the OpenCL standard, ensuring cross-platform compatibility across various hardware vendors, including NVIDIA and AMD. A critical component of the algorithm's efficiency is its optimization of the memory hierarchy.

OpenCL memory hierarchy utilized for optimizing data movement between compute units and memory types.

As shown in the diagram above, the algorithm minimizes reliance on slow "global memory" by loading blocks of atom coordinates into "local memory"—a fast, shared cache. This tiling approach allows multiple threads to reuse data simultaneously, significantly reducing latency and enabling the processing of large molecular structures that would otherwise exceed the GPU's immediate register capacity.

Performance and Scaling

The GPU-based direct summation was benchmarked against the standard Integrative Modeling Platform (IMP) C++ library and a parallelized CPU implementation. The results demonstrate a transformative increase in speed.

On consumer-grade hardware, such as a 2013-era laptop, the GPU implementation achieved a 47x speedup over the IMP library and a 22x speedup over the parallel CPU version. For a protein model with 40,000 atoms, the computation time was reduced from nearly 16 minutes (957 seconds) to just 20 seconds.

Discussion: Brute Force vs. Hierarchical Methods

A key insight of this research is the comparison between "brute force" $O(N^2)$ GPU summation and hierarchical $O(N \log N)$ algorithms like the Fast Multipole Method (FMM). While FMM is theoretically more efficient for extremely large systems, it carries significant overhead that scales with the cube of the molecule's diameter ($qD^3$).

As illustrated in the performance plot, the GPU-accelerated direct summation remains the fastest available method for molecules containing up to approximately 50,000 atoms. This range covers the vast majority of proteins and small-to-medium complexes studied in structural biology. Furthermore, the direct summation provides "machine-level" precision, avoiding the orientation-averaging errors common in approximation methods, which is particularly beneficial for elongated structures like DNA.

Conclusion

The development of this OpenCL-based GPU algorithm democratizes high-performance structural biology. By enabling complex refinements to be performed in seconds on standard laptops rather than hours on dedicated workstations, this approach facilitates real-time data analysis and broader access to advanced modeling techniques. Future work may involve integrating this accelerated core into larger modeling pipelines to enable real-time data fitting during experiments.

Summary updated

Abstract

Small Angle Scattering (SAS) of X-rays or neutrons is an experimental technique that provides valuable structural information for biological macromolecules under physiological conditions and with no limitation on the molecular size. In order to refine molecular structure against experimental SAS data, ab initio prediction of the scattering profile must be recomputed hundreds of thousands of times, which involves the computation of the sinc kernel over all pairs of atoms in a molecule. The quadratic computational complexity of predicting the SAS profile limits the size of the molecules and and has been a major impediment for integration of SAS data into structure refinement protocols. In order to significantly speed up prediction of the SAS profile we present a general purpose graphical processing unit (GPU) algorithm, written in OpenCL, for the summation of the sinc kernel (Debye summation) over all pairs of atoms. This program is an order of magnitude faster than a parallel CPU algorithm, and faster than an FMM-like approximation method for certain input domains. We show that our algorithm is currently the fastest method for performing SAS computation for small and medium size molecules (around 50000 atoms or less). This algorithm is critical for quick and accurate SAS profile computation of elongated structures, such as DNA, RNA, and sparsely spaced pseudo-atom molecules.
BibTeX
@misc{berlin2013performance,
  author = {Konstantin Berlin and Nail A. Gumerov and Ramani Duraiswami and David Fushman},
  title = {{Performance of a GPU-based Direct Summation Algorithm for Computation of Small Angle Scattering Profile}},
  year = {2013},
  eprint = {1306.2258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.2258},
}
Figure