This book proposes a new approach to circuit simulation that is still in its infancy. The reason for publishing this work as a monograph at this time is to quickly distribute these ideas to the research community for further study. The book is based on a doctoral dissertation undertaken at MIT between 1982 and 1985. In 1982 the author joined a research group that was applying bounding techniques to simple VLSI timing analysis models. The conviction that bounding analysis could also be successfully applied to sophisticated digital MOS circuit models led to the research presented here. Acknowledgments 'me author would like to acknowledge many helpful discussions and much support from his research group at MIT, including Lance Glasser, John Wyatt, Jr. , and Paul Penfield, Jr. Many others have also contributed to this work in some way, including Albert Ruchli, Mark Horowitz, Rich Zippel, Chtis Terman, Jacob White, Mark Matson, Bob Armstrong, Steve McCormick, Cyrus Bamji, John Wroclawski, Omar Wing, Gary Dare, Paul Bassett, and Rick LaMaire. The author would like to give special thanks to his wife, Deborra, for her support and many contributions to the presentation of this research. The author would also like to thank his parents for their encouragement, and IBM for its financial support of t,I-Jis project through a graduate fellowship. THE BOUNDING APPROACH TO VLSI CIRCUIT SIMULATION 1. INTRODUCTION The VLSI revolution of the 1970's has created a need for new circuit analysis techniques.

Test generation is one of the most difficult tasks facing the designer of complex VLSI-based digital systems. Much of this difficulty is attributable to the almost universal use in testing of low, gate-level circuit and fault models that predate integrated circuit technology. It is long been recognized that the testing prob lem can be alleviated by the use of higher-level methods in which multigate modules or cells are the primitive components in test generation; however, the development of such methods has proceeded very slowly. To be acceptable, high-level approaches should be applicable to most types of digital circuits, and should provide fault coverage comparable to that of traditional, low-level methods. The fault coverage problem has, perhaps, been the most intractable, due to continued reliance in the testing industry on the single stuck-line (SSL) fault model, which is tightly bound to the gate level of abstraction. This monograph presents a novel approach to solving the foregoing problem. It is based on the systematic use of multibit vectors rather than single bits to represent logic signals, including fault signals. A circuit is viewed as a collection of high-level components such as adders, multiplexers, and registers, interconnected by n-bit buses. To match this high-level circuit model, we introduce a high-level bus fault that, in effect, replaces a large number of SSL faults and allows them to be tested in parallel. However, by reducing the bus size from n to one, we can obtain the traditional gate-level circuit and models.

Only two decades ago most electronic circuits were designed with a slide-rule, and the designs were verified using breadboard techniques. Simulation tools were a research curiosity and in general were mistrusted by most designers and test engineers. In those days the programs were not user friendly, models were inadequate, and the algorithms were not very robust. The demand for simulation tools has been driven by the increasing complexity of integrated circuits and systems, and it has been aided by the rapid decrease in the cost of com puting that has occurred over the past several decades. Today a wide range of tools exist for analYSiS, deSign, and verification, and expert systems and synthesis tools are rapidly emerging. In this book only one aspect of the analysis and design process is examined. but it is a very important aspect that has received much attention over the years. It is the problem of accurate circuit and timing simulation.

Circuit simulation has been a topic of great interest to the integrated circuit design community for many years. It is a difficult, and interesting, problem be cause circuit simulators are very heavily used, consuming thousands of computer hours every year, and therefore the algorithms must be very efficient. In addi tion, circuit simulators are heavily relied upon, with millions of dollars being gambled on their accuracy, and therefore the algorithms must be very robust. At the University of California, Berkeley, a great deal of research has been devoted to the study of both the numerical properties and the efficient imple mentation of circuit simulation algorithms. Research efforts have led to several programs, starting with CANCER in the 1960's and the enormously successful SPICE program in the early 1970's, to MOTIS-C, SPLICE, and RELAX in the late 1970's, and finally to SPLICE2 and RELAX2 in the 1980's. Our primary goal in writing this book was to present some of the results of our current research on the application of relaxation algorithms to circuit simu lation. As we began, we realized that a large body of mathematical and exper imental results had been amassed over the past twenty years by graduate students, professors, and industry researchers working on circuit simulation. It became a secondary goal to try to find an organization of this mass of material that was mathematically rigorous, had practical relevance, and still retained the natural intuitive simplicity of the circuit simulation subject.

