Next: Diffusion algorithm Up: Dynamic Load Balancing Algorithms Previous: Dynamic Load Balancing Through

Flow Calculation

The problem can be formally stated as follows:

Definition     Given a graph , let each vertex have a load associated with it. The flow calculation problem is to find the amount of migrating load along each edge , such that after the migration, the load on each vertex is the same. That is

 (9)

Here is the average load over all vertices, defined as , and is the amount of load to be migrated from node to node .

The graph here is the so called processor graph of the partitioning. Each vertex of the processor graph corresponds to a subdomain (or a processor) and two vertices are linked by an edge if the two subdomains share a boundary. Figure 14 shows the processor graph corresponding to the partitioning in Figure 13 (b). The load can simply be taken as the number of nodes in the subdomain . Figure 14 shows that subdomain 1 has a load of 25 nodes, whilst others have 15 nodes each. In the following the terms vertex and processor are used interchangeably.

It is noted that the flow calculation problem does not have a unique answer. This is because the solutions are given by a linear system (9), with as the unknown. There are equations (out of these, are independent), and unknowns. As there are usually more edges than vertices in a graph (that is, ), there are usually more unknowns than equations and so the answer to the problem is not unique.

This flow calculation problem has been studied by many authors [4,6,14,28,43,44,41,78,88,89]. Apart from parallel unstructured mesh based applications, it has appeared in areas such as parallel molecular dynamic simulation [7,55]. Some of the algorithms are discussed in the following.

Subsections

Next: Diffusion algorithm Up: Dynamic Load Balancing Algorithms Previous: Dynamic Load Balancing Through

2000-03-21