| 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. |
