VLSI CAD Part II: Layout

About this course: You should complete the VLSI CAD Part I: Logic course before beginning this course. A modern VLSI chip is a remarkably complex beast: billions of transistors, millions of logic gates deployed for computation and control, big blocks of memory, embedded blocks of pre-designed functions designed by third parties (called “intellectual property” or IP blocks). How do people manage to design these complicated chips? Answer: a sequence of computer aided design (CAD) tools takes an abstract description of the chip, and refines it step-wise to a final design. This class focuses on the major design tools used in the creation of an Application Specific Integrated Circuit (ASIC) or System on Chip (SoC) design. Our focus in this part of the course is on the key logical and geometric representations that make it possible to map from logic to layout, and in particular, to place, route, and evaluate the timing of large logic networks. Our goal is for students to understand how the tools themselves work, at the level of their fundamental algorithms and data structures. Topics covered will include: technology mapping, timing analysis, and ASIC placement and routing. Recommended Background: Programming experience (C, C++, Java, Python, etc.) and basic knowledge of data structures and algorithms (especially recursive algorithms). An understanding of basic digital design: Boolean algebra, Kmaps, gates and flip flops, finite state machine design. Linear algebra and calculus at the level of a junior or senior in engineering. Elementary knowledge of RC linear circuits (at the level of an introductory physics class).

Who is this class for: You should be taking this course if (1) you are interested in building VLSI design tools; (2) you are interested in designing VLSI chips, and you want to know why the tools do what they do; (3) you just like cool algorithms, that work on big cool problems that involve bits, and gates, and geometry, and graphs, and matrices, and time, etc.

Created by:  University of Illinois at Urbana-Champaign

• Taught by:  Rob A. Rutenbar, Adjunct Professor

  Department of Computer Science

Level Intermediate Language English How To Pass Pass all graded assignments to complete the course. Задания курса

Каждый курс — это интерактивный учебник, который содержит видеоматериалы, тесты и проекты.

Помощь сокурсников

Общайтесь с тысячами других учащихся: обсуждайте идеи, материалы курса и помогайте друг другу осваивать новые понятия.

Сертификаты

Получите документы о прохождении курсов и поделитесь своим успехом с друзьями, коллегами и работодателями.

University of Illinois at Urbana-Champaign The University of Illinois at Urbana-Champaign is a world leader in research, teaching and public engagement, distinguished by the breadth of its programs, broad academic excellence, and internationally renowned faculty and alumni. Illinois serves the world by creating knowledge, preparing students for lives of impact, and finding solutions to critical societal needs.

Syllabus


WEEK 1


Orientation
In this module you will become familiar with the course and our learning environment. The orientation will also help you obtain the technical skills required for the course.


2 videos, 2 readings, 1 practice quiz expand

1. Video: Welcome and Introduction
2. Материал для самостоятельного изучения: Syllabus
3. Тренировочный тест: Demographics Survey
4. Материал для самостоятельного изучения: Tools For This Course
5. Video: Two Tools Tutorial

ASIC Placement



In this second part of our course, we will talk about geometry. We will begin with an overview of the ASIC layout process, and discuss the role of technology libraries, tech mapping (a topic we delay until the following week, to let those who want to do the Placer programming assignment have more time), and placement and routing. In this set of lectures, we focus on the placement process itself: you have a million gates from the result of synthesis and map, so, where do they go? This process is called “placement”, and we describe an iterative method, and a mathematical optimization method, that can each do very large placement tasks.


9 videos, 2 readings expand

1. Материал для самостоятельного изучения: Week 1 Overview
2. Video: Basics
3. Video: Wirelength Estimation
4. Video: Simple Iterative Improvement Placement
5. Video: Iterative Improvement with Hill Climbing
6. Video: Simulated Annealing Placement
7. Video: Analytical Placement: Quadratic Wirelength Model
8. Video: Analytical Placement: Quadratic Placement
9. Video: Analytical Placement: Recursive Partitioning
10. Video: Analytical Placement: Recursive Partitioning Example
11. Материал для самостоятельного изучения: Week 1 Assignments

WEEK 2


Technology Mapping



Technology Mapping! We omitted one critical step between logic and layout, the process of translating the output of synthesis -- which is NOT real gates in your technology library -- into real logic gates. The Tech Mapper performs this important step, and it is a surprisingly elegant algorithm involving recursive covering of a tree. Another place where knowing some practical computer science comes to the rescue in VLSI CAD.


6 videos, 2 readings expand

1. Материал для самостоятельного изучения: Week 2 Overview
2. Video: Technology Mapping Basics
3. Video: Technology Mapping as Tree Covering
4. Video: Technology Mapping—Tree-ifying the Netlist
5. Video: Technology Mapping—Recursive Matching
6. Video: Technology Mapping—Minimum Cost Covering
7. Video: Technology Mapping—Detailed Covering Example
8. Материал для самостоятельного изучения: Week 2 Assignments

Graded: Problem Set #1
Graded: Programming Assignment #3: Placer

WEEK 3


ASIC Routing



Routing! You put a few million gates on the surface of the chip in some sensible way. What's next? Create the wires to connect them. We focus on Maze Routing, which is a classical and powerful technique with the virtue that one can "add" much sophisticated functionality on top of a rather simple core algorithm. This is also the topic for final (optional) programming assignment. Yes, if you choose, you get to route pieces of the industrial benchmarks we had you place in the placer software assignment.


9 videos, 2 readings expand

1. Материал для самостоятельного изучения: Week 3 Overview
2. Video: Routing Basics
3. Video: Maze Routing: 2-Point Nets in 1 Layer
4. Video: Maze Routing: Multi-Point Nets
5. Video: Maze Routing: Multi-Layer Routing
6. Video: Maze Routing: Non-Uniform Grid Costs
7. Video: Implementation Mechanics: How Expansion Works
8. Video: Implementation Mechanics: Data Structures & Constraints
9. Video: Implementation Mechanics: Depth First Search
10. Video: From Detailed Routing to Global Routing
11. Материал для самостоятельного изучения: Week 3 Assignments

Graded: Problem Set #2

WEEK 4


Timing Analysis



You synthesized it. You mapped it. You placed it. You routed it. Now what? HOW FAST DOES IT GO? Oh, we need some new models, to talk about how TIMING works. Delay through logic gates and big networks of gates. New numbers to understand: ATs, RATs, SLACKS, etc. And some electrical details (minimal) to figure out how delays happen through the physical geometry of physical routed wires. All together this is the stuff of Static Timing Analysis (STA), which is a huge and important final "sign off" step in real ASIC design.


8 videos, 2 readings expand

1. Материал для самостоятельного изучения: Week 4 Overview
2. Video: Basics
3. Video: Logic-Level Timing: Basic Assumptions & Models
4. Video: Logic-Level Timing: STA Delay Graph, ATs, RATs, and Slacks
5. Video: Logic-Level Timing: A Detailed Example and the Role of Slack
6. Video: Logic-Level Timing: Computing ATs, RATs, Slacks, and Worst Paths
7. Video: Interconnect Timing: Electrical Models of Wire Delay
8. Video: Interconnect Timing: The Elmore Delay Model
9. Video: Interconnect Timing: Elmore Delay Examples
10. Материал для самостоятельного изучения: Week 4 Assignments

Graded: Problem Set #3
Graded: Programming Assignment #4: Router

WEEK 5


Final Exam
There is no new content this week. Instead, you should focus on finishing the last problem set and completing the Final Exam.


1 practice quiz expand

1. Тренировочный тест: End of Course Survey

Graded: Problem Set #4
Graded: Final Exam