Net lists are represented using the four data types, property, wire, cell type, and cell class [2]. These basic types permit the definition of an extensible set of abstractions that can represent a design at any desired level of detail. This extensibility derives from the ability to define new cell classes without affecting the code for those that already exist.

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. Only the atomic wires represent actual nets, the others simply provide structure.

A cell type represents a device. Cell types consist of an interface and some implementation data. The interface contains properties along with a public wire that specifies how an instance of this cell type is to be connected to other cell types. The implementation data contains the cell type's cell class and class-specific data. A cell instance represents an instantiation of a cell type within a net list.

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 be able to expand into this well known class.

The system provides a complete set of utilities to help create and manipulate annotated net lists by program. These utilities consist of modules for creating cell types and wires layered on top of more primitive creation functions. Figure 3.2.1 illustrates the use of these utilities to construct a decoder with n 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 two major advantages. It avoids a separate language for hardware design, so it is easier to implement. It also 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 schematic extractor converts a combination of pictures and code into a net list. It proceeds top-down in a recursive fashion 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 invokes the instance's extract method. The parameters passed to the method include the set of variable definitions visible in the current scope, the context, in effect immediately after satellite evaluation. 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. A new context is created by copying variable definitions from the existing stack top and then evaluating satellites in the new context. These copy semantics ensure that simple use of the context during extraction is side-effect-free.

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 a summary of satellite usage. Note that net list annotations may be specified directly via satellites.

The actual net list computation for an instance is performed by its extract method. For icons, the extract method proceeds differently depending on whether the icon 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 it encounters, the method recursively invokes the extractor and then instantiates the result within the cell type it is constructing. For icons, this result is a cell type or a wire, but for compositions it is always a cell type. 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.

This brings us to the other major task of the method, rectangle intersection to compute connectivity. When the method encounters a rectangle, 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 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.

In addition to processing annotations placed via satellites, the extractor annotates its result net list with all the graphical objects that were part of the net list's schematic. These graphical annotations establish a link between a wire and its rectangles, and a cell and its corresponding graphical object. Tools that need a wire as input can ask the user to designate a rectangle by pointing to it with the mouse. For example, signal waveforms are displayed this way during simulation. Similarly, tools that specify a wire or a cell as output can highlight the corresponding cells or rectangles. Analogous to symbolic debugging of source code, this approach permits real time interaction and has proven extremely effective in reducing the time around the extract-simulate-debug loop.

Some of the net list annotations are interpreted by a silicon assembler that does a walk of the net list hierarchy. At each level the assembler uses the value of a distinguished annotation to select a layout method. The method recovers its parameters from further annotations, including the positions of graphical objects in the schematics. It then generates layout and adds annotations that link the layout to the original net list. For example, the annotation <Layout:AbutX> on a cell type selects the AbutX method, which computes the layout of the cell type by abutting the layouts of the cell type's instances in the X direction.

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. The detailed specification stage involves paper design and/or high-level simulation. Upon its completion, the designer has a specification detailed enough to enter pieces of his design into the system. The design of a real chip rarely follows the clean cut path shown. More frequently, there is overlap between stages, the design involves more than just a two level description hierarchy, and the order of stages is hard to determine. Nevertheless, this figure provides us with a useful basis for discussion by identifying significant tasks involving the design capture system.

Often, a major portion 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. And, as with programs, ideally one would 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 approximate. The layout methodology varies 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 the chips have been fabricated and tested, and the remainder are just entering 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 improvements to the design capture system would have a significant impact on the overall design time.

Table 4.2.2 shows various size statistics for the same chips. The area and transistor counts indicate that several of the chips are moderate to large by today's standards, and so 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 set up a simulation and the number of clock cycles of the chip simulated per minute once the simulation is under way. We should emphasize that these numbers are for complete chips rather than for chip subblocks.

Our provision of parameterized schematics has worked well. Parameterization allowed our 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. Designers can therefore debug their designs with the smallest feasible sizes, and expect the full-size version to work with high confidence. For chip C3, for example, this technique changed the time around the debug loop by an order of magnitude (the time shown is after reduction). Delaying size decisions had the additional benefit of allowing analysis to proceed in parallel with description, potentially speeding up the schedule.

Parameterized schematics also permit us to annotate schematics to describe how layout is to be produced by a layout generator. Typical industry practice consists of describing the layout via a floor plan that is independent of the schematic (the floor plan describes the placement while the schematic specifies the connectivity). We have successfully linked net list and layout generators so that designers' schematics drive layout synthesis.

