Basic HTML version of Foils prepared October 22 1997

Foil 84 Parallel Cluster Algorithms

From GCF Talk U - Lewis/NASA 3/9/92 Mardi Gras Conference on Concurrent Computing in Physical Sciences -- February 18, 1993. by Geoffrey C. Fox
1 Parallel Component Labeling
  • Simple SIMD component labeling algorithms are very inefficient, taking order L iterations to label an L2 lattice
  • These algorithms can be used effectively on MIMD machines, however. Use fast sequential algorithms to label sub-lattices, and simple SIMD algorithm to match clusters across processors. Takes order square root of P iterations for an array of P processors. Good efficiencies if L>>P.
  • On SIMD machines (CM-2, Maspar) multi-grid algorithms using regular (hypercube) communication, and multi-scale algorithms using general non-local communication, do labeling in order log(L) iterations. Inefficient due to poor load balancing and irregular clusters.
2 Independent Parallelism
  • On coarse grain MIMD machines or workstation networks can parallelize over independent simulations with different random number streams. This is the only way to parallelize the Wolff algorithm efficiently.
  • On massively parallel machines, can use a combination of domain decomposition and independent parallelism for Swendsen-Wang algorithm, e.g. run 8 independent simulations of 64 nodes each on 512 node nCUBE.
in Table To:

© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Wed Oct 22 1997