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