SC16 Salt Lake City, UT

78. A Task-Based Directed Acyclic Graph Implementation of Additive AMG

Authors: Amani Alonazi (King Abdullah University of Science and Technology)George Markomanolis (King Abdullah University of Science and Technology)David Keyes (King Abdullah University of Science and Technology)

Abstract: Algebraic multigrid is the solver of choice in many and growing applications in today’s petascale environments and scales well in a weak, distributed-memory sense. Exascale architectures exacerbate the challenges of increased strong SIMT concurrency, reduced memory capacity and bandwidth per core, and vulnerability to global synchronization. The recent Vassilevski-Yang (2014) “mult-additive" AMG nearly preserves the convergence rate of the multiplicative form of AMG, while reducing communication and synchronization frequency and controlling memory growth. However, it remains bulk-synchronous. We extend the algorithm further toward exascale environments with a task-based directed acyclic graph implementation. The algorithm can then be represented as a task-based DAG where vertices represent tasks, and edges are dependencies among them. We implement a tiling approach for decomposing the grid hierarchy into parallel units within task containers. The distribution of tiles is left to the compiler and OmpSs runtime system to expose task-level parallelism.

Poster: pdf
Two-page extended abstract: pdf

Poster Index