Date of Award

2010

Thesis Type

PhD

Document Type

Thesis

Divisions

Faculty of Science

Department

Institute of Mathematical Sciences

Institution

Universiti Malaya

Abstract

In this thesis, a parallel implementation of explicit/implicit parallel algorithms such as the stationary iterative methods and the class of iterating alternating methods which includes: Alternating Direction Implicit (ADI), Iterative Alternating Direction Explicit (IADE), for D’Yakonov (IADE-DY), Double sweep Mitchell and Fairweather (MF-DS) and Alternating Group Explicit (AGE) method for solving 1-Dimensional (1-D), 2-Dimensional (2-D) Parabolic (special examples including 1-D, 2-D Bio-Heat Equation) and 1-D, 2-D and 3-D Telegraphic Equations on a distributed environment of Message Passing Interface (MPI) and Parallel Virtual Machine (PVM) platform is presented. To correlate the communication activity with computation, we counted events between significant MPI/PVM call sites. All the required input files are generated during the partitioning phase. We implemented the scheduling of n-tridiagonal system of equations with the above mentioned methods to show improvement on speedup and efficiency with parallel strategies on two platforms. These integrate memory and communication resources in an efficient manner. This platform was designed to solve a wide variety of time-dependent Partial Differential Equations (PDE) for various applications. The ADI, IADE-DY, MF-DS and other classes of AGE are developed by the splitting of the implicit equation using the finite-difference discretization. These schemes are found to be convergent and possess unconditional stability, high order accuracy and above all explicitly, which is highly favorable for numerical parallel processing. Sequential experiments on the dimensional model equations confirm the convergence and accuracies of the schemes. The comparison of sequential performance of the methods provides us the order of increased accuracy and rapid convergence in the IADE class of MF-DS and AGE. Between these classes, AGE has the edge over the rest in terms of speedup and efficiency, because of the ability to perform independently due to the presence of non-overlapping sub-domain and the nature of the implicit block, which can be easily converted to an explicit form. Here, the numerical solution of the Telegraph Equation in three space dimensions is obtained with 3-D ADI method. The method is shown to be computationally stable with linear runtime. The proposed algorithms in this thesis combine elements of numerical stability and parallel algorithm design that enhance overlap communication and computation to avoid unnecessary synchronization. Comparison of the parallel performance also indicates that the communication cost of class of AGE is minimum compared to the class of IADE and ADI. The parallelization of the program is implemented by a domain decomposition strategy. A Single Program Multiple Data (SPMD) model is employed for the implementation. The implementation is discussed in relation to means of parallel performance strategies and analysis. We present some analyses that are helpful for speedup and efficiency. Hence, the efficiency is strongly dependent on the grid size, block numbers and the number of processors for both MPI and PVM. Different strategies to improve the computational efficiency are proposed.

Initial

khm

Additional Information

Thesis (PhD) - Faculty of Science, Universiti Malaya, 2010.

Download

Share

COinS