High-Performance Matrix Computations --- 2016

When: Summer semester 2016

CAMPUS #: 16ss-24886

Contact: Prof. Paolo Bientinesi



Prerequisites

Basic knowledge of numerical linear algebra.
Principles of algorithms and programming.
Familiarity with Matlab and C.


Overview

The course centers around the idea of developing efficient numerical algorithms through a synergy between mathematics and architectures.


Tentative syllabus

  • processor architecture (cpu, memory system, interconnect)
  • floating point operations
  • roofline model
  • vectorization
  • matrix-matrix product, BLAS
  • factorizations
  • method of relatively robust representations (MR3)
  • blocked algorithms
  • algorithms by block
  • dynamic scheduling
  • data parallelism
  • shared memory vs. distributed memory paradigm
  • synchronization vs. communication

Lectures & Exercises

  • Tuesdays, 4.15-5.45pm (lecture)
  • Thursdays, 4.15-5.45pm (lecture + exercise)

Where: 1090|334 (klPhys), Rogowski Building, Schinkelstrasse 2

Start: Tuesday, April 19, 4.15pm


Office hours

  • Tuesdays, 11am-1pm, by appointment.
    AICES R432 (Rogowski Building - Schinkelstrasse 2)

Schedule

  • Tuesday, 19.04 Introduction [script]
  • Thursday, 21.04 Performance [GER] [slides] [script]
  • Tuesday, 26.04 Locality [A+B] [op] [script]
  • Thursday, 28.04 Defs, coding [slides] [GER] [GEMM] [script]
  • Tuesday, 03.05 ELAPS [GitHub]
  • Tuesday, 10.05 BLAS [slides] [reference]. Roofline Model [Paper] [script]
  • Thursday, 12.05 Blocked vs. unblocked algorithms: Cholesky factorization.
    HW #1 [PDF] Deadline: Friday, May 20th, midnight
  • Tuesday, 24.05 Partitioned Matrix Expression, variants [slides] [Cluster].
  • Tuesday, 31.05 High performance matrix matrix product [PPX] [references]
  • Thursday, 02.06 Strassen [PPX]
  • Tuesday, 07.06 Multithreading, dependencies [elaps experiments] [script]
  • Thursday, 09.06 Algorithms by blocks - pt.1 [Paper] [slides] [script]
  • Tuesday, 14.06 Algorithms by blocks - pt.2 [slides] [script]
  • Thursday, 16.06 Sequence of least squares problems [Paper] [script]
  • Tuesday, 21.06 Out-of-core algorithms. Double buffering [Paper]
  • Thursday, 23.06 Eigenproblems, preliminaries, accuracy, reductions. [script]
  • Tuesday, 28.06 Reduction to tridiagonal form [script] [notes]
  • Thursday, 30.06 Householder vs. SBR
    [Final projects] (Org mode, it's just a text file)
  • Tuesday, 05.07 Final projects. Bisection.
  • Thursday, 07.07
  • Tuesday, 12.07 Computation of eigenvalues; basics, power method
  • Thursday, 14.07 Computation of eigenvectors; inverse iterations, MR3 [Paper] [Slides]
  • Tuesday, 19.07 MR3, MR3-SMP, PMRRR [Paper] [Slides]
  • Thursday, 21.07 Matrix distributions [Slides, pp.19-28]

Exams

  • [Final projects] updated (Sept 9th)

  • July 26
  • July 28
  • August 2
  • September 27
  • September 29