DAG-Guided Parallel Asynchronous Variational Integrators with Super-Elements
Jen-Chih Huang, Xiangmin Jiao, Richard Richard M. Fujimoto and Hongyuan Zha
Summer Computer Simulation Conference 2007 (SCSC 2007)
San Diego, California (USA), July 15-18, 2007
Abstract
Physical systems often involve a wide spectrum of time scales, making traditional synchronous time integrators too slow even on the world's fastest supercomputers. Asynchronous variational integrators (AVIs) have recently been introduced to address this challenge for a class of nonlinear elastodynamic problems. In this paper, we introduce a new and efficient parallel algorithm for the AVIs. We propose a new local-minima interpretation of the dependencies in the AVIs. Based on this interpretation, we show that the expected amount of parallelism in the AVIs is proportional to the number of elements of a mesh assuming a uniform distribution of the dependencies. Second, we introduce a parallel algorithm for the AVIs guided by the dependency graph of the computation that avoids using priority queues, thereby improving scalability. Third, we present an efficient multi-threaded implementation of the AVIs and introduce performance-optimization techniques using super-elements. Preliminary experimental results are presented to verify our theoretical analysis and demonstrate the effectiveness of the proposed algorithms.