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
Christian Le Cocq December 10, 1987 3:36:56 pm PST
DIRECTORY
CD, CDBasics, CDRoutingObjects, CDSimpleRules, DABasics, RefTab, Rope, Route, RouteChannel, RoutePrivate, RouteTechnology, RTBasic, SymTab;
RouteImpl: CEDAR PROGRAM
IMPORTS CD, 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, enumerateNets, 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: Route.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[rules, trunkWidth];
netTab.n[nextNum] ← NEW[RoutePrivate.NetRec ← [name: name, num: nextNum, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, netData: netData, mayExit: mayExit]];
netTab.n[nextNum] ← NEW[RoutePrivate.NetRec ← [name: name, num: nextNum, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, netData: NIL, mayExit: mayExit]];
netTab.count ← nextNum};
EachObstruction: Route.EachChannelBarrierProc ~ {
PROC [side: DABasics.Side, min, max, depth: CD.Number, layer: CD.Layer];
};
chanData: RouteChannel.ChannelData;
technology: CD.Technology ← rulesParameters.technology;
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, rules.trunkToTrunk] ELSE [0, min, rules.trunkToTrunk, max];
parms.lambda ← technology.lambda;
parms.metalLayer ← CD.FetchLayer[technology, $met];
parms.metal2Layer ← CD.FetchLayer[technology, $met2];
parms.polyLayer ← CD.FetchLayer[technology, $pol];
parms.routerUsed ← channel;
parms.routingRect ← routingRect;
enumerateNets[channelData, EachNet];
IF enumerateObstructions # NIL THEN enumerateObstructions[channelData, EachObstruction];
chanData ← RouteChannel.InitChannel[routingSides, parms, rules, nets, signalSinglePinNets, signalCoincidentPins, FALSE, FALSE];
routingArea.privateData ← chanData;
intermediateResult ← IF RouteChannel.GenerateConstraints[chanData, parms, rules, channel] THEN
NEW[Route.IntermediateResultRec ← [routingArea, RouteChannel.TopoWiring[chanData, parms, rules, optimization]]]
ELSE
NEW[Route.IntermediateResultRec ← [routingArea, NEW[Route.ResultDataRec ← [routingRect: routingRect]]]];
};
ChannelRetrieve: PUBLIC PROC [intermediateResult: Route.IntermediateResult,
enumerateNets: Route.EnumerateChannelNetsProc,
brokenNets: Route.BrokenNetProc,
channelData: REF← NIL,
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.
EachNet: Route.EachChannelNetProc ~ {
PROC [name: Label, enumeratePins: EnumerateChannelPinsProc, exitLeftOrBottom, exitRightOrTop: BOOL ← FALSE, mayExit: BOOL ← TRUE, trunkSize: CD.Number ← 0, channelData, netData: REF ← NIL];
index ← index + 1;
netTab.n[index].netData ← netData;
};
index: NAT ← 0;
routingArea: RoutePrivate.RoutingArea ← NARROW[intermediateResult.routingArea];
netTab: RoutePrivate.NetTab ← routingArea.nets;
rules: Route.DesignRules ← routingArea.rules;
rect: DABasics.Rect ← IF retrieveRect = NIL THEN intermediateResult.resultData.routingRect
ELSE CDBasics.Surround[retrieveRect^, intermediateResult.resultData.routingRect];
object: CD.Object;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
parms.viaTable ← RefTab.Create[equal: EqualProc, hash: HashProc];
parms.entityTable ← SymTab.Create[];
enumerateNets[channelData, EachNet];
RouteChannel.GetRouting[chanData, parms, rules, rect, brokenNets, routingArea.channelData, RouteChannel.RetrieveSegments, RouteChannel.RetrieveVias, RouteChannel.RetrieveIncompletes];
object ← CDRoutingObjects.CreateRoutingObject[CDRoutingObjects.CreateNodes[routingArea.parms.entityTable], rect];
result ← NEW[Route.ResultRec ← [
object: object,
polyLength: intermediateResult.resultData.polyLength,
metalLength: intermediateResult.resultData.metalLength,
metal2Length: intermediateResult.resultData.metal2Length,
polyToMetal: intermediateResult.resultData.polyToMetal,
metalToMetal2: intermediateResult.resultData.metalToMetal2,
numTrunkTracks: intermediateResult.resultData.numTrunkTracks,
numIncompletes: intermediateResult.resultData.numIncompletes,
incompleteNets: intermediateResult.resultData.incompleteNets]];
RouteChannel.Destroy[chanData];
};
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: Route.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[rules, 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];
};
chanData: RouteChannel.ChannelData;
technology: CD.Technology ← rulesParameters.technology;
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]];
parms.lambda ← technology.lambda;
parms.metalLayer ← CD.FetchLayer[technology, $met];
parms.metal2Layer ← CD.FetchLayer[technology, $met2];
parms.polyLayer ← CD.FetchLayer[technology, $pol];
parms.routerUsed ← switchBox;
parms.routingRect ← routingRect;
enumerateNets[switchBoxData, EachNet];
IF enumerateObstructions # NIL THEN {
enumerateObstructions[switchBoxData, EachObstruction]};
chanData ← RouteChannel.InitChannel[routingSides, parms, rules, nets, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins];
routingArea.privateData ← chanData;
intermediateResult ← IF RouteChannel.GenerateConstraints[chanData, parms, rules, switchBox] THEN
NEW[Route.IntermediateResultRec ← [routingArea, RouteChannel.TopoWiring[chanData, parms, rules, optimization]]]
ELSE
NEW[Route.IntermediateResultRec ← [routingArea, NEW[Route.ResultDataRec ← [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];
rules: Route.DesignRules ← routingArea.rules;
object: CD.Object;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
parms.viaTable ← RefTab.Create[equal: EqualProc, hash: HashProc];
parms.entityTable ← SymTab.Create[];
RouteChannel.GetRouting[chanData, parms, rules, intermediateResult.resultData.routingRect, NIL, NIL, RouteChannel.RetrieveSegments, RouteChannel.RetrieveVias, RouteChannel.RetrieveIncompletes];
object ← CDRoutingObjects.CreateRoutingObject[CDRoutingObjects.CreateNodes[routingArea.parms.entityTable], intermediateResult.resultData.routingRect];
result ← NEW[Route.ResultRec ← [
object: object,
polyLength: intermediateResult.resultData.polyLength,
metalLength: intermediateResult.resultData.metalLength,
metal2Length: intermediateResult.resultData.metal2Length,
polyToMetal: intermediateResult.resultData.polyToMetal,
metalToMetal2: intermediateResult.resultData.metalToMetal2,
numTrunkTracks: intermediateResult.resultData.numTrunkTracks,
numIncompletes: intermediateResult.resultData.numIncompletes,
incompleteNets: intermediateResult.resultData.incompleteNets]];
RouteChannel.Destroy[chanData];
};
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: Route.Pin] ~ {
construct a Route.Pin
pin ← NEW[Route.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]};
}.