Hardware & Algorithms Lab (HAL)

In this course we will design reliable hardware that can contain faults which occur due to signals arriving from different “time zones”. This kind of hardware is useful when the goal is to design a processor or a chip with multiple clock domains.

In the preliminary part of the course I will quickly go over design and analysis of combinational and synchronous circuits, I will present the problem of Parallel Prefix Computation (PPC) and its application to the design of fast adders. At the end of this part I will present Sorting Networks.

In the second part of the course I will present the notion of “Metastability”. I will show that one cannot design (and implement) a circuit that detects, avoids, or resolves metastability. I will then present common (probabilistic) “solutions” to this problem.

In the last part of the course, I will present new methods of dealing with metastbility. These new methods *do not* try to avoid metastable faults, but provide hard guarantees despite these faults, that is, meaningful outputs can be computed even tough there are metastable faults. In this context I will present necessary theoretical background. I will show how to design optimal metastbility-containing sorting networks, how to use these networks to synchronize hardware clocks, and how to design a metastability-containing “producer-consumer” link that connects two circuits in two different clock domains.

The first and second part of the course are based on this book, and additional classical papers. The third part of the course is based on research papers from the last 2 years.

At the end of the course I will present open research problems, a solution of which can be a basis of a master’s (or PhD) thesis.