Dynamic Load Balancing Through Node Migration

The strategy of migrating boundary nodes to achieve load balancing is more complicated and is therefore discussed in detail in the following.

The process of migrating loads between processors to achieve load balance can be broken down into two distinctive steps [81,82,83]:

• Flow calculation:     Each processor works out a schedule for the amount of load that should be sent to (or received from) its neighboring processors. This is referred to as a flow calculation in [83].
• Node selection:    Once the flow is worked out, each processor decides which mesh nodes should be sent or received, to satisfy the flow as well as to minimize the edge-cut.

For real applications, there is also the third step to carry out the actual migration of the meshes and fields. This step is very complex and the exact details depend on the applications and the data structures used. In many adaptive computations, the amount of data associated with each mesh node may be quite large. The time for the migration of the data, and subsequent book-keeping cost of updating the data structures, can dominate overall run time, specially if there is a need to re-balance the load frequently. So far there exist few large scale applications that have a full dynamic load balancing capability (but see, e.g., [26]). We shall therefore concentrate on each of these first two steps, which are less application dependent.