Title :
Synchronous relaxation for parallel Ising spin simulations
Author :
Lubachevsky, Boris ; Weiss, Alan
Author_Institution :
Lucent Technol. Bell Labs, Murray Hill, NJ, USA
Abstract :
A new parallel algorithm for simulating Ising spin systems is presented. The sequential prototype is the n-fold way algorithm, which is efficient but is hard to parallelize using conservative methods. Our parallel algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp, our algorithm is synchronous. It also belongs to the class of simulations known as “relaxation”; hence it is named “synchronous relaxation.” We derive performance guarantees for this algorithm. If N is the number of PEs, then under weak assumptions we show that the number of correct events processed per unit of time is, on average, at least of order N/logN. All communication delays, processing time, and busy waits are taken into account
Keywords :
Ising model; delays; parallel algorithms; performance evaluation; physics computing; busy waits; communication delays; n-fold way algorithm; parallel Ising spin simulations; parallel algorithm; performance guarantees; processing time; sequential prototype; synchronous relaxation; Computational modeling; Delay effects; Lattices; Magnetization; Materials science and technology; Nearest neighbor searches; Parallel algorithms; Physics computing; Prototypes; Temperature;
Conference_Titel :
Parallel and Distributed Simulation, 2001. Proceedings. 15th Workship on
Conference_Location :
Lake Arrowehead, CA
Print_ISBN :
0-7695-1104-X
DOI :
10.1109/PADS.2001.924635