How To Clock Your Computer

Advanced Course, 4

Basic Information

Lectures:

Online. Zoom Link: https://cs-uni-saarland-de.zoom.us/j/95062856565  For password: check the mailing list

Organisers:Christoph Lenzen and Shreyas Srinivas
LecturersChristoph 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
Session Slots:

Monday 10:00 - 12:00,

Thursday 14:00-16:00

Assistant:Shreyas Srinivas
Credits:6
Exam:

A written submission

Registration
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
Mailing List:https://lists.mpi-inf.mpg.de/listinfo/how_to_clock_your_computer 

Announcements

  • 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.

Description

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.

Course Format

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. 

Evaluation

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).

Schedule

Date Topic Material Recording Slides
2 November 2020 Introduction to the Course None Session 1Slides 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 DesignSession 4Slides 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 ClockingSession 8  
30 November 2020 Centralized Clocking - II Session 9  
3 December 2020 Centralized Clocking - III Session 10  
7 December 2020 Metastability - I MetastabilitySession 11  
10 December 2020 Metastability - II Session 12  
14 December 2020 Phase Locked Loops - I Phase Locked LoopsSession 13Slides
17 December 2020 Phase Locked Loops - II Session 14Slides
Christmas Break        
4 Jan 2021 Simulating Synchronous Systems - I Simulating Synchronous SystemsSession 15Slides
7 Jan 2021 Simulating Synchronous Systems - II Session 16Slides
11 Jan 2021 Network Synchronisation - I Network SynchronisationSession 17Slides
14 Jan 2021 Network Synchronisation - II Session 18Slides
18 Jan 2021 Network Synchronisation - III Session 19Slides
21 Jan 2021 Network Synchronisation - IV Session 20  
25 Jan 2021 Gradient Clock Synchronisation - I Gradient Clock SynchronisationSession 21Slides
28 Jan 2021 Gradient Clock Synchronisation - II Session 22Slides
1 Feb 2021 Gradient Clock Synchronisation - III Gradient Clock Synchronisation - IISession 23 Slides
4 Feb 2021 Gradient Clock Synchronisation - IV Session 24 Slides

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/)

You can find Zoom's complete privacy policy at:
https://zoom.us/de-de/privacy.html

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.