Algorithms for VLSI Design Automation [Hardcover]

The book is targeted to students of electrical engineering in the first place. It only assumes an elementary knowledge of programming and some familiarity with digital IC design. However, the necessary knowledge of IC design is quite minimal and students of computer science or applied mathematics should perfectly be able to follow the text after reading the appendix that explains the very basics of CMOS technology. The book is also interesting for computer scientists and applied mathematicians as it shows the many applications of combinatorial optimization within the field of VLSI design automation.

After studying this book, the students should be sufficiently familiar with the notions and terminology of the field and be able to understand more specialized books and articles on their own. It is recommended that the study of the book is supplemented with programming exercises such that the student will not only understand typical CAD algorithms but be able to implement them efficiently as well.

The book consists of two groups of chapters and a group of appendices. The first group of chapters consists of introductions to "VLSI design" and "CAD tools", followed by introductions to the mathematical topics of "algorithmic graph theory", "computational complexity", "intractability" and "general methods for combinatorial optimization". The mathematical introductions have been included because many students of electrical engineering may not be familiar with them.

The second group of chapters presents a selection of CAD problems and algorithms to solve them. Although attention is paid to simulation, logic synthesis, high-level synthesis, and several aspects of layout design, the wide range of VLSI design automation tools is only partially covered by these chapters. The reason for this is that the author considers it more important to achieve some depth in a limited number of topics rather than to have a shallow coverage of many topics. Besides, a more complete but superficial presentation of all tools is given in Chapter 2 entitled "A Quick Tour of VLSI Design Automation Tools". Another reason for not attempting to cover a wide range of tools and algorithms is that research in the field continually moves its focus of attention to new topics. The material presented in this book sufficiently prepares the reader for the study of other texts dealing with VLSI design automation. Many pointers for further reading can be found in the "Bibliographic Notes" sections at the end of each chapter.

Apart from the the first appendix on the basics of CMOS technology mentioned earlier, there is an appendix that presents the language that is used in the book for the specification of algorithms in pseudo-code. The language is based on C with some extensions to write compact pseudo-code. The last appendix lists all acronyms used in this book.

Algorithms are the central theme of this book and the book presents many of them. Most of the algorithms are illustrated by means of small examples to make it easier to understand them. The algorithms in this book should not be considered recipes that can directly be applied. The goal of the book is rather to train the student in thinking about algorithms related to the field. -- The Author