Office address: 508 Computer Science Building
Department of Computer Science
Office phone: (212) 939-7056
E-mail address: nowick@cs.columbia.edu
Class Time: Tuesday/Thursday, 4:10-5:25 p.m.
Place: TBA
Credits: 3 points
Prerequisites:
(i) CS W3823 Digital Logic; and (ii) Data Structures
(either CS W3139 or CS W3131); or permission of the instructor.
No VLSI background is required.
Description:
An introduction to modern computer-aided design (``CAD'') of
digital systems. When you have completed the course, you will
have a good handle on the research aspects of digital CAD
(i.e., the underlying optimization algorithms used to automatically
design digital systems), as well as gain practical hands-on
experience in using existing CAD packages.
The course is a nice blend of three areas: (i) algorithms,
(ii) digital hardware, and (iii) software tools and applications.
You will learn state-of-the-art algorithms used in modern industrial
CAD tools, gain practical experience using software CAD tools,
and develop your own algorithms and tools.
The course systematically covers the various automated synthesis steps:
from a high-level user specification of an entire system down
to low-level optimized transistor-level circuits.
For high-level synthesis, we will cover basic tools and techniques,
such as resource scheduling, allocation and binding. We will also
cover the hardware description language, VHDL, which is widely used
in industry. Entire digital systems can be specified using this language.
For sequential logic synthesis, we will cover state machine synthesis,
including modern algorithms for state minimization, optimal
state encoding, and symbolic manipulation. We will then cover
recent optimization algorithms for combinational logic synthesis,
including 2-level, multi-level, Binary Decision Diagrams, Boolean
decomposition, and iterative resynthesis techniques used to
restructure and improve very large circuits.
Finally, we will cover algorithms for technology mapping,
where the abstract logic gates are mapped to physical transistor-level
cells.
If time permits, we will also cover recent applications of
``formal hardware verification'', ``testability'', ``timing optimization'',
``FPGA's'', as well as ``placement and routing'' techniques to automate
the final circuit layout.
You will also gain hands-on experience using a number of CAD packages, which you will apply to specify, synthesize and optimize a number of digital designs.