NewRoute.mesa
Copyright Ó 1985, 1987 by Xerox Corporation. All rights reserved.
Created by Bryan Preas
Preas, May 14, 1987 5:26:34 pm PDT
Bertrand Serlet May 15, 1987 12:08:01 pm PDT
DIRECTORY CD, DABasics, Rope;
Route: CEDAR DEFINITIONS = BEGIN
Thing still to do
Major problem:
EachChannelNetProc: TYPE = PROC [name: REF ANY ...] I thought we agreed to have 2 things: a unique ID (REF ANY) and a name (ROPE). This is conceptually something major.
It should be stated somewhere that all nodes of a routing cell carry this unique ID, and the name of the property should be exported.
breakAtExitNets: LIST OF Rope.ROPE I thought we agreed it had to be triplets of the three unique IDs.
Minor details:
Use the interface DesignRules, and a scale factor.
improve Range type.
SubType: TYPE = {};
documentation about trunkToTrunk, pinSpacing, trunkToEdge
documentation in general of the interface
Theory
This interface provides the procedures and data types necessary to define and route an interconnection area using the major routing algorithms: channel, and switchbox. The client program must first define the design rules. Next, one of the routing algorithms is invoked; this algorithm passes back summary routing information (required size, whether expansion is needed, list of incomplete nets if any) as well as the resulting ChipNDale object. Multiple channel routing specification methods are proveded; they all perform the same function.
Route supports both fixed coordinate routing (SwitchBox) where the pin and side locations are not modified by the algorithm and topological routing (Channel) where the routing area is expanded to the required size to hold all of the routing.
The following restrictions apply:
The routing area is rectangular but may have irregular routing barriers on the edges of the rectangle.
The pins may not lie in the routing area proper (that is, they must lie outside the routing area of within the route barriers).
The pins must be accessable by straight line segments on the layer for the routing material used.
The routing area (except for the routing barriers) is owned by Route. Route will disregard any pre-existing material in the routing area proper.
Channel Router restrictions:
Pins must have fixed positions on the sides parallel to the trunk layer direction. Pins on the channel ends (routing area sides parallel to the branch direction) are positioned by the channel router to minimize the routing area.
Channel routing algorithms do not exploit the area in the shadow of routing barriers well.
SwitchBox Router restrictions:
The routing area is not altered from the input specification. The SwitchBox router does the best it can in the area specified.
Common Types
Range: TYPE = RECORD [l, r: DABasics.Number]; -- INCLUDED ???; chose better field names
Optimization: TYPE = {full, noIncompletes};
Errors
Error: ERROR [errorType: ErrorType ← callingError, subType: SubType, explanation: Rope.ROPE ← NIL];
Signal: SIGNAL [errorType: ErrorType ← callingError, subType: SubType, explanation: Rope.ROPE ← NIL];
ErrorType: TYPE = {programmingError, callingError, noResource, other};
SubType: TYPE = {};
Design Rules
DesignRules: TYPE = REF DesignRulesRec;
DesignRulesRec: TYPE = RECORD[
trunkLayer, branchLayer: CD.Layer, -- ChipNDale layers for the indicatde direction
trunkDirection: DABasics.Direction, -- direction of the trunk layer
trunkToTrunk, pinSpacing, trunkToEdge: DABasics.Number,
technology: REF ANY  -- ChipNDale technology
];
the design rule parameters used by the Router
CreateDesignRules: PROC [tech: REF, horizLayer, vertLayer: CD.Layer, trunkDirection: DABasics.Direction] RETURNS [designRules: DesignRules];
Define the routing design rules.
tech must define a technology ChipNDale.
Symetrical Channel Routing Operation
Result: TYPE = REF ResultRec;
ResultRec: TYPE = RECORD [
object: CD.Object,
polyLength, metalLength, metal2Length: DABasics.Number ← 0,
polyToMetal, metalToMetal2, numTrunkTracks, numIncompletes: NAT ← 0,
incompleteNets, breakAtExitNets: LIST OF Rope.ROPE ← NIL];
Channel: PROC [enumerateNets: EnumerateChannelNetsProc, range: Range, rules: DesignRules, name: Rope.ROPE ← NIL, enumerateObstructions: EnumerateChannelBarriersProc ← NIL, clientData: REF ANY ← NIL, optimization: Optimization ← full, signalSinglePinNets, signalCoincidentPins: BOOL ← TRUE] RETURNS [result: Result];
Channel Route the routing area. The pin positions on the four sides are specified in the same manner.
NOTE: Error conditions are indicated through Errors and Signals. Proceeding from signals will cause design rule violations in the routing. Signals are raised instead of Errors so debugging will be easier! Use signalSinglePinNets and signalCoincidentPins = FALSE with caution!!!
EnumerateChannelNetsProc: TYPE = PROC [eachNet: EachChannelNetProc, clientData: REF ANY ← NIL];
EachChannelNetProc: TYPE = PROC [name: REF ANY, enumeratePins: EnumerateChannelPinsProc, mayExit: BOOL ← TRUE, trunkWidth: CD.Number ← 0];
mayExit indicates if the net wiring may be deferred out of the left or right side. A signal is raised if the router needs to defer a net which has mayExit FALSE. The channel geometry of enumeratePins should be thought of as line segments. If trunkWidth is 0 then the trunk will be the minimum size allowed for the trunk layer.
EnumerateChannelPinsProc: TYPE = PROC [eachPin: EachChannelPinProc, clientData: REF ANY ← NIL];
EachChannelPinProc: TYPE = PROC [side: DABasics.Side, range: Range ← [0, 0], depth: CD.Number ← 0];
The fields are interpreted differently depending if the pin is on a side (parallel to the trunk direction) or on the end of the channel.
Channel end: side and width (may be defaulted, 0 => mimimum trunk width) are used if the pin is on the "end" of the channel.
Channel Side: range indicates the the position along the side and depth indicates the penetration of the pin.
Switch Box Routing Operation
SwitchBox: PROC [enumerateNets: EnumerateChannelNetsProc, range: Range, rules: DesignRules, name: Rope.ROPE ← NIL, enumerateObstructions: EnumerateSwitchBoxBarriersProc ← NIL, clientData: REF ANY ← NIL, optimization: Optimization ← full, signalSinglePinNets, signalCoincidentPins: BOOL ← TRUE, okToDiddleLLPins, okToDiddleURPins: BOOL ← FALSE] RETURNS [result: Result];
SwitchBox Route the routing area. Side positions are not changed by SwitchBoxRoute. Incompletes should be remidied by increasing the routing area size.
NOTE: Error conditions are indicated through Errors and Signals. Proceeding from signals will cause design rule violations in the routing. Signals are raised instead of Errors so debugging will be easier! Use signalSinglePinNets and signalCoincidentPins = FALSE with caution!!!
NOTE: Setting okToDiddlePins TRUE allows the router to move pins on the ends of a switchBox up to one design rule spacing. Set this parameter to true only if this will not cause design rule violations in the output. This means that the pins on the end of the switchbox must be "sparse" and have no interfering material close by. If you don't know what this means, do't set okToDiddlePins TRUE!!!
EnumerateSwitchBoxNetsProc: TYPE = PROC [eachNet: EachSwitchBoxNetProc, clientData: REF ANY ← NIL];
EachSwitchBoxNetProc: TYPE = PROC [name: REF ANY, enumeratePins: EnumerateSwitchBoxPinsProc, mayExit: BOOL ← TRUE, trunkWidth: CD.Number ← 0];
mayExit indicates if the net wiring may be deferred out of the left or right side. A signal is raised if the router needs to defer a net which has mayExit FALSE. The channel geometry of enumeratePins should be thought of as line segments. If trunkWidth is 0 then the trunk will be the minimum size allowed for the trunk layer.
EnumerateSwitchBoxPinsProc: TYPE = PROC [eachPin: EachSwitchBoxPinProc, clientData: REF ANY ← NIL];
EachSwitchBoxPinProc: TYPE = PROC [side: DABasics.Side, range: Range ← [0, 0], depth: CD.Number ← 0];
The fields are interpreted differently depending if the pin is on a side (parallel to the trunk direction) or on the end of the channel.
Channel end: side and width (may be defaulted, 0 => mimimum trunk width) are used if the pin is on the "end" of the channel.
Channel Side: range indicates the the position along the side and depth indicates the penetration of the pin.
Horizontal Channel Routing Specification
HorizChannel: PROC [enumerateNets: EnumerateHorizChannelNetsProc, horizRange: Range, rules: DesignRules, name: Rope.ROPE ← NIL, enumerateObstructions: EnumerateChannelBarriersProc ← NIL, clientData: REF ANY ← NIL, optimization: Optimization ← full, signalSinglePinNets, signalCoincidentPins: BOOL ← TRUE] RETURNS [result: Result];
Channel Route the routing area. Routing area sides may be moved by Channel.
NOTE: Error conditions are indicated through Errors and Signals. Proceeding from signals will cause design rule violations in the routing. Signals are raised instead of Errors so debugging will be easier! Use signalSinglePinNets and signalCoincidentPins = FALSE with caution!!!
EnumerateHorizChannelNetsProc: TYPE = PROC [eachNet: EachHorizChannelNetProc, clientData: REF ANY ← NIL];
EachHorizChannelNetProc: TYPE = PROC [name: REF ANY, enumeratePins: EnumerateHorizChannelPinsProc, exitLeft, exitRight: BOOL ← FALSE, mayExit: BOOL ← TRUE, trunkWidth: CD.Number ← 0];
mayExit indicates if the net wiring may be deferred out of the left or right side. A signal is raised if the router needs to defer a net which has mayExit FALSE. exitLeft and exitRight indicate if the net must be routed to the respective channel side. The channel geometry of enumeratePins should be thought of as line segments. If trunkWidth is 0 then the trunk will be the minimum size allowed for the trunk layer.
EnumerateHorizChannelPinsProc: TYPE = PROC [eachPin: EachHorizChannelPinProc, clientData: REF ANY ← NIL];
EachHorizChannelPinProc: TYPE = PROC [side: DABasics.TBSide, xRange: Range ← [0, 0], yDepth: CD.Number ← 0];
Only Pins on the top and bottom sides are enumerated; channel exits on the left and right sides are specified by exitLeft, exitRight.
xRange indicates the the position along the side and yDepth indicates the penetration of the pin.
Vertical Channel Routing Specification
VertChannel: PROC [enumerateNets: EnumerateVertChannelNetsProc, vertRange: Range, rules: DesignRules, name: Rope.ROPE ← NIL, enumerateObstructions: EnumerateChannelBarriersProc ← NIL, clientData: REF ANY ← NIL, optimization: Optimization ← full, signalSinglePinNets, signalCoincidentPins: BOOL ← TRUE] RETURNS [result: Result];
Channel Route the routing area.
NOTE: Error conditions are indicated through Errors and Signals. Proceeding from signals will cause design rule violations in the routing. Signals are raised instead of Errors so debugging will be easier! Use signalSinglePinNets and signalCoincidentPins = FALSE with caution!!!
EnumerateVertChannelNetsProc: TYPE = PROC [eachNet: EachVertChannelNetProc, clientData: REF ANY ← NIL];
EachVertChannelNetProc: TYPE = PROC [name: REF ANY, enumeratePins: EnumerateVertChannelPinsProc, exitBottom, exitTop: BOOL ← FALSE, mayExit: BOOL ← TRUE, trunkWidth: CD.Number ← 0];
mayExit indicates if the net wiring may be deferred out of the left or right side. A signal is raised if the router needs to defer a net which has mayExit FALSE. exitBottom and exitTop indicate if the net must be routed to the respective channel side. The channel geometry of enumeratePins should be thought of as line segments. If trunkWidth is 0 then the trunk will be the minimum size allowed for the trunk layer.
EnumerateVertChannelPinsProc: TYPE = PROC [eachPin: EachVertChannelPinProc, clientData: REF ANY ← NIL];
EachVertChannelPinProc: TYPE = PROC [side: DABasics.LRSide, yRange: Range ← [0, 0], xDepth: CD.Number ← 0];
Only Pins on the top and bottom sides are enumerated; channel exits on the left and right sides are specified by exitLeft, exitRight.
yRange indicates the the position along the side and xDepth indicates the penetration of the pin.
Routing Barriers
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
EnumerateChannelBarriersProc: TYPE = PROC [eachObstruction: EachChannelBarrierProc];
EachChannelBarrierProc: TYPE = PROC [side: DABasics.Side, range: Range, depth: CD.Number, layer: CD.Layer];
A Channel Routing Barrier describes one of the routing layers adjacent to the associated side. The barrer extends from the routing area side to the fartherest extent of the barrier rectangle.
EnumerateSwitchBoxBarriersProc: TYPE = PROC [eachObstruction: EachSwitchBoxBarrierProc];
EachSwitchBoxBarrierProc: TYPE = PROC [side: DABasics.Side, rect: CD.Rect, layer: CD.Layer];
A SwitchBoxBarrier Routing Barrier describes one of the routing layers within the routing area.
END.