Advanced Systems Lab - Spring 2021
Basic Information
- COVID-19 info: We will follow the general ETH regulations, which are permanently updated, and communicate if there are updates. There are no course-specific exceptions. Right now this means we start with zoom lectures, make recordings available (details by email), and hope for a regular, physical midterm.
- READ: Course description, prerequisites, goals, integrity
- Read the slides of the first lecture
- FAQs
- Course number: 263-0007, 8 credits
- Spring 2021, lectures: M 10:15-12:00, HG F3; Th 9:15-10:00 HG F3; occasional substitute lectures: W 14:15-16:00 ETF C1
- Instructor: Markus Püschel (CAB H69.3, pueschel at inf), Ce Zhang (ce.zhang at inf)
- Head TA:
- Joao Rivera (JR)
- TAs:
- Eliza Wszola (EW)
- Konstantin Taranov (KT)
- Theodoros Theodoridis (TT)
- 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 TA)
- Office Hours: (No office hours after April 23)
- Mon 12:30-14:00: Theodoros
- Tue 13:30-15:00: Eliza
- Wed 14:00-15:30: Konstantin
- Fri 12:30-14:00: Joao
Time Line
This list can be subject to minor changes, which would be announced in a timely manner.
| Fr 12.03. | Project team and project registered in the project system |
| Th 11.03. | HW1 due |
| Th 18.03. | HW2 due |
| Th 01.04 | HW3 due |
| Sa 17.04. | HW4 due |
| Wed 21.04. | Midterm |
| week of 03.05 | 1st one-on-one project meeting |
| week of 24.05. | 2nd one-on-one project meeting |
| week of 07.06. | Project presentations |
| Fr 25.06. | Project report due |
Grading
- 40% research project
- Topic: Very fast, ideally adaptive implementation and associated performance analysis for a numerical problem
- Team up in groups of four: register in the project system
- March 12th: find team, find a problem (tip: look at the prior courses linked above under Teaching 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). If you pick from this list, the decision is final and cannot be changed.
- Once project is fixed: add it in the project system to your team
- 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 algorithm 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 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: 25.06 (in your git repository)
- Name: (Team ID) + _report.pdf, e.g. 07_report.pdf
- Presentation
- Week of 07.06 (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: two in May, see above
| # | Predefined Topics | Supervisor/s |
|---|---|---|
| 1 | Arbitrary precision ball arithmetic | JR |
| 2 | Hierarchical density based clustering (hdbscan) | EW |
| 3 | Relational queries over bit-parallel database layout | CZ |
| 4 | Sphere tracing | TT |
| 5 | T-stochastic neighbour embedding (t-SNE) | KT |
| # | Proposed Topics | Supervisor/s |
|---|---|---|
| 6 | Optimizing the EPIC System in the SCION Infrastructure | KT |
| 7 | Gilbert–Johnson–Keerthi distance algorithm | JR |
| 8 | Polynomial multipoint evaluation | JR |
| 9 | Wave Function Collapse | EW |
| 10 | SPIHT Image Compression | EW |
| 11 | Fortune’s Algorithm | CZ |
| 12 | Flow algorithms with emphasis on Edmonds-Karp | EW |
| 13 | Optimization of a FLIP algorithm | EW |
| 14 | SURF: Speeded Up Robust Features | CZ |
| 15 | Censorship-avoiding high-speed EC (Elligator with Curve1174) | KT |
Midterm
21.04.
- all the material up to then is fair game but the overwhelming part will be what was covered in the homeworks
- you can study previous exams, all on the website
- no books, notes, calculators, laptops, cell phones, or other electronic devices are allowed
- once the exam has finished, you should leave the building
Previous exams:
- 2015: without solution, with solution
- 2016: without solution, with solution
- 2017: without solution, with solution
- 2019: without solution, with solution
- 2020: without solution, with solution
- 2021: without solution, with 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 20 minutes or 7 hours late costs one late day.
We will be using Moodle for the homeworks.
It may help to look at the homeworks of previous iterations of this course (above under the Teaching tab).
| Homework | Deadline | Solution |
|---|---|---|
| Homework 0 | as soon as possible | |
| Homework 1 | Th March 11th, 5pm | Homework 1 |
| Homework 2 | Th March 18th, 5pm | Homework 2 |
| Homework 3 | Th April 1st, 5pm | programming exercise auto-assessed |
| Homework 4 | Sa April 17th, 5pm | Homework 4 |
Lectures Plan
| Date | Content | Other Material |
|---|---|---|
| 22.02 | Course motivation, overview, organization | |
| 25.02 | Cost analysis and performance | |
| 01.03 | Intel Haswell architecture/microarchitecture, operational intensity | Intel optimization manual, Section 2.2 |
| 04.03 | Instruction level parallelism | |
| 08.03 | Compiler limitations, benchmarking | |
| 11.03 | SIMD vector instructions, AVX | Intel intrinsics guide, Agner Fog’s instruction tables, see also the recent uops |
| 15.03 | SIMD vector instructions, AVX | |
| 18.03 | Compiler vectorization | |
| 22.03 | Locality, caches | |
| 25.03 | Caches, blocking MMM | |
| 29.03 | Roofline model, Linear algebra libraries, BLAS, ATLAS | |
| 01.04 | Fast MMM | |
| 12.04 | Fast MMM continued, register renaming, virtual memory | |
| 15.04 | Sparse linear algebra, sparse MVM | |
| 19.04 | Discrete/fast Fourier transform | |
| 26.04 | Fast FFT, FFTW | |
| 10.05 | Spiral: DSL-based program generation for performance |