Efficient Parallel Simulations of Asynchronous Cellular Arrays
Boris D. Lubachevsky
Bell Laboratories, Murray Hill, NJ 07974, USA
Abstract
A definition for a class of asynchronous cellular arrays is proposed. An example of such asynchrony would be independent Poisson arrivals of cell iterations. The Ising model in the continuous time formulation of Glauber falls into this class. Also proposed are efficient parallel algorithms for simulating these asynchronous cellular arrays. In the algorithms, one or several cells are assigned to a processing element (PE), local times for different PEs can be different. Although the standard serial algorithm by Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller can simulate such arrays, it is usually believed to be without an efficient parallel counterpart. However, the proposed parallel algorithms contradict this belief proving to be both efficient and able to perform the same tasks as the standard algorithm. The results of experiments with the new algorithms are encouraging: the speed-up is greater than 16 using 25 PEs on a shared memory MIMD but computer, and greater than 1900 using 
PEs on a SIMD computer. The algorithm by Bortz, Kalos, and Lebowitz can be incorporated in the proposed parallel algorithms, further contributing to speed-up.
