A property is a (key, value) pair. The value is a pointer to an arbitrary Cedar object. A key must be an identifier which is unique across the entire design automation system. There is no automatic detection of key conflicts. Generally each property is associated with a distinct portion of the system. A convention which requires that a property key have a prefix unique to that portion of the system has been sufficient to avoid trouble.

All of the basic data types have a property list, including properties themselves. A most useful property property is a procedure to pretty print the value of the property. A global property key for names is defined to allow systematic naming of all of the objects represented by data types.

Properties are used throughout the system for many purposes. They capture tool specific information such as names or transistor sizes. Properties can be used to store computed data, such as wire capacitance. It is common for a tool to cache its result in the property list of its argument. Properties can record the methods applicable to an object. Finally properties are convenient places for passing information between programs.

Wires represent electrical nodes. In order to capture the notion of a bus and to allow arbitrary grouping of nodes, a wire must be an arborescent data structure. A tree representation for wires would not be sufficient to represent wire permutations, as shown in figure 2.2.1., or to capture multiple groupings of the same nodes. Therefore wires are directed acyclic graphs. A wire representing a single electrical node is called atomic. Non atomic wires are called structured wires, and capture an ordered sequence of sub-wires. The list of wires without parents in a wire DAG is often grouped for convenience in a single wire called a root wire.

The need for wire types, i.e. a data type that describes the structure of a wire independent of its instantiation, never arose.

A cell type represents a device or a collection of devices. In addition to a property list every cell type has a public root wire which represents the electrical nodes that must be bound when the cell type is instantiated. A cell type belongs to a cell class and contains a data field specific to the class. A cell type which belongs to cell class C is referred to as a C cell.

A cell class defines the internal implementation of a cell type. A cell class can be primitive or composite. Primitive cell classes are technology and abstraction specific. In a switch level abstraction of a MOS technology the only primitive is the transistor. In a lumped element circuit abstraction of a technology the primitives include resistors, capacitors, inductances, voltage sources, etc. The unspecified cell class is an unique cell class independent of technology or abstraction. It indicates that the internal composition of a cell type is unknown. Usually, unspecified cells have properties that define their behavior for tools, e.g. the simulator. This allows tools to be applied to partially specified designs.

Composite cell classes are generally technology independent and are used to compose more complex objects out of simpler objects. There is a unique composite cell class, the record cell class, which is the most fundamental cell composition mechanism. The record cell class contains a literal list of instances. Alternatively this cell class could specify a literal list of nets where each net specifies a literal list of instances to which it is connected. Many tools enumerate the instances and the wires bound to the instance instead of enumerating them in the opposite order so this is an empirical decision. Here is the cell type specific class data for the record cell class, stored in the "data" field of every record cell:

Each instance specifies the cell type of the instance and a root wire, called actual, to which the public wire of the instantiated cell type is connected. The public subwires are bound to the actual subwires in a manner analogous to positional parameter notation in programming languauges but applied in a recursive manner. Instances also have a property list just as wires, cell types, and cell classes do.

All of the wires in a cell type of record cell type, including public and all actual wires, can be enumerated from a root wire called the internal.

Every tool which understands composite cell types must understand the record cell class. Every composite cell class except the record cell class must have a procedure, the recast procedure, which defines a translation from the original cell type to a cell type whose cell class is simpler. A finite series of recasts must result in a cell type of record or primitive cell class. In a traditional design aid system architecture, each tool knows how to deal with each class. With the recast mechanism, each tool can define new classes as appropriate, and as long as a recast procedure is supplied for these new classes, no changes need to be made to existing tools. This reduces a problem of size n*p, where n is the number of cell classes and p is the number of tools, to a problem of size n+p.

The cell class is the basic abstraction extension mechanism. Within this single structural framework it allows a cell type to be as complex as a state machine specification or as simple as a single transistor. The recast mechanism is invoked only when some tool is applied to an abstract cell type which it cannot understand. This allows lazy evaluation of the translation from abstract specifications to detailed implementation without requiring explicit sequencing control by the tool user. In addition to extending the set of abstractions available to capture design intent cell classes also allow abstractions with different space/time tradeoffs.

