Automatic Generation & Analysis of Algorithms - 2014

Prerequisites

Basic 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



Overview

This 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 syllabus

The focus of this semester is the automatic vectorization of code. (SSE, AVX, compilers, ...)



• Summer semester 2014.


• CAMPUS #: 14ss-38045


• Lectures begin: Thursday, April 10th, 5.15pm.


• Lectures & Exercises:
  Tuesdays, 5.15-6.45pm
  Thursdays, 5.15-6.45pm
  Rogowski 115 - AICES seminar room (Schinkelstrasse 2)


• Office hours: Tuesdays, 11am-1pm please email me
  AICES R432 (Rogowski Building - Schinkelstrasse 2)



Schedule

• 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. [Files]
  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 [Paper]
  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 [Files]
  
  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]





Exam dates


July: 8, 10, 15, 17
August: ??
September: ??

Send me an email to schedule an appointment -> first come, first served.