VLSI Physical Design. Springer

From Graph Partitioning to Timing Closure

Andrew B. Kahng • Jens Lienig • Igor L. Markov • Jin Hu

© Springer Science+Business Media B.V. 2011

No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work.

Cover design: eStudio Calamar S.L.

Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)

e-books shop
VLSI Physical Design:
From Graph Partitioning to Timing Closure

Foreword
Physical design of integrated circuits remains one of the most interesting and challenging
arenas in the field of Electronic Design Automation. The ability to integrate
more and more devices on our silicon chips requires the algorithms to continuously
scale up. Nowadays we can integrate 2e9 transistors on a single 45nm-technology
chip. This number will continue to scale for the next couple of technology generations,
requiring more transistors to be automatically placed on a chip and connected
together. In addition, more and more of the delay is contributed by the wires that
interconnect the devices on the chip. This has a profound effect on how physical
design flows need to be put together. In the 1990s, it was safe to assume that timing
goals of the design could be reached once the devices were placed well on the chip.
Today, one does not know whether the timing constraints can be satisfied until the
final routing has completed.

As far back as 10 or 15 years ago, people believed that most physical design problems
had been solved. But, the continued increase in the number of transistors on
the chip, as well as the increased coupling between the physical, timing and logic
domains warrant a fresh look at the basic algorithmic foundations of chip implementation.
That is exactly what this book provides. It covers the basic algorithms underlying
all physical design steps and also shows how they are applied to current instances
of the design problems. For example, Chapter 7 provides a great deal of
information on special types of routing for specific design situations.

Several other books provide in-depth descriptions of core physical design algorithms
and the underlying mathematics, but this book goes a step further. The authors very
much realize that the era of individual point algorithms with single objectives is over.
Throughout the book they emphasize the multi-objective nature of modern design
problems and they bring all the pieces of a physical design flow together in Chapter
8. A complete flow chart, from design partitioning and floorplanning all the way to
electrical rule checking, describes all phases of the modern chip implementation
flow. Each step is described in the context of the overall flow with references to the
preceding chapters for the details.

This book will be appreciated by students and professionals alike. It starts from the
basics and provides sufficient background material to get the reader up to speed on
the real issues. Each of the chapters by itself provides sufficient introduction and
depth to be very valuable. This is especially important in the present era, where
experts in one area must understand the effects of their algorithms on the remainder
of the design flow. An expert in routing will derive great benefit from reading the
chapters on planning and placement. An expert in Design For Manufacturability
(DFM) who seeks a better understanding of routing algorithms, and of how these
algorithms can be affected by choices made in setting DFM requirements, will benefit
tremendously from the chapters on global and detailed routing.

The book is completed by a detailed set of solutions to the exercises that accompany
each chapter. The exercises force the student to truly understand the basic physical
design algorithms and apply them to small but insightful problem instances.
This book will serve the EDA and design community well. It will be 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.
Dr. Leon Stok
Vice President, Electronic Design Automation
IBM Systems and Technology Group
Hopewell Junction, NY



Preface
VLSI physical design of integrated circuits underwent explosive development in the
1980s and 1990s. Many basic techniques were suggested by researchers and implemented
in commercial tools, but only described in brief conference publications
geared for experts in the field. In the 2000s, academic and industry researchers focused
on comparative evaluation of basic techniques, their extension to large-scale
optimization, and the assembly of point optimizations into multi-objective design
flows. Our book covers these aspects of physical design in a consistent way, starting
with basic concepts in Chapter 1 and gradually increasing the depth to reach advanced
concepts, such as physical synthesis. Readers seeking additional details, will
find a number of references discussed in each chapter, including specialized monographs
and recent conference publications.

Chapter 2 covers netlist partitioning. It first discusses typical problem formulations
and proceeds to classic algorithms for balanced graph and hypergraph partitioning.
The last section covers an important application – system partitioning among multiple
FPGAs, used in the context of high-speed emulation in functional validation.

