product iamge

VLSI Physical Design: From Graph Partitioning to Timing Closure

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

The complexity of modern chip design requires extensive use of specialized software throughout the process. To achieve the best results, a user of this software needs a high-level understanding of the underlying mathematical models and algorithms. In addition, a developer of such software must have a keen understanding of relevant computer science aspects, including algorithmic performance bottlenecks and how various algorithms operate and interact. This book introduces and compares the fundamental algorithms that are used during the IC physical design phase, wherein a geometric chip layout is produced starting from an abstract circuit design. This updated second edition includes recent advancements in the state-of-the-art of physical design, and builds upon foundational coverage of essential and fundamental techniques. Numerous examples and tasks with solutions increase the clarity of presentation and facilitate deeper understanding. A comprehensive set of slides is available on the Internet for each chapter, simplifying use of the book in instructional settings.

“This improved, second edition of the book will continue to serve the EDA and design community well. It is a foundational text and reference for the next generation of professionals who will be called on to continue the advancement of our chip design tools and design the most advanced micro-electronics.” 

Dr. Leon Stok, Vice President, Electronic Design Automation, IBM Systems Group

“This is the book I wish I had when I taught EDA in the past, and the one I’m using from now on.” 

Dr. Louis K. Scheffer, Howard Hughes Medical Institute

“I would happily use this book when teaching Physical Design. I know of no other work that’s as comprehensive and up-to-date, with algorithmic focus and clear pseudocode for the key algorithms. The book is beautifully designed!”

Prof. John P. Hayes, University of Michigan

“The entire field of electronic design automation owes the authors a great debt for providing a single coherent source on physical design that is clear and tutorial in nature, while providing details on key state-of-the-art topics such as timing closure.”

Prof. Kurt Keutzer, University of California, Berkeley

“An excellent balance of the basics and more advanced concepts, presented by top experts in the field.”

Prof. Sachin Sapatnekar, University of Minnesota


Author(s): Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu
Edition: 2
Publisher: Springer
Year: 2022

Language: English
Pages: 328
City: Cham

