SoSDoc.tioga
Written by Giordano Bruno Beretta, October 17, 1985 4:37:14 pm PDT
gbb, March 31, 1986 2:11:47 pm PST
SoS
CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY
SoS
Son of Spinifex
Giordano Bruno Beretta
© Copyright 1985, 1986 Xerox Corporation. All rights reserved.
Abstract: SoS is the Son of Spinifex. It is a hierarchical design rule checker that enumerates a Core design and uses the ChipNDale geometry with which it is decorated to verify separation and width design rules. Clients can define enumeration procedures for own classes.
Created by: Giordano Bruno Beretta
Maintained by: Giordano Bruno Beretta <Beretta.PA>
Keywords: Design Rule Checking, Layout Verification, Design Automation Tools
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304

For Internal Xerox Use Only
1. Principles of Operation
SoS traverses a Core data structure to retrieve and verify the layout geometry it contains. Verification is done against a simple set of design rules (separation and width) provided by ChipNDale. It uses a brute force quadratic algorithm, offsetting the time complexity penalty by performing heavy pruning on the data and by using a special dynamic cache for cell intersections.
The actions to be performed both on Core and ChipNDale objects depend upon their class. Therefore we use the object oriented formalism consisting in attaching a specific procedure as a property to each class. This procedure is applied on the object itself when it is encountered. Since this is quite expensive from a running time point of view due to the heavy list processing, the most frequent cases are treated separately in special cases.
As a means to speed up the verification of regular structures such as memory cells, SoS maintains special dynamic cache called neighbourhood table. It holds the most recently analysed pairs of objects. If an object pair to be analysed is found in this table, then the analysis of their interaction is skipped.
Separation violations are allowed if the pieces of material involved are equipotential. The design rule violations are reported in the Core data structure (see definition module for the details). If the Core data structure contains sufficient information, the design rule violations are reported also in the ChipNDale design.
2. Usage
Bring over [DATools]<DATools®>Top>SoS.df, where ® is the current Cedar release number.
You may want to avoid the verification of certain cells. This can be achieved by assigning a non-nil value to the property $DoNotDRC to such cells.
Interactive
To check a layout, type SoS in the command viewer. Go to the viewer containing your ChipNDale design and select a set of cells. Hit the p key while holding down the space bar. Select the entry Extract & DRC (Sinix & SoS) in the pop-up menu. This command will first execute Sinix to produce an appropriate Core design, and subsequently SoS to verify it. Upon termination the design rule violations will be visible as highlight rectangles in the ChipNDale design (if there is a correspondence among the Core and ChipNDale data structures). Eventually a summary is produced.
SoS registers also two commands to list all design rule violations found in a previously analyzed cell. These commands do not apply to cells analyzed by program. The first command, List Violations (SoS), presents a pop-up menu listing the names of the Core cells in which design rule violations were found by SoS. If a name is selected, the command prints the design rule violations of the cell (type of violation, layers names and wire names). It subsequently attempts heuristically to find a corresponding ChipNDale cell, and if successful tries to push into it and to change the display to show the selected cell. I do not know what to do if you have edited the cell you are currently pushed in, so the last part of the command may fail. A way out is to pop out of the cell you are currently in.
The second design rule violations listing command, List All Violations (SoS), lists all design rule violations it found in the last extraction and verification pass for design in the viewer with the input focus.
There is no heuristics on what to do if you edit a cell after you grind it through SoS. The following is the state after a pop with replace. Error rectangles (including their messages) you have not deleted manually are left in the cell. The design rule violations listing for the cell is invalidated and can no longer be examined. This is not a fancy user interface, but it is predictable and hence less confusing.
All commands can be aborted in the usual way (i.e. ESC DEL).
By program
SoS provides a procedural interface. For its clients SoS maintains an error count and a list of pairs {rectangle, message} in the Core cells, which can be accessed using the property with key $SoSError.
Clients can fully customize the verification by providing own procedures for all or part of the operations at the class or at the object level. Refer to the definition module for more details. If you want to make sure that you process all the geometry, you may want to set the variable SoSCommandImpl.debug to true during your development.
Comparison to Spinifex
Since SoS does not use a geometrical data structure, its memory requirements are minimal. The data space required are stack to propagate the binding, a cache of fixed size for the neighbourhood table, and a rectangle for each cell.
The use of the neighbourhood table makes SoS very fast in comparison to Spinifex in repetitive parts of a layout (e.g. RAMs). Spinifex cannot take shortcuts in such cases and has to instantiate and analyse the geometry for all terms of the repetition.
On small irregular designs with few cell overlaps, Spinifex will be faster than SoS due to the superiority of the corner stitched data structure over our quadratic algorithm. However, the limited virtual memory available on the Dorado is a show stopper for Spinifex.
Spinifex takes advantage of being based upon a geometrical data structure to produce detailed error messages. SoS can just say `separation violation' or `width violation' [it nevertheless uses the Core data structure to specify the affected wire names]. The fact that SoS processes the geometry locally (pairs of rectangles) - in opposition to globally (cells) in Spinifex - causes it to flag more design rule violations than Spinifex for some layouts.
The designer can avoid this problem by adapting his design style to the new fashion of the Cedar world. His cells should be correct in isolation. `Artificial' cells whose only purpose is to connect wires left open in child cells are bad. If the connections are included in the child cells, locality is preserved, the layout is easier to understand and `wrong' error messages are avoided.
In conclusion, the designer is suggested to use Spinifex while he is doing the layout of his base cells, in order to get more detailed error messages. When he assembles the cells, he can switch to SoS, which he can incorporate in the generating program. The first step of the switch should consist of a verification of the base cells with SoS and doing all the cosmetics to avoid unwanted error messages.
Remember that SoS verifies only the separation and the width rules. Use Gismo to check that vias are on flat topology. Although by construction with a catholic program you cannot have unconnected wells in your layout (they would be wires, but they do not conduct), it is nevertheless a good idea to use the well connection tool of Gismo, because it flags errors where there are not enough contacts.
Reliability
The correctness of SoS is easy to prove by using the propagation stack, its main invariant. The completeness of SoS depends on specific extraction and verification procedures with which objects are decorated.
3. Maintenance Hints
Try to determine whether the bug has to do with the exploration of the Core structure (first case) or with the finding of the geometry (second case).
First case. If you enter "← SoSImpl.Debug[]" in the Command Tool, SoS will create a typescript viewer into which he keeps a log of the cells and wires analysed. If you also say "← SoSCommandImpl.Debug[]", SoS will verify that all ChipNDale objects are examined. If your debugging session extends over several rollbacks, you may want to remake the package with "SoSImpl.debug ← TRUE" and "SoSCommandImpl.debug ← TRUE".
Second case. a. Two rectangles violate a design rule but are not detected. Give to both instances of them the ChipNDale propriety $SoSBreak (ChipNDale command N-space). When they will be processed SoS will call the debugger when it comes to a point called probe 1 in procedure MaterialSeparation. You will find all you need on the stack.
You may examine several pairs at the same time. To this purpose give different values to the property $SoSBreak. When you have examined a pair, simply press the button Proceed in the debugger viewer.
If SoS terminates without ever calling the debugger, this is a clear sign that something is wrong with the properties attached to the Core cells.
Second case. b. Two rectangles are flagged to violate a design rule but this is not true. Open SoSCommandImpl.mesa and set a break-point after the line marked Probe 2 in procedure MaterialSeparation. You will find all you need on the stack. Either the design rule will be wrong or the bindings of the wire will be wrong.
If a design is specified and the ChipNDale cell containing the violation can be accessed in Core, an error rectangle is inserted at the proper location. For debugging this can be a nuisance, therefore SoS can be made more persistent in finding correspondent ChipNDale cells by setting the variable SoSImpl.persistTRUE. (This is the default at the current time.)
Good luck !