Advanced Systems Lab - Spring 2020
Basic Information
- READ: Course description, goals, integrity, knowledge base
- Course number: 263-0007, 8 credits
- Spring 2020, lectures: M 10:15-12:00, HG F3; Th 9:15-10:00 HG F3; occasional substitute lectures: W 13:15-15:00 HG D3.2
- Instructor: Markus Püschel (CAB H69.3, pueschel at inf)
- Head TAs:
- Joao Rivera (JR)
- Bojan Karlas (BK)
- TAs:
- Gagandeep Singh (GS)
- Konstantin Taranov (KT)
- Theodoros Theodoridis (TT)
- Eliza Wszola (EW)
- Eric Stavarache (ES)
- Konstantinos Triantafyllou (KTr)
- Jakob Beckmann (JB)
- Hleb Makarchuk (HM)
- 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 Head TAs)
- Office Hours: (No office hours after April 9).
- Mon 12:30-14:00: Eliza
- Tue 13:30-15:00: Theodoros
- Wed 14:00-15:30: Konstantin
- Fri 12:30-14:00: Joao
Grading
- 40% research project
- Topic: Very fast, ideally adaptive implementation and performance analysis of a numerical problem
- Team up in groups of four: register in the project system
- March 6: find team, find a problem (tip: look at the prior courses linked above for examples)
- Finding a problem: either pick from the below list (6 teams max per topic) or suggest a project to MP for approval (email MP with paper containing algorithm)
- Baum-Welch algorithm: wiki page, building intuition, math details, scaling trick for numeric stability
- Fractal image compression
- Social force model (by Helbing and Molnar)
- Approximate Cholesky for Symmetric Diagonally Dominant Matrices (New Algorithm): info1, info2, explanation elimination procedure
- Number-theoretic transform
- Elliptic curve cryptography
- Once project is fixed: add it in the project system
- Complete “milestones” during the semester and enter them in the project system
- Later in semester: One or two 1 hour one-on-one meetings with a project supervisor
- Write 8 page standard conference paper (template is provided below)
- Give short presentation end of semester
- 30% midterm
- 30% homework
- Exercises on 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 (read integrity rules)
- There is no final exam
Research Project
- All projects have to be registered in our project system. This site contains a rough structure for your project and 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 (tested) 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 use (exclusively) a repository that we provide to you
- You analyze and try to reason about the performance behavior
- You write a paper about your work and give a presentation
- Paper:
- Maximal 8 pages (hard limit) without references, conference style, template and instructions below
- Everybody reads this: report.pdf
- Latex source: report.zip
- Due date: Friday, June 12 (in your git repository)
- Name: (Team ID) + _report.pdf, e.g. 07_report.pdf
- Presentation
- Last week of classes (information)
- Template (the use is totally optional) and some guidelines: presentation-template.pptx, presentation-template.pdf
- Rough timeline
- Start project work: any time, the earlier the better
- Assignment project advisor: around mid April
- One-on-one project meetings: End of April and early May
| # | Predefined Topics | Supervisor/s | |
|---|---|---|---|
| 1 | Baum-Welch algorithm | ES, HM | |
| 2 | Fractal image compression | EW | |
| 3 | Social force model (by Helbing and Molnar) | KTr, JB | |
| 4 | Approximate Cholesky for Symmetric Diagonally Dominant Matrices | TT | |
| 5 | Number-theoretic transform | JR | |
| 6 | Elliptic curve cryptography | KT |
| ID | Proposed Topics | Supervisor/s |
|---|---|---|
| 5 | HDR image construction from multi-exposed stereo LDR images | GS |
| 6 | Algorithms for Arbitrary Precision | JR |
| 7 | A SIFT Descriptor for Feature Matching | KT |
| 14 | Volume Estimation of High-Dimensional Convex Bodies | GS |
| 18 | Spectral Clustering | GS |
| 25 | local outlier factor | TT |
| 28 | Arbitrary precision floating point | JR |
| 30 | Improved SPH method | TT |
| 34 | Efros and Freeman Image Quilting Algorithm for Texture Synthesis | GS |
| 39 | XGBoost | TT |
| 40 | FastSLAM | GS |
| 41 | NSGA-II | TT |
| 42 | SURF: Speeded Up Robust Features | KT |
| 43 | tSNE vs accelerated tSNE with dual trees | TT |
| 45 | ADTBoost | TT |
| 46 | Seam Carving for Content-Aware Image Resizing | GS |
| 49 | Ray Marching | TT |
| 51 | Solving Linear Programs in the Current Matrix Multiplication Time | GS |
| 52 | NNDescent | GS |
| 53 | Robust Denoising using Feature and Color Information | KT |
| 55 | Subgraph Isomorphism | GS |
| 56 | DBScan and Dboost | GS |
| 59 | A Fast Implementation of Ed25519 ECDSA Scheme | KT |
Midterm
New date: July 8. Time: 10-12 (full 2 hours). Arrive: 9:45. Place: several rooms because of distancing that will be communicated in time. The exam will cover the entire lecture material except the part on transforms (which started April 6).
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 5th, 5pm | Homework 1 |
| Homework 2 | Th March 12th, 5pm | Homework 2 |
| Homework 3 | Th March 26th, 5pm | programming exercise auto-assessed |
| Homework 4 | Th April 9th, 5pm | Homework 4 |
Lectures Plan (subject to change)
Starting 9.3., lectures were recorded.
| Date | Content | Other Material |
|---|---|---|
| 17.02 | Course motivation, overview, organization | |
| 20.02 | Cost analysis and performance | |
| 24.02 | Intel Haswell architecture/microarchitecture, operational intensity | Intel Haswell, Intel Optimization Manual, Agner Fog’s instruction tables, see also the recent uops |
| 27.02. | Instruction level parallelism | |
| 02.03. | Compiler limitation, Benchmarking | |
| 05.03. | SIMD vector instructions | Intel Intrinsics Guide |
| 09.03. | SIMD vector instructions | |
| 12.03. | Compiler vectorization | |
| 16.03. | Locality, caches | |
| 19.03. | Caches, blocking MMM | |
| 23.03. | Roofline model, Linear algebra libraries, BLAS, ATLAS | |
| 26.03. | Model-based ATLAS | |
| 30.03. | Virtual memory optimizations for MMM | |
| 02.04. | Sparse linear algebra, sparse MVM | |
| 06.04. | Discrete/fast Fourier transform | |
| 20.04. | Fast FFT, FFTW library | |
| 27.04. | Spiral: DSL-based program generation for performance | This was the last lecture. All time for the project now! |
| 25.05. | Project presentations (information) | |
| 27.05. | Project presentations |