Basic Information

  • Course description, goals, integrity, knowledge base
  • Course number: 263-2300, 6 credits
  • Spring 2016, lectures: M 10:15-12:00, HG D3.2; Th 9:15-10:00 CAB G51; occasional substitute lectures: W 13:15-15:00 HG D3.2
  • Instructor: Markus Püschel (CAB H69.3, pueschel at inf, 2-7303)
  • TAs and their office hours:
    • Tyler Smith
    • Alen Stojanov
    • Gagandeep Singh
  • Mailing lists:
    • For technical questions: fastcode@lists.inf.ethz.ch (emails to this address go to the lecturer and all TAs)
    • Forum to find project partner: fastcode-forum@lists.inf.ethz.ch (emails go to all students who have no partner yet and to Alen & Tyler)

Grading

  • 40% research project
    • Topic: Very fast, ideally adaptive implementation of a numerical problem
    • Team up in groups of four
    • March 4: find team, find a problem (tip: look at the prior courses linked above for examples)
    • Complete “milestones” during semester and enter them into the online check list
    • Write 6 page standard conference paper (template will be provided)
    • Give short presentation end of semester
  • 25% midterm
  • 35% homework
    • Exercises on algorithm or code analysis
    • Implementation exercises
      • study the effect of program optimizations, compilers, special instructions, etc.
      • write and submit C code & create runtime/performance plots
    • Some templates will be provided
    • All homeworks are single-student homeworks
  • There is no final Exam

Research Project

  • All projects have to be registered in our project system. This site is also used later for updates.
  • How it works:
    • Weeks without homeworks should be used to work on the project
    • You select a numerical problem and create a correct (verified) implementation in C
    • You determine the arithmetic cost, measure the runtime and performance
    • You profile the implementation to find the parts in which most the runtime spent
    • Focusing on these you apply various optimization techniques from this class
    • You repeat the previous steps to create various versions with (hopefully) continuously better runtime
    • You write a paper about your work and give a presentation
  • Paper:
    • Maximal 6 pages (hard limit), conference style, template and instructions below
    • Everybody reads this: report.pdf
    • Latex source: report.zip (start with reading the README file)
    • Due date: Friday, June 14 (as final-report.pdf in your svn)
  • Presentation
    • Last week of classes
    • Template (the use is totally optional) and some guidelines (ppt is 2007 and later): presentation-template.pptx, presentation-template.pdf
    • The order will be determined randomly right before class # * Who talks will be determined randomly right before class
# Title Members Supervisor/s
1 Hierarchical Density-Based Spatial Clustering Clemens, Max, Leonoardo AS
2 Belief Propagation for Early Vision Ronan, Philip, Yannick, Michal AS
3 Metaheuristic Algorithms for Optimization Problems Abhimanyu, Matthäus, Jakob AS
4 SVD and Symmetric EVD Using Jacobi Rotations Martin, Rajasimha, Esref, Konstantinos TS
5 Baum-Welch Algorithm for Hidden Markov Models Eric, Gleb, Momchil MP
6 Stereo Matching with PatchMatch Niklaus, Jordan, Thomas GS
7 Forward and Backward Reaching Inverse Kinematics Felix, Tierry, Cédric, Benjamin GS
8 Gradient Boosting Decision Tree for Learning to Rank Zhifei, Meng-Yuan, Amaris, Meet TS
9 Hamilton Segmenter for R peak detection in ECG signals Xiaying, Hanjing, Tom, Robin MP
10 Bone Anisotropy Mapping Rajan, Ryan, João, Jarunan TS
11 Baum-Welch Algorithm Lilian, Elias, Georg, Hannes MP
12 Density Estimation with Distribution Element Trees Francesco, Stefano, Giovanni, Yi MP
13 Grid-based Fluid Simulation Karlis, Cedric GS

Midterm

April 15th, room HG E7 (solution, without solution).

Homework

Late policy: No deadline extensions, but you have 3 late days. You can use at most 2 on one homework. For example, submitting 7 hours late costs one late day.

We will be using Moodle for the homeworks.

Homework Deadline Solution
Homework 0 as soon as possible  
Homework 1 Th March 7th, 5pm Homework 1
Homework 2 Th March 14th, 5pm Homework 2
Homework 3 Th March 28th, 5pm Homework 3
Homework 4 Th April 11th, 5pm Homework 4

Lectures (including pdfs)

Date Content Other Material
18.02 Course motivation, overview, organization  
21.02 Cost analysis and performance  
25.02. Intel Haswell architecture/microarchitecture, operational intensity Intel Haswell, Intel Optimization Manual, Agner Fog’s instruction tables, see also the recent uops
28.02. Instruction level parallelism  
04.03. Compiler limitation, Benchmarking  
07.03. SIMD vector instructions Intel Intrinsics Guide
11.03. SIMD vector instructions  
14.03. Locality, caches  
18.03. Caches, analysis blocked MMM  
21.03. Roofline model, roofline plot  
25.03. Dense linear algebra libraries, model-based ATLAS  
28.03. Model-based ATLAS  
01.04. Virtual memory system  
04.04. Memory-bound computation, sparse linear algebra  
08.04. Sparse MVM, linear transforms  
11.04. Discrete/fast Fourier transform: overview  
15.04. Midterm  
29.04. FFTW, notes FFTW website
06.05. Computer generation of fast code (Spiral) Spiral website
27.05. Project presentations  
29.05. Project presentations