Foreword
Preface to the 2nd Edition
Preface to the 1st Edition
Contents
About the Authors
1: Introduction
1.1 Electronic Design Automation (EDA)
1.2 VLSI Design Flow
1.3 VLSI Design Styles
1.4 Layout Layers and Design Rules
1.5 Physical Design Optimizations
1.6 Algorithms and Complexity
Example: Exhaustively Enumerating All Placement Possibilities
1.7 Graph Theory Terminology
1.8 Common EDA Terminology
References
2: Netlist and System Partitioning
2.1 Introduction
2.2 Terminology
2.3 Optimization Goals
2.4 Partitioning Algorithms
2.4.1 Kernighan-Lin (KL) Algorithm
Kernighan-Lin Algorithm
Example: KL Algorithm
2.4.2 Extensions of the Kernighan-Lin Algorithm
2.4.3 Fiduccia-Mattheyses (FM) Algorithm
Fiduccia-Mattheyses Algorithm
Example: FM Algorithm
2.5 A Framework for Multilevel Partitioning
2.5.1 Clustering
2.5.2 Multilevel Partitioning
2.5 Exercises
References
3: Chip Planning
3.1 Introduction to Floorplanning
Example: Floorplan Area Minimization
3.2 Optimization Goals in Floorplanning
3.3 Terminology
3.4 Floorplan Representations
3.4.1 Floorplan to a Constraint Graph Pair
Example: Floorplan to a Constraint Graph Pair
3.4.2 Floorplan to a Sequence Pair
Example: Floorplan to a Sequence Pair
3.4.3 Sequence Pair to a Floorplan
Sequence Pair Evaluation Algorithm
Longest Common Subsequence (LCS) Algorithm
Example: Sequence Pair to a Floorplan
3.5 Floorplanning Algorithms
3.5.1 Floorplan Sizing
Example: Floorplan Sizing
3.5.2 Cluster Growth
Linear Ordering Algorithm
Example: Linear Ordering Algorithm
Cluster Growth Algorithm
Example: Floorplan Construction by Cluster Growth
3.5.3 Simulated Annealing
Simulated Annealing Algorithm
3.5.4 Integrated Floorplanning Algorithms
3.6 Pin Assignment
Example: Pin Assignment Using Concentric Circles (Including Algorithm)
3.7 Power and Ground Routing
3.7.1 Design of a Power-Ground Distribution Network
3.7.2 Planar Routing
3.7.3 Mesh Routing
3.7 Exercises
References
4: Global and Detailed Placement
4.1 Introduction
4.2 Optimization Objectives
Example: Total Weighted Wirelength of a Placement
Example: Cut Sizes of a Placement
Example: Wire Density of a Placement
4.3 Global Placement
4.3.1 Min-Cut Placement
Min-Cut Algorithm
Example: Min-Cut Placement Using the KL Algorithm
Example: Min-Cut Placement Using the FM Algorithm
Example: Min-Cut Placement with External Connections
Example: Min-Cut Placement Considering Pins Outside of the Partitioned Region
4.3.2 Analytic Placement
Example: Quadratic Placement
Example: ZFT Position
Force-Directed Placement Algorithm
Example: Force-Directed Placement
Force-Directed Placement with Ripple Move Algorithm
4.3.3 Simulated Annealing
Simulated Annealing Algorithm for Placement
4.3.4 Modern Placement Algorithms
4.4 Legalization and Detailed Placement
4.4 Exercises
References
5: Global Routing
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
Example: RMSTs and RSMTs
Sequential Steiner Tree Heuristic
Example: Sequential Steiner Tree Heuristic
5.6.2 Global Routing in a Connectivity Graph
Global Routing in a Connectivity Graph
Example: Global Routing in a Connectivity Graph
Example: Determining Routability
5.6.3 Finding Shortest Paths with Dijkstra´s Algorithm
Dijkstra´s Algorithm
Example: Dijkstra´s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
Integer Linear Programming (ILP) Global Routing Formulation
Example: Global Routing Using Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
Global Routing Framework with Rip-Up and Reroute
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated Congestion Routing
5.8 Exercises
References
6: Detailed Routing
6.1 Terminology
6.2 Horizontal and Vertical Constraint Graphs
6.2.1 Horizontal Constraint Graphs
6.2.2 Vertical Constraint Graphs
Example: Vertical and Horizontal Constraint Graphs
6.3 Channel Routing Algorithms
6.3.1 Left-Edge Algorithm
Left-Edge Algorithm
Example: Left-Edge Algorithm
6.3.2 Dogleg Routing
Example: Dogleg Left-Edge Algorithm
6.4 Switchbox Routing
6.4.1 Terminology
6.4.2 Switchbox Routing Algorithms
Example: Switchbox Routing
6.5 Over-the-Cell and Gcell Routing Algorithms
6.5.1 OTC Routing Methodology
6.5.2 OTC and Gcell Routing Algorithms
6.6 Modern Challenges in Detailed Routing
6.6 Exercises
References
7: Specialized Routing
7.1 Area Routing
7.1.1 Introduction
7.1.2 Net Ordering
7.2 Non-Manhattan Routing
7.2.1 Octilinear Steiner Trees
Octilinear Steiner Tree Algorithm
Example: Octilinear Steiner Tree
7.2.2 Octilinear Maze Search
7.3 Clock Routing
7.3.1 Terminology
7.3.2 Problem Formulations for Clock-Tree Routing
7.4 Modern Clock Tree Synthesis
7.4.1 Constructing Trees with Zero Global Skew
Basic Method of Means and Medians (BASIC_MMM(S,T))
Recursive Geometric Matching Algorithm (RGM(S,T))
Build Tree of Segments (DME Bottom-Up Phase)
Find Exact Locations (DME Top-Down Phase)
7.4.2 Clock Tree Buffering in the Presence of Variation
7.4 Exercises
References
8: Timing Closure
8.1 Introduction
8.2 Timing Analysis and Performance Constraints
8.2.1 Static Timing Analysis
Longest Paths Algorithm
8.2.2 Delay Budgeting with the Zero-Slack Algorithm
Zero-Slack Algorithm (Late-Mode Analysis)
Forward Path Search (FORWARD_PATH(vmin,G))
Backward Path Search (BACKWARD_PATH(vmin,G))
Near-Zero-Slack Algorithm (Early-Mode Analysis)
8.3 Timing-Driven Placement
8.3.1 Net-Based Techniques
8.3.2 Embedding STA into Linear Programs for Placement
8.4 Timing-Driven Routing
8.4.1 The Bounded-Radius, Bounded-Cost Algorithm
BRBC Algorithm
8.4.2 Prim-Dijkstra Trade-Off
8.4.3 Minimization of Source-to-Sink Delay
8.5 Physical Synthesis
8.5.1 Gate Sizing
8.5.2 Buffering
8.5.3 Netlist Restructuring
8.6 Performance-Driven Design Flow
8.7 Conclusions
8.7 Exercises
References
9: Appendix
9.1 Machine Learning in Physical Design
9.1.1 Introduction
9.1.2 ML: Promise and Challenges in Physical Design
9.1.3 Canonical ML Applications
9.1.4 The State of ML for Physical Design
9.1.5 Future Developments
9.2 Solutions to Chapter Exercises
9.2.1 Chapter 2: Netlist and System Partitioning
9.2.2 Chapter 3: Chip Planning
9.2.3 Chapter 4: Global and Detailed Placement
9.2.4 Chapter 5: Global Routing
9.2.5 Chapter 6: Detailed Routing
9.2.6 Chapter 7: Specialized Routing
9.2.7 Chapter 8: Timing Closure
9.3 Example CMOS Cell Layouts
References
Index