[Indigo]<DA>AlePaper.dm!1>Ale.paper

An implemented interactive system, Ale, for creation and modification of structures of parameterized cells is described. Cell parameters are geometric in nature and provide for stretchable cells, in which the positions of connectors to cells can be easily changed. Internal cell geometry can also be parameterized to provide for changes in the electrical characteristics of active devices and conductors. Having designed a set of such cells, the ease with which they can be distorted, without regard for internal details, greatly simplifies the task of chip assembly, and modification after assembly. Automatic chip assembly, based on the parameterized cells, is discussed. Cell libraries become far more viable when using parameterized cells since, unlike conventional rigid cells, they can be modified to fit a variety of contexts. Ale implements geometric parameters using purely graphical methods, so that no knowledge of programming is required of the user.

The majority of systems in use for custom integrated circuit layout are based on an interactive graphics editor [1][2]. Using such a facility a designer can interactively create and modify hierarchical descriptions of integrated circuit layouts, making use of a library of previously designed parts. Many systems still in use involve first drawing cells on mylar and then digitizing them for subsequent modification and integration with the rest of the layout. Either way, the resulting layouts can be analyzed by a variety of automatic programs to check various aspects of well-formedness and correctness. These analyses typically involve Geometric Design Rule Checking, Circuit Extaction with subsequent Electrical Rules Checking, Dynamic Simulation and Topological Comparison with the required circuit. The results of these analyses usually require that the layout be modified, and the synthesis~analysis loop continues until a satisfactory analysis is obtained.

At this point the layout submitted for fabrication. On receipt of test chips various dynamic tests are conducted, but, due to lack of complete coverage by the analysis tools, errors or inadequacies are often found. Even with a good set of tools problems are often encountered with nuances of timing. Such errors provoke a reentry to the synthesis~analysis loop and another round of fabrication and testing.

The message here is that interactive design is not a one-pass affair, but typically involves many iterations before a satisfacory result is obtained. Given that the interactive graphics editor is involved so prominently in this process it is worth considering what features such an editor should have, and how existing editors fall short of such an ideal.

In looking at a number of systems for interactive layout is seems apparent that the design of any one cell is not, in itself, very difficult. Even using drawing boards and digitizers basic cell design is rather well understood. Indeed, one of the main goals of Structured Design involving hierarchy and regularity, is to break down the layout into a small number of cells, each of which is of manageable complexity.

The major difficulty lies in designing the lower level cells in such a way as to facilitate connecting them together to form bigger cells - the problem of chip assembly. Cells designed using conventional interactive editors are normally rigid structures that can be interconnected either by juxtaposition, if the external connectors have been successfully arranged to line up with those of each neighbor, or by inter-cell wiring. The former approach normally gives more compact layouts. However, the positioning of connectors on each cell to achieve interconnection by juxtaposition is not a local issue, and often involves considerations of several levels of the cell hierarchy.

As a corollary to this, once a set of cells and connector positions has been chosen, and a layout is completed, any change to the position of any connector can have a global effect on the layout. As was observed above, such changes can be provoked by any of a large number of causes, even very late in the design. This means that in compact designs that exploit interconnection by juxtaposition, a seemingly minor change to a cell deep in the hierarchy can result in a major reworking of the layout.

Another related problem arising from the use of rigid cells is the observed fact that cell libraries have not achieved widespread usage except in a few limited contexts. These contexts are either in the very large, where a library cell is a whole system for which the overhead of interconnection by wiring is acceptable, or in the very small where the very simplicity of the cell limits the variability of its connector positions, such as in a library of PLA parts. The only other successful library cells have been those which connect very loosely with the rest of the system, bonding pads being the prime example. With these exceptions, the main use of library cells seems to be as exemplars, since they are rarely exactly what is needed but may provide a starting point from which a tailored cell can be derived.

The above observations highlight the need for parameterized cells. These are cells that are not rigid in form, but which can accept parameters that modify the layout to conform to various external requirements. Other parameters can be used to modify the functional or behavioural characteristics of a cell. Modification of logic function is an example of this, though modification of electrical characteristics such as drive capacity is more straightforward.

