https://www.ifte.de/books/eda/index.html
[EDACoverRed] 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
Overview
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 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8
Introduction Partitioning Chip Placement Global- Detailed Specialized- Timing
Planning Routing Routing Routing Closure
PDF PDF PDF PDF PDF PDF PDF PDF
PPT (0.7 MB) PPT (0.9 MB) PPT PPT PPT PPT PPT (0.9 MB) PPT
(2.1 MB) (1.4 MB) (1.5 MB) (1.0 MB) (1.1 MB)
Contents
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
Impressum
Last update: 20.12.2022