The series of recasts from the original cell type to a cell type with a cell class which is understood by the tool form a chain of cell types, each with its own property list. It is legal for a recast to compute a new property which did not exist on the original cell type. Thus a tool which is looking for a specific public property must continue searching the recast chain until it finds the property it wants or no more recasting is possible. The property search mechanism is further complicated by an inheritance scan of the property list on each cell class of each cell type in a recast chain and a performance optimization which avoids high cost recasts. This inheritance scan allows a property to be put once on the cell class rather than on each cell type of a cell class.

The split between evaluation during net list construction and evaluation during recast depends upon the abstractions which the tool set utilizing the net list support. Typically a new cell class is introduced when some synthesis or analysis tool needs a different abstraction to be captured. If the abstraction is merely structural then the structure is usually built during net list construction.

Printing procedures display properties, wires or cell types of arbitrary classes. Printing is object oriented, i.e. a specialized printing function can be defined for a new class or property. Printing utilities are helpful for debugging, but they are not intended to be used in designer interactions, where graphical feedback is preferred.

There are various procedures for enumerating wire DAGs or wire bindings. Some of these utilities only enumerate atomic wires, so that the implementation of tools which only need to know about atomic wires, such as layout tools, is as simple as if all wires were atomic.

Throughout the system enumerations are the preferred way to visit data structures because enumerations do not require object allocation other than on the program stack.

From the beginning of the system design names have not been mandatory. This forces the user interface to handle graphical abstractions as well as textual. Since names are not mandatory they are expressed as properties and not as fields in the data structure. This improves memory utilization, especially for representing layout where most objects are unnamed.

Any node in a wire DAG can be named. Sibling wires must have unique names. A root wire provides a naming context. Any wire reachable from a root wire has a name which is the concatenation of the names along the path from the root to the wire. If a wire is not explicitly named then its name is its index in its parents sequence of wires, as shown in figure 3.3.1. Functions are provided to construct all the path names for a given wire which is reachable from a root wire and to find a wire given its path name.

A rich set of utilities is provided to ease the creation of properties lists, wires or cell types. But even with these abbreviations, code description of record cells is painful and not very compatible with the concept of minimizing designer input. Therefore the system supplies a higher level set of functions for creating record cells, based on the assumption that public wires are usually named. These functions permit the creation of instances in which only bindings of wires with different names are specified. Arguments of these functions can be either names or wire objects, thus maintaining complete compatibility with the abbreviation utilities. Finally exhaustive error checking is made at the time the record cell is created. This approach offers many advantages compared to the traditional introduction of a hardware description language. It blends perfectly with the rest of the system, does not require yet another language design, is easy to implement (1 module, 10 functions, about 200 lines of Cedar), and most important is semantically simple and easy to understand. The following code fragment constructs an AND gate with an arbitrary number of inputs from a NAND gate and an inverter.

It is common for analysis or synthesis tools to recursively explore the cell type hierarchy while maintaining a binding context. Some tools, such as simulators, flatten the hierarchical net list into a new data structure prior to beginning their operation. Others, such as static checkers, operate on the hierarchical data structure but keep context dependent auxiliary information. Using the model of virtually flattened net lists, the system provides a set of functions useful in the implementation of any of these tools.

These functions operate on two new data types. A flat cell expresses a path from a root cell in the cell hierarchy. A flat wire combines a flat cell and a path from a root wire in a wire DAG. Currently, the only instances found in the path of a flat cell are record cell instances, designated by their index within the sequence of instances in the record cell.

The most basic operation provided is the enumeration of a hierarchical net list data structure. This operation can perform an inorder scan of the net list DAG or it can be directed to scan from a root cell to a target flat cell. The directed scan is useful when a flat cell is given in the context of a root cell type and some tool needs to directly access the data structure of the specified cell type. The enumerator can keep track of wire bindings, i.e. the mapping of the wires of the current cell into the highest level in the cell hierarchy where they were defined.

A tool independent method for controlling enumerations is needed. Cell instances, types or classes or specific flat cells can be marked to define a cut set. During an enumeration the cut set defines where the enumeration cuts off. Portions of the cell DAG below a cut point are not enumerated.

