The Metropolis algorithm [#!METROPOLIS!#] was invented by Metropolis et al in 1953 for sampling an arbitrary probability distribution. This algorithm has been very successful and influential in many areas of Monte Carlo method.

In the Metropolis algorithm, new states or configurations of the
system are found by systematically moving through all the lattice
sites and updating the spin variables.
A new configuration
is generated by updating a single variable in the old configuration
and calculating the change in energy

(6.9) |

The Metropolis algorithm for a spin model is well suited to parallelism, since it is regular--so one can use standard data decomposition of the lattice onto the processors to get good load balance, and local--the update of a site depends only on its nearest neighbors, so only local communication is required.

On SIMD computers, we cannot update a site and its neighbors at the same time, since they are dependent on each other, and we would violateOn MIMD computers, we do a checkerboard partitioning of the lattice to do the data communication as large blocks of spins rather than single spins, by passing all the edge data to neighboring processors after each red or black update. This checkerboard partitioning and blocked communication is illustrated in Figure 6.3. This blocked communication greatly reduces the latency time for communication, thereby improving efficiency. It is also possible to overlap communications with computation, by computing edge values first, and sending them while the interior points are being computed.