Parameterization did, however, complicate implementation. Generating net lists incrementally is considerably harder because determining what changed and what didn't is more difficult. Parameterization also made it more difficult to implement commands that use connectivity (for example the command to highlight a whole net) because this information is only available after a parameter dependent extraction and cannot be derived from the geometry alone.

Our decision to build an extensible system has also worked out well. The object oriented model used in the extractor's implementation is an advantage for the CAD programmer who maintains the system since it results in a simple structure. It is also beneficial to the VLSI designer because it kept his mental model of the extractor simple.

The extensibility of this model has made the addition of, and experimentation with, new graphical modes of expression very easy. It freed us from having to write a large number of graphical primitives before the system became useful. It allowed these primitives to be added on demand, and provided freedom to experiment with several alternatives before picking one. Because of this extensiblity we have been able to build 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. Thus far a unified sequence operator that is general enough to handle all the applications at hand has eluded us. We encountered surprising difficulty both in defining semantics and in implementation.

The schematics extractor and the layout extractor use a common geometry engine. This may seem strange because layout extraction is context independent while schematic extraction is strongly context dependent. As it turns out, it is useful to do layout in a context dependent manner because it enables neighbor overlaps to either be considered or not and it allows net list construction to depend on the names of wires rather than just on geometric features. On the other hand, layout extractors have fairly sophisticated rectangle intersection algorithms which may appear to be overkill for schematic extraction. In our experience sophistication is required since some schematics are quite large. The use of a common geometry engine is also valuable from a system structuring standpoint because it avoids redoing a substantial amount of intricate code.

The connection of graphics to code utilizes an interpreter for the local programming language. This provides great flexibility, since it allows general expressions to be used directly within schematics; variables in these expressions can be either variables in the context or in the load state of the machine, thereby providing direct graphical access to any program running on the machine. Along with this flexibility also came a speed liability. About half the time for extraction is spent in the interpreter because every time a schematic is reextracted expressions are 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 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 it is clear that the system's speed is not really adequate to debug large designs in an interactive manner. Extraction and simulation set up should be an order of magnitude faster to be compatible with the time spent thinking. Caching already buys a factor of around 4 over extraction from scratch, but as the figures for C2, C8 and C11 show, 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. Second, 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 setup also accounts for a significant fraction of the time. Moreover, our system currently does not have a way to do the set up incrementally so the gains to be had are large.

In our first implementation we used syntax to divide satellites into parameter expressions and result expressions. Parameter expressions computed values for parameters, while result expressions called the extract method for the instance being extracted. This approach was unsatisfactory because it requred satellite syntax to be embellished each time we added a new object class. It was also inefficient because the interpreter was invoked unnecessarily in calling the extract method. Our second attempt eliminates result expressions and has hidden properties from which the extract method can be inferred. This solution is not satisfactory either because it does not allow the extract method information to be easily seen. At least part of our trouble here is the use of an existing editor.

When we started building the system we had a high quality layout editor available to us. In one respect this was a big plus because it left us free to implement higher levels of the design capture system. In other respects, however, the editor had drawbacks, particularly with regard to displaying annotations. For example, we found it useful to provide designers the option of making information visible for emphasis or invisible to avoid clutter. However, our editor required all information to be hidden, forcing us to implement satellites, or properties that could be made visible or not and whose position and looks could be 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, at the same time, a hindrance because we have to reintersect rectangles each time an object is extracted. The slow down caused by reintersection is ameliorated somewhat by result caching but, as we noted earlier, caching does not work as well as we would like. The editor's lack of knowledge about schematic syntax makes syntatic errors difficult to detect interactively. The extractor finds out some of these errors and a separate checker weeds out the rest.

When we designed the computational 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. Really fixing this defect requires fundamental changes to the system. Most importantly, the underlying programming language needs to be modified to allow only side-effect-free procedures.

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. Maintaining an 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 information that guides the extraction process that is always hidden. This is because the concept of satellites appeared after the editor was written, and, as such, is not well integrated. A better way to allow users to control the display of useful information would be 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. One alternative is to change the contents of the net list incrementally when the net list generator is changed. In our model, every cell can be an arbitrary function of the subcells. Thus, every cell type, starting from the one that is changed all the way to the root cell type, must be rebuilt. Frequently, 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 computational 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 would be its interactive nature.

A schematic specific editor, rather than a general purpose editor followed by an extractor, would allow more effective capture and 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 now 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.