A large digital integrated circuit (IC) may require 100,000 lines of high-level description in a hardware modeling language, which then turns into 10,000,000 logic gates, which ultimately end up as 1 billion polygons on the
masks that define the integrated circuit. This course describes in detail the important CAD tools that perform the many steps of the transformation from Boolean equations to fabrication masks. We focus on mathematical models, algorithms, and data structures. We will write programs for simple versions of these tools. We will look at, and experiment with, a few real tools. The course covers a review of Boolean algebra, followed by (i) synthesis tools for 2-level and multi-level logic, that transform Boolean equations and finite state machine descriptions into optimized logic, and (ii) verification tools that decide whether the logic you built does the same thing as the specification you started with. Finally, the course covers geometric layout synthesis tools for component partitioning, placement, and wire routing and timing verification tools that determine if performance constraints are met. The CAD algorithms covered in the lectures are applicable not only to VLSI systems, but also to non-silicon applications (e.g., social computing, biology, financial).