Keywords: partitioning, heterogeneous, distributed computing, diffusion method, Kernighan-Lin method, cable-membrane structures.

The availability of networks of workstations and personal computers will continue to increase. Although these networks are generally provided for other reasons engineers will increasingly seek to utilise this computing resource for distributed finite element analysis. The partitioning of finite element meshes for distributed analysis has to be able to account for the heterogeneous nature of these networks in which each processor may be of a different capability.

In this paper a method for the non-uniform partitioning of cable membrane structures for analysis on distributed computing systems is presented. The developed partitioning method is based on simple, well-understood algorithms and some engineering heuristics. The general layout of the algorithm of the static partitioning for heterogeneous systems is:

• Using a state-of-the-art graph partitioning algorithm to generate a partitioning where an equal number of elements is assigned to each subdomain as in a homogeneous computational system.

• With the knowledge of the relative computational power of the processors in the heterogeneous system calculate the "correct", target number of elements that should finally be allocated to each subdomain.

• Setup a subdomain graph and allocate the number of elements calculated in the previous step to each node of the subdomain graph. In this case a node represents a processor to which the subdomain will ultimately be allocated. At this time the subdomain graph will reflect an unbalanced state.

• Use the diffusion algorithm [1] on the subdomain graph to determine the number of elements that should be migrated to other subdomains to equalise the number of elements in the subdomain graph.

• The migration of elements between subdomains is ordered in such a way that at one step, for one particular subdomain the elements are only migrated away, for example subdomain b in Figure 138.1.

  Figure 138.1: Diffusion between subdomains

• Now consider the equalised subdomain graph again and the number of migrating elements calculated by the diffusion algorithm. In this step "virtual" elements are assigned to the subdomains. The total number of "virtual" elements assigned to a subdomain is equal to the total number of elements which should be migrated to the subdomain as calculated in the previous step. The reason for the introduction of "virtual" elements is that the migration is carried out with a modified Kernighan-Lin algorithm which operates on pairs of elements.

• Apply the modified Kernighan and Lin algorithm [2] to determine the actual elements that should be migrated.

The paper includes a number of examples to assess the quality of the partitions generated by the method.

1

G. Cybenko. "Dynamic load balancing for distributed memory multiprocessors". J. Parallel and Distributed Computing, 7:279-301, 1989. doi:10.1016/0743-7315(89)90021-X

2

B. W. Kernighan and S. Lin. "An efficient heuristic procedure for partitioning graphs". The Bell System Technical Journal, 29:291-307, February 1970.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £123 +P&P)