Load balancing methods for message-passing multicomputers
Xu, Jian · University of Southern California Digital Library · 2017
With today's existing operating systems, it is difficult to achieve appreciable speedup in using a multicomputer to execute AI-oriented application programs which have irregular structures and unpredictable run-time behaviors. This thesis explores the role of load balancing for parallel execution of both numerical and AI programs on a message-passing multicomputer. A dual-level load balancing scheme will be presented, which includes both static program allocation and dynamic process migration. An optimization method is presented to solve the static mapping problems using simulated annealing. The minimization of a cost function reflects in a balanced load distribution. Theoretical proofs verify the near optimality of the proposed method. A new adaptive scheme is presented for dynamic load balancing, based on using easy to-implement heuristics and a variable threshold in migrating processes among the multicomputer nodes. We will explore parallelism of program execution at the process control level. Experiments performed on a 32-node iPSC/2 hypercube multicomputer include the development of a parallel discrete event-driven simulator and the prototype implementation of a distributed load balancer. Simulation and benchmark results will be shown to achieve higher performance at lower cost. The main contribution of this thesis lies in setting up a framework to achieve load balancing in multicomputers, which can be applied to both numerical and artificial intelligence applications. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)