| Improvements in computer technology over the past several decades have led to great interest in utilizing distributed multicomputer systems to solve complex problems that would be otherwise impractical or inefficient using a single processor. To achieve optimized multicomputer performance, however, it is essential to evenly distribute the workload among the available processors. For applications such as dynamic mesh adaptation of unstructured grids, achieving a balanced load is difficult because of the rapidly changing nature of the grid.; In this dissertation, the load balancing problem is addressed in several ways. First, three topology independent dynamic load balancing schemes are proposed that are directly implementable on a variety of multicomputer architectures including the hyper-cube. Experiments using synthetically generated loads compare these algorithms to other popular load balancers and demonstrate that the proposed algorithms compare favorably. Next, the approach is modified to provide a global view of system load so that the dynamic schemes can also be applied to unstructured mesh applications where dynamic load balancers are not often used. Simulation experiments using workload data obtained from actual solvers demonstrate that the proposed algorithms are an effective alternative.; Finally, a novel partitioner, called MinEX, is presented that is specifically designed to execute in a distributed computing environment. Unlike dynamic load balancers, this approach partitions processor workloads prior to execution. As the load balance shifts, application processing is temporarily suspended and repartitioning takes place. The MinEX partitioner has the novel objective to minimize runtime rather than to achieve an equal workload on each processor. This new approach takes into account the cost of inter-processor communication, as well as the cost of moving data sets between processors, and accounts for latency tolerance. MinEX is evaluated by comparing its performance in two ways. First results are obtained using data produced by unstructured mesh solvers. Next, a solver for the classic N-body application is developed so that direct comparisons between MinEX and MeTiS (a state-of-the-art partitioner) can be made. Results conclude that MinEX achieves superior performance in a truly distributed computing environment with lower bandwidths and slower interconnects. |
