Connected component labeling [19] has important applications in image processing and computer vision. [20] It is also the main computational requirement in Monte Carlo simulations of spin models of magnetism using cluster algorithms, in which clusters of spins are updated at once. [21] These non-local algorithms are much more effective than standard Monte Carlo methods such as the Metropolis algorithm. [22]
The Metropolis algorithm is regular and local and can therefore be easily and efficiently parallelized using standard domain decomposition. This is easy to express in HPF and should be handled efficiently by an HPF compiler for any architecture.
The clusters in spin models are highly irregular in both shape and size, and also highly non-local (there is usually one very large cluster). The cluster algorithms are therefore very difficult to parallelize, especially on a SIMD machine. However parallel algorithms exist which can be expressed in data parallel Fortran. [24] These algorithms use general irregular communication routines, and may also benefit from intrinsic functions such as the scan routine on the Connection Machine, which scans data along a row or column of an array (like a parallel prefix operation in HPF). Much more efficient algorithms are available on MIMD machines using message passing, [23] but it is difficult to see how these could be expressed in HPF.