A net list is a hierarchy of instantiated devices connected by nets. Some devices are primitive, while others are compositions eventually built using primitive devices. Net lists may be annotated with arbitrary properties such as name, transistor size, and net capacitance.

A net list generator is a function that takes parameters such as integers, geometrical objects, net lists, or other functions, and returns a net list. The function is represented concretely either by code that will be executed, or a schematic that will be interpreted, that is extracted. When a net list generator is evaluated, it either returns a primitive device, or it merges the results of subsidiary net list generators into a net list and returns it. Thus, the evaluation of a single net list generator may entail many levels of schematic extraction and/or code execution, possibly interleaved. Code and schematics are tightly linked, and the linkage works both ways.

A schematic is a hierarchy of instantiated graphical objects composed of rectangles, icons, satellites, and compositions. Each instance of these graphical objects has a procedure, the extract method, that knows how to convert the instance into a net list. This extract method provides the link from geometry to code. User code can call the extractor thus providing the code to geometry link.

Rectangles usually become nets, with touching rectangles inside a composition forming a single net. An icon is a graphical abstraction of a net list. Typically, it has some named rectangles to which connections are made, and some arbitrary pictorial geometry that denotes its function. Satellites are textual expressions attached to one of the non-text objects or its instance. The entity to which a satellite is attached is called its master. Satellites are evaluated during schematic extraction and serve principally to pass parameters to their master's extract method. Figure 2.2.1(a) shows an icon whose net list happens to be represented by a simple schematic. The schematic is a composition that contains transistor icons, an inverter icon, the rectangles that connect them, and satellites that serve to name nets and specify transistor sizes. Figure 2.2.1(b) shows how complicated functions can be represented graphically.

Our model of schematics is analgous to a program in a dynamically-scoped block-structured programming language. Icon instances are analogous to procedure calls, compositions to blocks, and satellites to variable declaration and variable assignment. Variables declared and/or assigned to in satellites have scopes determined by the geometric and icon hierarchies, analogous to scopes determined by the dynamic nesting of blocks and procedures.

Net lists are the output of net list generators. This output is represented using the data types, property, wire, cell type, and cell class [2]. These basic types allow an extensible set of abstractions to be defined that can represent a design at any desired level of detail. Extensibility derives from the ability to define new cell classes without affecting the code for those that already exist. This is achieved with a mechanism similiar to the Common Lisp [11] macro expansion facility.

The property data type represents an annotation consisting of a <key, value> pair. A property may be attached to a wire, a cell type, a cell class, or another property.

A wire represents a collection of nets. An atomic wire represents a single net, while a structured wire represents a collection that is organized hierarchically for convenience. A structured wire and its subwires form a directed acyclic graph whose leaves correspond to atomic wires.

A cell type represents a device. Cell types consist of an interface and implementation data. The interface contains some properties and a public wire that specifies how an instance of this cell type is to be connected to other cell types.

A cell class groups the implementations of different cell types into sets with common characteristics. Some cell classes are primitive, while others are composite. The primitive cell classes are used to encode the structural leaves of a net list; in MOS design these leaves are transistors. There is also a special primitive cell class, unspecified, that allows a cell type to have its interface defined while leaving its implementation unspecified. Composite cell classes describe how cell types may be combined to form more complex cell types. One composite cell class is well known. All others must expand into this well known class.

The system provides a complete set of utilities to create and manipulate net lists by program. These utilities consist of modules for creating cell types and wires with specification of interconnections by name. Figure 3.2.1 illustrates the use of these utilities. It constructs a decoder with an arbitrary number of inputs.

Although this approach of providing creation utilities for textual specification is more verbose than a specification based on a hardware description language, it has some advantages. It avoids a separate language for hardware design, so it is easier to implement. It fits an evolutionary system development style better since utilities may be added and improved piecemeal. This is much harder to do in a language based system once the language is fixed.

The task of the schematic extractor is to convert a combination of pictures and code into a net list. As outlined earlier, the extractor proceeds top-down in a recursive manner starting at the instance to be extracted. Each recursion computes the net list for some icon or composition instance in two steps. The first evaluates satellites associated with the instance, while the second passes the context containing the new evaluations to the instance's extract method. To speed up extraction for incremental changes, the extractor caches results on objects. Before extracting an instance, it checks whether the result, if any, cached on that instance's object is still valid. If it is, this result is returned, otherwise the instance is reextracted.

The context is central to the first step. Included in it are variables defined at higher levels in the recursion, as well as certain procedures and global variables accessible in the extractor's run time environment. To facilitate evaluation, the extractor maintains contexts in a stack, one frame per pending recursion level.

Satellite evaluation itself proceeds in two phases. Satellites bound to the instance's object are evaluated first, while those bound to the instance are evaluated second. This order allows defaults to be specified by object satellites and overridden by instance satellites. Table 3.3.1 provides examples of satellites.

