VLSI Physical Design: From Graph Partitioning to Timing Closure
Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu
2011, 310 pages, Springer

ISBN 978-90-481-9590-9, eBook 978-90-481-9591-6


Link to Springer / SpringerLink (eBook) / Amazon.de / Amazon.com / SLUB



Design and optimization of integrated circuits are essential to the creation of new semiconductor chips, and physical optimizations are getting more prominent as a result of semiconductor scaling. Modern chip design has become so complex that it is largely performed by specialized software, which is frequently updated to address advances in semiconductor technologies and increased problem complexities. A user of such software needs a high-level understanding of the underlying mathematical models and algorithms. On the other hand, a developer of such software must have a keen understanding of computer science aspects, including algorithmic performance bottlenecks and how various algorithms operate and interact.


This book introduces and compares algorithms that are used during the IC physical design phase, wherein a geometric chip layout is produced starting from an abstract circuit design. The emphasis is on essential and fundamental techniques, ranging from hypergraph partitioning and circuit placement to timing closure.


Cover   Foreword/Preface   Table of Contents   Flyer   Presentation Materials   Errata   Chinese Edition


Chapter Slides


Chapter 1

PPT (0.9 MB) 

Chapter 2

PPT (1.9 MB)

Chapter 3

PPT (3.1 MB)

Chapter 4

PPT (2.7 MB)

Chapter 5

PPT (3.6 MB)

Chapter 6

PPT (2.1 MB)

Chapter 7

PPT (1.6 MB)

Chapter 8

PPT (1.6 MB)





1     Introduction   This book introduces and evaluates algorithms used during physical design to produce a geometric chip layout from an abstract circuit design. Rather than list every relevant technique, however, it presents the essential and fundamental algorithms used within each physical design stage. The basic concepts, flows, methodologies and terms of physical design are presented in Chap. 1.

1.1      Electronic Design Automation

1.2      VLSI Design Flow

1.3      VLSI Design Style

1.4      Layout Layers and Design Rules

1.5      Physical Design Optimization

1.6      Algorithms and Complexity

1.7      Graph Theory Terminology

1.8      Common EDA Terminology


2     Netlist and System Partitioning   The design complexity of modern integrated circuits has reached unprecedented scale. A common strategy is to partition or divide the design into smaller portions, each of which can be processed with some degree of independence and parallelism. Manual partitioning can be performed in the context of system-level modules by viewing them as single entities, in cases where hierarchical information is available. In contrast, automated netlist partitioning (Secs. 2.1-2.4) can handle large netlists and can redefine a physical hierarchy of an electronic system, ranging from boards to chips and from chips to blocks. Traditional netlist partitioning can be extended to multi-level partitioning (Sec. 2.5), which can be used for large-scale circuits and system partitioning on FPGAs (Sec. 2.6).

2.1      Introduction

2.2      Terminology

2.3      Optimization Goals

2.4      Partitioning Algorithms

2.5      A Framework for Multilevel Partitioning

2.6      System Partitioning onto Multiple FPGAs


3     Chip Planning   Chip planning deals with large modules such as caches, embedded memories, and intellectual property (IP) cores that have known areas, fixed or changeable shapes, and possibly fixed locations. Assigning shapes and locations to circuit modules during chip planning produces blocks, and enables early estimates of interconnect length, circuit delay and chip performance. Chip planning consists of three major stages (1) floorplanning, (2) pin assignment, and (3) power planning. -- Floorplanning (Sects. 3.4-3.5) determines the locations and dimensions of these blocks, based on the areas and aspect ratios of the modules so as to optimize chip size, reduce interconnect and improve timing. Pin assignment (Sect. 3.6) connects outgoing signal nets to block pins. Power planning (Sect. 3.7) builds the power supply network, i.e., power and ground nets, so as to ensure that each block is provided with appropriate supply voltage.

3.1      Introduction to Floorplanning

3.2      Optimization Goals in Floorplanning

3.3      Terminology

3.4      Floorplan Representations

3.5      Floorplanning Algorithms

3.6      Pin Assignment

3.7      Power and Ground Routing


