Fundamental CAD algorithms

Computer-aided design (CAD) tools are now making it possible to automate ma ny aspects of the design process. This has mainly been made possible by the use of effective and efficient algorithms and corresponding software struc tures. The very large scale integration (VLSI) design process is extremely complex, and even after breaking the entire process into several conceptual ly easier steps, it has been shown that each step is still computationally hard. To researchers, the goal of understanding the fundamental structure o f the problem is often as important as producing a solution of immediate ap plicability. Despite this emphasis, it turns out that results that might fi rst appear to be only of theoretical value are sometimes of profound releva nce to practical problems. VLSI CAD is a dynamic area where problem definitions are continually changi ng due to complexity, technology and design methodology. In this paper, we focus on several of the fundamental CAD abstractions, models, concepts and algorithms that have had a significant impact on this field. This material should be of great value to researchers interested in entering these areas of research, since it will allow them to quickly focus on much of the key m aterial in our field. We emphasize algorithms in the area of test, physical design, logic synthesis, and formal verification. These algorithms are res ponsible for the effectiveness and efficiency of a variety of CAD tools. Fu rthermore, a number of these algorithms have found applications in many oth er domains.