VLSI Physical Design: From Graph Partitioning to Timing Closure
Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu
2022 (2nd edition), 317 pages, Springer

ISBN 978-3-030-96414-6, eBook 978-3-030-96415-3
DOI 10.1007/978-3-030-96415-3


Link to Springer (eBook) / Amazon.de / Amazon.com / SLUB (eBook / print) / German Edition



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.7 MB) 

Chapter 2

PPT (0.9 MB)

Chapter 3

PPT (2.1 MB)

Chapter 4

PPT (1.4 MB)

Chapter 5

PPT (1.5 MB)

Chapter 6

PPT (1.0 MB)

Chapter 7

PPT (0.9 MB)

Chapter 8

PPT (1.1 MB)





1     Introduction   The field of electronic design automation (EDA) concerns the research, development and use of computer programs, i.e. software tools, for the design of electronic systems, such as integrated circuits and printed circuit boards. This first chapter surveys the history of EDA, the steps of the VLSI design flow, the various design styles, design rules, core algorithmic and complexity considerations in physical design, and finally summarizes important terminology used in the area of EDA.

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   Partitioning divides the circuit into several subcircuits (partitions or blocks) while minimizing the number of connections between partitions. Such partitioning enables each subcircuit to be processed with some degree of independence and parallelism, in stages that follow. 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 to handle large-scale circuits and systems.

2.1      Introduction

2.2      Terminology

2.3      Optimization Goals

2.4      Partitioning Algorithms

2.5      A Framework for Multilevel Partitioning


3     Chip Planning   Chapter 3 is dedicated to chip planning, which includes floorplanning, pin assignment (I/O assignment), and power-ground planning. Floorplanning (Secs. 3.1 - 3.5) determines the locations and dimensions of the shapes that are the result of partitioning the entire circuit (Chap. 2). Hence, floorplanning produces assigned blocks and enables early estimates of interconnect length, circuit delay and chip performance. Pin assignment (Sec. 3.6) assigns outgoing signal nets to block pins. Pin assignment directly influences the quality of the floorplan, especially the wiring length. Therefore, floorplanning and pin assignment are generally closely coupled or even combined as a single step. Finally, power planning (Sec. 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 the outlines and positions of blocks and their pin locations (Chap. 3), placement seeks to determine the locations of (standard) cells or logic elements within each block. Placement is subject to multiple optimization objectives, a common one being the minimization of the total length of connections between elements. Global placement (Sec. 4.3) assigns general locations to movable objects, which is then followed by detailed placement (Sec. 4.4), which refines object locations to legal cell sites and enforces nonoverlapping constraints.

4.1      Introduction

4.2      Optimization Objectives

4.3      Global Placement

4.4      Legalization and Detailed Placement


5     Global Routing   The routing process determines the precise signal paths for nets on the chip layout. Routing algorithms often adopt a two-stage approach. Global routing first partitions the chip into routing regions and searches for region-to-region paths for all signal nets; this is followed by detailed routing, which determines the exact tracks and vias of these nets based on their region assignments (Chap. 6). During global routing, pins with the same electric potential are connected while minimizing total routed length, or optimizing other objectives (Sec. 5.3). The layout area is represented as routing regions (Sec. 5.4) and all nets are routed in a systematic manner (Sec. 5.5). To meet optimization objectives, the route of each net should be short (Sec. 5.6); however, because these routes often compete for the same set of limited resources, conflicts may occur. Such conflicts are often resolved by concurrent routing of all nets (Sec. 5.7). 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   Following 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. 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) or gcell routing (Sec. 6.5) allows wires to be routed over (standard) cells based on their gcell assignments. Due to technology scaling, modern detailed routers must account for additional manufacturing rules and the impact of manufacturing faults and resolution (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 and Gcell Routing Algorithms

6.6      Modern Challenges in Detailed Routing


7     Specialized Routing   Chapter 7 deals with several specialized types of routing which do not conform with the global-detailed paradigm followed by Chapters 5 and 6. In some types of designs, such as analog circuits and printed circuit boards (PCBs), area routing is applied. Here, the entire area available for interconnections is considered without geometric restrictions, such as global routing cells (gcells). Hence, an area router directly constructs metal routes for signal connections without separate global and detailed routing steps (Sec. 7.1). Non-Manhattan routing is introduced in Sec. 7.2. Clock routing and the related clock tree synthesis are discussed in Secs. 7.3 - 7.4.

7.1      Area Routing

7.2      Non-Manhattan Routing

7.3      Clock Routing

7.4      Modern Clock Tree Synthesis


8     Timing Closure   Chapter 8 focuses on timing closure, and its perspective is particularly unique. It offers a comprehensive coverage of timing analysis and relevant optimizations in placement, routing and netlist restructuring. Timing-driven placement (Sec. 8.3) minimizes signal delays when assigning circuit elements to locations. Timing-driven routing (Sec. 8.4) minimizes signal delays when selecting routing topologies and specific routes. Physical synthesis (Sec. 8.5) improves timing by making changes to the netlist.

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


9     Appendix   The appendix of the book first reviews the promise and challenges for machine learning (ML) in physical design and illustrates benefits that can be achieved in terms of schedule and quality of results, as demonstrated in recent publications (Appendix 9.1). It identifies a number of useful surveys and reviews ML-based methods that can be applied to tasks addressed in the preceding chapters of the book. Appendix 9.2 presents detailed solutions to the exercises of Chaps. 2-8. Finally, Appendix 9.3 depicts layout examples of typical CMOS-library cells, such as the inverter, buffer, NAND and NOR gates, and an AND-OR-Invert gate.

9.1      Machine Learning in Physical Design

9.2      Solutions to Chapter Exercises

9.3      Example CMOS Cell Layouts


Last update: 20.12.2022