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

  • Jan 25 - J. Demmel,
    Introduction: Why communication avoiding, slides pdf and ppt
    Presentation of potential class projects
  • Feb 1 - L. Grigori,
    Communication avoiding LU and QR factorizations, slides
  • Feb 8 - J. Demmel,
    Theoretical lower bounds on communication for nested loops with application to linear algebra, slides
  • Feb 15 - Holiday / no lecture
  • Feb 22 - L. Grigori,
    Computing low rank approximations of dense and sparse matrices, slides
  • Feb 29 - L. Grigori,
    Communication avoiding in iterative methods and preconditioners, slides
  • Mar 7 - J. Demmel,
    Part 1: Communication avoiding Strassen algorithms slides
    Part 2: Hardware aware communication avoiding algorithms: heterogeneity, network contention, non-volatile memories slides
  • Mar 14 - L. Grigori,
    Communication avoiding for sparse matrices and graphs, slides
  • Mar 21 - Spring recess / no lecture
  • Mar 28 - G. Ballard,
    Part 1: Avoiding Communication in Eigenvalue and Singular Value Decompositions, slides
    Part 2: Communication Costs of Tensor Decompositions, slides
  • Apr 4 - M. Gu,
    Spectrum-revealing matrix factorizations: Theory and Algorithms, slides
  • Apr 11
    Penporn Koanantakool, Communication-Avoiding Direct N-Body Algorithms, slides
    Francois Belletti, Scalable Linear Model Inference for Irregularly Sampled Time Series with Long Range Dependencies, slides
  • Apr 18
    Aditya Devarakonda, Communication-Avoiding Coordinate Descent Methods for Linear Systems, slides
    Yang You, CA-SVM: Communication-Avoiding Support Vector Machines on Distributed Systems, slides
  • Apr 25
    David Dinh, Complexity-theoretic Implications of Communication Bounds,
    final discussions.
  • > 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
  • Grey Ballard, Erin Carson, James Demmel, Mark Hoemmen, Nick Knight, and Oded Schwartz,
    Communication lower bounds and optimal algorithms for numerical linear algebra , Acta Numerica. Cambridge University Press, 23, 1-155, 2014.
  • Michael Christ, James Demmel, Nicholas Knight, Thomas Scanlon, and Katherine Yelick
    Communication Lower Bounds and Optimal Algorithms for Programs That Reference Arrays — Part 1
    EECS Technical Report No. UCB/EECS-2013-61, May 14, 2013.
  • Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz,
    Minimizing Communication in Numerical Linear Algebra,
    SIAM Journal on Matrix Analysis and Applications, SIAM, Volume 32, Number 3, pp. 866-901, 2011, pdf .
  • Communication avoiding algorithms for dense linear algebra
  • J. Demmel, L. Grigori, M. F. Hoemmen, and J. Langou,
    Communication-optimal parallel and sequential QR and LU factorizations,
    SIAM Journal on Scientific Computing, Vol. 34, No 1, 2012, pdf (also available on arXiv:0808.2664v1), short version of UCB-EECS-2008-89 and LAWN 204, available since 2008.
  • L. Grigori, J. Demmel, and H. Xiang,
    CALU: a communication optimal LU factorization algorithm,
    SIAM J. Matrix Anal. & Appl., 32, pp. 1317-1350, 2011, pdf preliminary version published as LAWN 226
  • G. Ballard, J. Demmel and I. Dumitriu,
    Communication-optimal parallel and sequential eigenvalue and singular value algorithms,
    UC Berkeley, Number EECS-2011-14, February 2011, pdf .
  • A. Khabou, J. Demmel, L. Grigori, and M. Gu
    LU factorization with panel rank revealing pivoting and its communication avoiding version, SIAM J. Matrix Anal. & Appl., Vol. 34, No. 3, pages 1401-1429, 2013, preliminary version published as LAWN 263, pdf.
  • J. Demmel, L. Grigori, M. Gu, and H. Xiang
    Communication avoiding rank revealing QR factorization with column pivoting, pdf,
    SIAM J. Matrix Anal. & Appl, Vol. 36, No. 1, pp. 55-89, 2015.
  • G. Ballard, J. Demmel, L. Grigori, M. Jacquelin, N. Knight, D. Nguyen
    Reconstructing Householder vectors for QR factorization ,
    Journal of Parallel and Distributed Computing, Aug 2015, pdf.
  • Communication avoiding algorithms for iterative methods and preconditioners
  • Marghoob Mohiyuddin, Mark Hoemmen, James Demmel, and Kathy Yelick,
    Minimizing Communication in Sparse Matrix Solvers
    In Proc. of SC09, November, 2009.
  • Erin Carson, Nicholas Knight, and James Demmel,
    Avoiding Communication in Nonsymmetric Lanczos-Based Krylov Subspace Methods
    SIAM J. Sci. Comput., 35(5), pp. S42-S61.
  • L. Grigori, S. Moufawad, F. Nataf
    Enlarged Krylov Subspace Conjugate Gradient Methods for Reducing Communication , INRIA TR 8597 ,
    to appear in SIAM J. Matrix Anal. & Appl, 2016.
  • L. Grigori, S. Moufawad,
    Communication avoiding ILU0 preconditioner , pdf
    preliminary version published as INRIA TR 8266 .
    SIAM Journal on Scientific Computing, 2015, Vol. 37, Issue 2.
  • Communication avoiding for sparse matrices and graphs
  • TBA
  • Communication avoiding for N-body problems
  • TBA
  • Hardware aware algorithms
  • Andrew Gearhart,
    PhD thesis: Bounds on the Energy Consumption of Computational Kernels
    Computer Science Division, U.C. Berkeley, October 2014
  • E. Carson, J. Demmel, L. Grigori, N. Knight, P. Koanantakool, O. Schwartz and H. V. Simhadri,
    Write-Avoiding Algorithms,
    Proceedings of IEEE International Parallel & Distributed Processing Symposium, IPDPS 2016, shorter version of Technical Report UCB/EECS-2015-163 .
  • Randomized numerical linear algebra: overview, elementary proofs, low rank approximation algorithms, sketching algorithms
  • for a list of suggested reading, please check the Reading group on randomized linear algebra, Spring 2015

  • > Top of the page  
    INRIA Paris
    Laboratoire J. L. Lions
    Universite Pierre et Marie Curie
    Contact: Laura Grigori (Laura(dot)Grigori(at)inria(dot)fr)

    © 2007 rs