CoreDescription.tioga
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Bland, July 6, 1987 3:38:28 pm PDT
Bertrand Serlet July 18, 1987 6:17:21 pm PDT
A DESCRIPTION OF THE CORE DATA STRUCTURE
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
A Description of the Core Data Structure
Lissy Bland and Mike Spreitzer
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract: Core is a hierarchical data structure used to describe electrical circuits. This paper describes Core is some detail. It includes sections on each of the data types that make up Core and discusses the mechanisms used for the inheritance of properties. Knowledge of VLSI design is assumed.
Maintained by: Bland.pa
Keywords: Core, CellType, CellClass, Structured Wire Sequences, Inheritance, Hierarchical Data Structure, Conform, Technical, VLSI, Circuit
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
1.0 Core
Core is a hierarchical data structure used to describe electrical circuits. It represents the electrical structure of a circuit with a number of small records. Core is very intentionally focused on the structure of a circuit. All additional information describing the circuit is hung off of Core at the appropriate place in the data structure. This information is said to decorate the Core data structure.
Each layer of the Core hierarchy is described by a CellType. The interface of a CellType is a sequence of wires. Each CellType belongs to a CellClass. CellClasses exist for two reasons: They provide an inheritance mechanism. And, they provide a procedure to change the way a CellType expresses its decomposition. This ability to change the way a CellType expresses its decomposition, called recasting, is very significant. It means that programs analyzing the Core data structure are not forced to understand the data type used in expressing the decomposition of every CellType and that circuit designs can be described at the appropriate level of abstraction.
Because the structure of Core is hierarchical, a CellType can represent circuits of varying complexity. Circuits as complex as a processor or as simple as a NAND gate are possible. Several data types are used to describe each layer of a CellType. Three of these types are fixed. They include: the CellTypeRec, the the WireRec, and the CellClassRec. The data field of the CellTypeRec is generally used to express the decomposition of the CellType. It is a REF ANY. Although the data field is a REF ANY, Core does provide a number of standard types for use in the data field. One of the most commonly used types is the RecordCellTypeRec. A RecordCellTypeRec is a simple list of CellInstanceRec's. Both the RecordCellTypeRec and the CellInstanceRec contain pointers to WireRecs that describe their connectivity. Finally, the CellClassRec provides the inheritance mechanism and recast procedure mentioned above.
The two figures given below present the Core data structure and a oneBitAdder. They will be used in explaining Core. Note that the diagram of Core uses the RecordCellType to express the decomposition of the CellType. This is a probable, not a required choice. The text following the two figures will discuss each of the fields of the records that make up the Core data structure. The fields will not be discussed in the order that they appear in the records. Instead, the fields expressing the most basic concepts of Core will be presented first with information about the less central fields following.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 2: oneBitAdder
Note: The heavy black mark on the top input to each gate designates that input as the 0th wire in the gate's wire sequence. The numbering of the wires proceeds in the most logical manner from the 0th wire.
2.0 CellType
A CellType describes a cell. A cell is a node in the Core hierarchy. Here is the Cedar definition for CellType:
CellType: TYPE = REF CellTypeRec;
CellTypeRec:
TYPE =
RECORD [
class: CellClass,
public: Wire,
data: REF ANY ← NIL,
properties: Properties ← NIL];
Most CellTypes are aggregates of simpler CellTypes. The data field of a CellType describes its decomposition. The data field is defined as a
REF
ANY for two reasons:
1. It allows the decomposition to be expressed efficiently for different CellTypes.
2. It facilitates an accurate description of each node in the CellType hierarchy.
Core provides a number of different standard types for use in the data field. These include: the RecordCellType, the Transistor, the SequenceCellType and the Unspecified type. Users of the Core data structure should define new types for decomposition as needed. For the oneBitAdder CellType pictured above, the decomposition would include 4 cells of CellType NAND, 5 cells of CellType NOR. This decomposition could be described conveniently by a RecordCellTypeRec.
The instantiation of CellInstances from CellTypes does not allow the CellInstance to be parameterized in any interesting way. Consequently, programs can analyze CellTypes rather than instances of CellTypes with the advantage that analysis can be performed once, on the CellType itself, rather than on each instance of the CellType.
Note: The use of the data field is not really this simple. There are times when the data field is not used to express the decomposition of a CellType. The role of the data field will make more sense after reading Section 5.1 on the inheritance of properties. Very curious readers can read Section 5.2 now.
3.0 Wire
Wires express electrical connectivity. Core uses the types Wire and WireSeq to express the connectivity of CellTypes, CellInstances, and RecordCellTypes. Here is the Cedar definition for Wire and WireSeq from Core.mesa:
Wire: TYPE = REF WireRec;
WireSeq: TYPE = REF WireRec;
WireRec:
TYPE =
RECORD [
properties: Properties ← NIL,
elements: SEQUENCE size: NAT OF Wire];
Note that this single data structure is used to describe atomic and aggregate wires, single wires and wire sequences. The advantage of this single definition is that it is possible to write one procedure that takes either a wire or a sequence of wires as an argument. The disadvantage is that having the same referent type for both a single wire (referenced by the Wire REF), and a sequence of wires (referenced by the WireSeq REF), is confusing. Given these referencing conventions for the use of the Wire and WireSeq REF's, the statement, WireSeq.size = 0, describes an empty sequence of wires. And the statement, Wire.size = 0 describes an atomic wire.
Note: The WireSeq REF was introduced in November, 1986. Before that time, a single REF, Wire, was used to describe both single wires and sequences of wires. A significant amount of code in the system uses the Wire REF to describe a sequence of wires.
3.1 Public: WireSeq
The
public wire sequence describes the interface wire of a CellType. The public wires are the points of connection to other CellTypes at the next higher level in the CellType hierarchy. There are five public wires in the oneBitAdder: A, B, C, COut and Sum. The
public wire sequence is contained in an instance of a CellType:
CellType: TYPE = REF CellTypeRec;
CellTypeRec:
TYPE =
RECORD [
class: CellClass,
public: WireSeq,
data: REF ANY ← NIL,
properties: Properties ← NIL];
3.2 Internal: WireSeq
The internal wire sequence is an inventory of all public and private wires in the decomposition of a RecordCellType. All of the wires pictured in Figure 2, the oneBitAdder, would be included in the internal wire. Internal is the first field in the RecordCellType decomposition:
RecordCellType: TYPE = REF RecordCellTypeRec;
RecordCellTypeRec:
TYPE =
RECORD [
internal: WireSeq,
instances: SEQUENCE size: NAT OF CellInstance];
3.3 Actual: WireSeq
The actual wire sequence is contained in the definition of a CellInstance:
CellInstance: TYPE = REF CellInstanceRec;
CellInstanceRec:
TYPE =
RECORD [
actual: WireSeq,
type: CellType,
properties: Properties ← NIL];
It describes how a CellInstance is connected into the internal wire which was inventoried by the RecordCellType. In the oneBitAdder, the actual wire sequence of the top-left NAND gate, labeled
one, includes two inputs, A and C, and one output, which is unlabeled. As Figure 1, the outline of the Core data structure illustrates, the elements of the actual wire sequence are internal wires.
3.4 Making the Connections Between Wires
3.4.1 In One Layer of a CellType Decomposition
The internal wire sequence is an inventory of all the public and private wires in the decomposition of a CellType. As Figure 1, the outline of the Core data structure illustrates, the public wire sequence of the CellType and the actual wire sequences of its CellInstances point into the internal wire sequence of the RecordCellType. All the connections that exist in a CellType become known as the the actual wire sequence of each of the CellInstances in a CellType is enumerated. For example, in the oneBitAdder, it becomes clear that the public wire labeled A is connected to two NAND CellInstances and two NOR CellInstances as the elements of the actual wire sequences of those NAND and NOR CellInstances are enumerated and found to point to A.
3.4.2 Between Two Layers of a CellType Decomposition
There is a strict relationship between the actual wire sequence of a CellInstance and the public wire sequence of that CellInstance's CellType. To be concrete, in the oneBitAdder, this relationship concerns the actual wire sequences of the individual NAND and NOR CellInstances in the oneBitAdder CellType and the public wire sequences of the NAND and NOR CellTypes. Core requires that these wire sequences conform. Conform describes a function with a two-part definition: First, this function requires that for each i, the ith public wire of that CellType is connected to the ith actual wire of the corresponding CellInstance. And, second, if public wire P is connected to internal wire A, and if P has children, the ith child of P is connected to the ith child of A. Figures 3a and 3b below show two examples of public and actual wires. Figure 3a depicts public and actual wire sequences that conform but do not have the same shape. Figure 3b depicts public and actual wire sequences that do not conform.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 3b. The public wire sequence of a cellType and the actual wire sequence of an instance of that cellType. These wire sequences do NOT conform. The first element of the public wire sequence is an atomic wire; the second element is a bus of size two. The first element of the actual wire sequence is a bus of size two; the second element is an atomic wire. There is no way to map the "orange" pointers at the leaf level.
The facts that: 1) the elements of the actual wire sequence point to selected elements of the internal wire sequence rather than pointing "below" them and 2) that the actual wire sequence of a CellInstance must conform to the public wire sequence of its CellType has an interesting consequence: Suppose the decomposition of a CellType includes two CellInstances that are four-bit buffers. And, suppose that the two four-bit buffers are being combined to create an eight-bit buffer. The internal wire sequence wants to represent the eight inputs as a single node with eight children; however, the requirement that the actual wire sequences of the four-bit buffer instances conform to the public wire sequence of the four-bit buffer CellType requires the internal wire sequence to represent the inputs as two nodes having four children each. Because the internal wire sequence prefers a representation showing one node with eight children, it stores pointers to two different representations of the inputs and outputs: one representation shows a single node with eight children and a second representation shows two nodes having four children each. (See Figures 4a and 4b below for two different graphical depictions of this consequence.)
4.0 CellClass
Here is the
CEDAR definiton for CellClass:
CellClass: TYPE = REF CellClassRec;
CellClassRec:
TYPE =
RECORD [
name: ROPE,
recast: RecastProc ← NIL,
properties: Properties ← NIL,
layersProps: BOOL ← TRUE];
The CellClass groups CellTypes. The primary reason for defining CellClasses is to provide a mechanism for the transformation of CellTypes through recast. This transformation is performed for two reasons: First, it means that every program analyzing the Core data structure is not forced to understand, or worse yet, anticipate future data types used to express any CellType's decomposition. And, second, the use of the recast proc facilitates the inheritance of properties. (See Section 1.4.1 for the use of the recast proc for the inheritance of properties.) Because there is only one recast procedure per CellClass, CellClasses must choose to use recast for the the inheritance of properties or for transformation of CellTypes. If layersProps is true, the CellClass uses its recast proc for the inheritance of properties. If layersProps is false, the recast proc is used to change the representation used in the CellType's data field. A maximal series of transformations should terminate in a basic representation. Basic in this context is a technical term that describes CellTypes whose CellClass contains no recast procedure.
There is exactly one CellClass that has a decomposition but does not provide a recast proc to express that decomposition. This is the RecordCellClass. The other basic CellTypes are either atomic, for example the transistorCellType, or have an undefined decomposition.
5.0 Properties
Core.Mesa defines properties as:
Properties: TYPE = PRIVATE ImplementationProperties.PropList.
The Properties field provides a place to store arbitrary information about CellTypes, CellInstances, CellClasses, and Wires. The uses of the Properties field are arbitrary. It has been used to store names, record the interface geometry of CellTypes, and to note the progress of an analysis program. The name of a property is always a CEDAR ATOM. The value of the property is a REF ANY.
Every property is owned by a particular CEDAR program. Properties are owned by a particular program because a single program must be responsible for determining exactly what a property means, and because every property must be registered, with the owning program responsible for doing the registration. Properties have a two-part name. The first part of the name is the name of the owning program and the second part describes the property, for example $CoreName.
Operations can be performed on properties. For example, properties may be printed. The operations that can be performed on a property are stored in the property's own property list. The program that owns the property sets up this additional property list. The only property contained in this additional property list that is universal is the one that tells how the property is to be printed. This property is the CoreProps.propPrint and its value is a REF to a PropPrintProc. A default PropPrintProc is provided in CoreProperties.
5.1 Property Inheritance: Layering
CellTypes and Wires can inherit properties. CellClasses and CellInstances cannot. There are two inheritance mechanisms for CellTypes. One inheritance mechanism is from the CellClass to the CellType. A second mechanism allows CellTypes to inherit from related CellTypes and their CellClasses through successive recasting of the orignal CellType. CoreProperties.InheritCellTypeProp implements both of these inheritance mechanisms. Here is the header for that procedure:
InheritCellTypeProp: PROC [from: CellType, prop: ATOM] RETURNS [value: REF ANY ← NIL];
This procedure looks for the value of a property for the given from: CellType and prop: ATOM arguments. If no value is stored directly in the CellType's property list for that property, the procedure first tries to inherit the value of the property in question from its CellClass. If the CellClass does not have the property and the cellType.class.layersProps BOOL is TRUE, the CellType is recasted and the procedure is repeated until the search for the property is successful or until the result of the recast has a CellClass in which the layersProps BOOL is FALSE.
The effect of this inheritance mechanism is to limit the properties actually stored with a particular CellType to those that distinguish it from the CellType upon which it is layered. By setting the cellType.class.layersProps
BOOL to
TRUE, a CellType inherits properties through recast. The properties actually stored with a particular CellType can be seen as a
delta value, a list of properties that are different from the corresponding properties of the CellType that it is layered on.
Sisyph is one user of the inheritance mechanism for properties. In particular, Sisyph uses Sinix, a mask extractor, to extract schematics. Here is part of what occurs as Sisyph extracts a schematic: Sisyph passes Sinix a schematic. Sinix can extract wires; more complex ChipNDale objects in the schematic have the following more complicated treatment. Sinix examines each of the more complex ChipNDale objects and finds the satellite expressions associated with it. One of the satellite expressions associated with it executes a call to Sisyph for the purpose of interpreting the ChipNDale object in question. Sisyph extracts the object and returns an Icon CellType for that object to Sinix. Sinix creates a CellInstance of that Icon CellType and adds it to the RecordCellTypeRec it is constructing. When the extraction is complete, Sinix has a RecordCellType composed of CellInstances that are instances of Icon CellTypes. Sinix passes that representation back to Sisyph.
Now suppose that a Sisyph client needs to understand the behavior of the extracted circuit. Properties describing the behavior are not stored with Icon CellTypes, they are stored on the CellTypes that Icons represent. A call to the CoreProperties.InheritCellTypeProp procedure recasts the Icon CellType into the appropriate CellType thus allowing the client to obtain information about the behavior of the CellType from the icon found in the containing schematic.
A second procedure, the CoreProperties.GetCellTypeProp PROC is used when a CellType does not want to use inheritance. Here is the header for that procedure:
GetCellTypeProp: PROC [from: CellType, prop: ATOM] RETURNS [value: REF ANY ← NIL];
This procedure is used by tools that manipulate the core data structure. For example, a program that stores a CellType to a file should only store those properties that are different from the corresponding properties of the CellType that it is layered upon. By using the GetCellTypeProp procedure which does not implement inheritance, the properties specific to that CellType are the properties that are stored. It is also a convenient way to verify that a particular property is not stored with a specific CellType.
Wires have a single inheritance mechanism based upon recast of CellTypes. The CoreProperties.InheritPublicProp provides this inheritance mechanism. Here is the definition of that procedure:
InheritPublicProp: PROC [cellType: CellType, from: Wire, prop: ATOM] RETURNS [value: REF ANY ← NIL];
This procedure examines the value of the property corresponding to the from and prop arguments. If no value is stored for the given from: and prop: arguments and the cellType.class.layersProps BOOL is TRUE, the CellType is recasted and the search is repeated. This process continues until the search for the property succeeds or the result of the recast has a CellClass in which layersProps is FALSE. The procedure, CoreProperties.GetWireProp is used when inheritance is not wanted. Here is the definition of the GetWireProp procedure.
GetWireProp: PROC [from: Wire, prop: ATOM] RETURNS [value: REF ANY ← NIL];
5.2 Layering: In Greater Detail
Essentially, the assertion of Section 2.0 that the data field of a CellType describes its decomposition is an over-generalization. A more accurate statement would be that the data field of a CellType exists to serve the needs of that CellType's CellClass. In general, CellClasses group CellTypes and store information that CellTypes included in a particular CellClass share. One of the reasons that CellClasses exist is to provide for the transformation of CellTypes through recast. When the recast proc is used for the transformation of a CellType, the CellClass uses the data field of the CellType to learn about the decomposition of that CellType. However, when the CellClass exists for the inheritance of properties, the CellClass does not need or user the data field to express the decomposition of the CellType. In such cases, recasting provides for the inheritance of properties and will eventually provide a new CellType whose data field is used for expressing the decomposition of that CellType.
To generalize, if the layersProps BOOL is false, the data field of the CellType is always used to express the decomposition of that CellType. However, if the layersProps BOOL is true, the data field assumes a function that is appropriate for that CellType's CellClass. When the layersProps BOOL is true, programmers may make assumptions about the role of a CellType's data field with CellClasses that are familiar, but should not make any assumptions about the role of the data field with unfamiliar CellClasses.
As an example, a CellType that belongs to an Icon CellClass provides a pictorial reference to the logical function of a another CellType. The Icon CellClass has layersProps
BOOL that is true. The data field of the Icon CellType does not store structural information about the CellType it represents. If a client holds an Icon CellType and needs to find structural information about that CellType, it must recast the Icon CellType to find a related CellType where the layersProps
BOOL is false.
Note: In writing code for Core, the definition of Properties in Core, Core.Properties, not the definition found in Properties, Properties.PropList, should be used. This is to assure that code using Core.Properties does not depend on any particular implementation of Core.Properties.
6.0 Standard Types for Expressing the Decomposition of CellTypes
6.1 Record:
The RecordCellType describes a structuring mechanism which takes a collection of instances of cell types of various classes and binds them together:
RecordCellType: TYPE = REF RecordCellTypeRec;
RecordCellTypeRec:
TYPE =
RECORD [
internal: WireSeq,
instances: SEQUENCE size: NAT OF CellInstance];
recordCellClass: CellClass;
6.2 Transistor:
E means enhancement mode.
D means depletion mode. The
n represents an n-channel transistor, the
p represents a p-channel transistor.
Transistor: TYPE = REF TransistorRec;
TransistorRec:
TYPE =
RECORD [
type: TransistorType ← nE];
TransistorCellClass: CellClass;
TransistorType: TYPE = {nE, pE, nD};
The length and width of the a transistor are included in the property list of the cellType:
lengthProp: ATOM; -- This ATOM denotes a ref to an integer.
widthProp:
ATOM;
-- This
ATOM
denotes a ref to an integer.
6.3 Sequences:
Sequences describe the class of CellTypes made from a collection of cell instances of identical type bound together in a regular pattern.
SequenceCellType: TYPE = REF SequenceCellTypeRec;
SequenceCellTypeRec:
TYPE =
RECORD [
base: CellType,
count: NAT,
sequence: SequenceSet ← NIL,
flatSequence: SequenceSet ← NIL];
SequenceSet: TYPE = REF SequenceSetRec;
SequenceSetRec:
TYPE =
RECORD [set:
SEQUENCE length:
NAT
OF
NAT];
sequenceCellClass: CellClass;
6.4 Unspecified:
The Unspecified CellType is generally used to describe cells that are seldom used or are important in a very specific application.
unspecifiedCellClass: CellClass;