<> <> <> <> <> DIRECTORY Basics, CD, CDPinObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO; RouteChannelTopolImpl: CEDAR PROGRAM IMPORTS CD, CDPinObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO EXPORTS RouteChannel SHARES Route = BEGIN SegProc: TYPE = PROC[seg: RouteChannel.Segment, activeTrackSpec: RouteChannel.ActiveTrackSpec] RETURNS [quit: BOOLEAN _ FALSE, segSpec: RouteChannel.ActiveSegSpec _ NIL]; debug: BOOLEAN _ FALSE; stopTrack: NAT _ 50; TopoWiring: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, opt: Route.Optimization] RETURNS [bestResult: Route.RoutingResult] = { <> <<>> lastMethod: RouteChannel.Method _ NEW[RouteChannel.MethodRec]; bestMethod: RouteChannel.Method; result: Route.RoutingResult; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; <> maxL: NAT = LAST[NAT]; bestResult _ NEW[Route.RoutingResultRec _ [routingArea, maxL, maxL, maxL, maxL, maxL, maxL, maxL, Route.Rect[maxL, maxL, maxL, maxL]]]; <> FOR method: RouteChannel.Method _ GetNextMethod[lastMethod], GetNextMethod[lastMethod] WHILE method # NIL DO result _ RouteOneChan[routingArea, method]; lastMethod _ method; IF debug THEN RouteChannel.WriteResult[result, method]; IF RouteUtil.CompareResult[result, bestResult] = less THEN {bestResult _ result; bestMethod _ method}; IF opt = noIncompletes AND bestResult.numIncompletes = 0 THEN EXIT; ENDLOOP; <> IF bestMethod # lastMethod THEN bestResult _ RouteOneChan[routingArea, bestMethod]; RouteChannel.WriteResult[bestResult, bestMethod]}; GetNextMethod: PROCEDURE [currentMethod: RouteChannel.Method] RETURNS [nextMethod: RouteChannel.Method] = { SELECT currentMethod.directionSequence FROM start => nextMethod _ NEW[RouteChannel.MethodRec _ [outsideInTop, leftToRight]]; leftToRight => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, rightToLeft]]; rightToLeft => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateLeft]]; alternateLeft => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateRight]]; alternateRight => BEGIN nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, leftToRight]]; SELECT currentMethod.trackSequence FROM start => nextMethod.trackSequence _ outsideInTop; outsideInTop => nextMethod.trackSequence _ outsideInBottom; outsideInBottom => nextMethod.trackSequence _ botToTop; botToTop => nextMethod.trackSequence _ topToBot; topToBot => nextMethod _ NIL; ENDCASE; END; ENDCASE; IF debug AND nextMethod # NIL THEN { TerminalIO.WriteRope[Rope.Cat["\nNew method: ", RouteChannel.directionSequenceName[nextMethod.directionSequence], ", ", RouteChannel.trackSequenceName[nextMethod.trackSequence]]]}; }; RouteOneChan: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] RETURNS [result: Route.RoutingResult] = { <> InitOneChan[routingArea]; PreAssignSegs[routingArea, method]; AssignVariableSegs[routingArea, method]; result _ AnalyzeResult[routingArea]; }; -- RouteOneChan InitOneChan: PROCEDURE[routingArea: Route.RoutingArea] = { <> <> SetTrackPos: RouteChannel.EachTrackActionProc = { chanTracks.tracks[trackIndex].trackNum _ trackIndex; chanTracks.tracks[trackIndex].firstSeg _ NIL; chanTracks.tracks[trackIndex].keep _ FALSE}; ClearSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN {FOR LRSide: RouteChannel.ChanLRSide IN RouteChannel.ChanLRSide DO seg: RouteChannel.Segment _ pin.conctSeg[LRSide]; IF seg # NIL THEN {seg.trackNum _ 0; seg.nextSeg _ NIL} ENDLOOP}}; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanTracks.count _ chanTracks.maxCount; [] _ RouteChannel.EnumTracks[routingArea, SetTrackPos]; <> FOR posIndex: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pinPos: RouteChannel.PinPosition _ chanPins.sides[posIndex]; [] _ RouteChannel.EnumPins[routingArea, pinPos, ClearSegs] ENDLOOP}; -- InitOneChan PreAssignSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = { <> PreSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND seg.trackConstraint # 0 AND ~seg.failed THEN { segSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: seg, segLayer: CanConvert[routingArea, seg]]]; quit _ FitSegment[routingArea, segSpec, activeTrackSpec, FALSE]}; }; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; <> FOR activeTrackSpec: RouteChannel.ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE activeTrackSpec # NIL DO <<>> <> FOR activeSegSpec: RouteChannel.ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, PreSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, PreSegProc] WHILE activeSegSpec # NIL DO <> PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; ENDLOOP; -- FOR GetNextSegment ENDLOOP; -- FOR activeTrackSpec: }; -- PreAssignSegs AssignVariableSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = { <> AsgnSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND ~seg.failed THEN { segSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: seg, segLayer: CanConvert[routingArea, seg]]]; quit _ FitSegment[routingArea, segSpec, activeTrackSpec, TRUE]}; }; moreToDo: BOOLEAN _ TRUE; numTracksWOSegs: NAT _ 0; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; <> FOR activeTrackSpec: RouteChannel.ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE moreToDo AND activeTrackSpec # NIL DO segOnThisTrack: BOOLEAN _ FALSE; <<>> <> FOR activeSegSpec: RouteChannel.ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, AsgnSegProc] WHILE activeSegSpec # NIL DO <> stillGoing: BOOLEAN _ TRUE; nextSegSpec: RouteChannel.ActiveSegSpec; PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE; nextSegSpec _ FollowingSeg[routingArea, activeSegSpec, activeTrackSpec, TRUE]; WHILE nextSegSpec # NIL AND stillGoing DO fits: BOOLEAN; nextSegSpec.segLayer _ CanConvert[routingArea, nextSegSpec.seg]; fits _ FitSegment[routingArea, nextSegSpec, activeTrackSpec, TRUE]; IF fits THEN {PlaceSegment[routingArea, nextSegSpec, activeTrackSpec]; nextSegSpec _ FollowingSeg[routingArea, nextSegSpec, activeTrackSpec, TRUE]} ELSE stillGoing _ FALSE; ENDLOOP; -- WHILE nextSeg # NIL ENDLOOP; -- FOR GetNextSegment <> IF segOnThisTrack THEN {numTracksWOSegs _ 0; moreToDo _ TRUE} ELSE { numTracksWOSegs _ numTracksWOSegs+ 1; IF parms.routerUsed = channel AND numTracksWOSegs >= chanData.chanParms.emptyTrackLimit THEN moreToDo _ FALSE}; ENDLOOP; -- WHILE moreToDo }; -- AssignVariableSegs NextTrack: PROCEDURE[routingArea: Route.RoutingArea, activeTrackSpec: RouteChannel.ActiveTrackSpec, method: RouteChannel.Method] RETURNS [nextTrackSpec: RouteChannel.ActiveTrackSpec] = { <> OutsideInTopStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = { IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1] ELSE RETURN[track = chanTracks.count/2]}; OutsideInBottomStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = { RETURN[track = chanTracks.count/2 + 1]}; trialTrack: RouteChannel.ZMaxTracks; freeArea: RouteChannel.AboveOrBelow; going: RouteChannel.GoingDirection; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; IF activeTrackSpec = NIL THEN { SELECT method.trackSequence FROM outsideInTop => {trialTrack _ chanTracks.count; freeArea _ below}; outsideInBottom => {trialTrack _ 1; freeArea _ above}; botToTop => {trialTrack _ 1; freeArea _ above}; topToBot => {trialTrack _ chanTracks.count; freeArea _ below}; ENDCASE => Route.Error[programmingError, "Pack direction error"]; SELECT method.directionSequence FROM leftToRight, alternateLeft => going _ leftToRight; rightToLeft, alternateRight => going _ rightToLeft; ENDCASE => Route.Error[programmingError, "Pack direction error"]} ELSE { -- keep going IF ~(activeTrackSpec.track IN RouteChannel.MaxTracks) THEN Route.Error[programmingError, "Invalid track state"]; SELECT method.trackSequence FROM outsideInTop => IF OutsideInTopStop[activeTrackSpec.track] THEN trialTrack _ 0 ELSE IF activeTrackSpec.track > chanTracks.count/2 THEN {trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ above} ELSE {trialTrack _ chanTracks.count - activeTrackSpec.track; freeArea _ below}; outsideInBottom => IF OutsideInBottomStop[activeTrackSpec.track] THEN trialTrack _ 0 ELSE IF activeTrackSpec.track <= chanTracks.count/2 THEN {trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ below} ELSE {trialTrack _ chanTracks.count - activeTrackSpec.track + 2; freeArea _ above}; botToTop => IF activeTrackSpec.track >= chanTracks.count THEN trialTrack _ 0 ELSE {trialTrack _ activeTrackSpec.track + 1; freeArea _ above}; topToBot => IF activeTrackSpec.track <= 1 THEN trialTrack _ 0 ELSE {trialTrack _ activeTrackSpec.track - 1; freeArea _ below}; ENDCASE => Route.Error[programmingError, "Pack direction error"]; SELECT method.directionSequence FROM leftToRight => going _ leftToRight; rightToLeft => going _ rightToLeft; alternateLeft => IF activeTrackSpec.going = leftToRight THEN going _ rightToLeft ELSE going _ leftToRight; alternateRight => IF activeTrackSpec.going = rightToLeft THEN going _ leftToRight ELSE going _ rightToLeft; ENDCASE => Route.Error[programmingError, "Pack direction error"]}; <> IF ~(trialTrack IN [1 .. chanTracks.count]) THEN nextTrackSpec _ NIL ELSE {nextTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec]; BuildTrackSpec[routingArea, trialTrack, chanTracks.count, going, freeArea, nextTrackSpec]; IF debug THEN {TerminalIO.WriteRope[Rope.Cat["\n New track: ", Convert.RopeFromInt[trialTrack], ", min Act: ", Convert.RopeFromInt[nextTrackSpec.minActTrack]]]; TerminalIO.WriteRope[Rope.Cat[", max Act: ", Convert.RopeFromInt[nextTrackSpec.maxActTrack]]]; TerminalIO.WriteRope[Rope.Cat["\n going: ", RouteChannel.GoingName[going], ", free area: ", RouteChannel.AboveOrBelowName[freeArea]]]}}; }; -- NextTrack <> PlaceSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec] = { chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; track: RouteChannel.ZMaxTracks _ activeTrackSpec.track; mustKeep: RouteChannel.ZMaxTracks _ RouteChannel.InfluenceTracks[routingArea, activeSegSpec.seg.net.trunkWidth]; lowerTrack: RouteChannel.ZMaxTracks _ MAX[track - mustKeep, 1]; upperTrack: RouteChannel.ZMaxTracks _ MIN[track + mustKeep, chanTracks.count]; firstSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, track]; <> IF activeSegSpec.seg.trackNum # 0 THEN Route.Error[programmingError, "Track state error"] ELSE activeSegSpec.seg.trackNum _ track; activeSegSpec.seg.routingLayer _ activeSegSpec.segLayer; FOR keepTrack: RouteChannel.ZMaxTracks IN [lowerTrack .. upperTrack] DO chanTracks.tracks[keepTrack].keep _ TRUE ENDLOOP; <> IF firstSeg = NIL THEN { <> activeSegSpec.seg.nextSeg _ NIL; chanTracks.tracks[track].firstSeg _ activeSegSpec.seg} ELSE IF activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pLoc <= firstSeg.exteriorPins[chanLeft].pinPosition.pLoc THEN { <> activeSegSpec.seg.nextSeg _ firstSeg; chanTracks.tracks[track].firstSeg _ activeSegSpec.seg} ELSE { nextSeg: RouteChannel.Segment; lastSeg: RouteChannel.Segment _ firstSeg; FOR nextSeg _ lastSeg.nextSeg, lastSeg.nextSeg WHILE nextSeg # NIL DO IF lastSeg.exteriorPins[chanRight].pinPosition.pLoc <= activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pLoc THEN EXIT; lastSeg _ nextSeg; ENDLOOP; lastSeg.nextSeg _ activeSegSpec.seg; activeSegSpec.seg.nextSeg _ nextSeg}}; -- PlaceSegment <<>> FitSegment: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, useConstraints: BOOLEAN] RETURNS [fitsSoFar: BOOLEAN _ FALSE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; blocked: BOOLEAN _ chanData.chanTracks.tracks[trackNum].blocked; trackConstraint: RouteChannel.ZMaxTracks _ nextSegSpec.seg.trackConstraint; IF (trackConstraint # 0 AND trackConstraint # activeTrackSpec.track) OR blocked THEN RETURN[fitsSoFar]; <<>> <> fitsSoFar _ FitSegmentThisTrack[routingArea, nextSegSpec, activeTrackSpec]; <<>> <> IF fitsSoFar THEN fitsSoFar _ FitSegmentAdjTracks[routingArea, nextSegSpec, activeTrackSpec, chanData.chanTracks.count]; <<>> <> IF fitsSoFar AND useConstraints THEN fitsSoFar _ FitSegmentConstraints[routingArea, nextSegSpec, activeTrackSpec]; RETURN[fitsSoFar]}; -- FitSegment FitSegmentThisTrack: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; rules: Route.DesignRules _ routingArea.rules; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; <> FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, trackNum], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO IF existingSeg.net.netNum # trialSeg.net.netNum OR existingSeg.net.netPart # trialSeg.net.netPart THEN { trunkTrunk: Route.Number _ rules.contactToContact - rules.branchSpacing; trunkBranch: Route.Number _ rules.branchToContact - rules.branchSpacing; branchBranch: Route.Number _ rules.branchSpacing; SELECT TRUE FROM segLayer = trunk AND existingSeg.routingLayer = trunk => fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, trunkTrunk]; segLayer = trunk AND existingSeg.routingLayer = branch => fitsSoFar _ ~EndOverlapCheck[existingSeg, trialSeg, trunkBranch]; segLayer = branch AND existingSeg.routingLayer = trunk => fitsSoFar _ ~EndOverlapCheck[trialSeg, existingSeg, trunkBranch]; segLayer = branch AND existingSeg.routingLayer = branch => fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, branchBranch]; ENDCASE}; ENDLOOP}; -- FitSegmentThisTrack FitSegmentAdjTracks: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; firstPass: BOOLEAN _ TRUE; rules: Route.DesignRules _ routingArea.rules; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; pinsOnTrialSeg: RouteChannel.ChanPinList; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; trialPos: Route.Number _ RouteChannel.TrackLoc[routingArea, trackNum]; edgeSpacing: Route.Number _ rules.trunkSpacing; maxPos: Route.Number _ RouteChannel.TrackLoc[routingArea, maxTrack] + rules.trunkToEdge - edgeSpacing; minPos: Route.Number _ RouteChannel.TrackLoc[routingArea, 1] - rules.trunkToEdge + edgeSpacing; segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; qTrunkTrunk: Route.Number _ rules.trunkSpacing; <<>> <> IF maxPos < trialPos + trialSeg.qWidth/2 OR trialPos - trialSeg.qWidth/2 < minPos THEN fitsSoFar _ FALSE; <> FOR adjTrack: RouteChannel.MaxTracks IN [activeTrackSpec.minActTrack .. activeTrackSpec.maxActTrack] WHILE fitsSoFar DO IF adjTrack # activeTrackSpec.track THEN { adjTrackPos: Route.Number _ RouteChannel.TrackLoc[routingArea, adjTrack]; contactToContact: Route.Number _ rules.contactToContact; IF firstPass THEN { -- don't get pinsOnTrialSeg until needed firstPass _ FALSE; pinsOnTrialSeg _ RouteChannel.GetPinsOnSeg[trialSeg]}; FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, adjTrack], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO IF existingSeg.net.netNum # trialSeg.net.netNum OR existingSeg.net.netPart # trialSeg.net.netPart THEN {-- check to see if contacts interfere with each other IF segLayer = trunk AND existingSeg.routingLayer = trunk THEN { pinsOnExistSeg: RouteChannel.ChanPinList _ RouteChannel.GetPinsOnSeg[existingSeg]; FOR trialPins: RouteChannel.ChanPinList _ pinsOnTrialSeg, trialPins.rest WHILE trialPins # NIL AND fitsSoFar DO trialPin: RouteChannel.ChanPin _ trialPins.first; FOR existPins: RouteChannel.ChanPinList _ pinsOnExistSeg, existPins.rest WHILE existPins # NIL AND fitsSoFar DO existPin: RouteChannel.ChanPin _ existPins.first; fitsSoFar _ ~ContactCheck[trialPin, trialPos, existPin, adjTrackPos, contactToContact]; ENDLOOP; ENDLOOP}; <> IF ABS[trialPos - adjTrackPos] < trialSeg.qWidth/2 + qTrunkTrunk + existingSeg.qWidth/2 THEN fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, qTrunkTrunk]}; ENDLOOP}; ENDLOOP}; -- FitSegmentAdjTracks FitSegmentConstraints: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; graph: RouteDiGraph.Graph _ chanData.constraints; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; <<>> <> IF activeTrackSpec.freeArea = above THEN { <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, TRUE]; <<>> <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, FALSE]}; <> IF activeTrackSpec.freeArea = below THEN { <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, TRUE]; <<>> <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, FALSE]}; RETURN[fitsSoFar]}; -- FitSegmentConstraints EndOverlapCheck: PROCEDURE[seg1, seg2: RouteChannel.Segment, dist: Route.Number] RETURNS [overlap: BOOLEAN] = { leftPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanLeft]; left1Loc: Route.Number _ leftPin1.pinPosition.pLoc - leftPin1.pWidth/2; rightPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanRight]; right1Loc: Route.Number _ rightPin1.pinPosition.pLoc + rightPin1.pWidth/2; leftPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanLeft]; left2Loc: Route.Number _ leftPin2.pinPosition.pLoc - leftPin2.pWidth/2; rightPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanRight]; right2Loc: Route.Number _ rightPin2.pinPosition.pLoc + rightPin2.pWidth/2; gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist}; OverlapCheck: PROCEDURE[seg1, seg2: RouteChannel.Segment, dist: Route.Number] RETURNS [overlap: BOOLEAN] = { overlap _ EndOverlapCheck[seg1, seg2, dist] OR EndOverlapCheck[seg2, seg1, dist]}; ContactCheck: PROCEDURE[pin1: RouteChannel.ChanPin, qPos1: Route.Number, pin2: RouteChannel.ChanPin, qPos2, dist: Route.Number] RETURNS [overlap: BOOLEAN _ FALSE] = BEGIN IF ABS[qPos1 - qPos2] < dist THEN { left1Loc: Route.Number _ pin1.pinPosition.pLoc - pin1.pWidth/2; right1Loc: Route.Number _ pin1.pinPosition.pLoc + pin1.pWidth/2; left2Loc: Route.Number _ pin2.pinPosition.pLoc - pin2.pWidth/2; right2Loc: Route.Number _ pin2.pinPosition.pLoc + pin2.pWidth/2; gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist}; END; -- ContactCheck ConstraintCheck: PROCEDURE[graph: RouteDiGraph.Graph, segment: RouteChannel.Segment, direction: RouteChannel.AboveOrBelow, track: RouteChannel.MaxTracks, mustBePlaced: BOOLEAN] RETURNS [constrained: BOOLEAN _ FALSE] = { <> CheckConstraints: RouteDiGraph.EnumArcsFromNodeProc = { nextNode: RouteDiGraph.Node _ IF direction = in THEN arc.inferiorNode ELSE arc.superiorNode; nodeInfo: RouteChannel.SegmentConstraint _ NARROW[nextNode.nodeInfo]; segment: RouteChannel.Segment _ nodeInfo.segment; IF segment.trackNum = 0 THEN { IF mustBePlaced THEN quit _ TRUE} -- segment must be placed ELSE { IF direction = out THEN quit _ track >= segment.trackNum ELSE quit _ track <= segment.trackNum}; IF ~quit THEN quit _ RouteDiGraph.EnumArcsFromNode[graph, nextNode, direction, CheckConstraints]}; node: RouteDiGraph.Node _ segment.constraintNode; gDirection: RouteDiGraph.Direction _ IF direction = above THEN out ELSE in; constrained _ RouteDiGraph.EnumArcsFromNode[graph, node, gDirection, CheckConstraints]; }; GetNextSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, segProc: SegProc] RETURNS [nextSegSpec: RouteChannel.ActiveSegSpec _ NIL] = { <> CheckSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN { [quit, trialSegSpec] _ segProc[pin.conctSeg[whichSide], activeTrackSpec]; IF ~quit THEN [quit, trialSegSpec] _ segProc[pin.altConctSeg[whichSide], activeTrackSpec]}}; found: BOOLEAN _ FALSE; whichSide: RouteChannel.ChanLRSide; pinPos: RouteChannel.ZMPinsOnCh; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; lastIndex: RouteChannel.ZMPinsOnCh _ chanData.chanPins.count; trialSegSpec: RouteChannel.ActiveSegSpec; <> SELECT activeTrackSpec.going FROM leftToRight => { IF activeSegSpec = NIL THEN pinPos _ 1 ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pinIndex; whichSide _ chanRight; FOR posIndex: RouteChannel.MPinsOnCh IN [pinPos .. lastIndex] WHILE ~ found DO pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex]; found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs] ENDLOOP}; -- posIndex rightToLeft => { IF activeSegSpec = NIL THEN pinPos _ lastIndex ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pinIndex; whichSide _ chanLeft; FOR posIndex: RouteChannel.MPinsOnCh DECREASING IN [pinPos .. 1] WHILE ~ found DO pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex]; found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs] ENDLOOP}; -- posIndex ENDCASE; IF found THEN nextSegSpec _ trialSegSpec; IF debug AND nextSegSpec # NIL THEN IF nextSegSpec.seg # NIL THEN {TerminalIO.WriteRope[Rope.Cat["\n New segment: ", nextSegSpec.seg.net.name, ", ", RoutePrivate.RoutingLayerName[nextSegSpec.segLayer]]]}; }; -- GetNextSegment FollowingSeg: PUBLIC PROCEDURE [routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, includeUnPlaced: BOOLEAN] RETURNS [nextSegSpec: RouteChannel.ActiveSegSpec _ NIL] = { <> <> <> CheckFitSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN {seg: RouteChannel.Segment _ pin.conctSeg[existingSide]; IF seg # NIL THEN IF seg = activeSegSpec.seg THEN {trialSegSpec: RouteChannel.ActiveSegSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: pin.conctSeg[newSide]]]; IF trialSegSpec.seg # NIL THEN IF ~includeUnPlaced OR trialSegSpec.seg.trackNum = 0 THEN nextSegSpec _ trialSegSpec; quit _ TRUE}}}; existingSide, newSide: RouteChannel.ChanLRSide; pinPos: RouteChannel.PinPosition; found: BOOLEAN _ FALSE; SELECT activeTrackSpec.going FROM leftToRight => {pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition; existingSide _ chanLeft; newSide _ chanRight}; rightToLeft => {pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition; existingSide _ chanRight; newSide _ chanLeft}; ENDCASE; <> found _ RouteChannel.EnumPins[routingArea, pinPos, CheckFitSegs] }; -- FollowingSeg AnalyzeResult: PROCEDURE[routingArea: Route.RoutingArea] RETURNS [result: Route.RoutingResult] = { RemoveTrackIfPossible: PROCEDURE[routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.MaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; IF track = stopTrack THEN track _ stopTrack; IF ~chanTracks.tracks[track].blocked AND ~chanTracks.tracks[track].keep THEN numTracks _ RemoveTrack[routingArea, track, oldNumTracks] -- assume track can be removed ELSE numTracks _ oldNumTracks}; <> <> <> <> <> <<{BuildTrackSpec [routingArea, nextLowerTrack, numTracks, leftToRight, above, lowerTrackSpec];>> <> <> <<{BuildTrackSpec [routingArea, nextUpperTrack, numTracks, leftToRight, above, upperTrackSpec];>> <> <> <> CheckRules: PROCEDURE[routingArea: Route.RoutingArea, trackSpec: RouteChannel.ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; rules: Route.DesignRules _ routingArea.rules; track: RouteChannel.MaxTracks _ trackSpec.track; FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, track], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO segSpec.seg _ existingSeg; segSpec.segLayer _ existingSeg.routingLayer; fitsSoFar _ FitSegmentAdjTracks[routingArea, segSpec, trackSpec, maxTrack]; ENDLOOP}; EnumExits: RouteChannel.EnumExitsProc = { <> IF constructedExit THEN IF ~RouteChannel.MembRopeList[name, breakAtExitList] THEN breakAtExitList _ CONS[name, breakAtExitList]}; EnumSegments: RouteChannel.EnumSegmentsProc = { length: Route.Number _ RouteUtil.Length[pos1, pos2]; SELECT TRUE FROM layer = metalLayer => metal1length _ metal1length + length; layer = metal2Layer => metal2length _ metal2length + length; layer = polyLayer => polyLength _ polyLength + length; ENDCASE => otherLength _ otherLength + length}; EnumPins: RouteChannel.EnumPinsProc = { <> pinLayer: Route.Layer _ CDPinObjects.GetLayer[pin.pin]; IF layer = polyLayer AND pinLayer = metalLayer OR layer = metalLayer AND pinLayer = polyLayer THEN polyToMetal _ polyToMetal +1 ELSE IF layer = metalLayer AND pinLayer = metal2Layer OR layer = metal2Layer AND pinLayer = metalLayer THEN metalToMetal2 _ metalToMetal2 +1}; EnumVias: RouteChannel.EnumViasProc = { <> IF layer1 = polyLayer AND layer2 = metalLayer OR layer1 = metalLayer AND layer2 = polyLayer THEN polyToMetal _ polyToMetal +1 ELSE IF layer1 = metalLayer AND layer2 = metal2Layer OR layer1 = metal2Layer AND layer2 = metalLayer THEN metalToMetal2 _ metalToMetal2 +1}; EnumIncompletes: RouteChannel.EnumIncompletesProc = { <> numIncompletes _ numIncompletes +1; IF ~RouteChannel.MembRopeList[name, incompleteList] THEN incompleteList _ CONS[name, incompleteList]}; ElimUselessTracks: RouteChannel.EachTrackActionProc = { <<>> <> IF RouteChannel.TrackSeg[routingArea, trackIndex] = NIL THEN -- this track has no segments numTracks _ RemoveTrackIfPossible[routingArea, trackIndex, numTracks]}; <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; metal1length, metal2length, polyLength, otherLength: Route.Number _ 0; polyToMetal, metalToMetal2, numIncompletes: NAT _ 0; technology: CD.Technology _ NARROW[routingArea.rules.technology]; metalLayer: Route.Layer _ CD.FetchLayer[technology, $met]; metal2Layer: Route.Layer _ CD.FetchLayer[technology, $met2]; polyLayer: Route.Layer _ CD.FetchLayer[technology, $pol]; rect: Route.Rect; loc1, loc2: Route.Position; incompleteList: LIST OF Rope.ROPE _ NIL; breakAtExitList: LIST OF Rope.ROPE _ NIL; numTracks: RouteChannel.ZMaxTracks _ chanTracks.count; lowerTrackSpec: RouteChannel.ActiveTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec]; upperTrackSpec: RouteChannel.ActiveTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec]; segSpec: RouteChannel.ActiveSegSpec _ NEW[RouteChannel.ActiveSegSpecRec]; <<>> <> <> <> IF parms.routerUsed = channel THEN { [] _ RouteChannel.EnumTracks[routingArea, ElimUselessTracks]; chanTracks.count _ numTracks}; loc1 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]]; IF parms.routerUsed = channel THEN { thisChanWidth: Route.Number _ RouteChannel.ChannelWidth[routingArea]; loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]]} ELSE IF parms.routerUsed = switchBox THEN loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]]; rect _ [loc1.x, loc1.y, loc2.x, loc2.y]; [] _ RouteChannel.GetRouting[routingArea, rect, NIL, EnumSegments, EnumPins, EnumVias, EnumExits, EnumIncompletes]; result _ NEW[Route.RoutingResultRec _ [routingArea, polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList, breakAtExitList]]; }; -- AnalyzeResult CanConvert: PROCEDURE[routingArea: Route.RoutingArea, seg: RouteChannel.Segment] RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone _ trunk] = { -- see if this trunk routingLayer seg can be pulled down onto the branch routingLayer chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; leftPin: RouteChannel.PinPosition _ seg.exteriorPins[chanLeft].pinPosition; rightPin: RouteChannel.PinPosition _ seg.exteriorPins[chanRight].pinPosition; segLength: Route.Number _ rightPin.pLoc - leftPin.pLoc; IF segLength <= chanData.chanParms.maxToConvert AND leftPin.pinIndex = rightPin.pinIndex + 1 THEN segLayer _ branch}; RemoveTrack: PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; trackNum, oldTrackNum: RouteChannel.MaxTracks; FOR upperTrack: RouteChannel.MaxTracks DECREASING IN [track+1 .. chanTracks.count] DO chanTracks.tracks[upperTrack].oldTrackNum _ chanTracks.tracks[upperTrack].trackNum; chanTracks.tracks[upperTrack].trackNum _ chanTracks.tracks[upperTrack-1].trackNum; ENDLOOP; IF track # 1 THEN chanTracks.tracks[track].trackNum _ chanTracks.tracks[track-1].trackNum; FOR upperTrack: RouteChannel.MaxTracks IN [track+1 .. chanTracks.count] DO trackNum _ chanTracks.tracks[upperTrack].trackNum; oldTrackNum _ chanTracks.tracks[upperTrack].oldTrackNum; chanTracks.tracks[trackNum].firstSeg _ chanTracks.tracks[oldTrackNum].firstSeg; ENDLOOP; IF track # chanTracks.count THEN { oldTrackNum _ chanTracks.tracks[chanTracks.count].oldTrackNum; chanTracks.tracks[oldTrackNum].firstSeg _ NIL}; numTracks _ oldNumTracks - 1}; PutBackTrack: PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; trackNum, oldTrackNum: RouteChannel.MaxTracks; IF track < chanTracks.count THEN {actualTrack: RouteChannel.MaxTracks _ chanTracks.tracks[track+1].trackNum; FOR upperTrack: RouteChannel.MaxTracks DECREASING IN [track+1 .. chanTracks.count] DO trackNum _ chanTracks.tracks[upperTrack].trackNum; oldTrackNum _ chanTracks.tracks[upperTrack].oldTrackNum; chanTracks.tracks[upperTrack].trackNum _ oldTrackNum; chanTracks.tracks[oldTrackNum].firstSeg _ chanTracks.tracks[trackNum].firstSeg; ENDLOOP; chanTracks.tracks[actualTrack].firstSeg _ NIL}; numTracks _ oldNumTracks + 1}; BuildTrackSpec: PROCEDURE [routingArea: Route.RoutingArea, track, maxTracks: RouteChannel.ZMaxTracks, going: RouteChannel.GoingDirection, freeArea: RouteChannel.AboveOrBelow, trackSpec: RouteChannel.ActiveTrackSpec] = { chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; influence: Route.Number _ RouteChannel.InfluenceTracks[routingArea, parms.widestTrunk] + 1; trackSpec.minActTrack _ MAX[track - influence, 1]; trackSpec.maxActTrack _ MIN[track + influence, maxTracks]; trackSpec.track _ track; trackSpec.going _ going; trackSpec.freeArea _ freeArea}; END.