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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Gahvari, Hormozd

Contributors dc:contributor

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

• Algebraic Multigrid
• Performance Modeling
• Massively Parallel Architectures

Statement dc:rights

• Copyright 2014 Hormozd Gahvari

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/50516