Circuit simulation is widely used for the design of circuits, both discrete and integrated. Device modeling is an impor tant aspect of circuit simulation since it is the link between the physical device and the sim ulate d device. Curren tly available circuit simulation programs provide a variety of built-in models. Many circuit designers use these built-in models whereas some incorporate new models in the circuit sim ulation programs. Understanding device modeling with particular emphasis on circuit simulation will be helpful in utilizing the built-in models more efficiently as well as in implementing new models. SPICE is used as a vehicle since it is the most widely used circuit sim ulation program. How ever, some issues are addressed which are not directly appli cable to SPICE but are applicable to circuit simulation in general. These discussions are useful for modifying SPICE and for understanding other simulation programs. The gen eric version 2G. 6 is used as a reference for SPICE, although numerous different versions exist with different modifications. This book describes field effect transistor models commonly used in a variety of circuit sim ulation pro grams. Understanding of the basic device physics and some familiarity with device modeling is assumed. Derivation of the model equations is not included. ( SPICE is a circuit sim ulation program available from EECS Industrial Support Office, 461 Cory Hall, University of Cali fornia, Berkeley, CA 94720. ) Acknowledgements I wish to express my gratitude to Valid Logic Systems, Inc.

Our purpose in writing this book was two-fold. First, we wanted to compile a chronology of the research in the field of mixed-mode simulation over the last ten to fifteen years. A substantial amount of work was done during this period of time but most of it was published in archival form in Masters theses and Ph. D. dissertations. Since the interest in mixed-mode simulation is growing, and a thorough review of the state-of-the-art in the area was not readily available, we thought it appropriate to publish the information in the form of a book. Secondly, we wanted to provide enough information to the reader so that a proto type mixed-mode simulator could be developed using the algorithms in this book. The SPLICE family of programs is based on the algorithms and techniques described in this book and so it can also serve as docu mentation for these programs. ACKNOWLEDGEMENTS The authors would like to dedicate this book to Prof. D. O. Peder son for inspiring this research work and for providing many years of support and encouragement The authors enjoyed many fruitful discus sions and collaborations with Jim Kleckner, Young Kim, Alberto Sangiovanni-Vincentelli, and Jacob White, and we thank them for their contributions. We also thank the countless others who participated in the research work and read early versions of this book. Lillian Beck provided many useful suggestions to improve the manuscript. Yun cheng Ju did the artwork for the illustrations.

This book contains the papers that have been presented at the ninth Very Large Scale Integrated Systems conference VLSI'97 that is organized biannually by IFIP Working Group 10.5. It took place at Hotel Serra Azul, in Gramado Brazil from 26-30 August 1997. Previous conferences have taken place in Edinburgh, Trondheim, Vancouver, Munich, Grenoble and Tokyo. The papers in this book report on all aspects of importance to the design of the current and future integrated systems. The current trend towards the realization of versatile Systems-on-a-Chip require attention of embedded hardware/software systems, dedicated ASIC hardware, sensors and actuators, mixed analog/digital design, video and image processing, low power battery operation and wireless communication. The papers as presented in Jhis book have been organized in two tracks, where one is dealing with VLSI System Design and Applications and the other presents VLSI Design Methods and CAD. The following topics are addressed: VLSI System Design and Applications Track • VLSI for Video and Image Processing. • Microsystem and Mixed-mode design. • Communication And Memory System Design • Cow-voltage & Low-power Analog Circuits. • High Speed Circuit Techniques • Application Specific DSP Architectures. VLSI Design Methods and CAD Track • Specification and Simulation at System Level. • Synthesis and Technology Mapping. • CAD Techniques for Low-Power Design. • Physical Design Issues in Sub-micron Technologies. • Architectural Design and Synthesis. • Testing in Complex Mixed Analog and Digital Systems.