Integrating Schematics and Programs for Design Capture
Richard Barth Bertrand Serlet Pradeep Sindhu
Xerox PARC Computer Science Laboratory
3333 Coyote Hill Rd., Palo Alto, CA 94304
Abstract: This paper presents a design capture system that allows parameterized schematics and code to be intermixed freely to produce annotated net lists. A key feature of the system is its openness. It provides a small set of abstractions for design description that can easily be extended by users. The system also allows convenient graphical specification of layout generators, and has been used to produce several large VLSI chips.
Keywords: Design Automation, Design Capture, Schematic Capture, Net List Generators, Parameterized Schematics, Schematic Annotation, VLSI
1. Introduction
Traditional design capture systems are typically either schematic based or text based. Most of the 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 either a conventional programming language, or a specialized hardware description language [1, 4, 8, 11, 12]. 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 has attempted to overcome these drawbacks by defining graphical languages that permit 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. The central thesis of this system is that permitting a designer to freely intermix 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 trivially allows schematics to be parameterized, thereby offering all the benefits of better abstraction. It also permits convenient graphical description of layout generators via schematics, an aspect that is explored in detail in a companion paper [3].
The particular way in which we have integrated text and graphics was influenced strongly by our programming environment. Rather than design a new graphical programming language, we chose to provide tight links between graphical objects and programs written in a strongly typed, block structured programming language. This has had the obvious benefit of avoiding a proliferation of concepts, but its two other effects have been perhaps even more important: It has resulted in an open system, one in which there is no distinction between built-in abstractions and user defined ones and where new abstractions may be added easily. And, it has made graphical and textual descriptions symmetric and interchangeable, permitting the designer to freely intermix the two in a given design.
A conceptual model that will facilitate discussion through the remainder of this paper is that intermixed specifications are net list generators that 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; in fact the output of a net list generator typically forms the input to a layout generator. We believe that this notion represents the appropriate next higher level of abstraction for design systems because it simplifies description while retaining the tight control over the result provided by layout generators. Accordingly, 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 a number of large chips, and point out directions for future work.
2. Net List Generation Model
2.1. Computational 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 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.
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, 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.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 2.2.1. An icon and its schematic
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.
2.3. Attributes of the Model
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.
3. Implementation
3.1. Background
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 had been built using the Cedar programming environment [13, 14] 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.
The Dorado supplied a high performance computing engine with a 32 MByte virtual memory, high resolution black and white and color monitors, a large local disk, keyboard and mouse, and an Ethernet connection. Cedar provided both the software base and a development style. The Cedar language is a strongly typed, block structured language that has modules, garbage collection, dynamic types, and procedure variables. The last of these permitted an object-oriented style of programming [10] that was used quite heavily in our system. In addition to the Cedar compiler, there is also an expression interpreter that we used to advantage. Of course, the Cedar environment also supplied the standard program development tools such as a text editor, symbolic debugger, run time library, and support for system management [9].
The major preexisting design tool was a high quality layout editor. The existence of this editor led us to build a system in which the designer prepares graphical input using the editor and then postprocesses this input to synthesize the net list. An alternative would have been to build a schematic editor that provided the designer with commands for incrementally specifying the net list, and then use the net list (rather than uninterpreted rectangles) to paint the display. We will return to this point in the section on future work.
3.2. Net List Representation
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. We will describe these data types only briefly, and a more detailed treatment may be found in a companion paper [2].
The property data type represents an annotation consisting of a <key, value> pair. The key is a unique name, and the value is a pointer to an arbitrary Cedar data type. A property may be attached to a wire, a cell type, a cell class, and even another property. Typical annotations are names, geometrical information such as orientation and size, and electrical information such as node capacitance.
A
wire represents a collection of nets. An a
tomic
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 (DAG) whose leaves correspond to atomic wires; only the atomic wires represent actual nets, the others simply provide structure. Each wire may carry arbitrary properties. This rather abstract structure is illustrated in Figure 3.2.1 by showing some of the graphical representations used in schematics for drawing wires.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 3.2.1. Some Graphical Representations Used for Drawing Wires
A cell type represents a device. Cell types consist of two parts, an interface and some implementation data. The interface contains some 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, in addition to class-specific data. Some of the properties of a cell type may be inherited from those of its class. A cell instance represent 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. The record cell class is a list of cell instances of potentially different type and arbitrary interconnection. The sequence class represents an array of cell instances of the same type. The tiling cell class represents a two dimensional array of cell instances (of potentially different type) in which the interconnections are nearest-neighbor. Finally, the icon cell class hides the net list it abstracts in its implementation data. We have extended this small set of classes with more complex and application-specific ones as the need for them arose.
3.3. Creating Net Lists by Program
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.
Decoder: PROC [nbBits: NAT] RETURNS [cell: CellType] = {
size: NAT := 2**nbBits;
array: TileArray := NEW [TileArrayRec[size]];
FOR i: NAT IN [0 .. size) DO
array[i] := NEW [TileRowRec[nbBits]];
FOR j: NAT IN [0 .. nbBits) DO
array[i][j] := NEW [TilingClass.TileRec];
array[i][j].type := IF XthBitOfN[j, i] THEN CellOne[] ELSE CellZero[];
array[i][j].renaming := LIST [
["Input", Index["Input", j]], ["NotInput", Index["NotInput", j]]]
];
ENDLOOP;
ENDLOOP;
cell := CreateTiling[
public: Wires[
Seq[nbBits, "Input"], Seq[nbBits, "NotInput"], Seq[size, "Output"], "Gnd", "Vdd"],
tileArray: array
];
};
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.
3.4. Schematic Extraction
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. When extracting an instance, the extractor first creates a new context by copying the existing top of stack (Figure 3.4.1). It then uses the Cedar interpreter to evaluate the satellites for the instance in this new context, performing whatever declarations and assignments are called for, and passes this context to the extract method. When the method returns, the extractor pops the stack, restoring the old context. These copy semantics are crucial in ensuring that extraction appears to be a simple, functional process with no side-effects, as long as the method itself and any procedures it calls are 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. Satellites of either type may be made invisible to avoid cluttering schematics. Invisible satellites of a given type are always evaluated before visible satellites of the same type to allow visible information to take precedence. Depending on its syntax, a satellite may have one of four effects: declare a new variable, assign to an existing one, cause an annotation to be placed on the extraction result, or cause the result to be named. Table 3.4.2 provides examples for each case.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Table 3.4.2. Syntax of satellites
The last two cases deserve more comment because they provide a direct way to place a property on any net list entity (a name is just another property, so the special syntax for names is just a convenience). When an annotation appears on a geometric instance (object) the property it represents is placed on the corresponding net list instance (object). For example, the satellite w𡤈 bound to a transistor instance sets the size of the corresponding transistor instance, while the satellite "MyCell" bound to a composition object ends up naming the corresponding cell type, not the cell instance.
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 gets instantiated within the parent composition, or a wire that gets used to make one or more connections. Icons that represent wires are typically used for connections invlolving structured wires. The wire composers and selectors in Figure 3.2.1 are all examples of such icons.
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. During this process, it treats certain names (for example, "Vdd" and "Gnd") specially so that designers do not need to draw sugh global signals in the interface of each icon or composition that uses them, and therefore do not need to hook them up explicitly either.
3.5. User Interface
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.
4. Results
Since its initial implementation in early 1986, the system has been used to describe around 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.
Portions of the system were designed and implemented in fall 1985, with the remainder being completed in winter. By February 1986, the first implementation was beginning to turn over. Early experience in describing a test chip made us revise several decisions, as did continuous attempts to improve speed, enhance the user interface, and clean up internal structure. The rate of change slowed considerably after mid 1986, and the system's functionality, though not its speed, has remained essentially the same since.
The remainder of this section provides data that characterize our experience with the system to date. To put this data in perspective, we first describe how the system fits within the larger context of a chip's overall design cycle, and then go on to 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. The detailed specification stage typically 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 description proceeds bottom up. The designer enters subblock descriptions and debugs them. He then enters the top level description in terms of the subblocks and debugs that. Finally, he specifies how layout is to be generated, generates it, and performs a number of checks to ensure that the layout is correct. 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. Figure 4.4.2 shows this activity broken up into a repetitive, five-stage process: instantiating the simulation, simulation, finding the problem, modifying the description to fix the problem, and extracting and/or compiling to rebuild the net list. 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).
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. 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.
5. Retrospective
We had to make the system work quickly since other researchers depended on the results of our work. This caused us to take steps such as using the existing graphical editor, and deferring a completely incremental system. In retrospect, many of these decisions turned out to be right, because had we been more ambitious in the beginning, we would not have gotten a working system and would not have benefited from the user feedback that is so important in building good tools. This section discusses some of the system's basic design decisions and points out which ones turned out well, which ones didn't, and where we encountered unexpected difficulty.
5.1. Parameterized Schematics
Our provision of parameterized schematics has been close to an unqualified success. Parameterization allowed our designers to delay decisions such as the number of lines in a 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 in the last section, for example, this technique resulted in over an order of magnitude reduction in time through the debug loop: it changed the time from somewhere around 10 hours to less than one hour. Delaying size decisions had the additional side benefit of allowing size 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. For example, 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.
5.2. Open System
Our decision to build an open system has, for the most part, worked well especially given the limited manpower we had to devote to building design tools. The extractor, for example, has been implemented using an object oriented model in which each instance of a graphical object has its own procedure to interpret it. This was an advantage for the CAD programmer who maintains the system since it resulted in a simple structure. It was also beneficial for the VLSI designer because it kept the mental model of the extractor quite simple. What is key, however, is that this model has proved easy to extend, and we have added several new graphical items since the system's initial design.
A great advantage of the openness was that it freed us from having to write a large number of graphical primitives before the system was useful. It allowed these primitives to be added more or less on demand, and provided a great deal of freedom in experimenting with alternatives before deciding to pick one. We have 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.
One area where we encountered surprising difficulty was in coming up with a unified sequence operator that was general enough to cover all of the applications on hand. Part of the problem was in deciding how close to the layout geometry one wanted the schematic representation. One extreme is the geometric sequencing model, in which the sequencing is identical to the layout. Another extreme 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 was conceptually very simple, though we found it more difficult to provide generality in this model. On the other hand, it was easier to provide generality in the logical sequencing model, but it proved more cumbersome to use.
5.3. Extractor Implementation
The schematics extractor and the layout extractor use a common geometry engine. This may seem strange at first sight, 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, however, 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 utilized an interpreter for the Cedar language to evaluate satellites embedded within schematics. This use of the interpreter provided us with a lot of flexibility, since it allowed general Cedar 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 came a speed liability. Currently, about half of the time for extraction is spent in the interpreter. Straightforward use of the interpreter meant that every time a schematic was reextracted expressions would 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 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 to take them into account. This approach was also inefficient because the interpreter was invoked more often in calling the extract method. Our second attempt was to eliminate result expressions and have hidden properties from which the extract method could 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.
5.4. Existing Editor
In one respect, having a high quality graphics editor available was a big plus because it left us free to implement higher levels of the design capture system. Had the editor not been available, we would have spent several man years implementing it. The editor did have some drawbacks, particularly with regard to displaying annotations. In our descriptions 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 were forced to implement satellites, or properties that could be made visible or not and whose position and looks could be controlled entirely by the designer.
The fact that the editor did not impose too many semantics on geometry was important because it allowed the same editor to be used for both layout and schematics. This was at the same time a hinderance, 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.
6. Future work
6.1. Operator Extension
We have found that 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 with a single cell type and combines power with conceptual simplicity. Decoders are obvious examples of such tilings. The wiring between cells, aggregation of wires into buses, and index dependence are just a few of the issues which must be considered.
6.2. Refinements to the Existing Model
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.
6.3. A New Computational Model
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.
6.4. Editor Framework
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.
7. Summary
We have described an open design capture system based on the notion of net list generators. Permitting generators to be specified with a combination of traditional 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, we have sketched both incremental and radical changes that need to be made to the system to improve it.
8. Acknowledgments
Many people have 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. The Dragon 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.
9. Bibliography
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", To appear.
3. R. Barth, L. Monier, B. Serlet, "PatchWork", To appear.
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. E. Schmidt, "Controlling Large Software Development In a Distributed Environment", Xerox Palo Alto Research Center Technical Report CSL-82-7, December 1982.
10. B. Serlet, "Object Oriented Programming in Cedar", Actes des Journees Langages Orientes Objet, Bigre Globule, pp. 64-68, January 1986.
11. 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.
12. M. Shahdad, "An Overview of VHDL Language and Technology", proceedings DAC 1986, pp. 320-326, July 1986.
13. 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.
14. W. Teitelman, "A tour through Cedar", IEEE Software, vol 1, no 2, pp. 44-73, April 1984.
Appendix