Chapter 3 is dedicated to chip planning, which includes floorplanning, powerground
planning and I/O assignment. A broad range of topics and techniques are
covered, ranging from graph-theoretical aspects of block-packing to optimization by
simulated annealing and package-aware I/O planning.

Chapter 4 addresses VLSI placement and covers a number of practical problem
formulations. It distinguishes between global and detailed placement, and first covers
several algorithmic frameworks traditionally used for global placement. Detailed
placement algorithms are covered in a separate section. Current state of the art
in placement is reviewed, with suggestions to readers who might want to implement
their own software tools for large-scale placement.

Chapters 5 and 6 discuss global and detailed routing, which have received significant
attention in research literature due to their interaction with manufacturability
and chip-yield optimizations. Topics covered include representing layout with graph
models and performing routing, for single and multiple nets, in these models. Stateof-
the-art global routers are discussed, as well as yield optimizations performed in
detailed routing to address specific types of manufacturing faults.

Chapter 7 deals with several specialized types of routing which do not conform with
the global-detailed paradigm followed by Chapters 5 and 6. These include non-
Manhattan area routing, commonly used in PCBs, and clock-tree routing required
for every synchronous digital circuit. In addition to algorithmic aspects, we explore
the impact of process variability on clock-tree routing and means of decreasing this impact.

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. Section 8.6 assembles all these techniques,
along with those covered in earlier chapters, into an extensive design flow,
illustrated in detail with a flow chart and discussed step-by-step with several figures
and many references.

This book does not assume prior exposure to physical design or other areas of EDA.
It introduces the reader to the EDA industry and basic EDA concepts, covers key
graph concepts and algorithm analysis, carefully defines terms and specifies basic
algorithms with pseudocode. Many illustrations are given throughout the book, and
every chapter includes a set of exercises, solutions to which are given in one of the
appendices. Unlike most other sources on physical design, we made an effort to
avoid impractical and unnecessarily complicated algorithms. In many cases we offer
comparisons between several leading algorithmic techniques and refer the reader to
publications with additional empirical results.

Some chapters are based on material in the book Layoutsynthese elektronischer
Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung, which
was published by Springer in 2006.

We are grateful to our colleagues and students who proofread earlier versions of this
book and suggested a number of improvements (in alphabetical order): Matthew
Guthaus, Kwangok Jeong, Johann Knechtel, Andreas Krinke, Nancy MacDonald,
Jarrod Roy, Yen-Kuan Wu and Hailong Yao.

Images for global placement and clock routing in Chapter 8 were provided by
Myung-Chul Kim and Dong-Jin Lee. Cell libraries in Appendix B were provided by
Bob Bullock, Dan Clein and Bill Lye from PMC Sierra; the layout and schematics in
Appendix B were generated by Matthias Thiele. The work on this book was partially
supported by the National Science Foundation (NSF) through the CAREER
award 0448189 as well as by Texas Instruments and Sun Microsystems.
We hope that you will find the book interesting to read and useful in your professional endeavors.
Sincerely,

Andrew, Jens, Igor and Jin



Author's
Andrew B. Kahng
University of California at San Diego
Departments of CSE and ECE
Mailcode #0404
La Jolla, California 92093
USA
Igor L. Markov
University of Michigan
Electrical Engineering and
Computer Science
2260 Hayward St.
Ann Arbor, Michigan 48109
USA

Jens Lienig
Dresden University of Technology
Electrical Engineering and
Information Technology
Helmholtzstr. 10
01069 Dresden
Germany


Jin Hu
University of Michigan
Electrical Engineering and
Computer Science
2260 Hayward St.
Ann Arbor, Michigan 48109
USA


