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 = { Error: PUBLIC ERROR[errorType: Route.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE; Signal: PUBLIC SIGNAL[errorType: Route.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE; DefaultDesignRulesParameters: PUBLIC PROC [technologyHint: REF, horizLayer, vertLayer: CD.Layer, trunkDirection: DABasics.Direction] RETURNS [designRules: Route.DesignRulesParameters] = { 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: 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] = { 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]; }; 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] = { designRules: Route.DesignRules _ DefaultDesignRules[rulesParameters]; intermediateResult: Route.IntermediateResult _ SwitchBoxRoute[enumerateNets, routingRect, rulesParameters, designRules, name, enumerateObstructions, switchBoxData, optimization, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins]; result _ SwitchBoxRetrieve[intermediateResult]}; 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] = { EachNet: Route.EachChannelNetProc ~ { EachPin: Route.EachChannelPinProc ~ { 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]}; 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; 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]; 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: NIL, mayExit: mayExit]]; netTab.count _ nextNum}; EachObstruction: Route.EachChannelBarrierProc ~ { }; 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] = { EachNet: Route.EachChannelNetProc ~ { 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] = { EachNet: Route.EachSwitchBoxNetProc ~ { EachPin: Route.EachSwitchBoxPinProc ~ { widestBranchPin _ MAX[widestBranchPin, max - min]; connections _ CONS[CreatePin[side, min, max, depth, layer], connections]}; 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; 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 ~ { }; 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] = { 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] ~ { designRules _ RouteTechnology.CmosDesignRules[designRuleParameters]}; CreatePin: PROC [side: DABasics.Side, min, max, depth: DABasics.Number, layer: CD.Layer] RETURNS [pin: 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]}; }. €RouteImpl.mesa Copyright c 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 Errors Design Rules Define the routing design rules. tech must define a ChipNDale technology. Channel 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. Switch Box 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. Primitive Operations 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. PROC [name: Label, enumeratePins: EnumerateChannelPinsProc, exitLeftOrBottom, exitRightOrTop: BOOL _ FALSE, mayExit: BOOL _ TRUE, trunkSize: CD.Number _ 0, channelData, netData: REF _ NIL]; PROC [bottomOrLeftSide: BOOL, min, max, depth: CD.Number _ 0, layer: CD.Layer]; enter the pins connected by this net enumerate the pins connected by the net do the end pins netTab.n[nextNum] _ NEW[RoutePrivate.NetRec _ [name: name, num: nextNum, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, netData: netData, mayExit: mayExit]]; PROC [side: DABasics.Side, min, max, depth: CD.Number, layer: CD.Layer]; 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. PROC [name: Label, enumeratePins: EnumerateChannelPinsProc, exitLeftOrBottom, exitRightOrTop: BOOL _ FALSE, mayExit: BOOL _ TRUE, trunkSize: CD.Number _ 0, channelData, netData: REF _ NIL]; 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. PROC [name: Label, enumeratePins: EnumerateSwitchBoxPinsProc, trunkSize: CD.Number _ 0, switchBoxData: REF, netData: REF PROC [side: DABasics.Side, min, max, depth: CD.Number _ 0, layer: CD.Layer]; enter the pins connected by this net enumerate the pins connected by the net PROC [side: DABasics.Side, min, max, depth: CD.Number, layer: CD.Layer]; 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. get design rules from parameters Internal Procedures construct a Route.Pin ส .˜codešœ™Kšœ ฯmœ7™BKšœ'ฯkœ™+Kšœ5™5K™2—K˜šž ˜ Kšžœ‰˜‹—K˜šัbln œžœžœ˜Kšžœd˜kKšžœ ˜—head™Kš ฯnœžœžœ>žœžœžœ˜dKš  œžœžœ>žœžœžœ˜f—™ š  œžœžœžœžœ,žœ/˜ปKšœ"™"Kšœ(™(K˜šžœžœžœ˜Kšœžœ:˜BKšœa˜a—šžœฯc˜Kšœ+˜+—Kšœ˜——™š œžœžœ1˜EKšœ˜Kšœžœ ˜Kšœ.˜.Kšœ žœ˜Kšœ!˜!Kšœ;˜;Kšœ žœ˜Kšœ"˜"Kšœ˜Kšœžœ˜Kšžœ˜"Kšœg™gKšœ]™]˜KšœF˜FKšœึ˜ึKšœU˜UKšœ˜———™ š  œžœžœ3˜IKšœ˜Kšœ.˜.Kšœ žœ˜Kšœ=˜=Kšœžœ˜Kšœ"˜"Kšœ˜Kšœžœ˜Kšœ˜Kšœžœ˜Kšžœ˜"Kšœ™™™Kšœ]™]—˜KšœF˜FKšœ˜Kšœ0˜0——™š  œžœžœ1˜JKšœ˜Kšœžœ ˜Kšœ.˜.Kšœ˜Kšœ žœ˜Kšœ;˜;Kšœ žœ˜Kšœ"˜"Kšœ˜Kšœžœ˜Kšžœ3˜:Kšœg™gKšœ]™]K˜š œ˜%KšžœZžœžœ žœžœ žœ#žœžœ™ฝK˜š œ˜%Kšžœžœžœžœ™OK˜Kšœ˜šœžœž˜!Kšœžœžœžœ˜7Kšœ žœžœžœ˜5Kšžœ6˜=—Kšœžœ˜2Kšœžœ8˜JK˜—Kšœ$™$Kšœ9˜9Kšœ/˜/Kšœ žœ˜ Kšœžœ˜#Kšœ%žœ ˜3Kšœžœ˜!KšœO˜OK˜Kšœ'™'Kšœ-˜-K˜šœ žœžœžœ)˜OKšžœžœ0˜8—Kšœžœ=˜NK˜Kšœ™šžœžœ˜Kšœžœžœžœ˜LKšœ5˜5Kšœžœd˜vKšœ"˜"—šžœžœ˜Kšœžœžœžœ˜NKšœ5˜5Kšœžœd˜vKšœ"˜"K˜—Kšœžœ ˜7Kšœžœ"˜:Kšœ`˜`KšœžœŸ™ถKšœžœƒžœ˜ฒKšœ˜K˜—š œ"˜1Kšžœ(žœžœ™HK˜K˜—Kšœžœ ˜#Kšœ žœ)˜7Kšœ'žœ#˜MKš œ.žœ%žœžœžœžœ˜kKšœžœDžœžœ˜nKšœ(žœฌ˜ืKšœžœ-žœ#žœ#˜šKšœ!˜!Kšœžœ˜3Kšœžœ˜5Kšœžœ˜2Kšœ˜Kšœ ˜ Kšœ$˜$Kšžœžœžœ5˜XKšœqžœžœ˜šœ#˜#K˜—šœžœCž˜^Kšžœl˜o—šž˜Kšžœ-žœ5˜h—Kšœ˜K˜—š œžœžœ0˜LKšœ.˜.Kšœ!˜!Kšœ žœžœ˜Kšœžœžœ˜'Kšžœ˜"Kšœg™gKšœ]™]K™š œ˜%KšžœZžœžœ žœžœ žœ#žœžœ™ฝKšœ˜Kšœ"˜"Kšœ˜K˜—Kšœžœ˜Kšœ(žœ!˜OKšœ/˜/Kšœ-˜-Kšœžœžœžœ*˜ZKšžœM˜QKšœžœ˜Kšœžœžœ˜EKšœ'žœ˜AKšœA˜AKšœ$˜$K˜Kšœ$˜$Kšœธ˜ธKšœq˜qšœ žœ˜ Kšœ˜Kšœ5˜5Kšœ7˜7Kšœ9˜9Kšœ7˜7Kšœ;˜;Kšœ=˜=Kšœ=˜=Kšœ?˜?—Kšœ˜Kšœ˜K˜—š œžœžœ2˜MKšœ˜Kšœ-˜-Kšœ˜Kšœ žœ˜Kšœ<˜Kšžœ˜K˜—Kšœ˜—K˜K˜K˜K˜—…—6|N*