SisyphDoc.tioga
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Written by: Pradeep Sindhu, November 24, 1985 11:57:14 pm PST
Bertrand Serlet August 4, 1986 11:10:30 pm PDT
Pradeep Sindhu, July 28, 1986 4:14:53 pm PDT
SISYPH: A SCHEMATICS EXTRACTOR
SISYPH: A SCHEMATICS EXTRACTOR
SISYPH: A SCHEMATICS EXTRACTOR
DATOOLS — FOR INTERNAL XEROX USE ONLY
DATOOLS — FOR INTERNAL XEROX USE ONLY
DATOOLS — FOR INTERNAL XEROX USE ONLY
Sisyph: A Schematics Extractor
User Manual
Pradeep Sindhu
Abstract: SISYPH is a schematics extractor that produces Core structural descriptions from circuit diagrams drawn using ChipNDale. The program has several interesting features: it encourages users to freely intermix graphical and procedural specifications, permitting more compact and comprehensible descriptions; it allows schematics to be parameterized, thereby deriving the benefits of better abstraction; it does not have the customary distinction between "built-in" circuit primitives and "user defined" ones, making it easy to modify even the lowest-level elements; and finally, it uses standard ChipNDale as input, capitalizing on its facility for hierarchical composition and its familiar user interface. The first three features all derive from a key design decision: namely to treat extraction as a stack-based computational process in which the basic step is the evaluation of expressions embedded within circuits. The scope rules for expression variables are determined by the geometric hierarchy. Sisyph package also provides a set of standard wire icons to describe structured wires.
Created by: Pradeep Sindhu
Maintained by: Pradeep Sindhu <Sindhu.pa>, Bertrand Serlet <Serlet.pa>
Keywords: Schematics Extraction, Schematics, Extraction, Wire Icons, Icons, Visual Programming
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
Introduction
SISYPH is a schematics extractor that takes logic diagrams drawn using ChipNDale and produces structural descriptions expressed in Core. Its main purpose is to provide a tool that allows the structure of a large VLSI chip to be conveniently specified using a combination of graphical and procedural methods. The motivation for such a tool comes from the fact that some structures such as decoders and trees are best expressed using code, while simple but relatively irregular collections are best handled pictorially. By combining the two methods we expect to get specifications that are both more compact and easier to understand.
The input to SISYPH is a circuit schematic drawn using icons that represent simpler schematics and wires that connect icons together. Icons may have arbitrary geometry, while wires are drawn as collections of connected rectangles. An icon does not necessarily represent a schematic that has actually been drawn—it may represent a fictitious schematic whose Core structure is computed directly by code attached to the icon.
This attachment of code to icons is part of a general mechanism that permits arbitrary CEDAR expressions to be attached to geometric objects to control their extraction. During extraction these expressions are evaluated in a stack based environment that includes all procedures callable in the current CEDAR world, certain SISYPH variables used internally during the extraction, and any new variables the user cares to define. This mechanism provides both a convenient link between geometry and code and tight control over the result of extraction. The link between geometry and code is more than just a one-way connection. Since user code may invoke SISYPH via its programming interface, and SISYPH may in turn invoke user code, a single extraction could result in a number of trips across the code-geometry boundary.
When creating schematics, a user typically starts off with a predefined set of icons for standard components such as transistors and SSI gates. For a simple circuit these icons probably will be sufficient, so the user won't need to define his own. Using standard ChipNDale commands he constructs his schematic and then extracts it by invoking SISYPH interactively or via the programming interface. For more complicated circuits the user builds up his schematic hierarchically using predefined icons and icons of his own in much the same way he would write a non-trivial program. The parallel between writing a program and building a schematic is more than a passing analogy. There is direct equivalence between the notion of a procedure and that of an icon: the use of an icon is a procedure call; an icon's schematic is the procedure's definition; expressions attached to the icon serve as parameters to the procedure call; and finally the returned Core is the procedure's result. Given this equivalence, the procedure model is a good one to keep in mind when using SISYPH.
The remainder of this document provides sufficient information to use SISYPH productively. The first section defines the basic geometric objects a user deals with when drawing schematics and describes the construction rules for each object. With these rules in hand the user knows enough to draw simple schematics. To use SISYPH for real examples, however, he must understand the evaluation mechanism for SISYPH expressions; this is taken up next. During extraction, wires with certain global names are treated specially; precisely what this special treatment entails is explained in the following section. Details of the programming interface, the user interface, and how to run the program occupy the last three sections. It is assumed throughout that the reader is familiar with the basic concepts of Core.
Basic Objects and Construction Rules
SISYPH uses five basic objects to express logic diagrams: expressions, wires, schematics, cell icons, and wire icons. Each object has its own construction rules that specify how it is to be drawn and its own semantics for how it is to be extracted.
Expressions
An expression is a rope that contains a CEDAR expression and is attached to one of the other four objects. The attachment can be made in several ways: as a property on the ChipNDale object, as a satellite on the object, as a property on the ChipNDale instance, or as a satellite on the instance. It is convenient to call expressions attached in these various ways object p-expressions, object s-expressions, instance p-expressions, and instance s-expressions, respectively. Object and instance p-expressions are invisible since they are kept as ChipNDale properties, but s-expressions are visible since they are kept as satellites. Each expression is further a parameter expression or a result expression.
The purpose of having these categories will become clear once the evaluation mechanism is described, but briefly here is what they are for. Object expressions typically supply default values for parameters and the resulting Core, while instance expressions override these defaults and supply any additional parameters. S-expressions are useful when a designer wants the information to be always visible, while p-expressions come in handy when visible information would clutter up a design.
Wires
A wire is a set of connected ChipNDale comment rectangles that represent a Core wire. Two rectangles are connected if a corner from one of them touches or lies inside the other, or if the rectangles have the same name. A rectangle is named by assigning the appropriate ROPE to the SISYPH variable name. Since naming is a frequent operation, simply using the wire's name in place of the expression is also accepted.
By default a rectangle extracts as an atomic wire. However, by using an expression that assigns to the SISYPH variable wire, a rectangle can be made to produce a wire with any desired structure.
Schematics
A schematic is a ChipNDale cell that expresses the structure of some electrical circuit in terms of simpler circuits. It is drawn using icons, wires, expressions, and perhaps other schematics.
The public wire of a schematic is defined by its interface geometry. This geometry consists of rectangles that either touch the cell's interestRect directly or are connected to directly touching rectangles by geometry or name. The interface geometry also determines where electrical connections may be made when a schematic is used directly within another schematic.
Cell Icons
A cell icon is a ChipNDale cell that serves as a pictorial shorthand for a circuit schematic. Its purpose is to provide a graphical abstraction mechanism that allows a complicated schematic to be drawn simply. The schematic corresponding to an cell icon may be real, in which case the icon points to the appropriate ChipNDale cell, or it may be non-existent, in which case it points directly to a procedure that returns the Core for the fictitious schematic. This scheme trivially allows a schematic to have more than one icon.
A cell icon normally contains pictorial geometry and interface geometry. Pictorial geometry is window dressing as far as extraction is concerned—its only purpose is to make the looks of the icon meaningful to the reader. This geometry is identified to the extractor by marking instances with the null extraction property. Instances not marked with this property are significant for extraction. Of the significant instances, those rectangles that touch the icon's interestRect (or are connected to such rectangles by geometry or name) constitute interface geometry, just as for a schematic. This geometry defines the icon's
drawnPublic and determines where electrical connections may be made to the icon when it is used. Once the Core for the icon has been computed by evaluating the result expression, a check is made to verify that the drawnPublic conforms to the result's public. The result's public and the drawnPublic must match in the sense that every wire of the drawnPublic must be named and exactly one wire of the result's public must have the same short name. The drawnPublic may be structured, but only the top level wires are considered for the matching. The algorithm can be expressed as follows:
Take each first level wire of the public of the cellType obtained by extracting the icon. If it has no name, error. Otherwise try to find in the schematic's public a wire with the same short name. If zero or more than one found, error.
Take every first level wire of the schematic's public. If it has a name, and if it does not match a drawn wire, and if it is not a global wire, emit a warning (but just a warning). Otherwise proceed.
Wire Icons
An wire icon is a ChipNDale cell that serves as a pictorial shorthand for a Core wire.
A wire icon normally contains pictorial geometry and interface geometry. Pictorial geometry is window dressing as far as extraction is concerned—its only purpose is to make the looks of the icon meaningful to the reader. This geometry is identified to the extractor by marking instances with the null extraction property. Instances not marked with this property are significant for extraction. Of the significant instances, those rectangles that touch the icon's interestRect (or are connected to such rectangles by geometry or name) constitute interface geometry. This geometry defines the icon's drawnWire and determines where electrical connections may be made to the icon when it is used. Once the Core for the icon has been computed by evaluating the result expression or by extracting the appropriate schematics, a check is made to verify that the drawnWires conforms to the resultWire. The algorithm for matching is the same as for cell icons, apart for the second rule that is just to emit a warning if the resultWire is unnamed and does not match a drawn wire, and apart that cells where there is only a single drawn wire are handled specially (so that that wire can be un-named).
Important restrictions: when a wire icon is defined by code, this code should return a new copy at every call. When a wire icon is defined by a schematic, this schematic should not extract as a wire itself (unexpected behavior otherwise because the wire is not copied).
The Evaluation Mechanism
During extraction, a ChipNDale instance passed to SISYPH generally has one or more expressions attached to it. These expressions are evaluated as part of the process of extracting the instance, and the evaluation directly affects the resulting Core.
The Environment
The environment in which evaluation proceeds consists of a SISYPH Context and an Interpreter Context. The SISYPH Context is simply a symbol table of <name> <value> pairs where each pair defines a SISYPH variable of arbitrary CEDAR type. The Interpreter Context contains definitions of all global frames and interface records currently loaded in the CEDAR world. During evaluation, names are first looked up in the SISYPH context, and if not found there are looked up in the Interpreter Context. If a name does not exist in either context then an error is signalled.
SISYPH uses a number of variables to hold key values such as the name of the entity being extracted, the design in which it lies, and the result to be returned by the extraction (a complete list appears in Appendix A). Since these variables are kept in the SISYPH context, and all SISYPH variables may be assigned to via expressions appearing in a schematic, a user has explicit control over extraction. The user may also use expressions to define new SISYPH variables. These variables can then be assigned to and used either during the extraction of the instance to which the expressions are bound or during the extraction of nested instances.
The Context Stack
To get the semantics of extraction to mimic the semantics of procedure call, SISYPH contexts are maintained in a stack. Before an instance is extracted, the SISYPH context for the instance's parent is first copied into a new context and then pushed onto the context stack after initializing certain local variables to NIL. This allows the new context to inherit values from the parent's context and at the same time isolates variables in the parent's context from any changes that may occur when expressions attached to the current instance are evaluated. When the extraction of the current instance is complete, the parent's context is restored.
Evaluation Order
The evaluation of expressions proceeds in the parameter phase and the result phase, performed in that order. Within the parameter phase the evaluation order is: object p-expressions, object s-expressions, instance p-expressions, and finally instance s-expressions. The result phase consists in evaluating a rope found under the $CodeFor property or to fetch the schematic found under the $IconFor property.
This order has the effect of giving the highest precedence to assignments done via instance s-expressions, a lower precedence to those done via instance p-expressions, lower still to those done via object s-expressions, and the lowest to those done via object p-expressions. This order is desirable for two reasons. First, it makes visible expressions take precedence over invisible ones, bringing us closer to "what you see is what you get". Second, it makes it possible to tailor the extraction of a particular instance of an icon, regardless of how the object says it is to be extracted.
Expression Sugar
Expressions have been embellished with a certain amount of syntactic sugar to make the specification of certain common cases palatable. The cases are: declarations, affectations, properties (that end up on the resulting core), names, and loopholes.
An expression of the form <var> ~ <value> declares a variable. The type can be specified (for example for a range) by using the Cedar syntax for <value>: <type>[<expression>]
An expression of the form <var> ← <value> is assumed to specify an affectation. <var> should have been declared earlier.
An expression of the form <pname>: <pvalue> is assumed to specify a Core property with name <pname> and value <pvalue>. It is shorthand for the complete expression:
coreProps ← CoreProperties.PutProp[coreProps, $<pname>, <pvalue>] or
coreInstProps ← CoreProperties.PutProp[coreInstProps, $<pname>, <pvalue>].
An expression <expr> with no embedded "←" or ":" is assumed to be a name. It is shorthand for the complete expression:
CoreName: <expr>.
Other expressions are passed to the interpreter. Users should try not to use this loopholing facility!
It is recommended NOT to use variables which names start with &. Those variables have slightly different rules (e.g. they do not have to be declared). May be one day we will get rid of them?
Restriction: coreProps must only be set by Object satellite/expression, and coreInstProps must only be set by Instance satellite/expression. Non repetitive behavior will occur otherwise. For a very subtle reason, it took me 3 days to figure out this restriction.
Global Names
The purpose of global names is to allow designers to omit certain ubiquitous signals like Vdd and Gnd and have them connected up automatically. Having to draw these signals explicitly for virtually every cell would increase a designers work without enhancing the clarity of his schematics. The designer specifies global names via the SISYPH variable globalNames whose value is a LIST OF ROPE, and which defaults to LIST ["Vdd", "Gnd"]. In fact there is a third wire "RosemaryLogicTime", but nobody should see it. Typically, this variable will be set by having a design object satellite such as 'globalNames ← List ["Vdd", "Gnd", "Clock"]'. Note that List here refers to Sisyph.List and not Cedar LIST for reasons that have to do with dynamic type-checking.
During the extraction of a cell C there are two rules that govern the treatment of global names. First, when an instance I is used within C, any atomic actual of I whose public has a short name equal to a global name is given that name and fused to any already existing first-level internal of C with that name. Second, any atomic internal of C that has a short name equal to a global name is promoted to be a public of C, if it isn't already public. Together, these rules ensure that a global name will propagate upwards in the hierarchy until the designer explicitly renames a global wire.
In the current implementation global wires must be atomic, but may be part of a structured wire. There is no plan to ever change that.
Standard Wire Icons
Annotating geometry with code is sufficient to use structured wires, but it is fairly cumbersome so, a more convenient mechanism is provided. This mechanism consists of a few generators available via the PatchWork command (P-MiddleClick). When one of these generators is invoked, it prompts for appropriate parameters and draws the desired wire icon. These icons are normal ChipNDale cells so they can be saved on files. Some caching is attempted to save memory and time.
Those icons come in two varieties: parameterized, or non parameterized. In the parameterized case, extraction first evaluates satellites and then calls the interpreter.
Sequence Cells
Cells may be marked as Sequence cells. Such cells will be extracted in a non-standard way, and will result in a Core data structure of class Sequence (cf. CoreClasses). This data structure allows description of repeated cells, with no intercell communication.
A sequence icon must be created using certain rules.
- It should contain only one instance of a base cell, the latter will get sequenced.
- All publics of that base cell should be public of the sequence cell.
- The sequence cell should contain one and exactly one object satellite of the form Keyword: Expression, where Keyword is one of the following: Seq, SeqX, SeqY, RSeqX, RSeqY, and where Expression is an arithmetic expression evaluating to an INT.
- The sequence cell should be marked so using the make sequence icon entry of the make icon sub menu (obtained by space-O). A warning will be emitted at that time if the sequence cell does not contain an object satellite of the appropriated form.
- Wires can be sequenced (grouped as bus) by putting a non-NIL $Sequence property. The Wire Icons menu (Patchwork menu) proposes an easy way to give such a property by putting down a Sequencing Slash. The FlatSequence functionality of Core sequence class can also be used by adding a non-NIL $FlatSequence property on a wire. There is no Wire Icon for that yet, come to see me with a picture if you want that.
The file SequenceExample.dale demonstrates an example of use. Once Logic is loaded, you should be able to click ExtractAndLayout on any schematic cell of that design.
Programming Interface
The programming interface resides in Sisyph.mesa. In addition to defining the names of SISYPH variables and certain properties used by SISYPH, it provides procedures for extraction and procedures for dealing with SISYPH contexts.
Non parameterized wire icons, usually created interactively with the PatchWork menu, can be generated by program using the interface WireIcons. [I wonder if someone really wants this feature!]
User Interface
The user interface for SISYPH consists of main commands accessible via the <space>-O menu, and a number of expression commands accessible via the <space>-L, or satellites and expressions menu. In addition, the user needs to be familiar with the usual ChipNDale commands.
Sisyph: Icons menu (<space>-O)
Proposes several commands to change the way cells are extracted and to make them iconic. Refers to the on-line documentation in the menu itself.
Sisyph: Visibility menu (<space>-O)
Make Invisible to Sisyph marks an instance with the null extraction property. This causes SISYPH to ignore the instance if it appears inside an icon.
Make Visible to Sisyph reverses the effects of previous command.
Sisyph: Parameters menu (<space>-O)
The context variables on which the extraction of a cell depends can be set explicitly by the user. This allows to make extraction much faster, since equality of contexts can just be checked for the specified variables, and since much less objects will be extracted and much more will be shared. Nethertheless it is a dangerous feature, since no check is done when the list of parameters is explicitly set, or whenever the cell changes. The Parameter menu allows showing, setting and editing the list of parameters. A list of parameters just containing the pseudo-parameter "0" means no parameter at all.
Other Commands in the <space>-O menu
Sisyph: Flush Caches erases all caches on the selected objects and their sons (and through the icon-schematics links). Users should never have to use this command in normal situations.
Sisyph: Extract extracts the selected instance and types out the resulting core on the terminal.
Sisyph: Highlight proposes a menu to do various kinds of highlight.
Expression Commands (<space>-L)
The expression commands share the satellites Menu accessible via <space>-L. There are three commands each for satellites, instance expressions, and object expressions.
Show Instance Satellites (I-LeftClick) selects the satellite group to which the currently selected instance belongs. Multiple selections are not allowed.
Add Instance Satellite (I-MiddleClick) prompts for text and makes that text a satellite of the currently selected instance. Multiple selections are not allowed, and the current selection must not be a text instance.
Set Instance Satellites (I-RightClick) takes a single non-text instance and zero or more text instances and makes the text instances be satellites of the non-text instance.
Show Object Satellites (O-LeftClick) selects satellites attached to the pushed-in object.
Add Object Satellite (O-MiddleClick) prompts for text and makes that text be a satellite of the pushed-in object.
Set Object Satellites (O-RightClick) takes zero or more text instances and makes them be object satellites of the pushed-in object.
Show Instance Expressions (LI-LeftClick) types out the instance expressions attached to the pointed instance.
Add Instance Expression (LI-MiddleClick) prompts for text and adds the text as an instance expression on the pointed instance.
Edit Instance Expressions (LI-RightClick) allows the instance expressions of the pointed instance to be edited. Existing expressions may be changed or deleted, and new ones may be added.
Show Object Expressions (LO-LeftClick) types out the object expressions attached to the pointed instance's object.
Add Object Expression (LO-MiddleClick) prompts for text and adds the text as an object expression on the pointed instance's object.
Edit Object Expressions (LO-RightClick) allows the object expressions of the pointed instance's object to be edited. Existing expressions may be changed or deleted, and new ones may be added.
Standard Wire Icons
Standard wire icons can be creating by the PatchWork command (P-MiddleClick) or by the generator command (U-Middle). Requests from the terminal should be self-explanatory.
Editing expressions
Expressions are edited in the following way: first each previous expression is printed and a replacement asked for. If the input is "-" that expression is deleted, if it is "", it is left unchanged, and otherwise the input replaces the previous expression. Then new expression are asked for. If the input is "-" or "" the edition is completed. A DEL stops the editing process at any time, leaving previous expressions unchanged.
Limitations
The implementation limits the number of levels to which wires can be nested to 32. This restriction was imposed to catch infinite recursion, and is not a fundamental one. The number of nesting levels will be increased if applications demand it.
Appendix A:
SISYPH Variables
The following variables are defined by SISYPH. Those marked local are initialized to NIL when a new context is created, those marked global are inherited from the parent context.
Variable Name Type Value Scope
design CD.Design current design global
globalNames LIST OF ROPE list of global names global
coreProps Core.Properties property to be put on result local
coreInstProps Core.Properties property to be put on instance local
cdObj CD.Object object currently being extracted local