Introduction
Over the past few years, a new system for describing circuits and generating layout has been developed in the Computer Science Laboratory at Xerox PARC. The validity of this automation system has been demonstrated by the successful design of several major chips. The system is fairly complete, in the sense that it includes tools for design capture, layout generation, analysis and verification. The three most orginal aspects of the system are: a single extensible data structure, a mechanism for the capture of high-level design abstractions, and the layout generation framework.
The first chapter covers the data structure that acts as the backbone of the automation system. The conceptual integrity of the structure, its rich expressive power, and its high extensibility are emphasized throughout the chapter. The second chapter concentrates on the capture of designs as a mix of programs and annotated schematics. Schematics can be parameterized; therefore they graphically describe net list generators, rather than just net lists. This chapter also presents statistics for some of the chips designed with the system. The third chapter presents the framework for generating layout, along with some examples of layout generators. Finally, the last chapter is a collection of examples, illustrating some of the previous points.
This report is an edited collection of papers. Three of them [Barth et al. 1, Barth et al. 2, Barth et al. 3] were presented at the 25th ACM/IEEE Design Automation Conference (Anaheim, June 1988). The fourth paper [Monier 3] was presented at MicroElectronics 88 (Sydney, May 1988). An earlier version of the Design Capture paper [Barth et al. 4] was presented at the Fifth MIT Conference (Boston, March 1988). The development of a state-of-the-art DA system cannot be dissociated from the development of state-of-the-art circuits. Many designers at PARC, mainly in the Dragon project, have acted both as alpha-users and developers, providing ample feedback, challenging requests, new libraries, and generators. In addition to the authors, Giordano Beretta, Lissy Bland, Don Curry, Jean-Marc Frailong, Jim Gasbarro, Christian Jacobi, Christian LeCocq, Ed McCreight, Bryan Preas, and Michael Spreitzer also left paw-prints on the DA system. Another development of the Xerox PARC Computer Science Laboratory, the Cedar programming environment, has to take credit for enabling quick prototyping and development of the system. Finally, none of this work would be possible without the research environment so graciously provided by Xerox.
A Structural Representation for VLSI Design
1. Introduction
The representation and management of VLSI design data has been the focus of intense scrutiny over the last few years. These efforts range from traditional database issues such as access synchronization and version management [Katz et al.] to data structures that represent specific views of a design [Knapp et al.]. Models of design representation that break design data into specific views, such as behavioral, structural, and physical, in which each view is further decomposed into multiple levels of abstraction, have also been proposed [Gajski et al., Harrison et al., Walker et al.].
This chapter describes a data structure for the structural representation of a design with an extensible set of abstractions. This data structure does not deal with traditional database issues nor is it a hardware description language. Rather it is an intermediate form that resides between design capture and design tools. Frameworks for design capture and layout synthesis which utilize this intermediate form are discussed in the following chapters.
In many respects, this data structure is a parsimonious implementation of previous ideas [Chailloux et al., Luk et al., LaPotin et al., Serlet 1]. A small number of data types are used to represent the fundamental structure of a hierarchical net list. These data types are liberally sprinkled with property lists to allow arbitrary annotations to be placed upon the data structure. Instead of a fixed set of device types, a universal device interface with a class mechanism facilitates new abstractions. Procedural translation from one abstraction to another allows new abstractions to be added to the system without requiring modification of all the tools.
A partial design automation system already existed at Xerox PARC when the design of this data structure began. It contained a high-quality layout editor and plotting and mask-making software, which are still in use today. In addition, an enhanced MOSSIM II [Bryant] switch level simulator, a transient analysis circuit simulator, and a combined DRC and extraction program were available, each with its own notion of net list specifications.
This software is implemented in the Cedar programming environment [Schmidt, Swinehart et al., Teitelman] running on Dorado computers [Pier]. The automatic storage management facilities of Cedar, notably an incremental garbage collector, and Cedar support for procedure variables, allowing widespread use of the object-oriented paradigm [Serlet 2], were influential in the design of our data structures and of the programs for manipulating them.
The major users of this software are the designers of the Dragon computer system [Monier et al. 1]. The additional tool requirements to support the Dragon design included integration of the simulators with a better design capture, synthesis, and analysis system. These additional requirements needed to be met quickly, so we took a fairly conservative approach to the design and implementation. The data structure presented here provided the nucleus of the additional tools needed to satisfy those requirements.
The following sections describe the basic data types of, and operations upon, the data structure and some abstract classes of design representation. The chapter concludes with results and plans for future work.
2. Basic Data Types
Only four data types are needed to define the annotated, hierarchical, net list: property, wire, cell type, and cell class. Net lists are composed hierarchically to form a directed acyclic graph (DAG) in which nodes are cell types and edges are instances of these cell types. We show the corresponding declarations for the data types in a Pascal-like syntax.
2.1 Property
Properties: TYPE = LIST OF RECORD [key: STRING, value: POINTER];
A property is composed of a key and a value. The value is a pointer to an arbitrary Cedar object. A key must be an identifier that 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 that a property key has a prefix unique to that portion of the system has been sufficient to avoid trouble. Most of the basic data types have property lists. A standard property key is used for naming objects. We use annotation as a synonym for property.
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.
2.2 Wire
Wire:
TYPE =
POINTER TO RECORD [
properties: Properties ← NIL,
elements: ARRAY size: INTEGER OF Wire];
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 indicate wire permutations, as shown in figure 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 wires without parents in a wire DAG are often grouped for convenience in a single wire called a root wire.
The need for wire types, i.e., data types describing the structure of wires independent of their instantiations, never arose.
2.3 Cell Type
CellType:
TYPE =
POINTER TO RECORD [
class: CellClass,
public: Wire,
data: POINTER ← NIL,
properties: Properties ← NIL];
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 that 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.
2.4 Cell Class
CellClass:
TYPE =
POINTER TO RECORD [
name: STRING,
recast: RecastProc ← NIL,
properties: Properties ← NIL];
RecastProc: TYPE = PROCEDURE [CellType] RETURNS [CellType];
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 a 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., for 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. A composite cell class, the record cell class, 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 would specify a literal list of instances to which it is connected. Both representations are equivalent. We chose the former because many tools enumerate the instances and the wires bound to the instances rather than enumerating wires and their related instances. The cell-type-specific class data for the record cell class is stored in the ``data'' field of every record cell:
RecordCellType:
TYPE =
POINTER TO RECORD [
internal: Wire,
instances: ARRAY size: INTEGER OF CellInstance];
CellInstance:
TYPE =
POINTER TO RECORD [
actual: Wire,
type: CellType,
properties: Properties ← NIL];
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 languages but applied in a recursive manner. Instances have property lists, as do wires, cell types, and cell classes. All of the wires in a record cell, including the public and all actual wires, can be enumerated from a root wire called the internal.
Every tool that 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, that 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 each of 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. This single structural framework 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 when a tool is applied to a cell type it does not understand. This allows lazy evaluation of the translation from abstract specifications to detailed implementation without requiring sequencing control by the tool user. Cell classes extend the set of abstractions available to capture design intent. In addition, they allow abstractions with different space/time tradeoffs.
The series of recasts from the original cell type to a cell type 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 that did not exist on the original cell type. Thus a tool that is looking for a specific public property must continue searching the recast chain until it finds the property it wants or until 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 by a performance optimization that avoids high cost recasts.
The split between computation during net list construction and computation during recast depends upon the abstractions supported by the tool set that uses the net list. 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.
3. Operations
This section presents operations available as Cedar modules for manipulating the net list.
3.1 Printing
Printing procedures display properties, wires, or cell types of arbitrary classes. Printing is object-oriented, i.e., a specialized printing function can be customized 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.
3.2 Wire Enumerations
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 that 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 traverse data structures because they do not require object allocation other than on the program stack.
3.3 Wire Naming
Names are not mandatory throughout the system. 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 the index in its parent's sequence of wires, as shown in figure 2. Functions are provided to construct all the path names for a given wire reachable from a root wire, and to find a wire given its path name.
3.4 Creation Conveniences
A rich set of utilities is provided to ease the creation of properties lists, wires, and cell types. But even with these abbreviations, code description of record cells is awkward and not quite 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 performed 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, and is easy to implement (1 module, 10 functions, about 200 lines of Cedar source code). Most importantly, the designer's model is simple. Figure 3 illustrates this on the construction of a decoder with
n inputs.
3.5 Flattening
It is common for analysis or synthesis tools to explore the cell type hierarchy recursively while maintaining a binding context. Some tools, such as simulators, flatten the hierarchical net list into a new data structure prior to their operation. Others, such as static checkers, operate on the hierarchical data structure but retain 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, and a flat wire combines a flat cell and a path from a root wire in a wire DAG. Currently, each instance found in the path of a flat cell is a record cell instance, designated by its index within the sequence of instances in its parent record cell.
The most basic operation provided is the enumeration of a hierarchical net list data structure. This operation can perform an in-order 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 when 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, classes, or even 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 representation of the net list generally store flat cells and flat wires as part of their data structures, in order to retain 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.
4. Abstract Cell Classes
In this section, we present some of the composition classes introduced to capture higher-level concepts than the standard record cell class. All these classes eventually recast into record cells. This is not an exhaustive list. Some styles of layout, e.g., Alps [Serlet 3], are better represented by special-purpose abstractions that will not be presented here.
4.1 Sequence
Repetitive structures are 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 somewhat restricted. The common cases are covered but not all unidimensional 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 that has as many elements as the number of cell types in the array, or the wire may be stitched from one cell type to the next. An example of this last type of connection is connecting carry-out to carry-in in a ripple adder.
The sequence cell 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 specified by the sequence cell. Other uses of this abstraction, e.g., speedup of a hierarchical DRC, can be imagined but are not currently implemented.
4.2 Tiling
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 enumerate 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).
4.3 Import
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 first recast the file is opened and the internal structure is read into memory.
4.4 Finite State Machine
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 that has a very heavyweight 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 cells or PLA, can be 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.
5. Results
5.1 Designs
Several chips have been or are being designed with tools based on this structural description. Among working circuits is a two-chip processor, totaling about 100,000 transistors. A recently-completed circuit is a small custom interface chip, containing almost 11,000 transistors, whose design was completed 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 the next chapter.
5.2 Observations
Approximately 12 man-years have been invested in building the design automation system that uses this data structure as one of its 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, which were 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 needs of the client program were not sufficiently well understood.
No source information is stored by this data structure or by any of the tools that 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 within the 32-megabyte virtual address space of the Dorado. It has been a battle to fit the largest chips into this space. At one point, this battle was temporarily lost and a checkpoint facility introduced to write partial results on the disk. Through improvements of data structures and algorithms, the need for checkpoints due to 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, avoiding 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.
Tools in the pre-existing automation system had over half the source code devoted to printing and parsing. We have completely eliminated intermediate file formats. Since all data structures, from the original source representation to the representations used by the tools, are in memory at the same time, it has been fairly easy to link them together. For example, the schematic capture program and the simulator, two quite unrelated programs, are linked tightly enough that a designer can select a rectangle in his schematic and invoke a command that displays the waveform of the wire represented by that rectangle.
The extensibility of the structural representation worked out well. Few substantial changes to the semantics of the structural representation had to be made after its initial definition. One exception: wires were initially defined as trees but, during the design of the schematic capture program, it became clear that the generality of a DAG representation was needed.
We assumed from the start that cells and wires were immutable, with the exception of properties. That assumption significantly simplified the system design. Relying on the Cedar garbage collector to recover the storage occupied by unused objects greatly reduced the complexity of tools, as well as communication between tools.
6. Future Work
This section describes possible improvements to design representation, to the computational model for programs that create the representation, and to the underlying programming environment. These changes would improve either designer or tool efficiency, or would improve support for a wider range of design methodologies.
6.1 Representation
The current instance binding mechanism is costly and inflexible. A class mechanism that 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 because the many wires that 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. The current mechanism is adequate for all tools, but a standard flattened representation could maintain the links to the original hierarchical representation. This would further reduce the amount of tool-specific code by eliminating both 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. Context-dependent property lists would allow removal of the isomorphism restriction. A context-dependent property would carry the path to the parent cell forming the context. Any tool searching for a property that might be context-dependent would have to supply the current path from the root cell in order to find the correct value of a property.
The provision for breaking the structural-to-physical isomorphism must be more general than just context-dependent properties. The schematics that 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 interconnections to guide layout generation, is needed. In such a scheme, 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.
6.2 Computation Model
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 in which 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, even if only minor changes have been made. For large chips, this model leads to source-change-and-simulate loops that 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.
6.3 Environment
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 introduced because some design ran into a brick wall.
The programming environment currently supports a single language. Added capability to run languages compatible with other design automation systems is critical for building a complete system that remains at the state of the art. Some tools have recently been 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.
7. Summary
An extensible data structure for the representation of the structure of VLSI devices has been presented. The utility of this data structure has been demonstrated by the design automation system quickly constructed on top of it and by the integrated circuits built using that system. Finally, we have sketched some ideas for improving the representation of designs, the computational paradigm used by the tools, and the software development environment.
Parameterized Schematics
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 conventional programming languages, or specialized hardware description languages [Barbacci, German et al., Piloty et al., Shahdad et al. 1, Shahdad2]. These systems offer great flexibility, but a textual description of structure is often harder to understand and manipulate than a graphical one. Recent work has attempted to overcome these drawbacks by defining graphical languages that permit flexible specification via schematics [Lieberherr, Nash et al.]. 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 chapter 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/her design; consequently, it is easier to create, modify, and maintain as well. The intermixing naturally 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 the next chapter.
The particular way in which we have integrated text and graphics was influenced strongly by our programming environment. Rather than designing 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: first, it has resulted in an extensible system, one in which there is no distinction between built-in abstractions and user-defined ones, and where new abstractions may be added easily; second, 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 chapter 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 resulting layout. Accordingly, the next section begins with the model for net list generation. Subsequent sections provide implementation details, 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 a program that will be executed, or by 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 the merged result. Thus, the evaluation of a single net list generator may entail many levels of schematic extraction and/or program 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. This extract method provides the link from geometry to program. The reverse link is provided simply by making the extractor available as a function that can be called from user program.
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 non-text objects or their instances; 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 masters' extract methods. Figure 1(a) shows an icon whose net list happens to be represented by a simple schematic. The schematic is a composition that contains transistor icons, an inverter icon, the rectangles that connect them, and satellites that serve to name nets and specify transistor sizes. Figure 1(b) shows a more complicated example.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 1. Examples of schematics and their icons
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 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.
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. This context is computed by applying the results of satellite evaluation to the old context, and 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 programs and schematics embodied in this model can be thought of as a more powerful language for describing designs. This language has three desirable attributes: extensibility, orthogonality, and homogeneity.
The language is extensible 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 programs. Icons, for example, provide a direct graphical link to arbitrarily complex user procedures. Users can exploit this connection to define simple constructors, such as arrays of cells and subrange selectors from a bus, or more complicated ones, such as data path and finite-state-machine generators.
The language is orthogonal because we avoided duplicating those concepts in graphics that are better handled by programs. 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 programs. This works well since net list generators that capture structural decompositions are often declarative—better expressed pictorially—while generators that reflect algorithms are more easily expressed by programs.
The language exhibits homogeneity in the sense that programs 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 derives from the bidirectional linkage between geometry and programs.
3. Implementation
3.1 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. A more detailed treatment may be found in the first chapter.
3.2 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 for 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 implementation performs a number of checks to ensure that invariants required by the net list data structure are maintained. An example of user program can be found in the previous chapter.
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. It avoids a separate language for hardware design, so it is easier to implement. Also, utilities may be added and improved piecemeal, allowing an evolutionary system development that is much harder to do in a language-based system once the language is fixed.
3.3 Schematic Extraction
The task of the schematic extractor is to turn a combination of pictures and programs into a net list. As outlined earlier, the extractor proceeds top-down in a recursive context-sensitive 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 instances and objects. Included in the extraction context 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.
Satellite evaluation is implemented so that instance satellites have precedence over object satellites. This allows defaults to be specified by object satellites and overridden by instance satellites. Some syntactic sugar differentiates between variable definitions or assignments and net list annotations. Table 1 provides syntax, semantics and examples of satellites.
3.4 User Interface
Each net list generated by the extractor is annotated with all the graphical objects that 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 may 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 program. A powerful disambiguation mechanism was introduced for cases that do not exhibit 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 in several contexts.
4. Results
Since its initial implementation in early 1986, the system has been used to describe over a dozen VLSI chips of varying sizes and complexities. Some of these chips have been fabricated while others are in the final stages of design.
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 supply statistics that form the basis for further discussion.
4.1 Chip Design Cycle
Figure 2 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 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 design of a real chip rarely follows such a simplistic path. More often than not, there is considerable overlap between stages: the design involves more than a simple 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 as shown in figure 3. This process closely resembles the load-run-think-modify-compile cycle so familiar to programmers. Ideally, as with programming, one would prefer a system in which most of the time around the loop is devoted to thinking about solutions (stage C).
4.2 Chip Designs and Statistics
Table 2 shows the layout styles and development times for chips that have been designed using the system (the numbers in parenthesis indicate 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 styles vary all the way from pure synthesis, through standard cells, to full custom (FC), while the design times range from a day to over two years. Of the 14 chips represented, six have been fabricated and tested (at least for functionality); four are currently under test; three are just entering the layout production and verification stage; one will be sent to fabrication soon. A figure that helps put the design capture system in proper perspective is the fraction of time spent in design capture/simulation/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 improvement in the design capture system would have a significant impact on the overall design time.
Table 3 shows various size statistics for the 14 chips. The area and transistor counts indicate that several of the chips are moderate to large by today's standards, thus constituting a serious test of the design system. The schematic and program sizes show that while most of the descriptions are dominated by schematics, sizable fractions of a few descriptions are by program, and most utilize some code.
Finally, Table 4 provides data that helps give a feel for the time around the debug loop (the letters in parenthesis 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. Adding a selected wire to the oscilloscope-like output of the logic simulator typically takes less than a second. These numbers are for complete chips rather than for chip sub-blocks.
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 of speed improvement before they would 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 define a piece of the design (the case with C8 and C11), then this piece is sometimes recomputed even if it 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 cannot 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 a workable system quickly because other researchers depended on the results of our work. This caused us to decide to use the existing graphical editor, and to postpone building a completely incremental system. This section discusses some of the system's basic design decisions, noting which ones were successful, which ones weren't, and where we encountered unexpected difficulty.
5.1 Parameterized Schematics
Our provision of parameterized schematics works well. Parameterization allows our designers to delay decisions such as the number of lines in a processor cache, the number of bits per line, and even the number of bits in a data path. Designers can therefore debug their design with the smallest feasible size, and confidently expect that the full-sized version also works. For chip C3 this technique changed the time around the debug loop by an order of magnitude. Delaying size decisions has the additional side benefit of allowing processor-cache capacity analysis to proceed in parallel with the description—potentially speeding up the schedule.
Parameterized schematics also permit us to annotate schematics with layout information. 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 the next chapter.
Parameterization did, however, complicate the system's implementation. 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). Actually this information is only available after a parameter-dependent extraction, and cannot be derived simply from the geometry.
5.2 Extensible System
Our decision to build an extensible system has also worked well. The extractor has been implemented using an object-oriented model in which each instance of a graphical object has its own procedure to interpret it. This is an advantage for the CAD programmer who maintains the system since it results in a simple structure. It is also beneficial for the VLSI designer because it keeps the mental model of the extractor quite simple. The key aspect, however, is that this model has proved easy to extend, and we have added several new graphical items since the system's initial design.
For example, we have introduced a variety of graphical items that generate Spice [Nagel] primitives such as diodes, resistors, voltage or current probes, and voltage generators. We applied the same principle to driving our mixed-mode simulator. Test vectors are applied by using digital signal-generator icons or supplying the name of a test vector file in a special icon. The graphical appearance is similar to a physical electronics workbench. This eliminates the need for hard-to-read command files and keeps the testing information bundled with the design source.
An advantage of extensibility is that it freed us from having to write a large number of graphical primitives before the system was useful. It allows these primitives to be added on demand and provides freedom to experiment with alternatives before selecting one. We 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.
It is difficult to design a unified sequence operator that is general enough to cover all of the applications on hand. Part of the problem is determining how close to the layout geometry one wants the schematic representation. One extreme is the geometric sequencing model, in which the sequencing is identical to the layout. The other 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 is conceptually very simple, though we find it more difficult to provide generality in this model. On the other hand, it is easier to provide generality in the logical sequencing model, but it is more cumbersome to use.
5.3 Extractor Implementation
The schematic extractor and the layout extractor use a common geometry engine. This may seem strange 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. It also allows net list construction to depend on the names of wires as well as on geometric features. On the other hand, layout extractors have fairly sophisticated rectangle intersection algorithms that may appear to be overkill for schematic extraction. In our experience, 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 intricate code.
In implementing the connection of graphics to programs, we employed an interpreter for the local programming language to evaluate satellites. This use of the interpreter provided us with a great deal of flexibility, since it allowed general 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 loaded program. Along with this flexibility also came a speed liability. Currently, about half of the extraction time is spent in the interpreter. Straightforward use of the interpreter means that every time a schematic is reextracted expressions have to be reparsed and reevaluated.
In our object-oriented model, the order in which instances are extracted cannot be controlled. This causes the same information to be specified more often than necessary. For example, when we select a component wire from a bus, the size of the bus must be specified within each selector. This is needed 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 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. This approach was also inefficient because the interpreter was invoked more often in calling the extract method. Our second attempt eliminates result expressions and has hidden properties from which the extract method can be inferred. This solution is not quite 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
When we started building the system, we had a high quality layout editor available to us. In one respect this was a bonus because it left us free to implement higher levels of the design capture system. However, the editor had some drawbacks, particularly with regard to displaying annotations. We found it useful to provide designers the option of hiding information to avoid clutter. However, it was extremely awkward if the system required all information to be hidden. Our editor did impose this constraint, and so we implemented satellites, i.e., properties that could be made visible or not and whose position and looks could be controlled entirely by the designer.
The editor does not impose any semantics on geometry, a property that allows the same editor to be used for both layout and schematics. This simplifies both the user model and the implementors' task, but it also implies that we have to reintersect rectangles each time an object is extracted. The slowdown caused by reintersection is ameliorated by result caching but, as we pointed out earlier, caching does not work as well as we would like. Another problem with semantic-free editing is that the editor cannot discover syntactic errors interactively. In our case, the extractor locates 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, particularly 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 that is best done in the context of many real designs.
Sequences have received a great deal of attention, but we have yet to find a way to both express the frequent tilings of a two dimensional plane with a single cell type, and combine power with conceptual simplicity. The wiring between cells, aggregation of wires into buses, and index dependence are just a few of the issues that 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 that are 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. Truly 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. We have observed that 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 an order of magnitude.
The satellites concept, introduced after the editor was written, was not well integrated, causing some of the information that guides extraction to be hidden. 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. There is caching that makes this process partially incremental, but the model is still one of complete reexecution of the generation function. A preferable model would change the contents of the net list incrementally when the net list generator changes. In our current model, every cell can be an arbitrary function of the subcells. Thus, every cell type, from the changed cell type all the way to the root, 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 a sound one 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 at the level of whole documents. We need to reduce this granularity, so that we can have a single document that permits free intermixing of comments, programs, schematics, layout, timing diagrams, and other information. This has the added advantage that it couples well with ongoing document management work at PARC.
7. Summary
We have described an extensible design capture system based on the notion of net list generators. Permitting generators to be specified with a combination of both traditional schematics as well as programs in an existing language leverages the familiarity that 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 changes that need to be made for improving the system.
PatchWork: Layout from Schematic Annotations
1. Introduction
Layout generation systems solve two problems. The first is the elimination of tedious, error-prone hand-layout assembly. This is especially important during the assembly of a large chip, when the resolution of the editing display is not sufficient to accurately position sub-blocks [Monier et al. 2]. The second is the capture of design knowledge in a parameterized form so that it may be reused [Buric et al., Matheson et al.].
Some layout generation systems use textual programming languages and have fixed operator sets. Others use menus or tables for capturing the parameters of blocks. Only tool developers can really extend these systems, and generators cover only the common cases because of the large development effort. At best, a tenuous connection to the logical representation of a design is formed. Some generators synthesize rectangles and focus on detailed leaf cell synthesis rather than whole chip assembly. For many full custom design systems the truth is in the layout. In these systems, schematics are an independent description used for comparison late in the design process.
Our layout sub-system, PatchWork, is so easy to use that every chip design can be a parameterized generator. This expands the base of generators with more and more abstract blocks, lifting the level of design description so that designers are more productive. PatchWork describes layout generators through a mixture of annotated schematics and programs. Thus the designer can pick the medium that best expresses his intent. Some of the layout information, such as relative position, is captured by drawing the schematic with a particular style. Entire chips can be completely described with schematics that do not require hardware designers to acquire programming skills. PatchWork is sufficiently powerful that libraries of common generators and macros written by experts can be quickly copied and customized by users. The resulting circuit descriptions can be simulated in addition to producing layout. New layout primitives are easily added.
In this chapter we present the basic schematic annotations for synthesizing and assembling layout, the overall layout generation framework, and our experience in using it for several designs. Finally, we discuss the extension of our silicon assembler towards the mythical silicon compiler.
2. Basic annotations
Let's define some terminology. At any level the hierarchical description of a circuit may consist of a schematic, an icon, and a layout. The schematic is the hierarchical description of the structure of the cell, expressed in terms of subcells. Leaf cells belong to atomic classes such as transistors. An icon summarizes the interface of the cell in a dense form. It simply describes the ports of the cell. Finally, the layout for the cell is assembled recursively from the layout of its components. In our system, schematics and layouts can be mixed in the same design, since the same editor is used to draw both. This has the advantage that designers only need to be familiar with a single graphical editor.
The designer annotates his schematic to specify the corresponding layout. This is done by including in the schematic a visible annotation Layout whose value is a preregistered key corresponding to a layout generator. Other annotations might provide extra parameters for the layout generation. An interactive command allows the designer to select the schematic and ask for its layout. At this point the layout is generated and displayed. Further commands allow the extraction of the net list and highlighting of all the rectangles belonging to a single electrical node.
The rest of this section presents examples, of increasing complexity, illustrating the use of layout annotations.
2.1 Hand Drawn layout
The hierarchical description of a circuit starts at the level of a leaf cell, i.e., a library cell or a critical cell. A designer uses the graphical editor to draw the schematic of a leaf cell with primitive objects (usually transistors or gates) and a layout for the same cell (figure 1).
He annotates his schematic with the visible property Layout: Get. Another property indicates the design from which the layout should be fetched. In the example in figure 1, a private design is used, which is indicated by the property: Design: ``LouisPrivateLibrary''. Producing the layout in this case is especially simple; the layout cell is simply fetched, extracted and checked for conformance to the schematic.
Leaf cell layout does not have to be produced by hand: it could be imported from another system (e.g., CIF reader), synthesized from a net list and interface constraints, or generated by a compactor from a sticks diagram. The corresponding generators would be quite similar to Get.
[Artwork node; type 'ArtworkInterpress on' to command tool]
2.2 Abutment
The simplest composition operator in PatchWork is the abut operator. Assuming that a cell is composed of a list of subcells whose abutment rectangles share a common dimension, its layout is the abutment of the layout of the subcells in the appropriate direction. We build almost all regular structures with this operator.
Figure 2 shows an example of horizontal abutment. The direction of abutment and the order of the subcells is implied by the schematic drawing. Ports must match so that after abutment the resulting net list is identical to that of the schematic.
[Artwork node; type 'ArtworkInterpress on' to command tool]
2.3 Routing
A higher-level operator invokes a channel router. Given two cells, the layout generator returns the abutment of the first cell, the routed channel, and the second cell. The channel is defined by
parsing the schematic. All wires that need to be connected and that appear on the appropriate side of the subcells' layout will be connected in the channel. The actual ordering of the subcells' wires may differ between the layout and schematic. Wires appearing on the exits of the channel are by convention found on the corresponding sides of the schematic. All router options, such as channel width or minimum net width, are explicit annotations in the schematic.
2.4 Standard Cell
A more powerful operator assembles standard cell blocks. The schematic is flattened so that the original hierarchy is ignored. The positions of the wires of the schematic define the sides from which the layout of those wires must exit. The relative ordering of wires in the schematic is used as a hint for the placer.
The standard cell operator accepts as a leaf any cell whose layout follows a number of rules such as standard height and standard position of the power rails. It may be hand drawn, the result of an abutment, or produced by a program from a symbolic description. As with the router, many standard cell options are controlled through visible properties, e.g., the number of rows, defaulting to a square aspect ratio.
A similar generator, SCRemote, utilizes a different placer on a remote server. The interface of the two generators is exactly the same.
3. Model
In order to understand how we integrate generators in our environment, it is necessary to review some of the data structures of our implementation.
Our most basic data structure is purely geometric and is the physical representation of layout. Primitive physical classes are rectangles, MOS transistors, contacts, and polygons. Composite classes include structured cells and abutments. In order to allow the abutment operator to deal with slightly overlapping cells, there is an abutment rectangle defined for each physical object. This rectangle may be set by the layout editor and defaults to the bounding box.
We extend this physical data structure with other atomic classes, such as text, in order to represent schematics. A side benefit of using the same data structure for both purposes—layout and schematics—is uniformity of user and programming interfaces.
In the data structure for structural representation as presented in the first chapter, a cell is either primitive, such as a transistor or behavioral cell, or composite. Every cell has an interface consisting of the list of its public wires. This data structure describes a structural abstraction of communicating black boxes and cannot be displayed without further information. Cells are created by applying the schematic extractor on schematics, or directly by executing programs, as described in the previous chapter.
All these data structures are extensible in different ways. They make heavy use of the object-class paradigm. They rely heavily on the existence of generic properties fields.
In the resulting decorated structural representation, a cell and its public wires are annotated with layout or schematic geometry. We call public wires' annotations pins. Decorated structures link the physical representation to the structural representation. They can be displayed: for example, one can display either a layout view or a schematic view of a decorated structure, depending on which decoration is present. Our layout and schematic extractors generate the structural representation decorated with the layout or schematic geometry and not just a net list.
Frequently, design aids operate with the structural representation as a basic abstraction. The decoration of the structural representation with geometric information allows these design aids to communicate easily with the user in geometrical terms. For example, when a program is checking that a structural representation derived from the layout matches that derived from the schematic, it can easily highlight the rectangles in either representation.
3.1 PatchWork Engine
The job of PatchWork is to take the structural representation annotated with layout keys such as Get or Abut and to decorate it with the layout that results from interpreting those keys. Layout keys have layout, decorate, and attribute procedures associated with them. The layout procedure, LayoutProc, generates the layout data structure; the decorate procedure, DecorateProc, links the layout to the net list expressed by the structural representation; the attribute procedure, AttributeProc, gathers parameters from the graphical information in the schematic. The function PatchWork.Layout takes as input the annotated structural representation, searches in a table of registered keys, and calls the corresponding LayoutProc followed by the DecorateProc. The AttributeProc is optional and, when present, is called before the LayoutProc is called. For efficiency, a cache is maintained so that successive calls to PatchWork.Layout with the same cell will return the same layout.
In the remainder of this section, we treat each of these procedures in turn.
3.2 Generating Layout
LayoutProcs can recursively use the PatchWork.Layout function. For example, when the annotation is Abut the layout method consists of applying PatchWork.Layout to each subcell and abutting the resulting layouts.
Each annotation may restrict the structure, cell class, and properties of the cells that use it. For example, the ChannelRoute LayoutProc assumes that the cell is a composition of two subcells, while the StandardCell LayoutProc only assumes that the layouts of leaf cells have matching heights.
The structure of the layout and the structure of the cell may be unrelated. For example, standard cell layouts are structured in rows abutted together to form an array, while the corresponding cell is structured according to the functional specification. Generally, however, flattening both structures should lead to isomorphic descriptions.
3.3 Linking Layout and Net List
LayoutProcs are sufficient for describing Abuts, but not for routing, since we need to know not only the sublayouts, obtained by calls to PatchWork.Layout, but also how the geometry relates to the structural representation. Pins define where in the sublayout a wire appears. Therefore, pins have to be built and propagated up as we compose layout with PatchWork.Layout. This is the purpose of the DecorateProc.
The DecorateProc corresponding to Abut decorates the cell with pins obtained by taking the union of all the pins of the subcells, properly translated, and clipped by the abutment rectangle.
The semantics of PatchWork.Layout can now be seen as a process of decorating a cell with layout. Checking that decorations are consistent, i.e., that every public wire has pins, has proved to be an efficient way to detect mismatches between the schematic and its layout implementation.
LayoutProcs and DecorateProcs use only interface information. This model is similar to the block-structure model in programming languages. For example, we do not allow a LayoutProc to decipher the inside of a subcell in order to do its own layout generation. Along the same lines, once a cell is generated it is never modified.
3.4 Gathering Schematic Parameters
Any layout generator is a procedure that can be called directly with all of its parameters provided explicitly. For example, Abut needs a list of subcells and a direction. However, when calling a generator from a schematic, a lot of information can be derived from the schematic itself with the help of a few conventions. A special procedure, the AttributeProc, uses the schematic decorations and the properties of the schematic to find such things as the relative placement of subcells or the side where a wire becomes public. The AttributeProc defines the user interface of each generator.
A problem we had to solve was a lack of uniformity among generators. We introduced a set of standard functions that derive annotations from schematics. These functions perform syntactic analysis of graphical descriptions, thereby defining a graphical language.
4. Results and Problems
4.1 Engineering Tradeoffs
Ideally, one would like the layout of a cell to be checked as PatchWork generates it. Many checkers, such as design rule, connectivity, and electrical checkers, or schematic comparators can work hierarchically. They are compatible with PatchWork if the checking information is propagated through the cell interface.
Unfortunately, these checks are time consuming, since they require an extraction of the layout that, in turn, necessitates solving a rectangle intersection problem—a typical nlog(n) algorithm. We decided to trade early detection of errors for speed of interaction, and, except for the basic interface check mentioned earlier, checks are done as batch jobs later in the design process.
The decoration of a cell is computed from the decorations of its subcells and knowledge of the layout operation being performed. In some cases, such as routing, the layout operation naturally produces the decorations. In other cases, such as abutment, the decorations can be produced at low computational cost by assuming invariants, or the invariants can be checked and the decorations produced simultaneously.
Another implementation difficulty is to reduce the memory size used for decorations. If we consider the case of a RAM composed of 100 rows of 32 cells each, each cell having 10 wires, and each wire 10 pins, a naive encoding of the decorations uses hundreds of thousands of objects. We solve this problem with several techniques. Sharing cells as much as possible is of course the most effective. Using a lazy representation for pins and trading time for memory has reduced the memory consumption by one to two orders of magnitude. A last optimization was to densely code the two common cases of irregularity in custom chips: routing areas and semiregular tilings such as PLAs, ROMs or decoders.
4.2 Wide Spectrum of Generators
Our collection of generators is already quite large and demonstrates that the framework is applicable to a large spectrum of generators. It includes geometrical transformations, PLA and Alps [Serlet 3] generators from boolean equations or truth tables, finite-state-machines, generalized arrays, a sophisticated pad frame generator with power routing, and a data path generator that is a hybrid of abutment and channel routing.
The modularity of our implementation language and the rich programming environment available at Xerox PARC help significantly by providing a set of interfaces that are like a tool box for building new generators. Most of the recent generators have been written by users other than the authors.
All of our generators are either technology-independent, e.g., Abut or Get, or parameterized by the design rules, e.g., ChannelRoute, or technology-independent but parameterized by technology-dependent cells, e.g., PLA and StandardCell.
4.3 Flexibility of Generated Layouts
In addition to the technology-independence of the generators, the specific chip layouts built using this system are relatively easy to modify. The assembly process is normally independent of detailed design rule or pitch changes. Changes in the layout assembly or local modifications can usually be implemented by minor editing of the source schematics. For example, the pitch of the data path of a microprocessor was increased in a few hours of editing, without changing the annotations.
4.4 Physical vs. Structural Description
For a wide range of VLSI circuits, the structural and physical descriptions are extremely close. In these cases, the schematic description of the physical implementation is concise and readable. However, structural and physical descriptions sometimes have little in common. PatchWork forces the description to be annotated schematics and some generators impose constraints on the structure of the description. Therefore, when our designers turn functional schematics into layout, they are forced to manually evolve their schematics from functional to physical descriptions. For several chips, this has led to a final description that is easy to relate to the layout, but which is no longer a readable functional specification. This ambiguous usage of schematics has been the dominant negative impact on design methodology caused by PatchWork.
4.5 Designs
Several chips have been, or are being, designed using PatchWork. One of the largest chips designed to this point, the control unit of a processor, contains over 60,000 transistors. For this chip, layout generation was done in less than 3 hours on a Dorado [Pier]. Most of that time was routing time. The entire layout description is annotated schematics. It includes a data path layout generator designed specifically for that chip, but which is now used in other designs. A more complete list of the chips designed with PatchWork can be found in the previous chapter.
5. Future work
5.1 Break Physical to Structural Isomorphism
We believe that more advanced generators that take high-level descriptions and that heavily modify the structure to produce layout will loosen the logical-physical tie. Currently available examples of such generators include a Standard Cell system, a datapath compiler, a pad frame router, and a finite-state machine synthesizer driven by transition diagrams. We are also working on a global place and route system that uses schematic hints.
Another possible strategy would acknowledge the difference between functional and physical descriptions, and would allow several related descriptions of the design. Although this is the traditional approach, it seems difficult to implement in its full generality, and too restrictive when implemented simply. It seems necessary to prove that the structural compositions of different behavioral primitives result in the same behavior. Promising results in the theorem-proving area may make this problem tractable.
5.2 Enhance Generators
The most obvious extension of the system would add more layout generators. We lack a cell compiler producing leaf cells in a way similar to Get, but starting from sticks or directly from a structural or functional representation. Such a generator would give us design rule independence. Full technology independence, for example, addition of a new metal layer, seems much harder to achieve.
5.3 Improve Decorations
So far, only connectivity information is preserved in decorations. More detailed information could be exported in the interface of a cell. The resistance between pins of a net could be of use to the global place and route algorithms for sizing power nets, and for using internal interconnect to decrease the routing area. The capacitance of wires could be used by sophisticated generators for sizing drivers. All of the geometry within a certain range of the abutment rectangle could be exported in order to construct DRC-correct cells hierarchically, as in the Pooh system [Whitney et al.].
5.4 Change Generation Framework
Currently, the generation process has no notion of a global context. Only local parameters for each generator are available. A global context would be useful to specify libraries, design rules, degree of optimization required, etc.
A great deal of time is spent synthesizing and verifying the layout. Some of our problems are due to the memory size limitations of our processors, but to achieve the multiple orders of magnitude improvement required to allow this portion of the design process to be interactive will require fundamental changes. An incremental computation model could provide the necessary framework.
The current generation framework is strictly hierarchical. Another direction for extending the framework would be to support constraint driven generation, as in the Electric system [Rubin], or to support generation directed by an intelligent system, such as in [Johannsen et al.].
6. Summary
We have presented PatchWork, a unified framework for generating layout from annotated parameterized schematics. In less than two years, PatchWork has matured from a prototype to a real system, complete with a large collection of generators. Designers at PARC have produced a variety of circuits proving the validity of this concept. Generation directed by annotated schematics is the next logical step in layout synthesis.
Examples of Layout Generation through Parameterized Schematics
1. Introduction
This chapter describes the DA system through examples that illustrate the major underlying principles. The first section takes a thorough look at the structure of a parameterized shift register; this shows the expressive power of schematics mixed with programs. The following section covers the assembly of a RAM array to exemplify how schematic annotations can be used to generate layout. This section focuses on low-level details, only necessary to optimize layout, and is by no means representative of the feel that a user would get from the system. Circuits described with high-level generators, such as standard cells, data path, and routers, usually carry few extra annotations. In the last section, we give an idea of how far some of the concepts are carried by describing a finite-state-machine directly with a transition diagram.
2. Parameterized Shift Register
As an illustration of the expressive power of mixing parameterized schematics and programs, we will walk through the description of a simple library element, a shift register.
2.1 The User's Point of View
For the designer, the shift register is simply an icon found in a library. This icon accepts a single numerical parameter nb that specifies its width in bits. After copying the icon into his design, the designer affixes to it a satellite, or text, that specifies the value for nb. In this example the text is of the form nb𡤈, but since it is handed to a general evaluator, it could be any valid Cedar expression, such as nb𡤅+Log(SizeOfBus/2).
Once part of a schematic, the shift register provides several things: a complete net list of a shift register based on primitive elements, including buffers on each control signal; behavioral models at various levels of abstraction; and layout in the form of standard cells. We now follow the extraction of an instance of this icon in order to understand its structure.
2.2 Structure of the Shift Register
Every object has an associated extractor that specifies how to obtain the net list that the object abstracts. In this case, the icon extractor simply refers to a schematic to be extracted. The value of
nb is passed along since it is needed to extract the schematic. Figure 1 shows both an instance of the icon with a byte-width, and the parameterized schematic defining it.
The schematic defines a shift register as a register (a member of the same library) whose input runs through a multiplexor that selects either the global input (when loading) or the previous output shifted by one position (when shifting). The input wire and the complementary outputs are nb-bit wide buses. Small symbols, called wire icons, describe the structure of wires. For example, the wire extractor (0: nb) specifies that the wire Output is composed of nb atomic wires and gives access to its high-order component (index 0), named outMSB. Similarly, the range extractor (1/nb-1: nb) defines a new wire of size nb-1, composed of the nb-1 low-order atomic wires of Output. Notice that the multiplexor, the wire icons, and the register are all icons parameterized by expressions using the variable nb and can be extracted as soon as nb receives a value.
Now let's shift our attention to the register. Its icon is bound to a procedure in the module defining the library. The code, slightly cleaned-up, is shown here:
Register:
PROCEDURE [b:
INTEGER]
RETURNS [cell: CellType] = {
IF b=0 THEN Error["Please specify a non-zero size for the register"];
cell ← Extract["register.sch", ["b", b]]; -- extract another schematic
SpecifyPorts[ -- specify directionality of ports -- ];
AttachBehavioralModel[cell, RegisterSimulationProcs];
};
This procedure simply asks for the extraction of a schematic with the specified value for the parameter b: it is the strict equivalent of a procedure call in a conventional programming language. This closes the loop between the graphical and procedural domains, and demonstrates that schematics and programs can be used interchangeably. The choice of the most practical representation is left to the designer.
The code also characterizes the ports of the cell and attaches a behavioral model to the register. This could be described completely in the schematic, but it is more conveniently done in a program. This justifies the extra step through code. The behavioral model is a procedure, written in Cedar, that can be used to simulate this block at register level. If no such behavioral model were available, the simulator could flatten the register down to gates or transistors, all of which have their own behavioral models.
The register is described by the Register.sch cell that contains only two elements: a sequence of D flip-flops with complementary enable lines and a driver for the control lines.
This graphical sequence of D flip-flops illustrates how generalized interpretation of a picture makes design capture quite natural. Imagine the designer editing and thinking: "I want to create a sequence (new class of cell) of b (Seq: b) flip-flops (he draws the base cell), so that the input and outputs become buses (he adds sequencing slashes on these wires), but the control wires are shared (clock and enables are untouched)".
A different circuit extractor interprets the picture in order to create a sequence cell: not only is the source smaller and more legible than tediously drawing all the flip-flops, but also a higher-level abstraction is captured, and therefore can be used by other tools.
In the left part of
Register.sch, we find another parameterized icon featuring a complementary buffer. The parameter
d specifies the load that the buffer is to drive, expressed in terms of unit gate load. Once again, the icon is bound to a procedure:
SymDriver:
PROCEDURE [d:
INTEGER]
RETURNS [cell: CellType] ~ {
SELECT d
FROM
-- extract another schematic according to the range of d
<=0 => Error["Please specify a non-zero strength for symmetrical driver"];
<=3 => cell ← Extract["symDriver3.sch"];
<=6 => cell ← Extract["symDriver6.sch"];
ENDCASE => {
-- use constant amplification in 3 stages
n2: INTEGER = (d+3)/4; -- last inverting stage
d1: INTEGER = d+n2; -- logic drive of initial non-inverting driver
cell ← Extract["symDriver.sch", ["n2", n2], ["d1", d1]];
};
SpecifyPorts[ -- specify directionality of ports -- ];
AttachBehavioralModel[cell, SymDriverSimulationProcs];
};
This time, the procedure extracts a schematic according to the value of the load: for small and medium loads, it picks fixed buffers of unit or double size; for larger loads, the buffer is itself a schematic that accepts two parameters. The buffer of size n2 is simply a sequence of unit-size buffers. The buffer of size d1 is again a parameterized icon, with a structure similar to the symmetric buffer we just described.
It is time to end this top-down exploration of the shift register. However, it should be clear that after another couple of steps, the shift register would be completely described in term of basic gates and D flip-flops. During this exploration, we encountered many parameterized macros from the same library: registers, multiplexors, and several types of buffers. This situation is common, illustrating that such parameterized macros can be re-used easily.
Many common parameterized macros have been assembled into a library that has become one of the most widely used components of this DA system. The library comprises basic gates, registers, multiplexors, comparators, drivers, counters, and adders. Several circuits developed at PARC are described mostly in terms of elements of this library.
2.3 Layout of the Shift Register
This shift register, like any other member of the library, can eventually be reduced to compositions of instances of about two dozen basic cells for which layout has been manually drawn. This is a surprisingly small library of standard cells, but our experience is that the introduction of parameterization is a much better move toward increased productivity than augmenting the library with rarely-used complex gates or fixed-sized macros (e.g., 4-bit multiplexor).
To obtain layout for a portion of a design expressed solely in terms of library elements, one adds to the top-level schematic the annotation Layout: StandardCells, together with a few optional parameters such as the number of rows. These annotations are preserved by the extractor and are eventually attached to the hierarchical net list representing the circuit. The layout generator processes this net list and flattens it until all the leaf cells carry a Layout annotation. At this point, the general layout mechanism is invoked to obtain the layout of these leaf cells, usually from a standard or user-defined library. This layout can also be obtained by composing other cells or generated by program: since standard cells are not special elements of the system, adding a new cell is a benign operation. This illustrates the extensibility of the system and the uniformity of the layout generation.
The last step is the usual placement and routing of those leaf cells to obtain the complete layout for that block. Notice that obtaining layout for such a design necessitates almost no overhead: it is just a matter of specifying a single annotation. This situation is typical of high-level generators.
3. Parameterized RAM
The following example is taken from the register file of an experimental processor. The description illustrates the construction of a typical module generator using parameterized schematics. As expected in dense full-custom areas, the main layout operators are the low-level assembly functions of abutment, rotations, and symmetries.
3.1 Leaf Cells
Only two leaf cells are needed to describe the memory array, one of which is a simple stitch cell needed only to distribute power. The main cell is a triple-port RAM cell, shown in figure 4 as a schematic at transistor-level with several annotations. The width of transistors is a typical annotation and is used by the schematics versus layout comparator, the static checker, and various simulators. An interesting annotation is Layout, whose value Get means that the layout is available as a user-defined cell. Computing the layout simply returns that cell, after checking that the schematics and layout cells have compatible interfaces.
3.2 Rows
The next level of assembly describes a quad-word: the RAM cell, shown in figure 5 in iconic form, is sequenced graphically, and the resulting cell is composed with a RamStitch, forming a complete RamQuad cell. The graphical sequence is similar to the one of Section 2.2., except that the keyword SeqX specifies that the layout must proceed by abutting cells in the horizontal direction.
When the layout generator processes the annotated net list, it first encounters the AbutX annotation; this indicates that cells are to be abutted in the horizontal direction to compose the layout. Notice that the order of cells is derived from the schematic and does not have to be repeated explicitly. This is an extremely simple illustration of the use of schematics as a graphical language: since the layout generator has access to the graphical representation of the circuit in addition to its net list, it can infer many hints: these hints are exactly the ones a designer would use. This minimizes the redundancy and improves the legibility of the design. The graphical language is put to full use by high-level layout generators, such as data path or pad frame generators. These generators use the relative positions of cells and wires as floorplanning information.
The Abut layout generator asks for the layout of its two components, the sequence and the stitch. The RamStitch cell carries a Get annotation and its layout is readily available; the sequence recursively calls the Array generator that finally fetches the layout of the RAM cell. The layout of these two pieces are abutted, and an interface check is performed before returning the final layout for RamQuad. This RamQuad is then sequenced to form the RamRow cell. Notice that the repetition factor is a parameter, making this a module generator rather than a fixed cell.
3.3 The Complete Array
The layout of adjacent rows in the array must alternate in order to share power rails and wells. The schematic of figure 6 shows a symmetric version of the row produced with the FlipY annotation. The row and its symmetric version are abutted, then sequenced vertically to form the entire array. The icon on the right side of figure 6 simply abstracts this whole array. Since it is parameterized by the number of quads per words and the number of words, one must bind specific values to these parameters, as shown.
The array can at this point be enhanced with I/O logic and address decoders (which are more naturally described by a page of code). The entire description for this parameterized RAM fits comfortably on two graphic pages (the schematics and layout of leaf cells) and on one page of code. Designs such as this memory array can be easily completed in a matter of hours, particularly if parts can be borrowed from other designs, like the program for assembling a decoder, or the schematic of a memory cell.
4. Finite-State-Machine
We illustrate how far we have carried some of these design concepts by skimming briefly over a last example. Figure 7 shows in its left half an example of a finite-state-machine, described graphically with named states, outputs, and boolean equations conditioning the transitions. To the designer, it is simply a readable picture that can be inserted into the circuit documentation. To the DA system, it is a portion of a schematic that can be extracted, just as a stack of gates would be.
The schematic is extracted by an extractor specific to the finite-state-machine cell class. Depending on the option used, the result of the extraction can be either an empty cell, with a behavioral model generated directly from the boolean equations, or a complete net list representing the finite-state-machine as standard cells or a PLA. An icon can be generated automatically from the schematic: it is shown in the right half of figure 7 as part of a FIFO controller.
5. Summary
We have presented a few examples that illustrate the major concepts behind our DA system, but these examples give only a glimpse of its power. Parameterized schematics mixed with programs lead to concise and natural descriptions of circuits. We have described circuits using representations bearing no resemblance to traditional schematics—i.e., finite-state-machines and data paths—and we have little doubt that the extensibility of the system will encourage new creative development.
It is remarkable that the mechanism of annotating the source to drive the layout generation does not impose unreasonable restrictions on the style of layout. As proof, a handful of designers have produced, over the past couple of years, a dozen chips ranging in complexity from small test chips, put together in a couple of hours, to full-custom circuits containing over 300K transistors. The set of generators they used is quite large; in addition to the basic generators exhibited in this chapter (Get, Abut, symmetries and rotations, arrays), one can place and route blocks and assemble data paths, semi-regular tilings, and pad frames. Specialized generators for logic arrays and libraries of parameterized macros complete the panoply.
Although work is proceeding to improve the system, the concept of design capture as parameterized schematics mixed with programs, and the use of annotations to drive layout generation have already been shown to be very powerful.
References
[Barbacci]
M. R. Barbacci, ``Instruction Set Processor Specification (ISPS): The Notation and its Applications,'' IEEE Transactions on Computers, 30(1), pp. 24-39, January 1981.
[Barth et al. 1]
R. Barth, B. Serlet, ``A Structural Representation for VLSI Design,'' 25th ACM/IEEE Design Automation Conference, June 1988, pp. 237-242.
[Barth et al. 2]
R. Barth, B. Serlet, and P. Sindhu, ``Parameterized Schematics,'' 25th ACM/IEEE Design Automation Conference, June 1988, pp. 243-249.
[Barth et al. 3]
R. Barth, L. Monier, and B. Serlet, ``PatchWork: Layout From Schematic Annotations,'' 25th ACM/IEEE Design Automation Conference, June 1988, pp. 250-255.
[Barth et al. 4]
R. Barth, B. Serlet, and P. Sindhu, ``Integrating Schematics and Programs for Design Capture,'' Advanced Research in VLSI, proceedings of the 1988 MIT conference, MIT Press, pp. 351-366.
[Bryant]
R. Bryant, ``A Switch-Level Model and Simulator for MOS Digital Systems,'' California Institute of Technology, July 1983.
[Buric et al.]
M. Buric, T. Matheson, ``Silicon Compilation Environment,'' proceedings IEEE, Custom Integrated Circuits Conference, May 1985, pp. 208-212.
[Chailloux et al.]
J. Chailloux, J.M. Hullot, J.J. Levy, J. Vuillemin, Le systeme Lucifer d'aide a la Conception de Circuits Int egr es, INRIA report 196, March 1983.
[Gajski et al.]
D. Gajski, N. Dutt, and B. Pangrle, ``Silicon Compilation: A Tutorial,'' Journal of Semicustom ICs, pp. 5-21, December 1986.
[German et al.]
S. German, K. Lieberherr, ``Zeus: A Language for Expressing Algorithms in Hardware,'' IEEE Computer, pp. 55-65, 18(2), February 1985.
[Harrison et al.]
D. Harrison, P. Moore, R. Spickelmier, and A. Newton, ``Data Management and Graphics Editing in the Berkeley Design Environment,'' IEEE International Conference on Computer-Aided Design, pp. 24-27, November 1986.
[Johannsen et al.]
D. Johannsen, S. Tsubota, K. McElvain, ``An Intelligent Compiler SubSystem for a Silicon Compiler,'' proceedings of 24th DAC, Computer Society Press, pp. 443-450, June 1987.
[Katz et al.]
R. Katz, M. Anwarrudin, and E. Chang, ``A Version Server for Computer-Aided Design Data,'' 23rd ACM/IEEE Design Automation Conference, June 1986.
[Knapp et al.]
D. Knapp and A. Parker, ``A Data Structure for VLSI Synthesis and Verification,'' Technical Report CRI-85-19, Department of EE Systems, USC, August 1985.
[LaPotin et al.]
D. LaPotin, S. Nasif, J. Rajan, M. Bushnell, and J. Nestor, ``DIF: A Framework for VLSI Multi-Level Representation,'' Semiconductor Research Corporation Preprint, November 1983.
[Lieberherr]
K. Lieberherr, ``A Two-dimensional Hardware Design Language for VLSI,'' North Holland, proceedings. EUROMICRO Symposium on Microprocessing and Microprogramming, pp. 131-142, March 1984.
[Luk et al.]
W.K. Luk and J. Vuillemin, ``Recursive implementation of Fast VLSI multipliers,'' Proceedings VLSI 83, August 1983.
[Matheson et al.]
T. Matheson, M. Buric, C. Christensen, ``Embedding Electrical and Geometric Constraints in Hierarchical Circuit-Layout Generators,'' proceedings IEEE International Conference on Computer Aided Design, September 1983, pp. 3-5.
[Mayo]
R. Mayo, ``Mocha Chip: A System for the Graphical Design of VLSI Module Generators,'' proceedings of ICCAD 86, pp. 74-77, November 1986.
[Monier et al. 1]
L. Monier and P. Sindhu, ``The Architecture of the Dragon,'' Proceedings of the IEEE 1985 COMPCON, pp. 118-121, Spring 1985.
[Monier et al. 2]
L. Monier and J. Vuillemin, ``Using Silicon Assemblers,'' Proceedings VLSI 85, pp. 309-318, June 1985.
[Monier 3]
L. Monier, ``Layout Generation through Parameterized Schematics,'' Proceedings MicroElectronics 88, pp. 157-164, Sydney, May 1988.
[Nagel]
L. Nagel, ``SPICE2—A Computer Program to Simulate Semiconductor Circuits,'' Technical Report ERL-M520, University of California, Berkeley, May 1975.
[Nash et al.]
J. Nash, S. Smith, ``A Front End Graphic Interface to the First Silicon Compiler,'' proceedings EDA, pp. 120-124, March 1984.
[Pier]
K. Pier, ``A Retrospective on the Dorado, a High-Performance Personal Computer,'' 10th Annual International Symposium on Computer Architecture, pp. 252-269, Dec. 1983.
[Piloty et al.]
R. Piloty, D. Borrione, ``The Conlan Project: Concepts, Implementations, and Applications,'' IEEE Computer, pp. 81-92, 18(2), February 1985.
[Rubin]
S. Rubin, Computer Aids for VLSI design, Addison-Wesley Publishing Company, 1987.
[Schmidt]
E. Schmidt, ``Controlling Large Software Development in a Distributed Environment,'' Xerox Palo Alto Research Center Technical Report CSL-82-7, December 1982.
[Serlet 1]
B. Serlet, Description Structurelle et Simulation de Circuits Int egr es, These de troisieme cycle, Faculte d'Orsay, January 1984.
[Serlet 2]
B. Serlet, ``Object Oriented Programming in Cedar,'' Actes des Journ ees Langages Orient es Objet, Bigre Globule, pp. 64-68, January 1986.
[Serlet 3]
B. Serlet, ``Fast, Small, and Static Combinatorial CMOS Circuits,'' 24th ACM/IEEE Design Automation Conference, pp. 451-458, June 1987.
[Shahdad et al.]
M. Shahdad, R. Lipsett, E. Marschner, K. Sheehan, and Howard Cohen, ``VHSIC Hardware Description Language,'' IEEE Computer, pp. 94-102, 18(2), February 1985.
[Shahdad]
M. Shahdad, ``An Overview of VHDL Language and Technology,'' proceedings DAC 1986, pp. 320-326, July 1986.
[Swinehart et al.]
D. Swinehart, P. Zellweger, R. Beach, and R. Hagmann, ``A Structural View of the Cedar Programming Environment,'' ACM Transactions on Programming Languages and Systems 8(4), October 1986.
[Teitelman]
W. Teitelman, ``A Tour Through Cedar,'' IEEE Software, 1(2), pp. 44-73, April 1984.
[Walker et al.]
R. Walker and D. Thomas, ``A Model of Design Representation and Synthesis,'' 22nd ACM/IEEE Design Automation Conference, pp. 453-459, June 1985.
[Whitney et al.]
T. Whitney and C. Mead, ``An Integer Based Hierarchical Representation for VLSI'' Advanced Research in VLSI, proceedings of the fourth MIT conference, MIT Press, pp. 241-257, April 1986.