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.
A routing area has top, bottom, left, and right edges.
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 has no concept of 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
Pin: TYPE = REF PinRec;
PinList: TYPE = LIST OF Pin;
PinRec:
TYPE =
RECORD[
min, max, depth: CD.Number ← 0,
layer: CD.Layer,
side: DABasics.Side];
Result: TYPE = REF ResultRec;
ResultRec:
TYPE =
RECORD [
object: CD.Object,
polyLength, metalLength, metal2Length: DABasics.Number ← 0,
polyToMetal, metalToMetal2, numTrunkTracks, numIncompletes: NAT ← 0,
incompleteNets: LIST OF Label ← NIL];
Optimization: TYPE = {full, noIncompletes};
Label: TYPE = Rope.ROPE;
Design Rules
DesignRulesParameters: TYPE = REF DesignRulesParametersRec;
DesignRulesParametersRec:
TYPE =
RECORD [
horizLayer, vertLayer: CD.Layer, -- ChipNDale layers for the indicatde direction
trunkDirection: DABasics.Direction, -- direction of the trunk layer
trunkToTrunk, pinSpacing, trunkToEdge: NAT,
technology: CD.Technology -- ChipNDale technology
];
the design rule parameters used by the Router
DefaultDesignRulesParameters:
PROC [technologyHint:
REF, horizLayer, vertLayer:
CD.Layer, trunkDirection: DABasics.Direction]
RETURNS [designRules: DesignRulesParameters];
Define the routing design rules.
technologyHint must define a technology ChipNDale.
Channel
A channel routing area has left, right, top, and bottom sides. There is a single x axis used to define the position of the left and right sides as well as the x position of the pins belonging to the top and bottom sides. Increasing values denote up and right. The left side is the line defined by x=min and the right side is the line defined by x = max. Thus the top and bottom sides must be of equal length. The top and bottom sides of the channel have a common x coordinate axis but different y coordinate axis. The top y coordinate axis lies above the bottom side coordinate axis. The top side is the line defined in the top side y coordinate system by y = maximum y coordinate of all top side pins. The bottom side is the line defined in the bottom side coordinate system by y = minimum y coordinate of all bottom side pins. All top side pins which lie below the top side, or bottom side pins which lie above the bottom side, must be within an obstruction.
Obstructions are rectangles with three sides defined and the fourth infinitely far away from the channel. Obstructions are associated with the top or bottom side. The fourth side of a top obstruction extends to plus infinity and that of a bottom side extends to minus infinity. Route will not place geometry outside of the routing area nor within an obstruction except that it will extend branches into an obstruction sufficiently to connect to a pin lying within it. Clients define the obstructions by supplying an enumerateObstructions procedure. If no obstruction procedure is passed then the channel is assumed to be a simple rectangular region and all of the y coordinates of the top pins must be equal and all of the y coordinates of the bottom pins must be equal.
The router calls a client supplied procedure, enumerateNets, to enumerate the nets and supply connectivity information. Each net has a set of pins which are to be connected by the router. Pins must be design rule correct and must not overlap.
The router may fail to complete the interconnection. If it does then it routes the electrical regions which still need to be connected to the left or right side of the channel. The client provides new net names via the brokenNets procedure. channelData is passed through to the enumerateNets, brokenNets, and enumerateObstructions procedures.
The router typically uses the trunkLayer to synthesize geometry which runs parallel to the top and bottom sides. It uses the branchLayer to synthesize geometry which runs parallel to the left and right sides. To improve density the router may move short segments of trunk material to the branchLayer.
If optimization is noIncompletes then the router stops searching when it finds a solution which completes all of the interconnections. optimization= full may result in shorter routes, fewer vias, and increased run time.
The router places the origin of the result object at x=min, y=0. The first trunk is placed above the bottom side by the trunkToEdge distance. Each succeeding trunk is placed above the previous by the trunkToTrunk distance. pinSpacing specifies the minimum separation distance of pins along the sides. The router uses the rulesParameters to synthesize rectangles and holes and to place them into the result object in a design rule correct manner.
The router returns the synthesized object and a number of indications of the quality of the solution. trunkLayerLength, and branchLayerLength report the length of the geometry synthesized in each of these layers. holes reports the number of holes synthesized. numTrunkTracks reports the number of horizontal trunk tracks the router used.
Channel:
PROC [enumerateNets: EnumerateChannelNetsProc, min, max:
CD.Number, rulesParameters: DesignRulesParameters, name: Rope.
ROPE ←
NIL, brokenNets: BrokenNetProc ←
NIL, enumerateObstructions: EnumerateChannelBarriersProc ←
NIL, channelData:
REF ←
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.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
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!!!
BrokenNetProc:
TYPE =
PROC [channelData, netData:
REF, sourceNet: Label, regionNumber, numberOfRegions:
NAT]
RETURNS [newLabel: Label];
BrokenNetProc is called by the Router if has to break a net at the end of the channel. This allows the client to assign different Labels to unconnected regions
EnumerateChannelNetsProc:
TYPE =
PROC [channelData:
REF, eachNet: EachChannelNetProc];
EachChannelNetProc:
TYPE =
PROC [name: Label, enumeratePins: EnumerateChannelPinsProc, exitLeftOrBottom, exitRightOrTop:
BOOL ←
FALSE, mayExit:
BOOL ←
TRUE, trunkSize:
CD.Number ← 0, channelData, netData:
REF ←
NIL];
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 trunkSize is 0 then the trunk will be the minimum size allowed for the trunk layer. The name and id are stored as the value of some properties on the Node property list in the synthesized routing cell.
EnumerateChannelPinsProc:
TYPE =
PROC [channelData, netData:
REF, eachPin: EachChannelPinProc];
EachChannelPinProc:
TYPE =
PROC [bottomOrLeftSide:
BOOL, min, max, depth:
CD.Number ← 0, layer:
CD.Layer];
If branchSize is 0 then the branch will be the minimum size allowed for the branch layer. If the actual branch size is different than the pin width then the branch is centered on the pin, justified left for odd sizes. bottomOrLeftSide indicates which of the two channel sides that the pin is on. If the layer is not included is not a branchLayer a signal is raised.
EnumerateChannelBarriersProc: TYPE = PROC [channelData: REF, eachObstruction: EachChannelBarrierProc];
EachChannelBarrierProc:
TYPE =
PROC [side: DABasics.Side, min, max, 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.
Switch Box
SwitchBox:
PROC [enumerateNets: EnumerateSwitchBoxNetsProc, routingRect: DABasics.Rect, rulesParameters: DesignRulesParameters, name: Rope.
ROPE ←
NIL, enumerateObstructions: EnumerateSwitchBoxBarriersProc ←
NIL, switchBoxData:
REF, 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.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
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 [switchBoxData:
REF, eachNet: EachSwitchBoxNetProc];
EachSwitchBoxNetProc:
TYPE =
PROC [name: Label, enumeratePins: EnumerateSwitchBoxPinsProc, trunkSize:
CD.Number ← 0, switchBoxData:
REF, netData: REF];
A signal is raised if the router needs to defer a net to the end of the switchbox. 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 [switchBoxData, netData:
REF, eachPin: EachSwitchBoxPinProc];
EachSwitchBoxPinProc:
TYPE =
PROC [side: DABasics.Side, min, max, depth:
CD.Number ← 0, layer:
CD.Layer];
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.
EnumerateSwitchBoxBarriersProc: TYPE = PROC [switchBoxData: REF, 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.
Primitive Operations
IntermediateResult:
TYPE =
REF IntermediateResultRec;
IntermediateResultRec:
TYPE =
RECORD [
routingArea: REF ANY ← NIL,
resultData: ResultData
];
ResultData:
TYPE =
REF ResultDataRec;
ResultDataRec:
TYPE =
RECORD [
polyLength, metalLength, metal2Length: CD.Number ← 0,
polyToMetal, metalToMetal2, numTrunkTracks, numIncompletes: NAT ← 0,
routingRect: DABasics.Rect ← [0, 0, 0, 0],
moreAreaRequired: BOOL ← FALSE,
incompleteNets: LIST OF Rope.ROPE ← NIL
];
ChannelRoute:
PROC [enumerateNets: EnumerateChannelNetsProc, min, max:
CD.Number, rulesParameters: DesignRulesParameters, rules: DesignRules, name: Rope.
ROPE ←
NIL, enumerateObstructions: EnumerateChannelBarriersProc ←
NIL, channelData:
REF ←
NIL, optimization: Optimization ← full, signalSinglePinNets, signalCoincidentPins:
BOOL ←
TRUE]
RETURNS [intermediateResult: IntermediateResult];
Channel Route the routing area. The pin positions on the four sides are specified in the same manner.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
ChannelRetrieve:
PROC [intermediateResult: IntermediateResult, enumerateNets: Route.EnumerateChannelNetsProc, brokenNets: BrokenNetProc ←
NIL, channelData: REF← NIL, retrieveRect:
REF DABasics.Rect ←
NIL]
RETURNS [result: Result];
Channel Route the routing area. The pin positions on the four sides are specified in the same manner.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
SwitchBoxRoute:
PUBLIC PROC [enumerateNets: EnumerateSwitchBoxNetsProc, routingRect: DABasics.Rect, rulesParameters: DesignRulesParameters, rules: DesignRules, name: Rope.
ROPE, enumerateObstructions: EnumerateSwitchBoxBarriersProc, switchBoxData:
REF, optimization: Route.Optimization, signalSinglePinNets, signalCoincidentPins:
BOOL, okToDiddleLLPins, okToDiddleURPins:
BOOL]
RETURNS [intermediateResult: IntermediateResult];
SwitchBox Route the routing area. Side positions are not changed by SwitchBoxRoute. Incompletes should be remidied by increasing the routing area size.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
SwitchBoxRetrieve:
PUBLIC PROC [intermediateResult: IntermediateResult]
RETURNS [result: Route.Result];
SwitchBox Route the routing area. Side positions are not changed by SwitchBoxRoute. Incompletes should be remidied by increasing the routing area size.
A Routing Barrier is an area where the Router should not put geometry on the specified layer.
DesignRules: TYPE = REF DesignRulesRec;
DesignRulesRec:
TYPE =
RECORD[
trunkLayer, branchLayer: CD.Layer,
trunkDirection, branchDirection: DABasics.Direction,
trunkWidth, trunkSpacing, trunkToContact, trunkToTrunk, trunkOffset, branchWidth, branchSpacing, branchToContact, branchToBranch, branchOffset, contactSize, contactToContact, pinSpacing, trunkToEdge: NAT ← 0];
DefaultDesignRules:
PROC [designRuleParameters: DesignRulesParameters]
RETURNS [designRules: DesignRules];
get design rules from parameters