Algorithms for VLSI Physical Design AutomationAlgorithms for VLSI Physical Design Automation, Third Edition covers all aspects of physical design. The book is a core reference for graduate students and CAD professionals. For students, concepts and algorithms are presented in an intuitive manner. For CAD professionals, the material presents a balance of theory and practice. An extensive bibliography is provided which is useful for finding advanced material on a topic. At the end of each chapter, exercises are provided, which range in complexity from simple to research level. Algorithms for VLSI Physical Design Automation, Third Edition provides a comprehensive background in the principles and algorithms of VLSI physical design. The goal of this book is to serve as a basis for the development of introductory-level graduate courses in VLSI physical design automation. It provides self-contained material for teaching and learning algorithms of physical design. All algorithms which are considered basic have been included, and are presented in an intuitive manner. Yet, at the same time, enough detail is provided so that readers can actually implement the algorithms given in the text and use them. The first three chapters provide the background material, while the focus of each chapter of the rest of the book is on each phase of the physical design cycle. In addition, newer topics such as physical design automation of FPGAs and MCMs have been included. The basic purpose of the third edition is to investigate the new challenges presented by interconnect and process innovations. In 1995 when the second edition of this book was prepared, a six-layer process and 15 million transistor microprocessors were in advanced stages of design. In 1998, six metal process and 20 million transistor designs are in production. Two new chapters have been added and new material has been included in almost allother chapters. A new chapter on process innovation and its impact on physical design has been added. Another focus of the third edition is to promote use of the Internet as a resource, so wherever possible URLs have been provided for further investigation. Algorithms for VLSI Physical Design Automation, Third Edition is an important core reference work for professionals as well as an advanced level textbook for students. |
Contents
| 1 | |
3 | 87 |
Data Structures and Basic Algorithms | 96 |
Partitioning | 157 |
Floorplanning and Pin Assignment | 191 |
Placement | 219 |
Global Routing | 247 |
Detailed Routing 9 1 Problem Formulation 291 | 291 |
OvertheCell Routing and Via Minimization | 369 |
2 2 Unconstrained Via Minimization 10 2 2 1 10 2 2 2 10 2 2 3 Optimal Algorithm for CrossingChannel TVM Problem Approximation Result for G... | 403 |
lem Routing Based on Topological Solution 10 3 10 4 Summary Exercises 11 Clock and Power Routing 11 1 Clock Routing 11 1 1 11 1 2 Clocking ... | 409 |
Compaction 12 1 Problem Formulation 449 | 449 |
| 525 | |
| 528 | |
| 562 | |
| 569 | |
Other editions - View all
Common terms and phrases
antifuses approach boundary capacitance channel height channel routing problem chip circle graphs circuit clock routing column compaction complete components computed connected constraint graph cost data structure delay denote density design automation design rules design style discussed doglegs edge fabrication floorplan FPGAs gate array given global routing graph G grid grid graph high performance horizontal input integer program interconnect intersection interval graph iteration layout logic block maximum independent set maze routing metal layers method minimize minimum modules node NP-complete NP-hard number of nets number of tracks over-the-cell routing partitioning problem path permutation graph phase physical design pin assignment placement algorithms placement problem planar rectangles rectilinear Steiner tree reduce result router routing algorithm routing region shown in Figure simulated annealing skew standard cell standard cell design Steiner tree switchbox techniques terminals tile total number transistors vacant vertex vertical constraint VLSI weight width wire length wire segments