Net list construction for an instance is performed by its extract method. The extract method proceeds differently for an icon which is associated with a schematic or a user-defined procedure. In the former case the method invokes the extractor on the schematic. In the latter it simply calls the user-defined procedure. In either case, the method subsequently checks that the interface of the result net list conforms with the interface of the icon. The result of extracting an icon is either a cell type that is instantiated within the parent composition, or a wire that is used to make one or more connections.

The extract method for compositions is considerably more complex because it is here that most of the geometric work of extraction takes place. For each icon or subcomposition instance that it encounters the method recursively invokes the extractor and then instantiates the result within the cell type it is constructing. When instantiating a cell type the method determines how the cell instance is to be connected to other nets based on intersecting rectangles, that represent connection points on the instance, with rectangles in the parent composition. When the method encounters a rectangle instance it creates a new wire and merges it with an existing wire if rectangle intersection indicates the two wires are connected. The geometrical engine used for this purpose is the same as for layout, since much of the code can be shared. In schematics and layout it is convenient to specify connectivity based on name equality as well as geometrical intersection, so the method also merges together wires with the same name.

Each net list generated by the extractor is annotated with all the graphical objects which were part of its schematic. These annotations establish a link between a wire and its rectangles, or a cell and its corresponding graphical object. Tools that require the specification of a wire can ask the user to select a rectangle with the graphical editor by pointing to it with the mouse. Similarly, tools that specify a wire or a cell as output, e.g. when an error occurs, highlight the corresponding rectangles or cells. This approach, analogous to symbolic debugging of source code avoids tedious names. It is extremely effective for reducing the extraction-simulation-debug loop. It allows the implementation of a command that adds a selected wire to the waveform display of the logic simulator.

Some of the net list annotations are interpreted by a silicon assembler which does a walk of the net list hierarchy. At each level it uses the value of a distinguished annotation to select a procedure which recovers its parameters from further annotations, including the positions of graphical objects in the schematics. The procedure generates the layout and adds annotations which link the layout to the original net list.

Figure 4.1.1 shows a highly idealized view of the design cycle of a VLSI chip. The bold boxes indicate stages that use the design capture system.

Often, a significant fraction of the overall design time is spent in debugging a description once it has been entered into the system (stages 3 and 5 in the figure), so it is useful to examine debugging more closely as shown in figure 4.1.2 This process closely resembles the load-run-think-modify-compile cycle so familiar to programmers. As with programs one would ideally like a system in which most of the time around the loop is spent in the thinking needed to find a problem (stage C).

Table 4.2.1 shows the layout methods and development times for chips that have been designed using the system (the parenthesized numbers in column headers refer to steps in the design cycle). The figures in the table are subjective measures obtained by interviewing designers, and as such are only approximate. The layout methods vary all the way from program generated, through standard cell, to full custom (FC), while the design times range from a day to over two years. About half have been fabricated and tested. The remainder have just finished the layout production and verification stage. A figure that helps puts the design capture system in proper perspective is the fraction of time spent in design capture/debugging over the entire design cycle. For our sample, this figure ranges from ~20% to ~75%, with the average being close to 50%. This indicates that further improvements in the design capture system would have a significant impact on the overall design time.

Table 4.2.2 shows various size statistics for the 12 chips. The area and transistor counts indicate that several of the chips are moderate to large by today's standards, and constitute a serious test of the design system. The schematic and code sizes show that while most of the descriptions are dominated by schematics, sizable fractions of a few descriptions are in code, and most utilize some code.

Finally, Table 4.2.3 provides data that helps give a feel for the time around the debug loop (the parenthesized letters in column headers refer to stages in the debug loop). The first column gives the time to produce a net list from scratch, while the second gives the same time after a "typical" change made during debugging. The next two columns indicate the time to initialize a simulation, and the number of clock cycles of the chip simulated per minute once the simulation has been initialized. These numbers are for complete chips rather than for chip subblocks.

Parameterized schematics work well but greatly increase the complexity of the system.

The chief benefit is the reuse of design information in multiple contexts. Parameterization also allows designers to delay decisions such as the number of lines in a processor cache, the number of bits per line, and even the number of bits in a data path. Delaying these decisions allows detailed architectural decisions, such as cache capacity, to proceed in parallel with the description. Designers can debug their designs with the smallest feasible sizes and expect with very high confidence that the full-size version also works. For chip C3 this technique changes the time around the debug loop by an order of magnitude.

Generating net lists incrementally is considerably harder because determining what changed and what did not is more difficult. Parameterization also makes it more difficult to implement commands that use connectivity, e.g. a command to highlight a net, because this information is only available after a parameter dependent extraction and cannot be derived simply from the geometry.

Our decision to build an extensible system has also worked out well. The extensibility of the model has made the addition of, and experimentation with, new graphical modes of expression very easy. The object oriented model used in the extractor implementation is an advantage for the CAD programmer who maintains the system since it results in a simple structure. It is also beneficial for the VLSI designer because it keeps the mental model of the extractor quite simple. Several powerful operators such as one and two dimensional sequencers, a data path generator, a finite automaton generator, and a rich set of wire structure manipulators have been added to the system since its design.

