An Efficient Priority Queue for Large FPGA-Based Discrete Event Simulations of Molecular Dynamics

Abstract: Molecular dynamics simulation based on discrete event simulation (DMD) is emerging as an alternative to time-step driven molecular dynamics (MD). Although DMD improves performance by sev-eral orders of magnitude, it is still compute bound. In previous work, we found that FPGAs are extremely well suited to accelerating DMD, with speed-ups of to being achieved. Large models, how-ever, are problematic because they require that most predicted events be stored in off-chip memory, rather than on the FPGA. Here we present a solution that allows the priority queue to be extended seamlessly into off-chip memory, resulting in a throughput equal to the hardware-only priority queue, or about faster than the best software-only algorithm. The solution is based on the observation that—when an event is predicted to occur far in the future—not only can its processing be imprecise, but the time when the processing itself occurs can also be substantially delayed. This allows numerous optimizations and re-structurings. We demonstrate the resulting design on standard hardware and present the experimental re-sults used to tune the data structures.