Networks are pervasive. Very large scale integrated (VLSI) systems are no different, consisting of dozens of interconnected subsystems, hundreds of modules, and many billions of transistors and wires. Graph theory is crucial for managing and analyzing these systems. In this book, VLSI system design is discussed from the perspective of graph theory. Starting from theoretical foundations, the authors uncover the link connecting pure mathematics with practical product development. This book not only provides a review of established graph theoretic practices, but also discusses the latest advancements in graph theory driving modern VLSI technologies, covering a wide range of design issues such as synchronization, power network models and analysis, and interconnect routing and synthesis. Provides a practical introduction to graph theory in the context of VLSI systems engineering; Reviews comprehensively graph theoretic methods and algorithms commonly used during VLSI product development process; Includes a review of novel graph theoretic methods and algorithms for VLSI system design.

Design and optimization of integrated circuits are essential to the creation of new semiconductor chips, and physical optimizations are becoming 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. "VLSI Physical Design: From Graph Partitioning to Timing Closure" introduces and compares algorithms that are used during the physical design phase of integrated-circuit design, 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.

One of the main problems in chip design is the enormous number of possible combinations of individual chip elements within a system, and the problem of their compatibility. The recent application of data structures, efficient algorithms, and ordered binary decision diagrams (OBDDs) has proven vital in designing the computer chips of tomorrow. This book provides an introduction to the foundations of this interdisciplinary research area, emphasizing its applications in computer aided circuit design.

This monograph represents a summary of our work in the last two years in applying the method of simulated annealing to the solution of problems that arise in the physical design of VLSI circuits. Our study is experimental in nature, in that we are con cerned with issues such as solution representations, neighborhood structures, cost functions, approximation schemes, and so on, in order to obtain good design results in a reasonable amount of com putation time. We hope that our experiences with the techniques we employed, some of which indeed bear certain similarities for different problems, could be useful as hints and guides for other researchers in applying the method to the solution of other prob lems. Work reported in this monograph was partially supported by the National Science Foundation under grant MIP 87-03273, by the Semiconductor Research Corporation under contract 87-DP- 109, by a grant from the General Electric Company, and by a grant from the Sandia Laboratories.

Symbolic Boolean manipulation using binary decision diagrams (BDDs) has been successfully applied to a wide variety of tasks, particularly in very large scale integration (VLSI) computer-aided design (CAD). The concept of decision graphs as an abstract representation of Boolean functions dates back to the early work by Lee and Akers. In the last ten years, BDDs have found widespread use as a concrete data structure for symbolic Boolean manipulation. With BDDs, functions can be constructed, manipulated, and compared by simple and efficient graph algorithms. Since Boolean functions can represent not just digital circuit functions, but also such mathematical domains as sets and relations, a wide variety of CAD problems can be solved using BDDs. `Binary Decision Diagrams and Applications for VLSI CAD provides valuable information for both those who are new to BDDs as well as to long time aficionados.' -from the Foreword by Randal E. Bryant. `Over the past ten years ... BDDs have attracted the attention of many researchers because of their suitability for representing Boolean functions. They are now widely used in many practical VLSI CAD systems. ... this book can serve as an introduction to BDD techniques and ... it presents several new ideas on BDDs and their applications. ... many computer scientists and engineers will be interested in this book since Boolean function manipulation is a fundamental technique not only in digital system design but also in exploring various problems in computer science.' - from the Preface by Shin-ichi Minato.

In the past two decades, research in VLSI physical design has been directed toward automation of layout process. Since the cost of fabricating a circuit is a fast growing function of the circuit area, circuit layout techniques are developed with an aim to produce layouts with small areas. Other criteria of optimality such as delay and via minimization need to be taken into consideration. This book includes 14 articles that deal with various stages of the VLSI layout problem. It covers topics including partitioning, floorplanning, placement, global routing, detailed routing and layout verification. Some of the chapters are review articles, giving the state-of-the-art of the problems related to timing driven placement, global and detailed routing, and circuit partitioning. The rest of the book contains research articles, giving recent findings of new approaches to the above-mentioned problems. They are all written by leading experts in the field. This book will serve as good references for both researchers and professionals who work in this field.

The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.