|
© Canadian Conference on VLSI (1987). This is the author's version of the work. It is posted here by permission of the Canadian Conference on VLSI for your personal use. Not for redistribution. The definitive version was published in Proceedings, CCVLSI - 87, Winnipeg, October 1987, pp5-16.
After 25 years of development, most of the issues in computer-aided circuit design are well understood. There are many reliable products that enable designers to edit, analyze, and synthesize highly complex (VLSI) circuits. However, some areas of computer-aided design remain unsolved and are largely ignored by researchers. This paper surveys some of these less explored topics in CAD, and presents detail on one problem in which some progress has been made. The hard problems that will be surveyed are the problem of automatic architecture selection (or derivation) in silicon compilation, the problem of parameterized cell representation, and the problem of correspondence between different abstract views of a circuit.
The hard problem of interest in this paper is the association of textual and graphical descriptions of a circuit. Graphical techniques allow sketching of the circuit on a display screen whereas textual techniques require programming in a hardware description language. Although each method has its advantages, the two are rarely used for the same circuit. Conversions are possible, but once converted there is still no direct linkage between them. In this paper, a circuit description language is shown that is both textual and graphical. Based upon linear inequalities, a popular textual method, the language system maintains both descriptions at all times.
In recent years, the notion of "Silicon Compilation" has become popular in VLSI design circles. Silicon compilation implies the ability of a computer to convert a behavioral or high-level structural circuit description into a physical description, suitable for manufacturing. Behavioral descriptions are the highest level of abstraction, providing only the functional characteristics of the circuit with no specified way of implementing it. For example, the behavioral description of a subtraction unit simply states that the output be the difference of the two inputs.
The other type of input to a silicon compiler is a structural description, which is closer to the final implementation because it provides some of the necessary building blocks. The structural description of a subtraction unit would show the negation modules, the summation modules, the carry lines, and other relevant detail. Neither description contains actual transistors, specific layers, or precise module placement: that is the job of the silicon compiler.
Unfortunately, the reality of silicon compilers is somewhat less glorious than it seems. Those silicon compilers that accept structural descriptions usually restrict the allowable components to those that are already known to the compiler. The compiler then becomes an "assembler" which merely does placement and routing of library components. Although these are difficult tasks, they are nowhere near the dream of silicon compilation.
Even those silicon compilers that accept behavioral descriptions are not truly general. These systems have predesigned architectures to which all input must conform [1, 7]. For example, the behavioral description may be mapped into an ALU with a control section and a datapath [12]. This architecture then provides the structural description necessary to, once again, place and route library components. Recent silicon compilers are able to handle a large set of architectures, covering a broad spectrum of possible circuits [4, 23, 24, 27]. However, there is no limit to the number of circuit architectures possible, so this method is guaranteed to fail in the long run.
What is needed is the ability to automatically generate an architecture that matches a functional specification. This problem is equivalent to the automatic synthesis of algorithms from behavioral descriptions, a problem that is also very difficult. Nevertheless, more research is needed in both problems in order for the field to advance [9].
Another hard problem in systems for VLSI design is the correct representation of parameterized cells. Parameterized cells are those that can alter their contents according to a set of parameters stored on each instance of the cell. For example, a parameterized inverter may have a "strength" value that determines the ratio of the transistors inside the inverter. Then, two different instances of the inverter cell with different parameters will actually produce different layout.
The representation problem is a question of how much layout to retain for each different parameterized instance. If all layout is retained in memory, then each instance of a cell may require a different description, causing the design system to consume as much memory for a hierarchical design as it would for a fully instantiated circuit. If the layout is not retained in memory, then each instance of a cell will require extensive computation to determine its layout, which may delay interactive editing unnecessarily.
One way to avoid solving this problem is with ever faster processors and ever larger memories. This "brute force" method has worked for a number of years, but will lose ground to VLSI circuits. Another nonsolution, used by most VLSI design systems, is to restrict user activity. Interactive graphic design systems typically do not allow parameterized cells, thus avoiding the issue completely. Those design systems that do allow parameterized cells are usually text-based and noninteractive. This also avoids the issue because the layout need only be computed once, and therefore is not stored in memory.
As with many issues in computer science, this is a tradeoff between space and time. A partial solution is to analyze the parameters to see whether the memory representations of multiple instances can be shared [2]. This presumes that most instances either are identical or are not sufficiently different to warrant a new layout although this presumption does seem to hold true for many current designs, it is not a general solution for the future.
The promise of VLSI circuits demands better representations for parameterized cells. Parameterized cells must be stored and retrieved as efficiently as possible, especially in interactive environments. To do this, the cell definition will have to be programmable at a detailed level so that it can be partially stored and partially computed. Most of the contents can then be retrieved from the cell definition, and the remainder can be computed from the individual parameters. However, the automatic determination of this separation is a difficult problem in computer-aided circuit design.
Any representation of a circuit is, by definition, an abstraction that only approximates the actual artifact. The use of these abstractions can be a very powerful design technique because it provides alternative views of the circuit. The possible abstract views of a circuit range from the most specific (IC layout and package locations) through many intermediate levels (stick transistors, register transfer, etc.) to the most abstract (architectural plans and functional specifications).
Ideally, the circuit designer would like to have many views of a circuit displayed at once, with changes to any one reflected in all. Sadly, this is not even close to being possible. Not only is it difficult to associate components in different views, but the proper handling of changes complicates the issue immensely. Instead, designers use independent editors that allow the views to be constructed, but not maintained or compared.
Some design systems provide view comparison by converting one view to another. For example, a schematics layout comparison works by converting the layout to a schematic and then comparing the two schematics. When direct conversion is not possible, the two views may be converted into a third, common view in which correspondence can be made. Regardless of the method, correspondence by conversion is time consuming and prone to errors. The comparison process, when done all at once, is particularly difficult, and most methods break down badly when there is the slightest difference in the circuits [8].
A more appropriate method would be to maintain correspondence and incrementally update this information as changes are made. This demands a many-to-one mapping of components between different views of a circuit. With such a scheme, correspondence would be immediate and would be able to make use of any special-purpose information pertinent to the particular views.
A problem that arises in the incremental maintenance of view correspondence is that designers often wish to make intermediate changes to one view that do not match the other view. The designer may be aware that the change is temporary, but the design system must be able to accept the failure of correspondence and to recover properly when the set of changes is complete. Thus, proper view correspondence demands complex mapping representations, a flexible user interface, and advanced circuit comparison techniques.
The final hard problem in VLSI design, and the one that this paper attempts to solve, is the issue of text and graphic design languages. Text and graphics are the two ways of specifying electronic circuits. Textual descriptions require that precise coordinates, sizes, and relationships be specified in some hardware description language. Many of these languages allow the omission of some information that can be derived automatically from constraints on other information. Graphical descriptions require sketching programs that allow the user to physically place circuitry on a display screen. These graphical programs can also derive missing information that is abstractly described [28, 29]. Both text and graphics have advantages as descriptive methods, but the two have rarely been combined in any effective way. The remainder of this paper explores the problem of associating textual and graphical descriptions, and illustrates a linkage that has been implemented by extending a traditionally textual language.
Textual circuit descriptions are becoming increasingly popular as more programmers become interested in hardware design. These hardware description languages view a circuit as a set of components and their connections. Declarative statements specify the interconnection and physical placement of components as well as constraints between components (see Figure lb). Subroutines of these statements are typically used to describe cells so that code hierarchy and circuit hierarchy match. The advantage of a textual description is that it can be parameterized for a wide variety of circuits. Also, documentation can be quite detailed throughout the code. And of course, textual descriptions are very easy to store and manipulate, making any computer terminal into a design workstation.
|
Graphical descriptions have the essential advantage of being true to the final artifact: the circuit. Before computers, graphical techniques were used exclusively for circuit layout. After that, the early computerized design programs mimicked the cut-and-paste methods that had been done manually. Current graphics systems combine powerful manipulation capabilities with specialized synthesis tools. Graphic description languages are easier and faster to use because of the intuitive feel of the circuitry that is provided. Combined with the dropping cost of graphic workstations, the method is remaining popular.
Unfortunately text and graphic languages each have limitations that the other solves. A designer might wish to sketch a circuit graphically and then use text editing facilities to manipulate the circuit. If both descriptions were unified, work could alternate from text to graphics whenever convenient. For example, Figure 1 shows an inverter that is drawn graphically (1a) and has a textual equivalent generated (1b). The text code is then parameterized (1c) so that the circuit can handle restored signals (R=1) or unrestored signals (R=2). The designer is saved the trouble of typing the code, and is further saved the trouble of redrawing the geometry for each circuit option.
Besides cell parameterization, a text/graphics unification is useful in the composition of array-based designs where a small circuit is specified graphically and then fully arrayed with the text. Here again, the designer need not type the details of an array element, nor must each of the array members be explicitly sketched. This kind of array-based support is provided by the Tpack system which can convert a graphic display into cells and then use a textual personality matrix to replicate them [17].
It might seem that graphic techniques are best for initially specifying the components whereas textual methods are best for finalizing their organization. This split appears because graphics can manipulate individual objects directly but has no apparent loops or algebraic expressions. In fact, loops can be specified graphically, as the Escher system has demonstrated [5]. This system maintains two separate graphic images: the specification and the layout. Graphic specification of a loop is done with three objects: the initial, final, and iterated parts. By placing, connecting, and parameterizing these parts, the loop is defined and its boundary conditions are illustrated. Escher also allows recursive specifications.
The drawback of Escher is that its two representations, the specification and the layout, are not unified once the layout is produced. Thus, a change to the layout does not affect the specification even though both may be visible on the screen. This problem arises in more traditional specification/layout systems that use textual specification. Some of these systems allow the graphics to be "reverse engineered" to produce a new textual specification. This is the approach taken by Daedalus/DPL which allows a Lisp-based textual specification (DPL) to generate layout, and allows a graphics editor (Daedalus) to modify the layout [2]. To complete the circle, Daedalus has the ability to generate DPL that corresponds with the graphics. However, this generated text has none of the original flavor, for it has lost variable names, algebraic expressions, conditionals, and loops. The problem is similar to decompiling object code in an attempt to reconstruct the high-level language.
To properly unify text specifications and graphical layout, the two must be maintained uniformly as changes are made to either. With such an approach, a common database holds both forms and maintains them in parallel. One system that does this is SAM, which tackles the two problems of algebraic expressions and loops [26]. In SAM, the textual specification may contain algebraic expressions that define the graphical layout. For every value of the variables in the text, a different graphical image is produced. However, it can be difficult to adjust these textual expressions if the user modifies the graphics. SAM makes this adjustment by adding constants to the algebraic expressions so that they remain correct. For example, if the implant transistor in Figure 1(a) is graphically changed to be 10x2, SAM will alter the textual declaration in Figure 1(c) to be "[8R+2 by 2]".
The other text/graphics association found in SAM is loop maintenance. Textual loops that generate many graphical components must accommodate the possibility of a graphical change to just one component. SAM chooses to retain the loop and change all components if any one is graphically altered. Although SAM's text/graphics maintenance techniques seem ad hoc, the algebraic expression association is actually fairly useful. Nevertheless, this system existed for illustrative purposes only and could not do real circuit design.
The solution to the problem of effective text/graphics linkage is to find a language that can be expressed both graphically and textually. Imperative languages are a poor choice since they have an execution sequence that is the same as the sequence in the textual description. Declarative languages, such as the code in Figure 1, are more sensible for this effort because there is no dependence on order in the text or the graphics.
Before describing the language that unifies text and graphics, some background is needed on the specific CAD environment. "Electric" is an integrated VLSI design system that provides an extendible circuit-network-oriented database for arbitrary CAD tools and process descriptions [20]. Among the tools currently integrated are design-rule checkers, simulators, PLA generators, routers, compactors, and so on. Design can be done in nMOS, CMOS, bipolar, schematics, printed circuitry, graphic artwork, and much more. The network-oriented database views components as nodes, and views wires as arcs. By insisting on connected layout, Electric is able to better analyze the circuit and communicate properly with the designer. In addition, the wires may contain constraint rules that control the layout as changes are made.
Because Electric is primarily a graphical editor, the wire constraints constitute a graphical design language. As part of the system's flexibility, different constraint systems can be used interchangeably. Currently there are two constraint systems: one for hierarchical layout and one for linear inequalities. Although the linear inequality constraint system is the subject of this paper, the hierarchical layout system deserves mention.
The hierarchical layout constraint system has been used by many designers in diverse applications. It is the primary constraint system in the Electric VLSI design package. There are four rules in Electric's hierarchical layout constraint system: three rules apply to individual wires and the fourth rule states that changes to a connection site in a cell definition must be reflected in those wires connected to instances of the cell higher up the hierarchy. This hierarchical constraint maintains correctly connected circuitry and permits both top-down and bottom-up design.
The three constraint rules on wires are optional, which gives Electric its programmability. By properly selecting constraints, the designer creates a circuit that reacts to changes and exhibits certain properties. The three constraints are rigid, Manhattan, and slidable. Rigid wires tightly couple the components they connect. Not only must the wire length remain constant, but the orientation with respect to the component cannot change, even if the component is rotated. Manhattan wires may stretch but may not rotate away from their horizontal or vertical orientation. Slidable wires may adjust their component connections if the connection sites have room. This sliding allows large contact and transistor components to connect properly at a number of different sites along the component body. When constraint loops are found that cannot be solved, the system jogs wires to keep the connectivity.
More detail on the Electric VLSI system can be found in [21]. The system is in use at many universities throughout the world and is sold commercially as Bravo3VLSI from Applicon, a Schlumberger Company.
The linear inequality constraint system is the basis of the text/graphics unification in Electric. This system is based on wire length inequality expressions in the X and Y axes. Any wire can have an expression of the form "L=k", "L≥k", or "L≤k" where k is a constant and L is either X or Y to indicate a length constraint in that axis. Since these expressions appear on graphical objects, their direction is clear: the constraint "Y≥15" on a vertical wire actually means that the upper component must remain 15 or more above the lower component. Also, since VLSI design is often done with Manhattan geometry, the graphical constraint system can be instructed to create implicit "X=0" and "Y=0" constraints for vertical and horizontal wires.
Many textual languages exist for specifying linear inequalities [6, 13, 14]. In ALI, the basic inequalities can be combined into higher-level properties such as inclusion, attachment, minimum size, etc [15]. Other systems capture design rules because they can describe minimum separation and other layout spacings [11, 16, 18, 22, 29].
Linear inequalities are easily solved by evaluating one axis at a time. The expressions in each axis can be ordered such that each constraint makes one component's position dependent on another component's position. Beginning with a component whose position is not dependent on anything else, the constraint solver assigns coordinates and eliminates constraints. Where constraint loops exist, the solver may find an inconsistency that makes a solution impossible.
One problem with graphical programming of linear inequality constraints is that the graphics places all expressions on wires which connect two components. However, some constraints may exist between unconnected components. To solve this problem, Electric has an "invisible" wire that may be run between two components without making an electrical connection (see Figure 2). This wire then declares a constraint that would otherwise not be expressible in the circuit.
 |
