Reducing communication in sparse solvers

Bienz, Amanda

Permalink

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

Description

Title

Reducing communication in sparse solvers

Author(s)

Bienz, Amanda

Issue Date

2018-06-29

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

Olson, Luke N.

Doctoral Committee Chair(s)

Olson, Luke N.

Committee Member(s)

• Gropp, William D.
• Solomonik, Edgar
• Grigori, Laura

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)

• Sparse solvers
• Linear solvers
• Parallel programming
• Parallel communication
• Algebraic multigrid
• Performance modeling

Abstract

Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of algebraic multigrid. Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of algebraic multigrid as a result of reduced communication costs in sparse matrix operations. Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.

Graduation Semester

2018-08

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2018 Amanda Bienz

Owning Collections