Multigrid Algorithms for Massively Parallel Machines

<p>Numerical solutions of partial differential equations (<em>pde's</em>) 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 <em>pde's</em> 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 <em>pde's</em> using the multigrid algorithm.</p> <p>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 <em>Overlap Parallel Multigrid</em> (<em>OPMG</em>) 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 <em>Chopped Parallel Multigrid</em> (<em>CPMG</em>) 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 <em>pde's</em> using the multigrid algorithm.</p> <p>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 <em>OPMG</em> algorithm, the <em>CPMG</em> algorithm and the hybrid algorithm respectively.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

1992

Author dc:creator

• Gupta, Satyanarayan

Contributors dc:contributor

• Mohammed Zubair
• Chester E. Grosch
• Kurt Maly
• Thomas L. Jackson

• Execution time
• Parallel machines
• Multigrid algorithms
• Computer Sciences

Statement dc:rights

• <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> 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).</p>

Repository record dc:identifier

https://digitalcommons.odu.edu/computerscience_etds/101

OAI identifier oai:identifier

oai:digitalcommons.odu.edu:computerscience_etds-1103