Parallel dynamic load-balancing for adaptive distributive memory PDE solvers

This thesis is concerned with the issue of dynamic load-balancing in connection with the parallel adaptive solution of partial differential equations (PDEs). We are interested in parallel solutions based upon either finite element or finite volume schemes on unstructured grids and we assume that geometric parallelism is used, whereby the finite element or finite volume grids are partitioned across the available parallel processors. For parallel efficiency it is necessary to maintain a well balanced partition and to attempt to keep communication overheads as low as possible . When adaptively occurs however a given partition may deteriorate in quality and so it must be modified dynamically. This is the problem that we consider in the is work.

Chapters one and two outline the problem is more detail and review existing work in this field. In Chapter one a brief history of parallel computers is presented and different kinds of parallel machines are mentioned. The finite element method is also introduced and its parallel implementation is discussed in some detail: leading to the derivation of a static load-balancing problem. A number of important static load balancing algorithms are then discussed. Chapter two commences with a brief description of some error indicators and common techniques for mesh adaptively. It is shown how this adaptively may lead to a load imbalance among the available processors of parallel machine. We then discuss some ways in which the static load-balancing algorithms of Chapter one can be modified and used in the context of dynamic load-balancing. The pros and cons of these strategies are discussed and then finally some specific dynamic load-balancing algorithms are introduced and discussed.

In Chapter three a new dynamic load-balancing algorithm is proposed based upon a number of generalisations of existing algorithms. The details of the new algorithm are outlined and a number of preliminary numerical experiments are undertaken. In this preliminary (sequential) version the dual graphed an existing partitioned computational mesh is repartitioned among the same number of processors so that after the repartitioning step each processor has an approximate equal load and the number of edges of this dual graph which cross from one processor to another are relatively small.

The remainder of the thesis is concerned with the practical parallel implementation of this new algorithm and making comparison with existing techniques. In Chapter four the algorithm is implemented for a 2-d adaptive finite element solver for steady-state problems, and in Chapter five the generality of the implementation is enhanced and the algorithm is applied in conjunction with a 3-d adaptive finite volume solver for unsteady problems. In this situation frequent repartitioning of the mesh is required. In this Chapter performance comparisons are made for that logarithm detailed here against new software that was developed simultaneously with the work of this thesis. These comparisons are very favourable for certain problems which involve very non-uniform refinement.

All software implementations described in this thesis have been coded in ANSI C using MPI version 1.1 (where applicable). The portability of the load-balancing code had been tested by making use of a variety of platforms, including a Cray T3D, an SGI PowerChallenge, different workstation networks (SGI Indys and SGI 02s), and an SGI Origin 2000. For the purposes of numerical comparisons all timings quoted in this thesis are for the SGI Origin 2000 unless otherwise stated.