Algorithmic And Knowledge Based Cad For Vlsi

Samples the present state-of-the-art in CAD for VLSI, covering both newly developed algorithms and applications of techniques from the artificial intelligence community. The material is based on a tutorial course run in conjunction with the 1991 European Conference on Circuit Theory and Design, and should interest engineers involved in the design and testing of integrated circuits and systems. Annotation copyrighted by Book News, Inc., Portland, OR

This book, and the research it describes, resulted from a simple observation we made sometime in 1986. Put simply, we noticed that many VLSI design tools looked "alike". That is, at least at the overall software architecture level, the algorithms and data structures required to solve problem X looked much like those required to solve problem X'. Unfortunately, this resemblance is often of little help in actually writing the software for problem X' given the software for problem X. In the VLSI CAD world, technology changes rapidly enough that design software must continually strive to keep up. And of course, VLSI design software, and engineering design software in general, is often exquisitely sensitive to some aspects of the domain (technology) in which it operates. Modest changes in functionality have an unfortunate tendency to require substantial (and time-consuming) internal software modifications. Now, observing that large engineering software systems are technology dependent is not particularly clever. However, we believe that our approach to xiv Preface dealing with this problem took an interesting new direction. We chose to investigate the extent to which automatic programming ideas cold be used to synthesize such software systems from high-level specifications. This book is one of the results of that effort.

Modern microprocessors such as Intel's Pentium chip typically contain many millions of transistors. They are known generically as Very Large-Scale Integrated (VLSI) systems, and their sheer scale and complexity has necessitated the development of CAD tools to automate their design. This book focuses on the algorithms which are the building blocks of the design automation software which generates the layout of VLSI circuits. Courses on this area are typically elective courses taken at senior undergrad or graduate level by students of Electrical and Electronic Engineering, and sometimes in Computer Science, or Computer Engineering.

To fully exploit VLSI technology, future CAD tools need to perform a high proportion of the intelligent decision-making necessary for design. It is imperative that these tasks be massively automated so that the intellectual load on the human designer is reduced, allowing a more efficient use of his time and creative abilities. This book investigates the applicability of knowledge-based techniques to the problems of VLSI design. Topics covered include: an overview of knowledge-based techniques; a description of work illustrating the application of these techniques to various VLSI design tasks; and a survey of workstations and software available for constructing knowledge-based systems. Although much of the material in this book has been illustrated using examples from microelectronic CAD, the issues and techniques have been presented in such a way as to make them useful to managers, designers and researchers who wish to learn of the advantages of knowledge-based techniques in practical applications.

Practical Problems in VLSI Physical Design Automation contains problems and solutions related to various well-known algorithms used in VLSI physical design automation. Dr. Lim believes that the best way to learn new algorithms is to walk through a small example by hand. This knowledge will greatly help understand, analyze, and improve some of the well-known algorithms. The author has designed and taught a graduate-level course on physical CAD for VLSI at Georgia Tech. Over the years he has written his homework with such a focus and has maintained typeset version of the solutions.