Integrating Schematics and Programs
for Design Capture
Richard Barth, Bertrand Serlet, Pradeep Sindhu

Xerox PARC Computer Science Laboratory
3333 Coyote Hill Road
Palo Alto, CA 94304
We present a design capture system that allows parameterized schematics and code to be intermixed freely to produce annotated net lists. Users can easily add new abstractions to the small base set supplied by the system. The system allows convenient graphical specification of layout generators and has been used to produce several large VLSI chips.
1. Introduction
Traditional design capture systems are schematic or text based. Most schematic based systems represent designs as static entities in which decisions such as the width of buses and the size of memories are fixed, thereby greatly limiting the potential expressive power of the graphical description. The text based systems use a conventional programming language or a specialized hardware description language [1, 4, 8, 9, 10]. These systems offer great flexibility, but a textual description of structure is often harder to understand and manipulate than a graphical one. More recent work overcomes these drawbacks by defining graphical languages with flexible specification via schematics [5, 6]. Typically the graphical language provides iterators and conditionals that are translated into a textual description. While this approach provides parameterized schematics, it fails to achieve a synthesis of graphical and textual descriptions in which either may be used with equal facility.
This paper describes an integrated text and graphics design capture system that has been used to produce several large (> 50,000 transistor) VLSI chips. Freely intermixing graphical and textual specifications offers significant advantages. The description tends to be more compact and comprehensible because the designer can choose the most appropriate way to express each piece of his design; consequently, it is easier to create, modify and maintain as well. The intermixing allows schematics to be parameterized thereby offering the benefits of better abstraction. It permits convenient graphical description of layout generators via schematics [3].
Rather than design a new graphical programming language, we choose to provide tight links between graphical objects and programs written in an existing strongly typed, block structured programming language. This avoids proliferation of concepts and results in an extensible system in which there is no distinction between built-in and user defined abstractions and where new abstractions are added easily.
The next section begins with the model for net list generation. Subsequent sections provide implementation detail, describe our experience with using the system to design chips, and point out directions for future work.
2. Net List Generation Model
A conceptual model that facilitates our discussion is that intermixed specifications are net list generators which produce annotated net lists when evaluated. A net list generator is like a layout generator, except that it operates at a higher level of abstraction. Indeed the output of a net list generator typically forms the input to a layout generator. This notion represents the next level of abstraction for design systems because it simplifies description while retaining the tight control provided by layout generators.
2.1. Computation Model
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.
2.2. Schematic Extraction
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.
3. Implementation
At the time implementation of this system began our laboratory already had an environment for the design of integrated circuits. Like most of the applications written locally this environment was built using the Cedar programming environment [12, 13] running on the Dorado personal computer [7]. Each of these preexisting components influenced the implementation of our design capture system in both substance and style.
3.1. Net List Representation
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.
3.2. Creating Net Lists by Program
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.
3.3. Schematic Extraction
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.
3.4. Annotations
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.
4. Results
Since its initial implementation in early 1986, the system has been used to describe about a dozen VLSI chips of varying size and complexity. Some of these chips have been fabricated while others are in the final stages of design.
This section provides data that characterize our experience with the system to date. To put this data in perspective we describe how the system fits within the larger context of a chip's overall design cycle and then provide the numbers which form the basis of the discussion in the retrospective section.
4.1. Chip Design Cycle
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).
4.2. Chip Designs and Statistics
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.
5. Retrospective
This section uses the data of the previous section to discuss some of the system's basic design decisions and point out which decisions turned out well, which ones didn't, and where we encountered unexpected difficulty.
5.1. Parameterized Schematics
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.
5.2. Extensible System
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.
5.3. Extractor Implementation
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.
5.4. Existing Editor
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.
6. Future work
6.1. Operator Extension
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.
6.2. Existing Computation Model Refinement
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.
6.3. New Computation Model
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.
6.4. Editor Framework
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.
7. Summary
We have described an extensible design capture system based on the notion of net list generators. Specifying generators with a combination of schematics and programs in an existing language leverages the familiarity designers have with these modes of expression. We have discussed some of the issues that arose during the construction and use of this system. Finally incremental and radical changes to improve the system were sketched.
Acknowledgments
Many people contributed to the evolution of graphical design capture systems within the Computer Science Laboratory. The members of CSL provided the Cedar system which enabled rapid development and provided a solid foundation. Many PARC chip designers supplied feedback and code which enriched the system. Finally, none of this work would be possible without the research environment which Xerox has so graciously provided.
References
1. M. R. Barbacci, "Instruction Set Processor Specification (ISPS): The Notation and its Applications", IEEE Transactions on Computers, Vol C-30, No 1, pp. 24-39, January 1981.
2. R. Barth, B. Serlet, "A Structural Representation for VLSI Design", Submitted for publication.
3. R. Barth, L. Monier, B. Serlet, "PatchWork", Submitted for publication.
4. S. German, K. Lieberherr, "Zeus: A Language for Expressing Algorithms in Hardware", IEEE Computer, pp. 55-65, Vol 18, No 2, February 1985.
5. K. Lieberherr, "A Two-dimensional Hardware Design Language for VLSI", North Holland, proceedings. EUROMICRO Symposium on Microprocessing and Microprogramming, pp. 131-142, March 1984.
6. J. Nash, S. Smith, "A Front End Graphic Interface to the First Silicon Compiler", proceedings EDA, pp. 120-124, March 1984.
7. K. Pier, "A retrospective on the Dorado, a high-performance personal computer", 10th Annual International Symposium on Computer Architecture, pp. 252-269, Dec. 1983.
8. R. Piloty, D. Borrione, "The Conlan Project: Concepts, Implementations, and Applications", IEEE Computer, pp. 81-92, Vol 18, No 2, February 1985.
9. M. Shahdad, R. Lipsett, E. Marschner, K. Sheehan, and Howard Cohen, "VHSIC Hardware Description Language", IEEE Computer, pp. 94-102, Vol 18, No 2, February 1985.
10. M. Shahdad, "An Overview of VHDL Language and Technology", proceedings DAC 1986, pp. 320-326, July 1986.
11. G. Steele, Common LISP: The Language, Digital Press, 1984.
12. D. Swinehart, P. Zellweger, R. Beach, R. Hagmann, "A Structural View of the Cedar Programming Environment", ACM Transactions on Programming Languages and Systems 8, 4, October 1986.
13. W. Teitelman, "A tour through Cedar", IEEE Software, vol 1, no 2, pp. 44-73, April 1984.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 2.2.1 Icons and Schematics
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 3.2.1 Decoder Program
[Artwork node; type 'ArtworkInterpress on' to command tool]
Table 3.3.1 Satellite Usage
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 4.1.1 Idealized View of Chip Design Cycle
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 4.1.2 The Debug Loop
[Artwork node; type 'ArtworkInterpress on' to command tool]
Table 4.2.1 Layout Methods and Development Times
[Artwork node; type 'ArtworkInterpress on' to command tool]
Table 4.2.2 Chip Size Statistics
[Artwork node; type 'ArtworkInterpress on' to command tool]
Table 4.2.3 Interaction Times