A Fast 3 × N Matrix Multiply Routine for Calculation of Protein RMSD

Imran S. Haque, Kyle A. Beauchamp, Vijay S. PandebioRxiv 2014 · DOI

Abstract The bottleneck for the rapid calculation of the root-mean-square deviation in atomic coordinates (RMSD) between pairs of protein structures for large numbers of conformations is the evaluation of a 3 × N × N × 3 matrix product over conformation pairs. Here we describe two matrix multiply routines specialized for the 3 × N case that are able to significantly outperform (by up to 3X) off-the-shelf high-performance linear algebra libraries for this computation, reaching machine limits on performance. The routines are implemented in C and Python libraries, and are available at https://github.com/simtk/IRMSD.

Introduction

Calculating the similarity between protein structures via Root-Mean-Square Deviation (RMSD) is a fundamental but computationally expensive task in molecular biology. Molecular Dynamics (MD) simulations frequently generate millions of conformations, and clustering these snapshots requires billions of pairwise comparisons. While algorithms like the Theobald method have improved efficiency, the process remains dominated by the inner product of coordinate matrices.

Protein coordinate matrices are typically "skinny," with dimensions of $3 \times N$ (where $N$ is the number of atoms). General-purpose high-performance linear algebra libraries (e.g., BLAS) are optimized for large, square matrices. When applied to these skinny matrices, the overhead of these libraries leads to significant inefficiencies. This paper introduces specialized $3 \times N$ matrix multiplication routines that leverage hardware-level vectorization to achieve up to 3x speedups, approaching the theoretical limits of modern CPU architectures.

Methods and Implementation

The authors developed two specialized routines optimized for the x86_64 architecture using Streaming SIMD Extensions (SSE). The core strategy involves two primary techniques: vectorization and register blocking. Vectorization allows the CPU to process four floating-point numbers simultaneously, while register blocking ensures data remains in high-speed registers to minimize latency from main memory.

The efficiency of these routines depends heavily on the underlying data layout. The paper explores two formats:

  1. Axis-major: Coordinates are stored contiguously by axis (all X, then all Y, then all Z). This layout is the most efficient for vectorization but often requires reformatting existing data.
  2. Atom-major: Coordinates are stored as triplets $(x_i, y_i, z_i)$. This is the standard format in biological software but requires an "in-register transpose" to align data for SIMD operations.
Comparison of Axis-major and Atom-major data layouts for protein coordinate matrices.

For the atom-major format, the authors implemented a sophisticated shuffle sequence using SSE instructions like SHUFPS and PSHUFD. This allows the CPU to reorganize data into a vectorized format on the fly. Interestingly, because the routine is memory-bound, these extra logic operations are effectively "free," occurring while the CPU waits for data to arrive from RAM.

The sequence of SSE register shuffles used to implement the in-register transpose for atom-major data.

Performance Evaluation

The routines were tested using synthetic data (4 GB of random floats) to measure raw throughput and real protein structures from the Protein Data Bank (PDB), ranging from 176 to nearly 5,000 atoms. Additionally, 40,000 conformations generated via Gromacs were used to evaluate real-world clustering performance.

Key results include:

  • Throughput: The axis-major routine outperformed GotoBLAS by 2x for small structures and was 3x faster than the original Theobald implementation.
  • Hardware Saturation: On a 4-core Intel i7, the routines achieved ~30 GFLOP/s, saturating the machine's memory bandwidth.
  • Application Impact: Integration into the MSMBuilder clustering tool resulted in an overall application speedup of 2x to 3x.

Conclusion

By specializing for the $3 \times N$ case, these routines eliminate the branching and setup overhead of general-purpose libraries. While currently optimized for x86_64 SSE, the principles of streaming efficiency and in-register transposes are broadly applicable. Future work may involve porting these methods to wider instruction sets like AVX or ARM architectures to further push the boundaries of MD simulation analysis.

Summary updated

Abstract

Abstract The bottleneck for the rapid calculation of the root-mean-square deviation in atomic coordinates (RMSD) between pairs of protein structures for large numbers of conformations is the evaluation of a 3 × N × N × 3 matrix product over conformation pairs. Here we describe two matrix multiply routines specialized for the 3 × N case that are able to significantly outperform (by up to 3X) off-the-shelf high-performance linear algebra libraries for this computation, reaching machine limits on performance. The routines are implemented in C and Python libraries, and are available at https://github.com/simtk/IRMSD .
BibTeX
@misc{haque2014fast,
  author = {Imran S. Haque and Kyle A. Beauchamp and Vijay S. Pande},
  title = {{A Fast 3 × <i>N</i> Matrix Multiply Routine for Calculation of Protein RMSD}},
  year = {2014},
  doi = {10.1101/008631},
  howpublished = {bioRxiv},
}
Figure