Dynamic Load Balancing at Runtime

The goal for load balancing in the Dome environment is to have parts of objects migrate among a set of heterogeneous machines connected by heterogeneous networks. As machine loads and network latencies change, portions of objects will be redistributed around the network to provide the best overall execution time of all the cooperating processes.

Load balancing dVectors

One of the first data structures to be load balanced is the dVector. This is a class defining a one-dimensional array of any type. On instantiation, a dVector is distributed evenly across all processors. As computations are performed, total times per process are computed. Elements in the dVector are moved to maintain the best total time.

The following figure shows the allocation of pieces of a dVector during runtime over 4 machines.

The allocations are due to the differences in total time between processors shown in the following figure:

As other classes of objects are added to Dome, each will have a load balancing method that will implement the class specific methodology for distributing the work.