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 arbitrary parameters (integers, geometrical objects, net lists, or other functions, for example) and returns a net list when evaluated. The function is represented concretely either by code that will be executed, or a schematic that will be interpreted, or 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, called the instance's extract method, that knows how to interpret it in terms of a net list. It is this extract method that provides the link from geometry to code. The reverse link is provided simply by making the extractor available as a function that can be called from user code.

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 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. More complex examples appear in the appendix.

Our model of schematic extraction can be described best by capitalizing on the close analogy between a schematic and 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. Schematic extraction, then, is analogous to interpreting a program in the above language.

It follows that extraction is a recursive process in which each step computes the net list for some icon or composition instance. This step breaks down into two parts, the first of which evaluates the satellites associated with the instance, and the second of which invokes the instance's extract method. The parameters passed to this method include the set of variable definitions visible in this scope, the context, in effect immediately after satellite evaluation. This context is computed by applying the results of satellite evaluation to the old context, the application being side-effect free in that the old context is restored at the end of the current recursion. This last property is important because it results in a simple, functional model of extraction.

The combination of code and schematics embodied in this model can be thought of as a more powerful language for describing designs. This language has three desirable attributes: openness, orthogonality, and homogeneity.

The language is open in the sense that there is a small set of abstractions for design description that may be easily extended by users for widely different styles of schematics. This extensibility has been facilitated primarily by the fact that we concentrated on providing close links from graphical objects to code. Icons, for example, provide a direct graphical link to arbitrarily complex user procedures. Users can exploit this connection to easily define simple constructors such as arrays of cells and subrange selectors from a bus, or more complicated ones like data path and finite-state-machine generators.

The language is orthogonal because we avoided duplicating those concepts in graphics that are better handled by code. We concentrated on the declarative power of schematics by introducing the equivalents of variables, blocks, and functions, but left constructs such as general iterators and conditionals to code. This works well since net list generators that capture structural decompositions are often declarative, so they are better expressed pictorially, while generators that reflect algorithms are more easily expressed by code.

The language exhibits homogeneity in the sense that code and schematics may be used with equal ease, and may be intermixed easily. This attribute frees the designer to choose the best way to express a given piece of his design based on whether it is inherently easier to express algorithmically, by schematics, or by an appropriate mixture of the two. Homogeneity has derived from the bidirectional linkage between geometry and code.

Net lists are represented using the four data types, property, wire, cell type, and cell class. These basic types allow us to define an extensible set of abstractions 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. A more detailed treatment may be found in a companion paper [2].

The system provides a complete set of utilities to help create and manipulate net lists by program. These utilities consist of modules for creating cell types and wires and specifying interconnections by name, layered on top of more primitive creation functions. The higher level modules avoid cumbersome declarative specifications that are typical when creating net lists using the primitive functions. When a composite cell type is created, the code performs a number of checks to ensure that invariants required by the net list data structure are maintained. To give some idea of what textual specification based on these utilities is like, we now present an example that constructs a decoder with an arbitrary number of inputs.

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

The task of the schematics extractor is to turn 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.4.2 provides examples of satellites.

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 designate a rectangle with the graphical editor by pointing to it with the mouse. Similarly, tools that specify a wire or a cell as output, for example when an error occurs, highlight the corresponding rectangles or cells. This approach, analogous to symbolic debugging of source code, permits real time interaction and avoids tedious names. It has proved extremely effective for reducing the extraction-simulation-debug loop. For example it allows the implementation of a command that adds a selected wire to the oscilloscope-like output of the logic simulator.

This tight integration between the graphical source and its net list stops, of course, whenever schematics refer to a net list generator expressed by code. A powerful disambiguation mechanism was introduced for cases when there is not a one-to-one correspondence between the net list and the schematic, for example when an icon that refers to the same net list is used several times.

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 design capture system. The design of a real chip rarely follows such a clean cut path. More often than not, there is considerable overlap between stages, the design involves more than just a two level description hierarchy, and the order of the stages is hard to determine. Nonetheless, this figure provides us with a useful basis for discussion by identifying significant tasks involving 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. 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 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. Of the 12 chips represented, six have been fabricated and tested, at least for functionality. 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 around 20% to around 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 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.

