RouteImpl.mesa
Copyright © 1985, 1987 by Xerox Corporation. All rights reserved.
Bryan Preas, July 10, 1985 11:14:39 am PDT
last edited Bryan Preas, July 28, 1987 3:46:59 pm PDT
DIRECTORY
CD, CDBasics, CDRoutingObjects, CDSimpleRules, DABasics, List, RefTab, Rope, Route, RouteChannel, RoutePrivate, RouteTechnology, RTBasic, SymTab;
RouteImpl: CEDAR PROGRAM
IMPORTS CDBasics, CDRoutingObjects, CDSimpleRules, RefTab, Route, RouteChannel, RouteTechnology, SymTab
EXPORTS Route = {
Errors
Error: PUBLIC ERROR[errorType: Route.ErrorType ← callingError, explanation: Rope.ROPE ← NIL] = CODE;
Signal: PUBLIC SIGNAL[errorType: Route.ErrorType ← callingError, explanation: Rope.ROPE ← NIL] = CODE;
Design Rules
DefaultDesignRulesParameters: PUBLIC PROC [technologyHint: REF, horizLayer, vertLayer: CD.Layer, trunkDirection: DABasics.Direction] RETURNS [designRules: Route.DesignRulesParameters] = {
Define the routing design rules.
tech must define a ChipNDale technology.
IF technologyHint # NIL THEN {
tech: CD.Technology ← CDSimpleRules.GetTechnology[technologyHint];
designRules ← RouteTechnology.DesignRulesParameters[tech, horizLayer, vertLayer, trunkDirection]}
ELSE -- invalid technology
Error[callingError, "Invalid technology."]};
Channel
Channel: PUBLIC PROC [enumerateNets: Route.EnumerateChannelNetsProc, min, max: CD.Number, rulesParameters: Route.DesignRulesParameters, name: Rope.ROPE, brokenNets: Route.BrokenNetProc, enumerateObstructions: Route.EnumerateChannelBarriersProc, channelData: REF, optimization: Route.Optimization, signalSinglePinNets, signalCoincidentPins: BOOL] RETURNS [result: Route.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.
designRules: Route.DesignRules ← DefaultDesignRules[rulesParameters];
intermediateResult: Route.IntermediateResult ← ChannelRoute[enumerateNets, min, max, rulesParameters, designRules, name, enumerateObstructions, channelData, optimization, signalSinglePinNets, signalCoincidentPins];
result ← ChannelRetrieve[intermediateResult, brokenNets, channelData]};
Switch Box
SwitchBox: PUBLIC PROC [enumerateNets: Route.EnumerateSwitchBoxNetsProc, routingRect: DABasics.Rect, rulesParameters: Route.DesignRulesParameters, name: Rope.ROPE, enumerateObstructions: Route.EnumerateSwitchBoxBarriersProc, switchBoxData: REF, optimization: Route.Optimization, signalSinglePinNets, signalCoincidentPins: BOOL, okToDiddleLLPins, okToDiddleURPins: BOOL] 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: Route.DesignRules ← DefaultDesignRules[rulesParameters];
intermediateResult: Route.IntermediateResult ← SwitchBoxRoute[enumerateNets, routingRect, rulesParameters, designRules, name, enumerateObstructions, switchBoxData, optimization, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins];
result ← SwitchBoxRetrieve[intermediateResult]};
Primitive Operations
ChannelRoute: PUBLIC PROC [enumerateNets: Route.EnumerateChannelNetsProc, min, max: CD.Number, rulesParameters: Route.DesignRulesParameters, rules: Route.DesignRules, name: Rope.ROPE, enumerateObstructions: Route.EnumerateChannelBarriersProc, channelData: REF, optimization: Route.Optimization, signalSinglePinNets, signalCoincidentPins: BOOL] RETURNS [intermediateResult: Route.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.
EachNet: Route.EachChannelNetProc ~ {
PROC [name: Label, enumeratePins: EnumerateChannelPinsProc, exitLeftOrBottom, exitRightOrTop: BOOL ← FALSE, mayExit: BOOL ← TRUE, trunkSize: CD.Number ← 0, channelData, netData: REF ← NIL];
EachPin: Route.EachChannelPinProc ~ {
PROC [bottomOrLeftSide: BOOL, min, max, depth: CD.Number ← 0, layer: CD.Layer];
side: DABasics.Side;
side ← SELECT trunkDirection FROM
horizontal => IF bottomOrLeftSide THEN bottom ELSE top,
vertical => IF bottomOrLeftSide THEN left ELSE right,
ENDCASE => Route.Error[programmingError, "Call maintainer."];
widestBranchPin ← MAX[widestBranchPin, max - min];
connections ← CONS[CreatePin[side, min, max, depth, layer], connections]};
enter the pins connected by this net
parms: RoutePrivate.RoutingAreaParms ← routingArea.parms;
netTab: RoutePrivate.NetTab ← routingArea.nets;
nextNum: NAT ← netTab.count + 1;
trunkWidth, branchWidth: CD.Number;
widestBranchPin, lowerPos, upperPos: CD.Number ← 0;
connections: RoutePrivate.PinList ← NIL;
trunkDirection: DABasics.Direction ← routingArea.ruleParameters.trunkDirection;
enumerate the pins connected by the net
enumeratePins[channelData, netData, EachPin];
trunkWidth ← IF trunkSize > 0 THEN MAX[routingArea.rules.trunkWidth, trunkSize]
ELSE MAX[routingArea.rules.trunkWidth, widestBranchPin];
branchWidth ← MAX[routingArea.rules.branchWidth, widestBranchPin, trunkWidth];
do the end pins
IF exitRightOrTop THEN {
pinSide: DABasics.Side ← IF trunkDirection = horizontal THEN right ELSE top;
upperPos ← upperPos + routingArea.rules.trunkSpacing;
connections ← CONS[CreatePin[pinSide, upperPos, upperPos + trunkWidth, 0, routingArea.rules.trunkLayer], connections];
upperPos ← upperPos + trunkWidth};
IF exitLeftOrBottom THEN {
pinSide: DABasics.Side ← IF trunkDirection = horizontal THEN left ELSE bottom;
lowerPos ← upperPos + routingArea.rules.trunkSpacing;
connections ← CONS[CreatePin[pinSide, lowerPos, lowerPos + trunkWidth, 0, routingArea.rules.trunkLayer], connections];
lowerPos ← lowerPos + trunkWidth};
parms.widestTrunk ← MAX[trunkWidth, parms.widestTrunk];
parms.widestBranch ← MAX[branchWidth, parms.widestBranch];
parms.numTracksToUse ← parms.numTracksToUse + 2*RouteChannel.InfluenceTracks[routingArea, trunkWidth];
netTab.n[nextNum] ← NEW[RoutePrivate.NetRec ← [name: name, num: nextNum, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, netData: netData, mayExit: mayExit]];
netTab.count ← nextNum};
EachObstruction: Route.EachChannelBarrierProc ~ {
PROC [side: DABasics.Side, min, max, depth: CD.Number, layer: CD.Layer];
};
parms: RoutePrivate.RoutingAreaParms ← NEW[RoutePrivate.RoutingAreaParmsRec];
routingSides: RoutePrivate.RoutingAreaSides ← NEW[RoutePrivate.RoutingAreaSidesRec ← [NIL, NIL, NIL, NIL]];
nets: RoutePrivate.NetTab ← NEW[RoutePrivate.NetTabRec ← [size: RoutePrivate.maxNets, count: 0, n: ALL[NIL]]];
routingArea: RoutePrivate.RoutingArea ← NEW[RoutePrivate.RoutingAreaRec ← [name: name, ruleParameters: rulesParameters, rules: rules, routingSides: routingSides, nets: nets, parms: parms, channelData: channelData]];
routingRect: DABasics.Rect ← IF rulesParameters.trunkDirection = horizontal THEN [min, 0, max, routingArea.rules.trunkToTrunk] ELSE [0, min, routingArea.rules.trunkToTrunk, max];
enumerateNets[channelData, EachNet];
IF enumerateObstructions # NIL THEN {
enumerateObstructions[channelData, EachObstruction]};
RouteChannel.InitChannel[routingArea, routingRect, channel, signalSinglePinNets, signalCoincidentPins, FALSE, FALSE];
intermediateResult ← IF RouteChannel.GenerateConstraints[routingArea, channel] THEN
RouteChannel.TopoWiring[routingArea, optimization]
ELSE
NEW[Route.IntermediateResultRec ← [routingArea: routingArea, routingRect: routingRect]]};
ChannelRetrieve: PUBLIC PROC [intermediateResult: Route.IntermediateResult, brokenNets: Route.BrokenNetProc, channelData: REF, retrieveRect: REF DABasics.Rect ← NIL] RETURNS [result: Route.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.
routingArea: RoutePrivate.RoutingArea ← NARROW[intermediateResult.routingArea];
rect: DABasics.Rect ← IF retrieveRect = NIL THEN intermediateResult.routingRect
ELSE CDBasics.Surround[retrieveRect^, intermediateResult.routingRect];
object: CD.Object;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
parms.viaTable ← RefTab.Create[equal: EqualProc, hash: HashProc];
parms.entityTable ← SymTab.Create[];
RouteChannel.GetRouting[routingArea, rect, brokenNets, RouteChannel.RetrieveSegments, RouteChannel.RetrieveVias, RouteChannel.RetrieveIncompletes];
object ← CDRoutingObjects.CreateRoutingObject[CDRoutingObjects.CreateNodes[routingArea.parms.entityTable], rect];
result ← NEW[Route.ResultRec ← [
object: object,
polyLength: intermediateResult.polyLength,
metalLength: intermediateResult.metalLength,
metal2Length: intermediateResult.metal2Length,
polyToMetal: intermediateResult.polyToMetal,
metalToMetal2: intermediateResult.metalToMetal2,
numTrunkTracks: intermediateResult.numTrunkTracks,
numIncompletes: intermediateResult.numIncompletes,
incompleteNets: intermediateResult.incompleteNets]];
RouteChannel.Destroy[routingArea]};
SwitchBoxRoute: PUBLIC PROC [enumerateNets: Route.EnumerateSwitchBoxNetsProc,
routingRect: DABasics.Rect, rulesParameters: Route.DesignRulesParameters,
rules: Route.DesignRules, name: Rope.ROPE,
enumerateObstructions: Route.EnumerateSwitchBoxBarriersProc,
switchBoxData: REF,
optimization: Route.Optimization,
signalSinglePinNets, signalCoincidentPins: BOOL,
okToDiddleLLPins, okToDiddleURPins: BOOL]
RETURNS [intermediateResult: Route.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.
EachNet: Route.EachSwitchBoxNetProc ~ {
PROC [name: Label, enumeratePins: EnumerateSwitchBoxPinsProc, trunkSize: CD.Number ← 0, switchBoxData: REF, netData: REF
EachPin: Route.EachSwitchBoxPinProc ~ {
PROC [side: DABasics.Side, min, max, depth: CD.Number ← 0, layer: CD.Layer];
widestBranchPin ← MAX[widestBranchPin, max - min];
connections ← CONS[CreatePin[side, min, max, depth, layer], connections]};
enter the pins connected by this net
parms: RoutePrivate.RoutingAreaParms ← routingArea.parms;
netTab: RoutePrivate.NetTab ← routingArea.nets;
nextNum: NAT ← netTab.count + 1;
trunkWidth, branchWidth: CD.Number;
widestBranchPin, lowerPos, upperPos: CD.Number ← 0;
connections: RoutePrivate.PinList ← NIL;
trunkDirection: DABasics.Direction ← routingArea.ruleParameters.trunkDirection;
enumerate the pins connected by the net
enumeratePins[switchBoxData, netData, EachPin];
trunkWidth ← IF trunkSize > 0 THEN MAX[routingArea.rules.trunkWidth, trunkSize]
ELSE MAX[routingArea.rules.trunkWidth, widestBranchPin];
branchWidth ← MAX[routingArea.rules.branchWidth, widestBranchPin, trunkWidth];
parms.widestTrunk ← MAX[trunkWidth, parms.widestTrunk];
parms.widestBranch ← MAX[branchWidth, parms.widestBranch];
parms.numTracksToUse ← parms.numTracksToUse + 2*RouteChannel.InfluenceTracks[routingArea, trunkWidth];
netTab.n[nextNum] ← NEW[RoutePrivate.NetRec ← [name: name, num: nextNum, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, mayExit: FALSE]];
netTab.count ← nextNum};
EachObstruction: Route.EachSwitchBoxBarrierProc ~ {
PROC [side: DABasics.Side, min, max, depth: CD.Number, layer: CD.Layer];
};
parms: RoutePrivate.RoutingAreaParms ← NEW[RoutePrivate.RoutingAreaParmsRec];
routingSides: RoutePrivate.RoutingAreaSides ← NEW[RoutePrivate.RoutingAreaSidesRec ← [NIL, NIL, NIL, NIL]];
nets: RoutePrivate.NetTab ← NEW[RoutePrivate.NetTabRec ← [size: RoutePrivate.maxNets, count: 0, n: ALL[NIL]]];
routingArea: RoutePrivate.RoutingArea ← NEW[RoutePrivate.RoutingAreaRec ← [name: name, ruleParameters: rulesParameters, rules: rules, routingSides: routingSides, nets: nets, parms: parms, channelData: switchBoxData]];
enumerateNets[switchBoxData, EachNet];
IF enumerateObstructions # NIL THEN {
enumerateObstructions[switchBoxData, EachObstruction]};
RouteChannel.InitChannel[routingArea, routingRect, switchBox, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins];
intermediateResult ← IF RouteChannel.GenerateConstraints[routingArea, switchBox] THEN
RouteChannel.TopoWiring[routingArea, optimization]
ELSE
NEW[Route.IntermediateResultRec ← [routingArea: routingArea, routingRect: routingRect]]};
SwitchBoxRetrieve: PUBLIC PROC [intermediateResult: Route.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.
routingArea: RoutePrivate.RoutingArea ← NARROW[intermediateResult.routingArea];
object: CD.Object;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
parms.viaTable ← RefTab.Create[equal: EqualProc, hash: HashProc];
parms.entityTable ← SymTab.Create[];
RouteChannel.GetRouting[routingArea, intermediateResult.routingRect, NIL, RouteChannel.RetrieveSegments, RouteChannel.RetrieveVias, RouteChannel.RetrieveIncompletes];
object ← CDRoutingObjects.CreateRoutingObject[CDRoutingObjects.CreateNodes[routingArea.parms.entityTable], intermediateResult.routingRect];
result ← NEW[Route.ResultRec ← [
object: object,
polyLength: intermediateResult.polyLength,
metalLength: intermediateResult.metalLength,
metal2Length: intermediateResult.metal2Length,
polyToMetal: intermediateResult.polyToMetal,
metalToMetal2: intermediateResult.metalToMetal2,
numTrunkTracks: intermediateResult.numTrunkTracks,
numIncompletes: intermediateResult.numIncompletes,
incompleteNets: intermediateResult.incompleteNets]];
RouteChannel.Destroy[routingArea]};
DefaultDesignRules: PUBLIC PROC [designRuleParameters: Route.DesignRulesParameters] RETURNS [designRules: Route.DesignRules] ~ {
get design rules from parameters
designRules ← RouteTechnology.CmosDesignRules[designRuleParameters]};
Internal Procedures
CreatePin: PROC [side: DABasics.Side, min, max, depth: DABasics.Number, layer: CD.Layer] RETURNS [pin: RoutePrivate.Pin] ~ {
construct a RoutePrivate.Pin
pin ← NEW[RoutePrivate.PinRec ← [side: side, min: min, max: max, depth: depth, layer: layer]]};
EqualProc: RefTab.EqualProc = {
p1: DABasics.Position ← NARROW[key1, REF DABasics.Position]^;
p2: DABasics.Position ← NARROW[key2, REF DABasics.Position]^;
RETURN [p1.x = p2.x AND p1.y = p2.y]};
HashProc: RefTab.HashProc = {
size: DABasics.Position ← NARROW[key, REF DABasics.Position]^;
RETURN [size.x + size.y]};
}.