Next: Parallel Metropolis Algorithms
Up: Other Monte Carlo
Previous: Connected Component Labeling
Metropolis algorithm for spin models is easy to parallelize efficiently,
since it is regular and local.
-
Regular data structures
simple domain decomposition
-
Regular algorithm
lots of parallelism and perfect load balance
-
Local interactions
local communications
Swendsen-Wang algorithm is difficult to parallelize efficiently,
since it is irregular and non-local.
-
Clusters are irregular (fractal!) in size and shape
hard to load balance, lots of non-local communication
Wolff algorithm is almost impossible to parallelize efficiently.
-
Grow a single, irregular cluster starting at a random lattice site
little parallelism, very hard to load balance
Paul Coddington, Northeast Parallel Architectures Center at Syracuse University, paulc@npac.syr.edu