Abstract Monte Carlo cluster update algorithms are extremely efficient for simulating spin models near their phase transitions, where local update algorithms suffer severe critical slowing down. Unfortunately, as the cluster algorithms are highly irregular as well as nonlocal, they are much more difficult to parallelize efficiently. The main difficulty lies in identifying which spins belong to which cluster. In this paper we investigate a number of cluster identification algorithms, both sequential and parallel, which we have implemented on serial, SIMD and MIMD computers.

Abstract Recently, a number of advanced architecture machines have become commercially available. These new machines promise better cost performance than traditional computers, and some of them have the potential of competing with current supercomputers, such as the CRAY X‐MP, in terms of maximum performance. This paper describes the methodology and results of a pilot study of the performance of a broad range of advanced architecture computers using a number of complete scientific application programs. The computers evaluated include: shared‐memory bus architecture machines such as the Alliant FX/8, the Encore Multimax, and the Sequent Balance and Symmetry shared‐memory network‐connected machines such as the Butterfly distributed‐memory machines such as the NCUBE, Intel and Jet Propulsion Laboratory (JPL)/Caltech hypercubes very long instruction word machines such as the Cydrome Cydra‐5 SIMD machines such as the Connection Machine ‘traditional’ supercomputers such as the CRAY X‐MP, CRAY‐2 and SCS‐40. Seven application codes from a number of scientific disciplines have been used in the study, although not all the codes were run on every machine. The methodology and guidelines for establishing a standard set of benchmark programs for advanced architecture computers are discussed. The CRAYs offer the best performance on the benchmark suite; the shared memory multiprocessor machines generally permitted some parallelism, and when coupled with substantial floating point capabilities (as in the Alliant FX/8 and Sequent Symmetry), provided an order of magnitude less speed than the CRAYs. Likewise, the early generation hypercubes studied here generally ran slower than the CRAYs, but permitted substantial parallelism from each of the application codes.

We have implemented Quantum Chromo-Dynamics (QCD) on the massively parallel Connection Machine in *Lisp. The code uses dynamical Wilson fermions and the Hybrid Monte Carlo Algorithm (HMCA) to update the lattice. We describe our program and give performance measurements for it. With no tuning or optimization, the code runs at approximately 500 to 1000 MFLOPS on a 64-K Connection Machine, model CM-2, depending on the VP ratio.