Optimizing the Performance of A Neighbor List Creation Algorithm For Molecular Dynamics Simulations on Graphics Processing Units

Abstract

In this thesis, I analyze and optimize the neighbor list algorithm for molecular dynamics simulations on graphics processing units (GPUs) based on linear bounding volume hierarchies (trees). Two methods were considered for building the trees based on how the particles are grouped together to make leafs. These are (1) merging together groups of four particles into one leaf in an approach I called merge-nearest-4, and (2) merging together groups of two to four particles based on how far they are relative to each other in an approach I called merge-grandchildren. It was found that the merge-grandchildren approach had slower tree construction speed but faster tree traversal speed compared to the merge-nearest-4 approach. Using the merge-grandchildren approach improved the algorithm performance by 12%. Tree traversal is shown to be the major remaining performance bottleneck that must be improved in future. These findings and improvements can be used to enhance the performance of tree-based molecular dynamics algorithms, and thereby improving the tools that are available for researchers who use molecular dynamics simulations as a research methodology; for instance, molecular dynamics simulations-based research on protein folding, designing new materials, etc.