# 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 |