It is clear that the system's speed is not really adequate to debug large designs in a completely interactive manner. Extraction and simulation set up could each use an order of magnitude speed improvement before they become comparable to the time spent thinking. Caching already buys a factor of around 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 setup also accounts for a significant fraction of the time. Moreover, our system currently does not have a way to do the setup incrementally so the gains to be had are large. Finally, the speed to display signals is adequate though some improvement would help, especially for the larger designs.

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 could therefore 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 changed the time around the debug loop by an order of magnitude. Delaying size decisions had the additional side benefit of allowing processor cache capacity analysis to proceed in parallel with the 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 more or less 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. This approach is presented in a companion paper [3].

Parameterization did, however, complicate the system's implementation. Generating net lists incrementally is considerably harder because determining what changed and what did not 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 simply from the geometry.

Our decision to build an open system has also worked well. The extractor has been implemented using an object oriented model in which each instance of a graphical object has its own procedure to interpret it. This is an advantage for the CAD programmer who maintains the system since it resulted in a simple structure. It is also beneficial for the VLSI designer because it kept the mental model of the extractor quite simple. What is key is that this model has proved easy to extend and we have added several new graphical items since the system's initial design.

An advantage of openness is that it frees us from having to write a large number of graphical primitives before the system is useful. It allows these primitives to be added on demand and provides freedom to experiment with alternatives before picking one. We built 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.

It is difficult to design a unified sequence operator that is general enough to cover all of the applications on hand. Part of the problem is deciding how close to the layout geometry one wants the schematic representation. One extreme is the geometric sequencing model, in which the sequencing is identical to the layout. The other is the logical sequencing model where no attempt is made to conform to the structure of the layout and all inter-cell interconnection is specified by appropriate manipulation of structured wires. The geometrical sequencing model is conceptually very simple, though we find it more difficult to provide generality in this model. On the other hand it is easier to provide generality in the logical sequencing model but it is more cumbersome to use.

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 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 fairly intricate code.

In implementing the connection of graphics to code we utilize an interpreter for the local programming language to evaluate satellites. This use of the interpreter provided us with a lot of flexibility, since it allowed general expressions to be used directly within schematics. Variables referenced in these expressions could 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 comes a speed liability. Currently about half of the time for extraction is spent in the interpreter. Straightforward use of the interpreter means that 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 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. The selector might in fact be the very first instance the extractor encounters within a composition.

In the first implementation we divided satellites into parameter expressions and result expressions depending on their syntax. The parameter expressions computed values for the parameters while the result expression called the extract method for the instance being extracted. This approach was unsatisfactory because as we added new classes of objects the syntax of expressions would have to be embellished. This approach was also inefficient because the interpreter was invoked more often 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 very 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. The editor has some drawbacks, particularly with regard to displaying annotations. We found it 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 did impose this constraint, and so we implemented satellites, or properties, that could be made visible or not and whose position and looks could be controlled entirely by the designer.

The editor does not impose any semantics on geometry permitting the same editor to be used for both layout and schematics. This was at the same time a hindrance, because we had to reintersect rectangles each time an object was extracted; the slow down caused by reintersection was ameliorated somewhat by result caching but, as we pointed out earlier, caching does not work as well as we would like. Another problem with the editor not knowing about schematic semantics is that the editor cannot discover syntactic errors interactively. In our case, 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. The underlying programming language needs to be modified to allow only side-effect-free procedures and the manipulations of the context by the extractor need to be changed to fit the functional 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. We could avoid reintersecting each time if we maintained another intermediate representation. Avoiding rectangle intersection 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 a result of the fact that the concept of satellites appeared after the editor was written, and therefore it is not well integrated. The right way to allow users to control the disposition of useful information would be to add properties that have user-definable display procedures.

The computational model that we currently use 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 would be to change the contents of the net list incrementally when the net list generator is changed. In our current 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. 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 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, of course, 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. This has the added advantage that it couples well with ongoing document management work at our research center.