| 1 |
Metropolis Algorithm
-
Regular, local algorithm
-
Local communication, perfect load balance using standard domain decomposition
-
Efficiently parallelizable on SIMD and MIMD machines
|
| 2 |
Swendsen-Wang Algorithm
-
Irregular, non-local, multiple cluster algorithm
-
Main computational task is to identify clusters - connected component labeling, also used in image processing
-
Clusters are highly irregular (fractal) in shape, and of all sizes (usually including one large cluster covering much of the lattice)
-
Efficient parallel component labeling is a very difficult problem - poor load balancing, lots of non-local communication
|
| 3 |
Wolff Algorithm
-
Irregular, non-local, single cluster algorithm
-
Standard domain decomposition gives very poor load balance and very limited parallelism
-
Traditional simple, regular, local algorithms parallelize efficiently
-
Newer irregular, adaptive, non-local algorithms are better sequentially but often more difficult to parallelize
|
