Automatic Generation and Analysis of Algorithms --- 2009
Prerequisites:
Basic knowledge of numerical linear algebra.
Principles of algorithms and programming.
Familiarity with at least one of the following languages: Mathematica,
Maple, Matlab, C.
Overview:
This course is research-oriented; it covers novel techniques on
automation.
In this course "automation" means that a computer makes decisions and
performs operations much like a human would do. This is in constrast
to the scenario in which automation means that a computer is used to
test a very large number of cases.
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 will study the generation methodology and we will explore the
following topics: generation of parallel algorithms for multi-core
processors, cost analysis, error analysis.
-
Summer semester 2009.
-
CAMPUS #: 09ss-24886
-
First meeting: Thursday, April 16th - 17.15 in Wullnerstrasse.
Lectures begin: Thursday, April 23rd - 10.30am.
-
Lectures:
Thursdays, 10.00-11.30, 2356|5055 (Ahornstrasse 55)
Thursdays, 17.15-18.45, 1810|013 (Wullnerstrasse 5 u.7)
-
Office hours:
Tuesdays, 11am-1pm, AICES R432 (Rogowski Building - Schinkelstrasse 2)
-
Lectures:
-
Preliminaries: Lectures 1 & 2.
-
Lectures 3 & 4: Matrix partitionings; intro to Mathematica pt.1.
Presentations:
Code generation, ATLAS.
-
Lectures 5 & 6: Semantics of Expressions and Commands.
-
Lectures 7 & 8: Fundamental Theorem of Invariance.
Presentations:
Theorem provers, ACL2.
-
Lectures 9 & 10: Partitioned Matrix Expression.
-
Lectures 12 & 13: Algorithm Generation.
-
Lectures 14 & 15: From PMEs to high-performance.
Presentation: Overview of Spiral.
-
Lectures 16 & 17: Floating point arithmetic and error analysis.
Presentation:
Spiral: parallelization and vectorization.
-
Lectures 18 & 19: Modular and systematic error analysis.
Presentation:
Overview of FFTW.
-
Lectures 20 & 21: Stability analisys: TRSV, TRSM, LU, Blocked LU.
Presentation:
Performance of FFTW.
-
Lecture 22: Cost analysis: projects.
Lecture 23: How to give a presentation.