The schematic extractor and the layout extractor use a common geometry engine. The sophisticated rectangle intersection algorithms of a layout extractor are required since schematics can be quite large.

The connection of graphics to code utilizes an interpreter for the local programming language. This use of the interpreter provides great flexibility since it allows general expressions to be used directly within schematics. Variables referenced in these expressions can be variables in the context or in the load state of the machine, providing direct graphical access to any program running on the machine. Along with this flexibility also comes a speed liability. About half of the extraction time is spent in the interpreter because every time a schematic is reextracted expressions have to be reparsed and reevaluated.

In our object oriented model the order in which instances are extracted cannot be controlled. This causes the same information to be specified more often than is strictly necessary. For example when we select a component wire from a bus the size of the bus must be specified within each selector because there is no way to guarantee that the bus size is known when the extractor encounters a particular selector.

From table 4.2.3 is clear that the system's speed is not really adequate to debug large designs in an interactive manner. Extraction and simulation initialization should be an order of magnitude faster to be compatible with the time spent thinking. Caching already buys a factor of about 4 over extraction from scratch, but as can be seen from the figures for C2, C8 and C11, the gains are sometimes considerably less. The current implementation, which caches results on geometric objects, is inadequate in two respects. First, if a design description is relatively flat (the case with C2), then the system has to redo most of the work. Secondly, if a description uses code to describe a piece of the design (the case with C8 and C11), then this piece is always recomputed even if doesn't need to be. Improving incremental extraction is only part of the problem, however, since simulation initialization also accounts for a significant fraction of the time. Moreover, our system currently does not have a way to do the initialization incrementally so the gains to be had are large.

When we started building the system we had a high quality layout editor available to us. This left us free to implement higher levels of the design capture system. The editor had some drawbacks, particularly with regard to displaying annotations. It is useful to provide designers the option of hiding information to avoid clutter. However, it is extremely awkward if the system requires all information to be hidden. Our editor imposed this constraint and so we implemented satellites that can be made visible or not and whose position and looks are controlled by the designer.

The editor does not impose any semantics on geometry and so the same editor can be used for both layout and schematics. This is a hindrance because we reintersect rectangles each time an object is extracted. The slow down caused by reintersection is ameliorated somewhat by result caching. The editor's lack of schematic syntax knowledge makes syntatic errors difficult to detect interactively. The extractor finds some syntatic errors and a separate checker weeds out the rest.

The design of operators that succinctly express the structure of VLSI is a difficult task, especially within our simple bottom up construction model. We do not yet have a common set of operators for all our designs because extending the operator set is a tedious cut and try process which is best done in the context of many real designs.

The cell sequence operator has received a great deal of attention but we have yet to find an expression of sequence that covers the frequent tilings of a two dimensional plane and combines power with conceptual simplicity. Decoders are obvious examples of such tilings. The wiring between cells, aggregation of wires into buses, and cell index dependence are just a few of the issues which must be considered.

When we designed the computation model we decided not to consider the frequent updates that occur during debugging. For instance the model allows arbitrary side effects to occur within procedures called during extraction. We have added manual specification of procedure arguments and a cache mechanism so that a procedure need not be reexecuted every time it is called but really fixing this defect requires a new computation model.

The greatest limitation to extraction speed is the interpreter, closely followed by rectangle intersection. The rectangles that make up the picture always intersect the same way even when the parameters of a cell are changed. Another intermediate representation to avoid rectangle reintersection and enhancing the interpreter to decouple parsing from evaluation could improve the speed by a factor of two to ten.

Even with the existence of satellites there is some information that guides the extraction process that is always hidden. This is because the concept of satellites appeared after the editor was written and so is not well integrated. A better way to allow users to control the display of useful information is to add properties that have user-definable display procedures.

Our current computation model is batch oriented. Whenever a new net list is built, the top level net list generation function is called to do so. There is caching that makes this process partially incremental, but the model is still one of complete reexecution of the generation function. An alternative is to change the contents of the net list incrementally when the net list generator is changed. In the current model every cell can be an arbitrary function of its subcells. Thus every cell type, starting from the one that is changed, all the way to the root cell type must be rebuilt. It is frequently the case that a change in a low level cell type does not really require changes all the way to the root. Differentiating the portions of the net list that need to be changed from those that do not requires a fundamentally different computation model.

A much more restricted functional model of evaluation would facilitate the definition of such a model and make it easier to construct an incremental system. The chief benefit of such a system is its interactive nature.

A schematic specific editor, rather than a general purpose editor followed by an extractor, would allow more effective capture and user feedback mechanisms. The decision to use an existing editor and translate afterwards was sound because we have sorted out many thorny semantic issues but we need to revisit this decision.

We would like to integrate representation specific editors into a single editor framework. Currently, the granularity at which we can intermix information is whole documents. We need to reduce this granularity so we can have a single document that allows us to freely mix commentary, code, schematics, layout, timing diagrams, and other information.