Date of Award

Summer 1992

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

Committee Director

Mohammed Zubair

Committee Member

Chester E. Grosch

Committee Member

Kurt Maly

Committee Member

Thomas L. Jackson

Abstract

Numerical solutions of partial differential equations (pde's) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving pde's is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving pde's using the multigrid algorithm.

In this dissertation, we present three parallel multigrid algorithms which address the above mentioned problems and thus obtain a better performance on massively parallel machines than the standard multigrid algorithm. The first of these, the Overlap Parallel Multigrid (OPMG) algorithm, uses unutilized processors on the coarse grids of the multigrid hierarchy to do additional computation. The additional computation improves the convergence rate of the multigrid algorithm and thus reduces the total parallel execution time to solve a problem. The second algorithm, the Chopped Parallel Multigrid (CPMG) algorithm, reduces the computational work on the coarse grids of the multigrid hierarchy, while keeping the convergence rate per cycle almost the same. The reduction in the computational work reduces the average parallel execution time per cycle, which in turn results in a reduced total parallel execution time. A combination of the complementary approaches used by these two algorithms is the source for our third algorithm, the hybrid algorithm. The hybrid algorithm obtains a better performance than the standard multigrid algorithm by improving the convergence rate per cycle and also by reducing the average parallel execution time per cycle. Both these factors reduce the total parallel execution time for solving pde's using the multigrid algorithm.

We implemented the above three algorithms and also the standard multigrid algorithm on a massively parallel SIMD machine, the AMT-DAP/510, consisting of 1024 processors. The parallel implementation results show that our algorithms obtain a significant advantage over the standard multigrid algorithm. On the average, a speed-up of approximately 30%, 40% and 60% over the standard multigrid algorithm is obtained by the OPMG algorithm, the CPMG algorithm and the hybrid algorithm respectively.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

DOI

10.25777/pcgp-an74

Download

Share

COinS