Another problem with the graphical language is that it must be able to capture all salient features of the equivalent text. To do this, Electric stores a pointer to the equivalent text on each graphical object. Comments above a line of text are considered to be part of that text. Unrelated parameter declarations can be stored with the cell definition that contains the graphics.
In a purely textual environment, any graphic solution that satisfies the specification can be used. However, when graphics already exists, introduction of new constraints must be solved carefully to minimally disturb the geometry. For example, a 4-long wire that is given the new constraint of being 7 or more in length will have to stretch. The constraint solver can choose to adjust either end, but should select the end that is closest to the cell boundary so that fewer components change. As another example, a 4-long wire, constrained to be 4 long, may have one of its end components graphically moved inward. The constraint solver must "anchor" the moved component to make sure that the other end is adjusted rather than the one that just moved. Electric does this anchoring implicitly, although there are graphical constraint systems that allow explicit specification of component immobility [19].
One complication that arises in a text/graphics unification of linear inequality constraints is that there are many graphic representations that meet the textual constraints. However, only one is the correct circuit as seen on the screen, and it must be reconstructible from the text. Thus, each text constraint has optional coordinate vectors that indicate exactly how the constraint has been met. For example, Figure 3 shows the text and graphics for a constraint "Y≥4" that is more than met. The actual distance appears as a default in square brackets in the text. The use of these defaults allows the text to precisely define the graphics, yet it does not damage the flexibility of either representation.
|
As the examples have illustrated, Electric's textual language has two types of constructs: components and connections. The syntax of a component declaration is:
declare INST1[OPTIONS], INST2[OPTIONS], ... , INSTn[OPTIONS] CLASS;
Each component declaration creates INSTances of a particular CLASS and describes specific OPTIONs such as size, position, and rotation.
The connection declarations identify two components and their connection sites. A constraint appears between the components and optional information may precede them:
connect [OPTIONS] COMP1[CONN1] [CONSTRAINT] [SATISFACTION] to COMP2[CONN2];
For example, Figure 4(a) shows two metal-diffusion contacts connected with an unconstrained metal wire that rises 7 units, described with this text:
connect [layer=metal] C1 [0,7] to C2;
where C1 and C2 are the components, no connection sites are needed because there is only one, and an actual wire length is specified because no constraints are given. Another example, shown in Figure 4(b) is:
connect T1:poly-left left 4 or more to C5;
which indicates that the "poly-left" connection of component T1 is connected to the default connection of component C5 and must be 4 or more in its X coordinate. The layer is defaulted because it can only be polysilicon.
In addition to components and connections, the language also has an "export" statement for hierarchical connections. To complete the syntax, a "begincell" and "endcell" statement delimit cells so that a complete hierarchy can be described.
 |