Several systems have been written that achieve parameterization of cells by embedding layout primitives into a programming language [3]. Execution of the program results in the creation of a specification of the layout. Parameterization is achieved by virtue of its existence in the host programming language chosen. The main difficulty with the programming language approach is that it is extremely difficult to specify the details of a layout by writing a program. Two dimensional relationships between different parts of the layout have no explicit, meaningful representation in a programming language. Consequently, parameterization is achieved at the expense of clarity and ease of modification of the design specification.

This observation led to the development of a system that provided simultaneous graphical and procedural versions of a cell being designed [4]. Aspects of a design that were more easily specified graphically were entered via the graphical representation, and aspects more easily specified procedurally were achieved using the procedural version, and the system kept the two representations coordinated. While this approach directly tackles the problem of accomodating both graphical and procedural representations, the problem for the user in correlating the two representations still exists to some degree. Also, IC designers have to become programmers.

The goal of the present approach is to investigate the degree to which useful cell parameterization can be achieved using purely graphical techniques. The main difficulty with providing for parameterization of cells in an interactive graphical environment is in finding techniques for conveniently specifying parameters. The parameters of main interest here are geometrical in nature. Such parameters can be used to modify the positions of connectors to a cell, and of directly associated internal structures, and to change the geometry of conductors or active devices. These geometric parameters take the form of coordinates of reference points which are used in the definition of coordinates of geometry within the cell.

In any system dealing with parameterized objects it is necessary to deal with the possibility of invalid combinations of parameters. At the very least such invalid combinations should be flagged, and if some corrective action can be taken then so much the better. In the case of geometric parameters, the simplest form of specification of valid parameters takes the form of linear constraints among the reference points. The alternative of associating constraints with the individual items of geometry within the cell leads quickly to an unmanageable explosion in the number of constraints.

Ale is an interactive graphical editor that supports the creation and modification of a hierarchical system of cells. Each cell is defined parametrically, and constraints among the parameters are supported. The parameters take the form of coordinates of referencee points. Coordinates of geometric primitives and instances of other cells, are defined as relative offsets from reference points.

There are two types of reference points - local and parameter. The parameter reference points are bound to values at the time the cell is instanced, much like the formal parameters of procedures in programming languages. The local reference points are defined relative to other reference points, either local or parameter. As such they are analogous to local variables in programming languages. Parameter reference points are therefore the roots of trees of local reference points. The coordinates of items within a cell are defined relative to nodes in these trees.

Constraints are applied to reference points. A constraint is a binary relationship between reference points that specifies a minimum allowed distance between them. Constraints are not only checked, but reference points are moved to resolve any violations.

In keeping with the parallels between Ale cell structures and structures of procedures in programming languages, Ale can generate a complete textual description of the layout in the language Silt [5]. Silt provides a superset of the expressible capabilities of Ale, most notably providing for arbitrary expressions, non-geometric variables and global variables. Part of the continuing development of Ale is to find ways of factoring more of the facilities of Silt into the graphical domain.

Ale has been implemented in Mesa [6] to run on Xerox personal computers. It uses a multiple window display in which each window displays the definition of one cell, Fig. 1. Several windows may give different views of the same cell. Coordinates and control are entered using a mouse, a pointing device with three buttons that controls the position of a cursor on the screen. The buttons are used to determine the function being executed, being loosely divided into menus, selection, and creation.

The menus are pop-up menus that are painted on the screen while the relevant button is depressed, Fig. 1. When the button is released the menu is removed and the function that was under the cursor is executed. By using multiple stacked menus a rich set of commands can be controlled conveniently using just one mouse button.

The only geometric primitives supported in Ale are rectangles, which are defined by their four edges. The position of each horizontal edge is defined relative to a vertical reference point, that is, a reference point on one of the vertical edge of the cell boundary. Vertical edges are similarly defined relative to horizontal reference points. Consequently stretchable rectangles can be defined by making opposite edges relative to different reference points.

Selection applies to edges of rectangles and to reference points. Single edges, adjacent edges, or all edges of a rectangle can be selected with a single button, and all edges within an area can be selected. Exactly one horizontal and one vertical reference point is selected at any one time. All edges of rectangles that are relative to a currently selected reference point are highlighted. This provides dynamic feedback concerning the dependencies in the layout without cluttering the display with this information displayed statically. Selected items can be moved under control of the mouse. For rectangles this implies either stretching each rectangle or moving it bodily, depending on the number of edges currently selected. Reference points are moved along their respective cell boundaries. All motions are supported dynamically, providing continuous feedback to the designer.

