A multiple-heaps algorithm for parallel simulation of collision systems

doi:10.1006/jcph.2002.7073

Return

A multiple-heaps algorithm for parallel simulation of collision systems

2002-07-01

PRE

Mu, M *

DOI：10.1006/jcph.2002.7073

Original

Original request for help

Save

Abstract

En 中文

We consider the parallel simulation of collision systems. It has wide application, such as in hard-sphere molecular dynamics simulation for gas dynamics and crystals, as well as in studying molecular collision dynamics of chemical reactions. With detailed analysis, proper data structures are designed so that the central computational task is formulated as a consecutive search for the minimum in the collision time space of O(N-2) entries, with Multiple updates on O(N) entries in the same space per collision step. The abstraction and formulation enable us to incorporate efficient techniques in computer science into this application, which leads to a heap-based sequential algorithm of 0 (N log N) time in one typical collision step, where N is the number of particles of the simulated collision system. A parallel algorithm of multiple heaps with a diagonal-oriented mapping is then proposed. We show that the parallel algorithm is load balanced and the parallel time per collision step is O((N/P) log (N-2/P) + log P), where P is the number of processors. The parallel algorithm uses two levels of partitioning independently, one in the particle-based physical space and the other in the collision time space. An exchange-shift communication algorithm is presented to bridge the two different partitioning schemes. Besides collision system simulation, the parallel multiple heaps algorithm may find applications in many other computing areas where a heap-based priority queue needs to be maintained, such as in fast level-set methods. (C) 2002 Elsevier Science (USA).

Keywords:

parallel computing

collision system

hard-sphere molecular dynamics simulations

heap

parallelism

load balance