One problem with linear inequalities as a VLSI description mechanism is that they require an overabundance of specification to work properly. Unconstrained distances that have no defaults are assumed to be zero, resulting in a circuit with many overlapped components. Although graphic specification does provide default spacings, textual languages have rarely included this information, requiring the user to type many constraints instead. The use of design rules as implicit constraints alleviates the problem but can make user-constraints hard to debug because of potentially nonobvious overconstraint situations.
Another problem with this particular text/graphics programming environment is that it is not very powerful. Although both Electric's hierarchical layout and its linear inequality constraint systems are useful for VLSI applications, they remain less than complete. For example, neither can express the desire to keep one component centered between two others.
Future work must consider the use of arbitrary constraints, as found in Sketchpad [25] and ThingLab [3]. These systems allow powerful textual language expressions to be placed on graphic objects, and the constraints are enforced through all changes to the circuit. The drawback of these systems is that they cannot use propagation methods to solve the constraints because they do not know the extent of a constraint's activity. As a result, global relaxation methods are used which are less efficient and can be inappropriate for VLSI design tasks. One way to alleviate this problem is to preprocess the constraints and reduce their complexity [10]. All of these techniques will someday be combined to produce a good text-and-graphics design language for VLSI.
This paper has described some of the unsolved problems in VLSI design systems and has addressed the problem of text and graphic design specification. Both text and graphics are important design methods, and the paper has demonstrated some methods of combining them. The Electric VLSI design system was discussed as a starting point for graphical programming. By extending this system, it has mimicked the traditionally textual languages based on linear inequalities. In this way, a truly unified text and graphics design system has been created.
