U.C. Berkeley CS294 / Math270, Spring 2016
Communication-Avoiding Algorithms
| Syllabus | Schedule of Lectures | Class projects | Recommended reading |
Syllabus, Mondays 1:30PM - 3PM
Instructors: J. Demmel and L. Grigori
Academic units: 2
Location: 405 Soda (except for the first three meetings on Jan 25, Feb 1, and Feb 8, which will be in 380 Soda)
Office Hours: M 9-10, T 9-10 and F 1:30-2:30, in 564 Soda Hall
Poster session: Wednesday May 4th, 10AM - 12PM, 5th floor Soda hallway
The traditional metric for the cost of an algorithm is the number of
arithmetic or logical operations it performs. But the most expensive
operation an algorithm performs, measured in time or energy, is not
arithmetic or logic, but communication, i.e. moving data between
levels of a memory hierarchy or between processors over a network.
The difference in costs can be orders of magnitude, and is growing
over time due to technological trends like Moore's Law. So our goal
is to design new algorithms that communicate much less than
conventional algorithms, attaining lower bounds when possible.
This course will present an overview of novel "communication-avoiding" (CA)
algorithms that attain these goals, including communication lower bounds,
and practical implementations showing large speedups. Problem domains
considered include dense and sparse linear algebra, graph theory,
N-body algorithms, and more generally many algorithms that can be
expressed as nested loops accessing arrays. Many open problems will be
presented, which may also be undertaken as class projects.
> Top of the page
Schedule of lectures
> Top of the page
Class projects
The class projects will include prove new lower bounds, design new algorithms, implement algorithms and compare performance, read and present a paper.
> Top of the page
Recommended reading (evolving)
Many of the papers described in the lectures can be found on BeBOP webpage.
Overlapping categories:
Lower bounds on communication and overview papers
Communication avoiding algorithms for dense linear algebra
Communication avoiding algorithms for iterative methods and preconditioners
Communication avoiding for sparse matrices and graphs
Communication avoiding for N-body problems
Hardware aware algorithms
Randomized numerical linear algebra: overview, elementary proofs, low rank approximation algorithms, sketching algorithms
> Top of the page
|