4     Global and Detailed Placement   After partitioning the circuit into smaller modules (Chap. 2) and floorplanning the layout to determine block outlines and pin locations (Chap. 3), placement seeks to determine the locations of standard cells or logic elements within each block while addressing optimization objectives, e.g., minimizing the total length of connections between elements. Specifically, global placement (Sec. 4.3) assigns general locations to movable objects, while detailed placement (Sec. 4.4) refines object locations to legal cell sites and enforces non-overlapping constraints.

4.1      Introduction

4.2      Optimization Objectives

4.3      Global Placement

4.4      Legalization and Detailed Placement


5     Global Routing   During global routing, pins with the same electric potential are connected using wire segments. The layout area is represented as routing regions (Sec. 5.4) and all nets in the netlist are routed in a systematic manner (Sec. 5.5). To minimize total routed length, or optimize other objectives (Sec. 5.3), the route of each net should be short (Sec. 5.6). However, these routes often compete for the same set of limited resources. Such conflicts can be resolved by concurrent routing of all nets (Sec. 5.7), e.g., integer linear programming (ILP), or by sequential routing techniques, e.g., rip-up and reroute. Several algorithmic techniques enable scalability of modern global routers (Sec. 5.8).

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.7      Full-Netlist Routing

5.8      Modern Global Routing


6     Detailed Routing   After global routing, each net undergoes detailed routing. The objective of detailed routing is to assign route segments of signal nets to specific routing tracks, vias, and metal layers in a manner consistent with given global routes of those nets. As long as the routes remain properly connected across all neighboring gcells, the detailed routing of one gcell can be performed independently of the routing of other gcells. This facilitates an efficient divide-and-conquer framework and also enables parallel algorithms. Thus, detailed routing runtime can (theoretically) scale linearly with the size of the layout. Traditional detailed routing techniques are applied within routing regions, such as channels (Sec. 6.3) and switchboxes (Sec. 6.4). For modern designs, over-the-cell (OTC) routing (Sec. 6.5) allows wires to be routed over standard cells. Due to technology scaling, modern detailed routers must account for manufacturing rules and the impact of manufacturing faults (Sec. 6.6).

6.1      Terminology

6.2      Horizontal and Vertical Constraint Graphs

6.3      Channel Routing Algorithms

6.4      Switchbox Routing

6.5      Over-the-Cell Routing Algorithms

6.6      Modern Challenges in Detailed Routing


7     Specialized Routing   For signal wires in digital integrated circuits, global routing (Chap. 5) is performed first, and detailed routing next (Chap. 6). However, some types of designs, such as analog circuits and printed circuit boards (PCBs) with gridless (trackless) routing, do not warrant this distinction. Smaller, older designs with only one or two metal layers also fall into this category. When global and detailed routing are not performed separately, area routing (Secs. 7.1-7.2) directly constructs metal routes for signal connections. Unlike routing with multiple metal layers, area routing emphasizes crossing minimization. Non-Manhattan routing is discussed in Sec. 7.3, and nets that require special treatment, such as clock signals, are discussed in Secs. 7.4-7.5.

7.1      Introduction to Area Routing

7.2      Net Ordering in Area Routing

7.3      Non-Manhattan Routing

7.4      Basic Concepts in Clock Networks

7.5      Modern Clock Tree Synthesis


8     Timing Closure   The layout of an IC must not only satisfy geometric requirements, e.g., non-overlapping cells and routability, but also meet the designís timing constraints, e.g., setup (long-path) and hold (short-path) constraints. The optimization process that meets these requirements and constraints is called timing closure. It integrates point optimizations discussed in previous chapters, such as placement (Chap. 4) and routing (Chaps. 5-7), with specialized methods to improve circuit performance. The following components of timing closure are covered in this chapter: Timing-driven placement (Sec. 8.3) minimizes signal delays when assigning locations to circuit elements. Timing-driven routing (Sec. 8.4) minimizes signal delays when selecting routing topologies and specific routes. Physical synthesis (Sec. 8.5) improves timing by changing the netlist. Section 8.6 integrates these optimizations in a performance-driven physical design flow.

8.1      Introduction

8.2      Timing Analysis and Performance Constraints

8.3      Timing-Driven Placement

8.4      Timing-Driven Routing

8.5      Physical Synthesis

8.6      Performance-Driven Design Flow

8.7      Conclusions


A     Solutions to Chapter Excercises

B     Example CMOS Cell Layouts


Last update: 12.02.2020