Dynamic load distributions for adaptive computations on MIMD machines using hybrid genetic algorithms
Timothy H. Kaiser · 1997
With the advent of readily available Multiple-Instruction, Multiple-Data (MIMD) machines, calculations are being performed which, until recently, were impractical. Physical scientific calculations such as weather forecasting, shock propagation, fluid migration and aerodynamics calculations are being performed at higher fidelity and over larger problem spaces. These types of calculations are often performed by mapping physical space onto a two dimensional grid. When using a MIMD computer, each processor is responsible for performing calculations for a portion of the grid. To obtain optimal performance on a MIMD computer, the computational load for each processor must be nearly equal and the communication between processors must be minimized. Unfortunately, balancing load and simultaneously reducing communication is difficult. Many modern scientific grid calculations exacerbate the problem because grid points are dynamically created and deleted during the calculation. If a calculation is started with an optimal distribution of points, it will not remain optimal. This dissertation addresses the issue of providing automatic, dynamic load balancing and communication reduction to achieve near optimum performance for dynamic grid calculations. It has resulted in a new hybrid genetic algorithm, run in parallel with a dynamic grid calculation to achieve near optimum dynamic load balance and communication cost. The hybrid genetic algorithm was incorporated into a parallel adaptive grid program framework, developed for this effort. As a particular test, routines to solve Euler's equation of gas dynamics were incorporated into the framework. The resultant parallel adaptive grid application with dynamic rebalancing capabilities was used to solve these problems in two dimensions. The hybrid genetic algorithm was shown to dramatically improve the run time of the simulations as compared to static or random dynamic reallocation of cells to processors. The algorithm was shown to improve performance when compared to recursive bisection techniques and standard genetic algorithms on the example calculations. The hybrid genetic algorithm load balancing technique can be incorporated into a large class of grid calculations. The framework developed for this effort is robust, flexible and extensible, and can also be used to create a wide variety of grid simulations. An outline for future enhancements to the framework is provided.