How To Clock Your Computer

Advanced Course, 2+2

Basic Information

Lectures:

Online. Link will be posted soon.

Organisers:Christoph Lenzen and Shreyas Srinivas
LecturersChristoph Lenzen, Moti Medina, Andreas Steininger, Danny Dolev, Ian Jones, Will Rosenbaum, Matthias Fuegger, Milos Krstic
First lecture:TBA
Tutorials:There will be no tutorials for this course
Assistant:Shreyas Srinivas
Credits:6
Exam:

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
Mailing List:The mailing list to register for this course will be posted shortly. Registrations for the exam will happen at the end of the term via email as well as HISPOS.

Announcements

Important course announcements concerning registration and general interest will be posted here. Most information will be conveyed via the mailing lists. 

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 of 2 or 3, each guided by a senior lecturer and as well as 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 provided 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 short 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 to 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%). Attendence at the weekly discussion session is mandatory
  • 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

Material