IEEE Transactions on Parallel and Distributed Systems · 2007 · 41 citations · 25 references
ComputingComputer EngineeringComputer ScienceComputer NetworksDistributed SystemsHeterogeneous ComputingDistributed AlgorithmsDistributed ComputingDistributed SchedulingNetwork Flow AlgorithmsResource SchedulingTask SchedulingAdaptive AllocationAdaptive Resource AllocationAdaptive Task AllocationBandwidthDecentralized Task AllocationDistributed Resource AllocationHeterogeneous Computing SystemsThroughput
In this paper, we consider the task allocation problem for computing a large set of equal-sized independent tasks on a heterogeneous computing system where the tasks initially reside on a single computer (the root) in the system. This problem represents the computation paradigm for a wide range of applications such as SETI@home and Monte Carlo simulations. We consider the scenario where the systems have a general graph-structured topology and the computers are capable of concurrent communications and overlapping communications with computation. We show that the maximization of system throughput reduces to a standard network flow problem. We then develop a decentralized adaptive algorithm that solves a relaxed form of the standard network flow problem and maximizes the system throughput. This algorithm is then approximated by a simple decentralized protocol to coordinate the resources adaptively. Simulations are conducted to verify the effectiveness of the proposed approach. For both uniformly distributed and power law distributed systems, a close-to-optimal throughput is achieved, and improved performance over a bandwidth-centric heuristic is observed. The adaptivity of the proposed approach is also verified through simulations.
25
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Tracy D. Braun, Howard Jay Siegel, Noah Beck et al. · Journal of Parallel and Distributed Computing · 2001 · 1.7K citations