Other functions are provided to print and parse flat cells and flat wires. They are very useful for implementing rudimentary textual user interfaces and for debugging tools. Tools maintaining a flattened representations of the net list generally store flat cells and flat wires as part of their data structures, in order to keep the relation with the hierarchical net list. In this manner all communication with the user can be in terms of his original source. For example the schematic editor has a command for adding a selected wire to the oscilloscope like output of the simulator.

Repetitive structures are very common in custom silicon. The simplest construct in the system for repetitive structures is the sequence cell class. This cell class abstracts one dimensional arrays of a single base cell type. The manner in which the base cells are wired together to form the sequence cell is very stylized. The common cases are covered but not all one dimensional arrays can be described with this abstraction.

Each public wire in the base cell type may belong to one of three different types of connections in the sequence cell type. The wire may be global to the array so that every cell has this wire connected to the same net. The wire may be used to form a bus which has as many elements as the number of cell types in the array. The wire can be stitched from one cell type to the next. An example of this last type of connection is connecting carry out to carry in of a ripple adder.

The sequence cell class abstraction is used by the layout synthesis software to generate layout by abutting the layout of the base cell type with itself as many times as the cardinality of the sequence cell. Other uses of this abstraction, e.g. speedup of a hierarchical DRC, can be imagined but are not currently implemented.

Custom silicon often comprises areas where a small number of tile types are abutted in rows and columns to form the layout. Common examples of tilings are PLAs, ROMs, decoders, and mask generators. A tiling cell type is specified by an array of cell types and two functions, one for each dimension, that enumerates the stitches between two neighbors, i.e. the list of pairs of public wires bound together.

The conceptual information conveyed by tiling cells is different from sequence cells. They allow for several different base cell types and the binding of the subcells is performed by pairwise enumeration.

Without a special representation tiling areas are usually the major memory consumer in the representation of a custom chip. A tiling cell is much more compact than its equivalent record cell, and even more compact than two levels of record cell (the first level expressing either rows or columns). Table 4.2.1. summarizes the space consumed for these three representations in the case of the AND plane of a PLA.

The recast mechanism is useful for dealing with pragmatic system issues as well as abstraction levels. Memory space and computational requirements sometimes require storing intermediate results in a file. The import cell class allows the internal structure of an arbitrary cell type to be represented by a file name. When the cell type is recasted the file is opened and the internal structure is read into memory.

A prototypical abstract representation of a digital network is a finite state machine. In this system a finite state machine is just another cell class which has a very heavy weight recast procedure. Properties of a finite state machine cell parameterize the translation. Different heuristics for state assignment and combinatorial network synthesis and different layout styles such as standard cell or PLA are selected. Typically designers simulate their machines at a level of abstraction in which the states, transitions, and outputs are the primitives. The translation to layout proceeds after the machine is debugged at this abstract specification level.

Several chips have been or are being designed with tools based on this structural description. Amongst working circuits is a two-chip processor, totaling about 100,000 transistors. The most recently completed design is a small custom interface chip, almost 11,000 transistors, entirely designed in 3 man months.

Various tools have been designed specifically for a given chip before being made available as general tools. A more complete review of the chips designed with this system can be found in [1].

Approximately 12 man years have been invested in building the design automation system for which this data structure serves as one of the foundations. This system contains about 200K lines of source, exclusive of the graphics editor.

The system has evolved rather than following a grand design. The form of the data structures and algorithms for relating flattened representations to the hierarchical representation presented in section 3.5 became apparent during development of the simulator. An attempt was made to design this functionality during the initial development of the structural representation. This attempt was unsuccessful because the client program needs were not sufficiently well understood.

No source information is stored by this data structure or any of the tools which depend on it. This eliminated stringent testing to ensure no loss of source information and enabled rapid evolution of the system to meet user requirements.

All the data structures necessary for capture, synthesis, and analysis were assumed to fit inside of the 32 megabyte virtual address space of the Dorado. It has been a battle to fit the largest chips into this space. This battle was temporarily lost and a checkpoint facility was introduced to write partial results on the disk. Through improvements of data structures and algorithms the need for checkpoints because of space constraints has been eliminated. They are still used as caches to avoid extracting library net lists each time a library element is used. In retrospect the elimination of consideration of secondary storage management was a good decision. It allowed focus to be placed upon clean design without all the confusion that such storage management would have added.

