Automatic Generation & Analysis of Algorithms - 2014
- Summer semester 2014.
- CAMPUS #: 14ss-38045
- Lectures begin: Thursday, April 10th, 5.15pm.
Lectures & Exercises:
Rogowski 115 - AICES seminar room (Schinkelstrasse 2)
Office hours: Tuesdays, 11am-1pm please email me
AICES R432 (Rogowski Building - Schinkelstrasse 2)
- 10.04.2014 - Thursday -> Introduction
- 15.04.2014 - Tuesday -> Triple loop vs. DGEMM. [gemm.c] [BLAS guide]
- 15.04.2014 - Thursday -> Storage. Memory hierarchy. [tests.c]
22.04.2014 - Tuesday -> Auto vectorization, part 1.
Assignment #1 (deadline: May 6th, 5pm) [HW1]
- 24.04.2014 - Thursday -> Vectorization, part 2. [Files]
- 29.04.2014 - Tuesday -> Partitionings, operators and properties.
06.05.2014 - Tuesday -> Partitioned Matrix Expression
5pm: Deadline assignment #1
- 08.05.2014 - Thursday -> From PME to loop invariants to algorithms [Paper]
13.05.2014 - Tuesday -> HW1 review, more on PME.
Assignment #1: |A|_F, A^t, |A|_inf, Ax, x^t A -> improve and re-submit
deadline: May 20th, 5pm
Assignment #2 (deadline: June 3th, 5pm) [HW2]
- 15.05.2014 - Thursday -> Implementations.
20.05.2014 - Tuesday -> Algorithm generation.
5pm: Deadline HW1 resubmission
- 22.05.2014 - Thursday -> CLAK [Paper]
- 27.05.2014 - Tuesday -> CLAK [Paper]
03.06.2014 - Tuesday -> RWTH's Sports day
5pm: Deadline assignment #2
05.06.2014 - Thursday -> Cilk, pragmas
Assignment #3 (deadline: June 24th, 5pm) [HW3]
- 24.06.2014 - (Tuesday) 5pm: Deadline assignment #3
- 26.06.2014 - Thursday -> Autotuning [Slides]
01.07.2014 - Tuesday -> Final assignment.
Assignment #4 (deadline: exam) [HW4]
PrerequisitesBasic knowledge of Numerical Linear Algebra: matrix product, linear systems, factorizations
Knowledge of programming: iteration, recursion, function definitions and calls
Familiarity with at least one of the following languages: Mathematica, Maple, Matlab, C
OverviewThis course is research-oriented; it covers novel techniques in computer automation. In this course, "automation" means that a computer makes decisions and performs operations much like a human would. The objective is a software system that creates algorithms without human intervention.
Starting from a problem expressed in symbolic (algebraic) form (example: Lx = b), it is possible to automatically generate algorithms and code to solve the problem with only minimal human intevention. Not only are the algorithms generated automatically, but they are provably correct!
We introduce the concepts of automation, autotuning and formal correctness of programs.
We first review a variety of methodologies to automatically generate algorithms in different fields. Then we restrict ourselves to linear algebra and introduce two different approaches towards automation. The first approach, based on program correctness and pattern matching, relies on Partitioned Matrix Expressions and Loop Invariants. The second approach, also based on pattern matching, originates a linear algebra compiler. Such techniques generate algorithms as well as cost and error analyses.
The course is research oriented, participation is crucial.
Tentative syllabusThe focus of this semester is the automatic vectorization of code. (SSE, AVX, compilers, ...)
July: 8, 10, 15, 17
Send me an email to schedule an appointment -> first come, first served.