Rectangles and reference points are created using a third mouse button. At the time a rectangle is created, its edges are defined relative to the currently selected pair of reference points. This provides for parameterization of the position of the rectangle, but not for its shape. To accomodate this need or to modify an existing dependency, edges can be re-referenced, that is, made relative to different reference points. Indeed, experience has shown that it is more convenient to design a cell initially without regard to dependencies on reference points, and then to re-reference groups of edges to appropriately created reference points.

Fig. 2 shows a single window containing a simple wiring cell. It consists of three conductors that connect to the left and bottom edges of the cell. This much of the definition is unparameterized. Reference points are shown as short lines crossing the boundary of the cell. Parameter reference points have caps on the lines. In Fig. 2 the reference points L1, L2, L3, B1, B2, B3 are all parameter reference points. The other reference points are unnamed, and define the boundary of the cell. The two at the lower left are parameters, while the two at upper right are local, and are defined relative to reference points L3 and B3. While designing this cell the user can experiment with parameters by selecting a reference point and moving it, to see, dynamically, what is the effect on the layout. Fig. 2 shows the cell in its most compact configuration. Although not shown there are constraints between adjacent pairs of connection points, to prevent the conductors from getting too close together.

Fig. 3 shows a cell containing three instances of the wiring cell, with different parameters. The positions of the parameter reference points of each instance are defined graphically, and can depend on different reference points in the calling cell. Fig. 4 shows the Silt code generated by Ale for this case. The Pascal-like syntax should be fairly self explanatory. The wiring cell itself is symbol LB3, and it is called three times from within the other cell, symbol LBEx. The default values are used in place of elided actual parameters

Going back to Fig. 1, the background window shows a cell, Shift, containing two instances of a shift register half cell, HalfShift, which is shown in the foreground window. The other window at the lower left provides a close-up view of part of Shift. The cell HalfShift has five parameter reference points, Vdd, Gnd, in, out, clk, and one local reference point a. The clk reference points of the two instances are dependent on two different reference points of Shift, namely Phi1 and Phi2. The pieces of geometry connecting the rectangles of HalfShift at clk to the boundary of Shift are defined as components of Shift.

Ale has been implemented as a purely interactive tool for creating, modifying, and interconnecting parameterized cells. While it is believed that Ale provides significant benefits as an interactive editor, certain aspects seem amenable to automation. The first of these is in the creation of certain commonly used cells for which the parameterization is richer than can currently be accomodated. The wiring cell is an example. It is fairly straightforward to write a procedure that will generate different configurations of wiring cells, in which the number of conductors, conductor material, and combination of edges are parameters, yet leaving the positions of these conductors as geometric parameters as in the example given. It is not expected that the average designer would write such a procedure. This is because the task of providing for the extended parameters is much more involved than the task of providing the geometric parameters that distort a given cell, in that it requires programming. Other candidates for this treatment are the usual members of cell libraries, but with the added power that stretchable library cells with non-geometric parameters can be defined.

Another area in which automation seems indicated is in the chip assembly process itself. Given the definitions of a number of parameterized cells to be interconnected by juxtaposition, and a specification of the desired connections, the task is to establish the positions of all the parameter reference points, subject to any constraints among them, so that the cells will properly abut to achieve the required interconnection. This is a two dimensional constraint satisfaction problem for which solutions are fairly well understood [7]. Moreover, the process can be extended up the hierarchy to interconnect a whole structure of cells.

At the simplest level, Ale can be used as a conventional graphical editor for designing rigid cells. The ability to selectively parameterize cells makes it possible to defer decisions concerning the exact layout of the cell until it is instantiated, and indeed, to allow different instantiations to differ from one another. It is believed that the provision of optional geometric parameterization, using a purely interactive graphical interface, greatly enhances the acceptability of the system to existing, non-programming, integrated circuit designers.

At the time of writing this draft Ale has not been used to design a large circuit. This is due to the need to remove a number of rough edges in the interface that have little to do with the novel aspects of the system, but which must be resolved before anyone can be expected to undertake the considerable investment in time that it will take to truly test the system on a large layout. The removal of these rough edges and subsequent large scale testing are the subject of current work.