Table of Contents
1 Introduction..................................................................3
1.1 Electronic Design Automation (EDA)............................................. 4
1.2 VLSI Design Flow........................................................................... 7
1.3 VLSI Design Styles ........................................................................ 11
1.4 Layout Layers and Design Rules................................................... 16
1.5 Physical Design Optimizations ...................................................... 18
1.6 Algorithms and Complexity ............................................................ 20
1.7 Graph Theory Terminology............................................................ 24
1.8 Common EDA Terminology ........................................................... 26
Chapter 1 References.......................................................................... 30
2 Netlist and System Partitioning ................................33
2.1 Introduction..................................................................................... 33
2.2 Terminology.................................................................................... 34
2.3 Optimization Goals......................................................................... 35
2.4 Partitioning Algorithms ................................................................... 36
2.4.1 Kernighan-Lin (KL) Algorithm ....................................... 36
2.4.2 Extensions of the Kernighan-Lin Algorithm .................. 41
2.4.3 Fiduccia-Mattheyses (FM) Algorithm............................ 41
2.5 A Framework for Multilevel Partitioning ......................................... 47
2.5.1 Clustering ...................................................................... 48
2.5.2 Multilevel Partitioning .................................................... 48
2.6 System Partitioning onto Multiple FPGAs...................................... 50
Chapter 2 Exercises............................................................................. 53
Chapter 2 References.......................................................................... 54
3 Chip Planning ..............................................................57
3.1 Introduction to Floorplanning ......................................................... 58
3.2 Optimization Goals in Floorplanning.............................................. 59
3.3 Terminology.................................................................................... 61
3.4 Floorplan Representations............................................................. 63
3.4.1 Floorplan to a Constraint-Graph Pair............................ 63
3.4.2 Floorplan to a Sequence Pair ....................................... 64
3.4.3 Sequence Pair to a Floorplan ....................................... 65
3.5 Floorplanning Algorithms ............................................................... 68
3.5.1 Floorplan Sizing ............................................................ 69
3.5.2 Cluster Growth .............................................................. 73
3.5.3 Simulated Annealing..................................................... 77
3.5.4 Integrated Floorplanning Algorithms............................. 81
3.6 Pin Assignment .............................................................................. 82
3.7 Power and Ground Routing ........................................................... 86
3.7.1 Design of a Power-Ground Distribution Network ......... 87
3.7.2 Planar Routing .............................................................. 87
3.7.3 Mesh Routing................................................................ 89
Chapter 3 Exercises............................................................................. 91
Chapter 3 References.......................................................................... 92
4 Global and Detailed Placement.................................95
4.1 Introduction..................................................................................... 95
4.2 Optimization Objectives ................................................................. 96
4.3 Global Placement........................................................................... 103
4.3.1 Min-Cut Placement ....................................................... 104
4.3.2 Analytic Placement ....................................................... 110
4.3.3 Simulated Annealing..................................................... 117
4.3.4 Modern Placement Algorithms ..................................... 120
4.4 Legalization and Detailed Placement ............................................ 122
Chapter 4 Exercises............................................................................. 125
Chapter 4 References.......................................................................... 126
5 Global Routing.............................................................131
5.1 Introduction..................................................................................... 131
5.2 Terminology and Definitions .......................................................... 133
5.3 Optimization Goals......................................................................... 136
5.4 Representations of Routing Regions............................................. 138
5.5 The Global Routing Flow ............................................................... 140
5.6 Single-Net Routing ......................................................................... 141
5.6.1 Rectilinear Routing........................................................ 141
5.6.2 Global Routing in a Connectivity Graph ....................... 146
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm.......... 149
5.6.4 Finding Shortest Paths with A* Search ........................ 154
5.7 Full-Netlist Routing......................................................................... 155
5.7.1 Routing by Integer Linear Programming ...................... 155
5.7.2 Rip-Up and Reroute (RRR) .......................................... 158
5.8 Modern Global Routing .................................................................. 160
5.8.1 Pattern Routing ............................................................. 161
5.8.2 Negotiated Congestion Routing.................................... 162
Chapter 5 Exercises............................................................................. 164
Chapter 5 References.......................................................................... 165
6 Detailed Routing..........................................................169
6.1 Terminology.................................................................................... 169
6.2 Horizontal and Vertical Constraint Graphs .................................... 172
6.2.1 Horizontal Constraint Graphs ....................................... 172
6.2.2 Vertical Constraint Graphs............................................ 173
6.3 Channel Routing Algorithms.......................................................... 175
6.3.1 Left-Edge Algorithm...................................................... 175
6.3.2 Dogleg Routing ............................................................. 178
6.4 Switchbox Routing ......................................................................... 180
6.4.1 Terminology .................................................................. 180
6.4.2 Switchbox Routing Algorithms...................................... 181
6.5 Over-the-Cell Routing Algorithms .................................................. 182
6.5.1 OTC Routing Methodology ........................................... 183
6.5.2 OTC Routing Algorithms............................................... 184
6.6 Modern Challenges in Detailed Routing ........................................ 185
Chapter 6 Exercises............................................................................. 187
Chapter 6 References.......................................................................... 188
7 Specialized Routing....................................................191
7.1 Introduction to Area Routing .......................................................... 191
7.2 Net Ordering in Area Routing......................................................... 193
7.3 Non-Manhattan Routing................................................................. 195
7.3.1 Octilinear Steiner Trees ................................................ 195
7.3.2 Octilinear Maze Search ................................................ 197
7.4 Basic Concepts in Clock Networks................................................ 197
7.4.1 Terminology .................................................................. 198
7.4.2 Problem Formulations for Clock-Tree Routing............. 201
7.5 Modern Clock Tree Synthesis........................................................ 203
7.5.1 Constructing Trees with Zero Global Skew.................. 203
7.5.2 Clock Tree Buffering in the Presence of Variation ....... 212
Chapter 7 Exercises............................................................................. 215
Chapter 7 References.......................................................................... 217
8 Timing Closure ............................................................221
8.1 Introduction..................................................................................... 221
8.2 Timing Analysis and Performance Constraints ............................. 223
8.2.1 Static Timing Analysis................................................... 224
8.2.2 Delay Budgeting with the Zero-Slack Algorithm........... 229
8.3 Timing-Driven Placement............................................................... 233
8.3.1 Net-Based Techniques ................................................. 234
8.3.2 Embedding STA into Linear Programs for Placement . 237
8.4 Timing-Driven Routing ................................................................... 239
8.4.1 The Bounded-Radius, Bounded-Cost Algorithm.......... 240
8.4.2 Prim-Dijkstra Tradeoff ................................................... 241
8.4.3 Minimization of Source-to-Sink Delay........................... 242
8.5 Physical Synthesis ......................................................................... 244
8.5.1 Gate Sizing.................................................................... 244
8.5.2 Buffering........................................................................ 245
8.5.3 Netlist Restructuring...................................................... 246
8.6 Performance-Driven Design Flow.................................................. 250
8.7 Conclusions.................................................................................... 258
Chapter 8 Exercises............................................................................. 260
Chapter 8 References.......................................................................... 262
A Solutions to Chapter Exercises ................................267
Chapter 2: Netlist and System Partitioning.......................................... 267
Chapter 3: Chip Planning..................................................................... 270
Chapter 4: Global and Detailed Placement ......................................... 273
Chapter 5: Global Routing.................................................................... 276
Chapter 6: Detailed Routing................................................................. 280
Chapter 7: Specialized Routing ........................................................... 284
Chapter 8: Timing Closure ................................................................... 292
B Example CMOS Cell Layouts.....................................299


Screenshot

e-books shop

Purchase Now !
Just with Paypal



Product details
 Price
 Pages
 318 p
 File Size
 24,936 KB
 File Type
 PDF format
 ISBN
 eISBN
 978-90-481-9590-9
 978-90-481-9591-6
 Copyright
 Springer Science+Business Media B.V. 2011 
  ●▬▬▬▬▬❂❂❂▬▬▬▬▬●
●▬▬❂❂▬▬●
●▬❂▬●

═════ ═════

Previous Post Next Post