How To Clock Your Computer
Advanced Course, 4
Online. Zoom Link: https://cs-uni-saarland-de.zoom.us/j/95062856565 For password: check the mailing list
|Organisers:||Christoph Lenzen and Shreyas Srinivas|
|Lecturers||Christoph Lenzen, Moti Medina, Andreas Steininger, Danny Dolev, Ian Jones, Will Rosenbaum, Matthias Fuegger, Milos Krstic|
|Assistant Lecturers:||Johannes Bund, Ben Wiederhake, Felipe Kuentzer, Shreyas Srinivas|
|First lecture:||Nov 2|
|Tutorials:||There will be no tutorials for this course|
Monday 10:00 - 12:00,
A written submission
|Prerequisites:||No prerequisites beyond basic familiarity with mathematical reasoning are required; prior knowledge on asymptotic notation and (occasionally) standard probabilistic notions can be useful, but is not essential for following the course. It is helpful but not essential to understand basic elements of digital circuits|
- Please check out the instructions for assignments file in the Materials section.
- Please note that the deadline for HISPOS registration for SIC students is 28 Jan 2021
- Having considered multiple options, we have chosen to use Zoom as the platform for this course. Please read the notes about zoom and data privacy at the bottom of this page.
- Register for the course via the mailing list : https://lists.mpi-inf.mpg.de/listinfo/how_to_clock_your_computer. Registration to the mailing list helps us know who is taking the course, communicate important announcements, discuss the course contents, etc. It does not automatically imply registration for the exams and grades. For this, please check the registration requirements of your respective programmes.
What this course is not about:
We will not teach you how to measure the actual running time of programs. This course does not cover topics like code instrumentation and benchmarking. We are teaching you how to clock the circuits that run your computer, not the code that runs on them.
What this course is about:
Computers chips are devices that are required to implement the abstraction of boolean logic. Ideally, this abstraction is maintained when the outputs of the circuits on a chip instantaneously and reliably reflect the input signals, and all parts of the chip are perfectly synchronised by a clock signal to maintain temporal sanity. In modern chips however, this is an increasingly difficult abstraction to maintain. A lot goes on under the hood, in a chip, to keep up the essential illusion of Boolean logic. A chip designer needs to confront the reality of continuously varying physical signals and their limited propagation speed, and build chips that can contain the resulting chaos to keep up the illusion. For years the brunt of this hidden labour has been borne by Electrical Engineers, so that Computer Scientists can safely build their grand theories of computation where everything works perfectly. As a token of gratitude, a motley bunch of CS theorists have been working over the last few years, to illuminate this dark and often ignored underbelly of computing (at least by Computer Scientists). They have been able to apply insights gained from decades of theorising to offer improved and distributed solutions to these problems. In this course, we will recount a part of the tale of this years long effort.
The goal of this course is to introduce the problem of clocking circuits from a theoretical perspective. We start out with the building blocks of digital logic and provide realistic models for their behavior. We explain the need for synchronised clock signals, present the existing solutions, and motivate the need for solutions which treat a chip as a distributed system of clock domains. We then proceed to discuss, in mathematical terms, the problems that circuits throw up when implementing these solutions. We discuss techniques to solve these issues. Finally we discuss the distributed solution, the gradient synchronisation algorithm, and show how these techniques enable us to adapt it to digital circuit design.
In this course, we do not deal with issues related to fault tolerance, i.e. when one or more clock domains behave in bizarre or even malicious ways. That scenario will be discussed in future courses which are built up on the foundations that this course establishes.
Although knowing digital logic can provide a teeny-tiny advantage, no prerequisites beyond basic familiarity with mathematical reasoning are assumed or required for this course. This course is a good starting point for getting involved with the current research topics of the group.
This course follows a flipped classroom model. This means the lecturers act as facilitators who will help you, through a short introductory lecture, and a guided group discussion, towards framing good questions and finding answers to them. Hence there will be two "discussion sessions" every week. Anywhere between one and three sessions will be devoted to a topic, according to the schedule.
Your goal throughout this course, is to prepare for these discussions. To do this, you must read the recommended material, understand it, analyse it, question it, and then reconstruct in your own way. You will then hand in a summary of the material for each major topic, where, in addition to the contents, you will describe your thoughts and questions on it. These submissions contribute a total of 25% for your final grade. Another 25% will be determined by the discussions and your presentation.
To make discussions productive and engaging, you will be split into teams, each guided by a senior lecturer and a PhD student or a Postdoc working in this research area, who will double up as a scribe for your discussion. Each session will consist of a short lecture by one of the senior lecturers which will set the theme for the discussions of the session. Following this, each team will be assigned some questions which they have to discuss over the next 30-40 minutes and present solutions/possible solutions/solution templates together. How you present the solutions is upto you, as a team. You are more than welcome to take your own notes or use the script that the PhD student/Postdoc prepares.
At the end of the semester, you will be tasked with writing a summary of one of the major topics. Details about this summary will be informed via the mailing list at a later date. This will contribute 50% of your grade.
Grades for he course will computed as follows:
- Topic Summaries (25%). The schedule for this will be announced shortly. Not more than 8 summaries will be expected throughout the semester. Summaries are individual pieces of work. We encourage you to discuss the material with your fellow classmates. But the final work must be your own and reflect your understanding and insights into the topic.
- Participation (25%). Attending the sessions is highly recommended, since the class discussions will be graded.
- Final Submission (50%). Final evaluation will be based on a written submission that presents a summary (larger and more detailed than the topic summaries for homework).
|2 November 2020||Introduction to the Course||None||Session 1||Slides for Introduction Sessions|
|5 November 2020||Challenges and Responses - I||None||Session 2|
|9 November 2020||Challenges and Responses - II||None||Session 3|
|12 November 2020||Digital Circuit Design - I||Digital Design||Session 4||Slides for Digital Design|
|16 November 2020||Digital Circuit Design - II||Session 5|
|19 November 2020||Digital Circuit Design - III||Session 6|
|23 November 2020||Tutorial for Digital Circuits||No Recording|
|26 November 2020||Centralized Clocking - I||Centralized Clocking||Session 8|
|30 November 2020||Centralized Clocking - II||Session 9|
|3 December 2020||Centralized Clocking - III||Session 10|
|7 December 2020||Metastability - I||Metastability||Session 11|
|10 December 2020||Metastability - II||Session 12|
|14 December 2020||Phase Locked Loops - I||Phase Locked Loops||Session 13||Slides|
|17 December 2020||Phase Locked Loops - II||Session 14||Slides|
|4 Jan 2021||Simulating Synchronous Systems - I||Simulating Synchronous Systems||Session 15||Slides|
|7 Jan 2021||Simulating Synchronous Systems - II||Session 16||Slides|
|11 Jan 2021||Network Synchronisation - I||Network Synchronisation||Session 17||Slides|
|14 Jan 2021||Network Synchronisation - II||Session 18||Slides|
|18 Jan 2021||Network Synchronisation - III||Session 19||Slides|
|21 Jan 2021||Network Synchronisation - IV||Session 20|
|25 Jan 2021||Gradient Clock Synchronisation - I||Gradient Clock Synchronisation||Session 21||Slides|
|28 Jan 2021||Gradient Clock Synchronisation - II||Session 22||Slides|
|1 Feb 2021||Gradient Clock Synchronisation - III||Gradient Clock Synchronisation - II||Session 23||Slides|
|4 Feb 2021||Gradient Clock Synchronisation - IV||Session 24||Slides|
- Instructions for your assignments
- Reading Material 1 - Summary due at 23:59 11 Nov
- Reading Material 2 - Summary due at 23:59 25 Nov
- Optional Reference for Circuit Design
- Reading Material 3 - Summary due at 23:59 6 Dec
- Reading Material 4 - Summary due at 23:59 13 Dec
- Reading Material 5 (Part I) - Summary due at 23:59 4 Jan 2021
- Reading Material 5 (Updated and Detailed Version)
- Reading Material 6 - Network Synchronisation - Summary due at 23:59 10 Jan 2021
- Reading Material 7-I - Gradient Clock Synchronisation (Part I) - Summary due at 23:59 24 Jan 2021
- Reading Material 7-II - Gradient Clock Synchronisation (Part II) - Summary due at 23:59 31 Jan 2021
Platform and Privacy
We have decided to use Zoom as a videoconferencing service. Note that
this provider (Zoom Video Communications, Inc., 55 Almaden Blvd, Suite
600, San Jose, CA 95113, USA) can access all data that you provide when
registering for the video conference. If you do not provide personal
data during the registration, there is still a possibility that Zoom
identifies you using your IP address. We would not have decided to use
Zoom if we considered this as a significant risk. As an additional
precaution, we have opted to use European computing centers. Should you
still have privacy concerns (and are not using an Internet Service
Provider that cannot map IP addresses to your name), we suggest using an
anonymization service such as Tor (https://www.torproject.org/)
We would be happy if we could create a pleasant lecture environment
despite the current situation. Personal interactions, with your
microphone and camera switched on, may contribute to this environment.
We also encourage you to ask questions verbally.
Note that this is voluntary. You may switch off both your camera and
your microphone, and register under a pseudonym. Questions are still
possible, in particular using the chat function.