The design and implementation of intermediate file formats has been completely eliminated. Tools in the old system which used net lists for their primary input description had over half the source code devoted to printing and parsing. Since all data structures from the original source representation to the representations used by the tools are all in memory at the same time it has been fairly easy to link them together. For example the schematic capture program and the simulator, which are two very independent programs, are linked tightly enough that a designer can select a rectangle in his schematic and invoke a command which displays the waveform of the wire represented by that rectangle.

The extensibility of the structural representation worked out very well. Very few substantial changes to the semantics of the structural representation were made after its initial definition. The property inheritance scheme mentioned in section 2.4 was added. Recast was redefined so that recast procedures may return the same cell type, suitably modified, rather than requiring a completely new cell type be constructed. Wires were initially defined as trees but during the design of the schematic capture program it became clear that the generality of a directed acyclic graph representation is needed.

The assumption that cells and wires are immutable, with the exception of properties and recasts with side effects, simplified the system design. Relying on the Cedar garbage collector to recover unused objects greatly reduced the complexity of tools and communication between tools.

The current instance binding mechanism is costly and inflexible. A class mechanism which discriminates on cell type or cell instance would allow experimentation with better methods. Wires are by far the most space consuming data in this representation. Frequently this is because a designer has described the physical cell structure as slices across a data path and the many wires which run orthogonal to the slicing structure must be repeated in every cell. Wires are often carried deep into a hierarchy and the wires must be represented at each level.

The recast mechanism currently returns a whole new cell type. It could compute a new representation of only the internal structure of the cell. This would eliminate the complex and inefficient property inheritance scheme mentioned in section 2.4.

Many of our tools, especially the simulators, flatten the hierarchy prior to doing their work. A standard flattened representation which maintains the links to the original hierarchical representation could reduce the amount of tool specific code substantially by eliminating the flattening code and much of the user interface code.

The physical and logical descriptions of a circuit must be isomorphic in order to back annotate the logical description with physical properties such as wire capacitance. Property lists which are context dependent would allow removal of the isomorphism restriction. A context dependent property carries the path to the parent cell which forms the context. Any tool searching for a property which might be context dependent must supply the current path from the root cell in order to find the correct value of a property.

Breaking the structural to physical isomorphism must be more general than just context dependent properties. The schematics which designers currently draw do not reflect the functional view of a design but rather the physical design. Two structural descriptions are needed, one functional which terminates at fairly high level behavioral components, and another physical, much the same as what exists now. These descriptions must be able to share common pieces so a single data structure must represent both. The physical description should not be required to specify connections already specified by the functional description. A physical cell decomposition which parallels the logical description and partially specifies interconnect, in order to guide layout generation, is needed. Checking procedures to ensure that the logical and physical representations match the functional description's leaf cell behavior are also needed.

The current specification of behavior uses Cedar procedures. These procedures are not easily manipulated. Automatic synthesis of structure from behavior, and tools to check that the implementation of behavior is correct, are difficult to implement because of this. Temporal information also needs better representation.

The issue of persistent data storage has been completely sidestepped by this representation. When designs are captured directly by the structural representation data structure then the issue of persistent storage of captured and computed data will have to be dealt with.

Currently each source change causes the structural description to be rebuilt before any tools are applied. Some caching occurs at the cell type level but the model of computation is essentially a batch procedural one where objects are immutable once built. All of the tools follow this batch model. No results are saved from the analysis of one structure to the next when only minor changes are made. For larger chips this model leads to source change and simulate loops which last 30 minutes or longer. Changing the model to one in which the objects are mutable and computed incrementally may require fundamental changes to the structural representation. Layout and simulation are both areas where significant performance improvements could be realized from this change in model. This requires changes to the design capture mechanisms, the intermediate form described in this paper, and the tools.

A lot of programming effort was expended because of lack of sufficient virtual memory. Many optimizations had to be created in a fire fighting fashion so that larger chips, 50,000 to 100,000 transistors, could be completed quickly. A larger virtual memory would allow space to be traded for ill thought out hacks because some design ran into a brick wall.

The programming environment currently has a single language. The capability of running languages which are compatible with other design automation efforts is critical for building a complete system which remains at the state of the art. Some tools have been recently integrated through the use of remote procedure calls but there is a need to tightly integrate interactive programs written elsewhere into our design aid system.