Mathematical Sciences Research Institute

Home » UCB Mathematics Department Colloquium: Communication Avoiding Algorithms


UCB Mathematics Department Colloquium: Communication Avoiding Algorithms October 01, 2015 (04:00 PM PDT - 05:00 PM PDT)
Parent Program: --
Location: 60 Evans Hall UCB
Speaker(s) James Demmel (University of California, Berkeley)
Description No Description
No Video Uploaded

Algorithms have two costs: arithmetic and communication, i.e. moving data between levels of a memory hierarchy or processors over a network. Communication costs (measured in time or energy per operation) already greatly exceed arithmetic costs, and the gap is growing over time following technological trends. Thus our goal is to design algorithms that minimize communication. We present algorithms that attain provable lower bounds on communication, and show large speedups compared to their conventional counterparts. These algorithms are for direct and iterative linear algebra, for dense and sparse matrices, as well as direct n-body simulations. Several of these algorithms exhibit perfect strong scaling, in both time and energy: run time (resp. energy) for a fixed problem size drops proportionally to the number of processors p (resp. is independent of p). Finally, building on recent work of Bennett, Carbery, Christ and Tao extending bounds of Hölder, Brascamp and Lieb, we describe extensions to very general algorithms involving arbitrary loop nests and array accesses, in a way that may be incorporated into compilers.

No Notes/Supplements Uploaded No Video Files Uploaded