IEEE Transactions on Parallel and Distributed Systems · 1996 · 133 citations · 30 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismDistributed ComputingDistributed Memory ParallelismDistributed Memory SystemsParallel Computing SystemsParallel Performance AnalysisData Partitioning StrategiesDistributed MemoryDynamic PartitioningNon-uniform ComputationParallel Partitioning StrategiesPartitioningPartitioning StrategiesWorkload Partitioning
We discuss inverse spacefilling partitioning (ISP), a partitioning strategy for non-uniform scientific computations running on distributed memory MIMD parallel computers. We consider the case of a dynamic workload distributed on a uniform mesh, and compare ISP against orthogonal recursive bisection (ORE) and a median of medians variant of ORE, ORB-MM. We present two results. First, ISP and ORB-MM are superior to ORE in rendering balanced workloads-because they are more fine-grained-and incur communication overheads that are comparable to ORE. Second, ISP is more attractive than ORB-MM from a software engineering standpoint because it avoids elaborate bookkeeping. Whereas ISP partitionings can be described succinctly as logically contiguous segments of the line, ORB-MM's partitionings are inherently unstructured. We describe the general d-dimensional ISP algorithm and report empirical results with two- and three-dimensional, non-hierarchical particle methods.
30
Smoothed Particle Hydrodynamics
J. J. Monaghan · Annual Review of Astronomy and Astrophysics · 1992 · 4.9K citations
Computer Simulation Using Particles
R. W. Hockney, J.W. Eastwood · 1988 · 2.1K citations