Concurrency Practice and Experience · 1990 · 208 citations · 13 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsParallel AlgorithmsParallel ComputingDistributed AlgorithmsDistributed ComputingLoad BalancingParallel ArchitecturesParallel Computer ArchitectureParallel Computing SystemsLoad Balancing AlgorithmsMimd ArchitecturesParallel Computing ArchitecturesParallel Processing ArchitecturesPoisson EquationPoisson Equation ModelsPoisson's EquationPolynomial-time Algorithms
Abstract We present a fully distributed dynamic load balancing algorithm for parallel MIMD architectures. The algorithm can be described as a system of identical parallel processes, each running on a processor of an arbitrary interconnected network of processors. We show that the algorithm can be interpreted as a Poisson (heath) equation in a graph. This equation is analysed using Markov chain techniques and is proved to converge in polynomial time resulting in a global load balance. We also discuss some important parallel architectures and interconnection schemes such as linear processor arrays, tori, hypercubes, etc. Finally we present two applications where the algorithm has been successfully embedded (process mapping and molecular dynamic simulation).
13
Statistical mechanics of cellular automata
Stephen Wolfram · Reviews of Modern Physics · 1983 · 3.1K citations
Very high-speed computing systems
Michael Flynn · Proceedings of the IEEE · 1966 · 951 citations