The International Conference for High Performance Computing, Networking, Storage and Analysis
Reducing Network Contention Associated with Parallel Algebraic Multigrid.
Student: Amanda J. Bienz (University of Illinois at Urbana-Champaign)
Supervisor: Luke Olson (University of Illinois at Urbana-Champaign)
Abstract: Algebraic multigrid (AMG) is an iterative method often used to solve PDEs arising in various fields of science and engineering. The method is optimal, requiring only O(n) work to solve a system of n unknowns. Parallel implementations of AMG, however, lack scalability. As problem size increases, parallel AMG suffers from increasingly dense communication patterns, yielding network contention and reduced efficiency. The amount of communication can be reduced algorithmically with little change in convergence, through use of non-Galerkin coarse grids. The overall performance of parallel AMG can be further improved upon through the tradeoff of communication and convergence rates. Removing costly communication, such as that between two processors on opposite ends of the network, can improve the runtime of AMG if the cost saved from communication is greater than that added from decreasing convergence.