Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling

Gahvari, Hormozd

Permalink

https://hdl.handle.net/2142/50516 Copy

Description

Title

Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling

Author(s)

Gahvari, Hormozd

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

Gropp, William D.

Doctoral Committee Chair(s)

Gropp, William D.

Committee Member(s)

• Heath, Michael T.
• Olson, Luke N.
• Vanka, Surya Pratap
• Yang, Ulrike M.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Algebraic Multigrid
• Performance Modeling
• Massively Parallel Architectures

Abstract

With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures. In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model. Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.

Graduation Semester

2014-08

Permalink

http://hdl.handle.net/2142/50516

Copyright and License Information

Copyright 2014 Hormozd Gahvari

Owning Collections