Touheed, Nasir (1998) Parallel dynamic loadbalancing for adaptive distributive memory PDE solvers. PhD thesis, University of Leeds.

Text
touheed.pdf Download (979Kb) 
Abstract
This thesis is concerned with the issue of dynamic loadbalancing 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 loadbalancing 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 loadbalancing algorithms of Chapter one can be modified and used in the context of dynamic loadbalancing. The pros and cons of these strategies are discussed and then finally some specific dynamic loadbalancing algorithms are introduced and discussed. In Chapter three a new dynamic loadbalancing 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 2d adaptive finite element solver for steadystate problems, and in Chapter five the generality of the implementation is enhanced and the algorithm is applied in conjunction with a 3d 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 nonuniform 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 loadbalancing 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.
Item Type:  Thesis (PhD) 

Additional Information:  Supplied directly by the School of Computing, University of Leeds. 
Academic Units:  The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds) 
Depositing User:  Dr L G Proll 
Date Deposited:  01 Mar 2011 15:20 
Last Modified:  07 Mar 2014 11:23 
URI:  http://etheses.whiterose.ac.uk/id/eprint/1286 